数据结构期末复习

标签：结点 return 复习 int ElemType 元素 期末 二叉树 数据结构

数据结构期末复习

1 绪论

1. 算法的基本概念
2. 数据结构的基本概念
3. 数据抽象和抽象数据类型
4. 描述数据结构和算法
5. 算法分析的基本方法

2 线性表

1. 线性表的定义及基本操作
2. 线性表的顺序存储
3. 线性表的链接存储

3 栈和队列

1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
3. 栈和队列的链式存储结构
4. 表达式计算
5. 递归

4 数组

1. 数组的基本概念
2. 特殊矩阵
3. 稀疏矩阵

5 树和二叉树

1. 树的基本概念
2. 二叉树

​ ① 二叉树的定义及主要特征

​ ② 二叉树的顺序存储和链式存储

​ ③ 二叉树的遍历

​ ④ 线索二叉树的基本概念和构造

3. 树和森林

​ ① 树的存储结构

​ ② 森林和二叉树的转换

​ ③ 树和森林的遍历

4. 树和二叉树的应用

​ ① 二叉排序树

​ ② 二叉平衡树

​ ③ 哈夫曼(Huffman)树和哈夫曼编码

6 图

1. 图的基本概念
2. 图的存储及基本操作

​ ① 邻接矩阵法

​ ② 邻接表表示法

3. 图的遍历

​ ① 深度优先搜索

​ ② 广度优先搜索

4. 图的基本应用

​ ① 拓扑排序

​ ② 关键路径

​ ③ 最小代价生成树

​ ④ 最短路径

7 搜索（Search）

1. 搜索的基本概念
2. 顺序搜索法
3. 二分搜索法
4. B-树及其基本操作
5. 散列(Hash)表
6. 搜索算法的分析及应用

8 内排序

1. 排序的基本概念
2. 简单选择排序
3. 直接插入排序
4. 冒泡排序(bubble sort)
5. 希尔排序(shell sort)
6. 快速排序
7. 堆排序
8. 两路合并排序(merge sort)
9. 基数排序
10. 各种内部排序算法的比较
11. 内部排序算法的应用

---

第一章 绪论

1.1 基本概念和术语

1.1.1 基本概念

1. 数据是可被计算机识别并加处理的对象。包括数值型（整型、浮点型等）和非数值型（图片格式、音频格式等）。

2. **数据元素（元素、记录）**是由数据组成的具有一定意义的基本单位。

3. 数据项是组成数据元素的不可分割的最小单位。

1.1.2 数据结构

1. 数据结构是由某一数据对象及该对象中所有数据元素之间的关系组成的。其中包括数据的逻辑结构、存储结构以及数据的运算三个方面。

2. 数据的逻辑结构是指数据元素之间的内在关系，他从逻辑关系上描述数据。其中包含线性结构（一对一）、树形结构（一对多）、图结构（多对多）以及集合结构。

3. 数据的逻辑结构可以进一步划分成线性结构和非线性结构。

4. 数据的存储结构是指数据元素之间的关系在计算机内的表示形式，是数据的逻辑结构在计算机存储中的映像。其中包含顺序存储结构和链式存储结构。

5. 数据的运算是定义在逻辑结构上的，而运算的实现则是依赖于存储结构。

6. 数据元素之间的关系在计算机中有顺序存储方式、链式存储方式、索引存储方式、散列存储方式。

7. 顺序存储方式：数据元素顺序存放，每个存储节点只含一个元素。存储位置反应数据元素间的逻辑关系。存储密度大，但有些操作（比如插入、删除）效率较差。

8. 链式存储方式：指针反应数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作，但是存储空间开销较大。

9. 索引存储方式：除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）。兼有动态和静态的特性。

10. 散列存储方式：通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。存储速度快，只能按照关键字随机存取，不能顺序存取，也不能折半存取。

1.2 抽象数据类型

1. 数据类型指性质相同的值的集合以及定义在该值集上的运算的集合。
2. 抽象数据类型的最主要的两个特征是数据封装和信息隐蔽。

1.3 算法

1.3.1 算法

1. 算法的五个特征：输入、输出、可行性、确定性、有穷性。
2. 算法可以用自然语言、流程图、程序设计语言以及伪代码描述。
3. 衡量算法优劣的四个基本标准：正确性、可读性、健壮性、高效性。

1.3.2 算法的时间复杂度

1. 时间复杂度是指程序运行从开始到结束所需的时间。

2. 一个算法中的语句执行次数称为语句频度。

3. 大O表示算法的一种上界渐近时间复杂度

4. 时间复杂度氛围最好情况、最坏情况、平均情况。

1.3.3 空间复杂度

1. 空间复杂度是指对应的程序从运行开始到结束所需的存储空间。其中分为固定部分和可变部分。

2. 固定部分与问题规模无关。

3. 可变部分的大小与问题规模有关。

第二章 线性表

2.1 线性表的定义

1. 线性表是零个或若干个数据元素构成的线性序列。

2.2 线性表的顺序存储结构和实现

2.2.1 线性表的顺序存储结构

1. 线性表的顺序存储结构是指使用连续的存储空间，按照数据元素在线性表中的序号依次存储数据元素。采用顺序存储结构的线性表称为顺序表。

2. 设线性表中第一个元素 a₀ 在内存中的存储地址是 loc(a₀) ，每个元素占用 k 个存储单元，则线性表中任意元素a_i 在内存中的存储地址为

loc ( a i ) = loc ( a 0 ) + i ∗ k \text{loc}(a_i)=\text{loc}(a_0)+i*k loc(ai​)=loc(a0​)+i∗k

2.2.2 顺序表基本运算的实现

1. 定义

typedef struct seqList
{
  int n;									// 顺序表的长度
  int maxLength;					// 顺序表的最大允许长度
  ElemType *element;  	  // 指针 element 指向顺序表的存储空间的首地址
}SeqList;

2. 初始化

#define ERROR 0
#define OK 1
#define Overflow 2			// Overflow 代表上溢
#define Underflow 3			// Underflow 代表下溢
#define NotPresent 4		// NotPresent 表示元素不存在
#define Duplicate 5			// Duplicate 表示有重复元素
typedef int Status;
Status Init(SeqList *L, int mSize)
{
  L->maxLength = mSize;
  L->n = 0;
  L->element = (ElemType *)malloc(sizeof(ElemType)*mSize);
  
  if(!L->element)
    return ERROR;
  return OK;
}

3. 查找

Status Find(SeqList L, int i, ElemType *x)
{
  if(i<0 || i>L.n-1)
    return ERROR;
 
  *x = L.element[i];
  return OK;
}

4. 插入

Status Insert(SeqList L, int i, ElemType x)
{
  int j;
  if(i<-1 || i>L->n-1)									// 判断下标 i 是否越界
    return ERROR;
  if(L->n == L->maxLength)						 	// 判断顺序表存储空间是否已满
    return ERROR;
  
  for(j = L->n-1; j>i; j--)
    L->element[j+1] = L->element[j];	 	// 从前往后逐个后移元素
  
  L->element[i+1] = x;									// 将新元素 x 放入下标 i+1 的位置
  L->n = L->n +1;
  return OK;
}

顺序表插入算法的平均时间复杂度为 O(n)，插入一个新元素时需移动元素的平均次数为
E i = ∑ i = − 1 n − 1 n − i − 1 = n 2 E_i = \sum_{i=-1}^{n-1}{n-i-1} = \frac{n}{2} Ei​=i=−1∑n−1​n−i−1=2n​

5. 删除

Status Delete(SeqList L, int i, ElemType x)
{
  int j;
  if(i<0 || i>L->n-1)										// 判断下标 i 是否越界
    return ERROR;
  if(!L->n)						 									// 判断顺序表是否为空
    return ERROR;
  
  for(j = i+1; j<L->n; j++)
    L->element[j-1] = L->element[j]; 		// 从前往后逐个前移元素
  L->n--;																// 表长减 1
  return OK;
}

顺序表删除算法的平均时间复杂度为 O(n)，删除一个新元素时需要移动元素的平均次数为
E d = ∑ i = 0 n − 1 n − i − 1 = n − 1 2 E_d = \sum_{i=0}^{n-1}{n-i-1} = \frac{n-1}{2} Ed​=i=0∑n−1​n−i−1=2n−1​

6. 输出

status Output(SeqList *L)
{
  int i;
  if(L->n == 0)						 					// 判断顺序表是否为空
    return ERROR;
  
  for(i=0; i<=L->n -1; i++)
    print("%d", L->element[i]);
  
  print("\n");
  return OK;
}

7. 撤销

void Destroy(SeqList *L)
{
  L->n = 0;
  L->maxLength = 0;
  free(L->element);
}

8. 主函数

#include <stdlib.h>
#include <stdio.h>
typedef int ElemType;
typedef struct seqList
{
  int n;									// 顺序表的长度
  int maxLength;					// 顺序表的最大允许长度
  ElemType *element;    	// 指针 element 指向顺序表的存储空间的首地址
}SeqList;

void main()
{
  int i;
  SeqList list;
  Init(&list, 10);				// 初始化线性表
  for(i=0; i<10; i++)
    Insert(&list, i-1, i);
  
  OutPut(&list);
  Delete(&list, 0);
  OutPut(&list);
  Destroy(&list);
}

2.3 线性表的链式存储结构和实现

2.3.1 单链表的定义和表示

1. 每个结点只包含一个指针域的链表，称为单链表。

2.3.2 单链表基本运算的实现

1. 定义

typedef struct node
{
  ElemType element;					// 结点的数据域
  struct node *link;				// 结点的指针域
}Node;

typedef struct singleList
{
  Node *first;
  int n;
}SingleList;

2. 初始化

Status Init(SingleList *L)
{
  L->first = NULL;
  L->n = 0;
  return OK;
}

3. 查找

Status Find(SingleList L, int i, ElemType *x)
{
  Node *p;
  int j;
  
  if(i<0 || i>L.n-1)				// 判断下标 i 是否越界
    return ERROR;
  
  p = L.first;
  
  for(j=0;j<i:j++)
    p=p->link;							 // 从头结点开始查找 ai
  
  *x = p->element;					 // 通过 x 返回 ai 的值
  return OK;
}

4. 插入

Status Insert(SingleList *L, int i, ElemType x)
{
  Node *p, *q;
  int j;
  
  if(i<-1 || i>L->n-1)									// 判断下标 i 是否越界
    return ERROR;
  
  p = L->first;
  
  for(j=0; j<i; j++)
    p = p->link;											// 从头结点开始查找 ai
  
  q = (Node*)malloc(sizeof(Node));  // 生成新结点
  q->element = x;
  
  if(i>-1)
  {
    q->link = p->link;
    p->link = q;
  }
  else
  {
    q->link = L->first;								// 新结点插在头结点之前，成为新的头结点
    L->first = q;
  }
  
  L->n++;
  return OK;
}

5. 删除

