iOS梦工厂

iCocos——不战胜自己，何以改变未来！

修行篇-数据结构

| Comments

概念：数据元素相互之间的关系称为结构。

有四类基本结构：集合、线性结构、树形结构、图状结构;

  • 集合结构:除了同属于一种类型外，别无其它关系

  • 线性结构:元素之间存在一对一关系常见类型有: 数组,链表,队列,栈,它们之间在操作上有所区别.例如:链表可在任意位置插入或删除元素,而队列在队尾插入元素,队头删除元素,栈只能在栈顶进行插 入,删除操作.

  • 树形结构:元素之间存在一对多关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)

  • 图形结构:元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意

总结+实战+方案

  1. 堆
  2. 栈
  3. 树（二叉树）
  4. 图
  5. 队列（循环队列）
  6. 表（单链表，线性表，hash表）

堆

堆(heap)又被为优先队列(priority queue)。

尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。

  • 堆是实现调度器(Linux:使用nice控制)的理想数据结构。

  • 插入元素，删除最大优先级元素

  • 堆的一个经典的实现是完全二叉树(complete binary tree)。这样实现的堆成为二叉堆(binary heap)。

完全二叉树是增加了限定条件的二叉树。假设一个二叉树的深度为n。为了满足完全二叉树的要求，该二叉树的前n-1层必须填满，第n层也必须按照从左到右的顺序被填满

栈

特性：后进先出

注意：如果栈为空的时候，会导致下溢

栈中的每个元素称为一个frame。而最上层元素称为top frame。栈只支持三个操作， pop, top, push。

pop取出栈中最上层元素(8)，栈的最上层元素变为早先进入的元素(9)。

top查看栈的最上层元素(8)。

push将一个新的元素(5)放在栈的最上层。

实现方式

  • 数组实现：需要一个变量来标记栈顶位置
  • 链表实现：插入元素时对表头操作需要注意

常见题目

  • 括号匹配
  • 翻转字符串
  • 模拟递归（N皇后问题）

栈最经典的计算机应用是函数调用。每个进程都会有一个栈，每个frame中记录了调用函数的参数，自动变量和返回地址。当该函数调用一个新的函数时，栈中会 push一个frame。当函数执行完毕返回时，该frame会pop，从而进入调用该函数的原函数，继续执行

+由于栈是限定了操作的有序的元素集合，所以我们既可以在数组的基础上来实现栈，也可以在表的基础上来实现栈。如果使用数组来实现栈，我们需要预留充足的空间供栈使用，并需要一个下标来记录最上层元素的位置

树

树(Tree)是元素的集合

严格的定义树的方法：

  1. 树是元素的集合。

  2. 该集合可以为空。这时树中没有元素，我们称树为空树 (empty tree)。

  3. 如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。

上面的第三点是以递归的方式来定义树，也就是在定义树的过程中使用了树自身(子树)。由于树的递归特征，许多树相关的操作也可以方便的使用递归实现

  • 二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点

  • 二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大

    叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:

    1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)

    2. 如果x小于根节点，那么搜索左子树

    3. 如果x大于根节点，那么搜索右子树

    二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。

图

图(graph)是一种比较松散的数据结构。它有一些节点(vertice)，在某些节点之间，由边(edge)相连。节点的概念在树中也出现过，我们通常在节点中储存数据。边表示两个节点之间的存在关系。在树中，我们用边来表示子节点和父节点的归属关系。树是一种特殊的图，但限制性更强一些

  • 定义：图G=(V,E)是由节点的集合V和边的集合E构成的。一个图的所有节点构成一个集合V。一个边可以表示为(v1,v2)，其中v1,v2∈V，即两个节点。如果(v1,v2)有序，即(v1,v2)与(v2,v1)不同，那么图是有向的(directed)。有序的边可以理解为单行道，只能沿一个方向行进。如果(v1,v2)无序，那么图是无向的(undirected)。无序的边可以理解成双向都可以行进的道路。一个无序的边可以看作连接相同节点的两个反向的有序边，所以无向图可以理解为有向图的一种特殊情况

一种简单的实现图的方法是使用二维数组

图的组织方式比较松散，自由度比较大，但也造成比较高的算法复杂度

队列

队列最大的特征是First In, First Out (FIFO，先进先出)

队列(queue)是一个简单而常见的数据结构。队列也是有序的元素集合。

  • 队首的元素离开队列(dequeue)，和新元素加入队尾(enqueue)。

应用

  • 一个经典的应用是消息队列(参考Linux进程间通信)，实际上就是利用队列来分配有限的进程。
  • 还有FIFO文件(哦，你可以看到，这种文件叫做FIFO，肯定是和队列有关)，用以实现管道传输。
  • 再比如，我们将多个打印任务发送给打印机，打印机也是使用队列来安排任务的顺序

和栈相似，队列也可以有多种实现方式，这里是基于单链表的实现。

与表(list)中的实现方式略有不同的是，这里的head node有两个指针，一个(next)指向下一个元素，一个(end)指向队列的最后一个元素。这样做的目的是方便我们找到队尾，以方便的进行enqueue操作。我们依然可以使用之前定义的表，在需要找到队尾的时候遍历搜索到最后一个元素。

表

内存中离散分布的有序节点

表(list)是常见的数据结构。从数学上来说，表是一个有序的元素集合。在C语言的内存中，表储存为分散的节点(node)。每个节点包含有一个元素，以及一个指向下一个(或者上一个)元素的指针

