Catologue

C语言数据结构一、基本概念和术语二、时间、空间复杂度（1）时间复杂度（2）空间复杂度 三、类C语言有关操作补充1：数组定义补充2：动态内存分配补充3：C++中的参数传递 四、线性表（1）定义（2）线性表的表示和实现1、线性表的==顺序==表示和实现2、顺序表的优缺点3、线性表的==链式==表示和实现a、单链表的实现b、单向循环链表的实现c、双向链表的实现d、双向循环链表的实现 4、链表的优缺点 （3）单链表、循环链表、双向链表的时间效率比较（4）顺序表和链表的比较（5）案例引入1、线性表的应用2、一元多项式的运算3、图书管理系统 五、栈和队列（1）栈（LIFO）（2）栈的表示和实现1、栈的==顺序==表示和实现2、栈的==链式==表示和实现 （3）栈与==递归==（4）队列（FIFO）（5）队列的表示和实现1、队列的==顺序==表示和实现2、队列的==链式==表示和实现 六、串、数组和广义表（1）串（2）串的表示和实现1、串的==顺序==表示2、串的==链式==表示3、串的模式匹配算法 （3）数组（4）数组的表示（5）广义表 七、树和二叉树（1）树（2）二叉树（3）二叉树的表示1、二叉树的==顺序==存储结构2、二叉树的==链式==存储结构 （4）二叉树的遍历1、==先序==遍历的实现2、==中序==遍历的实现3、==后序==遍历的实现4、中序遍历的==非递归==算法5、二叉树的==层次==遍历 （5）二叉树遍历算法的==应用==1、二叉树的建立2、复制二叉树3、计算二叉树的深度4、计算二叉树结点的总个数5、计算二叉树叶子结点的总个数 （6）==线索==二叉树（7）树的存储结构1、双亲表示法2、孩子链表3、孩子兄弟表示法（二叉树表示法）4、树和二叉树的转换5、森林和二叉树的转换 （8）树与森林的遍历1、树的遍历2、森林的遍历 （9）==哈夫曼树==（10）哈夫曼树的表示1、哈夫曼树的==顺序==存储结构 （11）哈夫曼编码 八、图（1）图的定义（2）图的表示1、==数组==（邻接矩阵）表示法2、==链表==（邻接表）表示法 （3）图的遍历1、==深度==优先搜索遍历（Depth First Search --- DFS）2、==广度==优先搜索遍历（Breath First Search --- BFS） （4）图的应用1、最小生成树2、最短路径3、拓扑排序4、关键路径 九、查找（1） 查找表（2）线性表的查找1、顺序查找（线性查找）2、二分查找3、分块查找 （3）树表的查找（4）==哈希表==的查找 十、排序（1）插入排序1、直接插入排序2、折半插入排序3、==希尔==排序 （2）交换排序1、冒泡排序2、==快速==排序 （3）选择排序1、直接选择排序2、==堆==排序 （4）归并排序（5）基数排序（6）排序算法小结 附录A- ASCII

C语言数据结构

---

一、基本概念和术语

**数据（data）**是对客观事物的符号表示。

**数据元素（data element）**是数据中的基本单位，在计算机程序中作为一个整体进行考虑和处理。

**数据对象（data object）**是性质相同的数据元素的集合，是数据的一个子集。

数据结构（data structrue）是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下4类基本逻辑结构：1、集合，结构中的数据元素之间除了同属于一个集合的关系外，别无其他关系；2、线性结构，结构中的数据元素之间存在一个对一个的关系；3、树形结构，结构中的元素之间存在一个对多个的关系；4、图状结构或网状结构，结构种的数据元素之间存在多个对多个的关系。存储结构也有四种：1、顺序结构，2、链式结构，3、索引结构，4、散列结构

C语言缺少类这一关键字，所以一般使用结构体和函数搭配起来构造数据类型，举个例子构造复数数据类型:

//定义复数数据类型#include <stdio.h>typedef struct { float realpart;float imagpart;} Complex;void assign(Complex* A, float real, float image);void add(Complex* C, const Complex A, const Complex B);void minus(Complex* C, const Complex A, const Complex B);void multiply(Complex* C, const Complex A, const Complex B);void divide(Complex* C, const Complex A, const Complex B);void assign(Complex* A, float real, float imag){ A->realpart = real;A->imagpart = imag;}void add(Complex* C, const Complex A, const Complex B){ C->realpart = A.realpart + B.realpart;C->imagpart = A.imagpart + B.imagpart;}void minus(Complex* C, const Complex A, const Complex B){ C->realpart = A.realpart - B.realpart;C->imagpart = A.imagpart - B.imagpart;}void multiply(Complex* C, const Complex A, const Complex B){ C->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;C->imagpart = A.realpart * B.imagpart + A.imagpart * B.realpart;}void divide(Complex* C, const Complex A, const Complex B){ Complex temp;Complex B1;B1.realpart = B.realpart;B1.imagpart = -B.imagpart;multiply(&temp, A, B1);C->realpart = temp.realpart / (B.realpart * B.realpart + B.imagpart * B.imagpart);C->imagpart = temp.imagpart / (B.realpart * B.realpart + B.imagpart * B.imagpart);}

---

二、时间、空间复杂度

（1）时间复杂度

算法的时间效率分析采用事前分析法

​ 我们假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论该算法中所有语句的执行次数，即语句频度之和。举一个例子：

该算法的时间效率就为 T ( n ) = 2 n 3 + 3 n 2 + 2 n + 1 T(n)=2n^3+3n^2+2n+1 T(n)=2n3+3n2+2n+1，但是这样计算过于麻烦，于是，为了比较不同算法的时间效率，我们仅仅比较它们的数量级。该算法的时间效率即为 O ( n 3 ) O(n^3) O(n3)。

​ 引入时间复杂度的概念：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数 f ( n ) f(n) f(n)算法的时间度量记作

T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中 O O O是数量级符号 O r d e r Order Order。

时间复杂度定义中所指的基本语句是在算法的执行过程中重复最多的语句，时间复杂度实际上是由嵌套层次最深语句的频度决定的。例如：

对于较为复杂的时间复杂度计算问题，可以采用级数的方法来进行计算，例如：

在考虑算法的时间复杂度时，还需要考虑问题的规模和问题的形式，因此，出现了：

最坏时间复杂度：指在最坏的情况下，算法的时间复杂度。

最好时间复杂度：指在最优的情况下，算法的时间复杂度。

平均时间复杂度：指在所有可能输入实例等概率出现的情况下，算法的期望运行时间。

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大 O O O的运算规则，计算算法的时间复杂度：

加法规则： T ( n ) = T 1 ( n ) + T 2 ( n ) = O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

乘法规则： T ( n ) = T 1 ( n ) × T 2 ( n ) = O ( f ( n ) ) × O ( g ( n ) ) = O ( f ( n ) × g ( n ) ) T(n)=T1(n) \times T2(n)=O(f(n)) \times O(g(n))=O(f(n) \times g(n)) T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

（2）空间复杂度

​ 引入空间复杂度的概念：空间复杂度作为算法所需存储空间的度量，记作

S ( n ) = O ( f ( n ) ) S(n)=O(f(n)) S(n)=O(f(n))

其中 n n n为问题大小的规模。算法要占据的空间包括，算法本身要占据的空间，输入/输出，指令，常数，变量等，算法在执行时所需的辅助空间。

例题：

---

三、类C语言有关操作

补充1：数组定义

补充2：动态内存分配

补充3：C++中的参数传递

C++特有的引用类型作为参数：

---

四、线性表

（1）定义

​ 线性表是具有相同特性元素的一个有限序列，数据元素之间是线性关系， ( a 1 , a 2 , … , a i − 1 , a i , a i + 1 , … , a n ) ⏟ 数 据 元 素 \underbrace{(a_1,a_2, \dots,a_{i-1},a_i,a_{i+1},\dots,a_n)}_{数据元素} 数据元素 (a1​,a2​,…,ai−1​,ai​,ai+1​,…,an​)​​，起始元素称为线性起点，终端元素称为线性终点。

线性表具有如下的特点：

(1)存在唯一的一个被称为“第一个”的数据元素；

(2)存在唯一的一个被称为“最后一个”的数据元素；

(3)除第一个元素外，集合中的每个元素均只有一个前驱；

(4)除最后一个元素外，集合中的每个元素均只有一个后继。

（2）线性表的表示和实现

1、线性表的顺序表示和实现

​ 线性表的顺序表示又称为顺序存储结构或者顺序映像。顺序存储的定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。换句话说，以元素在计算机内存中**“物理位置相邻”**来表示线性表中数据元素之间的逻辑关系。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序结构是一种随机存取的存储结构。

​ 顺序表中元素存储位置的计算：假设线性表中的每个元素需要占据 l l l个存储单元，则第 i + 1 i+1 i+1个数据元素的存储位置和第 i i i个数据元素的存储位置之间的关系满足

L O C ( a i + 1 ) = L O C ( a i ) + l LOC(a_{i+1})=LOC(a_i)+l LOC(ai+1​)=LOC(ai​)+l

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

L O C ( a i ) = L O C ( a 1 ) + ( i − 1 ) × l LOC(a_i)=LOC(a_1)+(i-1)\times{l} LOC(ai​)=LOC(a1​)+(i−1)×l

