【基础】2、动态数组

2014-02-02 | 阅读：

什么是数据结构

数据结构是计算机存储、组织数据的方式

在实际应用中，根据使用场景来选择最合适的数据结构

一、线性结构

线性表（数组、链表、栈、队列、哈希表）

二、树形结构

二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集

三、图形结构

邻接矩阵、邻接表

线性表

线性表是具有 n 个相同类型元素的有限序列（ n ≥ 0 ）

a1 是首节点（首元素）， an 是尾结点（尾元素）

a1 是 a2 的前驱， a2 是 a1 的后继

常见的线性表有
数组
链表
栈
队列
哈希表（散列表）

自实现动态数组

一、简介

数组是一种顺序存储的线性表，所有元素的内存地址是连续的

在很多编程语言中，数组都有个致命的缺点：无法动态修改容量

实际开发中，我们更希望数组的容量是可以动态改变的

二、动态数组设计

接口设计

#import <Foundation/Foundation.h>

#define ELEMENT_NOT_FOUND (-1) //未找到元素


NS_ASSUME_NONNULL_BEGIN

@protocol LCArrayDelegate <NSObject>


/// 清除所有元素
-(void)clear;

/// 元素的数量
-(int)size;

/// 是否为空
-(BOOL)isEmpty;

/// 是否包含某个元素
/// @param element 元素
-(BOOL)isContains:(nonnull id)element;


/// 添加元素到尾部
/// @param element 元素
-(void)add:(nonnull id)element;


/// 在index位置插入一个元素
/// @param index 位置
/// @param element 元素
-(void)add:(int)index element:(nonnull id)element;

/// 获取index位置的元素
/// @param index 位置
-(nonnull id)get:(int)index;

/// 设置index位置的元素,返回index位置的原元素
/// @param index 位置
/// @param element 元素
-(nonnull id)set:(int)index element:(nonnull id)element;

/// 查看元素的索引
/// @param element 元素
-(int)indexOf:(nonnull id)element;

/// 删除index位置的元素，并返回被删除的元素
/// @param index 位置
-(nonnull id)remove:(int)index;


@end

NS_ASSUME_NONNULL_END

三、父类LCArray设计实现

LCArray.h文件

#import <Foundation/Foundation.h>
#import "LCArrayDelegate.h"

NS_ASSUME_NONNULL_BEGIN

@interface LCArray : NSObject<LCArrayDelegate>{
    int     _size;          //当前数组大小
}

-(void)outOfBounds:(int)index;

-(void)rangeCheck:(int)index;

-(void)rangeCheckForAdd:(int)index;

@end

NS_ASSUME_NONNULL_END

LCArray.m文件

#import "LCArray.h"

@implementation LCArray


/// 元素的数量
-(int)size{
    return _size;
}

/// 是否为空
-(BOOL)isEmpty{
    return _size == 0;
}

/// 是否包含某个元素
/// @param element 元素
-(BOOL)isContains:(nonnull id)element{
    return [self indexOf:element] != ELEMENT_NOT_FOUND;
}

/// 添加元素到尾部
/// @param element 元素
-(void)add:(nonnull id)element{
    [self add:_size element:element];
}

- (void)add:(int)index element:(nonnull id)element { 
    
}


- (void)clear { 
    
}


- (nonnull id)get:(int)index { 
    return nil;
}


- (int)indexOf:(nonnull id)element { 
    return 0;
}


- (nonnull id)remove:(int)index { 
    return nil;
}


- (nonnull id)set:(int)index element:(nonnull id)element { 
    return nil;
}




-(void)outOfBounds:(int)index{
    NSString * reason = [NSString stringWithFormat:@"index is %d,but size is %d",index,_size];
    NSException * exception = [NSException exceptionWithName:@"数组越界" reason:reason userInfo:nil];
    @throw exception;

}

-(void)rangeCheck:(int)index{
    if (index < 0 || index >= _size) {
        [self outOfBounds:index];
    }
}

-(void)rangeCheckForAdd:(int)index{
    if (index < 0 || index > _size) {
        [self outOfBounds:index];
    }
}


@end

四、子类LCMutableArray2设计实现

LCMutableArray2.h文件

#import <Foundation/Foundation.h>
#import "LCArray.h"

NS_ASSUME_NONNULL_BEGIN

@interface LCMutableArray2: LCArray

