数据结构按照逻辑关系分为线性结构和非线性结构两大类，其中，非线性结构又可分为树结构和图结构。

3.1线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后驱的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”

3.1.1线性表

线性表示最简单、最基本也是最常见的一种线性结构。常采用顺序存储和链式存储，主要基本操作就是插入、删除和查找。

1.线性表的定义

一个线性表示n个元素的有限序列，通常表示为（a1,a2,a3.....an）。非空线性表的特点如下。

（1）存在唯一的一个称作“第一个”的元素。

（2）存在唯一的一个称作“最后一个”的元素。

（3）除第一个元素外，序列中的每一个元素均只有一个直接前驱。

（4）除最后一个元素外，序列中的每一个元素只有一个直接后驱。

2.线性表的存储结构

线性表的存储结构分为顺序存储和链式存储

1）顺序存储是是指用一组地址连续的存储单元依次存储线性表中的数据元素。

2）线性表的链式存储

a.单向链表，每个节点中只有指向下一个节点的地址

b.双向链表

c.循环链表

d.静态链表

3.1.2栈和列队

1.栈 

先进后出

2.列队

先进先出

3.1.3串

串（字符串）是一种特殊的线性表，其元素为字符。

朴素的模式匹配算法和KMP模式匹配算法

3.2数组、矩阵和广义表

3.2.1数组

数组是定长线性表在维数上的扩展，即线性表中的元素又是一个线性表

3.2.2矩阵

矩阵是很多科学与工程计算领域研究的数学对象。在数据结构中，主要讨论如何在节省存储空间的情况下使用矩阵的各种运算能高效的进行。

1.特殊矩阵

若矩阵中元素（或非0元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。

2.稀疏矩阵

在一个矩阵中。若非0元素的个数远远少于0元素的个数，且非0元素的分布没有规律，则称之为稀疏矩阵。

3.2.3广义表

广义表是线性表的推广，是由0个或多个单元素或字表组成的有限序列。

3.3树

树结构是一种非常重要的非线性结构，该结构中的一个元素可以由两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层析结构关系。

3.3.1树与二叉树的定义

1.树的定义

树是m(m>=0)个节点的有限集合，当m=0时称为空树。在任一个非空树种，有且仅有一个称为根的节点；其余节点可分为n个互不相交的有限子集。

2.树的基本概念

（1）双亲、孩子、兄弟。节点的自述的根称为该节点的孩子：相应地，该节点称为其子节点的双亲。具有相同双亲的节点互为兄弟。

（2）节点的度。一个节点的子树的个数称为该节点的度。

（3）叶子节点。叶子节点称为终端节点。

（4）内部节点 度不为0的节点，也称为分支节点或非终端节点。

（5）节点的层次，根节点为第一层，一次类推

（6）树的高度 一棵树的最大层次树记为树的高度

（7）有序（无序）树，若将书中节点的各子树看成是从左到右一次有序的，即不能交换，则称为有序树，否则称为无序树。

3.二叉树的定义

二叉树与树的区别：二叉树中节点的子树要区分左子树还是右子树，即使在节点只有一个树的情况下，也要指出是左子树还是右子树，另外，二叉树的最大度为2，而树的节点的度不做限制。

3.3.2二叉树的性质和存储结构

1.二叉树的性质

（1）二叉树第i层上最多有2^i-1个节点。

（2）高度为k的二叉树最多有2^K  -1 节点。

（3）对于任一二叉树，若其终端节点的个数为n，度为2 的节点个数为m ,则n=m+1

（4）具有n个节点的满二叉树的深度为log2n+1

2.二叉树的存储结构

1）二叉树的顺序存储结构

顺序存储结构是用一组连续的存储单元存储二叉树中的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列的相互位置能反映出节点之间的逻辑关系。

对于一个深度为k的完全二叉树，首先讲一下什么叫完全二叉树:

有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.

对于完全二叉树，如果数组下标识从1开始的，

则有a[i]的左子树根节点为啊a[2i],右子树的根节点为a[2i+1],用一个数组可以连续的表示完全二叉树，

对于一般的二叉树用数组结构来表示，会浪费很多空间。

2）二叉树的链式存储结构

由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以使用三叉链表或二叉链表（即一个节点含有3个指针或2个指针）来存储二叉树，链表的头指针指向二叉树的根节点。

