数据结构2-自定义动态数组

栏目: IOS · 发布时间: 5年前

内容简介：Objective-C中的NSMutableArray就是一个动态数组，不用指定数组的长度就可以放心向里边添加元素，不需要考虑溢出的问题。实现动态数据的方式非常多，例如对静态数组进行封装扩容或者链表，甚至多种方式混合使用，根据数据量的大小来动态改变自己的数据结构。这里就使用最简单的根据静态数据动态扩容的方式，来实现一个动态数组。为了实现一套完整的自定义数据结构，这里对静态数组的封装，使用的是上一篇文章中创建的自定义静态数组JKRArray。动态数组的应该提供的功能仿照NSMutableArray来设计，由于

Objective-C中的NSMutableArray就是一个动态数组，不用指定数组的长度就可以放心向里边添加元素，不需要考虑溢出的问题。实现动态数据的方式非常多，例如对静态数组进行封装扩容或者链表，甚至多种方式混合使用，根据数据量的大小来动态改变自己的数据结构。这里就使用最简单的根据静态数据动态扩容的方式，来实现一个动态数组。

为了实现一套完整的自定义数据结构，这里对静态数组的封装，使用的是上一篇文章中创建的自定义静态数组JKRArray。

自定义动态数组的效果

JKRArrayList *array = [JKRArrayList new];
for (NSUInteger i = 0; i < 60; i++) {
    [array addObject:[Person personWithAge:i]];
}
NSLog(@"添加后 %@", array);

打印：
--- 扩容: 16 -> 24 ---
--- 扩容: 24 -> 36 ---
--- 扩容: 36 -> 54 ---
--- 扩容: 54 -> 81 ---
添加后 size=60, {
<Person: 0x10285ad50>
<Person: 0x10285ae50>
<Person: 0x10285ae70>
...
<Person: 0x10285af30>
<Person: 0x10285af50>
<Person: 0x10285af70>
}


[array removeAllObjects];
NSLog(@"清空后 %@", array);

打印：
<Person: 0x100501070> dealloc
<Person: 0x1005010b0> dealloc
<Person: 0x1005010d0> dealloc  
...
<Person: 0x10285b010> dealloc
清空后 size=0, {

}
复制代码

动态数组的基本功能

动态数组的应该提供的功能仿照NSMutableArray来设计，由于之后还会用多种链表来实现动态数组，所以还会有很多相同的处理逻辑和接口，这里先定义一个动态数组的基类：

@interface JKRBaseList<ObjectType> : NSObject {
@protected
    // 记录动态数组的当前长度
    NSUInteger _size;
}

- (NSUInteger)count;
- (void)rangeCheckForAdd:(NSUInteger)index;
- (void)rangeCheckForExceptAdd:(NSUInteger)index;
- (void)addObject:(nullable ObjectType)anObject;
- (BOOL)containsObject:(nullable ObjectType)anObject;
- (nullable ObjectType)firstObject;
- (nullable ObjectType)lastObject;
- (void)removeFirstObject;
- (void)removeLastObject;
- (void)removeObject:(nullable ObjectType)anObject;
- (_Nullable ObjectType)objectAtIndexedSubscript:(NSUInteger)idx;
- (void)setObject:(_Nullable ObjectType)obj atIndexedSubscript:(NSUInteger)idx;

@end

@interface JKRBaseList<ObjectType> (JKRBaseList)

- (void)insertObject:(nullable ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(nullable ObjectType)anObject;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)anObject;
- (void)removeAllObjects;
- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;

@end
复制代码

JKRBaseList是所有动态数组的基类，之所以有一部分在扩展里边写，是为了便于区分，扩展内的接口是需要子类实现的，而扩展之外的接口则是不同方式实现的动态数组都相同的处理，不需要子类重写，只要JKRBaseList自己实现即可。把不需要JKRBaseList实现的方法写在扩展的好处就是不需要在JKRBaseList.m里边写接口的具体实现，如果定义成它的方法声明而不去实现的话，编译器会报警告。另外分成两部分写，也便于区分哪些是子类需要实现的。

系统的NSArray和NSMutableArray都允许存放nil，这里为了扩容功能，所以允许传入并保存nil到数据中。

