数据结构【软考】-技术轨迹

文章目录

一、线性结构
- 1. 线性表
- （1）线性表的定义
- （2）线性表的存储结构
2. 栈和队列
- （1）栈
- ① 定义
- ② 栈的存储结构
- ③ 栈的基本运算
- （2）队列
- ① 定义
- ② 队列的存储结构
- ③ 队列的基本运算
3. 串（字符串）
- （1）串的定义及基本运算
- （2）串的存储结构
- （3）串的模式匹配
二、数组、矩阵和广义表
- 1. 数组
- （1）数组的定义及基本运算
- （2）数组的顺序存储
2. 矩阵
- （1）特殊矩阵
- （2）稀疏矩阵
3. 广义表
- （1）广义表的基本操作
- （2）广义表的特点
- （3）广义表的存储结构
三、树
- 1. 树与二叉树的定义
- （1）树的定义
- （2）树的基本概念
- （3）二叉树的定义
2. 二叉树的性质与存储结构
- （1）二叉树的性质
- （2）二叉树的存储结构
3. 二叉树的遍历
4. 线索二叉树
- （1）线索二叉树的定义
- （2）建立线索二叉树
5. 最优二叉树
- （1）最优二叉树
- （2）哈夫曼编码
6. 树和森林
- （1）树的存储结构
- （2）树和森林的遍历
- - ① 树的遍历
- ② 森林的遍历
- （3）树、森林和二叉树之间的相互转换
四、图
- 1. 图的定义与存储
- （1）图的定义
- （2）图的存储结构
分段函数
- 2. 图的遍历
- （1）深度优先搜索（Depth First Search，DFS）
- （2）广度优先搜索（Breadth First Search，BFS）
3. 生成树及最小生成树
- （1）生成树的概念
- （2）最小生成树
- - ① 普里姆（Prim）算法
- ② 克鲁斯卡尔（Kruskal）算法
4. 拓扑排序和关键路径
- （1）AOV网（Activity On Vertex network）
- （2）拓扑排序及其算法
- （3）AOE网（Activity On Edge network）
- （4）关键路径和关键活动
5. 最短路径
- （1）单源点最短路径
- （2）每对顶点间的最短路径
- （3）迪杰斯特拉算法（Dijkstra）和弗洛伊德算法（Floyd）
五、查找
- 1. 查找的基本概念
- （1）基本概念
- （2）平均查找长度
2. 静态查找表的查找方法
- （1）顺序查找（Sequential Search）
- （2）折半查找（Binary Search）
- （3）分块查找（Block Search）
3. 动态查找表
- （1）二叉排序树（Binary Sort Tree）
- （2）平衡二叉树（Balanced Binary Search Tree）
- （3）B- 树和 B+ 树
4. 哈希表（Hashing）
六、排序
- 1. 排序的基本概念
2. 简单排序
- （1）插入排序（Insertion Sort）
- （2）冒泡排序（Bubble Sort）
- （3）选择排序（Selection Sort）
3. 快速排序（Quick Sort）
4. 希尔排序（Shell Sort）
5. 堆排序（Heap Sort）
6. 归并排序（Merge Sort）
7. 基数排序（Radix Sort）
8. 外部排序

数据结构：指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为存储结构（或物理结构）。按照逻辑关系的不同分为：线性结构和非线性结构【又可分为：树结构和图】两大类。算法与数据结构密切相关，数据结构是算法设计的基础，是程序设计的重要基础，设计合理的数据结构可使算法简单而高效。

一、线性结构

是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述，特点：数据元素之间呈现一种线性关系，即元素“一个接一个排列”。

1. 线性表

最简单、最基本、最常用的一种线性结构，常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。
在这里插入图片描述

（1）线性表的定义

一个线性表是个元素的有限序列，通常表示为 $a_1，a_2，…，a_n）$ ，非空线性表的特点：

存在唯一的一个称作 “第一个” 的元素
存在唯一的一个称作 “最后一个” 的元素
除第一个元素外，序列中的每个元素均只有一个直接前驱
除最后一个元素外，序列中的每个元素均只有一个直接后继

（2）线性表的存储结构

线性表的顺序存储
线性表的顺序存储：指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，在这种存储方式下，元素间的逻辑关系无须占用额外的空间来存储。
线性表采用顺序存储结构的，优点【可以随机存取表中的元素，查询操作较为方便】，缺点【插入和删除操作需要移动元素】。
线性表的链式存储
线性表的链式存储是用通过指针链接起来的结点来存储数据元素，基本的结点结构如下：

其中，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继的位置信息，指针域中的信息称为指针（或链）。存储各数据元素的结点的地址并不要求是连续的，存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请，无须事先分配。结点之间通过指针域构成一个链表，若结点中只有一个指针域，则称为线性链表（或单链表）。
设线性表中的元素是整型，则单链表结点类型的定义为：

typedef struct node { int data; /* 结点的数据域，此处假设为整型 */ struct node *next; /* 结点的指针域 */ } NODE, *LinkList;

在链式存储结构中，只需要一个指针（称为头指针，head）指向第一个结点，就可以顺序地访问到表中的任意一个元素，在链式存储结构下进行插入和删除，其实质都是对相关指针的修改，优点【易于插入和删除，内存利用率高】，缺点【链表中的元素或节点遍历很困难，访问元素的效率低】

2. 栈和队列

栈和队列是程序中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算有所限制：栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称为运算受限的线性表。

① 定义

只能通过访问它的一端来实现数据存储和检索的一种线性数据结构，栈的修改是按先进后出的原则进行的，栈又称为后进先出（Last In First Out，LIFO）的线性表。在栈中进行插入和删除操作的一端称为栈顶（Top），相应地，另一端称为栈底（Bottom），不含数据元素的栈称为空栈。

