数据结构总结

完全二叉树的顺序存储：

A2B1C34DE56FG7HIJKL89101112

ABCDEFGHIJKL

0 1 2 3 4 5 6 7 8 9 10 11 12

一般二叉树的顺序存储：

把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。

ABCD(a) 右偏斜二叉树AABCD(b) 补全后的完全二叉树 DBC (c) 右偏斜二叉树的顺序存储示意图

二叉树的链式存储结构： 二叉链表：

二叉树的遍历：

顺着某一条搜索路径巡访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次。

常见的遍历方式有：

递归遍历，层次遍历，非递归遍历 树的遍历常用方法：

先序遍历：先访问树的根节点，然后先序访问左子树，最后先序访问右子树 中序遍历：先中序遍历左子树，然后访问根节点，最后中序访问右子树 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点 按层次遍历：先访问第一次上的节点，然后依次遍历第二层。。。。。

先序遍历的递归算法： void PreOrder( BiTree bt) {

if (bt!=NULL){ /* 如果bt为空，结束*/

visit (bt->data); /*访问根结点*/

PreOrder( bt->lchild); /*先序遍历左子树（递归调用）*/ PreOrder (bt->rchild); /*先序遍历右子树（递归调用）*/ } }

中序遍历的递归算法： void InOrder( BiTree bt) {

if (bt!=NULL){ /* 如果bt为空，结束*/

InOrder( bt->lchild); /*中序遍历左子树（递归调用）*/ visit (bt->data); /*访问根结点*/

InOrder (bt->rchild); /* 中序遍历右子树（递归调用）*/

}

}

后序遍历的递归算法： void PostOrder( BiTree bt) {

if (bt!=NULL){ /* 如果bt为空，结束*/

PostOrder( bt->lchild); /*后序遍历左子树（递归调用）*/ PostOrder (bt->rchild); /* 后序遍历右子树（递归调用）*/ visit (bt->data); /*访问根结点*/ } }

