数据结构(Data Structure)

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

数据结构可透过编程语言所提供的数据类型、引用及其他操作加以实现。一个设计良好的数据结构,应该在尽可能使用较少的时间与空间资源的前提下,支持各种程序运行。

最为常见和基础的数据结构:

常见数据结构#

#

栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

通常使用链表或者数组实现。

在iOS开发中最为常见的栈结构就是 导航栏 :

UINavigationController中,使用pushViewController将一个控制器加入一个数组中,当需要返回上一个控制器的时候,在用popViewControllerAnimated将当前控制器出Pop出数组,再去获取这个数组的最后一个控制器作为返回后的显示控制器。

另外值得一提的是,我们平时接触到的 栈内存 并不是同一种东西。

  • 栈内存 是用来存放数据的内存空间,由操作系统来自动分配和管理的,某种意义上为“实际存在的物理结构”
  • 则是一种数据结构,是一种存储和组织数据的方式

队列#

队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。按先进先出(FIFO, First-In-First-Out)的原理运作。

队列 通常使用链表或者数组实现。

队列的操作方式和栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

iOS中最明显的队列结构就是莫过于 多线程操作

比如我们需要先执行某段代码,然后再执行某段代码。在GCD(iOS多线程技术)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
dispatch_queue_t queue = dispatch_queue_create("name", DISPATCH_QUEUE_SERIAL);

dispatch_async(queue, ^{

sleep(1);
NSLog(@"1");
});
dispatch_async(queue, ^{

sleep(3);
NSLog(@"2");
});
dispatch_async(queue, ^{

sleep(2);
NSLog(@"3");
});

/// 输出 1 2 3

#

堆是计算机科学中的一种特别的树状数据结构。

n个元素序列{k1, k2… ki…kn},当且仅当满足下列关系时称之为堆:(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4… n/2)

堆始于堆排序, 堆的实现通过构造二叉堆(实为二叉树的一种).

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
    • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
    • 根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

最常见的地方则是在排序算法中—堆排序

同样的, 堆内存 也并不是同一种东西。

  • 堆内存 也是用来存放数据的内存空间,但是通常在操作系统中,一般是由程序员动态分配释放的,堆的大小取决于计算机有效的虚拟内存
  • 则是一种数据结构,和 一样是一种存储和组织数据的方式

数组#

数组是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引可以计算出该元素对应的存储地址。最简单的数据结构类型是一维数组。

iOS中的数组

1
NSArray *list = @[@(0),@(1),@(2),@(3),@(4)];

散列表#

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数(散列函数),将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数(哈希函数),存放记录的数组称做散列表。

散列表数组 一样,都是开发中最为常见的数据结构。

iOS中字典的底层就是一个散列表结构(实际上大部分高级开发语言的字典都是散列表结构)

1
2
3
NSDictionary *hashTable = @{@"key1":@"content1",
@"key2":@"content2",
@"key3":@"content3"};

链表#

链表 是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

单链表:
单链表

双链表:
双链表

iOS中有链表结构的地方,比较明显的就是NSMutableArray拥有一定链表的特性,但是NSMutableArray是否就是底层使用链表却是不确定的,毕竟iOS并不开源。

1
2
3
4
5
NSMutableArray *list = @[@(0)].mutableCopy;
[list addObject:@(1)];
NSLog(@"%@",list);

// 输出 0 1

除此之外,AutoreleasePool 则应用到了双向链表结构,AutoreleasePool并没有单独的结构,而是由若干个AutoreleasePoolPage以双向链表的形式组合而成,结构如图:

  • 图中的parent指针child指针则是用于构建双向链表
  • thread当前线程
  • id *next指针作为游标指向栈顶最新add进来的autorelease对象的下一个位置
  • 一个AutoreleasePoolPage的空间被占满时,会新建一个AutoreleasePoolPage对象,连接链表(双向链表),后来的autorelease对象在新的page加入.
  • AutoreleasePoolPage每个对象会开辟4096字节内存(也就是虚拟内存一页的大小),除了上面的实例变量所占空间,剩下的空间全部用来储存autorelease对象的地址

#

是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点有零个或多个子节点
  • 没有父节点的节点称为根节点
  • 每一个非根节点有且只有一个父节点
  • 除了根节点外,每个子节点可以分为多个不相交的子树
  • 树里面没有环路

而iOS里面说到树,就不得不提到里面的UI结构了,因为iOS中的UI关系层次就是遵循树结构

#

图论(Graph theory)是组合数学的一个分支,和其他数学分支,如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。

图是一种复杂的非线性结构

图是由顶点和边组成的:(可以无边,但至少包含一个顶点)

  • 一组顶点:通常用 V(vertex) 表示顶点集合
  • 一组边:通常用 E(edge) 表示边的集合

笔记参考#

电幻国度 让自己的开源库支持CocoaPods

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×