Status Delete(SingleList *L, int i)
{
  int j;
  Node *p, *q;
  
  if(!L->n)
    return ERROR;
  if(i<0 || i>L->n-1)
    return ERROR;
  
  q = L->first;
  p = L->first;
  
  for(j=0; j<i-1; j++)
    q = q->link;
  
  if(i==0)
    L->first = L->first->link;
  else
  {
    p = q->link;
    q->link = p->link;
  }
  
  free(p);
  L->n--;
  return OK;
}

6. 输出

Status Output(SingleList *L)
{
  Node *p;
  
  if(!L->n)
    return ERROR;
  
  p = L->first;
  
  while(p)
  {
    printf("%d", p->element);
    p = p->link;
  }
  return OK;
}

7. 撤销

void Destroy(SingleList *L)
{
  Node *p;
  while(L->first)
  {
    p = L->first->link;
    free(L->first);
    L->first = p;
  }
}

8. 主函数

#include <stdlib.h>
#include <stdio.h>
typedef int ElemType;

typedef struct node
{
  ElemType element;					// 结点的数据域
  struct node *link;				// 结点的指针域
}Node;

typedef struct singleList
{
  Node *first;
  int n;
}SingleList;

void main()
{
  int i;
  int x;
  
  SingleList list;
  Init(&list);
  
  for(i=0; i<9; i++)
    Insert(&list, i-1, i);
  
  printf("the linklist is:");
  Output(&list);
  Delete(&list, 0);
  printf("\nthe linklist is:");
  Output(&list);
  Find(&list, 0, &x);
  printf("\nthe value is:");
  printf("%d", x);
  Destroy(&list);
}

2.3.3 带表头结点的单链表

1. 相较于之前的单链表，由于有表头节点，使得不需要对头结点的插入和删除做特别处理，简化了算法。
2. 头结点和头指针的区别：

​ ①头结点：为了操作统一、方便设立，放在第一个元素，其数据域一般无意义

​ ②头指针：头指针具有标识的作用，指向链表的第一个结点

3. 定义

typedef struct headerList
{
  Node *head;
  int n;
}HeaderList;

4. 初始化

Status Init(HeaderList *h)
{
  h->head = (Node *)malloc(sizeof(Node));
  
  if(!h->head)
    return ERROR;
  
  h->head-link = NULL;					// 设置单链表为空链表
  h->n = 0;
  return OK;
}

5. 插入

Status Insert(HeaderList *h, int i, ElemType x)
{
  Node *q, *p;
  int j;
  
  if(i<-1 || i>L->n-1)									// 判断下标 i 是否越界
    return ERROR;
  
  p = h->head;
  
  for(j=0; j<=i; j++)
    p = p->link;
  
  q = (Node *)malloc(sizeof(Node));
  q->element = x;
  q->link = p->link;
  p->link = q;
  h->n++;
  return OK;
}

6. 删除

Status Delete(HeaderList *h, int i)
{
  int j;
  Node *p, *q;
  
  if(!h->n)
    return ERROR;
  if(i<0 || i>h->n-1)
    return ERROR;
  
  q = h->first;
  
  for(j=0; j<i-1; j++)
    q = q->link;
  
  p = q->link;
  q->link = p->link
  free(p);
  h->n--;
  return OK;
}

2.3.4 单循环链表

1. 链表的最后一个结点的指针域指向链表的第一个结点或者表头结点称为单循环链表。
2. 循环链表最大的优点是：从任一结点出发都可以访问到链表中每一个元素。

2.3.5 双向链表

1. 链表的结点有两个指针域，分别指向前驱结点和后继结点，这样的链表称为双向链表。

2. 当查找一个结点前面的结点时，无需再从头重新扫描一遍链表，可以根据当前结点向前扫描链表。

2.4 顺序表与链表的比较

2.4.1 时间性能

	顺序表	链表
查找	O(1)	O(n)
插入与删除	O(n)	O(1)

2.4.2 空间性能

1. 线性表需要预先分配存储空间，若分配过大，则浪费；分配过小则容易溢出。
2. 链表不需要预先分配存储空间。
3. 当线性表中元素个数变化较大或者未知的时候，宜采用链表；反之宜采用线性表。

2.4.3 其它方面

1. 顺序存储结构是通过物理上相邻表示元素之间的关系的；链式存储结构是通过指针表示元素之间关系的。

第三章 堆栈和队列

3.1 堆栈

3.1.1 堆栈 ADT

1. 堆栈是限定插入和删除操作都在表的同一端进行的线性结构。

2. 堆栈具有先进后出的特点。

3.1.2 堆栈的顺序表示

1. 定义

typedef struct stack
{
  int top;
  int maxSize;
  ElemType *element;
}Stack;

2. 关键代码

// 堆栈结构体定义
typedef struct stack
{
  int top;
  int maxSize;
  ElemType *element;
}Stack;

// 创建一个能容纳 mSize 个单元的空堆栈
void Create(Stack *S, int mSize)
{
  S->maxSize = mSize;
  S->element = (ElemType *)malloc(sizeof(ElemType)*mSize);
  S->top = -1;
}

// 销毁一个已存在的堆栈，即释放堆栈占用的数组空间
void Destroy(Stack *s)
{
  S->maxSize = 0;
  free(S->element);
  S->top = -1
}

// 判断堆栈是否为空栈，若是，则返回true，否则返回false
bool IsEmpty(Stack *s)
{
  return S->top = S->maxSize-1
}

// 判断堆栈是否已满，若是，则返回true，否则返回false
bool IsFULL(Stack *S)
{
  return S->top == -1;
}

// 获取栈顶元素，并通过 x 返回。若操作成功，则返回true，否则返回false
bool Top(Stack *S, ElemType *x)
{
  if(IsEmpty(S))
    return false;
  
  *x = S->elemnt[S->top];
  return true;
}

// 在栈顶位置插入元素 x（入栈操作）。若操作成功，则返回true，否则返回false
bool Push(Stack *S, ElemType x)
{
  if(IsFull(S))
    return false;
  
  S->top++;
  S->elememt[S->top] = x;
  return true;
}

// 删除栈顶元素（出栈操作）。若操作成功，则返回true，否则返回false
bool Pop(Stack *S)
{
  if(IsEmpty(S))
    return false;
  S->top--;
  return true;
}

// 清除堆栈中全部元素，但并不释放空间
void Clear(Stack *S)
{
  S->top = -1;
}

3.2 队列

3.2.1 队列 ADT

1. 队列是限定在表的一段插入、在表的另一端删除的线性结构。

2. 队列有先进先出的特点。

3.2.2 队列的顺序表示

1. 定义

typedef struct queue
{
  int front;
  int rear;
  int maxSize;
  ElemType *element;
}Queue;

1. 由于普通的队列在不断入队和出队操作之后很容易造成假溢出的现象，所以需要对其进行改进。而最常用的一种改进方法是采用循环队列结构。
2. 由于循环队列从图像上看是一个圆，所以在计算机中需要通过表达式来计算 front 和 rear 指针前进后的位置

front = ( front + 1 ) mod ( maxSize ) \text{front} = (\text{front} + 1) \text{mod}(\text{maxSize}) front=(front+1)mod(maxSize)

rear = ( rear + 1 ) mod ( maxSize ) \text{rear} = (\text{rear} + 1) \text{mod}(\text{maxSize}) rear=(rear+1)mod(maxSize)

3. 假设以数组 A[m] 存放循环队列的元素，其头尾指针分别为 front 和 rear，则当前队列中的元素个数为

( rear − front + m ) mod ( m ) (\text{rear}-\text{front}+m)\text{mod}(m) (rear−front+m)mod(m)

4. 循环队列也存在空间溢出的问题。

5. 循环队列关键代码

// 循环队列结构体定义
typedef struct queue
{
  int front;
  int rear;
  int maxSize;
  ElemType *element;
}Queue;

// 创建一个能容纳 mSize 个单元的空队列
void create(Queue *Q, int mSize)
{
  Q->maxSize = mSize;
  Q->element = (ElemType *)malloc(sizeof(ElemType)*mSize);
  Q->front = Q->rear = 0;
}

// 销毁一个已存在的队列，即释放队列占用的数组空间
void Destroy(Queue *Q){
  Q->maxSize = 0;
  free(Q->element);
  Q->front = Q->rear = -1;
}

// 判断队列是否为空，若是，则返回true，否则返回false
bool IsEmpty(Queue *Q)
{
  return Q->front == Q->rear;
}

// 判断一个队列是否已满，若是，则返回true，否则返回false
bool IsFULL(Queue *Q)
{
  return (Q->rear+1) % Q->maxSize == Q->maxSize;
}

// 获取队头元素，并通过 x 返回。若操作成功，则返回true，否则返回false
bool Front(Queue *Q, ElemType *x)
{
  if(IsEmpty(Q))
    return false;
  *x = Q->element[(Q->front+1)%Q->maxSize];
  return true;
}

// 在队列 Q 的队尾插入元素 x（入队操作）。则返回true，否则返回false
bool EnQuene(Queue *Q, ElemType x)
{
  if(IsFULL(Q))
    return false;
  Q->rear = (Q->rear+1) % Q->maxSize;
  Q->element[Q->rear] = x;
  return true;
}

// 从队列 Q 中删除队头元素（出队操作）。则返回true，否则返回false
bool DeQueue(Queue *Q)
{
  if(IsEmpty(Q))
    return false;
  Q->front = (Q->front+1)%Q->maxSize;
  return true;
}

// 清除队列中全部元素，使队列恢复到初始状态（Q->front = Q->rear = 0），但并不释放空间
void Clear(Queue *Q)
{
  Q->front = Q->rear = 0;
}

3.3 表达式计算

1. 掌握前缀，中缀，后缀表达式

3.4 递归

3.4.1 递归的概念

1. 递归本质上也是一种循环的程序结构，它把“较复杂”的计算逐次归结为“较简单”的计算，一直归结到“最简单”的计算，并得到计算结果为止。
2. 递归适用于非数值计算领域。

3.4.2 递归的实现

1. 递归的优点：程序非常简介和清晰，易于分析。
2. 递归的缺点：费时间，费空间。

第四章 数组和字符串

4.1 数组

1. 数组是连续存储的数据类型，常被用来实现数据的顺序存储结构。

4.2 特殊矩阵

4.3.1 对称矩阵

1. n 阶矩阵 A 中的矩阵元素满足 a_ij = a_ji (0≤i, j≤n)，则称矩阵 A 为 n 阶对称矩阵。
2. 在计算机中，对称矩阵只需要存储上三角或下三角的元素。所以，一个 n 阶矩阵实际存储时只需要 n*(n+1)/2 个元素的存储空间。
3. 以行优先存储一个 n 阶对称矩阵在一维数组 B 中，则矩阵下三角元素 a_ij 在 B 中下标 k (0≤k<N)满足：

