数据结构教程(c语言)(已完结)

一、基本概念和术语

• 数据： 是客观事物的符号表示，能够输入到计算机中并能被计算机程序处理的符号的总称
• 数据元素： 是数据的基本单位，用于完整地描述一个对象
• 数据对象： 是性质相同的数据元素的集合，是数据的一个子集
• 数据项： 是组成数据元素的，有独立含义的，不可分割的最小单位
• 数据结构： 是相互之间存在的一种或者多种的特定关系的数据元素的集合，换句话说，数据结构是带结构的数据元素的集合，“结构”，就是指数据元素之间的关系。数据结构包括，逻辑结构和存储结构两个层次。

逻辑结构： 两个要素：数据元素和关系
四种基本逻辑结构：集合结构，线性结构，树结构，图结构

非线性结构：树，二叉树，有向图，无向图
线性结构：线性表（线性表，栈与队列，字符串，数组，广义表）

具体如下图：

存储结构： 数据对象在计算机中的存储表示成为数据的存储结构，也称为物理结构

顺序存储结构：
	顺序存储是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
	通常借助程序设计语言的 数组 来表示。
链式存储结构：
	顺序存储结构要求所有元素依次存放在一片连续的存储空间内
	链式存储结构，则不需要占据一整块存储空间
	只需要给每个节点附加指针，用于存放后继元素的存储地址
	通常借助于程序设计语言的 指针 来表示。

二、算法和算法分析

• 算法：是为了解决某类问题而规定的一个有限长的操作序列

  算法具有的五个特性：
  有穷性： 有限步骤，有限时间
  确定性： 不产生二义性
  可行性： 基本操作运算执行有限次来实现
  输入： 有零个或者多个输入
  输出： 有一个或者多个输出

• 评价算法优劣的基本准则：
  正确性，可读性（易于理解，相互交流），健壮性（能对非法输出做出良好的回应），高效性（时间复杂度，空间复杂在度来衡量）

---

接下来介绍时间复杂度和空间复杂度： 先来说明两个概念：

问题规模： 算法求解问题输入量的多少，是问题大小的本质表示
语句频度： 一条语句重复执行的次数

时间复杂度：(重要)

先来看个简单的例子

//求两个n阶矩阵的乘积算法
for(i=1;i<=n;i++){ //频度为 n+1
	for(j=1;j<=n;j++){ //频度为 n*(n+1)
		c[i][j]=0; //频度为 n^2
		for(k=1;k<=n;k++){ //频度为 n^2*(n+1)
			c[i][j] = c[i][j]+a[i][k]*b[k][j]; //频度为 n^3
		}
	}
}

该算法中的所有语句频度之和，是矩阵阶数n的函数
用$f(n)$表述：$$f(n)=2n^3+3n^2+2n+1$$
为了方便，我们这样来理解，至少我就是这样来理解的，忽略低阶，忽略系数，在数学中，当n无穷大时，$f(n)=n^3$，3次方对该方程的影响最大。

所以一般情况下:算法中的基本语句的，重复执行的次数，是问题规模n的某个函数$f(n)$，算法的时间度量记为：$T(n)=O(f(n))$，他表示问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，成为算法的渐进时间复杂度，简称为时间复杂度。
上述例子的时间复杂度为：O($n^3$)

加深理解，我们再来看两个例子：

{x++;s=0}//时间复杂度为O(1)	

实际上如果算大执行时间不随问题规模n的增加而增长，算法中的语句频度就是个常数，即使这个常数再大，算法的时间复杂度都是$O(1)$

再来看一个例子：

for(i=0;i<10000;i++){
	x++;
	s=0;
}
//时间复杂度仍然为O(1)

再来一个例子(对数阶)：

for(i=1;i<=n;i=i*2){x++;s=0;}
//设循环体内两条基本语句的频度为f(n),
//那么就有2^f(n)<=n,f(n)<=long2 n,时间复杂度：T(n)=O(long2 n)

i=1;
while(i<=n)
	i=i*3;
//同设：3^f(n)<=n，时间复杂度：O(long3 n)

常见的时间复杂度按数量级递增排列依次为：
$$常量阶O(1)，$$$$对数阶O(lon{g}_{2}n)，$$$$线性阶O(n)，$$$$线性对数阶O(nlon{g}_{2}n)，$$$$平方阶O(n^2)，$$$$立方阶O(n^3)，$$$$k次方阶O(n^k)，$$$$指数阶O(2^n)$$

最好时间复杂度：算法计算量可能达到的最小值
最坏时间复杂度：算法计算量可能达到的最大值
平均时间复杂度：算法在所有可能下，按输入实例以等概率出现，算法计算量的加权平均值

说明：一般情况人们只关心最坏情况下的时间复杂度，一般的时间复杂度，指的就是最坏时间复杂度

接下来举个例子说明

for(i=0;i<n;i++){
	if(a[i]==e) return i+1;
return o;
}

上述例子语句频度不止与n有关，还与输入实例中的**数组a[i]的各元素值以及e的取值有关，**假定数组中存在与e相同的值，且要查找的值就在a[0]位置，这样的情况最好，为$O(1)$，最坏的情况下为$O(n)$

---

空间复杂度

关于算法存储空间需求，类似于算法的时间复杂度，我们采用渐进空间复杂度作为算法所需存储空间的度量民间称空间复杂度，它也是问题规模n的函数，记作： $$S(n)=O(f(n))$$