首先先看一下JKRBaseList里边的成员变量：NSUInteger _size; 这个变量是所有动态数组都需要的，它负责记录当前动态数组的长度。因为动态数组对外部可见的长度和内部真实的长度是不一定一致的，比如现在我们要实现的通过静态数组封装的动态数组，刚刚开始初始化的时候，动态数组对象内部保存的静态数组长度可能是16，而外部展示的长度则为0，因为还没有添加任何元素。如果用链表来实现动态数组的话，同样需要记录数组长度，否则每次都要遍历链表所有节点来累加计算数组长度。

下面先看一下JKRBaseList里边不需要子类单独实现的逻辑，依次看一下为什么它们是公用的，以及它们是如何实现的。

注：有些公共接口需要调用子类需要重写的接口来实现具体功能，先不要考虑子类如何实现，假设子类已经实现，只需要调用对于接口实现完整功能即可。

公共接口的实现

以下方法全部在JKRBaseList.m中实现，不需要子类重写。

获取数组的长度

因为动态数组的长度保存在成员变量_size中，只需要返回_size即可

时间复杂度: O(1)

- (NSUInteger)count {
    return _size;
}
复制代码

添加元素时的越界检查

因为动态数组可以尾部添加元素的特性，添加元素的时越界检查范围应该是：index > 0 && index <= _size。index可以等于数组的长度，此时相当于在数组尾部追加一个元素。

- (void)rangeCheckForAdd:(NSUInteger)index {
    // index可以等于_size，相当于在数组尾部追加元素
    if (index < 0 || index > _size) {
        [self indexOutOfBounds:index];
    }
}

- (void)indexOutOfBounds:(NSUInteger)index {
    NSAssert(NO, @"index: %zd, size: %zd", index, _size);
}
复制代码

除添加之外的越界检查

除了添加之外，其他情况下，操作数组的index应该在数组长度范围之内：index > 0 && index < _size。

- (void)rangeCheckForExceptAdd:(NSUInteger)index {
    if (index < 0 || index >= _size) {
        [self indexOutOfBounds:index];
    }
}
复制代码

尾部追加元素

在数组尾部追加元素就相当于在 index=_size 的位置插入一个元素，插入元素的接口由子类实现。

- (void)addObject:(id)anObject {
    [self insertObject:anObject atIndex:_size];
}
复制代码

是否包含元素

是否包含元素，通过查找元素的index，判断是否找到。indexOfObject由子类实现，未找到则返回NSUIntegerMax，处理同NSArray。

- (BOOL)containsObject:(id)anObject {
    return [self indexOfObject:anObject] != NSUIntegerMax;
}
复制代码

返回第一个/最后一个元素

可以通过根据objectAtIndex接口获得，不同之处在于当数组长度为0的时候，直接返回nil，而不是调用objectAtIndex来越界报错(同NSArray处理)。

- (id)firstObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:0];
}

- (id)lastObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:_size - 1];
}
复制代码

删除第一个/最后一个元素

同返回第一次元素一样，当数组长度为0时世界返回，不会给removeObjectAtIndex去处理来越界报错。removeObjectAtIndex由子类实现。

- (void)removeFirstObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:0];
}

- (void)removeLastObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:_size - 1];
}
复制代码

删除某元素

这里调用分别调用indexOfObject接口获取元素的index，然后再调用removeObjectAtIndex接口删除元素。

- (void)removeObject:(id)anObject {
    NSUInteger index = [self indexOfObject:anObject];
    if (index != NSUIntegerMax) {
        [self removeObjectAtIndex:index];
    }
}
复制代码

支持数组的[]运算符

- (id)objectAtIndexedSubscript:(NSUInteger)idx {
    return [self objectAtIndex:idx];
}

// 这里需要区分处理
- (void)setObject:(id)obj atIndexedSubscript:(NSUInteger)idx {
    // 如果idx==_size，在数组尾部添加元素
    if (idx == _size) {
        [self insertObject:obj atIndex:idx];
    } else { // 否则替换index位置的元素
        [self replaceObjectAtIndex:idx withObject:obj];
    }
}
复制代码

子类需要单独实现的接口

首先创建JKRBaseList的子类JKRArrayList，在JKRArrayList.m中依次完成如下接口的具体实现：

- (void)insertObject:(nullable ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(nullable ObjectType)anObject;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)anObject;
- (void)removeAllObjects;
- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;
复制代码