k = { i ∗ ( i − 1 ) 2 + j − 1 i ≥ j j ∗ ( j − 1 ) 2 + i − 1 i < j k = \begin{cases} \frac{i*(i-1)}{2}+j-1 & i\geq j \\ \frac{j*(j-1)}{2}+i-1 & i<j \end{cases} k={2i∗(i−1)​+j−12j∗(j−1)​+i−1​i≥ji<j​

4. 以行优先存储一个 n 阶对称矩阵在一维数组 B 中，则矩阵上三角元素 a_ij 在 B 中下标 k (0≤k<N)满足：

k = { j ∗ ( 2 n − j − 1 ) 2 + i i > j i ∗ ( 2 n − i − 1 ) 2 + j j ≤ i k = \begin{cases} \frac{j*(2n-j-1)}{2}+i & i>j \\ \frac{i*(2n-i-1)}{2}+j & j\leq i \end{cases} k={2j∗(2n−j−1)​+i2i∗(2n−i−1)​+j​i>jj≤i​

4.3.2 三角矩阵

1. 定义：

​ ①上三角矩阵：矩阵 A 中的元素满足 a_ij (0<i<j<n) 为常数 c（通常 c = 0）。

​ ②下三角矩阵：矩阵 A 中的元素满足 a_ji (0<j<i<n) 为常数 c（通常 c = 0）。

3. 将一个 n 阶的下三角矩阵，以行优先存储到一维数组 B 中，则元素 a_ij 在一维数组中的下标 k (0≤k≤N) 满足：

k = { i ∗ ( i − 1 ) 2 + j − 1 i ≥ j N i < j k = \begin{cases} \frac{i*(i-1)}{2}+j-1 & i\geq j \\ N & i<j \end{cases} k={2i∗(i−1)​+j−1N​i≥ji<j​

4. 将一个 n 阶的上三角矩阵，以行优先存储到一维数组 B 中，则元素 a_ij 在一维数组中的下标 k (0≤k≤N) 满足：

k = { N i > j ( i − 1 ) ∗ ( 2 n − i + 2 ) 2 + j − i j ≤ i k = \begin{cases} N & i>j \\ \frac{(i-1)*(2n-i+2)}{2}+j-i & j\leq i \end{cases} k={N2(i−1)∗(2n−i+2)​+j−i​i>jj≤i​

4.4 稀疏矩阵

4.4.1 稀疏矩阵的抽象数据类型

1. 矩阵中非零元素数量占元素总数的比例称为矩阵的稠密度。

2. 稀疏矩阵：稠密度很小的矩阵。

3. 稀疏矩阵中的非零元素 a_ij 以三元组 <i, j, a_ij> 表示。

4.4.2 稀疏矩阵的转置算法

1. 稀疏矩阵转置算法1：对行三元组交换行列号 -> 根据行号排序。

2. 稀疏矩阵转置算法2：扫描行三元组，找到列下标 j = n（n=1,2,3,…）的所有三元组，然后交换行列号后保存。重复进行，每次进行使寻找的列下标加1。

3. 稀疏矩阵的快速转置算法：总体思想是根据行三元组中的列得出每一列的非零元素个数，然后将同一列作为一整个单元来划定范围，放置在新的矩阵中。比如一个三元组中有四列，每列的非零元素个数为 [1,3,2,4]，则每列的首元素存储地址起始为 [0,1,4,7]。

4.5 字符串

4.5.1 字符串的抽象数据类型

1. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符。
2. 两个串相等的充分必要条件是两串的长度相等并且两串对应位置的字符也相等。
3. 串的长度是指串中所含字符的个数。
4. 组成串的数据元素是字符。
5. 空串是任何串的子串。
6. 空格串是指由空格字符（ASCII 值 32）所组成的字符串，其长度等于空格个数。

4.5.2 简单字符串匹配算法

1. 字符串模式匹配是从主串 s 中 pos 位置开始查找子串 p 的过程。
2. 思路：从主串 s 的 pos 位置开始进行逐趟匹配，每趟匹配都与模式串 p 依次比较各个字符。
3. 代码

int Index(String s, String p, int pos)
{
  int s_start, p_start=0, s_fail, p_fail;
  
  for(s_start = pos; s_start<=s.length-p.length; s_start++)
  {
    if(Match(s, p, s_start, p_start, &s_fail, &p_fail))
      return s_start;
  }
  
  return -1;
}

// 从模式串 p_start 位置与主串的 s_start 位置开始进行匹配
bool Match(String s, String p, int s_start, int p_start, int *s_fail, int *p_fail)
{
  int i = s_start, j = p_start;
  
  for(; j<p.length; i++, j++)
  {
    if(s.str[i] != p.str[j])
    {
      if(s.str[i] != p.str[j])
      {
        *s_fail = i; // s_fail 记录主串失配位置
        *p_fail = j; // p_fail 记录模式串失配位置
      }
    }
  }
  
  return true;
}

4. 时间复杂度：O(m*n)

4.5.3 kmp 算法

该方法过于抽象，想要搞懂需要大量的绘图等步骤，遂建议看书或者是王道视频。但需记住以下的几点

1. 移动位数 = 已匹配的字符数 - 对应的部分匹配值
2. 部分匹配值取失配字符前一个字符
3. 当整体部分匹配值往右移一位（第一位用 -1 代替）时，可以取失配字符的部分匹配值带入计算
4. Fail 数组（失败函数，又称 next 数组）组为移动 3 中部分匹配值全部 +1 后的集合数组
5. nextval 数组 https://blog.csdn.net/coding_with_smile/article/details/125521122
6. kmp 算法的时间复杂度为 O(m+n)
7. 代码

// 失败函数
void Fail(String p, int *fail)
{
  int j=0, k=-1;
  fail[0] = -1;
  
  while(j<p.length)
  {
    if(k==-1 || p.str[j] == p.str[k])
    {
      j++; k++;
      fail[j] = k;
    }
    else
      k = fail[k];
  }
}

// KMP算法函数
int KMPIndex(String s, String p, int pos, int *fail)
{
  int s_start, p_start=0, s_fail, p_fail;
  
  while(s_start<=s.length-p,length)
  {
    if(Match(s, p, s_start, p_start, &s_fail, &p_fail))
      return s_start - p_start;
    else
    {
      // 如果本趟匹配失败，根据失败函数计算下一趟主串与模式串的开始匹配位置
      p_start = fail[p_fail];
      s_start = s_fail;
      if(p_start == -1)
      {
        p_start = 0;
        s_start ++;
      }
    }
  }
  return -1;
}

第五章 树和二叉树

5.1 树

5.5.1 树的定义

1. 树是包括 n(n≥0) 个结点的有限集合 D，R 是由 D 中元素构成的序偶的集合。若 D 为空，则 R 也为空，此时该树为空树。否则，R 满足一下特性：

​ （1）有且仅有一个结点 r ∈ D，不存在任何结点 v ∈ D，v ≠ r，使得 <v, r> ∈ R，称 r 为树的根；

​ （2）对于除根结点 r 以外的任一结点 u ∈ D，都有且仅有一个结点 v ∈ D，v ≠ u，使得<v, u> ∈ R。

​ 满足以上条件的称为树。

2. 树具有递归结构特征。

5.1.2 基本术语

1. 结点：树中的元素
2. 边：根和它的子树根之间形成边
3. 路径：如果从某结点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径
4. 双亲：根节点称为子树的双亲
5. 孩子：子树称为根结点的孩子
6. 兄弟：有相同双亲的结点互称为兄弟
7. 后裔：一个结点的所有子树上的任何结点都是该结点的后裔
8. 结点的度：一个结点拥有的子树数量
9. 叶节点：度为 0 的结点
10. 分支结点：度不为 0 的结点
11. 树的度：树中结点最大的度
12. 层次：根结点的层次为 1，其余结点层次等于其双亲层次加 1
13. 高度：树中结点最大层次
14. 森林：树的集合

5.2 二叉树

5.2.1 二叉树的定义

1. 二叉树是结点的有限集合，该集合或者为空集，或者由一个根和它互不相交的、同为二叉树的左子树和右子树组成。
2. 平衡因子是二叉树某一结点的左子树的深度减去右子树的深度的差。

5.2.2 二叉树的性质

1. 二叉树第 i(i≥1) 层上最多有 2^i-1 个结点。
2. 高度为 h 的二叉树上 至多有 2^h - 1 个结点。
3. 包含 n 个结点的二叉树的高度至少为 ⌈log₂(n+1)⌉，最高为 n。
4. 任意一颗二叉树中，若结点的数量为 n₀，度为 2 的结点的数量为 n₂，则 n₀ = n₂ + 1 成立。
5. 具有 n 个结点的完全二叉树的高度为 ⌈log₂(n+1)⌉。
6. 高度为 h 的完全二叉树上至少有 2^h-1 个结点，最多有 2^h-1 个结点。
7. 高度为 h 的完全二叉树上至少有 2^k-2 个叶子结点。
8. 一颗包含 n 个结点的完全二叉树，对树中的结点从上到下、从左到右的顺序，从 0 到 n - 1 编号，设树中某个结点的编号为 i，0 ≤ i < n，则有以下关系成立：

​ （1）当 i = 0 时，该结点为二叉树的根；

​ （2）当 i > 0 时，则该结点的双亲结点的编号为 ⌊(i-1)/2⌋；

​ （3）若 2i + i < n，则该结点有左孩子，该左孩子结点的编号为 2i + 1；

​ （4）若 2i + 2 < n，则该结点有右孩子，该右孩子结点的编号为 2i + 2。

5.2.3 二叉树的存储实现和基本运算

5.3 二叉树的遍历

5.3.1 二叉树的先序遍历

void PreOrderTree(BinaryTree *bt)
{
  PreOrder(bt->root);
}

void PreOrder(BTNode *T)
{
  if(!T)
    return;
  
  printf("%c", T->element);
  PreOrder(T->lChild);
  PreOrder(T->rChild);
}

5.3.2 二叉树的中序遍历

void InOrderTree(BinaryTree *bt)
{
  InOrder(bt->root);
}

void InOrder(BTNode *T)
{
  if(!T)
    return;
  
  InOrder(T->lChild);
  printf("%c", T->element);
  InOrder(T->rChild);
}

5.3.3 二叉树的后序遍历

void PostOrderTree(BinaryTree *bt)
{
  InOrder(bt->root);
}

void PostOrder(BTNode *T)
{
  if(!T)
    return;
  
  PostOrder(T->lChild);
  PostOrder(T->rChild);
  printf("%c", T->element);
}

5.3.4 二叉树的层次遍历

#define QUEUESIZE 100 									// 遍历过程中需要使用的队列的容量，根据实际需求调整

void LevelOrderTree(BinaryTree *tree)
{
  if(!tree->root)
    return;
  
  Queue Q;															// Q是用于存储 BTNode 结点类型的队列
  Create(&Q, QUEUESIZE);								// 创建包含 QUEUESIZE 个单元的队列存储空间
  BTNode *p = tree->root;
  EnQueue(&Q, p);											 	// 将根节点进队
  
  while(!IsEmpty(&Q))
  {
    Front(&Q, &p);
    DeQueue(&Q);
    
    printf("%c", p->element);
    if(p->lChild)
      EnQueue(&Q, p->lChild);
    if(p->rChild)
      EnQueue(&Q, p->rChild);
  }
}

5.4 线索二叉树

1. 为了能够保存遍历过程中结点之间的前驱和后继关系的信息，引入线索二叉树。
2. 线索二叉树是一种物理结构。
3. 线索二叉树的结点结构

lTag

lChild

element

rChild

rTag

当 lTag = 0 时，指向结点的左孩子，当 lTag = 1 时，指向结点的前驱结点；

当 rTag = 0 时，指向结点的左孩子，当 rTag = 1 时，指向结点的后继结点。

5.5 树和森林

5.5.1 森林与二叉树的转换

1. 二叉树转成森林，每个结点的右孩子变成与该结点同级的右兄弟，左孩子变成该结点的左孩子。
2. 森林转成二叉树，过程与 1 相反。

5.5.2 树和森林的存储表示

1. 多重链表表示法

element

child1

child2

...

child3

2. 孩子兄弟表示法

lChild

element

rChild

3. 双亲表示法
4. 三重链表表示法
5. 带右链的先序表示法

5.6 树和森林的遍历

5.6.1 按深度方向遍历

5.6.2 按宽度方向遍历

5.7 堆和优先权队列

5.7.1 堆

1. 堆的定义：一个大小为 n 的堆是一棵包含 n 个结点的完全二叉树，其根结点称为堆顶。

​ ① 最小堆：如果树中每个结点的元素都小于或等于其孩子结点的元素，则该堆为最小堆。

​ ② 最大堆：如果树中每个结点的元素都大于或等于其孩子结点的元素，则该堆为最大堆。

2. 堆的存储表示：顺序存储表示

3. 建堆运算

// 向下调整
void AdjustDown(ElemType heap[], int current, int border)
{
  int p = current;
  int minChild;
  ElemType temp;
  
  while(2*p+1 <= border)									// 若 p 不是叶节点，则执行调整
  {
    if((2*p+2 <= border) && (heap[2*p+1] > heap[2*p+2]))
      minChild = 2*p+2;										// 右孩子存在，且较小，则 minChild 指向 p 的右孩子
    else
      minChild = 2*p+1;										// 右孩子不存在，或较大，则 minChild 指向 p 的左孩子
    
    if(heap[p] <= heap[minChild])
      break;															// 若当前结点不大于其最小的孩子，则调整结束
    else																	// 否则将 p 和其最小孩子交换
    {
      temp = heap[p];
      heap[p] = heap[minChild];
      heap[minChild] = temp;
      p = minChild;												// 设置下轮循环待考察的元素的位置（即当前下移元素的位置）
    }
  }
}

// 向上调整
void AdjustUp(ElemType heap[], int current)
{
  int p = current;
  ElemType temp;
  
  while(p>0)
  {
    if(heap[p] < heap[(p-1)/2])			// 若 p 指向的元素小于其双亲节点，则与双亲结点交换
    {
      temp = heap[p]; heap[p]=heap[(p-1)/2]; heap[(p-1)/2] = temp;
      p = (p-1)/2;									// 将 p 向上移动至当前考察元素的双亲结点位置
    }
    else														// 若 p 指向的元素不小于其双亲结点，则调整完毕
      break;
  }
}

// 建堆
void CreateHeap(ElemType heap[], int n)
{
  int i;
  for(i=(n-2)/2; i>-i; i--)
    AdjustDown(heap, i, n-1);
}

5.7.2 优先权队列

1. 代码

typedef int BOOL;
typedef int ElemType;

typedef struct priorityQueue
{
  ElemType *elements;		// 存储元素的数组
  int n;								// 优先权队列中元素的数量
  int maxSize;					// 优先权队列的容量
}PriorityQueue;

// 创建一个空的优先权队列
void CreatePQ(PriorityQueue *PQ, int mSize)
{
  PQ->maxSize = mSize;
  PQ->n = 0;
  PQ->elements = (ElemType *)malloc(mSize *sizeof(ElemType));
}

// 销毁一个优先权队列，释放其占用的内存空间
void Destroy(PriorityQueue *PQ)
{
  free(PQ->element);
  PQ->n = 0;
  PQ->maxSize = 0;
}

// 判断优先权队列是否为空
BOOL IsEmpty(PriorityQueue *PQ)
{
  if(PQ->n == 0)
    return true;
  else
    return false;
}

// 判断优先权队列是否已满
BOOL IsFull(PriorityQueue *PQ)
{
  if(PQ->n == PQ->maxSize)
    return true;
  else
    return false;
}

// 获取当前优先权队列中元素的数量
int Size(PriorityQueue *PQ)
{
  return PQ->n;
}

// 在优先权队列中增加一个新元素 x
void Append(PriorityQueue *PQ, ElemType x)
{
  if(IsFull(PQ)) 													// 先判断优先权队列是否已满
    return;
  
  PQ->elements[PQ->n] = x;								// 将新元素 x 添加到队尾
  PQ->n++;
  AdjustUp(PQ->elements, PQ->n-1);				// 对新元素 x 做向上调整
}

// 取出优先级最高的元素，利用参数 x 返回，并在优先权队列中删除该元素
void Serve(PriorityQueue *PQ, ElemType *x)
{
  if(IsEmpty(PQ))
    return;
  
  *x = PQ->elements[0];
  PQ->n--;
  PQ->elements[0] = PQ->elements[PQ->n];	// 将队尾元素放至队首
  AdjustDown(PQ->elements, 0, PQ->n-1);		// 向下调整
}

5.8 哈夫曼树和哈夫曼编码

5.8.1 树的路径长度

1. 树的内路径长度：除叶结点以外，从树根到树中其他所有结点的路劲长度之和。
2. 树的外路径长度：从树根到树中所有叶结点的路径长度之和。
3. 不存在度为 1 的结点的二叉树称为扩充二叉树，也叫做 2- 树。
4. 设扩充二叉树的内路径长度为 I，外路径长度为 E，n 为该扩充二叉树的非叶结点的数量，则有

E = I+2n \text{E = I+2n} E = I+2n

5. 叶节点的加权路径长度：路径长度乘以该叶节点的权值。
6. 树的加权路径长度：树中所有叶结点的加权路径长度之和，记为WPL。

5.8.2 哈夫曼树和哈夫曼算法

1. 构造哈夫曼树的代码

BinaryTree CreateHFMTree(int w[], int m)
{
  PriorityQueue PQ;												// 定义优先权队列，用于存放二叉树根结点指针
  BinaryTree x, y, z;											// x, y, z，为二叉树变量
  CreatePQ(PQ, m);												// 初始化优先权队列 PQ，设优先权值存在根节点数据域
  
  for(int i=0; i<m; i++)
  {
    MakeTree(x, w[i], NULL, NULL);				// 创建仅包含根结点的二叉树，w[i] 为根的权值
    Append(PQ, x);												// 将新创建的二叉树插入优先权队列
  }
  
  while(PQ.n>1)
  {
    Serve(PQ, x);													// 从 PQ 中取出根结点权值最小的二叉树，存入 x
    Serve(PQ, y);													// 从 PQ 中取出根结点权值次小的二叉树，存入 y
    
    // 合并 x 和 y，作为新的二叉树 z 的左右子树，z 的优先权值等于 x 和 y 的优先权值之和
    if(x.root.element < y.root.element)		// 设置左子树根结点权值小于右子树
      MakeTree(z, x.root.element + y.root.element, x, y);
    else
      MakeTree(z, x.root.element + y.root.element, y, x);
    
    Append(PQ, z);												// 将合并生成的新二叉树 z 插入优先权队列
  }
  
  Serve(PQ, x);														// 获取优先权队列中唯一的二叉树，存入 x，该二叉树即为哈夫曼树
  return x;
}

5.8.3 哈夫曼编码

看王道视频

第六章 集合和搜索

6.1 集合的表示

6.1.1 集合的基本概念

1. 多重集是元素的无序汇集，其中每个元素都可以出现多次。一般以大括号表示。
2. 有序集是元素的汇集，其中每个元素可以出现多次。一般以圆括号表示。
3. 关键字用以表示一个数据元素的某个数据项。
4. 搜索是根据给定的某个值，确定集合中是否存在一个关键字值等于给定值的数据元素的过程。
5. 搜索又分为静态搜索和动态搜索。
6. 平均搜索长度（ASL）：在搜索过程中，给定值与集合中元素的关键字值的平均比较次数。

6.2 顺序搜索

6.2.1 无序表的顺序搜索

1. 代码

int Search(listSet L, ElemType x)
{
  int i;
  for(i=0; i<L.n; i++)
  {
    if(x == L.elment[i])
      return i;
  }
  return -1;
}

2. 算法分析

​ ① 搜索成功的情况下，假定表长为 n，每个元素 a_i（ i = 0, 1, 2, …）的搜索概率相同，即 P_i = 1/n，则平均搜索长度为
ASL = 1 n ∑ i = 0 n − 1 ( i + 1 ) = 1 n ∑ i = 1 n i = n + 1 2 \text{ASL} = \frac{1}{n}\sum_{i=0}^{n-1}{(\text{i}+1)} = \frac{1}{n}\sum_{i=1}^{n}{i}=\frac{n+1}{2} ASL=n1​i=0∑n−1​(i+1)=n1​i=1∑n​i=2n+1​
​ ② 搜索失败的情况下的平均搜索长度为 n。

6.2.2 有序表的顺序搜索

1. 代码

int Search(listSet L, ElemType x)
{
  int i;
  for(i=0; L.element[i]<x; i++)
  {
    if(x == L.elment[i])
      return i;
  }
  return -1;
}

2. 算法分析

​ ① 搜索成功的情况下，假定表长为 n，每个元素 a_i（ i = 0, 1, 2, …）的搜索概率相同，即 P_i = 1/n，则平均搜索长度为
ASL = 1 n ∑ i = 0 n − 1 ( i + 1 ) = 1 n ∑ i = 1 n i = n + 1 2 \text{ASL} = \frac{1}{n}\sum_{i=0}^{n-1}{(\text{i}+1)} = \frac{1}{n}\sum_{i=1}^{n}{i}=\frac{n+1}{2} ASL=n1​i=0∑n−1​(i+1)=n1​i=1∑n​i=2n+1​
​ ② 搜索失败的情况下，待查元素搜索失败可发生于共计 n+1 哥区间之内，若概率相等，即 P_i = 1/(n+1)，则平均搜索长度为
ASL = 1 + 1 n + 1 ∑ i = 0 n ( i + 1 ) = 1 + 1 n + 1 ∑ i = 1 n + 1 i = n 2 + 2 \text{ASL} = 1+\frac{1}{n+1}\sum_{i=0}^{n}{(\text{i}+1)} = 1+\frac{1}{n+1}\sum_{i=1}^{n+1}{i}=\frac{n}{2}+2 ASL=1+n+11​i=0∑n​(i+1)=1+n+11​i=1∑n+1​i=2n​+2

6.3 折半搜索

6.3.1 折半搜索的算法

1. 折半查找只能查找以顺序方式存储的有序表。
2. 递归算法

int binSearch(listSet L, ElemType x, int low, int high)
{
  if(low <= high)
  {
    int m = (low + high)/2;
    if(x < L.element[m]) 
      return binSearch(L, x, low, m-1);
    else if (x > L.element[m]) 
      return binSearch(L, x, m+1, high);
    else 
      return m;
  }
  return -1;
}

2. 迭代算法

int binSearch(listSet L, ElemType x)
{
  int m, low = 0, high = L.n-1;
  while(low <= high)
  {
    m = (low+high)/2;
    if(x < L.element[m]) 
      high = m-1;
    else if(x > L.element[m])
      low = m+1;
    else 
      return m;
  }
  return -1;
}

3. 折半搜索算法在搜索成功的情况下，关键字值比较次数不超过 ⌊log₂n⌋+1。在搜索失败的情况下，关键字值比较次数为 ⌊log₂n⌋或者⌊log₂n⌋+1。
4. 折半搜索算法在搜索成功的情况下平均时间复杂度为 O(log₂n)。
5. 折半搜索算法在查找成功的情况下平均查找长度为

ASL = 1 n ∑ i = 1 n l i = 1 n ( 1 × 1 + 2 × 2 + ⋯ + h × 2 h − 1 ) = n + 1 n l o g 2 ( n + 1 ) − 1 ≈ l o g 2 ( n + 1 ) − 1 \text{ASL} = \frac{1}{n}\sum_{i=1}^{n}{l_i} = \frac{1}{n}(1×1+2×2+\cdots+h×2^h-1)=\frac{n+1}{n}log_2(n+1)-1≈log_2(n+1)-1 ASL=n1​i=1∑n​li​=n1​(1×1+2×2+⋯+h×2h−1)=nn+1​log2​(n+1)−1≈log2​(n+1)−1

第七章 搜索树

7.1 二叉搜索树

7.1.1 二叉搜索树的定义

1. 中序遍历会得到一个递增排序的有序序列。

7.2.2 二叉搜索树的搜索

1. 搜索的递归实现的思路如下

​ （1）若二叉搜索树为空，则搜索失败，返回空指针。

​ （2）若二叉搜索树不为空，则将指定关键字值 k 与根结点元素的关键字值比较：

​ ① 若 k 等于该关键字值，则搜索成功，返回根结点地址；

​ ② 若 k 小于该关键字值，则以同样的方法搜索左子树；

​ ③ 若 k 大于该关键字值，则以同样的方法搜索右子树。

2. 递归实现的代码

BSTree RecSearchBST(BSTree T, KeyType k)
{
  if(!T)
    return NULL;
  
  if(T->Element.Key == k)
    return T;
  else if(k < T->Element.Key)
    return RecSearchBST(T->LChild, k);
  else
    return RecSearchBST(T->rChild, k);
}

3. 迭代实现的代码

BSTree IterSearchBST(BSTree T, KeyType k)
{
  while(T)
  {
    if(k == T->Element.Key)
      return T;
    else if(k < T->Element.Key)
      T = T->LChild;
    else
      T = T->RChild;
  }
  
  return NULL;
}

7.1.3 二叉搜索树的插入

1. 代码

bool InsertBST(BSTree &T, Entry e)
{
  BSTNode *p = T, *q, *r; // p 为 e 应插入的位置的结点；q 为 p 双亲结点；r 是用来存放 e 的结点
  KeyType = e.Key;
  
  // 先寻找树中是否已存在与待插入元素一致的元素，并确定待插入的位置
  while(p)
  {
    q = p;
    
    if(k < p->Element.Key)
      p = p->LChild;
    else if(k > p->Element.Key)
      p = p->RChild;
    else
    {
      printf("Duplicate\n");
      return false;
    }
  }
  
  // 创建新的结点 r 用来存放 e
  r = (BSTNode *)malloc(sizeof(BSTNode));
  r->Element = e;
  r->LChild = NULL;
  r->RChild = NULL;
    
  // 将 r 插入 T。若 T 为空树，则 r 即是根结点
  if(!T)
    T = r;
  else if(k < q->Element.Key)
    q->LChild = r;
  else
    q->RChild = r;
  
  return true;
}

7.1.4 二叉搜索树的删除

1. 代码

bool DeleteBST(BSTree &T, KeyType k)
{
  // p 为待删除元素所在的结点；c 用来取代 p，可以为空；s 为中序遍历次序下 p 的直接后继或者直接前驱；q 为 p 双亲结点
  BSTNode *c, *r, *s, *p = T, *q; 
  
  // 搜索待删除元素所在的位置，并用 p 来代表它
  while(p && p->Element.Key!=k)
  {
    q = p;
    if(k < p->Element.Key)
      p = p->LChild;
    else
      p = p->RChild;
  }
  
  // 若搜索不到，返回错误
  if(!p)
  {
    printf("NotPresent\n");
    return false;
  }
  
  if(p->LChild && p->RChild)
  {
    s = p->RChild;
    r = p;
    
    // 搜索 p 的中序直接后继结点 s
    while(s->LChild)
    {
      r = s;
      s = s->Child;
    }
    
    p->Element = s->Element; // 令 c 指示取代 p 的那棵子树
    p = s;
    q = r;
  }
  
  if(p->LChild)
    c = p->LChild;
  else
    c = p->RChild;
  
  // 若被删除的是根结点，则 c 成为新的根；否则结点 c 取代结点 p
  if(p == T)
    T = c;
  else if(p == q->LChild)
    q->LChild = c;
  else
    q->RChild = c;
  
  free(c);
  return true;
}

7.2 二叉平衡树

7.2.1 二叉平衡树的定义

1. **二叉平衡树 (AVL) **是带有平衡条件的二叉搜索树，即具有以下特点：

​ (1) 其根的左、右子树高度之差的绝对值不超过 1；

​ (2) 其根的左、右子树都是二叉平衡树。

7.2.2 二叉平衡树的平衡调整方法

1. 插入的四种类型

​ (1) LL 情形：新元素插入在树 A 的左孩子的左子树上；

​ (2) RR 情形：新元素插入在树 A 的右孩子的右子树上；

​ (3) LR 情形：新元素插入在树 A 的左孩子的右子树上 ；

​ (4) RL 情形：新元素插入在树 A 的右孩子的左子树上。

2. LL 情形对应的右单旋转方法：将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 向右下旋转成为 B 的右子树的根结点，则原 B 的右子树则作为 A 的左子树。

3. RR 情形对应的左单旋转方法：将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 向左下旋转成为 B 的左子树的根结点，则原 B 的左子树则作为 A 的右子树。

4. LR 情形对应的先左后右双旋转方法：先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。

5. RL 情形对应的先右后左双旋转方法：先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。

7.2.3 二叉平衡树的高度

1. 在高度为 h 的平衡二叉树中，最少节点数是

S ( h ) = S ( h − 1 ) + S ( h − 2 ) + 1 S(h) = S(h-1)+S(h-2)+1 S(h)=S(h−1)+S(h−2)+1

2. 时间复杂度为 O(log₂n)

7.3 B-树

7.3.1 B-树的定义

1. 一棵 m 阶 B-树是一棵 m 叉搜索树，它或者为空，或者满足如下性质：

​ ① 根结点至少有两个孩子；

​ ② 除根结点和失败结点外的每个结点至少有 ⌈m/2⌉ 个孩子，即至少含有 ⌈m/2⌉-1 个关键字；

​ ③ 每个结点至多有 m 个孩子，即至多含有 m-1 个关键字；

​ ④ 所有失败结点均在同一层上。

7.3.2 B-树的高度

1. 含有 n 个关键字的 m 阶 B-树的高度 h 为

log m ( n + 1 ) ≤ h ≤ 1 + log ⌈ m / 2 ⌉ n + 1 2 \text{log}_m(n+1)\leq h\leq1+\text{log}_{⌈m/2⌉}\frac{n+1}{2} logm​(n+1)≤h≤1+log⌈m/2⌉​2n+1​

7.3.3 B-树的插入

7.3.4 B-树的删除

1. 若被删除的关键字在非终端结点，则使用直接前驱或者直接后继来代替被删除的关键字

​ (1) 直接前驱：当前关键字左侧指针所指孩子“最右下”元素；

​ (2) 直接后继：当前关键字左侧指针所指孩子“最左下”元素；

第八章 散列表

8.1 散列技术的简介

1. 哈希函数：将关键字值映射到存储位置的函数 h 。
2. 散列地址：关键字值通过散列函数映射得到的散列值。
3. 散列表：通过散列函数建立的存储结构。
4. 冲突：关键字集合中两个不同的关键字值对给定的散列函数具有相同的散列地址的现象。
5. 聚集：散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或者堆积。

8.2 哈希函数

1. 除留余数法
2. 平方取中法
3. 折叠法
4. 数字分析法
5. 哈希函数 H(key) = key % p，p 最好取不大于比哦啊海沧的最大素数或不包含小于20的质因子合数。

8.3 散列冲突处理

8.3.1 拉链法

8.3.2 开地址法

1. 线性探查法
2. 二次探查法：容易产生二次聚集。
3. 双散列法：可以避免二次聚集。

第九章 图

9.1 图的基本概念

9.1.1 图的定义

1. 图 G 是由顶点集合 V 和边集合 E 组成。
2. 无向图一般表示为 G(V, E)，有向图表示为 G<V, E>。
3. 有向图的弧尾指的是射出的顶点，弧头指的是射入的顶点。

9.1.2 图的基本术语

1. 邻接：图中两个顶点之间有边相连。
2. 顶点的度、入度和出度

​ ① 度：顶点 u 的度指与 u 相关联的边的数目；

​ ② 入度：顶点 u 的入度是指有向图中与 u 相关联的弧头个数；

​ ③出度：顶点 u 的出度是指有向图中与 u 相关联的弧尾个数。

3. 路径和路径长度：顶点 x 到 y 的路径指从 x 到 y 连通的边集合，路径长度指边集合中边的数目。路径亦可以解释为有顶点和相邻顶点序偶构成的边所形成的序列。
4. 简单路径和回路：如果一个路径上的所有结点，除起点和终点可以相同外，其它顶点各不相同则称其为简单路径。回路是起点和终点相同的简单路径。
5. 自回路和多重图：自回路指 (u, u) 或者 <u, u>；多重路指两个顶点间存在多条相同的边。
6. 完全图：无向图中，若有 n 个顶点的无向图有最多的边数，即具有 n(n-1)/2 条边，则称该图为无向完全图；有向图中，若有 n 个顶点的有向图有最多的边数，即具有 n(n-1) 条边，则称该图为有向完全图。
7. 子图：图 G 中包含的任意小图。
8. 连通图：无向图中，任意两个顶点都是连通的，就称该无向图为连通图。
9. 连通分量：无向图中极大的连通子图。若无向图是连通的，则其连通分量就是其本身，否则存在多个连通分量。
10. 强连通图：有向图中，任意一对顶点 u 和顶点 v 之间，从 u 到 v 和从 v 到 u 都存在路径，则称该有向图为强连通图。
11. 强连通分量：有向图中的极大强连通子图。
12. 生成树：无向连通图 G 的生成树是一个极小连通子图，它包括图中所有的顶点，含有足以构成一棵树的 n-1 条边。
13. 有向树和生成森林：仅有一个顶点的入度为 0，其余顶点的入度均为 1 的有向图称为有向树。一个有向图 G 的生成森林是图 G 的一个子图，它由若干棵不相交的有向树组成，这些有向树包含图 G 中所有顶点。
14. 权和网：权是指图的每条边上可能标注的数值。若一个图的每条边都被赋予权，则称该图为网。

9.2 图的存储结构

9.2.1 邻接矩阵表示法

1. 定义

typedef int ElemType;
typedef struct mGraph{
  ElemType **a;						// 邻接矩阵
  int n;									// 图的当前顶点数
  int e;									// 图的当前边数
  ElemType noEdge;				// 两顶点间无边时的值
}

2. 操作代码

#define ERROR 0
#define OK 1
#define Overflow 2			// Overflow 代表上溢
#define Underflow 3			// Underflow 代表下溢
#define NotPresent 4		// NotPresent 表示元素不存在
#define Duplicate 5			// Duplicate 表示有重复元素
typedef int Status;

// 邻接矩阵初始化
Status Init(mGraph *mg, int nSize, ElemType noEdgeValue)
{
  int i, j;
  mg->n = nSize;							// 初始化顶点数
  mg->e = 0;									// 初始时没有边
  mg->a = (ElemType**)malloc(nSize *sizeof(ElemType*));		// 生成长度为 n 的一维指针数组
  
  if(!mg->a)
    return ERROR;
  
  for(i=0; i<mg->n; i++)			// 生成动态数组
  {
    mg->a[i] = (ElemType*)malloc(nSize *sizeof(ElemType));
    for(j=0; j<mg->n; j++)
      mg->a[i][j] = mg->noEdge;
    mg->a[i][i] = 0;
  }
  
  return OK;
}

// 撤销
void Destroy(mGraph *mg)
{
  int i;
  for(i=0; i<mg->n; i++)
    free(mg->a[i]);						// 释放 n 个一维数组的存储空间
  free(mg->a);								// 释放一维指针数组的存储空间
}

// 边的搜索
Status Exist(mGraph *mg, int u, int v)
{
  if(u<0 || v<0 || u>mg->n-1 || v>mg->n-1 || u==v || mg->a[u][v]==mg->noEdge)
    return ERROR;
  
  return OK;
}

// 边的插入
Status Insert(mGraph *mg, int u, int v, ElemType w)
{
  if(u<0 || v<0 || u>mg->n-1 || v>mg->n-1 || u==v)
    return ERROR;
  
  if(mg->a[u][v] != mg->noEdge)
    return Duplicate;					// 若插入的边已存在，则返回出错信息
  
  mg->a[u][v] = w;						// 插入新边
  mg->e++;
  return OK;
}

// 边的删除
Status Remove(mGraph *mg, int u, int v)
{
  if(u<0 || v<0 || u>mg->n-1 || v>mg->n-1 || u==v)
    return ERROR;
  
  if(mg->a[u][v] == mg->noEdge)
    return NotPresent;				// 若待删除的边不存在，则返回错误信息
  
  mg->a[u][v] = mg->noEdge;		// 删除边
  mg->e--;
  return OK;
}

9.2.2 邻接表表示法

1. 定义

typedef struct eNode{
  int adjVex;											// 与任意顶点 u 相邻接的顶点
  ElemType w;											// 边的权值
  struct eNode *nextArc;					// 指向下一个边结点
}ENode;

typedef struct lGraph{
  int n;													// 图的当前顶点数
  int e;													// 图的当前边数
  ENode **a;											// 指向一维指针数组
}LGraph;

2. 操作代码

// 初始化
Status Init(LGraph *lg, int nSize)
{
  int i;
  lg->n = nSize;
  lg->e = 0;
  lg->a = (ENode **)malloc(nSize *sizeof(ENode*)); 		// 动态生成长度为 n 的一维指针数组
  
  if(!lg->a)
    return ERROR;
  else
  {
    for(i=0; i<lg->n; i++)
      lg->a[i] = NULL; 						// 将指针数组 a 置空
    return OK;
  }
}

// 撤销
void Destroy(LGraph *lg)
{
  int i;
  ENode *p, *q;
  
  for(i=0; i<lg->n; i++)
  {
    p = lg->a[i];									// 指针 p 指向顶点 i 的单链表的第一个边结点
    q = p;
    
    // 释放顶点 i 的单链表中所有边结点
    while(p)
    {
      p = o->nextArc;
      free(q);
      q = p;
    }
  }
  
  free(lg->a);										// 释放一维指针数组 a 的存储空间
}

// 边的搜索
Status Exist(LGraph *lg, int u, int v)
{
  ENode *p;
  
  if(u<0 || v<0 || u>lg->n-1 || v>lg->n-1 || u==v)
    return ERROR;
  
  p = lg->a[u];										// 指针 p 指向顶点 u 的单链表的第一个边结点
  
  while(p && p->adjVex!=v)
    p=p->nextArc;
  
  if(!p)
    return ERROR;									// 若未找到此边，则返回 ERROR
  else 
    return OK;										// 若找到此边，则返回 OK
}

// 边的插入
Status Insert(LGraph *lg, int u, int v, ElemType)
{
  ENode *p;
  
  if(u<0 || v<0 || u>lg->n-1 || v>lg->n-1 || u==v)
    return ERROR;
  
  if(Exist(lg, u, v))
    return Duplicate;
  
  p = (ENode *)malloc(sizeof(ENode));			// 为新的边结点分配存储空间
  p->adjVex = v;
  p->w = w;
  p->nextArc = lg->a[u];									// 将新的边结点插入单链表的最前面
  lg->a[u] = p;
  lg->e++;
  return OK;
}

// 边的删除
Status Remove(LGraph *lg, int u, int v)
{
  ENode *p, *q;
  
  if(u<0 || v<0 || u>lg->n-1 || v>lg->n-1 || u==v)
    return ERROR;
  
  p = lg->a[u], q = NULL;
  
  
  // 查找待删除边是否存在
  while(p && p->adjVex!=v)
  {
    q = p;
    p = p->nextArc;
  }
  
  if(!p)
    return NotPresent;										// p 为空，待删除边不存在
  
  if(q)
    q->nextArc = p->nextArc;							// 从单链表中删除此边
  else
    lg->a[u] = p->nextArc;
  
  free(p);
  lg->e--;
  return OK;
}

9.3 图的遍历

9.3.1 深度优先遍历（DFS）

1. 深度优先遍历可以用来判断有向图和无向图中是否有回路。
2. 算法实现代码

void DFS(int v, int visited[], LGraph g)
{
  ENode *w;
  printf("%d", v);										// 访问顶点 v
  visited[v] = 1;											// 为顶点 v 打上访问标记
  
  // 遍历 v 的邻接点
  for(w=g.a[v]; w; w=w->nextArc)
    if(!visited[w->adjVex])						// 若 w 未被访问， 则递归调用 DFS
      DFS(w->adjVex, visited, g);
}

void DFSGraph(LGraph g)
{
  int i;
  int *visited = (int)malloc(g.n*sizeof(int));		// 动态生成标记数组 visited
  for(i=0; i<g.n; i++)
    visited[i] = 0;										// 初始化 visited 数组
  
  // 逐一检查每个顶点，若未被访问，则调用 DFS
  for(i=0; i<g.n; i++)
    if(!visited[i])
      DFS(i, visited, g);
  
  free (visited);
}

2. 邻接表下的时间复杂度为 O(|V|+|E|)，邻接矩阵下的时间复杂度为 O(|V|²)。

9.3.2 宽度优先搜索（BFS）

1. 算法实现代码

void BFS(int v, int visited[], LGraph)
{
  ENode *w;
  Queue q;
  create(&q, g.n);										// 初始化队列
  visited[v] = 1;											// 为顶点 v 打上访问标记
  printf("%d", v);										// 访问顶点 v
  EnQueue(&q, v);											// 将顶点 v 放入队列
  
  while(!IsEmpty(&q))
  {
    Front(&q, &v);
    DeQueue(&q);											// 队首顶点出队列
    
    // 遍历 v 的所有邻接点
    for(w=g.a[v]; w; w=w->nextArc)
      if(!visited[w->adjVex])					// 若 w 未被访问，则访问 w 并将其放入队列
      {
        visited[w->adjVex] = 1;
        printf("%d", w->adjVex);
        EnQueue(&q, w->adjVex);
      }
  }
}

2. 邻接表下的时间复杂度为 O(|V|+|E|)，邻接矩阵下的时间复杂度为 O(|V|²)。

9.4 拓扑排序

9.4.1 AOV 网

1. 顶点活动图（AOV 网）：为了反映出整个工程活动之间的这种领先关系，可用一个有向图表示工程，图中的顶点代表活动，图中的有向边代表活动间的领先关系。

9.4.2 AOV 网的拓扑排序

1. 拓扑排序可以用来判断有向图中是否有回路。
2. 若有向图的拓扑排序序列唯一，则可以确定该图。
3. 若一个有向图的邻接矩阵对角线以下均为零，则该图的拓扑有序序列必定存在。
4. 从图中选择一个入度为 0 的顶点并输出它，然后删除此顶点以及其所有出边，接着重复该步骤。
5. 拓扑排序的实现代码

void Degree(int *inDegree, LGraph *g)
{
  int i;
  ENode *p;
  
  for(i=0; i<g->n; i++)
    inDegree[i] = 0;										// 初始化 inDegree 数组
  
  for(i=0; i<g->n; i++)
    for(p=g->a[i]; p; p=p->nextArc)			// 检查以顶点 i 为尾的所有邻接点
      inDegree[p->adjVex]++;						// 将顶点 i 的邻接点 p->adjVex的入度加 1
}

Status TopoSort(int *topo, LGraph *g)
{
  int i, j, k;
  ENode *p;
  Stack s;
  int *inDegree = (int*)malloc(sizeof(int)*g->n);
  Create(&s, g->n);
  Degree(inDegree, g);									// 计算顶点入度
  
  for(i=0; i<g->n; i++)
    if(!inDegree[i])
      Push(&s, i);											// 入度为 0 的顶点进栈
  
  for(i=0; i<g->n; i++)									// 生成拓扑序列
  {
    if(IsEmpty(&s))											// 若堆栈为空，表示图中存在有向回路
      return ERROR;
    else
    {
      Top(&s, &j);											// 顶点出栈
      Pop(&s);
      topo[i] = j;											// 将顶点 j 输出到拓扑序列中
      printf("%d", j);
      
      for(p=g->a[j]; p; p=p->nextArc)		// 检查以顶点 j 为尾的所有邻接点
      {
        k = p->adjVex;
        inDegree[k]--;
        
        if(!inDegree[k])								// 若顶点 k 的入度为 0，则进栈
          Push(&s, k);
      }
    }
  }
}

4. 采用邻接表存储拓扑排序的时间复杂度为 O(|V|+|E|)，采用邻接矩阵存储拓扑排序的时间复杂度为 O(|V|²)。

9.5 关键路径

1. 定义：关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。
2. 求关键路径使用的是 AOE 网。
3. 具体如何操作看王道课程
4. Eearly 函数代码

void Eearly(int *eearly, int *topo, LGraph)
{
  int i,k;
  ENode *p;
  
  for(i=0; i<g.n; i++)													// 初始化数组 eearly
    eearly[i] = 0;
  
  for(i=0; i<g.n; i++)
  {
    k = topo[i];																// 取得拓扑序列中的顶点符号
    for(p=g.a[k]; p; p->nextArc)
      if(eearly[p->adjVex] < eearly[k]+p->w)		// 更新 eearly[k]
        eearly[p->adjVex] = eearly+p->w;
  }
}

3. Elate 函数代码

void Elate(int *elate, int *topo, int longest, LGraph g)
{
  int i, j;
  ENode *p;
  
  for(i=0; i<g.n; i++)													// 初始化数组 elate
    elate[i] = longest;
  
  for(i=g.n-2; i>-1; i--)												// 按逆拓扑次序计算 elate 值
  {
    j = topo[i];
    for(p=g.a[j]; p; p=p->nextArc)
      if(elate[j] > elate[p->adjVex]-p>w)				// 更新 elate[k]
        elate[j] = elate[p->adjVex]-p>w
  }
}

9.6 最小生成树

9.6.1 普利姆算法（Prim 算法）

1. 算法过程

​ ① 从一个顶点出发选择与其相关联的权值最小的边

​ ② 从现有的顶点出发选择与其相关联的权值最小的边，注意顶点不能重复

​ ③ 重复执行 ②，直至所有顶点都被关联

2. 算法实现代码

Status Prim(int k, int *closeVex, ElemType *lowWeight, LGraph g)
{
  ENode *p;
  int i, j;
  ElemType min;
  int *isMark = (int *)malloc(sizeof(int)*g.n);			// 动态生成数组 isMark
  
  if(k<0 || k>g.n; i++)
    return ERROR;
  
  for(i=0; i<g.n; i++)															// 初始化
  {
    closeVex[i] = -1;				// closeVex 数组中存放与 v 距离最近的顶点编号 u
    lowWeight[i] = INFTY;		// lowWeight 数组中存放 (closeVex[v], v) 的权值
    isMark[i] = 0;					// isMArk 数组用于标记顶点 v 是否在生成树中
  }
  
  lowWeight[k] = 0; closeVex[k] = k; isMark[k] = 1;	//源点加入生成树 
  
  for(i=1; i<g.n; i++)
  {
    for(p=g.a[k]; p; p=p->nextArc)
    {
      j = p->adjVex;
      
      if((!isMark[j]) && (lowWeight[j]>p->w))				// 更新生成树外顶点的 lowWeight 值
      {
        lowWeight[j] = p->w;
        closeVex[j] = k;
      }
    }
    
    min = INFTY;
    
    for(j=0; j<g.n; j++)										// 找生成树外顶点中，具有最小 lowWeight 值的顶点 k
      if((!isMark[j]) && (lowWeight[j]<min))
      {
        min = lowWeight[j];
        k=j;
      }
    isMark[k] = 1;																	// 将顶点 k 加到生成树上
  }
  
  for(i=0; i<g.n; i++)
  {
    printf("%d", closeVex[i]);
    printf("%d", i);
    printf("%d", lowWeight[i]);
    printf("\n");
  }
  
  return OK;
}

3. 普利姆算法的时间复杂度为 O(|V²|)。

9.6.3 克鲁斯卡尔算法（KruSkal 算法）

1. 算法过程：

​ ① 画出所有的顶点

​ ② 将最小边连入顶点，注意顶点不能重复

​ ③ 重复执行 ②，直至所有顶点都关联

2. 算法实现代码

typedef struct edge
{
  int u;
  int v;
  ElemType w;
}Edge;

// 对图中的边按权值递增排序
void SelectSort(Edge *eg, int n) 					
{
  int small, i, j;
  Edge t;
  
  for(i=0; i<n-1; i++)						// 执行 n-1 趟
  {
    small = i;										// 先假定待排序序列中就一个元素为最小
    
    for(j=i+1; j<n; j++)
      if(eg[j].w < eg[small].w)
        small = j;								// 如果扫描到一个比最小值元素还小的元素，则记下其下标
    
    t = eg[i];										// 最小元素与待排序序列中第一个元素交换
    eg[i] = eg[small];
    eg[small] = t;
  }
}

void Kruskal(mGrapg g)
{
  int i, j, k, u1, v1, vs1, vs2;
  /*
  	vexSet 数组用于标识个顶点所属的连通分量
  	若两个顶点属于不同的连通分量，则将这两个顶点关联的边加到生成树中时不会形成回路。
  */
  int *vexSet = (int *)malloc(sizeof(int)*g.n);
  Edfe *edgeSet = (Edge*)malloc(sizeof(Edge)*g.e);
  k = 0;
  
  for(i=0; i<g.n; i++)						// 由邻接矩阵产生边集数组
    for(j=0; j<i; j++)
      if(g.a[i][j]!=0 && g.a[i][j]!=g.noEdge)
      {
        edgeSet[k].u = i;
        edgeSet[k].v = j;
        edgeSet[k].w = g.a[i][j];
        k++;
      }
  SelectSort(edgeSet, g.e/2);			// 对边集数组排序
  
  for(i=0; i<g.n; i++)
    vexSet[i] = i;
  
  k = 0;
  j = 0;
  
  while(k < g.n-1)								// 加入 n-1 条 边
  {
    u1 = edgeSet[j].u;
    v1 = edgeSet[j].u;
    vs1 = vexSet[u1];
    vs2 = vexSet[v1];
    
    if(vs1 != vs2)								// 若 vs1 和 vs2 不相等，表示 u 和 v 属于不同的连通分量
    {
      printf("%d, %d, %d\n", edgeSet[j].u, edgeSet[j].v, edgeSet[j].w);		// 输出边
      k++;												// 边数加 1
      for(i=0; i<g.n; i++)				// 合并 u 和 v 所属的不同连通分量
        if(vexSet[i] == vs2)
          vexSet[i] = vs1;
    }
    
    j++;
  }
}

3. 克鲁斯卡尔的时间复杂度为 O(|E|log₂|E|)。

9.7 单源最短路径（迪杰斯特拉算法）

1. 迪杰斯特拉算法（Dijkstra 算法）代码

// 选出最小的 d[i], i∈V-S
int Choose(int *d, int *s, int n)
{
  int i, minpos;
  ElemType min;
  min = INFTY;
  minpos = -1;
  
  for(i=0; i<n; i++)
    if(d[i]<min && !s[i])
    {
      min = d[i];
      minpos = i;
    }
  
  return minpos;						// 返回下标位置
}

Status Dijkstra(int v, ElemType *d, int *path, mGraph g)
{
  int i, k, w;
  int *s;
  
  if(v<0 || v>g.n-1)
    return ERROR;
  
  s = (int *)malloc(sizeof(int)*g.n);
  
  for(i=0; i<g.n; i++)
  {
    s[i] = 0;									// 初始化
    d[i] = g.a[v][i];
    
    if(i!=v && d[i]<INFTY) 
      path[i] = v;
    else
      path[i] = i;
  }
  
  s[v] = 1; d[v] = 0;					// 顶点 v 为源点
  
  for(i=1; i<g.n-1; i++)
  {
    k = Choose(d, s, g.n);
    
    if(k == -1)
      continue;
    
    s[k] = 1;									// k 加入 s
    printf("%d", k);
    
    // 更新 d 和 path
    for(w=0; w<g.n; w++)
      if(!s[w] && d[k]+g.a[k][w]<d[w])
      {
        d[w] = d[k] + g.a[k][w];
        path[w] = k;
      }
  }
  
  for(i=0; i<g.n; i++)
    printf("%d", d[i]);
  
  return OK;
}

2. 当边上的权值为负数时，迪杰斯特拉算法不再适用。
3. 迪杰斯特拉算法的时间复杂度为 O(n²)。

9.8 所有顶点之间的最短路径（弗洛伊德算法）

1. 弗洛伊德算法（Floyd 算法）代码

void Floyd(mGraph g)
{
  int i, j, k;
  ElemType **d = (ElemType **)malloc(g.n*sizeof(ElemType *));
  int **p = (int **)malloc(g.n*sizeof(int *));
  
  // 动态生成二维数组空间
  for(i=0; i<g.n; i++)
  {
    d[i] = (Elemtype *)malloc(g.n*sizeof(ElemType));
    p[i] = (int *)malloc(g.n*sizeof(int));
    
    for(j=0; j<g.n; j++)
    {
      d[i][j] = g.noEdge;
      p[i][j] = 0;
    }
  }
  
  for(i=0; i<g.n; i++)
    // 初始化 d 和 p
    for(j=0; j<g.n; j++)
    {
      d[i][j] = g.a[i][j];
      if(i!=j && g.a[i][j]<INFTY)
        p[i][j] = i;
      else p[i][j] = -1;
    }
  
  for(k=0; k<g.n; k++)
    for(i=0; i<g.n; i++)
      for(j=0; i<g.n; j++)
        // 更新 d 和 p
        if(d[i][k] + d[k][j] < d[i][j])
        {
          d[i][j] = d[i][k] + d[k][j];
          p[i][j] = p[k][j];
        }
  
  for(i=0; i<g.n; i++)
  {
    for(j=0; j<g.n; j++)
      printf("%d", d[i][j]);
    printf("\n");
  }
}

2. 弗洛伊德算法允许图中有带负权值的边，但是不允许有包括带负权值的边组成回路。
3. 弗洛伊德算法的时间复杂度为 O(n³)。

第十章 排序

10.1 排序的基本概念

1. 稳定性：待排序列中两个数据 D_i = D_j，若在原序列中 D_i 的位置在 D_j 的前面，且在排序之后 D_i 的位置仍在 D_j 的前面，则称该排序过程是稳定的。否则称该排序过程是不稳定的。
2. 排序趟数：内排序算法核心过程都是循环执行一组运算，从最初无序状态到局部有序状态，最终到达数据元素完全有序状态。这一组不断被重复执行的操作，就被称为排序算法的一趟排序过程。
3. 该张所用到的顺序存储的实现

// 数据元素存储结构
typedef struct entry{
  KeyType key;						// 排序关键字
  DataType data;					// data 中包含数据元素中的其他数据项
}Entry;

// 顺序存储结构
typedef struct list{
  int n;									// 元素个数
  Entry D[MaxSize];				// 静态数组存储数据元素
}List;

10.2 插入排序

10.2.1 直接插入排序

1. 核心思想：从只包含一个数据元素的有序序列开始，不断地将待排序数据元素有序地插入这个有序序列中，知道有序序列包含所有待排序数据元素为止。
2. 算法代码

void InsertSort(List *list)
{
  int i, j; 											// 为待插入元素下标
  Entry insertItem; 							// 每一趟待插入元素
  
  for(i=1; i<list->n; i++)
  {
    insertItem = list->D[i];
    
    for(j=i-1; j>=0; j--)
    {
      // 不断将有序序列中元素向后移动，为待插入元素空出一个位置
      if(insertItem.key < list->D[j].key)
        list->D[j+1] = list->D[j];
      else break;
    }
    
    list->D[j+1] = insertItem;		// 待插入元素有序存放至有序序列中
  }
}

3. 稳定性：稳定。
4. 排序趟数：n-1。
5. 时间复杂度：最好情况下是 O(n)，最坏和平均情况下是 O(n²)。
6. 空间复杂度：O(1)。
7. 平均比较次数：O(n²)。
8. 当文件“局部有序”或者文件长度较小的情况下，该方法是最佳的内部排序方法。

10.2.2 希尔排序

1. 核心思想：将待排序列分成若干个相距一定步长的子表（比如 49，38，65，97，76，13，就可以取 [49, 97], [38, 76], [65, 13] 作为子表），然后对若干个子表进行直接插入排序，形成若干个相对有序的子表，然后再对全体记录进行一次直接插入排序。
2. 算法代码

void ShellSort(List *list)
{
  int dk, i, j;
  int temp;
  
  for(dk=list.n/2; dk>=1; dk=dk/2)								// 增量变化
    for(i=dk; i<=list.n; ++i)
      if(list.D[i] < list.D[i-dk])								// 需将 list.D[i] 插入有序增量子表
      {
        temp = list.D[i];													// 暂存在 temp 中
        
        for(j=i-dk; j>=0&&temp<list.D[j]; j-=dk)
          list.D[j+dk] = list.D[j];								// 记录后移，查找插入位置
        
        list.D[j+dk] = temp;											// 插入
      }
}

3. 稳定性：不稳定。
4. 时间复杂度：O(n²)。
5. 空间复杂度：O(1)。

10.3 交换排序

10.3.1 冒泡排序

1. 核心思想：从前向后不断交换相邻逆序数据元素，直至完成排序。

2. 算法代码

typedef int BOOL;

void BubbleSort(List *list)
{
  int i, j; 								// i 标识每趟排序范围最后一个元素的下标，每趟排序元素下标范围是 0 ~ i
  
  for(i=list->n-1; i>0; i--)
  {
    BOOL isSwap = FALSE; 		// 标记一趟排序中是否发生了元素交换
    
    for(j=0; j<i; j++)
    {
      if(list->D[j].key > list->D[j+1].key)
      {
        Swap(list->D, j, j+1);
        isSwap = TRUE;
      }
    }
    
    if(!isSwap) break;			// 如果本趟排序没有发生元素交换，排序完成 
  }
}

3. 稳定性：稳定。
4. 排序趟数：n-1，与序列初始状态有关。
5. 时间复杂度：最好情况下是 O(n)，最坏和平均情况下是 O(n²)。
6. 空间复杂度：O(1)。

10.3.2 快速排序算法

1. 核心思想：在待排序序列中选择一个分割元素，将待排序元素所有比分割元素关键字小或者相等的放到其左边，比分割元素关键字大的放到其右边。这样就将一个待排序列分成两个待排序列，此时，分割元素的位置已经确定。将两个待排序列分别重复进行该操作。
2. 算法代码

// 序列划分
int Partition(List *list, int low, int high)
{
  int i = low, j = high + 1;
  Entry pivot = list->D[low]; 										// pivot 是分割元素
  
  do {
    do i++; 
    while(i<=high && list->D[i].key<pivot.key); 	// i 前进 
    do j--; 
    while(list->D[j].key > pivot.key); 						// j 前进
    if(i < j)
      Swap(list->D, i, j);
  }while(i < j);
  
  Swap(list->D, low, j);
  return j; 																			// 此时 j 是分割元素下标
}

// 快排的递归函数
void QuickSort(List *list, int low, int high)
{
  int k;
  
  if(low < high)  // 当前快排序列至少包含两个元素
  {
    k = Partition(list, low, high);
    QuickSort(list, low, k-1);
    QuickSort(list, k+1, high);
  }
}

// 快排的主调用函数
void QuickSort(List *list)
{
  QuickSort(list, 0, list->n-1);
}

3. 稳定性：不稳定。

4. 排序趟数：最差情况下，每次划分都只产生一个子序列，此时排序趟数为 n-1；最好情况下每次划分都将序列划分成等长的两个子序列，此时排序趟数满足：
   Q(n) = Q(⌊ n-1 2 ⌋) + Q(⌈ n-1 2 ⌉) + 1 \text{Q(n)}=\text{Q(⌊}\frac{\text{n-1}}{2}\text{⌋)}+\text{Q(⌈}\frac{\text{n-1}}{2}\text{⌉)}+1 Q(n)=Q(⌊2n-1​⌋)+Q(⌈2n-1​⌉)+1
   此时 Q(0) = Q(1) =0.

   与序列初始状态有关。

5. 时间复杂度：最好和平均情况下是 O(nlog₂n)，最坏情况下是 O(n²)。当待排序列已经有序的情况下，花费时间较多。

6. 空间复杂度：最好与平均情况下是 O(log₂n)，最坏情况下是 O(n)。

7. 平均比较次数：O(nlog₂n)。

8. 在分割元素刚好是能将序列分成两个等长的序列时，快排达到最快的情况。同时，当待排序列基本有序时快排就变得很慢。

10.4 选择排序

10.4.1 简单选择排序

1. 核心思想：每一趟排序中，选择关键字最小的数据元素，并将其与待排序序列中第一个元素交换位置，然后将其从下一趟待排序序列中移出。重复该过程。
2. 算法代码

// 交换元素位置
void Swap(Entry *D, int i, int j)
{
  Entry temp;
  
  if(i == j) return;
  temp = *(D + i);
  *(D + i) = *(D + j);
  *(D + j) = temp;
}

void SelectSort(List *list)
{
  int minIndex, 														// minIndex 是最小元素的位置，
  int startIndex = 0; 											// startIndex 是用于将排好的元素移出待排序序列
  
  while(startIndex < list->n-1)
  {
    // 找出最小元素
    for(int i = startIndex+1; i<list.n; i++){
      if(list.D[i].key <list.D[minIndex].key)
        minIndex = i;
    }
    
    swap(list->D, startIndex, minIndex);    // 交换元素位置
    startIndex++;	
  }
}

3. 稳定性：不稳定。
4. 排序趟数：n-1。
5. 时间复杂度：O(n²)，与初始状态无关。
6. 空间复杂度：O(1)。
7. 该方法比较次数与初始状态无关。

10.4.2 堆排序算法

1. 核心思想：借助堆数据结构，不断输出当前堆顶元素，当堆顶元素离开堆后，重新将剩余元素调整成堆。一般用最大堆数据结构。
2. 算法代码

// 定义最大堆结构体
typedef struct maxheap{
  int n, MaxSize;
  Entry D[MaxSize];
}MaxHeap;

void HeapSort(MaxHeap *hp)
{
  int i; Enrty temp;
  
  for(i=hp->(n-2)/2; i>=0; i--)
    AdjustDown(hp->D, i, hp->n-1);
  
  for(i=hp->n-1; i>0; i--) 			// i 指向当前堆的堆底元素
  {
    Swap(heap->D, 0, i);				// 交换堆底与堆顶元素
    AdjustDown(hp->D, -, i-1);
  }
}

3. 稳定性：不稳定。
4. 排序趟数：n-1。
5. 时间复杂度：O(nlog₂n)。
6. 空间复杂度：O(1)。

10.5 两路合并排序算法

1. 核心思想：一开始将 n 个数据元素看作 n 个待合并有序序列，每个序列只包含一个数据元素；将每两个待合并序列合并成一个大的有序序列。重复合并过程，直到所有数据元素都属于同一个有序序列为止。

2. 算法代码

// 序列两路合并
// n1 和 n2 是两个子序列长度，low 是第一个子序列第一个元素下标
void Merge(List *list, Entry *temp, int low, int n1, int n2)
{
  int i = low, j = low + n1; 		// i，j 初始时分别指向两个序列的第一个元素
  
  while(i<=low+n1-1 && j<=low+n1+n2-1)
  {
    if(lisy->D[i].key <= list->D[j].key)
      *temp++ = list->D[i++];
    else
      *temp++ = list->D[j++];
  }
  
  while(i<=low+n1-1)
    *temp++ = list->D[i++]; 		// 剩余元素直接复制到 temp 
  while(j<=low+n1+n2-1)
    *temp++ = list->D[j++]; 		// 剩余元素直接复制到 temp 
}

// 两路合并排序
void MergeSort(List *list)
{
  Entry temp[MaxSize];
  int low, n1, n2, i, size = 1;
  
  while(size < list->n)
  {
    low = 0;										// low 是一堆待合并序列中第一个序列的第一个元素下标
    
    while(low + size < list->n)	// low + size < list->n 说明至少存在两个子序列需要合并
    {
      n1 = size;
      if(low+size*2 < list->n)
        n2 = size;							// 计算第二个序列长度
      else
        n2 = list->n-low-size;
      
      Merge(list, temp+low, low, n1, n2);
      low += n1 + n2; 					// 确定下一对待合并序列中第一个序列的第一个元素下标
    }
    
    for(i=0; i<low; i++)
      list->D[i] = temp[i]; 		// 复制一趟合并排序结果
    size *= 2;									// 子序列长度翻倍
  }
}

3. 稳定性：稳定。
4. 排序趟数：⌈log₂n⌉。
5. 时间复杂度：O(nlog₂n)。
6. 空间复杂度：O(n)。
7. 平均比较次数：O(nlog₂n)。
8. 该方法比较次数与初始状态无关。

10.6 基数排序

1. 核心思想：看王道，这玩意儿真神奇。
2. 稳定性：稳定。
3. 时间复杂度：O(d(n+r))。r 是队列数。
4. 空间复杂度：O®。

标签：结点,return,复习,int,ElemType,元素,期末,二叉树,数据结构
From： https://blog.csdn.net/weixin_46545179/article/details/145169235