② 栈的存储结构

顺序存储
指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈顶元素的位置，采用顺序存储结构的栈也称为顺序栈。在这种存储方式下，需要预先定义（或申请）栈的存储空间，栈空间的容量是有限的。在顺序栈中，当一个元素入栈时，需要判断是否栈满（栈空间中没有空闲单元），若栈满，则元素不能入栈。
栈的链式存储
用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。
栈的应用
栈的典型应用包括：表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。

③ 栈的基本运算

初始化栈【InitStack（S）】：创建一个空栈 S。
判栈空【isEmpty（S）】：当栈 S 为空时返回“真”，否则返回“假”。
入栈【Push（S，x）】：将元素 x 加入栈顶，并更新栈顶指针。
出栈【Pop（S）】：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将 Pop（S）定义为一个返回栈顶元素值的函数。
读栈顶元素【Top（S）】：返回栈顶元素的值，但不修改栈顶指针。

// C 语言版 // 1. 定义链式存储栈的结点结构体： typedef struct Node { int data; // 存储元素的数据域 struct Node* next; // 指向下一个结点的指针域 } Node; // 2. 初始化栈： typedef struct { Node* top; // 栈顶指针 } Stack; void initStack(Stack* s) { s->top = NULL; // 初始化栈顶指针为空 } // 3. 判断栈是否为空： int isEmpty(Stack* s) { return (s->top == NULL); // 栈顶指针为NULL表示栈为空 } // 4. 入栈操作 void push(Stack* s, int item) { Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新结点 newNode->data = item; // 设置结点的数据域为要入栈的元素 newNode->next = s->top; // 新结点指向原栈顶结点 s->top = newNode; // 更新栈顶指针 } // 5. 出栈操作 int pop(Stack* s) { if (isEmpty(s)) { printf("Stack Underflow\n"); // 栈已空，无法出栈 return -1; } Node* temp = s->top; // 保存栈顶结点的指针 int item = temp->data; // 获取栈顶元素的值 s->top = s->top->next; // 更新栈顶指针 free(temp); // 释放原栈顶结点的内存空间 return item; // 返回栈顶元素的值 } // 6. 获取栈顶元素： int top(Stack* s) { if (isEmpty(s)) { printf("Stack is Empty\n"); // 栈已空，无栈顶元素 return -1; } return s->top->data; // 返回栈顶结点的数据域的值 }

// C++ 版：可以使用STL（标准模板库）中的 std::stack 类来实现栈的基本运算 // 1. 头文件引入： #include <stack> // 2. 定义栈对象： std::stack<int> s; // 创建一个整型的栈对象 // 3. 入栈操作：使用 push() 函数将元素加入到栈中。 s.push(X); // 将元素 X 入栈 // 4. 出栈操作：使用 pop() 函数从栈中移除栈顶元素。 s.pop(); // 移除栈顶元素 // 5. 获取栈顶元素：使用 top() 函数返回栈顶元素的值。 int topElement = s.top(); // 获取栈顶元素的值，不移除 // 6. 判断栈是否为空：使用 empty() 函数判断栈是否为空，返回值为布尔类型。 if (s.empty()) { // 栈为空 } else { // 栈不为空 } // 7. 获取栈的大小：使用 size() 函数返回栈的元素个数。 int stackSize = s.size(); // 获取栈中元素的个数

① 定义

一种先进先出（First In First Out，FIFO）的线性表，只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。

② 队列的存储结构

队列的顺序存储
又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队头和队尾。
循环队列
在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的存储空间容量是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。若将顺序队列假想成一个环状结构（通过整除取余运算实现），则可维持入队、出队操作运算的简单性，称之为循环队列。
队列的链式存储
也称为链队列为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。
队列的应用
队列结构常用于处理需要排队的场合，如：操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

③ 队列的基本运算

初始化队列【InitQueue（Q）】：创建一个空的队列Q。
判队空【isEmpty（Q）】：当队列为空时返回“真”，否则返回“假”。
入队【EnQueue（Q，x）】：将元素 x 加入到队列 Q 的队尾，并更新队尾指针。
出队【DelQueue（Q）】：将队头元素从队列 Q 中删除，并更新队头指针。
读队头元素【FrontQue（Q）】：返回队头元素的值，但不更新队头指针。

// C语言版 // 1. 定义链式存储栈的结点结构体： typedef struct Node { int data; struct Node* next; } Node; // 2. 定义队列结构体 typedef struct { Node* front; // 队头指针 Node* rear; // 队尾指针 } Queue; // 2. 初始化队列 void initQueue(Queue* Q) { Q->front = NULL; Q->rear = NULL; } // 3. 判断队列是否为空 int isEmpty(Queue Q) { return Q.front == NULL; } // 4. 入队操作 void enQueue(Queue* Q, int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); return; } newNode->data = data; newNode->next = NULL; if (isEmpty(*Q)) { Q->front = newNode; Q->rear = newNode; } else { Q->rear->next = newNode; Q->rear = newNode; } } // 5. 出队操作 int deQueue(Queue* Q) { if (isEmpty(*Q)) { printf("队列为空，无法出队！\n"); return -1; } int data; Node* temp = Q->front; data = temp->data; Q->front = Q->front->next; free(temp); if (Q->front == NULL) { Q->rear = NULL; } return data; } // 6. 遍历队列 void traverseQueue(Queue Q) { printf("队列中的元素为："); Node* current = Q.front; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); } // 7. 清空队列 void clearQueue(Queue* Q) { while (!isEmpty(*Q)) { deQueue(Q); } } // 8. 销毁队列 void destroyQueue(Queue* Q) { clearQueue(Q); Q->front = NULL; Q->rear = NULL; }