一般情况下，一个程序在机器上执行时，除了需要本身所用的指令，常数，输入数据外，还需要一些对数据进行操作的辅助存储空间，其中对于输入数据所占的具体存储量取决于问题本身，与算法无关，这样，只需要分析该算法在实现时所需要的辅助空间就可以了

下面看两个例子：
均实现数组逆序
算法一

for(i=0;i<n/2;i++){
	t=a[i];
	a[i]=a[n-i-1];
	a[n-i-1]=t;
}

算法二

for(i=0;i<n;i++){
	b[i]=a[n-i-1];
}
for(i=0;i<n;i++){
	a[i]=b[i];
}

算法一仅需要借助一个变量t，与问题规模n大小无关，空间复杂度为:O(1)
算法二需要借助另外一个大小为n的辅助数组b，空间复杂度为：O(n)

总结：对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，当追求一个较好的时间复杂度时，可能会导致占用较多的存储空间，即可能会使空间复杂度的性能变差，反之亦然。不过通常情况下鉴于运算空间较为充足，人们都以算法的空间复杂度作为算法的衡量指标

三、线性表

• 基本特点：除第一个元素无直接前驱，最后一个元素无直接后继以外，其他每个基本元素都有一个前驱和后继
• 线性表是最基本最常用的一种线性结构，也是其他数据结构的基础，尤其单链表
• 定义：由$n(n\ge 0)$个数据特性相同的元素构成的有限序列称为线性表
• 空表： 线性表中元素的个数n定义为线性表的长度，n=0时为空表
• 顺序表： 线性表的顺序表示指的时用一组地址连续的存储单元依次存储线性表的数据元素，这种表示页称作表的顺序存储结构（随机存取）或顺序映像。
  顺序表特性：逻辑上相邻的数据元素，其物理地址次序也是相邻的