由此可以看出顺序表的特点是：1、以物理位置表示相邻的逻辑关系；2、任意的元素均可以快速访问，故称为随机存取。

顺序表（Sequence List）的类型定义模板：

//顺序表定义模板#define LIST_INIT_SIZE 100//顺序表存储空间的初始分配typedef struct { ElemType* elem;//数据指针，动态分配存储空间 int length;//当前的长度} SqList;

使用类型定义模板的案例：

顺序表的示意图：

在一些较为复杂的时间复杂度计算的问题中，我们往往采用问题的时间复杂度期望来作为整体问题的复杂度，例如在顺序表中计算插入算法的时间复杂度或者是计算删除算法的时间复杂度：

//头文件包含#include <stdio.h>#include <stdlib.h>//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status 是函数的类型，其值是函数结果状态代码typedef int Status;typedef char ElemType;//顺序表的定义#define MAXSIZE 100typedef struct { ElemType* elem;int length;} SqList;//顺序表的初始化函数Status InitList_Sq(SqList* L){ L->elem = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));if (!L->elem)exit(OVERFLOW);L->length = 0;return OK;}//销毁线性表void DestroyList_Sq(SqList* L){ if (L->elem)free(L->elem);L = NULL;}//清空线性表void ClearList(SqList* L){ L->length = 0;}//求线性表的长度int GetLength(const SqList* L){ return L->length;}//判断线性表是否为空Status IsEmpty(const SqList* L){ if (L->length == 0)return TRUE;elsereturn FALSE;}//线性表取第i个值Status GetElem(const SqList* L, int i, ElemType e){ if (i<1 || i>L->length)return ERROR;else{ e = L->elem[i - 1];return OK;}}//线性表按值顺序查找Status LocateElem(const SqList* L, const ElemType e){ int i;for (i = 0; i <= L->length - 1; i++){ if (L->elem[i] == e)return i + 1;//查找成功返回元素位置}return 0;//查找失败返回0}//顺序表的插入Status InsertList_Sq(SqList* L, int n, const ElemType e){ int i;if (n >= 1 && n <= L->length + 1)//判断插入位置是否合法{ if (L->length == MAXSIZE)//判断存储空间是否已满return ERROR;for(i=L->length-1; i>=n-1; i--)//插入位置及之后元素后移{ L->elem[i+1] = L->elem[i];}L->elem[n - 1] = e;L->length += 1;return OK;}return ERROR;}//顺序表删除Status DeleteElem(SqList* L, int n){ int i;if (n >= 1 && n <= L->length){ L->elem[n - 1] = 0;//删除指定元素for (i = n - 1; i <= L->length - 1; i++)//剩余元素移位{ L->elem[i] = L->elem[i + 1];}L->length--;//顺序表长度-1return OK;}return ERROR;}//顺序表显示void ShowList_Sq(const SqList* L){ if (L->length == 0)puts("The SqList is empty!");else{ int i;for (i = 0; i < L->length; i++){ printf("%d ", L->elem[i]);}putchar('\n');printf("The length of SqList is %d\n", L->length);}}//合并两个顺序表,将L2合并到L1中Status MergeList_Sq(SqList* L1, const SqList* L2){ if (L1->length == 0 || L2->length == 0){ puts("Length must be non-zero!");return ERROR;}else if (L1->length + L2->length > MAXSIZE){ puts("Overflow");return OVERFLOW;}else { int i;for (i = 0; i <= L2->length - 1; i++){ L1->elem[i + L1->length] = L2->elem[i];}L1->length += L2->length;return OK;}}

测试代码：