// C++ 版：可以使用STL（标准模板库）中的 std::queue 类来实现栈的基本运算 // 1. 头文件引入： #include <queue> // 2. 定义队列对象： std::queue<int> myQueue; // 3. 入队（enqueue）：将元素添加到队列的末尾。 myQueue.push(element); // 4. 出队（dequeue）：从队列的头部移除并返回元素。 myQueue.pop(); // 5. 访问队头元素（front）：获取队列的头部元素，但不移除。 element = myQueue.front(); // 6. 访问队尾元素（back）：获取队列的末尾元素，但不移除。 element = myQueue.back(); // 7. 判断队列是否为空（empty）：检查队列是否为空，返回布尔值。 if (myQueue.empty()) { // 队列为空 } else { // 队列非空 } // 8. 获取队列大小（size）：返回队列中元素的个数。 int size = myQueue.size();

3. 串（字符串）

是一种特殊的线性表，其数据元素为字符。计算机中非数值问题处理的对象经常是字符串数据。串具有自身的特性，运算时常常把一个串作为一个整体来处理。

（1）串的定义及基本运算

定义
是仅由字符构成的有限序列，是一种线性表。一般记为 $S='a_1a_2…a_n'$ 其中，S 是串名，单引号括起来的字符序列是串值。
串的基本概念
空串：长度为零的串称为空串，空串不包含任何字符。
空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。
子串：由串中任意长度的连续字符构成的序列称为子串,含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
串相等：指两个串长度相等且对应序号的字符也相同。
串比较：两个串比较大小时以字符的 ASCⅡ 码值（或其他字符编码集合）作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
串的基本操作
赋值操作【StrAssign（s，t）】：将串s的值赋给串t。
连接操作【Concat（s，t）】：将串 t 接续在串 s 的尾部，形成一个新串。
求串长【StrLength（s）】：返回串 s 的长度。
串比较【StrCompare（s，t）】：比较两个串的大小，返回值 -1、0和1 分别表示。
求子串【SubString（s，start，len）】：返回串s中从start开始的、长度为len的字符序列。

// 不同语言有不同内置函数对串进行操作，以 C 语言为例 // 1. 赋值操作（不用内置函数操作） void StrAssign(char s[], const char t[]) { int i = 0; while (t[i] != '\0') { s[i] = t[i]; i++; } s[i] = '\0'; // 在末尾添加字符串结束符 } // 2. 连接操作（不用内置函数操作） void Concat(char result[], const char s[], const char t[]) { int i = 0, j = 0; while (s[i] != '\0') { result[j] = s[i]; i++; j++; } i = 0; while (t[i] != '\0') { result[j] = t[i]; i++; j++; } result[j] = '\0'; // 在末尾添加字符串结束符 } // 3. 求串长（不用内置函数操作） int StrLength(const char s[]) { int length = 0; while (s[length] != '\0') { length++; } return length; } // 4. 串比较（不用内置函数操作） int StrCompare(const char s[], const char t[]) { int i = 0; while (s[i] == t[i]) { if (s[i] == '\0') { return 0; // 两个串相等 } i++; } return (int)(s[i] - t[i]); // 返回差值 } // 5. 求子串（不用内置函数操作） void SubString(const char s[], int start, int len, char sub[]) { int i = start, j = 0; while (s[i] != '\0' && j < len) { sub[j] = s[i]; i++; j++; } sub[j] = '\0'; // 在末尾添加字符串结束符 }

（2）串的存储结构

顺序存储结构
指用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。
链式存储
当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。在链式存储结构中，结点大小的选择会直接影响对串的处理效率。

（3）串的模式匹配

称为模式串，子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一也。

二、数组、矩阵和广义表

数组与广义表可看作是线性表的推广，其特点是数据元素仍然是一个表。

1. 数组

（1）数组的定义及基本运算

定义
定长线性表在维数上的扩展，即线性表中的元素又是一个线性表。n 维数组是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱，就单个关系而言，它仍是线性的。
二维数组，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
数组结构的特点
数据元素具有相同的类型。
数据元素的下标关系具有上下界的约束且下标有序。
数据元素数目固定，一旦定义了一个数组结构，就不再有元素个数的增减变化。
数组的两个基本运算
给定一组下标，存取相应的数据元素。
给定一组下标，修改相应的数据元素中某个数据项的值。

（2）数组的顺序存储

数组一般不做插入和删除运算，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
二维数组的存储结构可分为以行为主序和以列为主序的两种方法。
在这里插入图片描述

2. 矩阵

在一些矩阵中，存在很多值相同的元素或者是 0 元素。为了节省存储空间，可以对这类矩阵进行压缩存储，即为多个值相同的元素只分配一个存储单元，对 0 不分配存储单元。
在这里插入图片描述

若矩阵中元素（或非 0 元素）的分布有一定的规律，则称之为特殊矩阵。对于特殊矩阵，由于其非 0 元素的分布有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非 0 元素在矩阵中的位置与其在一维数组中的位置之间的对应关系
常见的特殊矩阵：对称矩阵、三角矩阵和对角矩阵【指矩阵中的非 0 元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为 0】等。

（2）稀疏矩阵

在一个矩阵中，若非 0 元素的个数远远少于 0 元素的个数，且非 0 元素的分布没有规律，则称之为稀疏矩阵。对于稀疏矩阵，存储非 0 元素时必须同时存储其位置（即行号和列号），所以三元组 $i，j，a_{ij}）$ 可唯一确定矩阵 A 中的一个元素，一个稀疏矩阵可由表示非 0 元素的三元组及其行、列数唯一确定。
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