3.3.3二叉树的遍历

（1）使用递归来遍历：

1.先序遍历 ，先遍历根节点

2.中序遍历，先访问左节点，再访问根节点

3.后续遍历，最后访问根节点

（2）二叉树的非递归遍历：

利用辅助栈来完成遍历

（3）二叉树的层序遍历算法

自上而下、自左至右逐层访问树种各节点的过程就是层序遍历

3.3.4 线索二叉树

1.线索二叉树的定义

而叉树的遍历实质上是对一个非线性结构进行线性化的过程，它使得每个节点在这些线性序列中有且仅有一个直接前驱和后驱。但在二叉树链表存储结构中，只能找到一个节点的左、右孩子，不能直接得到节点在任一遍历中的前继和后继，这些信息只有在遍历的动态过程中才能得到，因此，引入线索二叉树来保存这些动态过程中得到的信息。

2.建立线索二叉树

ltag

lchild

data

rchild

rtag

其中 ltag为0时，lchild指向节点的左孩子，ltag为1时，lchild指向节点的直接前驱

rtag为0时，rchild指向节点的右孩子，rtag为1时，rchild指向节点的直接后继

3.访问线索二叉树

以中序二叉树为例，

（1）若p->rtag为1，则rchild为直接后继节点

（2）若p->rtag为0，则之间后继节点则为右子树中“最左下”的节点。

3.3.5最优二叉树

最优二叉树又称哈夫曼树，它是一类带权路径长度最短的树，路径是从树的一个节点到另一个节点之间的通路，路径上的分支树目称为路径的长度。

树的路径长度是从根节点到每一个叶子之间的路径长度的总和，节点的带权路径长度为从该节点到树根之间的路径长度与该节点权值的乘积

树的带权路径长度为书中所有叶子节点的带权路径长度之和，

wpl = w1*k1+w2*k2+.....wn*kn

其中，n为带权叶子节点的数目，w为权值，k为叶子节点到根节点的权值。

那么如何构造最优二叉树呢？构造最优二茶水壶的哈夫曼算法如下。

（1）根据给定的n个权值{w1,w2....,wn}，构成n棵二叉树的集合F={T1,T2,.....Tn},其中每棵树Ti中只有一个带权的为wi的

根节点，其左、右子树均空。

（2）在F中选取两棵权值最小的树作为左、右子树构造一颗新的二叉树，置新构造的二叉树的根节点的权值为其左、右子树根节点的权值之和。

（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。

2.哈夫曼编码

若对每个字符编制相同长度的二进制码，则称为等长码，等长码实现简单，但是浪费空间

如果要设计长度不等的编码，必须满足下面的条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码，

可利用哈夫曼最优二叉树可以实现前缀码

左分支标0，右分支标1，则每个叶子节点代表的字符的编码就是从根节点到叶子节点路径上0、1组成的串。

3.3.6树和森林

森林就是有多个树，其他略

3.4图

图是比树结构更为复杂的一种数据结构。在线性结构中，除首节点没有前驱，末节点没有后继外，一个节点只有唯一一个直接前驱和一个直接后驱。在树结构中，除根节点没有前驱节点外，其余的节点只有唯一一个前驱（双亲节点）和多个后继节点。而在图中，任意两个节点之间都可能有直接的关系，所以图中的一个节点的前驱节点和后驱节点时没有限制的。

3.4.1图的定义与存储

1.图的定义

（1）有向图，若图中每条边都具有方向的，那么有向边称为弧，有向边的起点称为弧为，有向边的重点称为弧头。

（2）无向图，每条边都是无方向的。

（3）完全图，每个节点之间都有边

（4）度、出度和入度。节点的度，表示关联该节点边的数目，出度是指有向边的起点为该节点的边的数目，类似的入度是终点。

（5）路径。

（6）子图，包含的关系

（7）连通图与连通分量。在无向图中任意两点都是连通的，连通是指有路径。

（8）强连通和强连通分量。在有向图中任意两典都是连通的。

（9）网。边（弧）带权值的图称为网

（10）有向树。如果有一个图恰好有一个顶点的入度为0，其余顶点的入度均为1，则是一个有向树。

2.图的存储结构

1）邻接矩阵表示法