int main(void){ SqList my_list;ElemType a, b, c, d, e, f;a = 1;b = 2;c = 3;d = 4;e = 5;f = 6;SqList my_list2;InitList_Sq(&my_list);InsertList_Sq(&my_list, 1, a);InsertList_Sq(&my_list, 2, b);InsertList_Sq(&my_list, 3, c);InsertList_Sq(&my_list, 1, d);InsertList_Sq(&my_list, 2, e);InsertList_Sq(&my_list, 3, f);//printf("%d\n", LocateElem(&my_list, a));//ShowList_Sq(&my_list);//DeleteElem(&my_list, 2);ShowList_Sq(&my_list);InitList_Sq(&my_list2);InsertList_Sq(&my_list2, 1, a);InsertList_Sq(&my_list2, 2, b);InsertList_Sq(&my_list2, 3, c);ShowList_Sq(&my_list2);MergeList_Sq(&my_list, &my_list2);ShowList_Sq(&my_list);return 0;}

2、顺序表的优缺点

优点：1、存储密度大；2、可以随机存取表中任一元素。

缺点：1、在插入、删除某一元素时，需要移动大量其他元素；2、浪费大量存储空间；3、属于静态存储形式，数据元素的个数不能够自由扩充。

3、线性表的链式表示和实现

​ 线性表的链式结构的特点是用一组任意的存储单元存储线性表的数据元素（这种存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 a i a_i ai​与其直接后继数据元素 a i + 1 a_{i+1} ai+1​之间的逻辑关系，对数据元素 a i a_i ai​来说，除了本身的存储信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素 a i a_i ai​的存储映像，称为结点（node）。它包括两个域：其中存储信息数据元素信息的域被称为数据域；存储直接后继存储位置的域被称为指针域。指针域中存储的信息称为指针或链。 n n n个结点 ( a i ( 1 < = i < = n ) ) (a_i(1<=i<=n)) (ai​(1<=i<=n))的存储映像链结成一个链表，即为线性表

( a 1 , a 2 , … , a n ) (a_1,a_2,\dots{,a_n}) (a1​,a2​,…,an​)

的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。整个链表的存取必须从头指针开始，头指针指示链表中第一个结点（即第一个数据元素的存储映像）。

​ 链式存储结构的特点：1、结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。2、访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等，这种存取元素的方式称为顺序存取。

链表（Link List）的分类：单链表、双链表、循环链表

单链表还分为是否带头结点两种情况：

如何判断是否是空表：

设置链表的头结点有什么好处：

头结点的数据域能够存放什么内容：

a、单链表的实现

单链表的每个结点都可以通过一个结构体来表示：

// 链表定义模板typedef struct Lnode { ElemType data;struct Lnode* next;//注意这里需要struct关键字}Lnode, *LinkList;

举个例子，定义一个学生链表：

单链表基本操作的实现：

单链表的初始化

判断单链表是否为空

单链表的销毁

清空单链表

求单链表的表长

取单链表中第i个元素内容

单链表按值查找

单链表插入，在第 i i i个结点的前面插入新结点

单链表删除，删除第 i i i个结点

单链表的建立–头插法

单链表的建立–尾插法

单链表实现完整算法：

//头文件导入#include <stdio.h>#include <stdlib.h>//函数结果状态代码#define OK 1#define ERROR 0//Status 是函数的类型，其值是函数结果状态代码typedef int Status;typedef int ElemType;//单链表typedef struct Signle_Link_List{ ElemType data;struct LNode* next;} LNode, *LinkList;//创建空链表Status InitLinkList(LinkList* L){ *L = (LinkList)malloc(sizeof(LNode));if (*L == NULL)return ERROR;(*L)->next = NULL;return OK;}//判断链表是否为空int IsEmptyLinkList(const LinkList* L){ if ((*L)->next == NULL)return 1;elsereturn 0;}//单链表的销毁Status DestoryLinkList(LinkList* L){ LNode* p;while (*L != NULL){ p = *L;*L = (*L)->next;free(p);}return OK;}//清空单链表Status ClearLinkList(LinkList* L){ LNode* p, * q;q = (*L)->next;while (q != NULL){ p = q;q = q->next;free(p);}(*L)->next = NULL;return OK;}//求单链表的表长int LenLinkList(const LinkList* L){ LNode* p;p = (*L)->next;int i = 0;while (p){ i++;p = p->next;}(*L)->data = i;//将长度存储到L头结点的数据域中return i;}//取出单链表中第i个元素Status LocateElem(const LinkList *L, int i, ElemType *e){ int j = 1;LNode* p;p = (*L)->next;while (p && j < i){ j++;p = p->next;}if (!p || j > i)//如果待查找的元素大于链表长度或者小于1，查找错误return ERROR;*e = p->data;return OK;}//单链表按值查找,返回LNodeLNode* LocateElem_V_LNode(const LinkList *L, ElemType value){ LNode* p;p = (*L)->next;while (p && p->data != value)//p不为空指针，并且没找到{ p = p->next;}return p;//找到返回结点的地址，没找到返回NULL}//单链表按值查找,返回元素位置int LocateElem_V_Index(const LinkList *L, ElemType value){ int j = 1;LNode* p;p = (*L)->next;while (p && p->data != value){ j++;p = p->next;}if (!p)return 0;//没找到,返回0elsereturn j;//找到,返回第几个结点}//单链表插入,在第i个结点之前插入一个结点Status InsertLinkList(LinkList *L, int i, ElemType value){ LNode* p;p = (*L)->next;int j = 1;while (p && j < i - 1)//找到第i-1个结点{ j++;p = p->next;}if (!p || j > i - 1)//i大于表长+1,或者小于1,插入位置非法return ERROR;LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));newlnode->data = value;newlnode->next = p->next;p->next = newlnode;return OK;}//单链表删除,删除第i个结点Status DeleteLinkList(LinkList *L, int i){ LNode* p, * q;int j = 1;p = (*L)->next;while (p && j < i - 1){ j++;p = p->next;}if (!p || j > i - 1)return ERROR;q = p->next;p->next = q->next;free(q);return OK;}//单链表建立-头插法void CreateLinkList_H(LinkList* L, int n){ *L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;//先建立一个头结点int i;for (i = n; i > 0; i--){ LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:_____\b");scanf("%d", &newlnode->data);newlnode->next = (*L)->next;(*L)->next = newlnode;}}//单链表建立-尾插法void CreateLinkList_R(LinkList *L, int n){ *L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;//先建立一个头结点LNode* p;p = *L;int i;for (i = n; i > 0; i--){ LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:___\b");scanf("%d", &newlnode->data);newlnode->next = NULL;p->next = newlnode;p = p->next;}}//显示单链表void ShowLinkList(const LinkList* L){ LNode* p;p = (*L)->next;if (!p){ puts("The LinkList is empty");return;}int i = 1;while (p){ printf("%d : %d\n", i, p->data);i++;p = p->next;}putchar('\n');}

测试函数：

//测试函数int main(void){ LinkList my_list;my_list = NULL;ElemType answer = 0;//InitLinkList(my_list);//CreateLinkList_H(&my_list, 3);//测试头插法建立链表CreateLinkList_R(&my_list, 3);//测试尾插法建立链表//ClearLinkList(&my_list);//测试清空链表ShowLinkList(&my_list);//DestoryLinkList(&my_list);//测试销毁链表printf("%s\n",IsEmptyLinkList(&my_list) >0?"LinkList is Empty":"LinkList isn't Empty");//测试判断链表函数printf("The length of LinkList is %d\n", LenLinkList(&my_list));//测试求长度函数LocateElem(&my_list, 3, &answer);printf("The %d elem is %d\n", 3, answer);//测试取元素函数LNode *answer1;answer1 = LocateElem_V_LNode(&my_list, 2);printf("The answer is %d\n", answer1->data);//测试取元素函数printf("The Index of 3 is %d\n", LocateElem_V_Index(&my_list, 3));//测试取元素函数InsertLinkList(&my_list, 2, 10);//测试增加结点函数ShowLinkList(&my_list);DeleteLinkList(&my_list, 3);//测试删除结点函数ShowLinkList(&my_list);return 0;}

b、单向循环链表的实现

判断循环链表结束的条件：

当循环链表需要经常使用头结点和尾结点的时候，循环链表通常使用尾指针表示法更简单：

循环链表的基本操作实现

循环链表的合并

c、双向链表的实现

双向链表的定义：

//双向链表的定义typedef struct DuLNode { ElemType data;struct DuLNode* prior, * next;} DuLNode, *DuLinkList;

双向链表的操作

双向链表的插入

双向链表的删除

d、双向循环链表的实现

4、链表的优缺点

（3）单链表、循环链表、双向链表的时间效率比较

（4）顺序表和链表的比较

（5）案例引入

1、线性表的应用

线性表的合并

有序表的合并

用顺序存储结构来实现

用链式存储结构来实现

2、一元多项式的运算

采用链式结构会更简单。

尾插法建立链表

多项式相加

3、图书管理系统

---

五、栈和队列

​ 栈和队列是两种重要的线性结构，从数据结构的角度来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可以称为限定数据类型。

（1）栈（LIFO）

​ **栈（stack）**是限定仅在表位进行插入或删除操作的线性表。对栈来说，表尾称为栈顶（Top），表头称为栈尾（Base）。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（last-in-first-out）的线性表（简称LIFO）。插入元素到栈顶称为入栈（压栈Push），从栈尾删除一个元素称为出栈（弹栈Pop）。

栈和线性表有什么不同：

（2）栈的表示和实现

1、栈的顺序表示和实现

栈的顺序表示又称为顺序栈，具体如下所示：

​ 栈存在两种溢出的情况，当栈已经存放满元素时，若还将元素进行压栈此时会发生上溢（overflow）；当栈已经为空时，若还进行出栈此时会发生下溢（underflow）。上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题的处理结束。

顺序栈的表示：

//栈的顺序表示typedef struct { SElemType* top;//栈顶指针SElemType* base;//栈底指针，用于初始化动态存储空间int stacksize;//栈的最大容量} SqStack; 顺序栈的初始化

判断顺序栈是否为空

清空栈

销毁栈

顺序栈的入栈

顺序栈的出栈

这里一定是先进行指针下移，因为top指针指向的是栈顶空位置，用于存放下一个元素地址的地方，先进行下移则top指向栈中的栈顶第一个元素。

顺序栈的完整实现：

// 顺序栈的实现//导入头文件#include <stdio.h>#include <stdlib.h>//函数结果状态代码#define OK 1#define ERROR 0#define OVERFLOW -1#define TRUE 1#define FALSE 0//宏定义#define MAXSIZE 100//Status 是函数的类型，其值是函数结果状态代码typedef int Status;typedef int SElemType;//顺序栈的定义typedef struct { SElemType* top;SElemType* base;int stacksize;} SqStack;//顺序栈的初始化Status InitSqStack(SqStack* S){ S->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));if (!S->base)//S->base为NULL，开辟空间失败exit(OVERFLOW);S->top = S->base;S->stacksize = MAXSIZE;return OK;}//判断顺序栈是否为空Status IsEmptySqStack(const SqStack* S){ if (S->base == S->top)return TRUE;elsereturn FALSE;}//判断顺序栈是否已满Status IsFullSqStack(const SqStack* S){ if (!S->base)return ERROR;if (S->top - S->base == S->stacksize)return TRUE;elsereturn FALSE;}//清空栈Status ClearSqStack(SqStack* S){ if(S->base)S->top = S->base;return OK;}//销毁栈Status DestroySqStack(SqStack* S){ if (!S->base)return ERROR;free(S->base);S->top = S->base = NULL;S->stacksize = 0;return OK;}//顺序栈的入栈Status Push(SqStack* S, SElemType* e){ if (!S->base || S->top - S->base == S->stacksize)//栈为NULL,或者上溢return ERROR;*(S->top++) = *e;return OK;}//顺序栈的出栈Status Pop(SqStack* S, SElemType* e){ if (!S->base || S->top == S->base)//栈为NULL,或者下溢return ERROR;*e = *--S->top;return OK;}//栈显示函数void ShowSqStack(const SqStack* S){ if (!S->base || S->top == S->base)printf("SqStack is Empty!\n");SElemType* p;p = S->top;while (p-- != S->base){ printf("%d ", *p);}putchar('\n');}

测试函数：

//测试函数int main(void){ SqStack my_stack;InitSqStack(&my_stack);//测试栈初始化函数printf("%d\n", IsEmptySqStack(&my_stack));//测试判断空函数printf("%d\n", IsFullSqStack(&my_stack));//测试判断满函数SElemType a = 1;SElemType b = 2;SElemType c = 3;SElemType d = 10;SElemType answer;Push(&my_stack, &a);//测试入栈函数Push(&my_stack, &b);Push(&my_stack, &c);Push(&my_stack, &d);ShowSqStack(&my_stack);//显示栈中元素Pop(&my_stack, &answer);//测试出栈函数printf("The answer is %d\n", answer);ShowSqStack(&my_stack);ClearSqStack(&my_stack);//测试清空栈函数ShowSqStack(&my_stack);//DestroySqStack(&my_stack);//测试销毁栈函数//ShowSqStack(&my_stack);return 0;}

2、栈的链式表示和实现

栈的链式表示又称为链栈，具体如下：

在这个表示方法中，**栈顶指针就用单链表的头结点指针来表示，栈底指针就用单链表的尾结点指针来表示。链栈需要一个指针就能进行操作，是因为栈只能在栈顶进行入栈和出栈，所以仅仅直到栈顶的指针就可以操作整个链栈。**链栈是没有头结点的单链表，但是链栈也可以添加头结点，具体操作方法，要看自己是如何进行定义的。链栈的使用和创建，类似于单链表建立的头插法，都是从头部开始进行插入。

//链栈typedef struct StackNode { SElemType data;struct StackNode* next;} StackNode, *LinkStack; 链栈的初始化

判断链栈是否为空

链栈的入栈

链栈的出栈

取栈顶的元素

链栈实现完整代码

//链栈的实现 --该实现是保留了头结点，栈为空的条件为头结点的next为NULL//导入头文件#include <stdio.h>#include <stdlib.h>//函数状态宏定义#define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define OVERFLOW -1//类型定义typedef int Status;typedef int SElemType;//链栈定义typedef struct StackNode { SElemType data;struct StackNode* next;} StackNode, *LinkStack;//链栈的初始化Status InitLinkStack(LinkStack* S){ *S = (LinkStack)malloc(sizeof(StackNode));if (!S)//开辟空间失败return ERROR;(*S)->next = NULL;return OK;}//判断链栈是否为空Status IsEmptyLinkStack(LinkStack* S){ if ((*S)->next == NULL)return TRUE;elsereturn FALSE;}//链栈清空Status ClearLinkStack(LinkStack* S){ if (!(*S)->next)//当链栈已经为空时报错return ERROR;StackNode* p, *q;p = (*S);while (p->next){ q = p;p = p->next;free(q);}(*S)->next = NULL;return OK;}//链表销毁Status DestroyLinkStack(LinkStack* S){ if (!(*S))//当链栈不存在时报错return ERROR;StackNode* p, *q;p = *S;while (p->next){ q = p;p = p->next;free(q);}free(*S);*S = NULL;return OK;}//链栈入栈--链栈无上溢，所以不需要判断Status Push(LinkStack* S, SElemType* e){ StackNode* new;new = (StackNode*)malloc(sizeof(StackNode));new->data = *e;new->next = (*S);(*S) = new;return OK;}//链栈出栈--链栈有下溢，需要判断下溢Status Pop(LinkStack* S, SElemType* e){ if (!(*S)->next)//判断链栈下溢return ERROR;StackNode* p;p = *S;*e = p->data;*S = p->next;free(p);//释放栈顶空间}//获取链栈顶部元素，并不出栈SElemType GetTop(LinkStack* S){ if ((*S)->next)return (*S)->data;}//显示链栈void ShowLinkStack(const LinkStack* S){ if (!(*S)->next){ printf("The LinkStack is Empty\n");return;}else if (!(*S)){ printf("The LinkStack dosen't exsist\n");}StackNode* p;p = *S;while (p->next){ printf("%d ", p->data);p = p->next;}putchar('\n');}

测试函数：

//测试函数int main(void){ LinkStack my_stack;my_stack = NULL;SElemType a = 1;SElemType b = 2;SElemType c = 3;SElemType d = 10;SElemType answer;printf("%d\n", InitLinkStack(&my_stack));//测试初始化函数ShowLinkStack(&my_stack);//显示链栈printf("%d\n", IsEmptyLinkStack(&my_stack));//测试判断为空函数Push(&my_stack, &a);//测试入栈函数Push(&my_stack, &b);Push(&my_stack, &c);Push(&my_stack, &d);ShowLinkStack(&my_stack);Pop(&my_stack, &answer);//测试出栈函数printf("%d\n", answer);ShowLinkStack(&my_stack);printf("%d\n", GetTop(&my_stack));//测试获取首元素函数ClearLinkStack(&my_stack);//测试清空函数ShowLinkStack(&my_stack);//DestroyLinkStack(&my_stack);//测试销毁函数//ShowLinkStack(&my_stack);return 0;}

（3）栈与递归

递归的定义：

递归的问题往往采用分治法来解决，分治法是对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。分治法必备的三个条件：1、能够将一个问题转变成另一个新问题，而新问题的解法与原问题的解法相同或类似，不同仅是处理的对象，且这些处理这些问题是有变化规律的。2、可以通过上述转化来进行问题的简化。3、必须有一个明确的递归出口，或称为递归边界。

递归的调用过程，举个例子：

（4）队列（FIFO）

​ **队列（queue）**是一种先进后出（first-in-first-out，简称为FIFO）的线性表，它只允许在表的一端进行插入，另一端进行删除元素。在队列中，允许插入的一端叫做队尾（Rear），允许删除的一端叫做队头（Front）。插入操作称为入队，删除操作称为出队。

（5）队列的表示和实现

1、队列的顺序表示和实现

队列的顺序表示又称为顺序队，具体表示如下：

//顺序队的实现#define MAXISIZE 100typedef struct { QElemType* base;//数据指针，初始化动态存储空间int front;//头元素的索引，不是指针int rear;//尾元素的索引，不是指针} SqQueue;

顺序队入队时的假上溢问题：

顺序队存在假上溢的问题，即当队尾指针指向了最大元素个数MAXQSIZE，但是队头指针却不为0，这种情况称为假上溢，为了解决这个问题有以下两种做法：1、每次都将队列中剩余的元素向队头方向移动，这种方式时间效率低。2、把队列视为循环队列。

如何判断队空队满：

采用少用一个元素空间的方法比较简单。

循环队列的初始化

求队列的长度

循环队列入队

循环队列出队

取队头元素

顺序队列的完整实现：

//顺序队列的实现//头文件包含#include <stdio.h>#include <stdlib.h>//函数状态宏定义#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1//类型定义typedef int Status;typedef int QElemType;//顺序队定义#define MAXQSIZE 100typedef struct SqQueue { QElemType* base;//动态分配数据域，指针int front;//队头索引int rear;//队尾索引} SqQueue;//初始化Status InitSqQueue(SqQueue* Q){ Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));if (!Q->base)return ERROR;Q->front = Q->rear = 0;return OK;}//求循环队列的长度int GetLength(SqQueue* Q){ return ((Q->rear - Q->front + MAXQSIZE) % MAXQSIZE);}//入队Status EnQueue(SqQueue* Q, QElemType* e){ if ((Q->rear + 1) % MAXQSIZE == Q->front)//出现上溢return ERROR;Q->base[Q->rear] = *e;Q->rear = (Q->rear + 1) % MAXQSIZE;return OK;}//出队Status DeQueue(SqQueue* Q, QElemType* e){ if (Q->front == Q->rear)//出现下溢return ERROR;*e = Q->base[Q->front];Q->front = (Q->front + 1) % MAXQSIZE;return OK;}//取队头元素QElemType GetHead(SqQueue* Q){ if (Q->rear != Q->front)return Q->base[Q->front];}//销毁队列Status DestoryQueue(SqQueue* Q){ if (!(Q->base))return ERROR;free(Q->base);Q->front = Q->rear = 0;return OK;}//显示队列void ShowSqQueue(SqQueue Q){ if (Q.front == Q.rear){ printf("The SqQueue is Empty\n");return;}while (Q.rear != Q.front){ printf("%d ", Q.base[Q.front]);Q.front = (Q.front + 1) % MAXQSIZE;}putchar('\n');}

测试函数：

//测试函数int main(void){ SqQueue my_queue;QElemType a = 1;QElemType b = 2;QElemType c = 3;QElemType d = 10;QElemType answer;InitSqQueue(&my_queue);//测试初始化ShowSqQueue(my_queue);EnQueue(&my_queue, &a);//测试入队函数EnQueue(&my_queue, &b);EnQueue(&my_queue, &c);EnQueue(&my_queue, &d);ShowSqQueue(my_queue);DeQueue(&my_queue, &answer);//测试出队函数printf("The answer is %d\n", answer);DestoryQueue(&my_queue);//测试销毁函数ShowSqQueue(my_queue);return 0;}

2、队列的链式表示和实现

队列的链式表示又称为链队，具体表示如下：

//链队的实现typedef struct Qnode { QElemType data;struct Qndoe* next;} QNode, *QueuePtr;typedef struct { QueuePtr front;//队头指针QueuePtr rear;//队尾指针} LinkQueue;

在这种表示方法中，队头是单链表的头结点的指针，队尾是单链表尾结点的指针。与链栈不同，链队需要两个指针进行操作，是因为队列是在队头进行出队，队尾进行入队，需要两个指针分别来指示队列的队头和队尾。

链队的初始化

链队列的销毁

链队列的入队

链队的出队

链队列求队头元素

链队的完整实现：

//链队的实现//头文件包含#include <stdio.h>#include <stdlib.h>//函数状态宏定义#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1//类型定义typedef int Status;typedef int QElemType;//链队结点的定义typedef struct Qnode { QElemType data;struct Qnode* next;} QNode, *QueuePtr;//链队的定义typedef struct { QueuePtr front;//队头指针QueuePtr rear;} LinkQueue;//链队的初始化Status InitLinkQueue(LinkQueue* Q){ Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));if (!Q->rear)return ERROR;Q->rear->next = NULL;return OK;}//链队的销毁Status DestoryLinkQueue(LinkQueue* Q){ QNode* p;while (Q->front){ p = Q->front->next;free(Q->front);Q->front = p;}return OK;}//链队的入队Status EnLinkQueue(LinkQueue* Q, QElemType* e){ QNode* new;new = (QNode*)malloc(sizeof(QNode));new->data = *e;new->next = Q->rear->next;Q->rear->next = new;Q->rear = new;//更新队列尾指针return OK;}//链队的出队Status DeLinkQueue(LinkQueue* Q, QElemType* e){ if (Q->front == Q->rear)return ERROR;QNode* p;p = Q->front->next;*e = p->data;Q->front->next = p->next;if (Q->rear == p)Q->front = Q->rear;free(p);return OK;}//获取链队头元素QElemType GetHead(LinkQueue* Q){ if(Q->front != Q->rear)return Q->front->next->data;}//显示链队void ShowLinkQueue(LinkQueue Q){ if (Q.front == Q.rear){ printf("The LinkQueue is Empty\n");return;}Q.front = Q.front->next;//跳过头结点while (Q.front){ printf("%d ", Q.front->data);Q.front = Q.front->next;}putchar('\n');return OK;}

测试函数：

//测试函数int main(void){ LinkQueue my_queue;QElemType a = 1;QElemType b = 10;QElemType c = 100;QElemType d = 1000;QElemType answer;InitLinkQueue(&my_queue);//测试初始化链队ShowLinkQueue(my_queue);EnLinkQueue(&my_queue, &a);//测试链队入队EnLinkQueue(&my_queue, &b);EnLinkQueue(&my_queue, &c);EnLinkQueue(&my_queue, &d);ShowLinkQueue(my_queue);DeLinkQueue(&my_queue, &answer);//测试链队出队printf("The answer is %d\n", answer);ShowLinkQueue(my_queue);printf("The head is %d\n", GetHead(&my_queue));//测试获取头元素DestoryLinkQueue(&my_queue);//测试销毁链队printf("%d\n", &my_queue==NULL);return 0;}

---

六、串、数组和广义表

（1）串

​ 串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为

s = ′ a 1 a 2 … a n ′ ( n ≥ 0 ) s='a_1a_2\dots{a_n}'(n\ge0) s=′a1​a2​…an​′(n≥0)

其中， s s s是串的名字，用单引号''括起来的字符序列是串的值； a i ( 1 ≤ i ≤ n ) a_i(1\le{i}\le{n}) ai​(1≤i≤n)可以是字母、数字或其他字符；串中字符的数目 n n n称为串的长度。零个字符的串称为空串（null string），它的长度为0。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串的位置是子串的第一个字符在主串中的位置。

​ 串也具有顺序存储结构和链式存储结构，分别称为顺序串和链串。

（2）串的表示和实现

1、串的顺序表示

​ 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义大小，为每个定义的串变量分配一个固定长度的存储区。具体描述如下：

//串的顺序存储结构#define MAXLEN 255typedef struct { char ch[MAXLEN + 1]; //存储串的一维字符数组int length;//串的当前长度} SString;

2、串的链式表示

​ 和线性表的链式存储结构类似，串也可以采用链式表示方法存储串值。由于串结构的特殊性——结构中的每个元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符，这种结构一般称为块链。由于串长不一定是结点大小的整数倍，所以链表的最后一个结点不一定全被串值占满，此时通常补上“#”或其他非串值字符。

//串的链式存储结构（块链）#define CHUNKSIZE 80//定义块的大小typedef struct Chunk { char ch[CHUNKSIZE];struct Chunk* next;} CHUNK;typedef struct { CHUNK* head, * tail;//串的头指针和尾指针int curlen;//串的当前长度} LString;//字符串的块链结构

3、串的模式匹配算法

​ 算法的目的是：确定主串中所含子串（模式串）第一次出现的位置（定位）。算法的种类：BE算法（Brute Force，暴力破解法）；KMP算法（特点：速度快）。

BE算法：采用顺序串进行实现

算法的步骤：

新增了待查找的位置，从pos位置处开始进行查找。

BF算法的时间复杂度：

​ 最好的情况是第一次匹配就成功，设子串的长度为m，主串的长度为n，那么最优的时间复杂度为 O ( m ) O(m) O(m)；最坏的情况为前 n − m n-m n−m次匹配均失败，最后一次匹配成功，时间复杂度为 O ( ( n − m + 1 ) × m ) O((n-m+1)\times{m}) O((n−m+1)×m)，若 m < < n m<<n m<<n，则时间复杂度为 O ( n ∗ m ) O(n*m) O(n∗m)；平均时间复杂度为 O ( n 2 ∗ m ) O(\frac{n}{2}*m) O(2n​∗m)，数量级仍为 O ( n ∗ m ) O(n*m) O(n∗m)。

KMP算法：采用顺序串进行实现

next函数使用示例：

对next函数的修正方法：（掌握到会计算即可）

（3）数组

​ 之前讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。而数组和广义表可以看成线性表的一种扩展：表中的数据元素本身也是一个数据结构。

​ 数组：是按照一定格式排列起来的具有相同类型的数据元素的集合。一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。一维数组的逻辑结构：线性结构，定长的线性表。二维数组：若有一维数组中的数据元素又是一维数组结构，则称为二维数组。

数组的定义方法：

由此可以看出，线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。

（4）数组的表示

​ 数组的特点是：结构固定，且一般不做插入和删除操作，所以一般都是采用顺序结构来表示数组。在C语言中一般采用内置的数组数据类型的定义。

数组的存储，以二维数组为例：

稀疏矩阵的十字链表存储方式：

分别设置行的头指针，和列的头指针。

（5）广义表

​ 广义表（又称为列表list）是 n ≥ 0 n\ge{0} n≥0个元素 ( a 0 , a 1 , … a n − 1 ) (a_0,a_1,\dots{a_{n-1}}) (a0​,a1​,…an−1​)的有限序列，其中每一个 a i a_i ai​或者是原子，或者是一个广义表。广义表通常记作： L S = ( a 1 , a 2 , … , a n ) LS=(a_1,a_2,\dots{,a_n}) LS=(a1​,a2​,…,an​)，其中 L S LS LS为表名， n n n为表的长度，每一个 a i a_i ai​为表的元素，习惯上一般使用大写字母表示广义表，小写字母表示原子。表头：若 L S LS LS非空 ( n ≥ 1 ) (n\ge{1}) (n≥1)，则其第一个元素 a 1 a_1 a1​就是表头，记作 h e a d ( L S ) = a 1 head(LS)=a_1 head(LS)=a1​。表尾：除表头之外的其他元素组成表称为表尾。记作 t a i l ( L S ) = ( a 2 , … , a n ) tail(LS)=(a_2,\dots{,a_n}) tail(LS)=(a2​,…,an​)。一定注意表尾不是最后一个元素，而是一个子表。

广义表的示例：

广义表的长度定义为最外层包含的元素个数；广义表的深度定义为该广义表展开后所含括号的重数，特殊的有，原子的深度为0，空表的深度为1。

广义表和线性表的区别：

广义表的基本运算操作：

广义表的存储：广义表通常采用链表来进行存储（暂不介绍）

---

七、树和二叉树

（1）树

​ 树（Tree）是 n ( n ≥ 0 ) n(n\ge{0}) n(n≥0)个结点的有限集。若 n = 0 n=0 n=0，则称为空树，若 n > 0 n>0 n>0，且满足如下两个条件：1、有且仅有一个特定的称为根（Root）的结点；2、其余结点可分为 m ( m ≥ 0 ) m(m\ge{0}) m(m≥0)个互不相交的有限集 T 1 , T 2 , T 3 , … , T m T1,T2,T3,\dots,Tm T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。树是典型的非线性结构。

​ 树的基本术语：1、根节点：非空树中无前驱结点的结点；2、结点的度：该结点拥有子树（分支）的个数；3、树的度：树内所有结点的度的最大值；4、叶子（终端）结点：度为零的结点称为叶子结点；5、分支（非终端）结点：度不为零的结点；6、兄弟结点：有共同双亲的结点称为兄弟结点；7、树的深度（高度）：树中结点的最大层次；8、有序树：树中结点的各子树从左到右有次序；9、无序树：树中结点的各子树无次序；10、森林：是 m ( m ≥ 0 ) m(m\ge{0}) m(m≥0)棵互不相交的树的集合。

线性结构和树型结构的对比：

（2）二叉树

​ 二叉树（Binary Tree），是 n ( n ≥ 0 ) n(n\ge{0}) n(n≥0)个结点的有限集，或者它是空集 ( n = 0 ) (n=0) (n=0)，或者有一个根节点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。二叉树的特点：1、每个结点最多有两个子树；2、子树有左右之分，其次序不能颠倒；3、二叉树可以是空集合，根可以有空的左子树或空的右子树。

​ 二叉树和树的区别：二叉树的结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明该子树是左子树还是右子树。当树只有一个结点时，就无需区分它是左还是右的次序，因此二者是不同的。这就是二叉树和树的主要区别。

​ 二叉树的性质：1、在二叉树的第 i i i层上至多有 2 i − 1 2^{i-1} 2i−1个结点 ( i ≥ 1 ) (i\ge{1}) (i≥1)，那么有 n n n个结点的二叉树，深度为 ⌊ l o g 2 n ⌋ + 1 \lfloor{log_2n}\rfloor+1 ⌊log2​n⌋+1；2、第 i i i层上最少有一个结点；3、深度为 k k k的二叉树至多有 2 k − 1 2^k-1 2k−1个结点 ( k ≥ 1 ) (k\ge{1}) (k≥1)；4、对于任何一棵二叉树 T T T，如果其叶子树为 n 0 n_0 n0​，所有度为2的节点数为 n 2 n_2 n2​，则 n 2 = n 2 + 1 n_2=n_2+1 n2​=n2​+1。

性质4分析： n i n_i ni​是度为 i i i的结点， n n n是所有结点的总数。

**满二叉树**，一棵深度为$k$且有$2^k-1$个结点的二叉树称为满二叉树。特点：1、每一层上的结点数都是最大结点数（即每层都是满的）；2、叶子结点全部在最底层。对满二叉树位置进行编号，编号规则：从根结点开始，**自上而下，自左而右**；每一结点位置都有元素。

​ 完全二叉树，深度为 k k k的具有 n n n个结点的二叉树，当且仅当其每一个结点都与深度为 k k k的满二叉树中编号为 1   n 1~n 1 n的结点一一对应时，称之为完全二叉树。

完全二叉树的简单判别方式：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即获得了一棵完全二叉树。

​ 完全二叉树的特点：1、叶子只可能分布在层次最大的两层上；2、对任一结点，如果其右子树的最大层次为 i i i，则其左子树的最大层次必为 i i i或 i + 1 i+1 i+1。

​ 完全二叉树的性质：1、具有 n n n个结点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ + 1 \lfloor{log_2{n}}\rfloor{+1} ⌊log2​n⌋+1，其中 ⌊ x ⌋ \lfloor{x}\rfloor ⌊x⌋称作 x x x的底（向下取整），表示不大于 x x x的最大整数。2、如果对一棵有 n n n个结点的完全二叉树（深度为 ⌊ l o g 2 n ⌋ + 1 \lfloor{log_2{n}}\rfloor{+1} ⌊log2​n⌋+1的结点按层序编号（从第 1 1 1层到第 ⌊ l o g 2 n ⌋ + 1 \lfloor{log_2{n}}\rfloor{+1} ⌊log2​n⌋+1层，每层从左往右），则对任一结点 i ( 1 ≤ i ≤ n ) i(1\le{i}\le{n}) i(1≤i≤n)有：a、如果 i = 1 i=1 i=1，则结点 i i i是二叉树的根，无双亲；如果 i > 1 i>1 i>1，则其双亲结点 ⌊ i / 2 ⌋ \lfloor{i/2}\rfloor ⌊i/2⌋。b、如果 2 i > n 2i>n 2i>n，则结点 i i i为叶子结点，无左孩子；否则，其左孩子结点是 2 i 2i 2i。c、如果 2 i + 1 > n 2i+1>n 2i+1>n，则结点 i i i无右孩子；否则，其右孩子是结点 2 i + 1 2i+1 2i+1。

该性质2表明了完全二叉树中双亲结点编号和孩子结点编号之间的关系。

（3）二叉树的表示

​ 二叉树的存储结构，包括顺序存储结构和链式存储结构，链式存储结构又包括二叉链表和三叉链表。

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

​ 二叉树的顺序存储结构：实现，按照满二叉树的结点层次进行编号，依次存放二叉树中的数据元素。

不完全二叉树如何进行存储：

//二叉树的顺序存储#define MAXTSIZE 100typedef TElemType SqBiTree[MAXTSIZE];SqBiTree bt;//创建一个二叉树

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

​ 二叉树的链式存储结构中的二叉链表，需要包含指向左右子树的指针，还需包含本身结点的数据域。

//二叉树的链式存储结构typedef struct Binode { TElemType data;struct Binode* lchild, * rchild;//左右孩子指针}BiNode, *BiTree;

二叉树链式存储（二叉链表）示例：

结论：在 n n n个结点的二叉链表中，一定有 n + 1 n+1 n+1个空指针域。分析： n n n个结点的二叉链表，一定有 2 n 2n 2n个链域，每个结点都会有一个双亲（除根节点），所以会存在 n − 1 n-1 n−1个结点的链域存放指针，那么空指针的个数为 2 n − ( n − 1 ) = n + 1 2n-(n-1)=n+1 2n−(n−1)=n+1。

​ 三叉链表，除了需要包含指向左右子树的指针，还需要包含指向双亲结点的指针，同时还需要含本身结点的数据域。

//三叉链表typedef struct Trinode { TElemType data;struct Trinode* lchild, * rchild;//左右孩子指针struct Trinode* parent; //双亲指针} TriNode, *TriTree;

（4）二叉树的遍历

​ 二叉树遍历的定义：顺着某一条搜索路径巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。遍历的目的是得到树种所有结点的一个线性排列。 如果规定左右子树的访问顺序为先左后右，那么有三种遍历方式：都是以递归的方式进行

先序遍历（根左右）示例：

中序遍历（左根右）示例：

后序遍历（左右根）示例：

已知先序和中序序列求二叉树的方法：

已知中序和后序序列求二叉树的方法：

如果只知道先序和后序序列是不能确定二叉树的形状的，因为只知道先序和后序不能唯一确定根结点的位置。

1、先序遍历的实现

均在二叉链表的基础上进行实现：

先序遍历递归调用的执行过程：

2、中序遍历的实现

3、后序遍历的实现

​ 三种遍历算法的对比，如果去掉输出语句，从递归的角度来看，三种算法是完全相同的，或者说这三种算法的访问路径是相同的，只是算法访问结点的时机不同。

遍历算法分析，时间复杂度为： O ( n ) O(n) O(n)，因为每个结点都只访问一次；空间复杂度： O ( n ) O(n) O(n)，最坏情况下栈占用最大的辅助空间。

4、中序遍历的非递归算法

​ 二叉树中序遍历的非递归算法的关键：在中序遍历过某个结点的整个左子树后，如何找到该结点的根以及右子树。基本思想如下：1、建立一个栈；2、根结点进栈，遍历左子树；3、根结点出栈，输出根结点，遍历右子树。（很巧妙）

5、二叉树的层次遍历

​ 二叉树的层次遍历：对于一棵二叉树，从根结点开始，按从上到下，从左到右的顺序逐层访问每一个结点，每个结点仅访问一次。

​ 算法设计思路：使用一个队列。1、将根结点入队；2、队列不为空时循环，从队列中出队一个结点*p，访问它；若它有左孩子结点，将左孩子结点入队；若它有右孩子结点，将右孩子结点入队。这里实现时，采用顺序循环队列。

（5）二叉树遍历算法的应用

1、二叉树的建立

应用先序遍历算法

2、复制二叉树

应用先序遍历算法

3、计算二叉树的深度

应用先序遍历算法

4、计算二叉树结点的总个数

应用先序遍历算法

( ( 0 + 0 + 1 ) + ( ( 0 + 0 + 1 ) + 0 + 1 ) + 1 ) + ( ( ( 0 + 0 + 1 ) + 1 ) + 0 + 1 ) + 1 ((0+0+1)+((0+0+1)+0+1)+1)+(((0+0+1)+1)+0+1)+1 ((0+0+1)+((0+0+1)+0+1)+1)+(((0+0+1)+1)+0+1)+1

5、计算二叉树叶子结点的总个数

应用先序遍历算法

（6）线索二叉树

​ 二叉链表存储的特点：

​ 线索二叉树（Threaded Binary Tree），线索二叉树的改进：利用二叉链表中的空指针域。如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继。（注：这里说的前驱和后继指的是按照先序、中序或者后序遍历得到的结点顺序。）这种改变指向的指针称为“线索”。对二叉树按某种遍历次序使其变为线索二叉树的过程称为线索化。

线索二叉树示例：

线索二叉树的表示：

//线索二叉树typedef struct BiThrnode { int data;int ltag, rtag;struct BiThrnode* lchild, * rchild;} BiThrNode, *BiThrTree;

线索二叉树表示示例：

为了统一，给线索二叉树新增了头结点，如示例：

（7）树的存储结构

1、双亲表示法

​ 树的双亲表示法：定义结构数组存放树的结点每个结点含有两个域，数据域：存放结点本身信息；双亲域：指示本届点的双亲结点在数组中的位置。

//树的双亲表示法typedef struct PTnode { TElemType data;int parent;//双亲位置域} PTNode;#define MAX_TREE_SIZE 100typedef struct { PTNode nodes[MAX_TREE_SIZE];int r, n;//指向根结点的位置和结点的个数的索引} PTree;

2、孩子链表

​ 树的孩子链表，是把每个结点的孩子结点排列起来，看成一个线性表，用单链表存储，则 n n n个结点有 n n n个孩子链表（叶子结点的孩子链表为空）。而 n n n个头指针又组成了一个线性表，用顺序表（含 n n n个元素的结构数组）存储。

将孩子链表和双亲表示法结合起来，获得了带双亲的孩子链表。

//孩子链表typedef struct CTnode { //孩子结点 child + nextint child;struct CTnode* next;} *ChildPtr;typedef struct { //双亲结点 data + firstchildTElemType data;ChildPtr firstchild;//孩子链表头指针} CTBox;#define MAX_TREE_SIZE 100typedef struct { CTBox nodes[MAX_TREE_SIZE];int n, r;//指向结点数和根结点位置的索引} CTree;

3、孩子兄弟表示法（二叉树表示法）

​ 二叉树表示法，实现：用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

//孩子兄弟表示法（二叉树表示法）typedef struct CSnode { ElemType data;struct CSnode* firstchild, *nextsiblingl;}CSNode, *CSTree;

孩子兄弟表示法示例：

4、树和二叉树的转换

​ 由于树和二叉树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可以导出数和二叉树之间的一个对应关系。

举个例子：

​ 将树转化为二叉树：1、加线，在兄弟结点之间加一条线；2、抹线，对于每个结点，除了其左孩子外，去除与其他孩子之间的关系；3、旋转，以树的根结点为轴心，将整个树顺时针旋转45°。示例：

​ 将二叉树转化为树：1、加线，若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子 … \dots …沿分支找到所有的右孩子，都与p的双亲用线连起来；2、抹线，抹掉原二叉树中双亲与右孩子之间的连线；3、调整，将结点按层次排列，形成树结构。

5、森林和二叉树的转换

​ 森林转换成二叉树：1、将各棵树分别转换成二叉树；2、将每棵树的根结点用线相连；3、以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树结构。示例：

​ 二叉树转换成森林：1、抹线，将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树；2、还原， 将孤立的二叉树还原成树。示例：

（8）树与森林的遍历

1、树的遍历

​ 树的遍历主要包括三种方式。1、先根次序遍历：若树不为空，则先访问根结点，然后依次先根遍历各子树；2、后根次序遍历：若树不为空，则先依次后根遍历各子树，然后访问根结点；3、按层次遍历：若树不为空，则自上而下自左而右访问树中每个结点。

2、森林的遍历

​ 将森林看作由三部分构成：1、森林中第一棵树的根结点；2、森林中第一棵树的子树森林；3、森林中其它树构成的森林。森林的遍历方式有：1、先序遍历：访问森林中第一棵树的根结点，先序遍历森林中第一棵树的子树森林，先序遍历森林中其余树构成的森林。2、中序遍历：中序遍历森林中第一棵子树的子树森林，访问森森林中第一棵树的根结点，中序遍历森林中其余树构成的森林。

（9）哈夫曼树

​ 哈夫曼树（最优二叉树）的基本概念，1、路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径；2、结点的路径长度：两结点间路径上的分支数；3、树的路径长度：从树根结点到每个结点的路径长度之和，记作 T L TL TL；4、权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权；5、结点的带权路径长度（Weighted Path Length，WPL）：从根结点到该结点之间的路径长度 × \times ×该结点的权；6、树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作

W P L = ∑ k = 1 n w k l k WPL=\sum_{k=1}^{n}{w_kl_k} WPL=k=1∑n​wk​lk​

7、哈夫曼树的定义：最优树，带权路径长度（WPL）最短的树；8、哈夫曼树的定义：最优二叉树，带权路径长度（WPL）最短的二叉树。

哈夫曼树的构造方法：

1、根据 n n n个给定的权值 { W 1 , W 2 , … W n } \{ {W_1,W_2,\dots{W_n}}\} { W1​,W2​,…Wn​} 构成 n n n棵二叉树的森林 F = { T 1 , T 2 , … , T n } F=\{ {T_1,T_2,\dots,{T_n}}\} F={ T1​,T2​,…,Tn​}，其中 T i T_i Ti​只有一个带权为 W i W_i Wi​的根结点。（构造森林全是根）

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

3、在 F F F中删除这两棵树，同时将得到的二叉树加入森林中。（选用两小造新树）

4、重复2和3，直到森林中只有一棵树为止，这棵树即待构造的哈夫曼树。（删除两小添新人）

哈夫曼树构造示例：

哈夫曼树小结：

（10）哈夫曼树的表示

​ 哈夫曼树实际上就是一种特殊的二叉树，可以采用顺序存储结构，也可以采用链式存储结构。

1、哈夫曼树的顺序存储结构

//哈夫曼树Huffman Treetypedef struct { int weight;int parent, lch, rch;} HTNode, *HuffmanTree;

哈夫曼构造算法的实现：

1、初始化 H T [ 1 … 2 n − 1 ] HT[1\dots{2n-1}] HT[1…2n−1]，lch=rch=parent=0。

2、输入初始 n n n个叶子结点，置 H T [ 1 … n ] HT[1\dots{n}] HT[1…n]的weight值。

3、进行以下 n − 1 n-1 n−1次合并，依次产生 n − 1 n-1 n−1个结点 H T [ i ] , i = n + 1 … 2 n − 1 HT[i],i=n+1\dots{2n-1} HT[i],i=n+1…2n−1：

a）在 H T [ 1 … i − 1 ] HT[1\dots{i-1}] HT[1…i−1]中选择两个未被选过（从parent==0的结点中选择）的weight最小的两个结点 H T [ s 1 ] HT[s1] HT[s1]和 H T [ s 2 ] HT[s2] HT[s2]， s 1 , s 2 s1,s2 s1,s2为两个最小结点的下标。

b）修改 H T [ s 1 ] HT[s1] HT[s1]和 H T [ s 2 ] HT[s2] HT[s2]的parent值， H T [ s 1 ] . p a r e n t = i HT[s1].parent=i HT[s1].parent=i； H T [ s 2 ] . p a r e n t = i HT[s2].parent=i HT[s2].parent=i；

c）修改新产生的 H T [ i ] HT[i] HT[i]：

H T [ i ] . w e i g h t = H T [ s 1 ] . w e i g h t + H T [ s 2 ] . w e i g h t HT[i].weight=HT[s1].weight+HT[s2].weight HT[i].weight=HT[s1].weight+HT[s2].weight； H T [ i ] . l c h = s 1 ; H T [ i ] . r c h = s 2 HT[i].lch=s1; HT[i].rch=s2 HT[i].lch=s1;HT[i].rch=s2；

（11）哈夫曼编码

​ 哈夫曼编码：1、统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。2、利用哈夫曼树的特点，权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的结点路径越短。3、在哈夫曼树的每个分支上标0或1，结点的左分支标0，右分支标1，把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。示例：

哈夫曼编码不仅能够保证是前缀码，并且能保证字符编码总长最短。

哈夫曼编码的实现：

文件的编码和解码：

---

八、图

（1）图的定义

​ 图是一种较为复杂的数据结构，在图中两个结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。在图中的数据元素通常称为顶点（Vertex）， V V V是顶点的有穷非空集合， E E E是边有穷集合； V R VR VR是两个顶点之间的关系的集合。若 ⟨ v , w ⟩ ∈ V R \langle{v,w}\rangle{\in}VR ⟨v,w⟩∈VR ，则 ⟨ v , w ⟩ \langle{v,w}\rangle ⟨v,w⟩表示从 v v v到 w w w的一条弧（Arc），且称 v v v为弧尾（Tail），称 w w w尾弧头（Head），此时的图称为有向图（Digraph）。若 ⟨ v , w ⟩ ∈ V R \langle{v,w}\rangle\in{VR} ⟨v,w⟩∈VR，则必有 ⟨ w , v ⟩ ∈ V R \langle{w,v}\rangle\in{VR} ⟨w,v⟩∈VR，即 V R VR VR是对称的，则以无序对 ( v , w ) (v,w) (v,w)代替这两个有序对，表示 v v v和 w w w之间的一条边（Edge），此时的图称为无向图（Undigraph）。当任意两个顶点之间都具有边的时候，此时的图称为完全图，完全图又分为有向完全图和无向完全图。

有很少的边或者弧 ( e < n l o g n ) (e<nlogn) (e<nlogn)的图称为稀疏图（Sparse graph），反之称为稠密图（Dense graph）。有些图的边或者弧具有与之相关的数，这种数称为权（Weight），这种带权的图称为网（Network)。