/// 初始化
-(instancetype)init;

/// 初始化
/// @param capacity 容量大小
-(instancetype)initWithCapacity:(int)capacity;

@end

NS_ASSUME_NONNULL_END

LCMutableArray2.m文件

/**
 这只是一个测试类，很多功能还不是很完善，不能作为正常开发使用。
 比如：
    对加入对象的内存管理
    线程安全问题
 */

#import "LCMutableArray2.h"

#define DEFAULT_CAPACITY 4    //默认容量


@implementation LCMutableArray2{
    int     _capacity;      //容量大小
    void ** _elements;      //指向数组内存的首地址
}

/// 初始化
-(instancetype)init{
    return [self initWithCapacity:DEFAULT_CAPACITY];
}

/// 初始化
/// @param capacity 容量大小
-(instancetype)initWithCapacity:(int)capacity{
    self = [super init];
    if (self) {
        capacity = capacity<DEFAULT_CAPACITY?DEFAULT_CAPACITY:capacity;
        int memorySize = capacity*sizeof(void*);
        _elements = (void**)malloc(memorySize);
        memset(_elements, 0, memorySize);
        _size = 0;
        _capacity = DEFAULT_CAPACITY;
    }
    return self;
}



/// 清除所有元素
-(void)clear{
    for (int i=0; i<_size; i++) {
        _elements[i] = NULL;
    }
    _size = 0;
}


/// 在index位置插入一个元素
/// @param index 位置
/// @param element 元素
-(void)add:(int)index element:(nonnull id)element{
    
    [self rangeCheckForAdd:index];
    
    [self ensureCapacity:_size+1];
    
    for (int i=_size; i>index; i--) {
        _elements[i] = _elements[i-1];
    }
    
    _elements[index] = (__bridge void*)element;

    //该处需要对element做引用计数加1操作，否则无法持有
    _size++;
}

/// 获取index位置的元素
/// @param index 位置
-(nonnull id)get:(int)index{
    
    [self rangeCheck:index];

    return (__bridge id)_elements[index];
}

/// 设置index位置的元素
/// @param index 位置
/// @param element 元素
-(nonnull id)set:(int)index element:(nonnull id)element{
    
    [self rangeCheck:index];

    void* old = _elements[index];
    _elements[index] = (__bridge void*)element;
    return (__bridge id)old;
}

/// 查看元素的索引
/// @param element 元素
-(int)indexOf:(nonnull id)element{
    for (int i=0; i<_size; i++) {
        if([(__bridge id)_elements[i] isEqual:element]) return i;
    }
    return ELEMENT_NOT_FOUND;
}

/// 删除index位置的元素
/// @param index 位置
-(nonnull id)remove:(int)index{
    
    [self rangeCheck:index];
    
    void* old = _elements[index];
    
    for (int i = index+1; i<_size; i++) {
        _elements[i-1] = _elements[i];
    }
        
    _elements[--_size] = NULL;
    
    return (__bridge id)old;
}


#pragma mark - 内部方法

/**
 * 保证要有capacity的容量
 */
-(void)ensureCapacity:(int)capacity {

    int oldCapacity = _capacity;
    if (oldCapacity >= capacity) return;
    
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    void** newElements = malloc(newCapacity);
    
    for (int i = 0; i < _size; i++) {
        newElements[i] = _elements[i];
    }
    
    free(_elements);
    _elements = newElements;
    _capacity = newCapacity;
    
    NSLog(@"%d 扩容为 %d",oldCapacity,newCapacity);
}




-(NSString *)description{
    NSMutableString * des = [NSMutableString stringWithFormat:@"size=%d, [",_size];
    
    for (int i=0; i<_size; i++) {
        if (i!=0) {
            [des appendString:@", "];
        }
        
        [des appendFormat:@"%p",(__bridge id)_elements[i]];
        
//        if(i!=_size-1){
//            [des appendString:@", "];
//        }
    }
    
    [des appendString:@"]"];
    
    return des;
}

-(void)dealloc{
    if (_elements) {
        free(_elements);
        _elements = nil;
        NSLog(@"LCMutableArray 释放");
    }
}

@end

五、需要注意的点：

1、数组的扩容处理

2、数组内对象的内存处理

行者常至，为者常成！

JHHK

JHHK

【基础】2、动态数组

目录

什么是数据结构

线性表

自实现动态数组