什么是數(shù)據(jù)結(jié)構(gòu)？
接下來(lái)我們手寫一個(gè)動(dòng)態(tài)數(shù)組
首先動(dòng)態(tài)數(shù)組的接口設(shè)計(jì)如下：
實(shí)現(xiàn)代碼如下：
#import
? ? ? ? ? ? ? ? ? ? //修飾屬性的類型，如果一個(gè)類屬性的類型并不確定，那么就可以通過(guò)創(chuàng)建對(duì)象的時(shí)候來(lái)控制類的類型
@interface ArrayList? <__covariant objectType> : NSObject
//元素?cái)?shù)量
@property (readonly) NSUInteger count;
@property (nullable, nonatomic, readonly) id firstObject;
@property (nullable, nonatomic, readonly) id lastObject;
/**
默認(rèn)初始化
@return 實(shí)例對(duì)象
*/
+ (instancetype)arrary;
/**
類方法初始化
@param numItems 初始數(shù)量
@return 實(shí)例對(duì)象
*/
+ (instancetype)arrayWithCapacity:(NSUInteger)numItems;
/**
對(duì)象方法初始化
@param numItems 初始數(shù)量
@return 實(shí)例對(duì)象
*/
- (instancetype)initWithCapacity:(NSUInteger)numItems;
/**
取某個(gè)位置的元素
@param numItems 參數(shù)
*/
- (objectType)objectAtIndex:(NSUInteger)numItems;
/**
查看某個(gè)元素的下標(biāo)
@param anObject 某個(gè)元素
@return index
*/
- (objectType)indexOfobject:(objectType)anObject;
/**
是否包含某個(gè)元素
@param anObject 某個(gè)元素
@return 是否包含
*/
- (BOOL)containsObject:(objectType)anObject;
/**
添加元素
@param anObject 要添加的元素
*/
- (void)addObject:(objectType)anObject;
/**
插入某個(gè)元素
@param anObject 某個(gè)元素
@param index 要插入的下標(biāo)
*/
- (void)insertObject:(objectType)anObject atIndex:(NSUInteger)index;
/**
替換某個(gè)位置的元素
@param index 要替換的位置
@param anObject 要替換的參數(shù)元素
*/
- (void)replaceObjectAtIndex:(objectType)index withObject:(objectType)anObject;
/**
刪除所有元素
*/
- (void)removeAllObjects;
/**
刪除最后一個(gè)元素
*/
- (void)removeLastObjects;
/**
刪除某個(gè)下標(biāo)的元素
@param index index
*/
- (void)removeObjectAtIndex:(NSUInteger)index;
/**
刪除某個(gè)元素
@param anObject 某個(gè)元素
*/
- (void)removeObject:(objectType)anObject;
@end
#import "ArrayList.h"
static const int DEFAULT_CAPACITY = 10;
static const int ELEMENT_NOT_FOUND = -1;
typedef void* AnyObject;
@interface ArrayList? ()
{
? ? AnyObject *_array; //／<本來(lái)是想用 objectType ，但是calloc的去接收的時(shí)候會(huì)出野指針錯(cuò)誤，另外作用域只到interface>
? ? NSInteger _size;
? ? NSInteger _capacity;
}
@end
@implementation ArrayList
/**
默認(rèn)初始化
@return 實(shí)例對(duì)象
*/
+ (instancetype)arrary{
? return? [[self alloc] initWithCapacity:DEFAULT_CAPACITY];
}
/**
類方法初始化
@param numItems 初始數(shù)量
@return 實(shí)例對(duì)象
*/
+ (instancetype)arrayWithCapacity:(NSUInteger)numItems{
? ? return? [[self alloc] initWithCapacity:numItems];
}
/**
對(duì)象方法初始化
@param numItems 初始數(shù)量
@return 實(shí)例對(duì)象
*/
- (instancetype)initWithCapacity:(NSUInteger)numItems{
? ? _capacity = numItems < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : numItems;
? ? _array = (calloc(numItems, sizeof(AnyObject)));
? ? _size = 0;
? ? return self;
}
/**
取某個(gè)位置的元素
@param numItems 參數(shù)
*/
- (AnyObject)objectAtIndex:(NSUInteger )numItems{
? ? if (numItems >= _size) {
? ? ? ? @throw [NSException exceptionWithName:@"Array is out of bounds" reason:@"out of bounds" userInfo:nil];
? ? ? ? return nil;
? ? }
? ? return _array[numItems];
}
/**
查看某個(gè)元素的下標(biāo)
@param anObject 某個(gè)元素
@return index
*/
- (AnyObject)indexOfobject:(id)anObject{
? ? for (int i = 0; i < _size; i ++) {
? ? ? ? if ([anObject isEqual:anObject]){
? ? ? ? ? ? return i;
? ? ? ? }
? ? }
? ? return ELEMENT_NOT_FOUND;
}
/**
是否包含某個(gè)元素
@param anObject 某個(gè)元素
@return 是否包含
*/
- (BOOL)containsObject:(AnyObject)anObject{
? ? return [self indexOfobject:(__bridge id)(anObject)] != ELEMENT_NOT_FOUND;
}
/**
添加元素
@param anObject 要添加的元素
*/
- (void)addObject:(id)anObject{
? ? [self insertObject:(anObject) atIndex:_size];
}
- (NSUInteger)count{
? ? return _size;
}
- (void)insertObject:(id)anObject atIndex:(NSUInteger)index{
? ? ? ? [self ensureCapacity:_size + 1];
? ? ? ? ///交換索引位置
? ? ? ? if (self.count > 0 ) {
? ? ? ? ? ? for(NSInteger i = _size - 1 ; i >= index ; i--)
? ? ? ? ? ? _array[i + 1] = _array[i];
? ? ? ? }
? ? ? ? self->_array[index] = (__bridge_retained AnyObject)(anObject);
? ? ? ? _size++;
}
/**
替換某個(gè)位置的元素
@param index 要替換的位置
@param anObject 要替換的參數(shù)元素
*/
- (void)replaceObjectAtIndex:(NSInteger)index withObject:(AnyObject)anObject{
? ? _array[index] = anObject;
}
/**
刪除所有元素
*/
- (void)removeAllObjects{
? ? for (int i = 0; i < _size - 1; i++) {
? ? ? ? _array[i] = NULL;
? ? }
? ? [self resetArray];
}
/**
數(shù)組重置
*/
- (void) resetArray {
? ? _size = 0;
//? ? if (_array != NULL)
//? ? _array[_size] = NULL;
//? ? free(_array);
//? ? _capacity = DEFAULT_CAPACITY;
//? ? _array = calloc(_capacity, sizeof(AnyObject));
}
- (void)removeObjectAtIndex:(NSUInteger)index{
? ? if (index >= _size) {
? ? ? ? @throw [NSException exceptionWithName:@"Array is out of bounds" reason:@"out of bounds" userInfo:nil];
? ? }
? ? for (int i = index + 1; i < _size; i++) {
? ? ? _array[i -1 ] = _array[i];
? ? }
? ? _size--;
? ? _array[_size] = NULL;
? ? if (_size == _capacity / 2) {
? ? ? ? NSInteger newCapacity = _capacity / 2;
? ? ? ? AnyObject *newArr = (calloc(newCapacity , sizeof(AnyObject)));
? ? ? ? for (int i = 0; i < _size; i++) {
? ? ? ? ? ? newArr[i] = _array[i];
? ? ? ? }
? ? ? ? _array = newArr;
? ? ? ? _capacity = newCapacity;
? ? ? ? NSLog(@"新容量 %zd",newCapacity);
? ? }
}
/**
刪除某個(gè)元素
@param anObject 某個(gè)元素
*/
- (void)removeObject:(id)anObject{
? ? for (int i = 0; i < _size; i ++) {
? ? ? ? if ([anObject? isEqual:(__bridge id)(_array[i])]) {
? ? ? ? ? ? [self removeObjectAtIndex:i];
? ? ? ? }
? ? }
}
/**
擴(kuò)容
*/
- (void)ensureCapacity:(NSInteger)capacity{
? ? if (capacity <= _capacity) {
? ? ? ? return;
? ? }
? ? NSInteger newCapacity = _capacity + (_capacity >> 1);
? ? AnyObject *newArr = (calloc(newCapacity , sizeof(AnyObject)));
? ? for (int i = 0; i < _size; i++) {
? ? ? ? newArr[i] = _array[i];
? ? }
? ? _array = newArr;
? ? _capacity = newCapacity;
? ? NSLog(@"新容量 %zd",newCapacity);
}
- (NSString *)description {
? ? NSMutableString *string = [NSMutableString stringWithFormat:@"\nArrayList %p : [ \n" ,self];
? ? for (int i = 0; i<_size; i++) {
? ? ? ? AnyObject obj = _array[i];
? ? ? ? [string appendFormat:@"%@",(__bridge id)obj];
? ? ? ? if (i<_size-1) {
? ? ? ? ? ? [string appendString:@" , \n"];
? ? ? ? }
? ? }
? ? [string appendString:@"\n]\n"];
? ? return string;
}
@end
在寫動(dòng)態(tài)數(shù)組的過(guò)程中發(fā)現(xiàn)幾個(gè)問題。
1.范型作用域只有@interface
2.free（）函數(shù)并沒有將數(shù)組中的元素釋放。。。
3.擴(kuò)容realloc是一個(gè)提高性能的方向，malloc，calloc，realloc都能實(shí)現(xiàn)這個(gè)功能。。
