数据结构
2024-07-25 16:46:00 0 举报AI智能生成
数据结构思维导图（巨详细版本） 修改反馈or交个朋友微信id为zywlhxw
作者其他创作
大纲/内容
排序
基本概念和排序方法概述：排序的基本概念、排序方法的分类、排序算法效率的评价指标
排序是计算机科学中的一个基本操作，它将一组数据按照一定的顺序排列。排序的基本概念、排序方法的分类以及排序算法效率的评价指标如下：
排序的基本概念
有序性：排序后的数据应满足特定的顺序关系，如升序或降序。
稳定性：如果待排序的序列中存在多个相同的元素，排序后这些元素之间的相对顺序应该保持不变。
数据类型：排序可以应用于各种数据类型，如整数、浮点数、字符串等。
原地排序：排序操作不需要额外的存储空间，只通过交换或重排元素本身来完成排序。
排序方法的分类
内部排序：排序数据存储在计算机内存中。
外部排序：排序的数据太大，无法全部放入内存，需要与外部存储（如磁盘）进行交互。
比较排序：排序过程中需要比较两个元素的大小。
非比较排序：不需要比较元素的大小，例如基数排序。
原地排序：不需要额外空间，只通过交换或重排元素本身来完成排序。
稳定排序：如果序列中有多个相同元素的原始顺序在排序后保持不变。
不稳定排序：如果序列中有多个相同元素的原始顺序在排序后发生改变
排序算法效率的评价指标
时间复杂度：排序算法执行的时间，通常用大 O 表示法表示，如 O(n log n)、O(n^2) 等。
空间复杂度：排序算法所需的额外空间，包括用于临时存储的辅助空间和输出空间。
稳定性：如果序列中有多个相同元素的原始顺序在排序后保持不变，则该排序算法是稳定的。
原地性：如果排序操作不需要额外的存储空间，只通过交换或重排元素本身来完成排序，则该排序算法是原地的。
最差、平均和最好情况：排序算法在不同情况下的性能表现，包括最坏情况、平均情况和最好情况下的时间复杂度。
了解排序的基本概念、分类和效率评价指标对于选择合适的排序算法非常重要。在实际应用中，需要根据数据的特点和性能要求来选择合适的排序算法。
插入排序：直接插入排序、折半插入排序、希尔排序
直接插入排序
直接插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。其基本实现步骤如下：
把第一个元素当作已排序的序列，第二个元素和它比较。
如果第二个元素比第一个元素小，就把它和第一个元素交换。
然后把第三个元素和已排序的序列比较，直到找到插入的位置并插入。
重复上述过程，直到所有元素插入到已排序的序列中。
直接插入排序的代码实现如下：
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
折半插入排序
折半插入排序是插入排序的一种改进，它利用了二分查找的思想。基本步骤如下：
从第二个元素开始，将元素与已排序序列的元素进行比较。
利用二分查找的方法找到元素应该插入的位置。
插入元素。
折半插入排序的代码实现如下：
void binaryInsertionSort(int arr[], int n) {
int i, key, low, high, mid;
for (i = 1; i < n; i++) {
key = arr[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
for (j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = key;
}
}
希尔排序
希尔排序是插入排序的一种改进，它通过将数组分成几个子序列（或称为“组”）进行插入排序，然后逐渐减少子序列的大小，直到整个数组都被排序。
基本步骤如下：
选择一个增量序列 t1, t2, …, tk，其中 ti > tj，tk = 1。
按增量序列个数 k，对序列进行 k 趟排序。
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子序列进行直接插入排序。仅增量因子为 1 时，整个序列作为一个子序列来处理。
随着增量逐渐减少，子序列的长度逐渐增加，当增量因子为 1 时，整个序列恰被分成一个子序列，算法便终止。
希尔排序的代码实现如下：
void shellSort(int arr[], int n) {
int i, j, gap, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
}
}
总结
插入排序、折半插入排序和希尔排序都是插入排序的不同变体。它们的主要区别在于查找插入位置的方法不同，从而影响了算法的性能。直接插入排序的时间复杂度为 O(n^2)，折半插入排序的时间复杂度通常优于直接插入排序
插入排序（Insertion Sort）是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常使用in-place排序（即只需用到O(1)的额外空间的排序）。
交换排序：冒泡排序、快速排序
交换排序（Exchange Sort）是一种基础的排序算法，它通过元素之间的相互交换来达到排序的目的。交换排序主要包括冒泡排序（Bubble Sort）和快速排序（Quick Sort）两种算法。
冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
基本步骤：
比较相邻的元素。如果第一个比第二个大，就交换它们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后已经排序好的元素。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现：
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
快速排序
快速排序是一种分而治之的排序算法。它的工作原理是通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
基本步骤：
选择一个基准值（pivot）。
将数组分为两部分，一部分所有元素都小于基准值，另一部分所有元素都大于基准值。
对这两部分分别递归地进行快速排序。
最后将排好序的两部分合并。
代码实现：
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
总结
冒泡排序和快速排序都是交换排序的典型代表。冒泡排序的时间复杂度为 O(n^2)，而快速排序的平均和最坏时间复杂度为 O(n log n)，但在最坏情况下，其时间复杂度会退化到 O(n^2)。快速排序的性能通常优于冒泡排序，但在最坏情况下，快速排序的性能可能不如其他一些排序算法。
选择排序：简单选择排序、树形选择排序、堆排序
选择排序（Selection Sort）是一种简单的排序算法，它重复地从待排序的数据中选出最小（或最大）的元素，存放到排序序列的起始位置，直到全部待排序的数据元素排完。选择排序不涉及元素的交换，只涉及数据的移动。
简单选择排序
简单选择排序的基本步骤如下：
在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置。
然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
重复步骤 1 和 2，直到所有元素都排序完毕。
代码实现：
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(arr[min_idx], arr[i]);
}
}
树形选择排序
树形选择排序是一种改进的选择排序，它通过构建一个最小堆（最小树形选择排序）或最大堆（最大树形选择排序）来选择最小的元素。
代码实现：
void heapify(int arr[], int n, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(arr, n, smallest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
堆排序
堆排序是使用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
代码实现：
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
总结
选择排序、树形选择排序和堆排序都是基于选择最小（或最大）元素的排序算法。它们的主要区别在于选择最小（或最大）元素的方法不同。简单选择排序的时间复杂度为 O(n^2)，树形选择排序和堆排序的时间复杂度通常优于简单选择排序，且堆排序通常具有更好的性能。
归并排序：二路归并排序
归并排序（Merge Sort）是一种分治算法，它将一个无序序列分为两个子序列，分别对两个子序列递归地进行排序，最后将两个有序的子序列合并成一个有序的序列。
二路归并排序
二路归并排序的基本步骤如下：
分解：将待排序的数组分成两半，递归地对这两半数组进行排序。
合并：将排好序的两半数组合并成一个有序的数组。
分解步骤：
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
}
}
合并步骤：
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
完整代码实现：
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
总结
归并排序是一种分治算法，它将数组分成两半，递归地对这两半数组进行排序，最后将两个有序的子数组合并成一个有序的数组。二路归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。
基数排序：多关键字排序、链式基数排序
基数排序（Radix Sort）是一种非比较排序算法，它根据整数各个位上的数字来决定其最终顺序。基数排序通过从最低位开始进行排序，依次对每一位进行排序，直到最高位。
多关键字排序
基数排序可以处理多关键字排序的情况。在这种情况下，每个元素都被视为一个数字，每个关键字都是一个数字，并且每个关键字的值都可以决定元素的最终顺序。
链式基数排序
链式基数排序是基数排序的一种实现方式，它使用链表来存储元素，并通过链表的指针来实现元素的排序。链式基数排序的优点是可以更有效地处理大量元素，因为它不需要为每个元素分配额外的内存空间。
基数排序的实现步骤
确定基数：基数是用来表示数字的位数，例如基数为 10 表示整数有 10 个可能的位置（0-9）。
将所有待排序的数字（或数字序列）分别存放到对应的数组中：对于每个位置，数组的长度等于待排序数字的数量。
按从最低位到最高位的顺序对所有数字进行排序：每次对某一位进行排序时，需要将该位上的数字作为关键字，使用直接插入排序（或任何其他排序算法）对数字进行排序。
合并结果：对每个位置上的数组进行排序后，将所有数组合并成一个有序的序列。
代码实现
由于基数排序的实现较为复杂，这里提供一个简化版本的基数排序的代码实现：
#include <stdio.h>
void radixSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int exp = 1;
while (max / exp > 0) {
exp *= 10;
}
exp /= 10;
while (exp > 0) {
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
exp /= 10;
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
printf("Sorted array is \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
这个代码实现是一个简单的基数排序算法，它假设输入的整数都是正数。在实际应用中，基数排序可以处理负数，但需要额外的步骤来处理符号位。
总结
基数排序是一种高效的排序算法，特别适用于整数排序。它通过将整数分解成各个位上的数字，然后对每个位上的数字进行排序来实现整数的排序。多关键字排序和链式基数排序是基数排序的扩展，可以处理具有多个关键字的元素或使用链表来存储元素。
外部排序：基本方法、多路平衡归并、置换-选择排序、最佳归并树
外部排序是指当待排序的数据集过大，无法一次性全部加载到内存中进行排序时，需要与外部存储（如磁盘）进行交互的排序过程。外部排序的基本方法包括多路平衡归并、置换-选择排序和最佳归并树等。
基本方法
磁盘读写：外部排序的主要操作是在磁盘和内存之间进行数据的读写。
记录分割：将大数据集分割成可以一次性加载到内存中的小数据块。
内部排序：对每个小数据块进行排序，通常使用简单的内部排序算法，如快速排序或归并排序。
合并：将排序好的小数据块合并成更大的有序数据块，直到得到最终排序的数据集。
多路平衡归并
多路平衡归并是指同时合并多个小数据块的排序过程。为了平衡合并操作，可以采用平衡归并树（如最佳归并树）来指导合并操作。
置换-选择排序
置换-选择排序是一种外部排序算法，它首先将数据分割成多个小数据块，然后对每个小数据块进行选择排序。在选择排序过程中，每次选择最小元素时，需要将最小元素与已排序序列的末尾元素进行比较，如果最小元素小于末尾元素，则将它们交换。
最佳归并树
最佳归并树（Optimal Merge Tree, OMT）是一种用于指导外部排序中归并操作的树形结构。最佳归并树能够最小化外部排序过程中的磁盘 I/O 操作次数，从而提高排序效率。
实现步骤
磁盘读写：将数据分割成多个小数据块，并将每个小数据块加载到内存中。
内部排序：对每个小数据块进行排序。
归并：根据最佳归并树的结构，将排序好的小数据块合并成更大的有序数据块。
重复步骤 2 和 3：直到所有数据块都被合并成一个有序的数据集。
总结
外部排序是一种处理大数据集排序的算法，它涉及到磁盘和内存之间的数据交互。多路平衡归并、置换-选择排序和最佳归并树是外部排序中的基本方法，它们通过不同的策略来优化排序过程中的磁盘 I/O 操作，从而提高排序效率。
查找
查找的基本概念
查找（Search）是数据结构中的一个基本操作，其目的是在给定的数据集中找到一个或多个特定的元素。查找操作通常用于确定一个元素是否存在于数据集中，或者找到一个元素的位置。查找操作可以分为两大类：顺序查找和二分查找。
顺序查找
顺序查找（Sequential Search）也称为线性查找，它从数据集的第一个元素开始，逐个比较直到找到目标元素或者数据集结束。顺序查找的时间复杂度为 O(n)，其中 n 是数据集中的元素数量。
二分查找
二分查找（Binary Search）也称为折半查找，它适用于有序的数据集。在二分查找中，首先将数据集分为两半，然后比较中间元素与目标元素，如果中间元素是目标元素，则查找结束；如果目标元素小于中间元素，则在左半部分继续查找；如果目标元素大于中间元素，则在右半部分继续查找。重复这个过程，直到找到目标元素或者数据集为空。二分查找的时间复杂度为 O(log n)，其中 n 是数据集中的元素数量。
查找算法的选择
选择合适的查找算法取决于数据集的特性。对于有序数据集，二分查找是更高效的查找方法；对于无序数据集，顺序查找是唯一的选择。
查找的效率分析
查找算法的效率可以通过时间复杂度来分析。时间复杂度表示查找操作所需时间的度量，它是算法执行次数的对数或线性表达式。在实际应用中，通常选择时间复杂度较低的查找算法，以提高查找效率。
查找的应用
查找操作在计算机科学和编程中有着广泛的应用，例如：
在编程语言中，查找操作用于查找变量、函数、类等。
在数据库管理系统中，查找操作用于检索数据库中的记录。
在文件系统中，查找操作用于定位文件和目录。
在网络通信中，查找操作用于定位网络中的设备和服务。
总结
查找是数据结构中的一个基本操作，它用于在数据集中找到特定的元素。掌握查找的基本概念、算法和应用，对于理解和解决实际问题非常重要。
线性表的查找：顺序查找、折半查找、分块查找
顺序查找
顺序查找是最简单的查找方法，它从线性表的第一个元素开始，逐个比较直到找到目标元素或者线性表结束。
步骤：
设置两个指针，分别指向线性表的第一个元素和最后一个元素。
从第一个元素开始，比较目标元素与当前元素，如果找到目标元素，则查找结束；如果目标元素小于当前元素，则将第一个指针移到下一个元素；如果目标元素大于当前元素，则将最后一个指针移到上一个元素。
重复步骤 2，直到找到目标元素或者两个指针相遇。
时间复杂度：
顺序查找的时间复杂度为 O(n)，其中 n 是线性表的长度。在最坏情况下，需要比较整个线性表。
顺序查找
#include <stdio.h>
// 顺序查找
int SequentialSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 返回元素的位置
}
}
return -1; // 未找到元素
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
int index = SequentialSearch(arr, n, key);
if (index != -1) {
printf("元素 %d 在数组中的位置是 %d\n", key, index);
} else {
printf("元素 %d 不在数组中\n", key);
}
return 0;
}
折半查找
折半查找也称为二分查找，它适用于有序的线性表。折半查找通过将线性表分为两半，然后比较中间元素与目标元素，逐步缩小查找范围。
步骤：
设置两个指针，分别指向线性表的第一个元素和最后一个元素。
计算中间元素的位置，并比较中间元素与目标元素。
如果中间元素等于目标元素，则查找结束；如果目标元素小于中间元素，则在左半部分继续查找；如果目标元素大于中间元素，则在右半部分继续查找。
重复步骤 2 和 3，直到找到目标元素或者线性表为空。
时间复杂度：
折半查找的时间复杂度为 O(log n)，其中 n 是线性表的长度。在最坏情况下，需要比较 log n 次。
折半查找
#include <stdio.h>
// 折半查找
int BinarySearch(int arr[], int n, int key) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid; // 返回元素的位置
} else if (arr[mid] < key) {
low = mid + 1; // 在右半部分继续查找
} else {
high = mid - 1; // 在左半部分继续查找
}
}
return -1; // 未找到元素
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
int index = BinarySearch(arr, n, key);
if (index != -1) {
printf("元素 %d 在数组中的位置是 %d\n", key, index);
} else {
printf("元素 %d 不在数组中\n", key);
}
return 0;
}
分块查找
分块查找是一种改进的查找方法，它将线性表分为若干个块，每个块内部是无序的，但块与块之间是有序的。
步骤：
将线性表分为若干个块，块的大小可以根据需要进行调整。
在每个块内部使用顺序查找方法查找目标元素。
如果目标元素不在当前块内，则在块与块之间使用折半查找方法查找目标元素。
时间复杂度：
分块查找的时间复杂度为 O(m + log n)，其中 m 是块的大小，n 是线性表的长度。在最坏情况下，需要比较 m + log n 次。
分块查找
分块查找通常涉及更多的数据结构和算法，如索引块和分块查找算法。以下是一个简化版的分块查找实现示例：
#include <stdio.h>
// 分块查找
int BlockSearch(int arr[], int n, int key) {
int block_size = 5; // 假设块的大小为 5
int block_index = 0;
while (block_index < n) {
if (arr[block_index] == key) {
return block_index; // 返回元素的位置
}
block_index += block_size;
}
return -1; // 未找到元素
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
int index = BlockSearch(arr, n, key);
if (index != -1) {
printf("元素 %d 在数组中的位置是 %d\n", key, index);
} else {
printf("元素 %d 不在数组中\n", key);
}
return 0;
}
树表的查找：二叉排序树、平衡二叉树、B-树、B+树
二叉排序树（Binary Search Tree, BST）
二叉排序树是一种特殊的二叉树，其中每个节点都包含一个键值，并且满足以下性质：
左子树的所有键值都小于当前节点的键值。
右子树的所有键值都大于当前节点的键值。
左子树和右子树也都是二叉排序树。
查找步骤：
从根节点开始，比较目标键值与当前节点的键值。
如果目标键值小于当前节点的键值，则移动到左子节点。
如果目标键值大于当前节点的键值，则移动到右子节点。
如果目标键值等于当前节点的键值，则查找成功。
如果到达空节点，则查找失败
平衡二叉树（AVL Tree）
平衡二叉树是一种特殊的二叉排序树，其中每个节点的左右子树的高度最多相差 1。这种结构确保了树的高度是平衡的，从而保证了查找操作的时间复杂度为 O(log n)。
B-树
B-树是一种多路搜索树，它允许每个节点有多个子节点。B-树的主要特点是：
每个节点都包含多个键值和子节点。
子节点的数量是固定的，与节点的大小有关。
每个节点至少有 m/2 个键值，其中 m 是节点的最大子节点数。
每个节点至少有 m/2 + 1 个键值，其中 m 是节点的最大子节点数。
B+树
B+树是 B-树的一种变体，它具有以下特点：
所有键值都存储在叶子节点。
非叶子节点只包含键值和指向子节点的指针。
所有叶子节点都存储在同一层，并且叶子节点之间通过指针连接。
散列表的查找：基本概念、散列函数、处理冲突、查找
散列表（Hash Table）是一种数据结构，它通过散列函数将键（Key）映射到表中的一个位置，称为散列地址（Hash Address），从而实现快速的查找、插入和删除操作。散列表的基本概念包括散列函数、处理冲突和查找等。
基本概念
散列函数：将键映射到散列表中的一个位置的函数。理想的散列函数应该将键均匀地分布到散列表中，以减少冲突。
散列地址：通过散列函数计算得到的键在散列表中的位置。
冲突：当多个键通过散列函数映射到同一个散列地址时，就会发生冲突。
处理冲突：为了处理冲突，散列表中通常包含一些解决冲突的策略，如链地址法、开放定址法等。
散列函数
散列函数的设计非常重要，它直接影响到散列表的性能。一个好的散列函数应该具备以下特点：
均匀分布：尽可能地将键均匀地分布到散列表中，减少冲突。
简单快速：计算散列地址的算法简单且快速，以提高散列表的查找效率。
唯一性：理论上，每个键都应该通过散列函数映射到唯一的散列地址。
处理冲突
处理冲突是散列表设计中的一个重要问题。以下是一些常见的处理冲突的策略：
链地址法：在散列表的每个位置上存储一个链表，当发生冲突时，将冲突的键添加到对应的链表中。
开放定址法：当发生冲突时，通过探测表中的其他位置来找到一个空闲的位置。探测方法包括线性探测、二次探测、对数探测等。
再散列：当发生冲突时，使用另一个散列函数重新计算散列地址。
查找
在散列表中查找一个键，首先通过散列函数计算出散列地址，然后根据键在散列表中的位置进行查找。如果找到键，则查找成功；如果没有找到，则查找失败
总结
散列表是一种高效的数据结构，通过散列函数将键映射到散列表中的一个位置，从而实现快速的查找、插入和删除操作。散列函数的设计、冲突的处理以及查找算法的实现是散列表设计的关键。掌握散列表的基本概念、散列函数的设计和冲突的处理策略，对于理解和解决实际问题非常重要。
栈和队列
定义和特点：栈 (后进先出)、队列 (先进先出)
栈（Stack）
栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈的主要特点是插入和删除操作都在栈的一端进行，称为栈顶（Top）。
特点：
后进先出：最后压入栈的元素最先被弹出。
操作有限：仅允许在栈顶进行插入（Push）和删除（Pop）操作。
动态性：栈的大小可以动态变化，可以通过添加或删除元素来改变栈的大小。
存储连续：栈的元素通常存储在连续的内存空间中，可以通过索引直接访问。
队列（Queue）
队列是一种先进先出（First In First Out, FIFO）的数据结构。队列的主要特点是插入操作在队列的一端进行，称为队尾（Rear），而删除操作在队列的另一端进行，称为队头（Front）。
特点：
先进先出：最先进入队列的元素最先被移除。
操作有限：仅允许在队尾进行插入（Enqueue）操作，在队头进行删除（Dequeue）操作。
动态性：队列的大小可以动态变化，可以通过添加或删除元素来改变队列的大小。
存储连续：队列的元素通常存储在连续的内存空间中，可以通过索引直接访问。
总结
栈和队列是计算机科学中非常基础和重要的数据结构。栈主要用于后进先出的场景，如函数调用栈、浏览器历史记录等；而队列主要用于先进先出的场景，如打印队列、任务调度等。掌握栈和队列的概念、操作和应用，对于理解和解决实际问题非常重要。
案例引入：数制转换、括号匹配检验、表达式求值、舞伴问题
数制转换
数制转换是指将一个数从一种数制转换为另一种数制。例如，将十进制数转换为二进制、八进制或十六进制。这通常涉及到将数字除以目标数制的基数，并记录余数的过程。
括号匹配检验
括号匹配检验是指检查字符串中的括号是否正确匹配。例如，检查字符串 “{[()]}[]” 中的括号是否正确闭合。这通常涉及到使用栈来存储左括号，并在遇到右括号时检查是否匹配。
表达式求值
表达式求值是指计算数学表达式的值。例如，计算表达式 “2 + 3 * 4 / ( 1 - 5 )” 的值。这通常涉及到使用栈来存储操作数和操作符，并按照运算优先级进行计算。
舞伴问题
舞伴问题是指在有限数量的男女舞伴中，如何安排舞伴，使得每位舞伴都能找到舞伴，且每位舞伴都只与一位舞伴跳舞。这通常涉及到使用栈来模拟舞伴的配对过程。
案例分析与实现
数制转换：可以使用栈来存储每次除法操作的余数，并按照从下到上的顺序输出余数，得到转换后的数。
括号匹配检验：可以使用栈来存储左括号，并在遇到右括号时检查是否匹配。如果栈为空或右括号的数量大于左括号的数量，则括号不匹配。
表达式求值：可以使用栈来存储操作数和操作符，并按照运算优先级进行计算。在遇到操作符时，将栈顶的两个操作数弹出，与操作符一起进行计算，并将结果压入栈中。
舞伴问题：可以使用栈来模拟舞伴的配对过程，确保每位舞伴都能找到舞伴，且每位舞伴都只与一位舞伴跳舞。
栈的表示和操作的实现：
类型定义：抽象数据类型
栈（Stack）
栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈的插入和删除操作都只发生在栈的一端，通常称为栈顶（Top）。
ADT Stack { 数据对象：一个线性表，通常使用数组或链表实现。 数据关系：线性表中的元素按顺序排列。 基本操作：
IsEmpty(): 判断栈是否为空。
Push(e): 在栈顶添加一个新元素。
Pop(): 移除栈顶元素。
Peek(): 查看栈顶元素，但不从栈中移除。
Size(): 返回栈中元素的数量。
Clear(): 清空栈。 }
队列（Queue）
队列是一种先进先出（First In First Out, FIFO）的数据结构。队列的插入操作在队尾（Rear）进行，删除操作在队头（Front）进行。
ADT Queue { 数据对象：一个线性表，通常使用数组或链表实现。 数据关系：线性表中的元素按顺序排列。 基本操作：
IsEmpty(): 判断队列是否为空。
Enqueue(e): 在队尾添加一个新元素。
Dequeue(): 移除队头元素。
Peek(): 查看队头元素，但不从队列中移除。
Size(): 返回队列中元素的数量。
Clear(): 清空队列。 }
栈和队列的特点：
线性结构：栈和队列都是线性结构，元素之间是一对一的关系。
有序性：栈和队列的元素按特定的顺序排列，栈是后进先出，队列是先进先出。
操作方式：栈和队列的操作方式不同，栈只允许在栈顶进行插入和删除操作，而队列只允许在队尾进行插入操作，在队头进行删除操作。
实现方式：栈和队列可以使用数组或链表来实现，数组适合静态存储和随机访问，链表适合动态存储和高效操作。
栈和队列的应用：
栈：后进先出，常用于表达式求值、函数调用栈、浏览器的历史记录等。
队列：先进先出，常用于打印队列、任务调度、消息队列等。
总结：
栈和队列是常见的线性数据结构，它们遵循特定的规则来访问和修改数据。掌握栈和队列的定义、操作和应用，对于理解和解决实际问题非常重要。
顺序栈：定义和表示、基本操作的实现：初始化、入栈、出栈、取栈顶元素
顺序栈（Sequential Stack）是一种使用数组实现的栈，其中数组的大小是固定的。顺序栈的定义和表示如下：
定义和表示：
顺序栈可以使用数组来实现，数组的大小预先定义，通常是栈可能达到的最大容量。栈中的元素按照入栈的顺序依次排列在数组中，栈顶元素位于数组的末尾。
基本操作的实现：
初始化：创建一个新的顺序栈，并将栈顶指针设置为 -1，表示栈为空。
入栈（Push）：当栈未满时，将新元素添加到栈顶。这通常涉及将栈顶指针增加 1，并将新元素放入栈顶位置。
出栈（Pop）：当栈非空时，移除栈顶元素。这通常涉及将栈顶指针减 1，并将栈顶元素的值返回。
取栈顶元素（Peek）：当栈非空时，返回栈顶元素的值，但不移除该元素。这通常涉及返回栈顶指针指向的元素值。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int ElementType;
typedef struct {
ElementType stack[MAX_SIZE];
int top;
} SequentialStack;
// 初始化顺序栈
void InitStack(SequentialStack *s) {
s->top = -1;
}
// 入栈
void Push(SequentialStack *s, ElementType e) {
if (s->top < MAX_SIZE - 1) {
s->top++;
s->stack[s->top] = e;
} else {
printf("栈已满，无法入栈\n");
}
}
// 出栈
ElementType Pop(SequentialStack *s) {
if (s->top >= 0) {
ElementType e = s->stack[s->top];
s->top--;
return e;
} else {
printf("栈已空，无法出栈\n");
return -1; // 或者抛出异常
}
}
// 取栈顶元素
ElementType Peek(const SequentialStack *s) {
if (s->top >= 0) {
return s->stack[s->top];
} else {
printf("栈已空，无法取栈顶元素\n");
return -1; // 或者抛出异常
}
}
// 测试代码
int main() {
SequentialStack s;
InitStack(&s);
Push(&s, 1);
Push(&s, 2);
Push(&s, 3);
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
return 0;
}
注意：
在实际应用中，应该使用动态内存分配来避免栈溢出的问题，而不是预先定义栈的大小。
在上面的代码中，如果栈已满，Push 函数会打印一条错误消息并返回。如果栈已空，Pop 和 Peek 函数会打印一条错误消息并返回 -1。
代码中的 top 变量用于指示栈顶元素的位置，其初始值为 -1 表示栈为空。
链栈：定义和表示、基本操作的实现：初始化、入栈、出栈、取栈顶元素
链栈（Linked Stack）是一种使用链表实现的栈，其中链表的每个节点包含一个元素和一个指向下一个节点的指针。链栈的定义和表示如下：
定义和表示：
链栈使用链表作为其底层数据结构，链表中的每个节点包含一个元素和一个指向下一个节点的指针。链栈的头节点（Head）指向链表的第一个元素，栈顶元素是链表的最后一个元素。
基本操作的实现：
初始化：创建一个新的链栈，并设置头节点指向 null。
入栈（Push）：在链栈的末尾添加一个新元素。这通常涉及创建一个新的链表节点，将其链接到当前栈顶节点的下一个节点，并将新的栈顶节点的指针设置为新创建的节点。
出栈（Pop）：移除链栈的最后一个元素。这通常涉及将当前栈顶节点的指针设置为其下一个节点的指针，并返回当前栈顶节点的元素。
取栈顶元素（Peek）：查看链栈的最后一个元素，但不从栈中移除。这通常涉及返回当前栈顶节点的元素。
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node {
ElementType data;
struct Node *next;
} Node;
typedef Node *LinkStack;
// 初始化链栈
void InitStack(LinkStack *s) {
*s = NULL;
}
// 入栈
void Push(LinkStack *s, ElementType e) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = e;
newNode->next = *s;
*s = newNode;
}
// 出栈
ElementType Pop(LinkStack *s) {
if (*s == NULL) {
printf("栈已空，无法出栈\n");
return -1; // 或者抛出异常
}
ElementType e = (*s)->data;
Node *temp = *s;
*s = (*s)->next;
free(temp);
return e;
}
// 取栈顶元素
ElementType Peek(const LinkStack *s) {
if (*s == NULL) {
printf("栈已空，无法取栈顶元素\n");
return -1; // 或者抛出异常
}
return (*s)->data;
}
// 测试代码
int main() {
LinkStack s;
InitStack(&s);
Push(&s, 1);
Push(&s, 2);
Push(&s, 3);
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
printf("栈顶元素: %d\n", Peek(&s));
printf("出栈元素: %d\n", Pop(&s));
return 0;
}
注意：
在实际应用中，应该使用动态内存分配来避免栈溢出的问题，而不是预先定义栈的大小。
在上面的代码中，如果入栈操作失败（例如，内存分配失败），Push 函数会打印一条错误消息并返回。如果出栈操作失败（例如，栈为空），Pop 和 Peek 函数会打印一条错误消息并返回 -1。
代码中的 Peek 函数和 Pop 函数都检查了栈是否为空，以避免空栈操作。
栈与递归：递归算法、递归过程与递归工作栈、递归算法的效率分析、递归转换为非递归
栈与递归的关系非常紧密，因为递归算法通常涉及函数调用栈，而函数调用栈可以看作是一种后进先出（LIFO）的栈结构。在递归过程中，每次函数调用都会将当前的函数状态（包括局部变量、参数和返回地址）压入栈中，直到递归终止时，这些状态才会被弹出。
递归算法
递归算法是一种解决问题的方法，其中函数直接或间接地调用自身。递归算法通常用于解决具有分治性质的问题，即问题可以被分解为若干个子问题，每个子问题都是原问题的一个实例，并且可以递归地解决。
递归过程与递归工作栈
递归过程：
函数调用自身。
当前函数的状态被保存（包括局部变量、参数和返回地址）。
执行下一个递归调用。
当所有递归调用完成后，从最后一个递归调用开始，函数状态被恢复并执行返回语句。
递归工作栈：
函数调用栈：当函数调用自身时，当前函数的状态被压入栈中，直到所有递归调用完成。
每个栈帧包含当前函数的状态，包括局部变量、参数和返回地址。
递归算法的效率分析
递归算法的效率通常不如其非递归版本，原因包括：
栈空间消耗：递归算法可能会导致大量的栈空间消耗，尤其是在深度递归的情况下。
重复计算：在某些情况下，递归算法可能会重复计算相同的子问题，这会导致性能下降。
编译器优化：递归函数的编译器优化可能不如非递归函数，因为递归函数的调用和返回模式更复杂。
递归转换为非递归
递归算法可以转换为非递归算法，通常通过使用迭代（循环）来模拟递归过程。这种转换可以减少栈空间的使用，并可能提高算法的效率。例如，可以使用循环和辅助数据结构（如栈或队列）来模拟递归函数的工作栈。
递归算法：
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n -
非递归算法（使用循环和辅助数据结构）：
def fibonacci_non_recursive(n):
if n <= 1:
return n
fib_sequence = [0, 1]
for i in range(2, n + 1):
fib_sequence.append(fib_sequence[i - 1] + fib_sequence[i - 2])
return fib_sequence[n]
队列的表示和操作的实现：
类型定义：抽象数据类型
队列（Queue）是一种线性数据结构，遵循先进先出（First In First Out, FIFO）的原则。以下是队列的抽象数据类型（Abstract Data Type, ADT）定义：
ADT Queue { 数据对象：一个线性表，通常使用数组或链表实现。 数据关系：线性表中的元素按顺序排列。 基本操作：
IsEmpty(): 判断队列是否为空。
Enqueue(e): 在队尾添加一个新元素。
Dequeue(): 移除队头元素。
Peek(): 查看队头元素，但不从队列中移除。
Size(): 返回队列中元素的数量。
Clear(): 清空队列。 }
队列的特点：
线性结构：队列是线性结构，元素之间是一对一的关系。
有序性：队列中的元素按特定的顺序排列，遵循先进先出原则。
操作方式：队列的插入操作（Enqueue）在队尾进行，删除操作（Dequeue）在队头进行。
实现方式：队列可以使用数组或链表来实现，数组适合静态存储和随机访问，链表适合动态存储和高效操作。
队列的应用：
任务调度：在操作系统中，任务队列用于管理等待执行的任务。
消息队列：在通信系统中，消息队列用于存储和转发消息。
打印队列：在打印机中，打印队列用于管理待打印的文档。
总结：
队列是一种常见的线性数据结构，它遵循先进先出原则。掌握队列的定义、操作和应用，对于理解和解决实际问题非常重要。
循环队列：定义和表示、基本操作的实现：初始化、求队列长度、入队、出队、取队头元素
循环队列（Circular Queue）是一种特殊的队列，其内部结构使用数组实现，数组的边界被看作是循环的，即当队尾指针到达数组末尾时，它会自动从数组的开始处继续。循环队列的定义和表示如下：
定义和表示：
循环队列使用一个数组来表示队列，数组的边界被看作是循环的。队列的头部和尾部指针分别指向数组中的第一个元素和最后一个元素。当队尾指针到达数组末尾时，它会自动从数组的开始处继续。
基本操作的实现：
初始化：创建一个新的循环队列，并设置队头指针和队尾指针都指向数组的开始。
求队列长度：计算循环队列中有效元素的数量。
入队（Enqueue）：在队尾添加一个新元素。这通常涉及将队尾指针增加 1，并将新元素放入队尾指针指向的位置。如果队尾指针指向数组的末尾，则队尾指针会自动从数组的开始处继续。
出队（Dequeue）：移除队头元素。这通常涉及将队头指针增加 1，并返回队头指针指向的元素。如果队头指针指向数组的末尾，则队头指针会自动从数组的开始处继续。
取队头元素（Peek）：查看队头元素，但不从队列中移除。这通常涉及返回队头指针指向的元素。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int ElementType;
typedef struct {
ElementType data[MAX_SIZE];
int front;
int rear;
} CircularQueue;
// 初始化循环队列
void InitQueue(CircularQueue *q) {
q->front = q->rear = 0;
}
// 入队
void Enqueue(CircularQueue *q, ElementType e) {
if ((q->rear + 1) % MAX_SIZE != q->front) {
q->data[q->rear] = e;
q->rear = (q->rear + 1) % MAX_SIZE;
} else {
printf("队列已满，无法入队\n");
}
}
// 出队
ElementType Dequeue(CircularQueue *q) {
if (q->front != q->rear) {
ElementType e = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return e;
} else {
printf("队列已空，无法出队\n");
return -1; // 或者抛出异常
}
}
// 取队头元素
ElementType Peek(const CircularQueue *q) {
if (q->front != q->rear) {
return q->data[q->front];
} else {
printf("队列已空，无法取队头元素\n");
return -1; // 或者抛出异常
}
}
// 测试代码
int main() {
CircularQueue q;
InitQueue(&q);
Enqueue(&q, 1);
Enqueue(&q, 2);
Enqueue(&q, 3);
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
return 0;
}
注意：
在实际应用中，应该使用动态内存分配来避免队列溢出的问题，而不是预先定义队列的大小。
在上面的代码中，如果入队操作失败（例如，队列已满），Enqueue 函数会打印一条
链队：定义和表示、基本操作的实现：初始化、入队、出队、取队头元素
链队（Linked Queue）是一种使用链表实现的队列，其中链表的每个节点包含一个元素和一个指向下一个节点的指针。链队的定义和表示如下：
定义和表示：
链队使用链表作为其底层数据结构，链表中的每个节点包含一个元素和一个指向下一个节点的指针。链队的头节点（Head）指向链表的第一个元素，队尾元素是链表的最后一个元素。
基本操作的实现：
初始化：创建一个新的链队，并设置头节点指向 null。
入队（Enqueue）：在链队的末尾添加一个新元素。这通常涉及创建一个新的链表节点，将其链接到当前队尾节点的下一个节点，并将新的队尾节点的指针设置为新创建的节点。
出队（Dequeue）：移除链队的第一个元素。这通常涉及将头节点的指针设置为其下一个节点的指针，并返回头节点的元素。
取队头元素（Peek）：查看链队的第一个元素，但不从队列中移除。这通常涉及返回头节点的元素。
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node {
ElementType data;
struct Node *next;
} Node;
typedef Node *LinkedQueue;
// 初始化链队
void InitQueue(LinkedQueue *q) {
*q = NULL;
}
// 入队
void Enqueue(LinkedQueue *q, ElementType e) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = e;
newNode->next = *q;
*q = newNode;
}
// 出队
ElementType Dequeue(LinkedQueue *q) {
if (*q == NULL) {
printf("队已空，无法出队\n");
return -1; // 或者抛出异常
}
ElementType e = (*q)->data;
Node *temp = *q;
*q = (*q)->next;
free(temp);
return e;
}
// 取队头元素
ElementType Peek(const LinkedQueue *q) {
if (*q == NULL) {
printf("队已空，无法取队头元素\n");
return -1; // 或者抛出异常
}
return (*q)->data;
}
// 测试代码
int main() {
LinkedQueue q;
InitQueue(&q);
Enqueue(&q, 1);
Enqueue(&q, 2);
Enqueue(&q, 3);
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
printf("队头元素: %d\n", Peek(&q));
printf("出队元素: %d\n", Dequeue(&q));
return 0;
}
注意：
在实际应用中，应该使用动态内存分配来避免队列溢出的问题，而不是预先定义队列的大小。
在上面的代码中，如果入队操作失败（例如，内存分配失败），Enqueue 函数会打印一条错误消息并返回。如果出队操作失败（例如，队为空），Dequeue 和 Peek 函数会打印一条错误消息并返回 -1。
代码中的 Peek 函数和 Dequeue 函数都检查了队列是否为空，以避免空队列操作。
栈和队列的应用
栈的应用：
函数调用栈：在编程语言中，当一个函数调用另一个函数时，会使用栈来存储当前函数的状态，包括返回地址和局部变量。
后缀表达式计算：在计算后缀表达式（逆波兰表达式）时，栈可以用来暂存操作数和计算结果。
括号匹配：在编程语言编译器中，栈可以用来检查表达式中的括号是否匹配。
浏览器历史记录：浏览器使用栈来记录用户访问的网页，允许用户向前或向后导航。
系统调用栈：操作系统使用栈来存储系统调用的状态，包括返回地址和局部变量。
算法实现：许多算法，如递归算法、回溯算法等，都使用栈来模拟递归过程。
队列的应用：
打印队列：在打印机或绘图仪中，打印任务通常被放入队列中，按照先入先出的原则执行。
任务调度：操作系统使用队列来管理等待执行的任务，如进程调度队列、线程队列等。
消息队列：在网络编程中，消息通常通过队列进行传递，确保消息的顺序和完整性。
缓冲区管理：在数据传输过程中，使用队列作为缓冲区，以平衡输入和输出速度。
并发控制：在多线程编程中，使用队列来控制线程之间的通信和同步。
缓存策略：在数据库和缓存系统中，使用队列来管理数据的缓存和淘汰策略。
总结
栈和队列是计算机科学中不可或缺的数据结构，它们在程序设计、操作系统、网络通信等多个领域都有广泛的应用。掌握栈和队列的概念、操作和应用，对于理解和解决实际问题非常重要。
串、数组和广义表
串
定义
串（string）或字符串，是由零个或多个字符组成的有限序列，通常用双引号括起来表示，例如：
“Hello, World!”
串的基本概念：
长度： 串中字符的数量，用 length 表示。
子串： 串中任意个连续的字符组成的序列，例如 “World” 是 “Hello, World!” 的子串。
相等： 两个串相等当且仅当它们的长度相等，并且对应位置的字符也相等。
案例引入：病毒感染检测
串的应用：
文字编辑： 处理文本数据，例如拼写检查、语法分析等。
信息检索： 搜索文档中的关键词或短语。
语言编译： 分析源代码，进行词法分析和语法分析。
网络通信： 传输数据，例如电子邮件、网页等。
串的存储结构：
顺序存储： 使用数组存储字符序列，例如定长顺序存储结构和堆式顺序存储结构。
链式存储： 使用链表存储字符序列，例如块链结构。
问题描述：
研究者想要检测人是否感染了某种病毒。病毒和人的 DNA 序列都可以用字符串表示，通过比较这两个字符串，可以判断人是否感染了病毒。
数据格式：
输入文件：第一行是一个整数 num，表示待检测的任务数量。接下来 num 行，每行包含两个字符串，第一个字符串表示病毒的 DNA 序列，第二个字符串表示人的 DNA 序列。
输出文件：每行包含三个数据，第一个和第二个数据分别表示输入文件中对应病毒的 DNA 序列和人的 DNA 序列，第三个数据表示是否感染（“YES” 或 “NO”）。
案例分析与实现：
字符串表示： 将病毒和人的 DNA 序列都表示为字符串。
模式匹配： 使用 KMP 算法或 BF 算法判断病毒的 DNA 序列是否在人的 DNA 序列中出现。
结果输出： 根据模式匹配的结果，输出感染情况。
#include <iostream>
#include <string>
#include <vector>
// ... KMP 算法实现 ...
void DetectVirus(const std::vector<std::string> &data) {
for (const auto &row : data) {
std::string virus = row[0];
std::string human = row[1];
int pos = KMP(human, virus);
if (pos != -1) {
std::cout << virus << " " << human << " YES" << std::endl;
} else {
std::cout << virus << " " << human << " NO" << std::endl;
}
}
}
int main() {
int num;
std::cin >> num;
std::vector<std::string> data(num);
for (int i = 0; i < num; ++i) {
std::cin >> data[i];
}
DetectVirus(data);
return 0;
}
类型定义：抽象数据类型
ADT String {
数据对象: D = {a_i | a_i ∈ characterSet, i = 1, 2, ..., n, n ≥ 0}
数据关系: R = {<a_i, a_{i+1}> | a_i ∈ characterSet, i = 1, 2, ..., n-1}
基本操作:
CreateString(s): 创建一个空串 s
CopyString(s, t): 将串 s 复制到 t
CompareString(s, t): 比较串 s 和 t 的大小
GetLength(s): 返回串 s 的长度
ClearString(s): 将串 s 清空
ConcatString(s, t): 将串 t 连接到串 s 的末尾
SubString(s, pos, len): 从串 s 中提取长度为 len 的子串，起始位置为 pos
Index(s, t, pos): 在串 s 中查找子串 t，从位置 pos 开始
ReplaceString(s, t, v): 用串 v 替换串 s 中出现的所有与 t 相等的子串
InsertString(s, pos, t): 在串 s 的位置 pos 插入子串 t
DeleteString(s, pos, len): 从串 s 中删除长度为 len 的子串，起始位置为 pos
DestroyString(s): 销毁串 s
}
存储结构：顺序存储 (定长、堆式)、链式存储 (块链结构)
1. 顺序存储结构
定长顺序存储结构：
使用数组存储字符序列，数组长度固定。
优点：随机访问效率高，空间利用率高。
缺点：空间浪费，不灵活，无法动态扩展。
堆式顺序存储结构：
使用动态分配的数组存储字符序列，数组长度根据需要动态扩展。
优点：空间利用率高，灵活，可以动态扩展。
缺点：随机访问效率略低于定长数组。
2. 链式存储结构
块链结构：
使用链表存储字符序列，每个节点可以存储多个字符。
优点：空间利用率高，插入和删除操作效率高。
缺点：随机访问效率低，需要从头节点开始遍历。
选择合适的存储结构：
如果字符串长度固定，且操作以随机访问为主，则可以选择定长顺序存储结构。
如果字符串长度变化较大，且操作以插入和删除为主，则可以选择堆式顺序存储结构。
如果字符串长度变化很大，且操作以插入和删除为主，则可以选择链式存储结构。
总结
选择合适的字符串存储结构，可以提高字符串操作的效率，并满足不同的应用需求。
基本操作：赋值、复制、判断空串、比较、求长度、清除、连接、子串、索引、替换、插入、删除
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef char String[MAXSIZE + 1];
// 赋值
void StringAssign(String s, const char *str) {
strcpy(s, str);
}
// 复制
void StringCopy(String s, const String t) {
strcpy(s, t);
}
// 判断空串
int StringEmpty(const String s) {
return strlen(s) == 0;
}
// 比较
int StringCompare(const String s, const String t) {
return strcmp(s, t);
}
// 求长度
int StringLength(const String s) {
return strlen(s);
}
// 清除
void StringClear(String s) {
s[0] = '\0';
}
// 连接
void StringConcat(String s, const String t) {
strcat(s, t);
}
// 子串
void StringSubString(String s, const String t, int pos, int len) {
strncpy(s, t + pos, len);
s[len] = '\0';
}
// 索引
int StringIndex(const String s, const String t) {
return strstr(s, t) - s;
}
// 替换
void StringReplace(String s, const String t, const String v) {
char *pos = s;
while ((pos = strstr(pos, t)) != NULL) {
strncpy(pos, v, strlen(v));
pos += strlen(v);
}
}
// 插入
void StringInsert(String s, int pos, const String t) {
char temp[MAXSIZE * 2];
strncpy(temp, s, pos);
temp[pos] = '\0';
strcat(temp, t);
strcat(temp, s + pos);
strcpy(s, temp);
}
// 删除
void StringDelete(String s, int pos, int len) {
char temp[MAXSIZE * 2];
strncpy(temp, s, pos);
temp[pos] = '\0';
strcat(temp, s + pos + len);
strcpy(s, temp);
}
// 测试代码
int main() {
String s;
StringAssign(s, "Hello, World!");
StringCopy(s, "Hello");
printf("Length of string: %d\n", StringLength(s));
StringClear(s);
printf("String after clear: %s\n", s);
StringConcat(s, "Hello");
printf("String after concat: %s\n", s);
StringSubString(s, "World", 6, 5);
printf("Substring: %s\n", s);
printf("Index of 'Hello': %d\n", StringIndex(s, "Hello"));
StringReplace(s, "Hello", "Hi");
printf("String after replace: %s\n", s);
StringInsert(s, 0, "C++");
printf("String after insert: %s\n", s);
StringDelete(s, 0, 5);
printf("String after delete: %s\n", s);
return 0;
}
模式匹配算法：BF 算法、KMP 算法
1. BF 算法 (Brute-Force Algorithm)
BF 算法是最简单的模式匹配算法，其思想是逐个字符比较主串和子串，直到找到匹配的子串或比较完毕。
时间复杂度： O(nm)，其中 n 是主串长度，m 是子串长度。
缺点： 效率低，在最坏情况下需要进行 n*m 次比较。
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef char String[MAXSIZE + 1];
// BF 算法
int BF(const String s, const String t, int pos) {
int n = strlen(s);
int m = strlen(t);
int i = pos, j = 0;
while (i < n && j < m) {
if (s[i] == t[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
return j == m ? i - j : -1;
}
// 测试代码
int main() {
String s = "ABCDABD";
String t = "ABCDABDABCDABD";
printf("Position of substring: %d\n", BF(s, t, 0));
return 0;
}
KMP 算法 (Knuth-Morris-Pratt Algorithm)
KMP 算法是一种高效的模式匹配算法，其思想是利用子串的局部匹配信息，避免重复比较，提高效率。
时间复杂度： O(nm)，但在最坏情况下只需要 n+m-1 次比较。
优点： 效率高，且易于实现。
KMP 算法核心：
构建“部分匹配表” (Partial Match Table, PMT)，用于记录子串中每个位置之后的最长相同前后缀的长度。
模式匹配时，当出现不匹配时，利用 PMT 跳过一些不必要的比较，直接将模式串的指针跳到 PMT 记录的位置。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef char String[MAXSIZE + 1];
// 构建 PMT
void BuildPMT(const String t, int *pmt, int m) {
int len = 0;
pmt[0] = 0;
for (int i = 1; i < m; ++i) {
while (len > 0 && t[len] != t[i]) {
len = pmt[len - 1];
}
if (t[len] == t[i]) {
len++;
}
pmt[i] = len;
}
}
// KMP 算法
int KMP(const String s, const String t, int pos) {
int n = strlen(s);
int m = strlen(t);
int i = pos, j = 0;
while (i < n && j < m) {
if (s[i] == t[j]) {
i++;
j++;
} else {
if (j != 0) {
j = pmt[j - 1];
} else {
i++;
}
}
}
return j == m ? i - j : -1;
}
// 测试代码
int main() {
String s = "ABCDABD";
String t = "ABCDABDABCDABD";
int pmt[MAXSIZE];
BuildPMT(t, pmt, strlen(t));
printf("Position of substring: %d\n", KMP(s, t, 0));
return 0;
}
数组
定义
数组是存储在连续内存空间中，具有相同数据类型的一组元素的集合。数组是一种基本的数据结构，在 C 语言中非常重要。
数组定义语法：
数据类型 数组名[长度];
数据类型： 可以是任何基本数据类型，例如 int、float、char 等，也可以是自定义的数据类型，例如结构体、枚举等。
数组名： 数组变量的名称，由程序员指定。
长度： 数组中元素的个数，必须是一个正整数。
例如：
int arr[10]; // 定义一个长度为 10 的整型数组
float numbers[5]; // 定义一个长度为 5 的浮点型数组
char letters[26]; // 定义一个长度为 26 的字符数组
数组元素访问：
数组元素通过下标访问，下标从 0 开始。
例如：arr[0] 表示数组的第一个元素，arr[3] 表示数组的第四个元素。
数组初始化：
可以在定义数组时直接初始化数组元素。
例如：
int arr[5] = {1, 2, 3, 4, 5}; // 初始化整型数组
float numbers[] = {1.1, 2.2, 3.3}; // 初始化浮点型数组
如果不进行初始化，数组元素的值将被初始化为 0 或空字符，具体取决于数据类型。
数组的特点：
随机访问： 可以通过下标直接访问数组中的任何元素，访问效率高。
连续存储： 数组元素存储在连续的内存空间中，便于内存管理。
静态分配： 数组的大小在编译时确定，无法动态扩展。
数组的用途：
存储大量数据，例如整数数组、浮点数数组、字符数组等。
实现各种数据结构，例如线性表、栈、队列、树等。
总结
数组是 C 语言中非常基础且重要的数据结构，用于存储和管理大量数据。掌握数组的定义、访问和初始化等操作，是进行 C 语言程序设计的基础。
存储结构：顺序存储
顺序存储结构的实现：
在 C 语言中，可以使用以下方式实现数组的顺序存储结构：
#define ARRAY_SIZE 100 // 定义数组的大小
// 定义一个整型数组
int array[ARRAY_SIZE];
// 初始化数组
for (int i = 0; i < ARRAY_SIZE; ++i) {
array[i] = 0; // 将数组元素初始化为 0
}
// 访问数组元素
int element = array[5]; // 访问数组的第 6 个元素（下标从 0 开始）
特殊矩阵的压缩存储
特殊矩阵是指具有特定结构或特定元素分布的矩阵，这种矩阵在压缩存储时可以采用不同的方法来减少存储空间的需求。以下是几种常见的特殊矩阵及其压缩存储方法：
对称矩阵：如果一个矩阵的对称轴是主对角线，则可以只存储矩阵的一半，因为矩阵的上三角或下三角是可以通过对称性计算得到的。
上三角矩阵：如果一个矩阵的所有元素都位于主对角线及其以上，则可以只存储上三角部分，并通过公式计算下三角部分。
下三角矩阵：如果一个矩阵的所有元素都位于主对角线及其以下，则可以只存储下三角部分，并通过公式计算上三角部分。
三角矩阵：如果一个矩阵同时是上三角矩阵和下三角矩阵，则可以只存储主对角线及其两侧的部分。
对角矩阵：如果一个矩阵的所有非对角线元素都是 0，则可以只存储对角线上的元素。
稀疏矩阵：如果矩阵中大部分元素都是 0，则可以使用稀疏矩阵的压缩存储方法，例如三元组表（Triplets）或十字链表（Crux List）。
三元组表：
三元组表是稀疏矩阵的一种压缩存储方法，它包含三个数组：
I：存储非零元素在行向量中的位置。
J：存储非零元素在列向量中的位置。
V：存储非零元素的值。
例如，对于矩阵：
0 1 0 0 4 0
0 0 5 0 0 6
0 0 0 7 0 0
0 0 0 0 8 0
0 0 0 0 0 9
0 0 0 0 0 0
其三元组表表示为：
I = [0, 1, 3, 5, 7, 9]
J = [1, 2, 4, 5, 6, 7]
V = [1, 5, 4, 6, 8, 9]
十字链表：
十字链表是另一种稀疏矩阵的压缩存储方法，它包含两个数组：
ROW：存储非零元素所在的行号。
COL：存储非零元素所在的列号。
例如，对于矩阵：
0 1 0 0 4 0
0 0 5 0 0 6
0 0 0 7 0 0
0 0 0 0 8 0
0 0 0 0 0 9
0 0 0 0 0 0
其十字链表表示为：
ROW = [1, 2, 4, 5, 6, 7, 9]
COL = [1, 2, 4, 5, 6, 7, 8]
广义表
定义
广义表（Generalized List）是列表的一种扩展，它在列表的基础上增加了一层抽象，允许列表的元素本身也可以是列表。广义表的概念在 Lisp 语言中尤为重要，因为 Lisp 语言使用列表来表示数据，而列表可以包含其他列表，形成嵌套结构。
在广义表的定义中，一个元素可以是单个值（称为原子），也可以是一个子列表。广义表由原子和子列表组成，子列表也可以是广义表，形成嵌套的列表结构。
广义表的表示：
广义表通常使用前缀表示法（prefix notation）或后缀表示法（postfix notation）来表示。在 Lisp 语言中，广义表通常使用括号来表示，括号内的元素可以是原子或子列表。
例子：
(a b (c d (e f)))
在这个例子中，(a b (c d (e f))) 是一个广义表，它包含三个元素：
原子 a
原子 b
子列表 (c d (e f))，它本身也是一个广义表
广义表的特性：
嵌套性：广义表可以嵌套其他广义表，形成多层的列表结构。
可变性：广义表的大小可以在运行时动态变化，即可以添加或删除元素。
递归性：广义表的定义和操作可以递归地进行，即广义表可以包含自身。
广义表的应用：
广义表在数据表示和算法实现中非常有用，尤其是在函数式编程和 Lisp 语言中。它允许程序员以一种直观和自然的方式表示和处理复杂的数据结构，如列表、树和图等。
总结：
广义表是列表的一种扩展，它允许列表的元素本身也可以是列表，形成嵌套的列表结构。
存储结构
广义表的存储结构可以根据不同的编程语言和实现需求而有所不同。以下是一些常见的广义表存储结构：
数组：
优点：实现简单，随机访问效率高。
缺点：内存利用率低，动态扩展困难。
示例：在 C 语言中，可以使用二维数组来表示广义表，其中每个子列表对应一个二维数组。
链表：
优点：内存利用率高，动态扩展容易。
缺点：随机访问效率较低，需要从头节点开始遍历。
示例：在 C 语言中，可以使用链表（如单向链表、双向链表）来表示广义表，其中每个节点包含一个指向子列表的指针。
栈和队列：
优点：操作效率高，适合实现广义表的递归操作。
缺点：内存利用率较低，不适用于存储大量元素。
示例：在 Lisp 语言中，广义表的递归操作通常使用栈来实现。
前缀表示法：
优点：直观，易于理解和实现。
缺点：存储效率低，需要额外的存储空间来表示括号。
示例：在 Lisp 语言中，广义表通常使用前缀表示法，即括号表示列表的开始和结束。
后缀表示法：
优点：存储效率高，不需要额外的存储空间来表示括号。
缺点：实现复杂，不易于理解和实现。
示例：在某些编程语言中，后缀表示法用于存储广义表，其中操作符和操作数按照操作顺序排列。
总结：
广义表的存储结构可以根据应用场景和需求选择合适的方式。数组适合静态存储和随机访问，链表适合动态存储和高效操作，栈和队列适合递归操作，前缀表示法直观易实现，后缀表示法存储效率高但实现复杂。在实际应用中，可以根据具体情况选择合适的存储结构。
绪论
研究内容：非数值计算程序设计中的操作对象、关系和操作
基本概念和术语：
数据、数据元素、数据项、数据对象
数据元素 (Data Element): 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。例如：
学生信息表中的一条记录
二叉树中的一个节点
图中的一个顶点
数据项 (Data Item): 是组成数据元素的、有独立含义的、不可分割的最小单位。例如：
学生信息表中的学号、姓名、性别等
二叉树节点中的数据域
图中顶点的属性
数据对象 (Data Object): 是性质相同的数据元素的集合。例如：
整数集合
字母字符集合
学生信息表
数据 (Data): 指客观事物的符号表示，是所有能输入到计算机中并被程序处理的符号的总称。例如：
数学计算中用到的整数和实数
文本编辑中用到的字符串
多媒体程序处理的图形、图像、声音及动画等
数据结构：逻辑结构和存储结构
逻辑结构：
定义： 从逻辑关系上描述数据元素之间的相互关系，独立于计算机的存储方式。
特点： 反映数据的本质特征和运算规则，与数据的物理存储无关。
类型：
集合结构： 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，班级和学生之间的关系。
线性结构： 数据元素之间存在一对一的关系。例如，线性表、栈、队列、字符串、数组。
树结构： 数据元素之间存在一对多的关系。例如，二叉树、树状结构。
图结构： 数据元素之间存在多对多的关系。例如，网络图、社交网络。
存储结构：
定义： 数据对象在计算机中的存储表示，也称为物理结构。
特点： 将数据对象存储到计算机时，需要存储数据元素本身和它们之间的关系。
类型：
顺序存储结构： 利用数组存储数据元素，数据元素之间通过元素在存储器中的相对位置来表示关系。例如，顺序表。
链式存储结构： 利用指针存储数据元素，每个数据元素包含数据和指向下一个数据元素的指针。例如，链表。
定义： 数据对象在计算机中的存储表示，也称为物理结构。
特点： 将数据对象存储到计算机时，需要存储数据元素本身和它们之间的关系。
类型：
顺序存储结构： 利用数组存储数据元素，数据元素之间通过元素在存储器中的相对位置来表示关系。例如，顺序表。
链式存储结构： 利用指针存储数据元素，每个数据元素包含数据和指向下一个数据元素的指针。例如，链表。
数据类型和抽象数据类型 (ADT)
数据类型：
定义： 高级程序设计语言中的一个基本概念，指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
特点：
值的集合： 数据类型定义了数据可能的取值范围。
操作集合： 数据类型定义了可以对该数据类型进行的一组操作，例如，加法、减法、比较等。
例子：
基本数据类型： 整型 (int)、实型 (float)、字符型 (char) 等。
构造数据类型： 数组、结构体、指针等。
作用： 数据类型为程序设计提供了更高级的数据抽象，方便了数据的描述和处理。
抽象数据类型 (ADT)：
定义： 由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
特点：
数据对象： ADT 定义了数据对象的组成和结构。
数据关系： ADT 定义了数据对象之间的关系。
基本操作： ADT 定义了可以对该数据对象进行的一组基本操作。
例子：
线性表 (List): 由一系列元素组成，元素之间存在线性关系。
栈 (Stack): 一种特殊的线性表，只允许在表的一端进行插入和删除操作。
队列 (Queue): 一种特殊的线性表，只允许在表的一端进行插入操作，在另一端进行删除操作。
作用： ADT 提供了更高级的数据抽象，将数据和操作封装在一起，隐藏了数据的具体实现细节，方便了程序设计和维护。
抽象数据类型的表示与实现
表示：
逻辑表示： 使用伪代码或自然语言描述 ADT 的数据对象、数据关系和基本操作。
物理表示： 选择合适的存储结构来实现 ADT，例如，顺序存储结构、链式存储结构等。
实现：
类： 在面向对象编程语言中，可以使用类来表示 ADT，类中包含数据成员和成员函数，数据成员对应 ADT 的数据对象，成员函数对应 ADT 的基本操作。
结构体和函数： 在 C 语言中，可以使用结构体和函数来表示 ADT，结构体中包含数据成员，函数中包含 ADT 的基本操作。
其他方法： 可以使用其他方法来实现 ADT，例如，使用表驱动的方法、使用模板等。
例子： 复数 ADT
定义： 复数由实部和虚部组成。
数据对象： {实部, 虚部}
数据关系： 实部和虚部之间存在加法、减法、乘法、除法等运算关系。
基本操作： 创建复数、获取实部、获取虚部、复数加法、复数减法等。
typedef struct {
float realPart;
float imagPart;
} Complex;
Complex createComplex(float real, float imag) {
Complex c;
c.realPart = real;
c.imagPart = imag;
return c;
}
float getReal(Complex c) {
return c.realPart;
}
float getImag(Complex c) {
return c.imagPart;
}
Complex addComplex(Complex c1, Complex c2) {
Complex sum;
sum.realPart = c1.realPart + c2.realPart;
sum.imagPart = c1.imagPart + c2.imagPart;
return sum;
}
算法和算法分析：
算法的定义及特性
算法是解决特定问题的操作序列，它具有以下五个重要特性：
1. 有穷性：
算法必须总是在执行有限步后结束。
每一步操作必须在有限时间内完成。
2. 确定性：
对于每种情况下所应执行的操作，算法中都有确切的规定，不会产生歧义。
算法的执行者或阅读者都能明确其含义和执行方式。
3. 可行性：
算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
算法能够有效地解决特定问题。
4. 输入：
算法可以有零个或多个输入。
输入可以通过形参传递给算法。
5. 输出：
算法可以有一个或多个输出。
输出是算法执行结果，可以通过返回值或引用传递给调用者。
评价算法优劣的标准：正确性、可读性、健壮性、高效性
1. 正确性：
算法在合理的数据输入下，能够在有限的运行时间内得到正确的结果。
算法能够有效地解决特定问题。
2. 可读性：
算法易于人们理解和相互交流。
算法清晰、简洁，没有歧义。
3. 健壮性：
当输入的数据非法时，算法能适当地做出正确反应或进行相应处理，不会产生错误的结果。
算法能够处理各种异常情况。
4. 高效性：
算法设计合理，执行效率高。
算法的时间复杂度和空间复杂度较低。
关系：
正确性是算法的最基本要求，没有正确性的算法是没有意义的。
可读性和健壮性是算法的次要要求，但它们对于算法的维护和扩展非常重要。
高效性是算法的重要要求，它决定了算法在实际应用中的性能。
算法的时间复杂度：渐近时间复杂度 (时间复杂度)
定义：
渐近时间复杂度是算法执行时间与问题规模之间的增长关系。
它表示随着问题规模增大，算法执行时间的增长趋势。
数学符号：
使用大 O 符号 (O) 表示渐近时间复杂度。
例子：
算法 A：当问题规模 n 增大时，算法 A 的执行时间增长速度与 n 的平方成正比，即 O(n^2)。
算法 B：当问题规模 n 增大时，算法 B 的执行时间增长速度与 n 的对数成正比，即 O(log n)。
总结： 时间复杂度是衡量算法效率的重要指标，它反映了算法执行时间随问题规模增长的趋势。选择合适的时间复杂度分析方法可以帮助我们更好地理解和评估算法的性能。
计算方法：
基本步骤：
找出算法中所有基本语句的执行次数。
计算基本语句执行次数之和。
取基本语句执行次数之和的数量级，用大 O 符号表示。
注意事项：
忽略低次项和最高次项的系数。
忽略常数因子。
例子：
线性搜索： 在长度为 n 的数组中查找一个元素，最坏情况下需要比较 n 次，因此时间复杂度为 O(n)。
二分搜索： 在有序数组中查找一个元素，最坏情况下需要比较 log2 n 次，因此时间复杂度为 O(log n)。
常用时间复杂度：
O(1)：常量阶，算法执行时间与问题规模无关。
O(log n)：对数阶，算法执行时间随问题规模对数增长。
O(n)：线性阶，算法执行时间随问题规模线性增长。
O(n^2)：平方阶，算法执行时间随问题规模平方增长。
O(2^n)：指数阶，算法执行时间随问题规模指数增长。
算法的空间复杂度：渐近空间复杂度
算法的空间复杂度是指算法执行过程中所需的存储空间随问题规模增长的趋势。它通常使用渐近空间复杂度来表示，也称为空间复杂度。
定义：
渐近空间复杂度是算法所需存储空间与问题规模之间的增长关系。
它表示随着问题规模增大，算法所需存储空间的变化趋势。
数学符号：
使用大 O 符号 (O) 表示渐近空间复杂度。
例子：
算法 A：当问题规模 n 增大时，算法 A 所需存储空间增长速度与 n 的平方成正比，即 O(n^2)。
算法 B：当问题规模 n 增大时，算法 B 所需存储空间增长速度与 n 的对数成正比，即 O(log n)。
总结： 空间复杂度是衡量算法效率的重要指标，它反映了算法所需存储空间随问题规模增长的趋势。选择合适的空间复杂度分析方法可以帮助我们更好地理解和评估算法的性能。
计算方法：
基本步骤：
找出算法中所有辅助空间的使用情况。
计算辅助空间大小与问题规模之间的关系。
取辅助空间大小的数量级，用大 O 符号表示。
注意事项：
忽略低次项和最高次项的系数。
忽略常数因子。
例子：
冒泡排序： 最坏情况下需要使用一个长度为 n 的数组来存储临时数据，因此空间复杂度为 O(n)。
快速排序： 最坏情况下需要使用一个长度为 n 的数组来存储临时数据，因此空间复杂度为 O(n)。
二分搜索： 只需要使用常数空间来存储临时变量，因此空间复杂度为 O(1)。
常用空间复杂度：
O(1)：常量阶，算法所需存储空间与问题规模无关。
O(log n)：对数阶，算法所需存储空间随问题规模对数增长。
O(n)：线性阶，算法所需存储空间随问题规模线性增长。
O(n^2)：平方阶，算法所需存储空间随问题规模平方增长。
O(2^n)：指数阶，算法所需存储空间随问题规模指数增长。
线性表
定义和特点
线性表是最基本且最常用的线性结构，它由一系列元素组成，元素之间存在线性关系。线性表的特点如下：
1. 元素个数：
线性表可以包含零个或多个元素。
线性表中元素的个数称为线性表的长度。
2. 元素关系：
除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和一个后继。
数据元素之间存在一对一的关系。
3. 操作：
访问： 可以随机访问线性表中任意位置的元素。
插入： 可以在线性表的任意位置插入新的元素。
删除： 可以删除线性表中的任意元素。
遍历： 可以按顺序访问线性表中的所有元素。
案例引入：一元多项式运算、稀疏多项式运算、图书信息管理系统
类型定义：抽象数据类型
ADT List {
数据对象: D = {a1, a2, ..., an | ai ∈ E, i = 1, 2, ..., n, n ≥ 0}
数据关系: R = {<ai, ai+1> | ai ∈ E, i = 1, 2, ..., n-1}
基本操作:
InitList(&L): 构造一个空的线性表 L
DestroyList(&L): 销毁线性表 L
ClearList(&L): 将线性表 L 重置为空表
ListEmpty(L): 判断线性表 L 是否为空
ListLength(L): 返回线性表 L 的长度
GetElem(L, i, &e): 获取线性表 L 中第 i 个元素的值
LocateElem(L, e): 查找线性表 L 中第一个与 e 相等的元素的位置
PriorElem(L, cur_e, &pre_e): 获取线性表 L 中 cur_e 元素的前驱元素
NextElem(L, cur_e, &next_e): 获取线性表 L 中 cur_e 元素的后继元素
ListInsert(&L, i, e): 在线性表 L 中第 i 个位置之前插入元素 e
ListDelete(&L, i): 删除线性表 L 中第 i 个元素
TraverseList(L): 遍历线性表 L
}
总结： 线性表的 ADT 定义了线性表的数据对象、数据关系和基本操作，它为线性表的设计和实现提供了规范和指导
顺序表示和实现：
顺序存储结构：顺序表
顺序存储结构是一种常用的存储结构，用于实现线性表。在顺序存储结构中，线性表的元素按照逻辑顺序依次存储在一段连续的存储单元中。这种存储方式被称为顺序表。
顺序表的特点：
连续的存储空间： 顺序表中的元素存储在一块连续的存储空间中，可以是数组或者是预先分配的一段内存。
随机访问： 顺序表允许随机访问，即可以通过索引直接访问表中的任一元素。
存储密度高： 由于元素紧凑存储，存储密度比链式存储结构高。
插入和删除操作可能需要移动元素： 在顺序表中插入或删除元素时，可能需要移动大量元素以保持元素的连续性。
顺序表中基本操作的实现：初始化、取值、查找、插入、删除
初始化： 创建一个空的顺序表。
void InitList(SeqList *L) {
L->data = (ElementType *)malloc(MAXSIZE * sizeof(ElementType));
if (!L->data) exit(OVERFLOW);
L->length = 0;
}
获取元素： 获取顺序表中指定位置的元素。
int GetElem(SeqList L, int i, ElementType *e) {
if (i < 1 || i > L.length) return ERROR;
*e = L.data[i - 1];
return OK;
}
销毁： 释放顺序表的存储空间。
void DestroyList(SeqList *L) {
free(L->data);
L->length = 0;
}
查找元素： 在顺序表中查找与给定值相等的元素。
int LocateElem(SeqList L, ElementType e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) return i + 1;
}
return 0;
}
清空： 将顺序表置为空表。
void ClearList(SeqList *L) {
L->length = 0;
}
插入元素： 在顺序表的指定位置插入一个新元素。
int ListInsert(SeqList *L, int i, ElementType e) {
if (i < 1 || i > L->length + 1) return ERROR;
if (L->length == MAXSIZE) return ERROR;
for (int j = L->length - 1; j >= i - 1; j--) {
L->data[j + 1] = L->data[j];
}
L->data[i - 1] = e;
L->length++;
return OK;
}
判断是否为空： 判断顺序表是否为空。
int ListEmpty(SeqList L) {
return L.length == 0;
}
删除元素： 删除顺序表中指定位置的元素。
int ListDelete(SeqList *L, int i) {
if (i < 1 || i > L->length) return ERROR;
for (int j = i; j <= L->length - 1; j++) {
L->data[j - 1] = L->data[j];
}
L->length--;
return OK;
}
求长度： 返回顺序表的长度。
int ListLength(SeqList L) {
return L.length;
}
遍历： 遍历顺序表，对每个元素执行特定操作。
void TraverseList(SeqList L) {
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
优点：
随机访问效率高：顺序表允许随机访问，即通过索引直接访问表中的任一元素，其时间复杂度为 O(1)。
内存利用率高：顺序表中的元素紧密排列，不需要额外的存储空间来存储指针，因此内存利用率较高。
插入和删除操作高效：顺序表的插入和删除操作可以在 O(1) 的时间复杂度内完成，特别是当操作的是数组尾部元素时。
数据元素有序：顺序表中的数据元素按照逻辑顺序依次存储，可以方便地进行排序和查找操作。
空间分配灵活：可以根据实际需要动态地分配数组的大小，以适应不同的数据规模。
缺点：
插入和删除操作开销大：当插入或删除操作需要移动大量元素时，其时间复杂度会退化为 O(n)，因为需要移动元素以保持数组的连续性。
空间分配可能浪费：如果数组分配过大，可能会浪费存储空间；如果数组分配过小，可能会频繁进行扩容操作，导致性能下降。
数组访问需要考虑边界条件：在顺序表中访问元素时，需要检查索引是否在数组的有效范围内，以避免越界访问。
数组索引不支持负数：顺序表中的索引通常是从 0 开始的非负整数，不支持负数索引。
数组元素类型限制：顺序表中的元素类型必须是固定大小的，不支持动态类型的元素。
总结：顺序表的优点在于其高效的随机访问能力和高内存利用率，缺点在于插入和删除操作的开销大以及数组访问的限制。在实际应用中，需要根据具体的需求和场景来选择合适的数据结构。
链式表示和实现：
单链表：定义和表示、基本操作的实现：初始化、取值、查找、插入、删除、创建单链表
单链表是一种链式存储结构，它由一系列节点组成，每个节点包含数据域和指针域。在单链表中，每个节点只指向下一个节点，形成一个单向的链式结构。
单链表的定义和表示：
typedef struct Node {
ElementType data; // 数据域
struct Node *next; // 指针域，指向下一个节点
} Node, *LinkList;
初始化： 创建一个空的单链表。
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if (!*L) exit(OVERFLOW);
(*L)->next = NULL;
}
查找元素： 在单链表中查找与给定值相等的元素。
int LocateElem(LinkList L, ElementType e) {
LinkList p = L->next;
int i = 1;
while (p && p->data != e) {
p = p->next;
i++;
}
if (!p) return 0;
return i;
}
删除元素： 删除单链表中指定位置的元素。
int ListDelete(LinkList *L, int i, ElementType *e) {
LinkList p = *L, *q;
int j;
if (i < 1) return ERROR;
for (j = 1, p = *L; p && j < i; j++) p = p->next;
if (!p || j > i) return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
获取单链表中指定位置的元素。
int GetElem(LinkList L, int i, ElementType *e) {
LinkList p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) return ERROR;
*e = p->data;
return OK;
}
插入元素： 在单链表的指定位置插入一个新元素。
int ListInsert(LinkList *L, int i, ElementType e) {
LinkList p = *L, *s;
int j;
if (i < 1) return ERROR;
for (j = 1; p && j < i; j++) p = p->next;
if (!p) return ERROR;
s = (LinkList)malloc(sizeof(Node));
if (!s) exit(OVERFLOW);
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
创建单链表： 从一组元素创建一个单链表。
void CreateList(LinkList *L, ElementType a[], int n) {
InitList(L);
for (int i = 0; i < n; i++) {
ListInsert(L, i + 1, a[i]);
}
}
创建单链表的示例：
int main() {
ElementType a[] = {1, 2, 3, 4, 5};
LinkList L;
CreateList(&L, a, sizeof(a) / sizeof(a[0]));
// 后续可以进行其他操作，如遍历、查找等
return 0;
}
循环链表
循环链表是一种特殊的链表，它的最后一个节点的指针不是指向 NULL，而是指向链表的头部，形成一个环状的结构。在循环链表中，从链表的任何一个节点出发，都可以找到链表中的其他所有节点。
循环链表的定义和表示：
循环链表的定义与单链表类似，但最后一个节点的指针指向链表的头部。
typedef struct Node {
ElementType data; // 数据域
struct Node *next; // 指针域，指向下一个节点
} Node, *LinkList;
初始化： 创建一个空的循环链表。
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if (!*L) exit(OVERFLOW);
(*L)->next = (*L); // 头节点的指针指向自身
}
查找元素： 在循环链表中查找与给定值相等的元素。
int LocateElem(LinkList L, ElementType e) {
LinkList p = L->next;
while (p != L && p->data != e) {
p = p->next;
}
if (p == L) return 0;
return 1;
}
删除元素： 删除循环链表中指定位置的元素。
int ListDelete(LinkList *L, int i, ElementType *e) {
LinkList p = L->next;
int j;
if (i < 1) return ERROR;
for (j = 1, p = L->next; p != L && j < i; j++) p = p->next;
if (p == L || j > i) return ERROR;
LinkList q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
取值： 获取循环链表中指定位置的元素。
int GetElem(LinkList L, int i, ElementType *e) {
LinkList p = L->next;
int j = 1;
while (p != L && j < i) {
p = p->next;
j++;
}
if (p == L || j > i) return ERROR;
*e = p->data;
return OK;
}
插入元素： 在循环链表的指定位置插入一个新元素。
int ListInsert(LinkList *L, int i, ElementType e) {
LinkList p = L->next;
int j;
if (i < 1) return ERROR;
for (j = 1; p && j < i; j++) p = p->next;
if (!p || j > i) return ERROR;
LinkList s = (LinkList)malloc(sizeof(Node));
if (!s) exit(OVERFLOW);
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
创建循环链表： 从一组元素创建一个循环链表。
void CreateList(LinkList *L, ElementType a[], int n) {
InitList(L);
for (int i = 0; i < n; i++) {
ListInsert(L, i + 1, a[i]);
}
(*L)->next = (*L); // 最后一个节点的指针指向头节点
}
双向链表
双向链表是一种链式存储结构，它除了包含单链表中的数据域和指针域之外，还包含一个指向前一个节点的指针域。在双向链表中，每个节点都包含两个指针，一个指向前一个节点，一个指向下一个节点，这样可以从任一节点出发，双向遍历整个链表。
双向链表的定义和表示：
typedef struct DNode {
ElementType data; // 数据域
struct DNode *prior; // 指向前一个节点的指针
struct DNode *next; // 指向下一个节点的指针
} DNode, *DLinkList;
在双向链表中，通常会设置一个头节点，头节点的指针域指向链表的第一个有效节点，而最后一个节点的指针域指向头节点。
初始化： 创建一个空的双向链表。
void InitList(DLinkList *L) {
*L = (DLinkList)malloc(sizeof(DNode));
if (!*L) exit(OVERFLOW);
(*L)->prior = (*L); // 头节点的指针域和前一个指针域都指向自身
(*L)->next = (*L);
}
查找元素： 在双向链表中查找与给定值相等的元素。
int LocateElem(DLinkList L, ElementType e) {
DLinkList p = L->next;
while (p != L && p->data != e) {
p = p->next;
}
if (p == L) return 0;
return 1;
}
创建双向链表： 从一组元素创建一个双向链表。
void CreateList(DLinkList *L, ElementType a[], int n) {
InitList(L);
for (int i = 0; i < n; i++) {
ListInsert
取值： 获取双向链表中指定位置的元素。
int GetElem(DLinkList L, int i, ElementType *e) {
DLinkList p = L->next;
int j = 1;
while (p != L && j < i) {
p = p->next;
j++;
}
if (p == L || j > i) return ERROR;
*e = p->data;
return OK;
}
插入元素： 在双向链表的指定位置插入一个新元素。
int ListInsert(DLinkList *L, int i, ElementType e) {
DLinkList p = *L;
int j;
if (i < 1) return ERROR;
for (j = 1; p && j < i; j++) p = p->next;
if (!p || j > i) return ERROR;
DLinkList s = (DLinkList)malloc(sizeof(DNode));
if (!s) exit(OVERFLOW);
s->data = e;
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;
return OK;
}
删除元素： 删除双向链表中指定位置的元素。
int ListDelete(DLinkList *L, int i, ElementType *e) {
DLinkList p = *L;
int j;
if (i < 1) return ERROR;
for (j = 1, p = *L; p && j < i; j++) p = p->next;
if (p == *L || j > i) return ERROR;
DLinkList q = p->next;
p->next = q->next;
q->next->prior = p;
*e = q->data;
free(q);
return OK;
}
优点：
动态分配：链表可以动态地分配内存，可以根据需要动态地增加或减少节点的数量。
插入和删除操作方便：链表的插入和删除操作可以在常数时间内完成，因为只需要修改指针即可，而不需要移动其他元素。
无大小限制：链表的大小不受内存中连续空间的限制，可以无限扩展。
数据元素的顺序可以任意：链表中数据元素的顺序可以根据需要任意排列，不需要在内存中连续存储。
可以方便地实现双向链表、循环链表等变体：通过在节点中添加额外的指针，可以实现具有双向链接、循环链接等特性的链表。
缺点：
随机访问效率低：链表中的数据元素不能像数组那样随机访问，需要从头节点开始逐个节点遍历到目标节点，因此随机访问的时间复杂度为 O(n)。
空间利用率低：链表中的每个节点除了包含数据域外，还需要额外存储指针域，因此相对于数组，链表的空间利用率较低。
插入和删除操作开销大：虽然单个插入和删除操作的时间复杂度为 O(1)，但是这些操作可能会导致链表结构的改变，从而影响后续操作的性能。
需要额外的内存空间：链表中的每个节点都需要额外的内存空间来存储指针域，这可能导致内存浪费。
链表长度难以直接获取：链表的长度需要通过遍历链表来计算，无法像数组那样直接获取。
总结：链表的优点在于其动态性和方便的插入删除操作，缺点在于随机访问效率低和空间利用率低。选择使用链表还是数组取决于具体应用场景的需求。
顺序表和链表的比较：空间性能、时间性能、适用情况
空间性能：
顺序表：在内存中占用连续的存储空间，空间利用率高，但是可能存在一定的空间浪费，特别是在顺序表的大小远小于其分配空间时。
链表：每个节点包含数据域和指针域，需要额外的存储空间来存储指针。空间利用率较低，但是没有存储空间浪费的问题。
时间性能：
顺序表：随机访问的时间复杂度为 O(1)，插入和删除操作的时间复杂度为 O(n)，因为需要移动大量元素以保持顺序表的连续性。
链表：随机访问的时间复杂度为 O(n)，因为需要从头节点开始逐个节点遍历到目标节点。插入和删除操作的时间复杂度为 O(1)，因为不需要移动其他元素，只需修改指针即可。
顺序表：在内存中占用连续的存储空间，空间利用率高，但是可能存在一定的空间浪费，特别是在顺序表的大小远小于其分配空间时。
链表：每个节点包含数据域和指针域，需要额外的存储空间来存储指针。空间利用率较低，但是没有存储空间浪费的问题。
时间性能：
顺序表：随机访问的时间复杂度为 O(1)，插入和删除操作的时间复杂度为 O(n)，因为需要移动大量元素以保持顺序表的连续性。
链表：随机访问的时间复杂度为 O(n)，因为需要从头节点开始逐个节点遍历到目标节点。插入和删除操作的时间复杂度为 O(1)，因为不需要移动其他元素，只需修改指针即可。
适用情况：
顺序表：适用于频繁进行随机访问的场景，例如数组。
链表：适用于频繁进行插入和删除操作的场景，例如动态数组、栈和队列。
总结：
顺序表和链表各有优缺点，选择哪种数据结构取决于具体的需求。顺序表的空间利用率高，随机访问速度快，适用于需要频繁随机访问的场景；链表的空间利用率低，随机访问速度慢，适用于需要频繁进行插入和删除操作的场景。
线性表的应用：合并
合并操作的应用场景：
文件合并：在文件处理中，合并操作可以将多个文件的内容合并到一个文件中，常用于文本文件的合并。
数据集合并：在数据库操作中，合并操作可以将多个数据集合并为一个数据集，常用于数据仓库中的数据整合。
排序算法：在排序算法中，如归并排序（Merge Sort），合并操作是将两个有序子序列合并为一个有序序列的过程。
数据流处理：在数据流处理中，合并操作可以将多个数据流合并为一个数据流，常用于处理实时数据。
网络通信：在网络通信中，合并操作可以将多个网络包合并成一个更大的网络包，常用于数据压缩和传输。
树和二叉树
定义
树和二叉树是计算机科学中常见的数据结构，它们在存储和组织数据方面具有重要的应用。
树 (Tree)：
定义：树是一种非线性的数据结构，它由节点组成，每个节点包含数据域和指向其他节点的指针域。在树中，一个节点可以有多个子节点，但每个子节点只能有一个父节点。树有一个特殊的节点称为根节点，它是树的入口点，没有父节点。
特点：
层次结构：树是一种层次结构，节点之间通过父子关系连接。
无环路：树中不存在循环，每个节点最多有一个父节点。
子节点数量：一个节点可以有多个子节点，但子节点之间没有顺序。
二叉树 (Binary Tree)：
定义：二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，节点之间存在特定的顺序关系。
特点：
层次结构：二叉树是一种层次结构，节点之间通过父子关系连接。
无环路：二叉树中不存在循环，每个节点最多有一个父节点。
子节点数量：一个节点最多有两个子节点，分别是左子节点和右子节点。
节点顺序：在二叉树中，左子节点的值小于或等于父节点的值，右子节点的值大于或等于父节点的值。
总结：树和二叉树是数据结构中的重要概念，它们在存储和组织数据方面具有重要的应用。树是一种非线性的数据结构，每个节点可以有多个子节点；而二叉树是一种特殊的树，每个节点最多有两个子节点，并且节点之间存在特定的顺序关系。
案例引入
树的应用案例：
组织结构：在企业或组织中，员工之间的关系可以通过树形结构来表示，根节点是组织的高层领导，子节点是下级员工。
文件系统：在计算机的文件系统中，文件和目录之间的关系可以用树形结构来表示，根目录位于顶层，子目录和文件位于下一层。
数据存储：在数据库中，关系型数据库中的表和表之间的关系可以用树形结构来表示，根节点是表，子节点是表之间的关系。
网络拓扑：在计算机网络中，节点和节点之间的关系可以用树形结构来表示，根节点是网络的中心节点，子节点是网络的边缘节点。
二叉树的应用案例：
排序和查找：二叉树可以用于实现高效的排序和查找操作。例如，二叉排序树（BST）是一种二叉树，其左子节点的值小于根节点的值，右子节点的值大于根节点的值。二叉查找树（BST）可以在 O(log n) 的时间复杂度内完成查找、插入和删除操作。
优先队列：二叉堆是一种特殊的二叉树，它可以用于实现优先队列。在优先队列中，最小（或最大）元素总是位于队列的顶部，可以在 O(log n) 的时间复杂度内完成插入和删除操作。
字符串匹配：Trie（发音为“try”）是一种树形结构，它用于实现高效的字符串匹配。在 Trie 中，每个节点代表一个字符，根节点不包含任何字符。通过 Trie，可以在 O(m) 的时间复杂度内完成字符串匹配，其中 m 是字符串的长度。
表达式树：在编译器中，表达式树是一种树形结构，它用于表示和简化数学表达式。在表达式树中，每个节点代表一个操作符或操作数，节点之间通过父子关系连接。
抽象数据类型定义
树的抽象数据类型定义：
ADT 树 (Tree) {
数据对象：
T = {r | r 是根节点，r 是任意节点的子节点}
节点的子节点数称为树的深度。
数据关系：
每个节点最多有一个父节点，除根节点外，每个节点有一个父节点。
每个节点可以有多个子节点。
基本操作：
InitTree(&T): 构造一个空的树。
DestroyTree(&T): 销毁树 T。
ClearTree(&T): 清空树 T。
TreeEmpty(T): 判断树 T 是否为空。
TreeDepth(T): 返回树 T 的深度。
Root(T): 返回树 T 的根节点。
Parent(T, p): 返回节点 p 的父节点。
Child(T, p): 返回节点 p 的子节点。
PrevSibling(T, p): 返回节点 p 的前一个兄弟节点。
NextSibling(T, p): 返回节点 p 的下一个兄弟节点。
InsertChild(T, p, c): 在节点 p 处插入子节点 c。
DeleteChild(T, p, c): 删除节点 p 的子节点 c。
TraverseTree(T): 遍历树 T。
}
二叉树的抽象数据类型定义：
ADT 二叉树 (Binary Tree) {
数据对象：
BT = {r | r 是根节点，r 的左子节点是二叉树的最小值节点，r 的右子节点是二叉树的最大值节点}
数据关系：
每个节点最多有两个子节点，分别称为左子节点和右子节点。
左子节点的值小于或等于父节点的值，右子节点的值大于或等于父节点的值。
基本操作：
InitTree(&BT): 构造一个空的二叉树。
DestroyTree(&BT): 销毁二叉树 BT。
ClearTree(&BT): 清空二叉树 BT。
TreeEmpty(BT): 判断二叉树 BT 是否为空。
TreeDepth(BT): 返回二叉树 BT 的深度。
Root(BT): 返回二叉树 BT 的根节点。
LeftChild(BT, p): 返回节点 p 的左子节点。
RightChild(BT, p): 返回节点 p 的右子节点。
InsertLeftChild(BT, p, c): 在节点 p 处插入左子节点 c。
InsertRightChild(BT, p, c): 在节点 p 处插入右子节点 c。
DeleteChild(BT, p, c): 删除节点 p 的子节点 c。
TraverseTree(BT): 遍历二叉树 BT。
}
性质和存储结构：二叉树的性质、二叉树的存储结构
二叉树的性质：
性质1：在二叉树中，任意节点的左子树不包含大于该节点值的任何节点。(排序树)
性质2：在二叉树中，任意节点的右子树不包含小于该节点值的任何节点。(排序树)
性质3：二叉树的每个节点最多有两个子节点。
性质4：二叉树的每个节点至少有 0 个或 1 个子节点。
性质5：二叉树可以是不平衡的，即节点的子节点数可能不相等。
性质6：二叉树可以是完全的，即所有节点都有两个子节点，除了叶子节点。
性质7：二叉树可以是满的，即所有节点都有两个子节点，包括叶子节点。
性质1：在二叉树中，任意节点的左子树不包含大于该节点值的任何节点。(排序树)
性质2：在二叉树中，任意节点的右子树不包含小于该节点值的任何节点。(排序树)
性质3：二叉树的每个节点最多有两个子节点。
性质4：二叉树的每个节点至少有 0 个或 1 个子节点。
性质5：二叉树可以是不平衡的，即节点的子节点数可能不相等。
性质6：二叉树可以是完全的，即所有节点都有两个子节点，除了叶子节点。
性质7：二叉树可以是满的，即所有节点都有两个子节点，包括叶子节点。
二叉树的存储结构：
顺序存储结构：使用一维数组来存储二叉树的所有节点。在这种结构中，数组的索引表示节点的层数和在该层中的位置。
链式存储结构：使用链表来存储二叉树的所有节点。每个节点包含数据域和两个指针域，分别指向其左子节点和右子节点。
线索化存储结构：在链式存储结构的基础上，通过添加额外的指针来表示节点的前驱和后继关系，使得不需要遍历整个链表就可以找到节点的直接前驱和后继。
总结：二叉树的性质决定了它的特殊性质，如节点值的大小关系，而存储结构则决定了二叉树在内存中的组织方式。顺序存储结构适合于静态的二叉树，而链式存储结构适合于动态的二叉树，因为它可以方便地进行插入和删除操作。
遍历二叉树和线索二叉树：遍历算法、线索化
遍历二叉树：
前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。
void PreOrder(BiTree T) {
if (T) {
visit(T->data); // 访问根节点
PreOrder(T->lchild); // 遍历左子树
PreOrder(T->rchild); // 遍历右子树
}
}
void InOrder(BiTree T) {
if (T) {
InOrder(T->lchild); // 遍历左子树
visit(T->data); // 访问根节点
InOrder(T->rchild); // 遍历右子树
}
}
void PostOrder(BiTree T) {
if (T) {
PostOrder(T->lchild); // 遍历左子树
PostOrder(T->rchild); // 遍历右子树
visit(T->data); // 访问根节点
}
}
线索化：
在链式存储结构的基础上，通过添加额外的指针来表示节点的前驱和后继关系，使得不需要遍历整个链表就可以找到节点的直接前驱和后继。
void Threading(BiTree T) {
if (T) {
T->lchild = Thread(T->lchild); // 线索化左子树
T->rchild = Thread(T->rchild); // 线索化右子树
if (!T->lchild) T->lchild = T; // 如果左子树为空，则将根节点指向自身
if (!T->rchild) T->rchild = T; // 如果右子树为空，则将根节点指向自身
if (!T->lchild) T->lchild = Thread(T->rchild); // 如果左子树为空，则将根节点的左子节点指向右子树
if (!T->rchild) T->rchild = Thread(T->lchild); // 如果右子树为空，则将根节点的右子节点指向左子树
}
}
在上面的代码中，Threading 函数实现了对二叉树进行线索化的操作。通过添加额外的指针，可以方便地找到节点的直接前驱和后继。
总结：遍历二叉树和线索化是二叉树操作中的重要部分。遍历二叉树可以按照不同的顺序访问所有节点，而线索化可以方便地找到节点的直接前驱和后继。在实际应用中，需要根据具体需求选择合适的方法。
树和森林
树（Tree）：
树是一种非线性的数据结构，它由节点组成，每个节点包含数据域和指向其他节点的指针域。在树中，一个节点可以有多个子节点，但每个子节点只能有一个父节点。树有一个特殊的节点称为根节点，它是树的入口点，没有父节点。
特点：
层次结构：树是一种层次结构，节点之间通过父子关系连接。
无环路：树中不存在循环，每个节点最多有一个父节点。
子节点数量：一个节点可以有多个子节点，但子节点之间没有顺序。
森林（Forest）：
森林是由多个树组成的集合，每个树都是独立的，没有共同的父节点。在森林中，每个树都至少有一个节点。
特点：
树集合：森林是由多个树组成的集合，每个树都是独立的。
子节点数量：每个树中的节点可以有多个子节点，但子节点之间没有顺序。
总结：树和森林是数据结构中的重要概念，它们在存储和组织数据方面具有重要的应用。树是一种非线性的数据结构，每个节点可以有多个子节点；而森林是由多个树组成的集合，每个树都是独立的。树和森林的概念和实现对于解决实际问题具有重要意义。
树转换为二叉树：
选择一个节点作为根节点：可以选择树的任一节点作为二叉树的根节点。
构建左子树和右子树：将根节点的所有子节点分为两组，分别构建左子树和右子树。左子树的所有节点都小于根节点的值，右子树的所有节点都大于根节点的值。
递归转换：对左子树和右子树分别进行上述步骤，直到所有节点都被转换为二叉树。
二叉树转换为树：
选择一个节点作为根节点：可以选择二叉树的任一节点作为树的根节点。
构建左子树和右子树：将根节点的左子节点和右子节点作为新树的子节点。
递归转换：对左子树和右子树分别进行上述步骤，直到所有节点都被转换为树。
二叉树转换为森林：
选择一个节点作为根节点：可以选择二叉树的任一节点作为森林的树。
构建左子树和右子树：将根节点的左子节点和右子节点作为新树的根节点。
递归转换：对左子树和右子树分别进行上述步骤，直到所有节点都被转换为森林。
树转换为森林：
选择一个节点作为森林的树：可以选择树的任一节点作为森林的树。
构建左子树和右子树：将根节点的左子节点和右子节点作为新森林的树。
递归转换：对左子树和右子树分别进行上述步骤，直到所有节点都被转换为森林。
哈夫曼树及其应用
哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，它由带权节点组成，树的带权路径长度是所有叶子节点的带权路径长度之和。哈夫曼树在数据压缩中有着广泛的应用，特别是在无损压缩算法中，如哈夫曼编码。
哈夫曼树的构建过程：
初始化：将所有字符按照出现的频率从小到大排序，并按照频率从高到低构建一个优先队列。
构建哈夫曼树：
从优先队列中取出两个频率最小的节点，合并成一个新节点，新节点的频率是两个节点的频率之和。
将新节点放回优先队列中。
重复步骤1和2，直到优先队列为空，此时剩下的节点就是哈夫曼树的根节点。
哈夫曼树的性质：
带权路径长度最短：哈夫曼树的带权路径长度是最短的，这意味着每个节点的路径长度与其频率成反比。
所有叶子节点都是字符：在哈夫曼树中，所有叶子节点都是原始字符，而内部节点是字符的组合。
树的结构：哈夫曼树的结构是一个二叉树，每个节点最多有两个子节点。
哈夫曼树的应用：
数据压缩：哈夫曼树在数据压缩中有着广泛的应用，特别是在无损压缩算法中。通过哈夫曼编码，可以将数据中出现频率高的字符编码为较短的序列，而出现频率低的字符编码为较长的序列，从而实现数据的压缩。
频率分析：哈夫曼树可以用于分析数据中各个字符的频率，从而了解数据的分布情况。
编码和传输：哈夫曼编码可以用于字符编码和传输，通过将字符编码为较短的序列，可以提高传输效率。
总结：哈夫曼树是一种带权路径长度最短的二叉树，它在数据压缩中有着广泛的应用。通过哈夫曼编码，可以将数据中出现频率高的字符编码为较短的序列，而出现频率低的字符编码为较长的序列，从而实现数据的压缩。哈夫曼树的概念和实现对于解决实际问题具有重要意义。
图
定义和基本术语
基本术语：
顶点（Vertex）：图中的基本元素，也称为节点。
边（Edge）：连接两个顶点的线段。
无向图（Undirected Graph）：图中任意两个顶点之间的边都是双向的。
有向图（Directed Graph）：图中任意两个顶点之间的边都是单向的。
自环（Self-Loop）：从顶点指向自身的边。
平行边（Parallel Edges）：连接同一个顶点的两条或多条边。
简单图（Simple Graph）：不包含自环和平行边的图。
加权图（Weighted Graph）：每条边都有一个权重，用于表示边的代价或长度。
无权图（Unweighted Graph）：每条边都没有权重，通常用于表示非加权图。
连通图（Connected Graph）：图中任意两个顶点之间都存在路径。
非连通图（Disconnected Graph）：图中存在至少两个顶点，它们之间没有路径。
完全图（Complete Graph）：一个连通图，其中任意两个不同顶点之间都存在边。
子图（Subgraph）：一个图是另一个图的子图，如果它包含另一个图的所有顶点和边。
路径（Path）：图中从顶点 s 到顶点 t 的连续边序列。
简单路径（Simple Path）：路径中不包含重复的顶点。
连通分量（Connected Component）：图中最大的连通子图。
边集（Edge Set）：图中所有边的集合。
顶点集（Vertex Set）：图中所有顶点的集合。
图的表示：
邻接矩阵（Adjacency Matrix）：一个二维数组，用于表示图中顶点之间的关系。
邻接表（Adjacency List）：一个数组，每个元素是一个链表，用于表示图中顶点之间的关系。
案例引入
社交网络：社交网络中的用户可以看作是图中的顶点，用户之间的关系（如朋友、关注等）可以看作是图中的边。通过图可以分析用户之间的社交关系，发现社区和影响力。
交通网络：城市中的道路、桥梁和隧道可以看作是图中的边，城市中的区域可以看作是图中的顶点。通过图可以分析城市交通流量，规划最优路径和优化交通系统。
计算机网络：计算机网络中的主机和路由器可以看作是图中的顶点，网络连接可以看作是图中的边。通过图可以分析网络拓扑结构，发现网络瓶颈和故障。
生物信息学：基因之间的关系可以通过图来表示，基因可以看作是图中的顶点，基因之间的关联可以看作是图中的边。通过图可以分析基因之间的调控关系，发现基因网络和疾病相关基因。
推荐系统：用户和物品可以看作是图中的顶点，用户对物品的评分可以看作是图中的边。通过图可以分析用户之间的相似性，为用户推荐感兴趣的物品。
游戏地图：游戏中的区域和道路可以看作是图中的顶点，区域之间的连接可以看作是图中的边。通过图可以分析游戏地图的结构，优化游戏体验和设计。
电力网络：电网中的发电站、变电站和用户可以看作是图中的顶点，电力线路可以看作是图中的边。通过图可以分析电力网络的拓扑结构，优化电力调度和故障定位。
供应链管理：供应商、制造商和零售商可以看作是图中的顶点，物流线路可以看作是图中的边。通过图可以分析供应链网络的结构，优化物流配送和库存管理。
自然语言处理：词汇可以看作是图中的顶点，词汇之间的语义关系可以看作是图中的边。通过图可以分析词汇之间的关联，提高自然语言处理任务的性能。
地理信息系统：地理位置和道路可以看作是图中的顶点，地理位置之间的连接可以看作是图中的边。通过图可以分析地理信息，进行路径规划、空间分析和可视化。
类型定义
无向图（Undirected Graph）：
定义：无向图中的边没有方向，任意两个顶点之间的边都是双向的。
表示：无向图可以用邻接矩阵或邻接表表示，其中邻接矩阵是一个对称矩阵，邻接表中的每个顶点的邻接点以链表形式存储。
有向图（Directed Graph）：
定义：有向图中的边有方向，每个边只从一个顶点指向另一个顶点。
表示：有向图可以用邻接矩阵或邻接表表示，其中邻接矩阵不是一个对称矩阵，邻接表中的每个顶点的邻接点以链表形式存储。
加权图（Weighted Graph）：
定义：加权图中的边有权重，表示边的长度、代价或重要性。
表示：加权图可以用加权邻接矩阵或加权邻接表表示，其中加权邻接矩阵是一个对角线为零的矩阵，加权邻接表中的每个顶点的邻接点以链表形式存储，链表中的每个节点包含邻接点的索引和边的权重。
无权图（Unweighted Graph）：
定义：无权图中的边没有权重，边的代价或长度为1。
表示：无权图可以用无权邻接矩阵或无权邻接表表示，其中无权邻接矩阵是一个对角线为零的矩阵，无权邻接表中的每个顶点的邻接点以链表形式存储。
连通图（Connected Graph）：
定义：连通图中的任意两个顶点之间都存在路径。
表示：连通图可以用连通邻接矩阵或连通邻接表表示，其中连通邻接矩阵是一个对角线为1的矩阵，连通邻接表中的每个顶点的邻接点以链表形式存储。
非连通图（Disconnected Graph）：
定义：非连通图中的存在至少两个顶点，它们之间没有路径。
表示：非连通图可以用非连通邻接矩阵或非连通邻接表表示，其中非连通邻接矩阵不是一个对角线为1的矩阵，非连通邻接表中的每个顶点的邻接点以链表形式存储。
完全图（Complete Graph）：
定义：完全图是一个连通图，其中任意两个不同顶点之间都存在边。
表示：完全图可以用完全邻接矩阵或完全邻接表表示，其中完全邻接矩阵是一个对角线为1的矩阵，完全邻接表中的每个顶点的邻接点以链表形式存储。
稀疏图（Sparse Graph）：
定义：稀疏图中的边数较少，相对于顶点数来说，边的数量不多。
表示：稀疏图可以用稀疏邻接矩阵或稀疏邻接表表示，其中稀疏邻接矩阵是一个对角线为零的矩阵，稀疏邻接表中的每个顶点的邻接点以链表形式存储。
稠密图（Dense Graph）：
定义：稠密图中的边数较多，相对于顶点数来说，边的数量很多。
表示：稠密图可以用稠密邻接矩阵或稠密邻接表表示，其中稠密邻接矩阵是一个对角线为1的矩阵，稠密邻接表中的每个顶点的邻接点以链表形式存储。
简单图（Simple Graph）：
定义：简单图不包含自环和平行边。
表示：简单图可以用简单邻接矩阵或简单邻接表表示，其中简单邻接矩阵是一个对角线为零的矩阵，简单邻接表中的每个顶点的邻接点以链表形式存储。
存储结构：邻接矩阵、邻接表、十字链表、邻接多重表
邻接矩阵（Adjacency Matrix）：
定义：邻接矩阵是一个二维数组，其中矩阵的行和列分别代表图中的顶点。如果顶点 i 和顶点 j 之间存在边，则邻接矩阵中的元素 A[i][j] 非零；否则为零。
特点：
适合稠密图，因为矩阵中的非零元素较少。
适用于无向图和有向图。
易于实现，但空间复杂度较高，通常为 O(V^2)，其中 V 是顶点的数量。
适用场景：
当图的边数相对于顶点数较多时。
需要快速检查两个顶点之间是否存在边时。
十字链表（Double-ended Queue）：
定义：十字链表是一种特殊的链表，用于表示有向图的邻接表。每个节点包含两个指针，一个指向前驱节点，一个指向后继节点，这样可以从任一方向遍历图。
特点：
适用于有向图。
空间复杂度较低，通常为 O(V + E)。
适用场景：
当图的边数相对于顶点数较少时。
需要频繁进行前向和后向遍历时。
邻接表（Adjacency List）：
定义：邻接表是一个数组，每个元素是一个链表，链表中的每个节点包含一个邻接点的索引和边的权重（如果有的话）。
特点：
适合稀疏图，因为链表中的元素较少。
适用于无向图和有向图。
空间复杂度较低，通常为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。
适用场景：
当图的边数相对于顶点数较少时。
需要频繁插入和删除边时。
邻接多重表（Adjacency Multiset）：
定义：邻接多重表是一种用于表示加权图的邻接表。每个顶点的邻接点以多重集的形式存储，多重集中的每个元素包含一个邻接点的索引和边的权重。
特点：
适用于加权图。
空间复杂度较低，通常为 O(V + E)。
适用场景：
当图的边数相对于顶点数较少时。
需要频繁进行加权边的插入和删除时。
图的遍历和搜索：深度优先搜索、广度优先搜索
深度优先搜索（DFS）：
定义：从图中的一个顶点开始，沿着一条路径遍历，直到到达路径的末端，然后回溯到上一个顶点，继续沿着其他路径遍历。
特点：
适合解决需要找到所有路径的问题，如连通性问题。
适合解决需要找到所有顶点的最大深度的问题，如计算连通分量的数量。
可以使用递归或栈来实现。
通常使用递归实现，但递归可能会导致栈溢出，特别是在处理大型图时。
适用场景：
连通性检测。
寻找所有路径。
计算连通分量的数量。
广度优先搜索（BFS）：
定义：从图中的一个顶点开始，沿着一条路径遍历，直到达到路径的末端，然后回溯到上一个顶点，继续沿着其他路径遍历。
特点：
适合解决需要找到最短路径的问题，如单源最短路径问题。
适合解决需要找到所有顶点的最大深度的问题，如计算连通分量的数量。
可以使用队列来实现。
不会使用递归，因此不会导致栈溢出。
适用场景：
单源最短路径问题。
连通性检测。
寻找所有路径。
计算连通分量的数量。
图的应用：最小生成树、最短路径、拓扑排序、关键路径
1. 最小生成树 (Minimum Spanning Tree, MST)
最小生成树是指连接图中所有顶点且权值之和最小的子图。在许多实际应用中，例如网络设计、电路设计等，都需要寻找最小生成树。
算法：
普里姆算法 (Prim’s Algorithm): 从某个顶点开始，逐步添加边和顶点，直到构建出最小生成树。
克鲁斯卡尔算法 (Kruskal’s Algorithm): 按照边的权值从小到大排序，逐步添加边和顶点，直到构建出最小生成树。
应用：
网络设计：找到连接所有节点的最小成本网络。
电路设计：找到连接所有组件的最小成本电路。
拓扑排序 (Topological Sorting)
拓扑排序是一种对有向无环图（DAG）的顶点进行排序的方法，使得对于图中任意有向边 u -> v，u 在排序中出现在 v 之前。
应用：
作业调度：根据任务之间的依赖关系进行排序，以便高效地执行。
程序设计：对程序中的模块进行排序，以便进行代码优化和调试。
最短路径 (Shortest Path)
最短路径是指从一个顶点到另一个顶点的路径中权值之和最小的路径。在许多实际应用中，例如导航系统、网络路由等，都需要寻找最短路径。
算法：
迪杰斯特拉算法 (Dijkstra’s Algorithm): 从起点开始，逐步扩展到最近的未访问顶点，直到找到终点。
贝尔曼-福特算法 (Bellman-Ford Algorithm): 对所有顶点进行松弛操作，直到找到最短路径。
应用：
导航系统：找到从起点到终点的最短路径。
网络路由：找到从源节点到目的节点的最短路径。
关键路径 (Critical Path)
关键路径是指在一个项目中，决定项目完成时间的最长路径。在项目管理中，关键路径可以帮助项目经理了解项目的关键环节，并制定相应的计划来确保项目按时完成。
应用：
项目管理：确定项目的关键任务，并制定相应的计划来确保项目按时完成。
网络设计：确定网络的瓶颈环节，并采取措施进行优化。
0 条评论
下一页