（2）图的表示

​ 图没有顺序结构，但是可以借助二维数组来描述元素之间的关系。数组表示法可以采用邻接矩阵（数组表示法）来表示。图具有链式结构，可以采用邻接表（链式表示法）来表示。

1、数组（邻接矩阵）表示法

邻接矩阵表示示例：

邻接矩阵表示图的类型定义：

//邻接矩阵表示图#define MaxInt 32767//表示极大值，即无穷大#define MVNum 100//最大顶点数typedef char VerTexType;//设顶点数的数据类型为字符型typedef int ArcType;//假设边的权值类型为整型typedef struct { VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum;//图的当前点数和边数} AMGraph;//Adjecency Matrix Graph

1、采用邻接矩阵创建无向网

2、采用邻接矩阵创建无向图、有向图（由算法1改进而来）

2、链表（邻接表）表示法

无向图的邻接表：

有向图的邻接表：

邻接表表示法的实现：

//邻接表表示法的实现#define MVNum 100//最大顶点数typedef struct Arcnode { //边结点int adjvex;//该边所指向的顶点的位置struct Arcnode* nextarc;//指向下一条边的指针OtherInfo info;//和边相关的信息}ArcNode;typedef struct Vnode { VerTexType data;//顶点信息ArcNode* firstarc;//指向第一条衣服该顶点的指针} VNode, AdjList[MVNum];//AdjList表示邻接表类型//图结构的定义typedef struct { AdjList vertices;//vertices-vertex的复数int vexnum; arcnum;//图当前的顶点数和弧数}ALGraph;

