数据结构与算法(C/C++)

Ne0inhk

24 Mar 2026 — 53 min read

一、引言

1.数据结构

解决问题方法的效率,跟数据的组织方式有关
解决问题方法的效率,跟空间的利用效率有关
解决问题方法的效率,跟算法的巧妙程度有关
什么是数据结构？数据结构是数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）
- 数据类型
  - 数据对象集
  - 数据集合相关联的操作集
- 抽象:描述数据类型的方法不依赖于具体实现
  - 与存放数据的机器无关
  - 与数据存储的物理结构无关
  - 与实现操作的算法和编程语言均无关
- 只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
例子："矩阵"的抽象数据类型定义
- 类型名称：矩阵（Matrix）
  - Matrix Create（int M，int N）：返回一个M×N的空矩阵
  - int GetMaxRow（Matrix A）：返回矩阵A的总行数
  - int GetMaxCol（Matrix A）：返回矩阵A的总列数
  - ElementType getEntry（Matrix A，int i，int j）：返回矩阵A的第i行、第j列的元素
  - Matrix Add（Matrix A，Matrix B）：（先按行加？先按列加？什么语言）如果矩阵A和B的行数、列数一致，则返回矩阵C=A+B，否则返回错误标志
  - Matrix Multiply（Matrix A，Matrix B）：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志

操作集：对任意矩阵A，B，C

Matrix,以及整数i、j、M、N

数据对象集：一个M×N的矩阵（二维数组？一维数组？十字链表？）

=a(i,j)（i=1，...，M；j=1，...，N）由M×N个三元组<a，i，j>构成,其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号

2.算法

算法（Algorithm）
- 一个有限指令集
- 接受一些输入（有些情况不需要输入）
- 产生输出
- 一定在有限步骤后终止
- 每一条指令必须
  - 有充分明确的目标，不可以有歧义
  - 要在计算机能处理的范围之内
  - 描述应不依赖于任何一种计算机语言以及具体的实现手段
什么是好的算法？
- 空间复杂度S（n）：根据算法写成的程序在执行时占用的存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断
- 时间复杂度T（n）：根据算法写成的程序在执行时消耗的时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果
- 在分析一般算法的效率时，我们经常关注下面两种复杂度
复杂度的渐进表示
复杂度分析小窍门
- 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
- if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中的最大
例子：最大子列和问题

若

是关于n的k阶多项式，那么

T_{}\left ( n \right )= \theta \left ( n^{k} \right )

T_{1}\left ( n \right )\times T_{2}\left ( n \right )= O_{}\left ( f_{1}\left ( n \right )\times f_{2}\left ( n \right ) \right )

T_{1}\left ( n \right )+T_{2}\left ( n \right )= max\left ( O_{}\left ( f_{1}\left ( n \right ) \right ), O_{}\left ( f_{2}\left ( n \right ) \right )\right )

若两段算法分别有复杂度

T_{1}\left ( n \right )= O_{}\left ( f_{1}\left ( n \right ) \right )

和

T_{2}\left ( n \right )= O_{}\left ( f_{2}\left ( n \right ) \right )

，则

T_{}\left ( n \right )= \theta _{}\left ( h_{}\left ( n \right ) \right )

表示同时有

T_{}\left ( n \right )= O_{}\left ( h_{}\left ( n \right ) \right )

和

T_{}\left ( n \right )= \Omega _{}\left ( h_{}\left ( n \right ) \right )

T_{}\left ( n \right )= \Omega _{}\left ( g_{}\left ( n \right ) \right )

表示存在常数

，

使得当

时有

T\left ( n \right )\geq C\cdot g\left ( n \right )

T_{}\left ( n \right )= O_{}\left ( f_{}\left ( n \right ) \right )

表示存在常数

，

使得当

时有

T\left ( n \right )\leq C\cdot f\left ( n \right )

T_{avg}\left ( n \right )\leqslant T_{worst}\left ( n \right )

平均复杂度

最坏情况复杂度

算法1：三重循环暴力枚举法

核心思想： 穷举所有可能的连续子序列，逐一计算它们的和，并记录下出现过的最大值。

执行步骤：

使用三个嵌套的循环：
- 外层循环 i确定子序列的起始位置。
- 中层循环 j确定子序列的结束位置。
- 内层循环 k从起始位置 i遍历到结束位置 j，将 A[k]累加到 thisSum中，从而计算出该子序列的和。
每次计算完一个子序列的和后，将其与当前记录的最大和 maxSum进行比较。如果更大，就更新 maxSum。
最终，maxSum就是整个数组中连续子序列的最大和。

特点： 思路直接，但效率极低，时间复杂度为 O(N³)。因为它重复计算了大量子序列的和（例如，从 i 到 j 的和在计算了 i...j 之后，计算 i...j+1 时又重新从 i 开始加了一遍）。

#include <stdio.h> int MaxSubSeqSum1(int A[],int N); int main(){ int N = 8; int A[] = {4, -3, 5, -2, -1, 2, 6, -2}; printf("算法1：%d\n",MaxSubSeqSum1(A,N)); return 0; } /* 算法1：最笨的方法 O(N^3)*/ int MaxSubSeqSum1(int A[],int N){ int thisSum,maxSum = 0; int i,j,k; for(i=0;i<N;i++){ for(j=i;j<N;j++){ thisSum = 0; for(k=i;k<=j;k++) thisSum += A[k]; if(thisSum > maxSum) maxSum = thisSum; } } return maxSum; }

算法2：二重循环优化法

核心思想： 在算法1的基础上进行优化，通过消除最内层的循环来避免重复计算，将时间复杂度降为平方级别。

执行步骤：

使用两个嵌套的循环：
- 外层循环 i依然确定子序列的起始位置。
- 中层循环 j从起始位置 i开始向右移动，每移动一步，不是重新计算，而是在上一次计算出的 thisSum（即 i 到 j-1 的和）基础上加上新的元素 A[j]，从而得到 i 到 j 的新子序列的和。
同样，每次得到一个新的 thisSum后，都与 maxSum比较并更新。
当 j到达数组末尾后，i增加一位，然后 j再次从 i开始，并重置 thisSum为0，重复上述过程。

特点： 避免了大量的重复累加操作，效率比算法1有显著提升，但仍然是平方时间复杂度 O(N²)，对于大规模数据依然不够快。

#include <stdio.h> int MaxSubSeqSum2(int A[],int N); int main(){ int N = 8; int A[] = {4, -3, 5, -2, -1, 2, 6, -2}; printf("算法2：%d\n",MaxSubSeqSum2(A,N)); return 0; } /* 算法2：改进版 O(N^2)*/ int MaxSubSeqSum2(int A[],int N){ int thisSum,maxSum = 0; int i,j,k; for(i=0;i<N;i++){ thisSum = 0; for(j=i;j<N;j++){ thisSum += A[j]; if(thisSum > maxSum) maxSum = thisSum; } } return maxSum; }

算法3：分治法