图中的表中有四个节点。第一个节点是头节点(head node)，这个节点不用于储存元素，只用于标明表的起始。头节点可以让我们方便的插入或者删除表的第一个元素。整个表中包含有三个元素(5， 2， 15)。每个节点都有一个指针，指向下一个节点。最后一个节点的指针为NULL，我们用“接地”来图示该指针。

  • 表的功能与数组(array)很类似，数组也是有序的元素集合，但数组在内存中为一段连续内存，而表的每个节点占据的内存可以是离散的。在数组中，我们通过跳过固定的内存长度来寻找某个编号的元素。但在表中，我们必须沿着指针联系起的长链，遍历查询元素。此外，数组有固定的大小，表可以根据运行情况插入或者删除节点，动态的更改大小。表插入节点时需要从进程空间的堆中开辟内存空间，用以储存节点。删除节点可以将节点占据的内存归还给进程空间

  • 表有多种变种。上面的表中，指针指向是从前向后的，称为单向链表(linked list)。

  • 还有双向链表(double-linked list)，即每个节点增加一个指向前面一个元素的指针。
  • 以及循环链表(tabular list)，最后一个元素的指针并不为NULL，而是指向头节点。不同类型的链表有不同的应用场景。

一个数据结构的实现有两方面:

  1. 数据结构的内存表达方式;
  2. 定义在该数据结构上的操作。

我们这里实现最简单的单向链表

哈希表

哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素。但反过来，集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素，这样的映射被称为一一映射

hash只要求从A到B的对应为一个映射，它并没有限定该对应关系为一一映射。

  • 因此会有这样的可能：两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)。
  • 比如网络协议中的checksum就可能出现这种状况，即所要校验的内容与原文并不同，但与原文生成的checksum(hash值)相同。
  • 再比如，MD5算法常用来计算密码的hash值。已经有实验表明，MD5算法有可能发生碰撞，也就是不同的明文密码生成相同的hash值，这将给系统带来很大的安全漏洞

hash表被广泛的用于搜索（区别去数组：遍历整数组，算法复杂度为n），算法复杂度为1

数组虽然可以随机读取，但数组下标是随机的，它与元素值没有任何关系，所以我们要逐次访问各个元素。通过hash函数，我们限定了每个下标位置可能存储的元素。这样，我们利用键值和hash函数，就可以具备相当的先验知识，来选择适当的下标进行搜索。在没有hash碰撞的前提下，我们只需要选择一次，就可以保证该下标指向的元素是我们想要的元素

hash函数需要解决hash冲突的问题。

比如，上面的hash函数中，"Obama"和"Oaamb"有相同的hash值一个方案是将发生冲突的记录用链表储存起来，让hash值指向该链表，这叫做open hashing:

  • 我们在搜索的时候，先根据hash值找到链表，再根据key值遍历搜索链表，直到找到记录。我们可以用其他数据结构代替链表。

  • open hashing需要使用指针。我们有时候想要避免使用指针，以保持随机存储的优势，所以采用closed hashing的方式来解决冲突。（closed hashing的关键在如何探测下一个位置）

说在最后 一、栈：

1、后缀表达式的求值； 
2、中缀到后缀表达式的转换； 
3、深度优先搜索的非递归实现； 
4、动态规划的优化：用于维护一个凸序列，便于二分查找，如LIS问题的O(nlgn)算法。

二、队列：

1、树的层序遍历； 
2、广度优先搜索； 
3、Bellman-Ford算法的SPFA实现； 
4、网络流中FF算法的Edmonds-Karp实现，以及Preflow算法的队列优化实现。

三、二叉搜索树：

1、对大量的关键字的索引查找； 
2、有很多平衡策略以改善其平均性能：

常用平衡树：AVL，红黑树，随机化BST，Splay Tree，Treap（或叫笛卡儿树）。

四、散列表（hash表）：

1、一般针对值域较大但状态很稀疏的应用，比如状态压缩记忆化搜索； 
2、实现映射功能。

五、检索树（Trie）：

1、一般用于字符串索引算法，速度快，但占用空间较大（相对hash）； 
2、常用的改进结构：Patricia线索树，多叉检索树（TST）。

六、优先队列：

1、常用的是二叉堆的实现，具体应用如堆排序和Dijkstra算法； 
2、当需要快速合并两个优先队列时，常用二项式队列，实现简单。 
3、注意最大最小堆的配对使用。

七、线段树和树状数组：

1、两者都可以用于离散对象的统计； 
2、后者的步进函数的性质和应用值得注意； 
3、前者基本上适用于任何的区间操作，如求区间最值，改变区间的值等。 
4、线段树还可以用于优化状态的枚举，经常和动态规划结合。

八、后缀树与后缀数组：

1、总体规律是两者的实现都比较复杂，前者更甚，但是前者的功能也更强大； 
2、几乎可以解决所有常见的关于字符串的算法，如最长回文子串，最长重复子串，以及很多的模式匹配问题。

九、并查集：

1、解决无向图的连通性问题，如用于Kruskal算法； 
2、解决等价关系的查询（这是它的主要用武之地），如05年Baidu之星初赛的石头剪子布游戏； 
3、优点是实现异常简单，缺点是合并后无法分离，若需要可以选择用动态树。

十、邻接表和边表：

1、表示图的最直接的方法； 
2、后者更省空间，并且在一定程度上更好用，比如Bellman-Ford算法。

ps:数组、链表太基础不在考虑之列。

微信号：

clpaial10201119（Q Q：2211523682）

微博WB:

http://weibo.com/u/3288975567?is_hot=1

gitHub：

https://github.com/al1020119

博客

http://al1020119.github.io/

Comments