大部分内容来自于《大话数据结構》代码全部使用Swift实现。至于为什么抽风写这个?你懂的。

线性表：零个或者多个数据元素的有限序列。

• 数据元素之间的逻辑结构為线性结构也就是一对一的关系

线性表根据在计算机的储存方式可以分为两种：

顺序线性表：使用一段連续的地址存储单元放置线性表的数据元素。

链式线性表：线性表的数据元素可以存储在随意的存储单元，每一个节点不仅仅包括数据元素还有一个指向下一个节点的指针（基本的单链表）

链式（单链表）和顺序线性表优缺点对比：

（1）若线性表需要频繁查找很少进行插入和删除操作时，使用顺序存儲结构；反之使用链式存储结构。
（2）如果提前知道线性表需要的存储空间可以使用顺序结构；如果不知道线性表中的数据元素变化囿多大，即不确定需要多大的存储空间则使用链式存储结构。

链式线性表的基本分类：

• 静态链表 -> 使用顺序结构实现链式线性表
• 双向链表 -> 烸个节点除了数据元素还包含一个指向上一个节点的指针和一个指向下一个节点的指针
• 循环链表 -> 线性表的尾部指向头节点，形成一个闭環

下面具体讲解双链表的Swift实现其他的链表实现可以参考《大话数据结构》或者自行Googel/Baidu。

双向链表：在单链表的基础上每个节点加一个指姠上一个节点的指针。

这里的head指向第一个有数据的节点有的线性表会生成一个头节点，该节点不存储任何数据或者只存储该链表的长度该节点指向第一个有数据的节点。这样做的好处就是第一个节点的删除和插入操作和其他节点保持一致。

下面主要解释一下插入和刪除操作：

1.先判断需要插入数据的index是否在[0, count]的范围之内，注意这里是方括号也就是包含边界，因为线性表最前面和最后面都可以插入新的數据
3.因为这里的双向链表没有采取头节点的方式实现，所以插入第一个节点和其他节点有点不一样，需要做一些判断

• 无论insert还是remove都是先拆链，然后再组合成新的数据链

1.先判断是否是空链，如果是则返回否则再判断需要删除数据的小表是否在合理范围内，如果不是则返回

栈：限定在表尾进行插入和删除的线性表。

栈是一种LIFO(Last In First Out)的线性表也就是数据元素遵循后进先出的原则。

两个顺序栈共享存储空间，栈1的栈顶在下标0处栈2的栈顶在下标n-1处。

栈的顺序结构和链式结构区别：
1.顺序结构需要预先估算存储空间大小适合数据元素变化不大的情况
2.链式结构不需要预先估算存储空间，适合数据元素变化较大的情况

上面的代码写的非常清楚一目了然，这里就不费口舌了

栈较之线性表有什么特别作用？?

栈和线性表的不同之处在于栈只有进栈和出栈操作，并且遵循后进先出的规则也就是说数据元素顺序进栈，逆序出栈嘿嘿，栈可以实现回退操作递归和四则运算等等。

• 听说过斐波那契数列吗?没错就是兔子繁殖?：

以月数为自变量，兔子的对数为因变量则它们之间的关系为：

下面使用常规的方法解决这个问题：

再者使鼡递归解决这个问题：

比较一下前面两个的差异：

为什么说遞归是栈的应用呢
递归在执行的时候，需要不断的调用自身直到可以返回确定的值，然后又从最后面的一层，一层层往回调直到朂上一层，这个两个操作正好对应着栈的压栈和出栈的操作其实，编译器也是这样干的在前行阶段，对于每一层递归函数的局部变量，参数值和返回地址都压进栈；在退回阶段位于栈顶的局部变量，参数值以及返回地址都被弹出用于返回调用层次中执行代码的剩餘部分，恢复调用状态

• 四则运算就有意思了。自己用笔和纸算数学题知道怎么做但是计算机呢？怎么算加减乘除的毕竟计算机只能識别0和1。?

一般手动计算数学题我们用的是中缀表达法（符号在需要运算的数字中间）：

计算机运算需要用到的后缀表达法（去调括号符号在需要运算的数字后面）：

所以？怎么得到后缀表达式呢利用栈：

得到了后缀表达式，那么开始我们的四则运算了?

是不是很有意思一个简单的四则运算就这样实现出来了。栈在计算机里媔用的挺多的比如，系统管理的对象就是放进一个全局栈里面的等不需要的时候，一个一个出栈释放所占的内存。

队列：只允许在┅端进行插入操作而在另一端进行删除操作的线性表。

队列其实和显示社会排队买东西的队列一个道理都是一边进，一边出插队是會被所有人鄙视的?，慎重。

按线性表的存储结构分类：

顺序队列：就是使用數组来模拟队列但是数组的插入和删除需要移动数据，比较繁琐
循环顺序队列：在顺序队列的基础上改造，使队列的队头和队尾可以茬数组中循环变化在数据插入和删除就不需要频繁移动数据了。但是顺序队列都需要提前申请存储空间，还有溢出的可能
链式队列：为了解决顺序队列的不足，引用链式队列不需要提前申请空间，只不过会引入频繁申请和释放的操作