核心思想： “分而治之”。将大问题分解成小问题来解决，然后将小问题的解合并成原问题的解。对于最大子序列和问题，任何子序列要么完全位于数组的左半部分，要么完全位于右半部分，要么跨越了数组的中间点。我们只需递归地解决前两种情况，并单独处理第三种情况，最后取三者中的最大值。

执行步骤：

分解： 将当前数组区间 [left, right]从中间分成左右两个子区间 [left, mid]和 [mid+1, right]。
解决： 递归地求解这两个子区间各自的最大子序列和（max_left和 max_right）。
合并： 计算跨越中点的最大子序列和 (max_cross)。这需要：
- 从中点向左扫描，找出左边部分能产生的最大和。
- 从中点向右扫描，找出右边部分能产生的最大和。
- 将左右两边的最大和相加，即为跨越中点的最大和。
返回： 返回 max_left, max_right, max_cross三者中的最大值。

特点： 思路巧妙，将问题规模不断对半分割，递归深度为 logN，每层需要线性时间 O(N) 来合并，因此总的时间复杂度为 O(N log N)，效率远高于前两种暴力方法。

#include <stdio.h> int MaxSubSeqSum3(int A[],int N); int MaxCrossingSum(int A[], int left, int mid, int right); int MaxSubSeqSum3_Recursive(int A[], int left, int right); int main(){ int N = 8; int A[] = {4, -3, 5, -2, -1, 2, 6, -2}; printf("算法3：%d\n",MaxSubSeqSum3(A,N)); return 0; } /* 算法3：分而治之 O(N*log N) */ int MaxSubSeqSum3(int A[], int N) { return MaxSubSeqSum3_Recursive(A, 0, N - 1); } /* 辅助函数：计算跨越中点的最大子序列和 */ int MaxCrossingSum(int A[], int left, int mid, int right) { int sum = 0; int left_sum = 0; int right_sum = 0; // 从中点向左扫描，找最大和 int i; for (i = mid; i >= left; i--) { sum += A[i]; if (sum > left_sum) { left_sum = sum; } } sum = 0; // 重置sum // 从中点向右扫描，找最大和 for (i = mid + 1; i <= right; i++) { sum += A[i]; if (sum > right_sum) { right_sum = sum; } } // 返回跨越中点的最大和 return left_sum + right_sum; } /* 分治递归函数 */ int MaxSubSeqSum3_Recursive(int A[], int left, int right) { // 基本情况：只有一个元素 if (left == right) { if (A[left] > 0) { return A[left]; } else { return 0; // 如果允许空子序列，负数返回0 } } // 找到中间位置 int mid = (left + right) / 2; // 递归求解三部分的最大值： // 1. 左半部分的最大子序列和 // 2. 右半部分的最大子序列和 // 3. 跨越中点的最大子序列和 int max_left = MaxSubSeqSum3_Recursive(A, left, mid); int max_right = MaxSubSeqSum3_Recursive(A, mid + 1, right); int max_cross = MaxCrossingSum(A, left, mid, right); // 返回三者中的最大值 if (max_left >= max_right && max_left >= max_cross) { return max_left; } else if (max_right >= max_left && max_right >= max_cross) { return max_right; } else { return max_cross; } }

算法4：在线处理法（Kadane算法）

核心思想： 一次遍历，动态决策。在扫描数组的过程中，维护两个变量：thisSum（以当前元素结尾的最大子序列和）和 maxSum（全局最大子序列和）。根据 thisSum的状态实时做出最优决策：是继续扩展当前子序列，还是放弃当前子序列，从下一个元素重新开始。

执行步骤：

初始化 thisSum和 maxSum都为 0。
顺序遍历数组中的每一个元素 A[i]：
- 将 A[i]加到 thisSum上。
- 比较 thisSum和 maxSum：
  - 如果 thisSum大于 maxSum，则更新 maxSum为 thisSum。
  - 如果 thisSum小于 0，说明当前子序列的和为负数，那么它不可能对后续的任何子序列产生正面贡献（因为加上一个负数只会让后面的和变小），于是果断地将 thisSum重置为 0，意味着我们从下一个元素开始，寻找一个全新的子序列。
遍历结束后，maxSum即为所求的最大子序列和。

特点： 这是最高效的算法，只需要一次遍历，时间复杂度为 O(N)，空间复杂度为 O(1)。它的精妙之处在于其“在线”特性，即可以在数据流输入的同时即时给出当前已知的最大子序列和，无需等待所有数据处理完毕。这个算法也常被称为 Kadane算法。

#include <stdio.h> int MaxSubSeqSum4(int A[],int N); int main(){ int N = 8; int A[] = {4, -3, 5, -2, -1, 2, 6, -2}; printf("算法4：%d\n",MaxSubSeqSum4(A,N)); return 0; } /* 算法4：在线处理 O(N) */ int MaxSubSeqSum4(int A[],int N){ int thisSum,maxSum; int i; thisSum = maxSum = 0; for(i=0;i<N;i++){ thisSum += A[i]; if(thisSum > maxSum) maxSum = thisSum; else if(thisSum < 0) thisSum = 0; } return maxSum; }

二、数据结构

1.顺序表(静态分配)

①定义

“线性表（Linear List）”：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的的长度，后续用L.length或者n表示
线性表没有元素时，称为空表
表的起始位置称表头，表的结束位置称表尾

根据数据元素的存储结构是否连续，线性表可以分为顺序表和链表两种类型

在顺序表中，逻辑上相邻的数据元素在存储结构（物理结构）上也相邻
在链表中，逻辑上相邻的数据元素在存储结构（物理结构）上不一定相邻

②抽象数据类型描述

类型名称：顺序表（SqList）

数据对象集：顺序表是n（n>0）个元素构成的有序序列

操作集：顺序表 L

SqList，整数 i 表示位序，元素 e

ElemType，顺序表基本操作主要有：

void InitList(SqList &L)：初始化一个顺序表
bool ListInsert(SqList &L,int i,ElemType e)：将元素e插入到L的第i个位置
bool ListDelete(SqList &L,int i,ElemType &e)：将L第i个位置的元素删除，并用e返回
ElemType GetElem(SqList L,int i)：返回第i个位置的元素值
int LocateElem(SqList L,ElemType e)：返回第一个元素值为e的元素的位序
void ListDisplay(SqList L)：打印顺序表

③结构实现

利用数组的连续存储空间顺序存放线性表的各元素

#include <stdio.h> //用于printf #define MaxSize 10 //定义最大长度 typedef int ElemType; //以整型数据为例 typedef struct{ ElemType data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义

④主要操作实现

初始化一个顺序表

void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i]=0; //将所有数据元素设置为默认初始值 L.length=0; //顺序表初始长度为0 }

插入：将元素e插入到L的第i个位置（位序i满足：

）