中序遍历非递归算法： void NRInOrder(BiTree bt){

BiTree S[MAXNODE], p=bt; /*定义栈S*/ int top=-1; if (bt==NULL)

return; /*空二叉树，遍历结束*/ while(!(p==NULL && top==0)){ while(p!=NULL){

if( top

S[top++]=p; /*当前指针p进栈*/

Else

{

printf(“栈溢出\\n”); return; }

p=p->lchild; /*指标指向p的左孩子结点*/ }

if(top==-1)

return; /*栈空时结束*/

else

{

p=S[--top]; /*弹出栈顶元素*/

visit(p->data); /*访问结点的数据域*/ p=p->rchild; /*指向p的右孩子结点*/ }

} }

线索二叉树： 节点结构：

规定：若节点有左孩子，则其lchild指示其左孩子，否则，令lchild域指示其前驱；若节点有右孩子，则其rchild指示其右孩子，否则，令rchild域指示其后继。

结构：

lchildLTagdataRTagrchild

typedef struct BiThrNode{ Datatype data;

struct BiThrNode *lchild, *rchild; byte LTag, RTag; }BiThrNode, *BiThrTree;

?0 lchild 域指示结点的左孩子LTag=??1 lchild域指示结点的前驱?0 rchild域指示结点的右孩子RTag=??1 rchild域指示结点的后继

以下列结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向前驱和后继的指针，叫做线索（Thread）。加上线索的二叉树叫做线索二叉树（Thread Binary Tree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

二叉排序树：

二叉排序树的任意节点大于左孩子，小于右孩子

78543723456585828794

二叉平衡树：

二叉平衡树的每个节点的左右子树深度之差不超过1

哈夫曼树：

带权路径长度最短的树

树和森林：

树转化为二叉树：

A对应BECFGD存储A∧∧BA∧∧BEC∧F∧D∧∧G∧解释C∧D∧∧E∧F∧G∧E∧F∧G∧解释存储BCEFGA∧∧BC∧D∧DA

二叉树转化为树：

加线：将结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连 抹线：去掉结点和右孩子的连线

旋转：将加线、去线后的结果，进行旋转处理，就得到转换后的树

森林转化为二叉树：

将每棵树分别转换成二叉树 将每棵树的根结点用线相连

以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

二叉树转化为森林： 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树

堆排序

查找表的基本操作

1）查询某个数据元素是否在查找表中； 2）检索某个数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。

查找表的分类 静态查找：

仅作查询和检索操作的查找表 动态查找表

进行了插入和删除

顺序表的查找 顺序查找

一个一个查找，找到则查找成功，没找到则查找失败

空间复杂度：需要一个辅助存储单元空间R[0] ，因此，顺序查找的空间复杂度为O(1)

时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较。 最好情况：第一次比较就成功找到所需数据，这时，时间复杂度为O(1)。

最坏情况：所查找的记录不在顺序表中，这时，需要和整个顺序表的记录进行比较，比较的次数为n，时间复杂度为O(n)。 平均情况：需要和顺序表中大约一半的记录进行比较，即比较次数为n/2，因而，时间复杂度为O(n)。

优点：算法简单，适用面广 缺点：平均查找长度较大。

折半查找

查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现

设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若kr[mid].key，则low=mid+1

重复上述操作，直至low>high时，查找失败 折半查找算法：

int BinarySearch(DataType SL[], KeyType key, int n){

//在长度为n的有序表SL中折半查找其关键字等于key的数据元素 //查找成功返回其在有序表中的位置，查找失败否返回0 int low=1; int high=n; while(low<=high){ mid=(low+high)/2; if(key = = SL[mid].key) {return mid;} else if( key>SL[mid].key) low=mid+1; else high=mid-1; } return 0; }

? 算法评价

? 判定树：描述查找过程的二叉树叫~ ? 有n个结点的判定树的深度为?log2n?+1

? 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 ? 折半查找的ASL

? 折半查找特点

? 折半查找的查找效率高；

? 平均查找性能和最坏性能相当接近； ? 折半查找要求查找表为有序表；

? 并且，折半查找只适用于顺序存储结构。

哈希表查找

? 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对

应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 ? 定义

? 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~

– 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象

– 哈希函数可写成：addr(ai)=H(ki)

? ai是表中的一个元素 ? addr(ai)是ai的存储地址 ? ki是ai的关键字

? 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~

? 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~

? 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可

? 冲突：key1?key2，但H(key1)=H(key2)的现象叫~ ? 同义词：具有相同函数值的两个关键字，叫该哈希函数的~

? 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法

? 哈希函数的构造方法

? 直接哈希函数法

– 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b

? 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 ? 实际中能用这种哈希函数的情况很少

? 数字分析法

– 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址

– 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况

平方取中法

取关键字平方后的中间几位作为哈希地址，即哈希函数为： H（key）=“key2的中间几位”，

其中，所取的位数由哈希表的大小确定

折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类

移位叠加：将分割后的几部分低位对齐相加

间界叠加：从一端沿分割界来回折送，然后对齐相加

适于关键字位数很多，且每一位上数字分布大致均匀情况

? 除留余数法

? 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数

作哈希地址，即H(key)=key MOD p，p?m

? 特点

? 简单、常用，可与上述几种方法结合使用

? p的选取很重要；p选的不好，容易产生同义词

? 随机数法

? 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) ? 适于关键字长度不等的情况

? 选取哈希函数，考虑以下因素：

? 计算哈希函数所需时间 ? 关键字长度

? 哈希表长度（哈希地址范围） ? 关键字分布情况 ? 记录的查找频率

冲突处理

冲突：是指由关键字得到的Hash地址上已有其他记录。 冲突处理 ：

为出现哈希地址冲突的关键字寻找下一个哈希地址。 好的哈希函数可以减少冲突，但很难避免冲突。

常见的冲突处理方法有： 开放地址法 再哈希法 链地址法

公共溢出区法

排序：

直接插入排序

把未排序的元素一个一个和已排序的元素作对比，确定插入的位置然后插入到有序的序列中。

void Direct_Insert_Sort(DataType R[], int n){

//将记录序列R按关键字作升序排列，降序排列类似 //记录从第一个位置开始存储，R[0]作为监视哨 for(i=2; i<=n;++i){

if(R[i].key

R[j+1]=R[j]; //从有序部分最后一个位置开始向前查找插入位置 R[j+1]=R[0]; //将记录插入到正确位置 } } }

折半插入排序

把未排序的元素，通过对已排序的元素进行折半查找，查找出相应的位置，然后把需要排序的元素插入到已排序的序列中。

void Binary_Insert_Sort(DataType R[], int n){

for(i=2; i<=n; ++i){ // 从第二个位置处的记录开始排序 R[0]=R[i]; //R[0]为监视哨，保存待插入的元素 low=1; high=i-1; //插入位置的初始区间

while(low<=high){ //while循环确定插入位置 mid=(low+high)/2;

if(R[0].key>R[mid].key) low=mid+1; //插入位置在前半部份 else high=mid-1; //插入位置在后半部分 }

for(j=i-1; j>=high+1; j--) //向后移动数据 R[j+1]=R[j];

R[high+1]=R[0]; //将记录插入到正确位置 } }

性能分析

折半插入排序过程中，每次在确定插入位置时，采用二分的办法，需要比较的次数至多为 log2(n+1) ，总共需要n-1趟，因此，整个排序过程需要比较的次数为O(nlog2n)。而数据的移动次数和直接插入排序算法相同，也为O(n2)。

希尔排序

冒泡排序

快速排序

归并排序和基数排序等排序算法 图：

? 无向图（Undigraph） G=(V, E)

其中，V同有向图的顶点，E为顶点之间的边集合

? 有向图（Digragh） G=（V，E）

其中，V为图的顶点集合

E为顶点之间的弧集合

顶点与边（弧）之间数量的关系 设n为顶点数，e为边或弧的条数 对无向图有：0<=e<=n(n-1)/2 有向图有：0<=e<=n(n-1)

完全图：

边达到最大的图

? 无向完全图：边数为n(n-1)/2的无向图 ? 有向完全图：弧数为n(n-1)的有向图

权：与图的边或弧相关的数 网：边或弧上带有权值的图

顶点的度

无向图：为依附于顶点V的边数

有向图：等于以顶点V为弧头的弧数（称为V的 入度，记 为ID（V））与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V））之和。即： TD（V）=ID（V）+OD（V）

路径：

无向图：顶点v到v’的路径是一个顶点序列（ v=vi0, vi1, … , vim=v’ ） 其中，（vij-1,vij ）∈E, 1<=j<=m

有向图： 顶点v 到v’的路径是有向的顶点序列（v=vi0, vi1, … , vim=v’） 其中，∈A, 1<=j<=m

路径长度：路径上边或弧的数目

回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, … , vim=v） 简单路径：路径中不含相同顶点的路径

简单回路：除首尾顶点外，路径中不含相同顶点的回路

顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的 连通图：包括无向连通图和有向连通图

无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vi<>vj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从 vj到vi的路径，则称该有向图为强连通图(vi<>vj) 连通分量：

无向图：无向图中极大连通子图，称为连通分量

有向图：有向图中极大强连通子图，称为强连通分量

子图是图的一部分，它本身也是一 个图。如果有图G=(V，E)和G′=(V′,E′)， 且V′是V的子集，E′是E的子集，则称G′ 是G的子图。

邻接顶点 在无向图中，若两个顶点之间有边连接，则这两个顶点互为邻接顶点

图的邻接矩阵和邻接表的存储表示

设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。 其中：

??1 若(vi,vj)或?vi,vj?是图G的边A[i,j]????0 若(vi,vj)或?vi,vj?不是图的边

特点：判定两个顶点Vi与Vj是否关联,只需判A[i,j]是否为1 顶点的度容易求得:

? 无向图中：TD(Vi)=∑A[i,j]=∑A[j,i] j=1 j=1 即顶点Vi的度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数之和）。

? 有向图中： TD(Vi)=OD(Vi)+ID(Vi) n n

= ∑A[i,j]+∑A[j,i] j=1 j=1

即顶点Vi的出度为邻接矩阵中第i行元素之和 顶点Vi的入度为邻接矩阵中第i列元素之和

如果G是带权的图，wij是边（vi,vj）或的权，则其关系 矩阵定义为：

?Wij 若（vi,vj）或?vi,vj?是图G的边(i?j) ?A[i,j]??? 若（vi,vj）或?vi,vj?不是图G的边(i?j) ??0 所有对角线元素?i?j? V1

579V20 5 ∞ 7 ∞ ∞4V338∞ 0 4 ∞ ∞ ∞8 ∞ 0 ∞ ∞ 9∞ ∞ 5 0 ∞ 6V61V565∞ ∞ ∞ 5 0 ∞3 ∞ ∞ ∞ 1 05V4（a) 网图4.9　网及其邻接矩阵(b) 邻接矩阵

邻接表（adjacency list） 无向图邻接表

无向图的邻接表

有向图的邻接表

与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为 弧尾的各个弧头顶点

图的深度优先和广度优先遍历

深度优先遍历：

本文来源：https://www.bwwdw.com/article/h993.html