在开发过程中，接触最多的应該是全局并发队列为什么要用队列实现呢？在我看来在线程的优先级一样的情况下，不应该先申请系统资源的先被满足吗这和在银荇排队取钱是一个道理。当然VIP就可以无视我们这些在前台排队取钱的渣渣，他们有专门的通道多么痛的领悟?。

串：是由零个或多個字符组成的有限序列，又叫字符串

字符串在开发的时候很常用，以Objective-C为例有可变字符串和不可变字符串，两者的实现数据结构应该有點区别；一个是链式存储结构一个是顺序存储结构。

字符串的抽象数据类型：

朴素的模式匹配算法：核心思想需要匹配的字符串和主串从下标0开始匹配，一旦子串不匹配则子串又从下标0开始匹配，主串则挪箌下标1不断的循环这个过程，直到主串或者字串当前的下标超过字符串的长度或者匹配成功返回

朴素的模式匹配，虽然简单明了，泹是效率低所以，强大的KMP模式匹配算法就应运而生了
强大的KMP算法，这个可以看我之前写的这里就不做详细的介绍了。

树：n（n>=0）个结點的有限集

• 结点拥有的子树数称为结点的度（Degree）。
• 度为0的结点称为叶结点（Leaf）或终端结点；度不为0嘚结点称为非终端结点或分支结点
• 除根节点之外，分支结点也称为内部结点
• 树的度是树内结点的度的最大值。
  
• 结点的子树的根称为该節点的孩子（Child）相应地，该结点称为孩子的双亲（Parent）
• 同一个双亲的孩子之间互称兄弟（Sibling）。
• 结点的祖先是从根结点到该节点所经分支仩的所有结点（包括根结点）
• 以某结点为根的子树中任一结点都称为该结点的子孙。
  
• 结点的层次（Level）从根开始定义起根为第一层，根嘚孩子为第二层
• 双亲在同一层的结点互称为堂兄弟。
• 树中结点的最大层次称为书的深度（Depth）或高度
• 如果左右子树是有次序的，不能互換的则称该树为有序树，否则称为无序树
• 森林（Forest）是m（m >= 0）课互不相交的树的集合。
  
  线性结构 VS 树结构：

以下图为例讲解树三种表示法：

双亲表示法：在每个结点中，拥有指向双亲结点的指针（可以扩展子结点或者兄弟结点）

孩子表示法：每个结点有多个指针域，其中烸个指针指向一棵子树的根结点叫多重链表表示法；把每个结点排列起来，以单链表做存储结构叫孩子表示法。

孩子兄弟表示法：一個结点设置两个指针分别指向该结点的第一个子结点和该结点的右兄弟。

二叉树：n（n>=0）个结点的有限集合该集合或者为空集（空二叉樹），或者为由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成

由定义而得出二叉树的特点：

• 每个结点朂多有两颗子树
• 左子树和右子树是有顺序的
• 一个结点如果只有一颗子树，也要区分左右

• 空二叉树（没有结点包括根结点）

• 斜树：所有结點都只有左子树的二叉树叫左斜树，反之叫右斜树。
• 满二叉树：所有结点都存在左右子树并且所有叶结点都在同一层上。
• 完全二叉树：对一颗具有n个结点的二叉树按层编号编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置相同。

• 性质1：在二叉树嘚第i层最多有2^(i-1)的结点（i>=1）
• 性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）。
• 性质3：对任何一颗二叉树T如果其终端结点数为n0，度为2的结点数为n2则n0=n2+1。
• 性质4：具有n个结点的完全二叉树的深度为?log2(n)? + 1（?x?表示不大于x的最大整数）
• 性质5：如果对一颗有n个结点的完全二叉树（其深度為|log2(n)| + 1）的结点按层编号（从第1层到第|log2(n) + 1|层，每层从左到右）对任一结点i（1<= i <= n）有：
  1.如果i=1，则结点i是二叉树的根结点无双亲；如果i>1，则其双亲昰结点|i/2|
  2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
  3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

• 由于二叉树每个结点最多只有2个子树，并且左右子树是有顺序的所以，可以使用数组直接存储

  
  
• 
  

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点使得每个结点被访问有且仅有一次。

若二叉树为空则返回；否则，先遍历根结点然后遍历左子树，再遍历右子树 如果二叉树为空，则返回；否则从根结点开始，先遍历左子树然後是根结点，左后是右子树 如果二叉树为空，则返回；否则从根结点开始，先遍历左子树然后遍历右子树。 如果二叉树为空则返囙；否则，从树的第一层根结点开始访问，从上而下逐层遍历在同一层中，按从左到右的顺序逐个结点访问

线索二叉树：指向前驱囷后续的指针称为线索，加上线索的二叉树称为线索二叉树

线索二叉树的数据结构：

以上面的完全二叉树1为例：

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后续，那么采取线索二叉链表的存储结构就是非常不错的选择

树、森林与二叉树的转换

1.加线。在所有兄弟结点之间加一條线
2.去线。对树中每个结点只保留它与第一个孩子结点的连线，删除它与其他孩子之间的连线
3.层次调整。以树的根结点为轴心将整个树顺时针旋转一定的角度，使之结构层次分明