n个节点的图用n阶的方阵来表示

2）邻接链表表示法

存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中

3.4.2图的遍历

图的遍历是指从某个顶点出发，沿着某条路径对图中的所有顶点进行访问且只访问一次的过程。

1.深度优先搜索（depth first search，DFS）

此种方法类似于树的先序遍历，在第一次经过一个顶点时就进行访问操作。从图G中任一节点v出发按深度优先搜索法进行遍历的步骤。

（1）设置搜索指针怕，使p指向顶点v。

（2）访问p所指顶点，并使p指向与其相邻的且尚被访问过的顶点。

（3）若p所指顶点存在，则重复步骤（2），否则执行步骤（4）。

（4）沿着刚才访问过的次序和方向回溯到一个尚有邻接顶点且未访问过的顶点，并使p指向这个为访问过的顶点，然后重复步骤（2），直到所有的顶点均被访问到。

2.广度优先搜索(Breadth First search)

图的广度优先搜索方法为：从图中的讴歌顶点v出发，在访问v之后一次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发一次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有的已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选一个为被访问的顶点为起点，重复上述过程。直到所有的钉钉都被访问到为止。

3.4.3生成树及最小生成树

1.生成树的概念。

对于有n个顶点的连通图，至少有n-1条边，而生成树种恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若在图的生成树种任意加一条边，则必然形成回路。

2.最小生成树

对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。

（1）普里姆（Prim）算法

（2）克鲁斯卡尔（Kruskal）算法

3.4.4拓扑排序的关键路径

1.AOV网

在AOV网中不应爱出现有向环。

2.拓扑排序及其算法

3.AOE网

在带权的有向图G中以顶点表示事件。

4.关键路径和关键活动

3.4.5最短路径

1.单源点最短路径

2.每对顶点间的最短路径

3.5查找

3.5.1查找的基本概念

1.基本概念

查找是一种常用的基本运算。查找表是指同一类型的数据元素（或记录）构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因此，查找表是一种非常灵活的数据结构。

对查找表经常要进行的两种操作如下。

（1）查询某个特定的数据元素是否在查找表中。

（2）检索某个特定的数据元素的各种属性。

通常将进行这两种操作的查找表称为静态查找表。

对查找表经常要进行的另外两种操作如下。

（1）在查找表中插入一个元素。

（2）在查找表中删除一个数据元素。

若需要在查找表中插入一个不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。

关键字是数据元素（或记录）的某个数据项的值，用它来识别这个数据元素。主关键字是指唯一标识一个数据元素的关键字。次关键字是指能标识多个数据元素的关键字。

2.平均查找长度

对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行比较的记录个数的期望值”作为衡量查找算法好坏的依据。

为确定记录在查找表中的位置，需要给定关键字值进行比较的次数的期望值称为其算法在查找成功时的平均查找长度。

相当于查找每一个元素的权值和

3.5.2静态查找表的查找方法

1.顺序查找

即一个一个按顺序查找。平均查找长度为（n+1）/2

2.折半查找

前提是，关键字以按大小顺序排序了，平均查找长度为log2(n+1)+1

3.分块查找

分块查找又称为索引顺序查找，是对顺序查找方法的一种改进其效率介于顺序查找与折半查找之间。

在分块查找的过程中首先将表分成若干块，每块的关键字不一定有序，但块与块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字，此外，还建立了一个“索引表”，索引表按关键字有序排列。

3.5.3动态查找表

1.二叉排序树

1）二叉排序树的定义

二叉排序树又称为二叉查找树，若非空有一下性质

（1）若它的左子树非空，则左子树上所有节点的值均小于根节点的值

（2）若它的右子树非空，则右子树的所有节点的值均大于根节点的值

（3）左。右子树本身就是二叉排序树

2）二叉排序树的查找过程

3）在二叉排序树中插入节点的操作

二叉排序树是通过依次输入数据元素并把它们插入到二叉树的适当位置构造起来的，具体的过程是：每读入一个元素，建立一个新节点。若二叉树非空，则将新节点的值与根节点的值相比较，如果小于根节点的值，则插入到左子树，否则插入到右子树；若二叉排序树为空，则新节点走位二叉排序树的根节点。

4）在二叉排序树种删除节点的操作。