1、采用邻接表建立无向网

（3）图的遍历

​ 从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，这就叫做图的遍历，它是图的基本运算。遍历的实质是找每个顶点的邻接点的过程。

如何避免重复访问：

1、深度优先搜索遍历（Depth First Search — DFS）

用邻接矩阵实现图的深度优先搜索遍历：

2、广度优先搜索遍历（Breath First Search — BFS）

用邻接表实现图的广度优先搜索遍历：广度优先搜索遍历和树的层次遍历的思想类似。

（4）图的应用

1、最小生成树

​ 生成树是所有顶点都连在一起，但不存在回路的图。

​ 最小生成树：给定一个无向网，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树。

MST性质

构造最小生成树**普里姆（Prim）**算法：

构造最小生成树**克鲁斯卡尔（Kruskal）**算法：（贪心算法）

2、最短路径

​ 最短路径问题：在有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。第一类问题（单源最短路径）采用**Dijkstra（迪杰斯特拉）算法，第二类问题（所有顶点间的最短路径），采用Floyd（佛洛依德）**算法。

Dijkstra算法：

Floyd算法：

3、拓扑排序

有向无环图：是一种特殊的有向图，该有向图中没有环形结构。

​ 拓扑排序：在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧 < i , j > <i,j> <i,j>存在，则在这个序列中， i i i一定排在 j j j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