3. 广义表

是线性表的推广，由 0 个或多个单元素或子表组成的有限序列。广义表的长度：指广义表中元素的个数。广义表的深度：指广义表展开后所含的括号的最大层数。
广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。
在这里插入图片描述

（1）广义表的基本操作

取表头【head（LS）】：非空广义表 LS 的第一个元素称为表头，它可以是一个单元素，也可以是一个子表。
取表尾【tail（LS）】：在非空广义表中，除表头元素之外，由其余元素所构成的表称为表尾。非空广义表的表尾必定是一个表。

// C 语言 // 1. 定义广义表的结构体： typedef struct Node { int tag; // 0 表示原子结点，1 表示子表结点 union { int data; // 当 tag 为 0 时，表示数据元素 struct Node *subList; // 当 tag 为 1 时，表示子表 } value; struct Node *next; // 指向下一个结点 } Node; // 2. 取表头： Node* head(Node *LS) { if (LS == NULL) { printf("Error: Empty list.\n"); return NULL; } else if (LS->tag == 0) { printf("Error: Cannot get head of an atomic element.\n"); return NULL; } else { return LS->value.subList; } } // 3. 取表尾： Node* tail(Node *LS) { if (LS == NULL) { printf("Error: Empty list.\n"); return NULL; } else if (LS->tag == 0) { printf("Error: Cannot get tail of an atomic element.\n"); return NULL; } else { return LS->next; } }

（2）广义表的特点

广义表可以是一个递归的表，即广义表中的元素也可以是本广义表的名字。
广义表可以是多层次的结构，因为广义表的元素可以是子表，而子表的元素还可以是子表。
广义表中的元素可以是已经定义的广义表的名字，所以一个广义表可被其他广义表所共享。

（3）广义表的存储结构

由于广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。若广义表不空，则可分解为表头和表尾两部分。反之，一对确定的表头和表尾可唯一确定一个广义表。针对原子和子表可分别设计不同的结点结构。

三、树

树结构是一种非常重要的非线性结构，该结构中的一个数据元素可以有两个或两个以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构关系。

1. 树与二叉树的定义

（1）树的定义

是个结点的有限集合，当时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余结点可分为个互不相交的有限子集 $T_1，T_2，…，T_m$ ，其中，每个 T 又都是一棵树，并且称为根结点的子树。
树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。从数据结构的逻辑关系角度来看，树中元素之间有严格的层次关系。对于树中的某个结点，它最多只和上一层的一个结点（即其双亲结点）有直接的关系，而与其下一层的多个结点（即其孩子结点）有直接关系。

（2）树的基本概念

结点的度：一个结点的子树的个数记为该结点的度。
叶子结点：叶子结点也称为终端结点，指度为 0 的结点。
树的高度：一棵树的最大层数记为树的高度（或深度）。
内部结点：度不为 0 的结点，也称分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
结点的层次：根为第一层，根的孩子为第二层，依此类推，若某结点在第 i 层，则其孩子结点在第计层。
有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
双亲、孩子和兄弟：结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。

（3）二叉树的定义

是个结点的有限集合，它或者是空树，或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成，二叉树同样具有递归性质。
树和二叉树之间最主要的区别是：二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树；二叉树结点最大度为 2 ，而树中不限制结点的度数。
在这里插入图片描述

2. 二叉树的性质与存储结构

（1）二叉树的性质

二叉树第 i 层上最多有 $2^{i - 1}$ 个结点。
高度为 k 的二叉树最多有 $2^{k- 1}$ 个结点。
每一层的结点数都取最大值 $\sum_{i = 1} ^k 2^{i - 1} = 2^{k- 1}$ 即可：
具有 n 个结点的完全二叉树的深度为 $\lfloor log_2n \rfloor + 1$
对于任何一棵二叉树，若其终端结点数为 $n_o$ ，度为 2 的结点数为 $n_2$ ，则 $n_0 = n_2 + 1$ 。

若深度为 k 的二叉树有 $2^{k- 1}$ 个结点，则称其为满二叉树。可以对满二叉树中的结点进行连续编号：约定编号从根结点起，自上而下、自左至右依次进行。深度为 k 、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。
在一个高度为 h 的完全二叉树中，除了第 h 层（最后一层），其余各层都是满的。在第 h 层上的结点必须从左到右依次放置，不能留空。
在这里插入图片描述

（2）二叉树的存储结构

二叉树的顺序存储结构
用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。在最坏情况下，一个深度为 k 且只有 k 个结点的二叉树（单支树）需要 $2^{k - 1}$ 个存储单元。假设有编号为 i 的结点，则有：
若，则该结点为根结点，无双亲；若，则该结点的双亲结点为 $\lfloor i/2 \rfloor$ 。
若，则该结点的右孩子编号为，否则无右孩子。
若，则该结点的左孩子编号为，否则无左孩子。
二叉树的链式存储结构
由于二叉树的结点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根结点。

// 设结点中的数据元素为整型，则二叉链表的结点类型定义： typedef struct BiTnode { int data; struct BiTnode *lchild, *rchild; } BiTnode, *BiTree;

在这里插入图片描述

3. 二叉树的遍历

遍历：按某种策略访问树中的每个结点，且仅访问一次的过程。由于二叉树所具有的递归性质，一棵非空的二叉树是由根结点、左子树和右子树三部分构成的，因此若能依次遍历这三部分，也就遍历了整棵二叉树。按照先遍历左子树后遍历右子树的约定，根据访问根结点位置的不同，可得到二叉树的先序【根左右】、中序【左根右】和后序【左右根】 3 种遍历方法。