（1）若节点p为叶子节点且p不是根节点，因此此时删除p不会破坏树的结构，只需将p的双亲节点原来指向p的指针现在指向NULL。

（2）若p只有左子树或右子树且不是根节点。此时只需将p的双亲节点原来指向p的指针现在指向p的左子树或右子树。

（3）若p的节点的左右子树都存在，则删除p节点时应将其左子树、右子树连接到适当的位置，并保持二叉排序树的有序的特性。可采用以下两种方法处理：一是p的左子树为p的双亲节点的左子树，而将p的右子树下接到中序遍历是p的直接前驱及节点（p的左子树中最右下方的节点）的右孩子指针上；二是用p的中序直接前驱代替p节点，然后在删除替换后的p节点。

2.平衡二叉树

平衡二叉树又称为AVL树，它或者是一棵空树，或者具有以下性质的二叉树。

1）它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不会超过1.

2）若将二叉树节点的平衡因子（balance factor，BF）定义为该节点左子树的高度减去右子树的高度，则平衡二叉树上所有的节点的平衡因子只可能是-1、0和1.只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

分析二叉排序树的查找过程可知，只有在树的形态比较均匀的情况下，查找的效率才能达到最佳，因此，希望在构造二叉排序树的过程中，保持其为一颗平衡二叉树。

使二叉树排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入破坏了平衡，若是，则超出其中最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡，所谓最小不平衡子树，是指离插入节点最近且以平衡因子的绝对值大于1节点作为根的子树。

1）平衡二叉树上的插入操作

一般情况下，假设由于在二叉排序树上插入节点而失去平衡的最小树根节点的指针为a,也就是说，a为最小不平衡子树

（1）LL型单向右旋平衡处理

（2）RR型单向左旋处理

（3）LR型先左后右双向旋转平衡处理。

（4）RL型先右后左双向旋转平衡处理。

2）平衡二叉树上的删除操作

在平衡二叉树上进行删除操作比插入操作更复杂。若待删除节点的两个子树都不为空，就用该机诶单左子树上的中序遍历的最后一个节点（或其右子树上的第一个节点）替换该节点，将情况转化为待删除的节点只有一个子树后再进行处理，当一个节点被删除后，从被删除节点到树根的路径上所有节点的平衡因子都需要更新，对于每一个该路径上的平和因子大于2的节点来说都需要进行平衡处理。

3.B_树

一颗m阶的B_树，或者为空树，或满足一下特性的m叉树

（1）树中每个节点最多有m棵子树

（2）若根节点不是叶子节点，则最少有两棵子树。

（3）除根之外的所有非终端节点最少有[m/2]棵子树。

（4）所有非终端的节点包含下列数据信息

（n,A0,K1,A1,K2....Kn,An），其中，K为关键字且Ki<Ki+1;A为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki,An所指子树中所有节点的关键字均大于Kn,n为节点中关键字的个数且满足[m/2]-1<n<m-1。

（5）所有的叶子节点都出现在同一层次上，并且不带信息（可以看作是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空）

B_树上的插入和删除运算较为复杂，因为要保证运算节点中关键字的个数等符合要求。

3.5.4哈希表

1.哈希表的定义

哈希表通过计算以记录的关键字为自变量函数来得到该记录的存储地址，所以在哈希表中进行查找操作时，需要同一哈希函数计算的到存储地址。然后在存储地址内查找。

对于哈希表，主要考虑两个问题：一是如何构造哈希函数，而是如何解决冲突。

2.哈希函数的构造方法

应解决好两个主要问题

（1）哈希函数应是一个压缩映像函数，它应该具有较大的压缩性，以节省存储空间。

（2）哈希函数应该具有较好的散列性，虽然冲突是不可避免的，但应该尽量避免。

3.处理冲突的方法

（1）开放地址法

线性探测法

（2）链地址法

（3）再哈希法

（4）建立一个公共溢出区

4.哈希表的查找

与其他类似

3.6排序

3.6.1排序的基本概念

假设含n个记录的文件内容为{R1,R2,....Rn},相应地关键字为{k1,k2,...kn}。进过排序确定一种排列，使得关键字满足递增或递减。

若在待排序的序列中，Rj和Ri的关键字相同，且排序前Ri领先于Rj,那么在排序后，如果Ri和Rj的相对次序保持不变，则称此类排序方法时稳定的。否则称为不稳定的。

