脚踏实地之常见数据结构

数据结构是什么，首先出现在脑海中的可能是那本厚厚的数据结构大学教材，我想大部分猿在大学时可能没有好好上过这门课，那时根本不知道学了可以有什么用，所以大家可能在聊天、在睡觉、在玩游戏。。。，现在回顾下还是很遗憾当时没有好好学习这门功课，工作这么多年后，发现了解这些数据结构还是非常有必要的，今天就来记录下一些常见的数据结构，也是自己对数据结构学习的一个起点。。。

数据结构，是以某种布局方式存储数据的容器。
数据结构，存储分为顺序存储结构和链式存储结构。

常见数据结构

常见的数据结构有数组、栈、队列、链表、散列表、树、图。
下面主要介绍下平时开发会遇到的几个

数组

数组，在内存中连续存储多个元素的结构，在内存中的分配是连续的，可以通过下标进行访问。

• 优点
  根据索引进行遍历数组方便；
  根据索引进行查询元素速度快；
• 缺点
  大小固定；
  增删操作慢；

栈

栈，一种操作受限的线性表，只允许从一端插入和删除数据，也就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素，即LIFO。栈有两种操作，即进栈和出栈。

栈的代码实现

@interface LStack()
//定义容器
@property (nonatomic, strong) NSMutableArray *dataContainer;

@end

//实现基本操作
//压栈操作
- (void)push:(id)obj {
    if (obj) {
        [self.dataContainer addObject:obj];
    }
}

//出栈操作，并返回出栈的元素
- (id)pop {
    if (![self isEmpty]) {
        id obj = [self.dataContainer lastObject];
        [self.dataContainer removeLastObject];
        NSLog(@"出栈成功，出栈元素为：%@",obj);
        return obj;
    }
    NSLog(@"出栈失败，当前为空栈");
    return nil;
}

//判断是否为空栈
- (BOOL)isEmpty {
    if (self.dataContainer && self.dataContainer.count > 0) {
        return NO;
    }
    return YES;
}

//取出栈顶元素
- (id)topObj {
    if (self.dataContainer && self.dataContainer.count > 0) {
        return [self.dataContainer lastObject];
    }
    return nil;
}

调用

LStack *stack = [LStack new];
NSLog(@"当前%@空栈",[stack isEmpty]?@"为":@"不为");
        
[stack push:@"路飞"];
[stack push:@"索隆"];
NSLog(@"当前%@空栈",[stack isEmpty]?@"为":@"不为");
NSLog(@"栈顶元素：%@",[stack topObj]);

打印结果

2020-03-08 16:35:55.148372+0800 20200308-数据结构&算法[40480:1719141] 当前为空栈
2020-03-08 16:35:55.148907+0800 20200308-数据结构&算法[40480:1719141] 当前不为空栈
2020-03-08 16:35:55.149019+0800 20200308-数据结构&算法[40480:1719141] 栈顶元素：索隆

队列

队列，也是一种操作受限的线性表，不同的是，队列需要在一端进行添加元素，在另一端进行取出元素，即FIFO。队列有两种操作，即入队和出对。

队列代码实现

//定义容器
@interface LQueue ()

@property (nonatomic, strong) NSMutableArray *dataContainer;

@end

//初始化容器
- (instancetype)init {
    if (self = [super init]) {
        self.dataContainer = [NSMutableArray array];
    }
    return self;
}
//实现基本操作
//入队操作
- (void)push:(id)obj {
    if (obj) {
        [self.dataContainer addObject:obj];
    }
}

//出队操作，并返回出对的元素
- (id)pop {
    if (![self isEmpty]) {
        id obj = [self.dataContainer firstObject];
        [self.dataContainer removeObjectAtIndex:0];
        NSLog(@"出栈成功，出栈元素为：%@",obj);
        return obj;
    }
    NSLog(@"出栈失败，当前为空栈");
    return nil;
}

//判断是否为空队列
- (BOOL)isEmpty {
    if (self.dataContainer && self.dataContainer.count > 0) {
        return NO;
    }
    return YES;
}

//取出队首元素
- (id)topObj {
    if (self.dataContainer && self.dataContainer.count > 0) {
        return [self.dataContainer firstObject];
    }
    return nil;
}

调用

LQueue *queue = [LQueue new];
NSLog(@"当前%@空栈",[queue isEmpty]?@"为":@"不为");
        
[queue push:@"路飞"];
[queue push:@"索隆"];
NSLog(@"当前%@空栈",[queue isEmpty]?@"为":@"不为");
NSLog(@"栈顶元素：%@",[queue topObj]);

打印结果

2020-03-08 16:46:57.267426+0800 20200308-数据结构&算法[40795:1730305] 当前为空栈
2020-03-08 16:46:57.267880+0800 20200308-数据结构&算法[40795:1730305] 当前不为空栈
2020-03-08 16:46:57.267977+0800 20200308-数据结构&算法[40795:1730305] 栈顶元素：路飞

链表

链表，是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用次序实现的。链表是由一系列结点组成的；每个结点包含数据存储区和下一个结点的地址区两部分。

• 优点
  不需要初始化容量；
  增删速度快；
• 缺点
  因含有大量的指针域，占用空间相对大；
  查找元素耗时；

链表分为单向链表和双向链表，下面我们用代码实现一个单向链表

//定义结点
struct LNode {
    int value;
    struct LNode *next;
};
//构造结点
struct LNode *constructList(void){
    //头结点
    struct LNode *head = NULL;
    //记录当前尾结点
    struct LNode *curEnd = NULL;
    for (int i=0; i < 4; i++) {
        struct LNode *tmpNode = malloc(sizeof(struct LNode));
        tmpNode->value = i;
        //头结点为空，该结点即为头结点
        if (head == NULL) {
            head = tmpNode;
        }
        else {
            curEnd->next = tmpNode;
        }
        curEnd = tmpNode;
    }
    return head;
}
//打印链表
void listLog(struct LNode *head){
    struct LNode *tmp = head;
    while (tmp != NULL) {
        NSLog(@"结点value：%ld", tmp->value);
        tmp = tmp->next;
    }
}

打印结果为：

2020-03-08 16:19:17.102871+0800 20200308-数据结构&算法[40032:1702590] 结点value：0
2020-03-08 16:19:17.103411+0800 20200308-数据结构&算法[40032:1702590] 结点value：1
2020-03-08 16:19:17.103495+0800 20200308-数据结构&算法[40032:1702590] 结点value：2
2020-03-08 16:19:17.103567+0800 20200308-数据结构&算法[40032:1702590] 结点value：3

树

树，是由结点或顶点和边组成的且不存在任何环的一种数据结构。
它的特点是：

• 每个结点有零个或者多个子结点；
• 没有父结点的结点称为根结点；
• 每一个非根结点有且只有一个父结点；
• 除了根结点外，每个子结点可以分为多个不相交的子树；
  最常用的一种树，二叉树，它的特点是：
• 每个结点最多有两颗子树；
• 左子树和右子树是由顺序的；
• 即使某个结点只有一个子树，也要区分左右子树；

散列表

散列表，也叫哈希表，是根据key和value直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
哈希函数，得到key的固定算法就叫做哈希函数。
哈希表的应用有很多：字典的底层实现、weak的底层实现、自动释放池的底层实现等等。

生活如此美好，今天就点到为止。。。