拓扑排序的作用是，判断图中是否存在环，如果图中存在环，那么存在一些顶点不在图的拓扑序列中。

4、关键路径

关键路径的描述量：

九、查找

（1） 查找表

​ 查找表是由同一类型的数据元素构成的集合，由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录，若查找表中存在这样一个记录，则称为“查找成功”，此时给出整个记录的信息，或者指示该记录在查找表中的位置；否则称为“查找失败”，查找结果给出空指针。查找算法的评价指标：关键字平均比较次数，也称为平均比较长度（ASL，Average Search Length）

A S L = ∑ i = 1 n p i c i ASL=\sum_{i=1}^{n}{p_ic_i} ASL=i=1∑n​pi​ci​

其中， n n n是记录个数， p i p_i pi​查找的第 i i i个记录的概率（通常认为 p i = 1 / n p_i=1/n pi​=1/n）， c i c_i ci​是找到的第 i i i个记录所需的比较次数。查找表分为静态查找表和动态查找表。

（2）线性表的查找

1、顺序查找（线性查找）

​ 应用范围：1、顺序表或线性表表示的静态查找表；2、表内元素之间无序。思想：从线性表的某一端开始，遍历线性表进行查找。

为了避免每次查找都进行两次比较，可以作如下改进：带哨兵的顺序查找