bool ListInsert(SqList &L,int i,ElemType e){ if(i<1 || i>L.length+1) return false; //位序i不在有效范围内 if(L.length>=MaxSize) return false; //顺序表的存储空间已满，不能插入 for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; //将第i个元素及之后的元素往后移 L.data[i-1]=e; //在位序i处放入e L.length++; //长度+1 return true; }

删除：将L第i个位置的元素删除，并用e返回（位序i满足：

）

bool ListDelete(SqList &L,int i,ElemType &e){ if(i<1 || i>L.length) return false; //位序i不在有效范围内 e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) L.data[j-1]=L.data[j]; //将第i个元素之后的元素往前移 L.length--; //长度-1 return true; }

按位查找：返回第i个位置的元素

ElemType GetElem(SqList L,int i){ if(i<1 || i>L.length){ printf("位序i不合理\n"); return NULL; } return L.data[i-1]; }

按值查找：返回第一个元素值为e的元素的位序

int LocateElem(SqList L,ElemType e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; return 0; }

打印顺序表

void ListDisplay(SqList L){ printf("顺序表L："); for(int i=0;i<L.length;i++){ if(i==L.length-1){ printf("%d，",L.data[i]); break; } printf("%d -> ",L.data[i]); } printf("总共有%d个元素\n",L.length); }

⑤源代码

说明：主函数中实现了以下5个功能

声明并初始化、打印顺序表L
从键盘输入要删除的元素的位序i，判断位序i合理性，打印删除成功后的L
从键盘输入要查找的元素的位序i，返回元素e
从键盘输入要查找的元素值e，判断LocateElem函数返回的位序，如果不为0，则输出该元素值的位序，否则输出“没有这个元素”

往L中插入10个奇数，判断位序i合理性，元素值e与位序i的关系是

，打印L

#include <stdio.h> //用于printf #define MaxSize 10 //定义最大长度 typedef int ElemType; //以整型数据为例 typedef struct{ ElemType data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 //基本操作：初始化一个顺序表 void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i]=0; //将所有数据元素设置为默认初始值 L.length=0; //顺序表初始长度为0 } //插入：将元素e插入到L的第i个位置 bool ListInsert(SqList &L,int i,ElemType e){ if(i<1 || i>L.length+1) return false; //位序i不在有效范围内 if(L.length>=MaxSize) return false; //顺序表的存储空间已满，不能插入 for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; //将第i个元素及之后的元素往后移 L.data[i-1]=e; //在位序i处放入e L.length++; //长度+1 return true; } //删除：将L第i个位置的元素删除，并用e返回 bool ListDelete(SqList &L,int i,ElemType &e){ if(i<1 || i>L.length) return false; //位序i不在有效范围内 e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) L.data[j-1]=L.data[j]; //将第i个元素之后的元素往前移 L.length--; //长度-1 return true; } //按位查找：返回第i个位置的元素 ElemType GetElem(SqList L,int i){ if(i<1 || i>L.length){ printf("位序i不合理\n"); return NULL; } return L.data[i-1]; } //按值查找：返回第一个元素值为e的元素的位序 int LocateElem(SqList L,ElemType e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; return 0; } //打印顺序表 void ListDisplay(SqList L){ printf("顺序表L："); for(int i=0;i<L.length;i++){ if(i==L.length-1){ printf("%d，",L.data[i]); break; } printf("%d -> ",L.data[i]); } printf("总共有%d个元素\n",L.length); } int main(){ SqList L; //声明一个顺序表 InitList(L); //初始化顺序表 ListDisplay(L); //打印顺序表 for(int i=0;i<MaxSize;i++){ //插入10个奇数 if(!ListInsert(L,i+1,2*(i+1)-1)) printf("\n在第%d个位置插入%d失败\n",i+1,2*(i+1)-1); } printf("\n插入成功\n"); ListDisplay(L); int j; ElemType e=-1; printf("\n输入你要删除的元素的位序："); scanf("%d",&j); if(ListDelete(L,j,e)) printf("删除成功，元素值为%d\n",e); else printf("位序%d不合理，删除失败\n",j); ListDisplay(L); int k; printf("\n输入你要查找的元素的位序："); scanf("%d",&k); ElemType result = GetElem(L,k); if(result!=NULL) printf("该元素的值为%d\n",result); else printf("没有该元素\n"); ElemType e1; printf("\n输入你要查找的元素值："); scanf("%d",&e1); int location = LocateElem(L,e1); if(location!=0) printf("该元素的位序为%d\n",location); else printf("没有该元素\n"); return 0; }

运行结果：

2.顺序表(动态分配)

①结构实现

利用指针指向一片连续的存储空间，即数组

要扩展空间时，先用另一个指针p保留原有数据，再重新分配存储空间，最后复制原有数据即可

#include <stdio.h> //用于printf、sizeof #include <stdlib.h> //用于malloc、free #define InitSize 10 //默认最大长度 typedef int ElemType; //以整型数据为例 typedef struct{ ElemType *data; //指示动态分配数组的指针 int MaxSize; //顺序表的实际最大容量 int length; //顺序表的当前长度 }SeqList; //顺序表的类型定义

②主要操作实现

只有初始化、扩展存储空间和打印三个操作与静态分配方式下的顺序表不同

其他操作除了参数(两种L类型分别为SqList和SeqList)有所不同，基本是一致的

初始化一个顺序表

void InitList(SeqList &L){ //用malloc函数申请一片连续的存储空间 L.data=(ElemType *)malloc(InitSize*sizeof(ElemType)); L.MaxSize=InitSize; L.length=0; }

扩展最大存储空间

void IncreaseSize(SeqList &L,int len){ ElemType *p=L.data; L.data=(ElemType *)malloc((InitSize+len)*sizeof(ElemType)); for(int i=0;i<L.length;i++) L.data[i]=p[i]; //将数据复制到新区域 L.MaxSize+=len; //顺序表最大长度增加len free(p); //释放原来的内存空间 }

打印顺序表

void ListDisplay(SeqList L){ printf("顺序表L："); for(int i=0;i<L.length;i++){ if(i==L.length-1){ printf("%d，",L.data[i]); break; } printf("%d -> ",L.data[i]); } printf("总共有%d个元素，最大存储空间为%d(个元素)\n",L.length,L.MaxSize); }

插入：将元素e插入到L的第i个位置（位序i满足：

）

按位查找：返回第i个位置的元素

删除：将L第i个位置的元素删除，并用e返回（位序i满足：

）

按值查找：返回第一个元素值为e的元素的位序

//插入：将元素e插入到L的第i个位置 bool ListInsert(SeqList &L,int i,ElemType e){ if(i<1 || i>L.length+1) return false; //位序i不在有效范围内 if(L.length>=L.MaxSize) return false; //顺序表的存储空间已满，不能插入 for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; //将第i个元素及之后的元素往后移 L.data[i-1]=e; //在位序i处放入e L.length++; //长度+1 return true; } //删除：将L第i个位置的元素删除，并用e返回 bool ListDelete(SeqList &L,int i,ElemType &e){ if(i<1 || i>L.length) return false; //位序i不在有效范围内 e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) L.data[j-1]=L.data[j]; //将第i个元素之后的元素往前移 L.length--; //长度-1 return true; } //按位查找：返回第i个位置的元素 ElemType GetElem(SeqList L,int i){ if(i<1 || i>L.length){ printf("位序i不合理\n"); return NULL; } return L.data[i-1]; } //按值查找：返回第一个元素值为e的元素的位序 int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; return 0; }

⑤源代码

说明：主函数中实现了以下6个功能，其中第3个是动态分配方式下顺序表特有操作的实现

声明并初始化、打印顺序表L
从键盘输入要扩展的存储空间的大小，打印扩展空间后的L
从键盘输入要删除的元素的位序i，判断位序i合理性，打印删除成功后的L
从键盘输入要查找的元素的位序i，返回元素e
从键盘输入要查找的元素值e，判断LocateElem函数返回的位序，如果不为0，则输出该元素值的位序，否则输出“没有这个元素”

往L中插入10个奇数，判断位序i合理性，元素值e与位序i的关系是

，打印L

#include <stdio.h> //用于printf、sizeof #include <stdlib.h> //用于malloc、free #define InitSize 10 //默认最大长度 typedef int ElemType; //以整型数据为例 typedef struct{ ElemType *data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度 }SeqList; //顺序表的类型定义 //初始化一张顺序表 void InitList(SeqList &L){ //用malloc函数申请一片连续的存储空间 L.data=(ElemType *)malloc(InitSize*sizeof(ElemType)); L.MaxSize=InitSize; L.length=0; } //扩展最大存储空间 void IncreaseSize(SeqList &L,int len){ ElemType *p=L.data; L.data=(ElemType *)malloc((InitSize+len)*sizeof(ElemType)); for(int i=0;i<L.length;i++) L.data[i]=p[i]; //将数据复制到新区域 L.MaxSize+=len; //顺序表最大长度增加len free(p); //释放原来的内存空间 } //插入：将元素e插入到L的第i个位置 bool ListInsert(SeqList &L,int i,ElemType e){ if(i<1 || i>L.length+1) return false; //位序i不在有效范围内 if(L.length>=L.MaxSize) return false; //顺序表的存储空间已满，不能插入 for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1]; //将第i个元素及之后的元素往后移 L.data[i-1]=e; //在位序i处放入e L.length++; //长度+1 return true; } //删除：将L第i个位置的元素删除，并用e返回 bool ListDelete(SeqList &L,int i,ElemType &e){ if(i<1 || i>L.length) return false; //位序i不在有效范围内 e=L.data[i-1]; //将被删除的元素赋值给e for(int j=i;j<L.length;j++) L.data[j-1]=L.data[j]; //将第i个元素之后的元素往前移 L.length--; //长度-1 return true; } //按位查找：返回第i个位置的元素 ElemType GetElem(SeqList L,int i){ if(i<1 || i>L.length){ printf("位序i不合理\n"); return NULL; } return L.data[i-1]; } //按值查找：返回第一个元素值为e的元素的位序 int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; return 0; } //打印顺序表 void ListDisplay(SeqList L){ printf("顺序表L："); for(int i=0;i<L.length;i++){ if(i==L.length-1){ printf("%d，",L.data[i]); break; } printf("%d -> ",L.data[i]); } printf("总共有%d个元素，最大存储空间为%d(个元素)\n",L.length,L.MaxSize); } int main(){ SeqList L; //声明一个顺序表 InitList(L); //初始化顺序表 ListDisplay(L); //打印顺序表 for(int i=0;i<InitSize;i++){ //插入10个奇数 if(!ListInsert(L,i+1,2*(i+1)-1)) printf("\n在第%d个位置插入%d失败\n",i+1,2*(i+1)-1); } printf("\n插入成功\n"); ListDisplay(L); int len; printf("\n输入你要扩展的空间大小："); scanf("%d",&len); IncreaseSize(L,len); ListDisplay(L); int j; ElemType e=-1; printf("\n输入你要删除的元素的位序："); scanf("%d",&j); if(ListDelete(L,j,e)) printf("删除成功，元素值为%d\n",e); else printf("位序%d不合理，删除失败\n",j); ListDisplay(L); int k; printf("\n输入你要查找的元素的位序："); scanf("%d",&k); ElemType result = GetElem(L,k); if(result!=NULL) printf("该元素的值为%d\n",result); else printf("没有该元素\n"); ElemType e1; printf("\n输入你要查找的元素值："); scanf("%d",&e1); int location = LocateElem(L,e1); if(location!=0) printf("该元素的位序为%d\n",location); else printf("没有该元素\n"); return 0; }

运行结果：

3.单链表(带/不带头结点)

①定义

不要求逻辑上相邻的两个元素物理上也相邻
通过“链”建立起数据元素之间的逻辑关系
插入、删除不需要移动数据元素，只需要修改“链”

②结构实现

利用结构体的next指针串联起线性表的各元素

typedef int ElemType; //定义元素的数据类型 typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //next指针指向下一个结点 }LNode,*LinkList; //LNode指结点，LinkList指头结点

导入的库文件：

#include <stdio.h> //用于scanf、printf #include <stdlib.h> //用于malloc、free

③主要操作实现

初始化一个单链表

bool InitList(LinkList &L){ //初始化一个单链表 L = (LinkList)malloc(sizeof(LNode)); //分配一个头结点 if(L==NULL) return false; //内存不足，分配失败 L->next = NULL; //只有一个头结点，没有第一个结点 return true; }

判断单链表是否为空

bool Empty(LinkList L){ //判断单链表是否为空 return (L->next==NULL); //判断第一个结点是否为空 }

求表的长度

int Length(LinkList L){ //求表的长度 if(Empty(L)) return 0; //空表 int len = 0; //统计表长 LNode *p = L->next; //p指向第1个结点 while(p!=NULL){ //遍历单链表 p = p->next; //p指向下一个结点 len++; //len+1 } return len; }

按位查找，返回第i个结点（i>=0）

LNode *GetElem(LinkList L,int i){ //按位查找，返回第i个结点（i>=0） if(i<0) return NULL; //位序不合理 LNode *p = L; //指针p从头开始指向各个结点 int j = 0; //当前p所指结点位序 while(p!=NULL && j<i){ //循环找到第i个结点 p = p->next; //p指向下一结点 j++; } return p; }

按值查找，找到数据域==e的结点

LNode *LocateElem(LinkList L,ElemType e){ //按值查找，找到数据域为e的结点 if(L->next==NULL) return NULL; //空表 LNode *p = L->next; //p指向第一个结点 while(p != NULL && p->data != e) //循环遍历单链表 p = p->next; //从第1个结点开始往后查找 return p; //找到后返回该结点指针，否则返回NULL }

前插操作：在p结点之前插入元素e

bool InsertPriorNode(LNode *p,ElemType e){ //前插操作：在p结点之前插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //新s连到p之后 s->data = p->data; //将p中元素复制到s中 p->data = e; //将p中元素替换为e return true; }

后插操作：在p结点之后插入元素e

bool InsertNextNode(LNode *p,ElemType e){ //后插操作：在p结点之后插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //将s连到p之后 s->data = e; //用s保存数据元素e return true; }

按位序插入：在表L中的第i个位置上插入指定元素e

bool ListInsert(LinkList &L,int i,ElemType e){//按位序插入：在L的第i个位置插入元素e if(i<1) return false; //位序不合理 LNode *p = GetElem(L,i-1); //找到前驱结点 if(p==NULL) return false; //前继结点不存在 return InsertNextNode(p,e); //对前驱结点执行后插操作 }

按位序删除：删除第i个位置上的结点，并用e保存其元素值

bool ListDelete(LinkList &L,int i,ElemType &e){//按位序删除：删除第i个位置上的结点，并用e保存其元素值 if(i<1) return false; //位序不合理 LNode *p = GetElem(L,i-1); //找前驱结点 if(p==NULL) return false; //前继结点不存在 if(p->next == NULL) return false; //不存在第i个结点 LNode *q = p->next; //q为待删结点 e = q->data; //用e保存其值 p->next = q->next; //前驱结点的后面变为第i+1个结点 free(q); //释放待删结点的空间 return true; }

指定结点的删除

bool DeleteNode(LinkList &L,LNode *p) { //指定结点的删除 if(p==NULL) return false; //p结点不存在 if(p->next==NULL){ //若p是尾结点 ElemType e; //用e保存其元素值但不使用 return ListDelete(L,Length(L),e); //调用按位序删除最后1个结点 } LNode *q = p->next; //令q指向p的后继结点 p->data = q->data; //p元素被后继结点覆盖 p->next = q->next; //将q结点从链中“断开” free(q); //释放后继结点的存储空间 return true; }

尾插法建立单链表

bool List_TailInsert(LinkList &L){ //尾插法：正向建立单链表 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 if(L==NULL) return false; //内存分配失败 L->next = NULL; //初始为空链表 LNode *s,*r = L; //s为新结点指针，r为表尾指针 ElemType x; //设元素类型为int printf("(尾插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->data = x; r->next = s; r = s; //r指向新的表尾结点 scanf("%d",&x); } r->next = NULL; //尾结点next指针置空 return true; }

头插法建立单链表

bool List_HeadInsert(LinkList &L){ //头插法：逆向建立单链表 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 if(L==NULL) return false; //内存分配失败 L->next = NULL; //初始为空链表 LNode *s; //s为新结点指针 ElemType x; //设元素类型为int printf("(头插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); //创建新结点 if(s==NULL) return false; //内存分配失败 s->data = x; //赋值给新结点 s->next = L->next; //将新结点插在第1个位置上 L->next = s; //L为头指针 scanf("%d",&x); } return true; }

打印单链表

void DisplayList(LinkList L){ if(Empty(L)){ printf("L为空表\n"); return; } LNode *p = L->next; //p指向第1个结点 while(p != NULL){ printf("%d", p->data); //打印元素值 if (p->next != NULL) //尾结点元素值后面不打印“-> ” printf(" -> "); p = p->next; //p指向下一个结点 } printf("\n"); //换行 return; }

④源代码

说明：

主函数中实现了以下功能

声明初始化头结点，并赋值头结点的next指针为空
提供了尾插法和头插法两种选择来建立单链表，输入1使用尾插法，输入2使用头插法
依次输入并回车给新结点赋值，直到输入9999后停止插入新结点
提供了1.打印单链表2.插入新结点3.删除某结点4.查找某结点共4种功能，输入-1退出程序
插入新结点前会判断位序i是否在[1,n+1]范围内，若位序不合理则拒绝执行
删除某结点和查找某结点前会判断位序i是否在[1,n]范围内，若位序不合理则拒绝执行

【单链表-带头结点.cpp】

#include <stdio.h> //用于scanf、printf #include <stdlib.h> //用于malloc、free typedef int ElemType; //定义元素的数据类型 typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //next指针指向下一个结点 }LNode,*LinkList; //LNode指结点，LinkList指头结点 //（1）单链表的定义 bool InitList(LinkList &L){ //初始化一个单链表 L = (LinkList)malloc(sizeof(LNode)); //分配一个头结点 if(L==NULL) return false; //内存不足，分配失败 L->next = NULL; //只有一个头结点，没有第一个结点 return true; } bool Empty(LinkList L){ //判断单链表是否为空 return (L->next==NULL); //判断第一个结点是否为空 } int Length(LinkList L){ //求表的长度 if(Empty(L)) return 0; //空表 int len = 0; //统计表长 LNode *p = L->next; //p指向第1个结点 while(p!=NULL){ //遍历单链表 p = p->next; //p指向下一个结点 len++; //len+1 } return len; } //（2）单链表的查找 LNode *GetElem(LinkList L,int i){ //按位查找，返回第i个结点（i>=0） if(i<0) return NULL; //位序不合理 LNode *p = L; //指针p从头开始指向各个结点 int j = 0; //当前p所指结点位序 while(p!=NULL && j<i){ //循环找到第i个结点 p = p->next; //p指向下一结点 j++; } return p; } LNode *LocateElem(LinkList L,ElemType e){ //按值查找，找到数据域为e的结点 if(L->next==NULL) return NULL; //空表 LNode *p = L->next; //p指向第一个结点 while(p != NULL && p->data != e) //循环遍历单链表 p = p->next; //从第1个结点开始往后查找 return p; //找到后返回该结点指针，否则返回NULL } //（3）单链表的插入 bool InsertPriorNode(LNode *p,ElemType e){ //前插操作：在p结点之前插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //新s连到p之后 s->data = p->data; //将p中元素复制到s中 p->data = e; //将p中元素替换为e return true; } bool InsertNextNode(LNode *p,ElemType e){ //后插操作：在p结点之后插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //将s连到p之后 s->data = e; //用s保存数据元素e return true; } bool ListInsert(LinkList &L,int i,ElemType e){//按位序插入：在L的第i个位置插入元素e if(i<1) return false; //位序不合理 LNode *p = GetElem(L,i-1); //找到前驱结点 if(p==NULL) return false; //前继结点不存在 return InsertNextNode(p,e); //对前驱结点执行后插操作 } //（4）单链表的删除 bool ListDelete(LinkList &L,int i,ElemType &e){//按位序删除：删除第i个位置上的结点，并用e保存其元素值 if(i<1) return false; //位序不合理 LNode *p = GetElem(L,i-1); //找前驱结点 if(p==NULL) return false; //前继结点不存在 if(p->next == NULL) return false; //不存在第i个结点 LNode *q = p->next; //q为待删结点 e = q->data; //用e保存其值 p->next = q->next; //前驱结点的后面变为第i+1个结点 free(q); //释放待删结点的空间 return true; } bool DeleteNode(LinkList &L,LNode *p) { //指定结点的删除 if(p==NULL) return false; //p结点不存在 if(p->next==NULL){ //若p是尾结点 ElemType e; //用e保存其元素值但不使用 return ListDelete(L,Length(L),e); //调用按位序删除最后1个结点 } LNode *q = p->next; //令q指向p的后继结点 p->data = q->data; //p元素被后继结点覆盖 p->next = q->next; //将q结点从链中“断开” free(q); //释放后继结点的存储空间 return true; } //（5）单链表的建立 bool List_TailInsert(LinkList &L){ //尾插法：正向建立单链表 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 if(L==NULL) return false; //内存分配失败 L->next = NULL; //初始为空链表 LNode *s,*r = L; //s为新结点指针，r为表尾指针 ElemType x; //设元素类型为int printf("(尾插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->data = x; r->next = s; r = s; //r指向新的表尾结点 scanf("%d",&x); } r->next = NULL; //尾结点next指针置空 return true; } bool List_HeadInsert(LinkList &L){ //头插法：逆向建立单链表 L = (LinkList)malloc(sizeof(LNode)); //建立头结点 if(L==NULL) return false; //内存分配失败 L->next = NULL; //初始为空链表 LNode *s; //s为新结点指针 ElemType x; //设元素类型为int printf("(头插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); //创建新结点 if(s==NULL) return false; //内存分配失败 s->data = x; //赋值给新结点 s->next = L->next; //将新结点插在第1个位置上 L->next = s; //L为头指针 scanf("%d",&x); } return true; } //（6）打印单链表 void DisplayList(LinkList L){ if(Empty(L)){ printf("L为空表\n"); return; } LNode *p = L->next; //p指向第1个结点 while(p != NULL){ printf("%d", p->data); //打印元素值 if (p->next != NULL) //尾结点元素值后面不打印“-> ” printf(" -> "); p = p->next; //p指向下一个结点 } printf("\n"); //换行 return; } //（7）基本操作测试 int main(){ LinkList L; InitList(L); printf("单链表初始化成功\n"); int build_way=0; printf("1.尾插法\t2.头插法\n"); printf("请选择建表方式："); while(true){ scanf("%d",&build_way); if(build_way==1){ if(List_TailInsert(L)) printf("建立成功\n"); else printf("建立失败\n"); break; } else if(build_way==2){ if(List_HeadInsert(L)) printf("建立成功\n"); else printf("建立失败\n"); break; } else{ printf("没有该选项，建表失败，请重新选择\n"); continue; } } int option; //功能号 int i; //位序 int e; //元素值 LNode *p; //某一结点 while(1){ option=0;i=0;e=0;p=NULL; printf("-------------------------------------\n"); printf("1.打印单链表\t2.插入新结点\t3.删除某结点\t4.查找某结点\n"); printf("-------------------------------------\n"); printf("输入你想要实现的功能(输入-1结束程序):"); scanf("%d",&option); switch(option){ case 1: DisplayList(L); break; case 2: printf("请输入插入的位序："); scanf("%d",&i); if(i>Length(L)+1 || i<1){ printf("位序不合理\n"); break; } printf("请输入插入的元素值："); scanf("%d",&e); if(ListInsert(L,i,e)) printf("插入成功\n"); else printf("插入失败\n"); break; case 3: printf("请输入删除的位序："); scanf("%d",&i); if(i>Length(L) || i<1){ printf("位序不合理\n"); break; } if(ListDelete(L,i,e)) printf("删除成功，元素值为%d\n",e); else printf("删除失败\n"); break; case 4: printf("请输入查找的位序："); scanf("%d",&i); if(i>Length(L) || i<1){ printf("位序不合理\n"); break; } p=GetElem(L,i); if(p!=NULL) printf("查找成功，元素值为%d\n",p->data); else printf("查找失败\n"); break; case -1: return 0; } printf("\n"); } return 0; }

【单链表-不带头结点.cpp】

#include <stdio.h> //用于scanf、printf #include <stdlib.h> //用于malloc、free typedef int ElemType; //定义元素的数据类型 typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //next指针指向下一个结点 }LNode,*LinkList; //LNode指结点，LinkList指头结点 //（1）单链表的定义 bool InitList(LinkList &L){ //初始化一个单链表 L = NULL; //置第一个结点为空 return true; } bool Empty(LinkList L){ //判断单链表是否为空 return (L==NULL); //判断第一个结点是否为空 } int Length(LinkList L){ //求表的长度 if(Empty(L)) return 0; //空表 int len = 0; //统计表长 LNode *p = L; //p指向第1个结点 while(p!=NULL){ //遍历单链表 p = p->next; //p指向下一个结点 len++; //len+1 } return len; } //（2）单链表的查找 LNode *GetElem(LinkList L,int i){ //按位查找，返回第i个结点（i>=0） if(i<1) return NULL; //位序不合理 LNode *p = L; //指针p从头开始指向各个结点 int j = 1; //当前p所指结点位序 while(p!=NULL && j<i){ //循环找到第i个结点 p = p->next; //p指向下一结点 j++; } return p; } LNode *LocateElem(LinkList L,ElemType e){ //按值查找，找到数据域为e的结点 if(L==NULL) return NULL; //空表 LNode *p = L; //p指向第一个结点 while(p != NULL && p->data != e) //循环遍历单链表 p = p->next; //从第1个结点开始往后查找 return p; //找到后返回该结点指针，否则返回NULL } //（3）单链表的插入 bool InsertPriorNode(LNode *p,ElemType e){ //前插操作：在p结点之前插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //新s连到p之后 s->data = p->data; //将p中元素复制到s中 p->data = e; //将p中元素替换为e return true; } bool InsertNextNode(LNode *p,ElemType e){ //后插操作：在p结点之后插入元素e if(p==NULL) return false; //p结点不存在 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next = p->next; p->next = s; //将s连到p之后 s->data = e; //用s保存数据元素e return true; } bool ListInsert(LinkList &L,int i,ElemType e){//按位序插入：在L的第i个位置插入元素e if(i<1) return false; //位序不合理 if(i==1){ //若插在第1个位置 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->next =L; //第1个结点连在新结点之后 L = s; //L指向新的结点 s->data = e; //用s保存元素e return true; } LNode *p = GetElem(L,i-1); //找到前驱结点 if(p==NULL) return false; //前继结点不存在 return InsertNextNode(p,e); //对前驱结点执行后插操作 } //（4）单链表的删除 bool ListDelete(LinkList &L,int i,ElemType &e){//按位序删除：删除第i个位置上的结点，并用e保存其元素值 if(i<1) return false; //位序不合理 if(i==1){ //若删除第1个结点 LNode *s = L; //s指向第1个结点 e = L->data; //用e保存第1个结点的值 L = L->next; //L指向第2个结点 free(s); //释放第1个结点的空间 return true; } LNode *p = GetElem(L,i-1); //找前驱结点 if(p==NULL) return false; //前继结点不存在 if(p->next == NULL) return false; //不存在第i个结点 LNode *q = p->next; //q为待删结点 e = q->data; //用e保存其值 p->next = q->next; //前驱结点的后面变为第i+1个结点 free(q); //释放待删结点的空间 return true; } bool DeleteNode(LinkList &L,LNode *p) { //指定结点的删除 if(p==NULL) return false; //p结点不存在 if(p->next==NULL){ //若p是尾结点 ElemType e; //用e保存其元素值但不使用 return ListDelete(L,Length(L),e); //调用按位序删除最后1个结点 } LNode *q = p->next; //令q指向p的后继结点 p->data = q->data; //p元素被后继结点覆盖 p->next = q->next; //将q结点从链中“断开” free(q); //释放后继结点的存储空间 return true; } //（5）单链表的建立 bool List_TailInsert(LinkList &L){ //尾插法：正向建立单链表 L = NULL; //初始化为空表 LNode *s,*r = NULL; //s为新结点指针，r为表尾指针 ElemType x; //设元素类型为int printf("(尾插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); if(s==NULL) return false; //内存分配失败 s->data = x; if(L==NULL){ L = s; //L被赋值 r = s; //r指向新的尾结点 }else{ r->next = s; //s接在尾结点后面 r = s; //s成为尾结点 } scanf("%d",&x); } r->next = NULL; //尾结点next指针置空 return true; } bool List_HeadInsert(LinkList &L){ //头插法：逆向建立单链表 L = NULL; //初始化为空表 LNode *s; //s为新结点指针 ElemType x; //设元素类型为int printf("(头插法)输入元素x的值（输入9999视为退出）："); scanf("%d",&x); //输入x while(x != 9999){ s = (LNode *)malloc(sizeof(LNode)); //创建新结点 if(s==NULL) return false; //内存分配失败 s->data = x; //赋值给新结点 s->next = L; //将新结点插在第1个位置上 L = s; //L为第一个结点 scanf("%d",&x); } return true; } //（6）打印单链表 void DisplayList(LinkList L){ if(Empty(L)){ printf("L为空表\n"); return; } LNode *p = L; //p指向第1个结点 while(p != NULL){ printf("%d", p->data); //打印元素值 if (p->next != NULL) //尾结点元素值后面不打印“-> ” printf(" -> "); p = p->next; //p指向下一个结点 } printf("\n"); //换行 return; } //（7）基本操作测试 int main(){ LinkList L; InitList(L); printf("单链表初始化成功\n"); int build_way=0; printf("1.尾插法\t2.头插法\n"); printf("请选择建表方式："); while(true){ scanf("%d",&build_way); if(build_way==1){ if(List_TailInsert(L)) printf("建立成功\n"); else printf("建立失败\n"); break; } else if(build_way==2){ if(List_HeadInsert(L)) printf("建立成功\n"); else printf("建立失败\n"); break; } else{ printf("没有该选项，建表失败，请重新选择\n"); continue; } } int option; //功能号 int i; //位序 int e; //元素值 LNode *p; //某一结点 while(1){ option=0;i=0;e=0;p=NULL; printf("-------------------------------------\n"); printf("1.打印单链表\t2.插入新结点\t3.删除某结点\t4.查找某结点\n"); printf("-------------------------------------\n"); printf("输入你想要实现的功能(输入-1结束程序):"); scanf("%d",&option); switch(option){ case 1: DisplayList(L); break; case 2: printf("请输入插入的位序："); scanf("%d",&i); if(i>Length(L)+1 || i<1){ printf("位序不合理\n"); break; } printf("请输入插入的元素值："); scanf("%d",&e); if(ListInsert(L,i,e)) printf("插入成功\n"); else printf("插入失败\n"); break; case 3: printf("请输入删除的位序："); scanf("%d",&i); if(i>Length(L) || i<1){ printf("位序不合理\n"); break; } if(ListDelete(L,i,e)) printf("删除成功，元素值为%d\n",e); else printf("删除失败\n"); break; case 4: printf("请输入查找的位序："); scanf("%d",&i); if(i>Length(L) || i<1){ printf("位序不合理\n"); break; } p=GetElem(L,i); if(p!=NULL) printf("查找成功，元素值为%d\n",p->data); else printf("查找失败\n"); break; case -1: return 0; } printf("\n"); } return 0; }

运行结果（以【单链表-带头结点.cpp】尾插法为例）：

4.双链表

①定义

在单链表的基础上，除了头结点，每个结点都有一个prior指针指向其前驱结点
除了尾结点，每个结点都有next指针指向其后继结点

②结构实现

利用结构体的prior和next指针串联其前后两个结点

typedef int ElemType; typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinkList;

导入的库文件

#include <stdio.h> //用于printf、scanf #include <stdlib.h> //用于malloc、free

③主要操作实现

初始化双链表

bool InitDLinkList(DLinkList &L){ //初始化双链表 L = (DNode *)malloc(sizeof(DNode)); if(L==NULL) return false; //内存分配失败 L->prior = NULL; //头结点的prior永远指向NULL L->next = NULL; //头结点后暂时没有结点 return true; }

判断双链表是否为空

bool Empty(DLinkList L){ //判断双链表是否为空 return L->next==NULL; }

计算双链表长度

int Length(DLinkList L){ //计算双链表长度 if(Empty(L)) return 0; //空表 int len = 0; //统计表长 DNode *p = L->next; //p从第1个结点开始遍历 while(p!=NULL){ //循环遍历 p = p->next; //p指向下一个结点 len++; //len+1 } return len; }

后插操作：在p结点后插入一个新结点s

bool InsertNextDNode(DNode *p,DNode *s){//在p结点后插入s结点 if(p==NULL || s==NULL) return false;//非法参数 s->next = p->next; if(p->next!=NULL) //如果p结点有后继结点 p->next->prior = s; s->prior = p; p->next = s; return true; }

按位序插入：在L第i个位置上插入数据域为e的新结点

bool ListInsert(DLinkList &L,int i,ElemType e){ if(i<1 || i>Length(L)+1) return false; //位序不合理 DNode *s,*p = L; //s为新结点，p指向当前结点 s = (DNode *)malloc(sizeof(DNode)); s->data = e; int j = 0; //p当前所指结点的位序 while(p!=NULL && j<i-1){ //找到前驱结点 p = p->next; j++; } return InsertNextDNode(p,s); }

后删操作：删除p的后继结点

bool DeleteNextDNode(DNode *p){ //删除p的后继结点 if(p==NULL) return false; //非法参数 DNode *q = p->next; //设q为p的后继结点 if(q==NULL) return false; //q不存在 p->next = q->next; //p后面连着q的后继结点或置空 if(q->next!=NULL) //若q后面还有结点 q->next->prior = p; //将q的后继结点连在p后面 free(q); //释放q的空间 }

按位序删除：删除L第i个位置上的结点

bool ListDelete(DLinkList &L,int i,ElemType &e){ if(i<1 || i>Length(L)) return false; //位序不合理 DNode *p = L; //p指向当前结点 int j = 0; //p当前所指结点的位序 while(p!=NULL && j<i-1){ //找到前驱结点 p = p->next; j++; } if(p==NULL) return false; //前驱结点不存在 if(p->next==NULL) return false; //该结点不存在 e = p->next->data; //e保存待删结点的数据域 return DeleteNextDNode(p); }

双链表的销毁

bool DestroyList(DLinkList &L){ DNode *p = L; while(p!=NULL){ // 从头结点开始逐个释放 DNode *temp = p; p = p->next; free(temp); } L = NULL; return true; }

打印双链表

void DisplayDList(DLinkList L){ if(Empty(L)){ printf("L是空表\n"); return; } DNode *p = L->next; printf("L："); while(p!=NULL){ printf("%d",p->data); if(p->next!=NULL) printf(" -> "); p = p->next; } printf("\n"); }

④源代码

说明：

主函数中实现了以下功能：

声明后初始化一个双链表L，打印L，输出L的长度
往L中插入2，4，6，8四个元素后，打印L，输出L的长度
输入一个位序后，删除该处的结点，打印L，输出L的长度
选择1以销毁表L，结束程序
选择2则最后一次打印L并输出L的长度

#include <stdio.h> //用于printf、scanf #include <stdlib.h> //用于malloc、free typedef int ElemType; typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinkList; //（1）双链表的定义 bool InitDLinkList(DLinkList &L){ //初始化双链表 L = (DNode *)malloc(sizeof(DNode)); if(L==NULL) return false; //内存分配失败 L->prior = NULL; //头结点的prior永远指向NULL L->next = NULL; //头结点后暂时没有结点 return true; } bool Empty(DLinkList L){ //判断双链表是否为空 return L->next==NULL; } int Length(DLinkList L){ //计算双链表长度 if(Empty(L)) return 0; //空表 int len = 0; //统计表长 DNode *p = L->next; //p从第1个结点开始遍历 while(p!=NULL){ //循环遍历 p = p->next; //p指向下一个结点 len++; //len+1 } return len; } //（2）双链表的插入 bool InsertNextDNode(DNode *p,DNode *s){//在p结点后插入s结点 if(p==NULL || s==NULL) return false;//非法参数 s->next = p->next; if(p->next!=NULL) //如果p结点有后继结点 p->next->prior = s; s->prior = p; p->next = s; } bool ListInsert(DLinkList &L,int i,ElemType e){ if(i<1 || i>Length(L)+1) return false; //位序不合理 DNode *s,*p = L; //s为新结点，p指向当前结点 s = (DNode *)malloc(sizeof(DNode)); s->data = e; int j = 0; //p当前所指结点的位序 while(p!=NULL && j<i-1){ //找到前驱结点 p = p->next; j++; } return InsertNextDNode(p,s); } //（3）双链表的删除 bool DeleteNextDNode(DNode *p){ //删除p的后继结点 if(p==NULL) return false; //非法参数 DNode *q = p->next; //设q为p的后继结点 if(q==NULL) return false; //q不存在 p->next = q->next; //p后面连着q的后继结点或置空 if(q->next!=NULL) //若q后面还有结点 q->next->prior = p; //将q的后继结点连在p后面 free(q); //释放q的空间 } bool ListDelete(DLinkList &L,int i,ElemType &e){ if(i<1 || i>Length(L)) return false; //位序不合理 DNode *p = L; //p指向当前结点 int j = 0; //p当前所指结点的位序 while(p!=NULL && j<i-1){ //找到前驱结点 p = p->next; j++; } if(p==NULL) return false; //前驱结点不存在 if(p->next==NULL) return false; //该结点不存在 e = p->next->data; //e保存待删结点的数据域 return DeleteNextDNode(p); } //（4）双链表的销毁 bool DestroyList(DLinkList &L){ DNode *p = L; while(p!=NULL){ // 从头结点开始逐个释放 DNode *temp = p; p = p->next; free(temp); } L = NULL; return true; } //（5）打印双链表 void DisplayDList(DLinkList L){ if(Empty(L)){ printf("L是空表\n"); return; } DNode *p = L->next; printf("L："); while(p!=NULL){ printf("%d",p->data); if(p->next!=NULL) printf(" -> "); p = p->next; } printf("\n"); } int main(){ DLinkList L; if(InitDLinkList(L)) printf("初始化成功\n"); DisplayDList(L); printf("双链表的长度：%d\n",Length(L)); for(int i=1;i<5;i++){ ListInsert(L,i,2*i); } DisplayDList(L); printf("双链表的长度：%d\n",Length(L)); int x = 0; ElemType e = 0; printf("输入位序以删除结点："); scanf("%d",&x); if(ListDelete(L,x,e)) printf("删除成功\n"); else printf("删除失败\n"); DisplayDList(L); printf("双链表的长度：%d\n",Length(L)); printf("是否要销毁双链表？(1:是,2:否)"); int choice; scanf("%d",&choice); if(choice==1){ DestroyList(L); return 0; } DisplayDList(L); printf("双链表的长度：%d\n",Length(L)); }

5.循环链表

6.静态链表

7.栈

8.队列

9.串

10.ST表

11.堆

12.树状数组

13.线段树

14.Trie树

15.并查集

16.平衡树(利用系统自带的标准库实现)

三、算法

1.枚举

2.排序

①冒泡排序

②选择排序

③插入排序

④归并排序

⑤快速排序

⑥桶排序

⑦堆排序

⑧基数排序

3.搜索

①深度优先搜索(DFS)

②广度优先搜索(BFS)

③剪枝

④双向BFS

⑤记忆化搜索

⑥迭代加深搜索

⑦启发式搜索

4.贪心

5.模拟

6.二分

7.高精度

8.动态规划

①DP(普通一维问题)

②背包DP

③树形DP

④状压DP

⑤数位DP

⑥DP的常见优化

四、网课网站

浙江大学数据结构陈越_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1H4411N7oD/?spm_id_from=333.337.search-card.all.click&vd_source=6613dfdfd1c62e3011814de29af5aca9

五、刷题网站

一、引言

1.数据结构

2.算法

二、数据结构

1.顺序表(静态分配)

①定义

②抽象数据类型描述

③结构实现

④主要操作实现

⑤源代码

2.顺序表(动态分配)

①结构实现

②主要操作实现

⑤源代码

3.单链表(带/不带头结点)

①定义

②结构实现

③主要操作实现

④源代码

4.双链表

①定义

②结构实现

③主要操作实现

④源代码

5.循环链表

6.静态链表

7.栈

8.队列

9.串

10.ST表

11.堆

12.树状数组

13.线段树

14.Trie树

15.并查集

16.平衡树(利用系统自带的标准库实现)

三、算法

1.枚举

2.排序

①冒泡排序

②选择排序

③插入排序

④归并排序

⑤快速排序

⑥桶排序

⑦堆排序

⑧基数排序

3.搜索

①深度优先搜索(DFS)

②广度优先搜索(BFS)

③剪枝

④双向BFS

⑤记忆化搜索

⑥迭代加深搜索

⑦启发式搜索

4.贪心

5.模拟

6.二分

7.高精度

8.动态规划

①DP(普通一维问题)

②背包DP

③树形DP

④状压DP

⑤数位DP

⑥DP的常见优化

四、网课网站

五、刷题网站

1.洛谷

2.蓝桥杯官方题库

3.AcWing

4.力扣

Read more

大学计算机专业面向对象程序设计教程（C++）——基于电子工业出版社《面向对象程序设计教程——C++》（西安理工大学教材）——期末看完心里有底！

《C++ 递归、搜索与回溯》第1题：汉诺塔问题

C++ 虚函数与纯虚函数：多态的核心实现基石

C++可变参数队列与压栈顺序：从模板语法到汇编调用约定的深度解析