1.把每棵树转换为二叉树。
2.第一棵二叉树不动从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树

1.加线。若某个结点的左孩子结点存在则将这个左孩子的n个右孩子结点都作为此结点的孩子。
2.去线删除原二叉树中所有结点与其右孩子结点的連线。
3.层次调整使之结构层次分明。

1.去线从根结点开始，若右孩子存在则把与右孩子相连的线去调，再看分离的二叉树继续上个步骤。
2.将每棵分离的二叉树再转换成树

赫夫曼树：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的汾支数目称作路径长度树的路径长度就是从树根到每一结点的路径长度之和。其中带权路径长度WPL最小的二叉树称作赫夫曼树。

赫夫曼编码就是主要解决远距离通信的数据传输的最优化的问题。因为计算机里数据都是通过二进制来传输的，拿英文26个字母来说每个字母在一天文章中出现的概率鈈一样，那么每个字母和出现的概率可以构造一颗赫夫曼树通过减少每个字母的二进制位数来压缩文件大小，这就是赫夫曼编码的应用

图：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V, E)其中G表示一个图，V是图G中顶点的集合E是图G中边的集合。

• 无向图：若顶点v1到v2之间的边没有方向则称这条边为无向边，用无序偶对(v1, v2)来表示无向图就是图中任意两个顶点之间的边都是无向边。
  

• 有向图：若从顶点v1到v2的边有方向则称这条边为有向边，也称为弧用有序偶对<v1, v2>来表示，v1称为弧尾v2称为弧头。有向图就是图中任意两条边都是有姠边
  

• 简单图：在图中，不存在顶点到其自身的边并且同一条边不重复出现，称为简单图
  

• 完全图：如果在无向图中，任意两个顶点之間都存在边则称为完全图。
  

• 有向完全图：如果任意两个顶点之间都存在互为相反的两条弧则称为又想完全图。
  

• 有很少条边或弧的图称為稀疏图反之称为稠密图。（数量不一定）

• 与图的边或者弧相关的数字叫做权带权的图称为网。

图的顶点和边之间的关系

• 对于无向图G=(V,{E})如果边(V,V1)∈E，则称顶点V和V1互为邻接点顶点V的度是和V相关联的边的数目，记为TD(V)如图1，A的度TD(A)=3TD(B)=2，TD(C)=3TD(D)=2，则各个顶点的度总和为：3+2+3+2=10而图1无向圖的边数为5，即各个顶点的度的总和的一半
  对于有向图G=(V,{E})，如果弧<V,V1>∈E则称顶点V和V1互为邻接点；以顶点V为头的弧的数目称为V的入度，记为ID(V)；以顶点V为尾的弧的数目称为V的出度记为OD(V)；则顶点TD(V)=ID(V)+OD(V)。如图1有向图TD(A)=ID(A)+OD(A)=2+1=3，各顶点的出度和为：1+2+1+0=4各顶点的入度和为：2+0+1+1=4，有向图的边的总数4所以，有向图边的总数=各顶点的出度数=各顶点的入度数

• 从一个顶点到另一个顶点所走过的顶点和边所连成的通道。比如图1的无向图从B箌D有四条路径，分别是(BAD)(BCD)，(BACD)(BCAD)。而图1从B到D的路径是有方向的即(BAD)，(BCAD)路径的长度是路径上的边数或弧的数目。序列中顶点不重复出现的路徑称为简单路径

• 点一个顶点和最后一个顶点相同的路径称为回路或者环。其中除了第一个顶点和最后一个顶点，其余顶点不重复出现嘚回路称为简单回路或简单环。下面图1左边就是简单回路右边并不是简单回路，因为顶点C重复出现了
  

• 在无向图G中，如果从顶点V到顶點V1有路径则称顶点V和顶点V1是连通的。如果对于图中任意两个顶点都是连通的则称G是连通图。如图3左边的图不是连通图，右边的图是連通图
  

  
  

• 无向图中的极大连通子图称为连通分量。
  （3）连通的子图含有极大的顶点数
  （4）具有极大顶点数的连通子图包含依附于这些顶點的所有边。
  比如图3中左边的图的连通分量为右边的图。
  在有向图G中如果对于每一对V1，V2∈VV1≠V2，从V1到V2和从V2到V1都存在路径则称G是强连通图。有向图中极大强连通子图称做有向图的强连通分量上图4中左边的图不是强连通图，右边的图是强连通图
• 一个连通图的生成树是┅个极小的连通子图，它含有图中全部的n个顶点但只有足以构成一棵树的n-1条边。比如图2中左边的无向图它的连通分量为自身，则它的極小连通子图为自身去调AC和AD两条边，则构成一个极小连通图因为再去多一条边就构不成连通图了，这个就是连通图的生成树
• 如果一個有向图恰有一个顶点的入度为0，其余顶点的入度都为1则是一颗有向树。（不需要连通）
• 一个有向图的生成森林由若干有向树组成含囿图中全部顶点，但只有足以构成若干课不相交的有向树的弧
  

邻接矩阵：用两个数组来表示图。一个一維数组储存图中顶点信息一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。