当待查找的长度过长时，这样改进之后能使所需的平均时间减少一半。

顺序查找的复杂度分析：

顺序查找的特点：1、算法简单，逻辑次序无要求，且不同存储结构均适用；2、缺点是时间复杂度高。

2、二分查找

​ 应用范围：表内之间元素有序，且顺序可知。思想是：每次将待查找的记录所在的区间缩小一半。

非递归的写法：

递归的写法：

​ 二分查找的特点：优点，查找效率比顺序查找高；缺点，只适用于有序表，且限于顺序存储结构（对线性表链表无效）。

3、分块查找

分块查找法的思想：

分块查找法的时间效率：

（3）树表的查找

​ 当表插入、删除等操作频繁时，为了维护表的有序性，需要移动很多记录，此时就可以采用动态查找表。表的结构在查找的过程中动态生成。

​ 二叉排序树（Binary Sort Tree），又称为二叉搜索树，二叉查找树。二叉排序树的定义：1、若其左子树非空，则左子树上所有结点的值均小于根结点的值；2、若其右子树非空，则右子树上的所有节点的值均大于等于根结点的值；3、其左右子树本身又各是一棵二叉排序树。

二叉排序树的性质：

二叉排序树的存储：采用二叉链表来进行存储

二叉排序树的查找：（递归算法）