动态数组内部成员变量

动态数组保存这一个静态数组，并且在初始化的时候创建静态数据，并指定其长度。

#define JKRARRAY_LIST_DEFAULT_CAPACITY (1<<4)

@interface JKRArrayList ()

@property (nonatomic, strong) JKRArray *array;

@end

@implementation JKRArrayList

+ (instancetype)array {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

+ (instancetype)arrayWithCapacity:(NSUInteger)capacity {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)init {
    return [self initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)initWithCapacity:(NSUInteger)capacity {
    self = [super init];
    self.array = [JKRArray arrayWithLength:capacity > JKRARRAY_LIST_DEFAULT_CAPACITY ? capacity : JKRARRAY_LIST_DEFAULT_CAPACITY];
    return self;
}
复制代码

插入元素

插入元素不是简单的在静态数组对应的index位置将元素放进去这么简单，假设现在有一个长度为6的数组，要将71插入到index为1的位置，如下图：

如果直接将71替换到index为1的位置，那么数组元素就变成了：

这样并没有增加元素，静态数组元素数量没有变化，并且原来index为1位置存放的32丢失了。

正确的做法应该是，从最后的位置开始到index位置，每一个元素都向后移动一位，将index位置空出来，然后将index位置放入新元素：

代码如下：

// 时间复杂度复杂度O(n) 
// 尾部追加元素复杂度O(1)
- (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
    // 越界检查
    [self rangeCheckForAdd:index];
    // 如果需要扩容则扩充容量
    [self ensureCapacityWithCapacity:_size + 1];
    // 添加元素
    for (NSUInteger i = _size; i > index; i--) {
        self.array[i] = self.array[i - 1];
    }
    self.array[index] = anObject;
    // 添加元素之后，_size要加1
    _size++;
}
复制代码

动态持续添加元素时，肯定会出现静态数组容量无法满足的情况，这是就需要扩充静态数组的容量，下面开始实现扩容操作。

扩容

当插入一个元素的时候，首先需要判断当前静态数组是否有足够的容量存放新添加的元素，当前动态数组内元素的个数为_size，所以静态数组需要满足其长度不小于_size + 1，即 _array.length >= _size + 1。如果静态数组容量不够，则就要进行扩容，扩容的方式就是创建一个比当前静态数组长度更大的静态数据，并将原数组数据全部复制到新数组中，然后再进添加新元素。

具体代码如下：

// 时间复杂度复杂度O(n) 
- (void)ensureCapacityWithCapacity:(NSUInteger)capacity {
    NSUInteger oldCapacity = self.array.length;
    if (oldCapacity >= capacity) {
        return;
    }
    NSUInteger newCapacity = oldCapacity + (oldCapacity >> 1);
    NSLog(@"--- 扩容: %zd -> %zd ---", oldCapacity, newCapacity);
    JKRArray *newArray = [JKRArray arrayWithLength:newCapacity];
    for (NSUInteger i = 0; i < _size; i++) {
        newArray[i] = self.array[i];
    }
    self.array = newArray;
}
复制代码

删除元素

删除元素同样需要挪动节点：

// 时间复杂度复杂度O(n) 
// 删除尾部元素复杂度O(1)
- (void)removeObjectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];
    for (NSUInteger i = index + 1; i < _size; i++) {
        self.array[i - 1] = self.array[i];
    }
    self.array[--_size] = nil;
}
复制代码

获取元素的index

获取元素的index需要遍历静态数组的全部节点，找到匹配相等的元素，并返回对于的index。

遍历的最终节点不应该是静态数组的长度，而是动态数组的长度_size。
由于自定义的数组允许传入并保存nil，所以需要对查找nil的index做单独处理，返回第一个nil对应的index。

// 时间复杂度复杂度O(n) 
- (NSUInteger)indexOfObject:(id)anObject {
    if (!anObject) {
        for (NSUInteger i = 0; i < _size; i++) {
            if (self.array[i] == nil) {
                return i;
            }
        }
    } else {
        for (NSUInteger i = 0; i < _size; i++) {
            if ([anObject isEqual:self.array[i]]) {
                return i;
            }
        }
    }
    return NSUIntegerMax;
}
复制代码

清空数组