// 1. 结构体定义： struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 3. 先序遍历： void preorderTraversal(struct TreeNode* root) { if (root != NULL) { printf("%d ", root->val); // 先访问根节点 preorderTraversal(root->left); // 然后遍历左子树 preorderTraversal(root->right); // 最后遍历右子树 } } // 4. 中序遍历： void inorderTraversal(struct TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); // 先遍历左子树 printf("%d ", root->val); // 然后访问根节点 inorderTraversal(root->right); // 最后遍历右子树 } } // 5. 后序遍历： void postorderTraversal(struct TreeNode* root) { if (root != NULL) { postorderTraversal(root->left); // 先遍历左子树 postorderTraversal(root->right); // 然后遍历右子树 printf("%d ", root->val); // 最后访问根节点 } }

遍历二叉树的基本操作就是访问结点，不论按照哪种次序遍历，对于含有 n 个结点的二叉树，遍历算法的时间复杂度都为：。
遍历二叉树的过程实质上是按一定的规则将树中的结点排成一个线性序列的过程，因此遍历操作得到的是树中结点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终结点，其余结点有且仅有唯一的直接前驱和直接后继。显然，关于结点的前驱和后继的讨论是针对某一个遍历序列而言的。
借助于一个栈，可将二叉树的递归遍历算法转换为非递归算法，对二叉树还可以进行层序遍历【自上而下、自左至右逐层访问树中各结点】。

// 1. 结构体定义： struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; #define MAX_SIZE 1000 // 1. 先序遍历的非递归实现： void preorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } struct TreeNode* stack[MAX_SIZE]; int top = -1; stack[++top] = root; while (top >= 0) { struct TreeNode* node = stack[top--]; printf("%d ", node->val); if (node->right != NULL) { stack[++top] = node->right; } if (node->left != NULL) { stack[++top] = node->left; } } } // 2. 中序遍历的非递归实现： void inorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } struct TreeNode* stack[MAX_SIZE]; int top = -1; struct TreeNode* current = root; while (top >= 0 || current != NULL) { while (current != NULL) { stack[++top] = current; current = current->left; } current = stack[top--]; printf("%d ", current->val); current = current->right; } } // 3. 后序遍历的非递归实现： void postorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } struct TreeNode* stack1[MAX_SIZE]; struct TreeNode* stack2[MAX_SIZE]; int top1 = -1, top2 = -1; stack1[++top1] = root; while (top1 >= 0) { struct TreeNode* node = stack1[top1--]; stack2[++top2] = node; if (node->left != NULL) { stack1[++top1] = node->left; } if (node->right != NULL) { stack1[++top1] = node->right; } } while (top2 >= 0) { struct TreeNode* node = stack2[top2--]; printf("%d ", node->val); } } // 4. 层次遍历的实现： void levelOrderTraversal(struct TreeNode* root) { if (root == NULL) { return; } struct TreeNode* queue[MAX_SIZE]; int front = 0, rear = 0; queue[rear++] = root; while (front < rear) { struct TreeNode* node = queue[front++]; printf("%d ", node->val); if (node->left != NULL) { queue[rear++] = node->left; } if (node->right != NULL) { queue[rear++] = node->right; } } }

4. 线索二叉树

（1）线索二叉树的定义

在二叉链表存储结构中，只能找到一个结点的左、右孩子，不能直接得到结点在任一遍历序列中的前驱和后继，这些信息只有在遍历的动态过程中才能得到，因此，引入线索二叉树来保存这些动态过程得到的信息。

（2）建立线索二叉树

若 n 个结点的二叉树采用二叉链表做存储结构，则链表中必然有 n + 1 个空指针域，可以利用这些空指针域来存放结点的前驱和后继信息。为此，需要在结点中增加标志 ltag 和 rtag，以区分孩子指针的指向。
在这里插入图片描述
若二叉树的二叉链表采用以上所示的结点结构，则相应的链表称为线索链表，其中指向结点前驱、后继的指针称为线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程称为线索化。

5. 最优二叉树

（1）最优二叉树

又称为哈夫曼树，是一类带权路径长度最短的树。路径【从树中一个结点到另一个结点之间的通路】，路径上的分支数目称为路径长度，树的路径长度【从树根到每一个叶子之间的路径长度之和】，结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为： $\sum_{k = 1} ^n w_k l_k$ 其中，n 为带权叶子结点数目， $w_k$ 为叶子结点的权值， $l_k$ 为叶子结点到根的路径长度。
哈夫曼树：指权值为 $w_1，w_2，…，w_n$ 的 n 个叶子结点的二叉树中带权路径长度最小的二叉树。

以下 3 个具有 4 个叶子结点的二叉树，求二叉树带权路径长度最小的树

因此，（B）二叉树带权路径长度最小。

构造最优二叉树的哈夫曼算法：
① 根据给定的 n 个权值 $w_1，w_2，…，w_n\$ ，构成 n 棵二叉树的集合 $F = \T_1，T_2，…，T_n\$ ，其中，每棵树 $T_i$ 中只有一个带权为 $w_i$ 的根结点，其左、右子树均空。
② 在 F 中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
③ 从 F 中删除这两棵树，同时将新得到的二叉树加入到F中。
④ 重复 ②、③ 步，直到 F 中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
当给定了 n 个权值后，构造出的最优二叉树中的结点数目 m 就确定了，即，所以可用一维的结构数组来存储最优二叉树。

（2）哈夫曼编码