（1）内部排序，内部排序指带排序几率全部存放在内存中进行的排序的过程。

（2）外部排序，外部排序指待排序记录的数量很大，以至于内存不能容纳全部几率，在排序过程中尚需为外村进行访问的排序过程。

3.6.2简单排序

1.直接插入排序

直接插入排序是一种简单的排序方法，具体的做法是：在插入第i个记录时，R1、R2..Ri-1已经排好序，这时将R的关键字ki依次与关键字ki-1、ki-2等进行比较，从而找到应该插入的位置并将Ri插入，插入位置及其后的记录依次向后移动。

最好情况下，比较次数为n-1次，移动次数为0

最坏情况下，比较次数为n*(n-1)/2,移动的次数为（包括中间变量的赋值）为（n+3）*(n+2)/2。

时间复杂度为O(n^2),空间复杂度为O(1),是一种稳定的排序。

2.冒泡排序

方法是：首先将第一个记录的关键字和第二个关键字进行比较，若为逆序，则交换，侯然第二个记录与第三个记录比较，若为逆序，再交换，依次类推，直到n-1和n比较位置。这样是一趟冒泡排序，结果是，最大的记录被交换到了n的位置，然后进行第二趟n-1.

时间复杂度为O(n^2),空间复杂度为O(1)

3.简单选择排序

通过n-i(1<=i<=n)次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列。就是找最小关键字的下标。

时间复杂度为O(n^2),空间复杂度为O(1),是一种不稳定的排序。

3.6.3希尔排序

希尔排序又称为“缩小增量排序”，它是对直接插入排序的改进。

基本思想是：先将真个待排记录序列分割成若干个子序列，然后分别进行直接插入排序，带真个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。先取一个小于n的整数d1作为第一个增量，把全序列分成d1组，直到di=1时，即所有的记录整体有序。

希尔排序是一种不稳定的排序方法，根据统计分析其时间复杂度约为O(n^1.3)，在排序过程中，仅需要一个元素的辅助空间用于数组元素值得交换，空间复杂度为O(1)。

3.6.4快速排序

快速排序的基本思想是：通过一趟排序将待排的记录划分为两个独立的两部分，称为前半区和后半区，其中前半区中记录的关键字不大于后半区记录的关键字，然后分别对这两部分记录继续使用快速排序，从而使整个排序有序。

一趟快速排序的过程称为一次划分，具体做法是：附设两个位置指示变量i和j,他们的初始值分别指向序列的第一个记录和最后一个记录，设枢轴记录（通常是第一个记录）的关键字为pivot,则首先从j所指定位置起向前搜索，找到一个关键字小于pivot的记录时将该记录向前移到i指示的位置，然后从i所指示位置起向后搜索，找到第一个关键字大于pivot的记录时将该记录向后移动j所指位置，重复该过程直至i与j相等为止。

快速排序算法的时间复杂度为O(nlogn)，在所有算法复杂度为此数量级的排序方法中，快速排序被认为平均性最好的一种，但是若初始记录序列按关键字有序或基本有序时，即每次划分都是将序列划分为某一半的长度为0的情况下，此时快速排序的性能退化为时间复杂度是O(n^2)，快速排序是不稳定的排序方法。

3.6.5堆排序

堆排序的基本思想是：对一组待排序的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新推，变得到次大的关键字，如此反复，直到所有关键字排成有序序列为止。

对于记录较少的文件来说，堆排序的优越性并不明显，但对于大量的记录来说，堆排序是很有效的，堆排序的整个算法时间是由建立初始化堆和不断调整堆这两部分时间构成的。可以证明，堆排序的时间复杂度为O(nlogn),此外，堆排序只需要记录大小的辅助空间。

3.6.6归并排序

将两个或两个以上的有序文件合并成一个新的有序文件。如此反复，直到合并是成度是1的子序列。

时间复杂度为O(nlogn)，空间复杂度为O(n)

3.6.7基数排序

基数排序的时间复杂度为O(d(n+rd)),空间复杂度为O(rd),r为基数,d是关键字的位数，这里d取所有关键字中的最大值。

3.6.8内部排序方法总结

略

3.6.9外部排序

略