C语言数据结构知识点小结(全），C语言数据结构知识点全面总结

温馨提示：这篇文章已超过408天没有更新，请注意相关的内容是否还可用！

摘要：本文总结了C语言数据结构的主要知识点，涵盖了线性结构如数组、链表、栈和队列，以及非线性结构如树和图。文章详细解释了每种结构的特点、实现方法和应用场景，帮助读者深入理解数据结构的原理和在C语言中的实际应用。本文还涉及了一些常见算法和性能分析，为学习和应用C语言数据结构提供了全面的指导。

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 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 #include //函数结果状态代码 #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 100 typedef 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; else return FALSE; } //线性表取第i个值 Status GetElem(const SqList* L, int i, ElemType e) { if (iL->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 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 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 length) { L->elem[n - 1] = 0; //删除指定元素 for (i = n - 1; i length - 1; i++) //剩余元素移位 { L->elem[i] = L->elem[i + 1]; } L->length--; //顺序表长度-1 return 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 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 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 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 next; } if (!p || j > i) //如果待查找的元素大于链表长度或者小于1，查找错误 return ERROR; *e = p->data; return OK; } //单链表按值查找,返回LNode LNode* 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; //没找到,返回0 else return j; //找到,返回第几个结点 } //单链表插入,在第i个结点之前插入一个结点 Status InsertLinkList(LinkList *L, int i, ElemType value) { LNode* p; p = (*L)->next; int j = 1; while (p && j 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 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 #include //函数结果状态代码 #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; else return FALSE; } //判断顺序栈是否已满 Status IsFullSqStack(const SqStack* S) { if (!S->base) return ERROR; if (S->top - S->base == S->stacksize) return TRUE; else return 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 #include //函数状态宏定义 #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; else return 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 100 typedef struct { QElemType* base; //数据指针，初始化动态存储空间 int front; //头元素的索引，不是指针 int rear; //尾元素的索引，不是指针 } SqQueue;
        
        顺序队入队时的假上溢问题：
        顺序队存在假上溢的问题，即当队尾指针指向了最大元素个数MAXQSIZE，但是队头指针却不为0，这种情况称为假上溢，为了解决这个问题有以下两种做法：1、每次都将队列中剩余的元素向队头方向移动，这种方式时间效率低。2、把队列视为循环队列。
        如何判断队空队满：
        采用少用一个元素空间的方法比较简单。
        循环队列的初始化
        求队列的长度
        循环队列入队
        循环队列出队
        取队头元素
        顺序队列的完整实现：
        
        //顺序队列的实现 //头文件包含 #include #include //函数状态宏定义 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 //类型定义 typedef int Status; typedef int QElemType; //顺序队定义 #define MAXQSIZE 100 typedef 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 #include //函数状态宏定义 #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=′a1a2…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 255 typedef 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 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 100 typedef 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 100 typedef 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 + next int child; struct CTnode* next; } *ChildPtr; typedef struct { //双亲结点 data + firstchild TElemType data; ChildPtr firstchild; //孩子链表头指针 } CTBox; #define MAX_TREE_SIZE 100 typedef 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∑nwklk
        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 Tree typedef 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 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