若对每个字符编制相同长度的二进制码，则称为等长编码。等长编码方案的实现方法比较简单，但对通信中的原文进行编码后，所得电文的码串过长，不利于提高通信效率。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，那么传送的电文码串总长度则可减少。
设计长度不等的编码，必须满足条件：任一字符的编码都不是另一个字符的编码的前缀，这种编码也称为前缀码。对给定的字符集 $D = \d_1，d_2…，d_n\$ 及字符的使用频率 $W = \ w_1，w_2，…，w_n\$ ，构造其最优前缀码的方法为：以 $d_1，d_2…，d_n$ 作为叶子结点， $w_1，w_2，…，w_n$ 作为叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上 0，右分支标上 1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的 0、1 组成的串。

6. 树和森林

（1）树的存储结构

树的双亲表示法
用一组地址连续的单元存储树的结点，并在每个结点中附设一个指示器，指出其双亲结点在该存储结构中的位置（即结点所在数组元素的下标）。
求指定结点的双亲和祖先都十分方便，但对于求指定结点的孩子及后代则需要遍历整个数组。
树的孩子表示法
在存储结构中用指针指示出结点的每个孩子，为树中每个结点的孩子建立一个链表，即令每个结点的所有孩子结点构成一个用单链表表示的线性表，则 n 个结点的树具有 n 个单链表。将这 n 个单链表的头指针又排成一个线性表。
便于查找每个结点的子孙，若要找出指定结点的双亲则可能需要遍历所有的链表。可以将双亲表示法和孩子表示法结合起来，形成树的双亲孩子表示结构。
孩子兄弟表示法
孩子兄弟表示法又称为二叉链表表示法，它在链表的结点中设置两个指针域分别指向该结点的第一个孩子和下一个兄弟。

（2）树和森林的遍历

① 树的遍历

树的先根遍历
先访问树的根结点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
树的后根遍历
先依次后根遍历树根的各棵子树，然后访问树根结点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。

② 森林的遍历

先序遍历森林
若森林非空，首先访问森林中第一棵树的根结点，然后先序遍历第一棵树根结点的子树森林，最后先序遍历除第一棵树之外剩余的树所构成的森林。
中序遍历森林
若森林非空，首先中序遍历森林中第一棵树的子树森林，然后访问第一棵树的根结点，最后中序遍历除第一棵树之外剩余的树所构成的森林。

（3）树、森林和二叉树之间的相互转换

树、森林转换为二叉树
利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，一棵树可转换成唯一的一棵二叉树。
&emsp森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树的右子树，第三棵树作为转换后二叉树根的右子树的右子树，依此类推。
二叉树转换为树和森林
一棵二叉树可转换为唯一的树或森林。

四、图

比树结构更复杂的一种数据结构，在图中，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱结点和后继结点的数目没有限制。

1. 图的定义与存储

（1）图的定义

图是由集合和构成的二元组，记作，其中，是图中顶点的非空有限集合，是图中边的有限集合。图中任一顶点都有可能与其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系，数据元素用顶点表示，数据元素之间的关系用边表示。

有向图
若图中每条边都是有方向的，那么顶点之间的关系用 $v_i，v_y>$ 表示，它说明从 $v_i$ 到 $v_j$ 有一条有向边（也称为弧）。 $v_i$ 是有向边的起点，称为弧尾； $v_j$ 是有向边的终点，称为弧头。所有边都有方向的图称为有向图。
无向图
若图中的每条边都是无方向的，顶点 $v_i$ 和 $v_j$ 之间的边用 $v_i，v_y）$ 表示，在有向图中 $v_i，v_y>$ 与 $v_y，v_i>$ 分别表示两条边，而在无向图中 $v_i，v_y）$ 与 $v_y，v_i）$ 表示的是同一条边。
完全图
若一个无向图具有个顶点，而每一个顶点与其他个顶点之间都有边，则称之为无向完全图。显然，含有个顶点的无向完全图共有 $\frac{n（n - 1）}{2}$ 条边。类似地，有个顶点的有向完全图中弧的数目为，即任意两个不同顶点之间都有方向相反的两条弧存在。
度、出度和入度
顶点 v 的度是指关联于该顶点的边的数目，记作。若为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为和。无论是有向图还是无向图，顶点数、边数与各顶点的度之间有以下关系： $\frac{1}{2} \sum_{i = 1} ^k 2^{i - 1} D（v_i）$
路径
在无向图中，从顶点 $v_p$ ，到顶点 $v_q$ 的路径是指存在一个顶点序列 $v_p，v_{i 1}，v_{i 2}，...，v_{i n}，v_q$ ，使得 $v_p，v_{i 1}），（v_{i 1}，v_{i 2}），...，（v_{i n}，v_q）$ 均属于。若是有向图，其路径也是有方向的，它由中的有向边 $v_p，v_{i 1}>，<v_{i 1}，v_{i 2}>，...，<v_{i n}，v_q>$ 组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了 $v_p$ ，和 $v_q$ 可以相同外，其余顶点均不相同，则称其为简单路径。
子图
若有两个图和，如果且，则称为的子图。
连通图与连通分量
在无向图中，若从顶点 $v_i$ 到顶点 $v_j$ ，有路径，则称顶点 $v_i$ 和顶点 $v_j$ 是连通的。如果无向图中任意两个顶点都是连通的，则称其为连通图。无向图的极大连通子图称为的连通分量。
强连通图与强连通分量
在有向图中，如果对于每一对顶点 $v_i，v_j ∈ V$ 且 $v_i ≠ v_j$ ，从顶点 $v_i$ 到顶点 $v_j$ 和从顶点 $v_j$ 到顶点 $v_i$ 都存在路径，则称图为强连通图，有向图中的极大连通子图称为有向图的强连通分量。
网
边（或弧）带权值的图。
有向树
如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。