至于具体的线性表操作算法，此处不再赘述！ 实在想知道，[百度一下~](https://www.baidu.com/)

接下来，我们要关注的是线性链表（单链表）

• 线性链表的存储结构特点： 用一组任意的存储单元存储线性表的数据（存储单元可连续，也可不连续）

所以，数据元素$a_i$，与其直接后继元素的$a_{i+1}$的逻辑关系。对于$a_1$来说，处理本身的存储信息外，还需要一个指示其直接后继的信息（即直接后继的存储位置），这两部分组成了$a_i$ 的存储映像，即结点，它包括两个域：数据域（存储数据信息），指针域（存储直接后继的位置信息），指针域中存储的信息称为：指针或者链

以上两张图，比较全面的表示出了单链表的特点！

一般情况下，为了方便处理，我们还会再单链表的第一个节点之前附设一个节点，称为头结点，作用有如下两点：1. 便于首元结点的处理 2 .便于空表和非空表的统一处理

下面对三个容易混淆的概念加以说明：

• 首元结点： 指链表中存储第一个数据元素$a_1$的结点，例如图2.8中的结点“ZHAO”
• 头结点： 在首元结点之前的一个结点，其指针域只想首元结点，头节点的数据域可以不存储任何信息
• 头指针： 指向链表中的第一个结点的指针。若链表设有头结点， 则头指针所指结点为线性表的头结点；若链表没有设头节点，则头指针所指结点为该线性表的首元结点

同上，单链表的操作算法，不在赘述

接下里，介绍循环链表和双向链表

• 循环列表：是一种形式的链式存储结构，其特点是，表中的最后结点的指针域指向头结点，整个链表形成一个环。

• 双向链表： 顾名思义，在双向链表中有两个指针域，一个指向直接后继，另一个指向直接前驱

接下来是总结，为了方便，直接贴图！

一个公式：$$存储密度=\frac{数据元素本身所占的存储量}{结点结构占用的存储量}$$

##四、栈和队列

• 栈和队列的定义和特点

  栈：是限定仅在表尾进行插入或者删除的线性表，所以，对于栈来说，表尾端有特殊含义，称为栈顶，表头称为栈底，其最大的特点就是后进先出
  
  个人觉得，火车的例子很好理解~

  队列：是仅允许在表的一端插入，一端删除，前者那一端称为队尾，后者那一端称为队头，实际生活中，排队时最好的例子，其最大的特点是先进先出
  

• 栈的表示和操作实现

  栈的类型定义，顺序栈和链栈，初始化，增删改查！

• 栈和递归

  递归： 若是在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归

  例如：

  阶乘的定义：
  $$若n=0，则$$$$Fact(n)=1$$$$若n>0，则$$$$Fact(n)=n\ast Fact(n-1)$$
  Hanoi问题：

  • 问题描述：假设有3个分别命名为A、B、C的塔座，在塔座A上插有n个直径大小各不同，一小到大标号为1，2，…，n的圆盘，要求将塔座A上的n个圆盘移动到C盘上，并且仍按原来的顺序叠排。

    同时遵循下列规则：

    • 每次只能移动一个圆盘
    • 圆盘可以插在A、B、C中的任一塔座上
    • 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上

    
    算法如下：

    void Hanoi(int n,char A,char B,char C){
    	//将塔座A上的n个圆盘按规则搬到C上，B做辅助塔
    	if(n==1) move(A,1,C); //将编号为1的圆盘从A移动到C
    	else{
    		Hanoi(n-1,A,C,B); //将编号为1至n-1的圆盘移动到B,C做辅助塔
    		move(A,n,C); //将编号为n的圆盘从A移动到C
    		Hanoi(n-1,B,A,C); //将B上编号为1至n-1的圆盘移动到C，A做辅助塔
    	}
    }
    

    个人理解：当有3个圆盘时，怎么移动大家应该都很清楚，那么当有多个圆盘时，把最底层的两个圆盘除外，上面的所有圆盘当作整体，然后在研究这个**“整体”，如果数量还很多，可以继续使用整体思想**。

  而上述算法，则是一直递归到n=1为止，然后在把递归，一层层“翻”出来！

  递归算法优缺点：

  • 优点：程序结构清晰，形式简洁但递归程序在执行时需要系统提供隐式的工作栈来保存调用过程中的参数、局部变量和返回地址
  • 缺点：占用内存空间多，运行效率较低

与此类似的还有八皇后问题，迷宫问题等。。

• 队列的表示和操作实现

  队列也有两种存储表示：顺序存储，链式存储
  其操作实现和顺序栈类似，具体算法，具体分析，此处不再赘述
  ##五、串，数组，广义表

• 串：
  定义：是由零个或者多个字符组成的有限序列，或者称为字符串。
  特点：串是一种特殊的线性表，特殊性体现在，其处理的数据元素是一个字符。串中的字符数目n称为串的长度，领个字符的串称为空串
  子串：串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串
  位置： 通常，称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个子都在主串中的位置来表示

下面举例说明:

a = "BEI"        b = "JING"
c = "BEIJING"    d = "BEI JING"

他们的长度长度分别为：3，4，7，8
a和b都是c和d的子串
a在c和d中的位置都是1
b在c中的位置是4，在d中的位置则是5

相等的串: 当且仅当这两个串的值相等，也就是说，两个串的长度，并且对应位置的字符都相等时才相等。
空格串： 由一个或者多个空格组成的串“ ”，注意：此处并不是空串。

串的存储结构： 顺序存储，链式存储，但考虑到存储效率和算法的方便性，串多采用顺序结构

顺序存储：

//--------串的定长顺序存储结构------------
#define MAXLEN 225 //串的最大长度
typedef struct{
	char ch[MAXLEN+1]; //存储串的一维数组
	int length; //串的当前长度
}

//----------串的堆式存储结构-----------
type struct{
	char *ch; //若是非空串，则按串长分配存储区，否则ch为空
	int length； //串的当前长度
}

链式存储：

//顺序串的插入和删除不方便，需要移动大量元素，因此采用单链表方式存储串
#define CHUNKSIZE 80 //由用户定义块大小
typedef struct{
	char ch[CHUNKSIZE];
	struct Chunk *next;
}Chunk;
typedef struct{
	Chunk *head,*tail; //串的头和尾指针
	int length； //串的当前长度
}LString；

贴一张图加深理解：

下面介绍两个著名的**模式匹配算法：**应用于：搜索引擎，拼写检查，语言翻译，数据压缩等
1.BF算法
此算法是最简单直观的模式匹配算法

int Index_BF(SString S,SString T,int pos){
	//返回模式T在主串S中第pos个字符开始第一次出现的位置，若是不存在，则返回0
	//其中，T为非空，1<=pos<=S.length
	i=pos;j=1; //初始化
	while(i<=S.length && j<=T.length){//两个串均为比较到串尾
		if(S.ch[i] == T.ch[j]){//继续比较后继字符
			++i;
			++j;
		}else{//指针后退重新开始
			i=i-j+2;
			j=1;
		}
		if(j>T.length) return i-T.length;//匹配成功
		else return 0;//匹配失败
		
	}
}

下图为子模式：$T=“abcac”$和主串S匹配过程：

2.KMP算法
此算法是BF算法的改进版

int index_KMP(SString S,SString T,int pos){
	//利用模式串T的next函数求T在主串S中的第pos个字符之后的位置
	//其中，T非空，1<=pos<=S.length
	i = pos;j=1; //初始化
	while(i<=S.length && j<=T.length){//两个串均为比较到串尾
		if(j==0 || S.ch[i] == T.ch[j]){//继续比较后继字符
			++i;
			++j;
		}else{//模式串向右移动
			j=next[j];
		}
		if(j>T.length) return i-T.length;//匹配成功
		else return 0;//匹配失败
}

KMP算法是在已知模式串的next函数值的基础上进行的。
下面两张图说明函数$next()$:


以上可以看出，$next()$的函数值，取决于模式串本身。下面介绍求$next()$函数值的算法

void get_next(SString T,int next[]){
	//求模式串T的next值，并存放到数组next中
	i=1;
	next[1]=0;
	j=0;
	while(i<T.length){
		if(j==0 || T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}
		else j=next[j];
	}
}

• 数组：

  定义： 数组是由类型相同的元素构成的有序集合，每个元素称为数组元素
  特点： 结构中的元素本身可以是具有某种结构的数据，但属于统一数据类型
  数组的顺序存储：
  由于数组一般不做插入或删除操作，所以一般采用顺序存储。
  对于二维数组来说，有两种存储方式

  • 以行序为主的存储
    假设每个数据元素占L个存储单元，则二维数组$A[0...m-1,0...n-1]$ (即下标从0开始，共有m行n列)中任意元素aij的存储单元位置可由下式确定：$$LOC(i,j)=LOC(0,0)+(n\ast i+j)L$$
    式中，$LOC(i,j)$是$a_{ij}$的存储位置；$LOC(0,0)$是$a_{00}$的存储位置，即二维数组A的起始位置，也称为基地址或者基址

推广到n维数组：$$LOC(j_1,j_2,...,j_n)=LOC(0,0,...,0)+\sum _{i=1}^n{c}_i{j}_i$$$$其中，C_n=L，C_{i-1}=b_i{c}_i,1<i\le n$$

• 以列序为主的存储：
  同理有以下公式可确定位置：$$LOC(i,j)=LOC(0,0)+(m\ast i+j)L$$

特殊矩阵的压缩存储：

• 对称矩阵
• 三角矩阵
• 对角矩阵

以上，自行了解，不再赘述

• 广义表：
  定义：顾名思义广义表就是线性表的推广，也称为列表，一般记作：$$LS=(a_1,a_2,...,a_n)$$$$其中，LS是广义表的名字，n是其长度$$$$ai既可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表$$

举例如下：

• A=() ——A是一个空表，其长度为0
• B=(e) ——B只有一个原子e，其长度为1
• C=(a,(b,c,d)) ——C的长度为2，两个元素分别为原子a和子表（b,c,d）
• D=(A,B,C) ——D的长度为3，3个元素都是广义表，可以将值带入
• E=(a,E) ——E的长度为2，这是一个递归表，E相当于一个无限广义表E=(a,(a,(a,…)))

由上述例子得出三个结论

• 广义表的元素可以是子表，而子表的元素还可以是子表，由此，广义表是一个多层次结构
• 广义表可以为其他广义表所共享，由D可以看出
• 广义表可以是一个递归的表

广义表的运算

• 取表头
• 取表尾

注意：广义表()和(())不同，前者为空表，长度为0，后者长度为1，可分解得到其表头，表尾均为空表()

广义表的存储结构
通常情况，采用链式存储结构，分为两种：

• 头尾链表的存储结构
• 扩展线性链表的存储结构

以上两种结构，自行了解，此处不再赘述

六、树和二叉树

• 树和二叉树的定义：
  树： 是$n（n\ge 0）$个结点的有限集，它或为空树（n=0），或为非空树，对于非空树T：
  • 有且仅有一个称之为根的结点；
  • 出根节点以外的其余结点可分为$m（m>0）$个互不相交的有限集$T_1,T_2,...,T_m$，其中每一个集合本身又是一棵树，并且称为根的子树

树的一般表示：

树的其他表示：

• 嵌套集合形式：
  

• 广义表形式：
  

• 凹入表示法(类似书的编目)：
  
  树的基本术语：

  • 结点： 树中的一个独立单元，包含一个数据元素及若干指向子树的分支，如图5.1(b)中的A,B,C,D等（下面术语，均以图5.1（b）为例）
  • 结点的度： 结点拥有的子树数称为结点的度，例如，A的度为3，C的度为1，F的度为0
  • 树的度： 树的度是树内各结点度的最大值，5.1（b）所示的树的度为3
  • 叶子： 度为0的结点称为叶子或者终端结点。结点K,L,F,G,M,I.J都是树的叶子
  • 非终端结点： 度不为0的结点称为非终端结点或者分支结点，除根结点，非终端结点也称为内部结点
  • 双亲和孩子： 结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲，例如：B的双亲为A，B的孩子由E和F
  • 兄弟： 同一个双清的孩子之间互称为兄弟，例如H,I,J互为兄弟
  • 祖先： 从根到该结点所经分支上的所有结点，例如：M的祖先为A，D，H
  • 子孙： 以某结点为根的子树中的任一结点都称为该结点的子孙，如B的子孙为E，K，L，F
  • 层次： 结点的层次从根结点定义起，根为第一层，根的孩子为第二层，树中任一结点的层次等于其双亲层次加1
  • 堂兄弟： 双亲在同一层的结点互为堂兄弟。例如：结点G与E，F，H，J，I为堂兄弟
  • 树的深度： 树中的结点的最大层次称为树的深度或高度，例子中的深度为4
  • 有序树和无序树： 如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子
  • 森林： 是$m（m\ge 0）$棵互不相交的树的集合，对于树中每个结点而言，其子树的集合即为森林

  二叉树：

  • 定义： 是$n（n\ge 0）$个结点所构成的集合，它或为空树或为非空树，对于非空树T：

    • 有且仅有一个称之为根的结点；

  • 除根结点以外的其余结点分为两个互不相交的子集$T_1，T_2$，分别称为T的左子树和右子树，且$T_1，T_2$本身又都是二叉树

  • 二叉树与树的区别

    • 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）

  • 二叉树的子树有左右之分，其次顺序不能任意颠倒

  • 二叉树的性质和存储结构：

    性质：

    • 性质1： 在二叉树的第i层上至多有$2^{i-1}$个结点（i≥1），至少有1个
    • 性质2： 深度为k的二叉树至多有$2^{k-1}$个结点（k≥1），至少有k个
    • 性质3： 对任一棵二叉树T，如果其终端结点数为n，度为2的结点数为m，则n=m+1

  接下来，先介绍满二叉树和完全二叉树

• **满二叉树：**深度为k且含有$2^{k-1}$个结点的二叉树
  特点：
  - 每一层上的结点数都是最大结点数
  - 对满二叉树的结点进行连续编号，约定编号从根结点开始，自上而下，自左向右，由此得出完全二叉树的概念

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

  特点：

  • 叶子结点只可能是在层次最大的两层出现；
  • 对于任一结点，若其右分支下的子孙的最大层次为 i，则其左分支下的子孙的最大层次必为 i 或者 i+1

  性质：

  • 性质4： 假设深度为k，则根据性质2和完全二叉树的定义有$$2^{k-1}-1<n\le 2^{k-1}或者2^{k-1}\le n＜2^k$$于是$k-1\le lo{g}_{2}n＜k，因为k是整数，所以k=\lfloor lo{g}_{2}n\rfloor +1$
  • 性质5： 如果对一棵树有n个结点的完全二叉树（其深度为$\lfloor lo{g}_{2}n\rfloor +1$）的结点按层序编号（从第一层到第$\lfloor lo{g}_{2}n\rfloor +1$层，每层从左到右），则对任一结点$i(1\le i\le n)$，则有：
    • (1)如果i=1，则结点i是二叉树的根，无双亲，如果i>1，则其双亲PARENT(i)是接待你$\lfloor i/2\rfloor$
    • (2)如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i
    • (3)如果2i+1>n，则几点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1

  符号说明：

  • $\lfloor x\rfloor$表示不大于$x$的最大整数
  • $\lceil x\rceil$表示不小于$x$的最小整数
    

  存储结构：

• 顺序存储结构
  适用于完全二叉树，按层序存储，一般的二叉树会造成空间的浪费

• 链式存储结构
  类似于线性表，设置数据域，左右指针域
  

• 遍历二叉树：

  • 遍历二叉树： 是指按某条搜索路径巡访树中的每个结点，使得每个接待你均被访问一次，而且仅被访问一次

    • 约定：L,D,R分别代表遍历左子树，访问根结点，遍历右子树
    • 访问方法：一般有三种方式：前序遍历（DLR），中序遍历（LDR），后序遍历（LRD），这是在不分左右的情况下，如果分左右，可得到另外三种访问方式
    • 结论：得知前序遍历和中序遍历或者中序遍历和后序遍历，可以画出该二叉树，前序遍历和后续遍历不能确定唯一的一棵二叉树

    下面举个例子：
    先来看看几个特性：
    - 特性A，对于前序遍历，第一个肯定是根节点；

    • 特性B，对于后序遍历，最后一个肯定是根节点；
    • 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
    • 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；

    题目：前序遍历的顺序是: CABGHEDF，中序遍历的顺序是: GBHACDEF，画出这棵二叉树，找到其后序遍历
    解:
    

• 哈夫曼树：

  • 定义：哈夫曼树又称最优树，是一类带权路径长度最短的树

  接下来介绍一些基本概念：

  • 路径： 从树的一各结点到另一个结点之间的分支构成两个结点之间的路径
  • 路径长度： 路径上的分支数目称作路径长度
  • 树的路径长度： 从树根到每一个接待你的路径长度之和
  • 权： 赋予某个实体一个量，是对实体的某个或某些属性的数值化描述，在数据结构中实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由实际情况决定，如果在一棵树中的结点上带有权值，则对应的就带有权树等概念
  • 结点的带权路径长度： 从该结点到树根之间的路径长度与结点上权的乘积
  • 树的带权路径长度： 树中所有叶子结点的带权路径长度之和，通常记作:$$\sum _{k=1}^n{w}_k{l}_k$$
  • 哈夫曼树：假设有m个权值 { w 1 , w 2 , . . . , w m } \{w_1,w_2,...,w_m\} { w1​,w2​,...,wm​}，可以构造一棵含有n个叶子结点的二叉树，每个叶子结点的权为$w_i$，其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树
    
    上图（c）即为哈夫曼树

那么如何构造一棵哈夫曼树呢？
哈夫曼树构造过程：

• 根据给定的n个权值 { w 1 , w 2 , . . . , w n } \{w_1,w_2,...,w_n\} { w1​,w2​,...,wn​}，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
• 在森林F中选取两棵根结点权值最小的树最为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
• 在森林F中删除这两棵树，同时将新的到的二叉树加入F中
• 重复第二步，第三步，直到F中含有一棵树为止，这棵树便是哈夫曼树
  

七、图

• 图定义和基本术语：

• 定义：图G由两个集合V和E组成，记作$G=(V,E)$，其中V是顶点的有穷非空集合，E是V中的顶点偶对的有穷集合，这些顶点偶对称为边。$V(G)$和$E(G)$通常分别表示图G的顶点集合和边集合，$E(G)$可以为空集。若$E(G)$为空，则图G只有顶点而没有边。

  对于图G，若边集$E(G)$为有向边的集合，则该图为有向图；反之，则该图为无向图。
  在有向图中顶点对用尖括号表示，例如：$<x,y>$是有序的
  在无向图中用圆括号表示，例如：$(x,y)$是无序的。
  
  用n表示图中的顶点数目，用e表示边的数目，来说明一些基本术语：

  • 子图： 假设有两个图$G=(V,E)$和$G^{\prime }=(V^{\prime },E^{\prime })$，如果$V^{\prime }\in V$且$E^{\prime }\in E$，则称$G^{\prime }$为$G$的子图
  • 无向完全图和有向完全图： 对于无向图，若具有$n(n-1)/2$条边，则称为无向完全图，对于有向图，若具有$n(n-1)$条弧，则称为有向完全图
  • 稀疏图和稠密图： 有很少条边或弧（如$e<nlo{g}_{2}n$），的图称为稀疏图，反之称为稠密图
  • 权和网： 每条边可以标上具有某种意义的数字，该数值就称为该边的权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网
  • 邻接点： 对于无向图G，如果图的边$(v,v^{\prime })\in E$，则顶点v，v’称为邻接点。
  • 度，入度，出度： 顶点y的度是指和y相关联的边的数目，记为$TD(v)$，入度是指以顶点v为头的弧的数目记作$ID(v)$，出度是以v为顶点的弧数目，记作$OD(v)$ ，三者满足：$TD(v)=ID(v)+OD(v)$。一般的满足：$$e=\frac{1}{2}\sum _{i=1}^{n}TD(v_i)$$例如：图6.1中，$G_1$中$V_1$的出度为2，入度1，度为3
  • 路径和路径长度： 在无向图G中，从顶点v到顶点v’的路径是一个顶点序列集合，如果是有向图，那么路径也是有向的。路径长度是一条路径上经过的边或弧的数目
  • 回路或环： 第一个顶点和最后一个顶点相同的路径
  • 简单路径，简单回路，简单环： 序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环
  • 连通，连通图，连通分量： 在无向图中，两个顶点之间有路径，则称这两个顶点之间是连通的，如果一个图中的任意两个顶点之间连通，则称该图为连通图，连通分量是指无向图中的极大连通子图
  • 强连通图，强连通分量： 在有向图中，如果任意两个顶点（不相等的两个顶点），之间都存在路径。则称该图为强连通图，有向图中的极大连通子图称为有向图的强连通分量
  • 连通图的生成树： 一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边，这样的连通子图称为连通图的生成树

• 图的存储结构：

• 邻接矩阵

  • 表示顶点之间相邻关系的矩阵，设G（V,E）是具有n个顶点的图，则矩阵具有如下性质：$$若<v_i,v_j>或(v_i,v_j)\in E$$$$则A[i][j]=1$$$$反之$$$$A[i][j]=0$$
    下图是图6.1所示$G_1$$G_2$的邻接矩阵
    
    若G是网：
    
    邻接矩阵的优点：

    • 便于判断两个点之间是否有边
    • 便于计算各个顶点的度

    邻接矩阵的 缺点：

    • 不便于增加和删除顶点
    • 不便于统计边的数目
    • 空间复杂度高

• 邻接表
  邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点$v_i$建立一个单链表，把与$v_i$相邻接的顶点放在这个链表中，邻接表中每个单链表的第一个结点存放有关顶点的信息，把这以结点看出链表的表头，其余节点存放有关边的信息，这样，邻接表便有两部分组成，表头结点表和边表

  • 表头结点表：由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表。表头结点包括数据域和链域
  • 边表：由表示图中顶点间关系的2n个边链表组成，边链表中边结点包括邻接点域，数据域，链域
    
    下图为表示图6.1的邻接表
    
    注意：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一

  邻接表优点：

  • 便于增加和删除顶点
  • 便于统计边的数目
  • 空间效率高

  邻接表缺点：

  • 不便于判断顶点之间是否有边
  • 不便于计算各个顶点的度

• 十字链表
  十字链表是有向图的另一种链式存储结构。可以看成将有向图的邻接表和逆邻接表结合起来得到的一种链表。
  在十字链表中，对应有向图中每一条弧由一个结点，对应每个顶点也有一个结点
  
  在弧结点中有5个域：

  • 尾域（tailvex）：弧尾这个顶点在图中的位置
  • 头域（headvex）：弧头这个顶点在图中的位置
  • 链域（hlink）：指向弧头相同的下一条弧
  • 链域（tlink）：指向弧尾相同的下一条弧
  • info域（info）：指向弧的相关信息

  在顶点结点中有3个域：

  • data：存储和顶点相关的信息
  • firstin：指向该顶点为弧头的第一个弧结点
  • firstout：指向该顶点为弧尾的第一个弧结点
    

• 图的遍历：

图的遍历类似于树的遍历们也是从图中某一顶点出发，按照某种方法对图中所有顶点访问且仅访问一次，图的遍历算法是求解图的连通性问题，拓扑排序和关键路径等算法的基础

根据搜索路径的方向：有两条遍历图的路径：

首先说明：这两种方法对有向图和无向图都适用

• 深度优先搜索（depth first search DFS）

• 这种遍历类似于树的前序（先序）遍历，是树的线序遍历的推广

  • （1）从图中某个顶点v出发，访问v
  • （2）找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点，以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止
  • （3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点
  • （4）重复（2）（3），直到图中所有顶点都被访问过，搜索结束

• 广度优先搜索 （breadth first search BFS）

  • （1）从图中某个顶点v出发，访问v
  • （2）依次访问v的各个未曾访问过的邻接点
  • （3）分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，重复步骤（3）直到图中所有已被未访问的顶点的邻接点都被访问到

  接下来看个例子：
  
  可以看出：
  DFS的访问序列为：

  • $v_1\to v_2\to v_4\to v_8\to v_5\to v_3\to v_6\to v_7$

  BFS的访问序列为：

  • $v_1\to v_2\to v_3\to v_4\to v_5\to v_6\to v_7\to v_8$

  图中以带箭头的粗实线表示遍历时的访问路径，以带箭头的虚线表示回溯路径，小圆圈表示已经被访问过的邻接点，大圆圈表示未被访问的邻接点

  至于两者的算法实现：只做一点说明：遍历过程为了区别顶点是否被访问，需要附设一个标志数组visited[n]，其初值为“false”，一旦顶点被访问，相应的分量置为“true”，其他情况，具体问题具体分析

• 图的应用：

• 最小生成树：在一个连通网中，各边代价之和最小的那棵生成树为该连通网的最小代价生成树，简称最小生成树

  • 具体算法应用有：
    • 普里姆算法
    • 克鲁斯卡尔算法

• 最短路径：从源点到终点的所有路径中，路径上的边的权值之和最小的即为最短路径

  • 具体算法应用有：
    • 迪杰斯特拉算法
    • 弗洛伊德算法

• 拓扑排序算法

• 关键路径算法

以上四点就是图的应用，具体算法，自行查找
下来是一个小结：

八、查找

• 查找的基本概念：
• 查找表：是同一类型的数据元素（或记录）构成的集合。
• 关键字：是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录） 。若此关键字可以唯一标识一个记录，则称此关键字为主关键字（不同记录，不同主关键字），反之，称用以识别若干记录关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值
• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样一个记录，则查找成功，此时查找结果可以给出整个记录信息，或指示该记录在查找表中的位置，若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找结果可以给出一个“空”记录或“空”指针
• 动态查找表和静态查找表：若查找的同时对表做修改操作（如：插入和删除），则相应的表称为动态查找表，反之，称为静态查找表
• 平均查找长度： 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为在查找成功时的平均查找长度。
  对含有n个记录的表，查找成功时的平均查找长度为：$$ASL=\sum _{i=1}^n{P}_i{C}_i$$其中，$P_i$为查找表中第$i$个记录的概率，且${\sum }_{i=1}^n{P}_i=1$；$C_i$为找到表中其关键字与给定值相等的第$i$个记录时，和给定值已进行比较过的关键字个数。显然，$C_i$随查找过程不同而不同
• 线性表的查找:
• 顺序查找
  • 过程：从表的一端开始，依次将记录的关键字和给定值进行比较，若记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败 。顺序查找，前面已经介绍过了，此处不再赘述
• 二分查找
  • 二分查找也称折半查找，它是一种效率较高的查找方法，但是，折半查找要求线性表必须采用顺序存储结构

例如：已知如下 11个数据元素的有序表(关键字即为数据元素的值)
（5，16，20，27，30，36，44，55，60，67，71）
查找27,65的过程：

• 分块查找
  • 分块查找又称索引顺序查找，这是一种性能介于顺序查找和二分查找之间的一种查找方法。在此方法中，除表本身外，尚需建里一个索引表。
    
    这样，分块查找分为两步，先和索引表做比较，在确定子表。例如：查找38，22<38<48，如果38存在，那么一定在第二子表中，然后在该子表中做顺序查找

分块查找的平均查找度：
将长度为n的表，平均分为b块，每个块有s个记录，即$b=\lceil n/s\rceil$假定表中每个记录的查找概率相等，则，每块查找的概率为$1/b$，块中每个记录的查找概率为$1/s$，设$L_b，L_w$分别为：查找索引表确定所在的块的平均查找长度，在块中查找元素的平均查找长度。则分块查找的平均查找长度为：$$AS{L}_{bs}=L_b+L_w=\frac{1}{b}\sum _{j=1}^{b}j+\frac{1}{s}\sum _{i=1}^s=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1$$可见，此时的平均查找长度不仅与n有关还和s有关，容易证明当$s=\sqrt{n}$时，平均查找长度取到最小值$\sqrt{n}+1$，但其远不及折半查找

分块查找的优缺点：

• 优点：在表中插入和删除数据元素时，只需要找到该元素对应的块，就可以在该块内进行插入和删除运算
• 缺点：要增加一个索引表的存储可见并对初始索引进行排序运算

树表的查找:

• 二叉排序树

  • 二叉排序树又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树

  • 二叉排序树定义：二叉排序树或者式一棵空树，或者是具有下列性质的二叉树

     （1） 若**左子树**不空，则左子树上所有结点的值**均小于它的根结点的值**
     （2） 若**右子树**不空，则右子树上所有结点的值**均大于它的根结点的值**
     （3）它的左，右子树分别也为二叉排序树
    

  由二叉排序树的定义（递归定义）得知一个重要性质：中序遍历一棵二叉树时，可以得到接待你值递增的有序序列

  所以在二叉排序树上进行查找和折半查找类似

• 平衡二叉树

  • 定义：或者是空树，或者是具有以下性质的二叉排序树

    • 左子树和右子树的深度之差的绝对值不超过1；

    • 左子树和右子树也是平衡二叉树

      若将二叉树上的所有结点的定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是1 0 -1 。如下图
      

• 散列表的查找:

• 散列表查找又叫哈希表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。即：
  —存储位置=f（关键字），其中f为哈希函数。

  • 几个基本术语:
  • 散列函数和散列地址：在记录的存储位置$p$和其关键字$key$之间建立一个确定的对应关系$H$，使$p=H(key)$,称这个对应关系$H$为散列函数，$p$为散列地址。
  • 散列表：一个有限连续的地址空间，所以存储按散列函数计算得到的相应散列地址的数据记录，通常散列表的存储空间是一个一维数组，散列地址是数组的下标
  • 冲突和同义词：对不同的关键字可能得到同一散列地址，即$ke{y}_1\ne ke{y}_2$，然而$H(ke{y}_1)=H(ke{y}_2)$，这种现象称为 冲突，具有相同函数值的关键字对该散列函数来说称作同义词，$ke{y}_1和ke{y}_2$互称为同义词
  • 哈希表的构造方法：
    • 直接定址法
    • 数字分析法
    • 平方取中法
    • 折叠法
    • 除留余数法
  • 处理冲突的方法：
  • 开放地址法
    • 线性探测法
    • 二次探测发
    • 伪随机探测法
  • 链地址法
    
    图中装填因子α定义为：$$\alpha =\frac{表中填入的记录数}{散列表的长度}$$α标志散列表的装满程度

下来，是一个小结：

九、排序

• 基本概念和方法：
• 排序： 是按关键字的非递减或非递增顺序对一组记录进行重新排列的操作
• 排序稳定性：当排序记录中的关键字右两个或以上的关键字记录相等时。假设$k_i=k_j(i\ne j，i，j都在范围内)$，且排序前的序列中$R_i$领先$R_j$即$i<j$若排序后$R_i$仍然领先$R_j$那么，称所使用的排序方法是稳定的，反之，称为不稳定
• 内部排序和外部排序：内部排序是指排序记录全部存放在计算机内存中进行排序的过程，外部排序是指排序记录数量很大，内存不能全部容纳，在拍戏过程中尚需对外村进行访问的排序过程
• 内部排序的分类：
  • 插入类：
    • 插入排序
    • 折半插入排序
    • 希尔排序
  • 交换类：
    • 冒泡排序
    • 快速排序
  • 归并类：
    • 2-路归并排序
  • 分配类：
    • 基数排序
  • 选择类：
    • 简单选择排序
    • 树形选择排序
    • 堆排序
• 插入排序：
  • 直接插入排序
    • 最简单的排序方法，基础操作为：将一条记录插入到已排好序的有序表中
      
      时间复杂度为：$O(n^2)$
      空间复杂度为：$O(1)$
  • 折半插入排序
    • 在直接插入排序的基础上增加“折半查找”这一操作，例如，在图8.1中，在每一次插入新的数据时，都得从第一个元素开始比较，而折半插入排序，则是，每次“比较”都使用折半查找找到要插入数据的该插入位置，而不是一个个的比较。
    • 时间和空间复杂度和直接插入排序相同
    • 此算法时稳定排序
    • 适用于顺序结构，
    • 适用于初始记录无须，n较大
  • 希尔排序
    • 又称缩小增量排序，希尔排序，从减少记录个数和序列基本有序，两个方面对直接插入排序进行改进
    • 本质上时采用分组插入法
      
      d代表所有间隔为d的记录在一组。对组两头的数据进行交换即可
• 交换排序：
  • 冒泡排序：
    • 是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而实现排序
      
      时间复杂度：$O(n^2)$
      空间复杂度：$O(1)$
  • 快速排序

    • 由冒泡排序改进而来，在冒泡排序中，支队相邻的两个记录进行比较，因此每次交换两个相邻的记录只能消除一个逆序，如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大增加排序的速度。快速排序即可一次交换消除多个逆序
      
      说明：

      • 先选择排序表中的第一个记录作为枢轴（pivotkey），将其暂时记录在r[0]的位置，附设两个指针low和high，分别指向表的下界和上界
      • 从表的右侧依次向左搜索，找到第一个关键字小于枢轴关键字的记录，将其移动到low处
      • 从表的左侧依次向右搜索，找到第一个关键字大于枢轴关键字的记录，将其和枢轴关键字交换位置。
      • 重复第二步和第三步，直到low和high相等

      时间复杂度：$O(nlo{g}_{2}n)$
      空间复杂度：

      • 最好情况下：$O(lo{g}_{2}n)$
      • 最坏情况下：$O(n)$
• 选择排序：
  • 选择排序的基本思想：每一趟从待排序的记录中选出关键字最小的记录，放到已排序的序列中，重复直到全部拍完
    • 简单选择排序：
      • 也称为直接选择排序
        
        
        时间复杂度：$O(n^2)$
        空间复杂度：$O(1)$
    • 树形选择排序：
      • 又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法，首先对n个记录的关键字进行两两比较，然后在其中$[\frac{n}{2}]$个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。这个记录可用一棵由n个叶子结点的完全二叉树表示。
        
        接下来，看一种树形选择排序
    • 堆排序：
      • 堆排序是一种树形选择排序，是维洛姆斯在1964年提出的，在该排序过程中，将待排序的记录 r[1…n] 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录
      • 堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。
      • 其实我们的堆排序算法就是抓住了堆的这一特点，**每次都取堆顶的元素，将其放在序列最后面，**然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。
        
        时间复杂度：$O(nlo{g}_{2}n)$
        空间复杂度：$O(1)$
• 归并排序：
  • 归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。
  • 2-路归并：
    • 将两个有序表合并成一个有序表的过程称为2-路归并
    • 思想：假设初始序列由含有n个记录，则可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1 的有序子序列，在两两归并，…，如此重复，直至得到一个长度为n的有序序列为止。
      
      时间复杂度：$O(nlo{g}_{2}n)$
      空间复杂度：$O(n)$
• 基数排序：

  • 基数排序与前面的排序方法都不同，它不需要比较关键字的大小。它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。 例如：扑克牌的按花色分配收集和按面值分配收集
    例如：

    • 初始序列： R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}

    我们知道，对于数字来说，个十百位的数字无非0~9，所以先按个位分类得到：

接下来，按照，0~9的顺序，排列得到 ：
{50, 30, 0, 100, 11, 2, 123, 543, 187, 49}
同理，按十位数排列，百位数排列，…，最后得到的必然是有序序列

• 外部排序：
  • 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的

转载：https://blog.csdn.net/Song_JiangTao/article/details/79717012