二叉排序树查找性能分析：

二叉排序树的插入：

二叉排序树的生成：从空树出发，经过一系列的查找、插入操作之后，可以生成一棵二叉排序树。

​ 平衡二叉树（Balanced Binary Tree）又称为（AVL树），一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：1、左子树与右子树的高度只差的绝对值小于等于1；2、左子树和右子树也是平衡二叉排序树。平衡因子就是左子树的高度减去右子树高度的绝对值。

平衡二叉树的调整有四种，分别是LL、RR、LR、RL调整。

（4）哈希表的查找

​ 哈希表又称为散列表，其基本思想：记录的存储位置与关键字之间存在对应关系——hash函数，通过hash函数就可以对元素进行查找，查找效率高，但是空间效率低。

​ 关键术语：1、散列方法，选取某个函数，依照该函数按照关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比对，确定查找是否成功。2、散列函数（hash），散列方法中运用的转换函数。3、散列表，按照上述思想构造的表。 4、冲突，不同关键码映射到同一个散列地址上。

​ 散列函数的构造方法：

直接定址法： H a s h ( k e y ) = a × k e y + b Hash(key)=a\times{key}+b Hash(key)=a×key+b（ a 、 b a、b a、b为常数），优点是以关键字 k e y key key的某个线性函数为散列地址，不会产生冲突。缺点是要占用连续的地址空间，空间效率较低。

除留余数法： H a s h ( k e y ) = k e y m o d p Hash(key)=key\qquad{mod}\qquad{p} Hash(key)=keymodp（ p p p是一个整数），设表长为 m m m，取 p ≤ m p\le{m} p≤m且 p p p为质数。

​ 解决散列表中的冲突问题的方法：1、开放定址法（开地址法）；2、链地址法（拉链法）；3、再散列法（双散列函数法）；4、建立一个公共溢出区。

1、开放定址法：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

线性探测法的示例：

二次探测法的示例：

2、链地址法：将具有相同散列地址的记录链成一单链表， m m m个散列地址就设 m m m个单链表，然后用一个数组将 m m m个单链表的表头指针存储起来，形成一个动态结构。（散列表的链式存储结构）

散列表的查找：

散列表的查找效率分析：

---

十、排序

​ 排序是将一组杂乱无章的数据按照一定规律顺次排列起来，即将无序序列排成一个有序序列的运算。排序的分类：

排序算法是否稳定，看排序的过程中记录的相对次序是否发生改变，若发生改变那么是不稳定的，反之，是稳定的。自然排序，如果排序算法在序列基本有序的情况下，排序速率越快，那么排序算法是自然的，反之，是非自然的。

待排序的数据存储结构定义：

（1）插入排序

​ 基本思想：每步将一个待排序的对象，按其关键码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

插入排序的分类：

1、直接插入排序

使用带哨兵的直接插入排序：

直接插入排序的时间复杂度分析：

2、折半插入排序

折半插入排序时间复杂度分析：

3、希尔排序

​ 基本思想：先将整个待排序的记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的特点是：1、缩小增量，2、多遍插入排序。示例：

​ 希尔排序的基本思路：1、定义增量序列 D K : D M > D M − 1 > … > D 1 = 1 D_K:D_M>D_{M-1}>\dots{>D_1}=1 DK​:DM​>DM−1​>…>D1​=1；2、对每个 D K D_K DK​进行" D K − 间 隔 D_K-间隔 DK​−间隔"插入排序（ K = M , M − 1 , … , 1 K=M,M-1,\dots{,1} K=M,M−1,…,1）

希尔排序的时间复杂度分析：

（2）交换排序

1、冒泡排序

​ 基本思想：每趟不断将记录两两进行比较，并按照前小后大规则进行交换。

当某一趟比较时不出想记录的交换，说明已经排好序了，可以结束算法了。

冒泡排序的时间复杂分析：

2、快速排序

​ 基本思想：任取一个元素作为中心，所有比它小的元素一律放在前面，比它大的元素一律后放，形成左右两个子表。对各子表重新选择中心元素并依次规则进行调整，直到每个子表的元素只有一个。

快速排序的时间复杂度分析：

（3）选择排序

​ 基本思想：在待排序的数据中选出最大（小）的元素放在最终的位置。基本操作：1、首先通过 n − 1 n-1 n−1次关键字比较，从 n n n个记录中找出关键字最小的记录，将他与第一个记录交换；2、再通过 n − 2 n-2 n−2次比较，从剩余的 n − 1 n-1 n−1个记录中找出关键字次小的记录，将它与第二个记录交换；3、重复上述操作，共进行 n − 1 n-1 n−1趟排序后，排序结束。

1、直接选择排序

2、堆排序

​ 堆的定义：若 n n n个元素的序列 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots ,a_n\} { a1​,a2​,…,an​}满足

KaTeX parse error: Unknown column alignment: * at position 39: … \begin{array}{*̲*lr**} a_i\le…

则分别称该序列 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots ,a_n\} { a1​,a2​,…,an​}为小根堆和大根堆。从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点。

堆判别的示例：

​ 堆排序的思想：若在输出堆顶的最小值（最大值）后，使得 n − 1 n-1 n−1个元素的序列又建成一个堆，则得到 n n n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程称为堆排序。

​ 堆的向下调整：

堆的实现采用顺序表的结构，具体的关系如下，父亲结点和孩子结点之间的编号关系：当列表从0开始编号时，1、父亲结点和左孩子结点之间的编号关系 i → 2 i + 1 i\to{2i+1} i→2i+1；2、父亲结点和右孩子之间的编号关系 i → 2 i + 2 i\to{2i+2} i→2i+2；3、从孩子结点找父亲结点 i → ⌊ ( i − 1 ) / 2 ⌋ i\to{\lfloor{(i-1)/2\rfloor}} i→⌊(i−1)/2⌋。当列表从1开始编号时，1、父亲结点和左孩子结点之间的编号关系 i → 2 i i\to{2i} i→2i；2、父亲结点和右孩子之间的编号关系 i → 2 i + 1 i\to{2i+1} i→2i+1；3、从孩子结点找父亲结点 i → ⌊ i / 2 ⌋ i\to{\lfloor{i/2\rfloor}} i→⌊i/2⌋。

​ 堆的建立：

堆建立的示例：

堆排序算法：

（4）归并排序

​ 基本思想：将两个或两个以上的有序子序列“归并”为一个有序子序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 R [ l … m ] R[l\dots{m}] R[l…m]和 R [ m + 1 … n ] R[m+1\dots{n}] R[m+1…n]归并为一个有序子序列 R [ l … n ] R[l\dots{n}] R[l…n]。

归并排序算法：

（5）基数排序

​ 基本思想：分配+收集，也叫桶排序或箱排序，设置若干个箱子，将关键字为 k k k的记录放入第 k k k个箱子，让后再按序号将非空的箱子连接。基数排序：数字是有范围的，均由 0 ∼ 9 0\sim9 0∼9这十个数字组成，则只需设置十个箱子，相继按个、十、百…进行搜索。

（6）排序算法小结

---

附录A- ASCII