（2）图的存储结构

邻接矩阵表示法
指用一个矩阵来表示图中顶点之间的关系。对于具有个顶点的图 $G = （V，E），其邻接矩阵是一个阶方阵，且满足：

分段函数

$\begin{cases} 1，\quad 若（v_i，v_j）或 <v_i,v_j> 是 E 中的边 \ 0，\quad 若（v_i，v_j）或 <v_i,v_j> 不是 E 中的边 \end{cases}$
无向图的邻接矩阵是对称的，有向图的邻接矩阵则不一定对称。借助于邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。对于无向图，顶点 $v_i$ 的度是邻接矩阵第行（或列）中值不为 0 的元素个数；对于有向图，第行（或列）中值不为 0 的元素个数是顶点 $v_i$ 的出度 $OD（v_i）$ ，第列的非 0 元素个数是顶点v的入度 $ID（v_y）$ 。网（赋权图）的邻接矩阵可定义为：
$\begin{cases} W_{i j}，\quad 若（v_i，v_j）或 <v_i,v_j>∈ E \ ∞，\quad 若（v_i，v_j）或 <v_i,v_j> ∉ E \end{cases}$
其中， $W_{i j}$ 是边（弧）上的权值。
在这里插入图片描述

邻接链表表示法
为图的每个顶点建立一个单链表，第个单链表中的结点表示依附于顶点 $v_i$ 的边（对于有向图是以 $v_i$ 为尾的弧），邻接链表中的结点有表结点（或边结点）和表头结点两种类型：

这些表头结点通常以顺序的形式存储，以便随机访问任一顶点的邻接链表。对于有个顶点、条边的无向图来说，其邻接链表需用个头结点和个表结点。若图用邻接链表来表示，则对应的数据类型可定义如下：

#define MaxN 50 /* 图中顶点数目的最大值 */ /* 邻接链表的表结点 */ typedef struct ArcNode{ int adjvex; /* 邻接顶点的顶点序号 */ double weight; /* 边（弧）上的权值 */ struct ArcNode *nextarc; /* 指向下一个邻接顶点的指针 */ } EdgeNode; /*邻接链表的头结点*/ typedef struct VNode{ char data; /* 顶点表示的数据，以一个字符表示 */ struct ArcNode *firstarc; /* 指向第一条依附于该顶点的边或弧的指针 */ } AdjList[MaxN]; typedef struct { int Vnum; /* 图中顶点的数目 */ AdjList Vertices; } Graph;

对于无向图的邻接链表，顶点 $v_i$ 的度恰为第个邻接链表中表结点的数目，而在有向图中，为求顶点的入度，必须扫描逐个邻接表，这是因为第个邻接链表中表结点的数目只是顶点 $v_i$ 的出度。为此，可以建立一个有向图的逆邻接链表。
在这里插入图片描述

2. 图的遍历

指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。

（1）深度优先搜索（Depth First Search，DFS）

类似于树的先根遍历，在第一次经过一个顶点时就进行访问操作。从图中任一结点出发按深度优先搜索法进行遍历的步骤：
① 设置搜索指针，使指向顶点。
② 访问所指顶点，并使指向与其相邻接的且尚未被访问过的顶点。
③ 若所指顶点存在，则重复步骤②，否则执行步骤④。
④ 沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使指向这个未被访问的顶点，然后重复步骤②，直到所有的顶点均被访问为止。

（2）广度优先搜索（Breadth First Search，BFS）

从图中的某个顶点出发，在访问了之后依次访问的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点"先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问到为止。
特点：尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队列中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。
在这里插入图片描述
遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历图的运算时间复杂度相同，其耗费的时间取决于所采用的存储结构。邻接矩阵时，查找所有顶点的邻接点所需时间为【 $O（n^2）$ 】；邻接表时，查找所有顶点的邻接点所需时间为【】；邻接表时，深度优先搜索遍历图的时间复杂度为【】。不同之处仅仅在于对顶点访问的次序不同。

3. 生成树及最小生成树

（1）生成树的概念

对于有个顶点的连通图，至少有条边，而生成树中恰好有条边，所以连通图的生成树是该图的极小连通子图，若在图的生成树中任意加一条边，则必然形成回路。
在这里插入图片描述
图的生成树不是唯一的，从不同的顶点出发，选择不同的存储方式，用不同的求解方法，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树，把它们称为非连通图的生成树森林。按深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。
在这里插入图片描述

（2）最小生成树

对于连通网来说，边是带权值的，生成树的各边也带权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。

① 普里姆（Prim）算法

以一个顶点集合 $U = {u_0} ，（u_0 ∈ V）$ 作为初态，不断寻找与中顶点相邻且代价最小的边的另一个顶点，扩充集合直到时为止。
在这里插入图片描述
时间复杂度为【 $O（n^2）$ 】，与图中的边数无关，该算法适合于求边稠密的网的最小生成树。

② 克鲁斯卡尔（Kruskal）算法

假设连通网 $N = （V，E），令最小生成树的初始状态为只有个顶点而无边的非连通图 ${ } ） T = （V，\\）$ ，每个顶点自成一个连通分量。在中选择代价最小的边，若该边依附的顶点落在中不同的连通分量上，则将此边加入到中，否则舍去此边而选择下一条代价最小的边。依此类推，直到T中所有顶点都在同一连通分量上为止。
在这里插入图片描述
时间复杂度为，与图中的顶点数无关，该算法适合于求边稀疏的网的最小生成树。

4. 拓扑排序和关键路径