// 时间复杂度 O(n)
- (void)removeAllObjects {
    if (_size == 0) return;
    for (NSUInteger i = 0; i < _size; i++) {
        self.array[i] = nil;
    }
    _size = 0;
}
复制代码

通过index获取元素

// 时间复杂度 O(1)
- (id)objectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];
    return self.array[index];
}
复制代码

重写打印

- (NSString *)description {
    NSMutableString *string = [NSMutableString string];
    [string appendString:[NSString stringWithFormat:@"size=%zd, {\n", _size]];
    [self enumerateObjectsUsingBlock:^(id  _Nullable obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if (idx) {
            [string appendString:@"\n"];
        }
        [string appendString:[NSString stringWithFormat:@"%@", obj]];
    }];
    [string appendString:@"\n}"];
    return string;
}
复制代码

源码

JKRBaseList.h

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface JKRBaseList<ObjectType> : NSObject {
@protected
    NSUInteger _size;
}

- (NSUInteger)count;
- (void)rangeCheckForAdd:(NSUInteger)index;
- (void)rangeCheckForExceptAdd:(NSUInteger)index;
- (void)addObject:(nullable ObjectType)anObject;
- (BOOL)containsObject:(nullable ObjectType)anObject;
- (nullable ObjectType)firstObject;
- (nullable ObjectType)lastObject;
- (void)removeFirstObject;
- (void)removeLastObject;
- (void)removeObject:(nullable ObjectType)anObject;
- (_Nullable ObjectType)objectAtIndexedSubscript:(NSUInteger)idx;
- (void)setObject:(_Nullable ObjectType)obj atIndexedSubscript:(NSUInteger)idx;

@end

@interface JKRBaseList<ObjectType> (JKRBaseList)

- (void)insertObject:(nullable ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(nullable ObjectType)anObject;
- (nullable ObjectType)objectAtIndex:(NSUInteger)index;
- (NSUInteger)indexOfObject:(nullable ObjectType)anObject;
- (void)removeAllObjects;
- (void)enumerateObjectsUsingBlock:(void (^)(_Nullable ObjectType obj, NSUInteger idx, BOOL *stop))block;

@end
复制代码

JKRBaseList.m

#import "JKRBaseList.h"

@implementation JKRBaseList

- (instancetype)init {
    if (self.class == [JKRBaseList class]) {
        NSAssert(NO, @"只能使用BaseList的子类");
    }
    self = [super init];
    return self;
}

- (NSUInteger)count {
    return _size;
}

- (void)addObject:(id)anObject {
    [self insertObject:anObject atIndex:_size];
}

- (BOOL)containsObject:(id)anObject {
    return [self indexOfObject:anObject] != NSUIntegerMax;
}

- (id)firstObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:0];
}

- (id)lastObject {
    if (_size == 0) {
        return nil;
    }
    return [self objectAtIndex:_size - 1];
}

- (void)removeFirstObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:0];
}

- (void)removeLastObject {
    if (_size == 0) {
        return;
    }
    [self removeObjectAtIndex:_size - 1];
}

- (void)removeObject:(id)anObject {
    NSUInteger index = [self indexOfObject:anObject];
    if (index != NSUIntegerMax) {
        [self removeObjectAtIndex:index];
    }
}

- (id)objectAtIndexedSubscript:(NSUInteger)idx {
    return [self objectAtIndex:idx];
}

- (void)setObject:(id)obj atIndexedSubscript:(NSUInteger)idx {
    if (idx == _size) {
        [self insertObject:obj atIndex:idx];
    } else {
        [self replaceObjectAtIndex:idx withObject:obj];
    }
}

- (void)indexOutOfBounds:(NSUInteger)index {
    NSAssert(NO, @"index: %zd, size: %zd", index, _size);
}

- (void)rangeCheckForExceptAdd:(NSUInteger)index {
    if (index < 0 || index >= _size) {
        [self indexOutOfBounds:index];
    }
}

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

@end
复制代码

JKRArrayList.h

#import "JKRBaseList.h"

NS_ASSUME_NONNULL_BEGIN

@interface JKRArrayList : JKRBaseList

+ (instancetype)array;
+ (instancetype)arrayWithCapacity:(NSUInteger)capacity;
- (instancetype)initWithCapacity:(NSUInteger)capacity;

@end