（1）AOV网（Activity On Vertex network）

用有向边表示活动之间开始的先后关系，这种有向图称之为用顶点表示活动网络，简称 AOV 网络。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。在AOV网中不应出现有向环，若存在，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。
不存在回路的有向图称为有向无环图，或 DAG（Directed Acycline Graph）)图。检测的方法：对有向图构造其顶点的拓扑有序序列。若图中所有的顶点都在它的拓扑有序序列中，则该 AOV 网中必定不存在环。

求下图中的拓扑序列
>

上图的拓朴序列有：02143567，01243657，02143657，01243567

（2）拓扑排序及其算法

拓扑排序：将 AOV 网中的所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV 网中从顶点 $v_i$ 到 $v_j$ 有一条路径，则在该线性序列中，顶点 $v_i$ 必然在顶点 $v_j$ 之前，对 AOV 网进行拓扑排序的方法：
① 在 AOV 网中选择一个入度为 0（没有前驱）的顶点且输出它。
② 从网中删除该顶点及与该顶点有关的所有弧。
③ 重复上述两步，直到网中不存在入度为 0 的顶点为止。
在这里插入图片描述
执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。当有向图中无环时，也可以利用深度优先遍历进行逆拓扑排序，时间复杂度为。

（3）AOE网（Activity On Edge network）

若在带权有向图中以顶点表示事件，以有向边表示活动，以边上的权值表示该活动持续的时间，则这种带权有向图简称为AOE网。
一般情况下，在AOE网中至少有一个入度为 0 的开始顶点，称为源点。另外，应有一个出度为 0 的结束顶点，称为汇点。AOE 网中不应存在有向回路，否则整个工程无法完成。

（4）关键路径和关键活动

在从源点到汇点的路径中，长度最长的路径称为关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成，就会影响整个工程的进度，而缩短关键活动的工期通常可以缩短整个工程的工期。

5. 最短路径

（1）单源点最短路径

指给定带权有向图和源点 $v_0$ ，求从 $v_0$ 到中其余各顶点的最短路径。
迪杰斯特拉（Dijkstra）：提出了按路径长度递增的次序产生最短路径的算法，从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

求下图所示的有向网，用迪杰斯特拉算法求解顶点 $v_0$ 到达其余顶点的最短路径

___
因此，根据迪杰斯特拉算法，顶点 $v_0$ 到达其余顶点的最短路径过程为： ${V_0，V_5，V_3，V_4，V_2}$

（2）每对顶点间的最短路径

弗洛伊德（Floyd）：又称为插点法，利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，稠密图效果最佳，适用于出现负边权的情况。

（3）迪杰斯特拉算法（Dijkstra）和弗洛伊德算法（Floyd）

单源最短路径 VS 全局最短路径
迪杰斯特拉算法：用于求解单源最短路径，即从一个顶点到其他所有顶点的最短路径。
弗洛伊德算法则：用于求解全局最短路径，即任意两个顶点之间的最短路径。
贪心算法 VS 动态规划
迪杰斯特拉算法：使用贪心算法，每次选择当前最短路径来进行扩展，并不断更新到各个顶点的距离。
弗洛伊德算法：使用动态规划，通过不断地考察是否存在更短的路径来更新整个路径矩阵。
复杂度
迪杰斯特拉算法：在稠密图上的时间复杂度为 $O（n^2）】$ ，在稀疏图上为（使用最小堆实现）。
弗洛伊德算法：时间复杂度为 $O（n^3）】$ ，其中表示顶点数。

五、查找

1. 查找的基本概念

（1）基本概念

查找：一种常用的基本运算。
查找表：指由同一类型的数据元素（或记录）构成的集合，查找表是一种非常灵活的数据结构。
关键字：数据元素（或记录）的某个数据项的值，用来识别（标识）这个数据元素。主关键字【能唯一标识一个数据元素的关键字】，次关键字是【能标识多个数据元素的关键字】。

（2）平均查找长度

通常以“其关键字和给定值进行过比较的记录个数的期望值”作为衡量查找算法好坏的依据。为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。

2. 静态查找表的查找方法

对查找表经常要进行的两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。通常将只进行这两种操作的查找表称为静态查找表。

3. 动态查找表

对查找表经常要进行的另外两种操作：在查找表中插入一个数据元素；从查找表中删除一个数据元素。若需要在查找表中插入不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。

（1）二叉排序树（Binary Sort Tree）

二叉排序树查找算法详情

（2）平衡二叉树（Balanced Binary Search Tree）

平衡二叉树查找算法详情

（3）B- 树和 B+ 树

B- 树和 B+ 树查找算法详情

4. 哈希表（Hashing）

哈希表查找算法详情

六、排序

1. 排序的基本概念

假设含个记录的文件内容为 $R_1，R_2，…，R_n\$ ，相应的关键字为 $k_1，k_2，…，k_n\$ 。经过排序确定一种排列 $R_{j 1}，R_{j 2}，…，R_{j n}\$ ，使得它们的关键字满足以下递增（或递减）关系。
若在待排序的一个序列中， $R_i$ 和 $R_j$ 的关键字相同，即 $k_i = k_j$ ，且在排序前 $R_i$ 领先于 $R_j$ 那么在排序后，如果 $R_i$ 和 $R_j$ 的相对次序保持不变， $R_i$ 仍领先于 $R_j$ ，则称此类排序方法为稳定的。若在排序后的序列中有可能出现 $R_j$ 领先于 $R_i$ 的情形，则称此类排序为不稳定的。

内部排序：待排序记录全部存放在内存中进行排序的过程。
外部排序：待排序记录的数量很大，以至于内存不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

相关文章