NS_ASSUME_NONNULL_END
复制代码

JKRArrayList.m

#import "JKRArrayList.h"
#import "JKRArray.h"

#define JKRARRAY_LIST_DEFAULT_CAPACITY (1<<4)

@interface JKRArrayList ()

@property (nonatomic, strong) JKRArray *array;

@end

@implementation JKRArrayList

+ (instancetype)array {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

+ (instancetype)arrayWithCapacity:(NSUInteger)capacity {
    return [[self alloc] initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)init {
    return [self initWithCapacity:JKRARRAY_LIST_DEFAULT_CAPACITY];
}

- (instancetype)initWithCapacity:(NSUInteger)capacity {
    self = [super init];
    self.array = [JKRArray arrayWithLength:capacity > JKRARRAY_LIST_DEFAULT_CAPACITY ? capacity : JKRARRAY_LIST_DEFAULT_CAPACITY];
    return self;
}

- (NSUInteger)indexOfObject:(id)anObject {
    if (!anObject) {
        for (NSUInteger i = 0; i < _size; i++) {
            if (self.array[i] == nil) {
                return i;
            }
        }
    } else {
        for (NSUInteger i = 0; i < _size; i++) {
            if ([anObject isEqual:self.array[i]]) {
                return i;
            }
        }
    }
    return NSUIntegerMax;
}

- (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
    [self rangeCheckForAdd:index];
    [self ensureCapacityWithCapacity:_size + 1];
    for (NSUInteger i = _size; i > index; i--) {
        self.array[i] = self.array[i - 1];
    }
    self.array[index] = anObject;
    _size++;
}

- (void)removeObjectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];
    for (NSUInteger i = index + 1; i < _size; i++) {
        self.array[i - 1] = self.array[i];
    }
    self.array[--_size] = nil;
}

- (void)removeAllObjects {
    if (_size == 0) return;
    for (NSUInteger i = 0; i < _size; i++) {
        self.array[i] = nil;
    }
    _size = 0;
}

- (id)objectAtIndex:(NSUInteger)index {
    [self rangeCheckForExceptAdd:index];
    return self.array[index];
}

- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(id)anObject {
    [self rangeCheckForExceptAdd:index];
    self.array[index] = anObject;
}

- (void)enumerateObjectsUsingBlock:(void (^)(id _Nullable, NSUInteger, BOOL * _Nonnull))block {
    BOOL stop = NO;
    for (NSUInteger i = 0; i < _size && !stop; i++) {
        block(self.array[i], i, &stop);
    }
}

- (void)ensureCapacityWithCapacity:(NSUInteger)capacity {
    NSUInteger oldCapacity = self.array.length;
    if (oldCapacity >= capacity) {
        return;
    }
    NSUInteger newCapacity = oldCapacity + (oldCapacity >> 1);
    NSLog(@"--- 扩容: %zd -> %zd ---", oldCapacity, newCapacity);
    JKRArray *newArray = [JKRArray arrayWithLength:newCapacity];
    for (NSUInteger i = 0; i < _size; i++) {
        newArray[i] = self.array[i];
    }
    self.array = newArray;
}

- (NSString *)description {
    NSMutableString *string = [NSMutableString string];
    [string appendString:[NSString stringWithFormat:@"size=%zd, {\n", _size]];
    [self enumerateObjectsUsingBlock:^(id  _Nullable obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if (idx) {
            [string appendString:@"\n"];
        }
        [string appendString:[NSString stringWithFormat:@"%@", obj]];
    }];
    [string appendString:@"\n}"];
    return string;
}

@end
复制代码

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Web开发权威指南

[美] Chris Aquino,、[美] Todd Gandee / 奇舞团 / 人民邮电出版社 / 2017-9 / 99.00元

本书在知名培训机构Big Nerd Ranch 培训教材的基础上编写而成，囊括了JavaScript、HTML5、CSS3等现代前端开发人员急需的技术关键点，包括响应式UI、访问远程Web 服务、用Ember.js 构建应用，等等。此外，还会介绍如何使用前沿开发工具来调试和测试代码，并且充分利用Node.js 和各种开源的npm 模块的强大功能来进行开发。全书分四部分，每部分独立完成一个项......一起来看看《Web开发权威指南》这本书的介绍吧!

码农工具