第一章 绪论
1.1 数据结构的基本概念
1.1.1 基本概念和术语
数据：是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
数据元素：是数据的基本单位，通常作为一个整体进行考虑和处理，一个数据元素可由若干数据项组成。
数据项：数据项是构成数据元素的不可分割的最小单位。
数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
数据结构：是相互之间存在一种或者多种特定关系的数据元素的集合。
同样的数据元素，可组成不同的数据结构；不同的数据元素，可组成相同的数据结构。
数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算 ，数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
数据类型：是一个值的集合和定义在此集合上的一组操作的总称，
1）原子类型：其值不可再分的数据类型
2) 结构类型：其值可再分解为若干成分（分量）的数据类型
3) 抽象数据类型（ADT）：是抽象数据组织及与之相关的操作
1.1.2 数据结构的三要素
数据的逻辑结构：
集合：各个元素同属一个集合，别无其他关系。
线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一的后继。（第二、三章）
树形结构：数据元素之间是一对多的关系。（第四章）
网状（图）结构：数据元素之间是多对多的关系。（第五章）
数据的运算：针对于某种逻辑结构，结合实际需求，定义基本运算。
数据的物理结构（存储结构）：数据结构在计算机中的表示（又称映像）
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
非顺序存储（离散存储）：
链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借组指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储：在存储元信息的同时，还建立附加的索引表。索引表中的每项称为索引项的一般形式是（关键字，地址）
散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储
数据结构的三要素：
1.若采用顺序存储，则各个数据元素在物理上必须是连续的，若采用非顺序存储，则各个数据元素在物理上可以是离散的。
2.数据的存储结构会影响存储空间分配的方便程度。
3.数据的存储结构会影响对数据运算的速度
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的指出运算的具体操作步骤。
1.2 算法和算法评价
1.2.1 算法的基本概念
算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。（可以用自然语言和伪代码或代码描述）
算法的特性（必须具备）
有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
PS：算法必须是有穷的，而程序可以无穷的
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
可以联系函数联想一下，y=f(x),y为输出，f为特定的算法,x为输入。
“好”算法的特质（设计算法时要尽量追求的目标）
1）正确性：算法应能够正确地解决求解问题。
2）可读性：算法应具有良好的可读性，以帮助人们理解。例：写注释
3）健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
4）高效率与低存储量需求
时间复杂度低 空间复杂度低
1.2.2 算法效率的度量
算法时间复杂度
算法效率的度量：是通过时间复杂度和空间复杂度来描述
事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”）
这里举例提出了两个问题，注意这都是建立在n趋于无穷大的前提下
引入大O表示法
证明了量级之间的比较（不需要会证明，要记住）
背记技巧
两个练习题方便理解
算法空间复杂度
算法原地工作--算法所需内存空间为常量
强调要求空间复杂度与问题规模相关
这里举例来说明复杂度的共性和计算方式
函数递归调用带来的内存开销（相关了解：函数调用栈）
其他（很少出现/考察）情况（定义的是数组时）它的算法空间复杂度则不一定为递归调用的深度
第二章 线性表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义 (数据元素三要素--逻辑结构)
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为
L=(,
,...,
)
是线性表中的“第i个”元素线性表中的位序 PS：位序从1开始 数组下标从0开始
是表头元素；
是表尾元素。
除了第一个元素外，每一个元素有且仅有一个直接前驱；除了最后一个元素外，每一个元素有且仅有一个直接后驱
2.1.2 线性表的基本操作
InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L)： 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
ListInsert(&L;i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
其他常用操作：
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
Tips:
1.对数据的操作（记忆思路）--创销增删改查
2.C语言函数的定义--<返回值类型>函数名（<参数1类型>参数1，<参数2类型>参数2，......）
3.实际开发中，可根据实际需求定义其他的基本操作
4.函数名和参数的形式、命名都可改变（Reference:严蔚敏版《数据结构》）Key：命名要有可读性
5.什么时候要传入引用“&”--对参数的修改结果需要“带回来” （个人理解：全局、局部变量的区别）
举例：
#include<stdio.h>
void test(int x){
x=1024;
printf("test函数内部 x=%d\n",x);
}
int main(){
int x=1;
printf("调用test前 x=%d\n",x);
test(x);
printf("调用test后 x=%d\n",x);
} 运行结果：
2.2 线性表的顺序表示
2.2.1 顺序表的定义
顺序表的定义：用顺序存储的方式来实现线性表顺序存储。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
C语言里 sizeof(ElemType) 可以获取到目标数据元素类型的大小。
ElemType就是你的顺序表中存放的数据元素类型
顺序表的实现--静态分配
//顺序表的实现--静态分配
#include<stdio.h>
#define MaxSize 10 //定义表的最大长度
typedef struct{
int data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++){
L.data[i]=0; //将所有数据元素设置为默认初始值
}
L.length=0;
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化一个顺序表
for(int i=0;i<MaxSize;i++){ //顺序表的打印
printf("data[%d]=%d\n",i,L.data[i]);
}
return 0;
}1.初始化的重要性：如果不进行初始化一个顺序表，会因为内存残留的数据而产生干扰
(系统给予我们的空间对于我们来说是未知的，内存中有遗留的“脏数据”)
2.L.length的重要性：因为第1点，所有我们在循环遍历数组的时候，要用length来表示，减少对第1点的犯错几率并且此改动利于算法的优化 （这种访问方式也不够好，更多的做法是用基本操作来访问各个数据元素 eg:GetElem(L;i)）
（修正后的代码）
//顺序表的实现--静态分配
#include<stdio.h>
#define MaxSize 10 //定义表的最大长度
typedef struct{
int data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
void InitList(SqList &L){
for(int i=0;i<L.length;i++){
L.data[i]=0;
}
L.length=0; //将所有数据元素设置为默认初始值（可省略）
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化一个顺序表
for(int i=0;i<L.length;i++){ //顺序表的打印
printf("data[%d]=%d\n",i,L.data[i]);
}
return 0;
}3.静态分配遇到需要扩充数组时，这种静态存储空间是无法改变的；（可以考虑用新数组替换--动态分配的精髓）
顺序表的实现--动态分配
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的定义类型(动态分配方式)Key:动态申请和释放内存空间
C--malloc free函数
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize)
当我们申请一片空间时malloc函数会返回一个指针，需要强制转型为你定义的数据元素类型指针
malloc函数的参数，要指明要分配多大的连续内存空间（ps:InitSize）
C++--new delete 关键字
动态分配的底层逻辑
//顺序表的实现——动态分配
#include<stdio.h>
#include<stdlib.h> //malloc、free函数的头文件
#define InitSize 10 //默认的初始值
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SeqList &L){ //初始化
//用malloc 函数申请一片连续的存储空间
L.data =(int*)malloc(InitSize*sizeof(int)) ;
L.length=0;
L.MaxSize=InitSize;
}
void IncreaseSize(SeqList &L,int len){ //增加动态数组的长度
int *p=L.data;
L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len
free(p); //释放原来的内存空间
}
int main(){
SeqList L; //声明一个顺序表
InitList(L); //初始化顺序表
IncreaseSize(L,5);//增加顺序表的长度
return 0;
}我们定义一个int类型的顺序表，创建一个InitList（SeqList &L）来初始化顺序表
增加动态数组的函数IncreaseSize；其中在IncreaseSize函数里使用malloc和free函数来创建和释放顺序表存储空间。
1.运行第一模块代码，计算机开辟一个空间来装*data、MaxSize、length的变量
2.运行第二模块代码，计算机开始初始化顺序表，通过malloc来申请一块地址空间来存储顺序表，malloc返回一个指针，而后强行转换为int类型的指针，把指针的数据赋值给data（起始地址）设置顺序表的长度为0；并且使得MaxSize的大小与申请的一致。
3.数据填入后；需要扩充时，调用IncreaseSize函数；（首先，把data的起始地址给予*p；然后重新运用malloc函数来开辟空间，把旧顺序表的数据复制到新的区域；MaxSize的值重新赋值+5，最后释放原来的存储空间）ps:data和p两个指针在函数调用时完成了一个地址传递
这里的复制操作使得时间开销很大（可以了解一下realloc函数）
顺序表的特点
1.随机访问,即可以在O(1)的时间内找到第i个元素
2.存储密度高，每个节点只存储数据元素
3.扩展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
4.插入、删除操作不方便，需要移动大量元素
2.2.2 顺序表上基本操作的实现
顺序表的基本操作--插入
再次注意位序和数组下标的区别
下面是代码演示
#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct {
int data[MaxSize]; //用静态的数组存放数据
int length; //顺序表的当前长度
} SqList; //顺序表的类型定义
// 初始化顺序表
void InitList(SqList& L) {
L.length = 0;
}
// 在顺序表L中的第i个位置插入新元素e
bool ListInsert(SqList& L, int i, int e) {
if (i < 1 || i > L.length + 1)
return false;
if (L.length >= MaxSize)
return false;
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
//打印顺序表
void PrintList(SqList& L) {
printf("顺序表的元素为：");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
int main() {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
// 假设此处插入一些元素，例如插入数组data中的元素
int data[MaxSize] = { 1, 2, 3, 4, 5 };
for (int i = 0; i < 5; i++) {
ListInsert(L, i + 1, data[i]);
}
// 打印当前顺序表状态
PrintList(L);
// 插入新元素3到位置3
if (ListInsert(L, 3, 3)) {
printf("插入成功。\n");
}
else {
printf("插入失败。\n");
}
// 再次打印当前顺序表状态
PrintList(L);
return 0;
}当我第一次打这个代码的时候遇到了这些问题
1.const修饰符功能的遗忘
2.PrintList的代码编程时顺序表L的数据没有得到载入（是因为&的使用出现差错）
时间复杂度的计算
顺序表的基本操作--删除
int a和int &a都是指向的同一块地址，用的同一个内容
下面是代码演示
//#include <stdio.h>
//#define MaxSize 10
//
//typedef struct {
// int data[MaxSize];
// int length;
//} SqList;
//
删除顺序表i位置的数据并存入e
//bool ListDelete(SqList* L, int i, int* e) { // 修改为使用指针
// if (i < 1 || i > L->length) { // 判断i的范围是否有效
// return false;
// }
// *e = L->data[i - 1]; // 将被删除的元素赋值给e
// for (int j = i - 1; j < L->length - 1; j++) { // 从后向前移动元素
// L->data[j] = L->data[j + 1];
// }
// L->length--; // 减少长度
// return true;
//}
//
//void InitList(SqList* L) { // 修改为使用指针
// L->length = 0;
//}
//
打印顺序表
//void PrintList(SqList* L) { // 修改为使用指针
// printf("顺序表的元素为：");
// for (int i = 0; i < L->length; i++) {
// printf("%d ", L->data[i]);
// }
// printf("\n");
//}
//
//int main() {
// SqList L;
// InitList(&L); // 使用指针初始化顺序表
// for (int i = 0; i < 5; i++) { // 只填充5个元素
// L.data[i] = i + 1; // 填充元素
// }
// L.length = 5; // 设置顺序表的长度为5
//
// PrintList(&L); // 打印顺序表
//
// int e;
// if (ListDelete(&L, 3, &e)) { // 传递L的地址和e的地址
// printf("已删除第3个元素，删除元素值为%d\n", e);
// PrintList(&L); // 打印删除元素后的顺序表
// }
// else {
// printf("位序i不合法，删除失败\n");
// }
// return 0;
//}
#include <stdio.h>
#define MaxSize 10
typedef struct {
int data[MaxSize];
int length;
} SqList;
// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList* L, int i, int* e) { // 修改为使用指针
if (i < 1 || i > L->length) { // 判断i的范围是否有效
return false;
}
*e = L->data[i - 1]; // 将被删除的元素赋值给e
for (int j = i - 1; j < L->length - 1; j++) { // 从后向前移动元素
L->data[j] = L->data[j + 1];
}
L->length--; // 减少长度
return true;
}
void InitList(SqList* L) { // 修改为使用指针
L->length = 0;
}
// 打印顺序表
void PrintList(SqList* L) { // 修改为使用指针
printf("顺序表的元素为：");
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\n");
}
int main() {
SqList L;
InitList(&L); // 使用指针初始化顺序表
for (int i = 0; i < 5; i++) { // 只填充5个元素
L.data[i] = i + 1; // 填充元素
}
L.length = 5; // 设置顺序表的长度为5
PrintList(&L); // 打印顺序表
int e;
if (ListDelete(&L, 3, &e)) { // 传递L的地址和e的地址
printf("已删除第3个元素，删除元素值为%d\n", e);
PrintList(&L); // 打印删除元素后的顺序表
}
else {
printf("位序i不合法，删除失败\n");
}
return 0;
}注释的代码依然是正确的只是在输出时会输出无内容的数组数据（数组越界的原因---有点懵）
要及时更新length的值
代码的健壮性
代码的健壮性指的是程序能够优雅地处理错误情况、异常输入和边界条件，而不会导致崩溃或未定义行为。提高代码的健壮性通常涉及以下几个方面：
1. **输入验证**：检查所有输入数据是否有效，包括用户输入、函数参数和来自外部源的数据。
2. **错误处理**：合理地处理错误情况，例如使用返回值、异常或错误代码来指示函数调用失败的原因。
3. **边界条件检查**：确保程序能够处理数组和集合的边界情况，例如空数组、数组的最小和最大容量。
4. **资源管理**：确保所有分配的资源（如内存、文件句柄等）在使用后都能被正确释放，避免资源泄漏。
5. **异常安全**：设计程序使其能够从异常中恢复，不会导致数据损坏或不一致。
6. **并发和线程安全**：如果程序是多线程的，确保共享资源的访问是安全的，避免竞态条件和死锁。
7. **鲁棒的第三方库使用**：如果使用了第三方库，确保理解其行为，并妥善处理可能的失败情况。
8. **日志记录**：记录关键操作和错误信息，以便于调试和追踪问题。
9. **单元测试**：编写测试用例来验证代码的各个部分按预期工作，包括正常情况和边缘情况。
10. **代码审查**：定期进行代码审查，以发现潜在的错误和改进代码质量。
顺序表的基本操作--按位查找
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
静态分配
#define MaxSize 10 //定义最大长度
typedef struct {
ElemType data[MaxSize]; //用静态的“数组”存放数据元素（静态分配）
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
ElemType GetElem(SqList L, int i) {
return L.data[i - 1];
}动态分配
#define MaxSize 10 //顺序表的初始长度
typedef struct {
ElemType *data; //指示动态分配数组的指针（动态分配）
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（动态分配方式）
ElemType GetElem(SqList L, int i) {
return L.data[i - 1];
}
当执行这行代码时，计算机会根据指针的类型的所占用的数据类型空间大小来计算每一个数组下标所对应的字节数据（个人理解：调用时data指向顺序表开始位置的地址，根据类型的大小来划分字节数据给予数组）
时间复杂度：O(1) 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素--“随机存取”特性
顺序表的基本操作--按值查找
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素
#define InitSize 10 //定义最大长度
typedef struct{
ElemTyp *data; //用静态的“数组”存放数据元素
int Length; //顺序表的当前长度
}SqList;
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, ElemType e){
for(int i=0; i<L.lengthl i++)
if(L.data[i] == e)
return i+1; //数组下标为i的元素值等于e，返回其位序i+1
return 0; //推出循环，说明查找失败
}
//调用LocateElem(L,9)在L.data[i] == e的比较时，要注意如果是结构体的比较不能直接用“==”；需要依次对比各个分量来判断两个结构体是否相等（也可以重载运算符）
时间复杂度
附：动态分配顺序表的基本操作
//顺序表————动态分配
#define InitSize 5 // 顺序表初始长度
#include <iostream>
#include <stdio.h>
using namespace std;
struct SqList {
int* data; // 数组
int MaxSize; // 顺序表的最大长度
int length; // 顺序表的当前长度
};
// 初始化顺序表
void InitList(SqList& L) {
L.data = new int[InitSize];
L.MaxSize = InitSize;
L.length = 0;
}
// 为顺序表中的数据赋值
void AssginList(SqList& L) {
for (int i = 0; i < InitSize; i++) {
L.data[i] = i;
L.length++;
}
}
// 求表长
int Length(SqList& L) { return L.length; }
// 动态增加顺序表长度
void IncreaseSize(SqList& L, int len) {
int* p = L.data;
L.data = new int[L.MaxSize + len];
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i]; // 将原数据赋值到新内存中
}
L.MaxSize = L.MaxSize + len;
delete p;
}
// 按位查找：查找第i个位置的元素
int GetElem(SqList& L, int i) {
return L.data[i - 1];
}
// 按值查找：查找值为i的元素位置
int LocateElem(SqList& L, int i) {
for (int j = 0; j < L.length; j++) {
if (L.data[j] == i) {
return j + 1;
}
}
return 0; // 没有查找到则返回0
}
// 插入：在第i个位置插入e
void ListInsert(SqList& L, int i, int e) {
if (L.length = L.MaxSize) { // 内存已满需要扩充
IncreaseSize(L, 1);
}
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1]; // 插入位置之后的数据后移
}
L.data[i - 1] = e;
L.length++;
}
// 删除：删除第i个位置的元素
bool ListDelete(SqList& L, int i, int& e) {
if (i < 0 || i > L.length) { // 删除超出范围
return false;
}
e = L.data[i - 1];
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j]; // 数据前移
}
L.data[L.length] = 0; //最后一个元素初始化
L.length--;
return true;
}
// 按顺序输出
void PrintList(SqList& L) {
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
}
int main() {
struct SqList L;
InitList(L);
AssginList(L);
PrintList(L);
// 求表长
int len = Length(L);
cout << "表长：" << len << endl;
// 插入数据
ListInsert(L, 3, 44);
Length(L);
PrintList(L);
// 删除数据
int e = -1;
if (ListDelete(L, 3, e)) {
cout << "删除的数据：" << e << endl;
PrintList(L);
}
else {
cout << "删除数据超出范围" << endl;
}
// 按值查找
int locate_elem;
locate_elem = LocateElem(L, 3);
cout << "查找到的位置：" << locate_elem << endl;
// 按位查找
int get_elem;
get_elem = GetElem(L, 3);
cout << "查找到的数据：" << get_elem << endl;
}
2.3 线性表的链式表示
2.3.1 单链表的定义
单链表（线性表的链式存储）：是指通过一组任意的存储单元来存储线性表中的数据元素。各结点间的前后关系用一个指向其后继的指针表示。
PS:单链表非随机存取的数据结构
头结点和头指针的关系
不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点通常不存储信息。
引入头结点后的优点：
1.由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2.无论链表是否为空，其头指针都是指向头结点的非空指针（空表中的头结点的指针域为空），
因此空表和非空表的处理得到了统一。
代码定义演示
//定义一个单链表
struct LNode { //定义单链表结点类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节电
};
struct LNode* p = (struct LNode*)malloc(sizeof(struct LNode));
//增加一个新的结点，在内存中申请一个结点所需空间，并用指针p指向这个结点在这个代码基础上，可以用typedef<数据类型><别名>
等效：
typedef struct LNode LNode;
LNode *p = (LNode *) malloc (sizeof(LNode))
综上所述：
//定义一个单链表
typedef struct LNode { //定义单链表结点类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节电
}LNode , *LinkList;
//等效于
struct LNode { //定义单链表结点类型
ElemType data; //每个节点存放一个数据元素
struct LNode* next; //指针指向下一个节电
}；
typedef struct LNode LNode;
typedef struct LNode *LinkList;要表示一个单链表时，只需要声明一个头指针L,指向单链表的第一个结点
LNode * L;//声明一个指向单链表第一个结点的指针
或；LinkList L;//声明一个指向单链表第一个结点的指针 (代码可读性更强)
Tips:使用LinkList：强调这是一个单链表 使用 LNode *：强调这是一个结点
不带头结点的单链表
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL; //空表，暂时还没有任何结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的头指针
//初始化一个空表
InitList(L);
...
}
//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL)
}带头结点的单链表
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个单链表（带头结点）
bool InitList(LinkList &L)
{
L = (LNode*) malloc(sizeof(LNode)); //头指针指向的结点——分配一个头结点（不存储数据）
if (L == NULL) //内存不足，分配失败
return false;
L -> next = NULL; //头结点之后暂时还没有结点
return true;
}
void test()
{
LinkList L; //声明一个指向单链表的指针: 头指针
//初始化一个空表
InitList(L);
//...
}
//判断单链表是否为空（带头结点）
bool Empty(LinkList L)
{
if (L->next == NULL)
return true;
else
return false;
}
个人理解：
单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。在单链表中，可以引入一个特殊的节点，称为头结点。头结点是链表的第一个节点，但它不存储实际的数据，而是作为链表的起始点。引入头结点有以下几个好处：
1. 统一处理：在单链表中，头结点使得空表和非空表的处理方式统一。即使链表为空，头结点也存在，这使得我们可以在链表为空时返回一个有效的指针。
2. 简化操作：头结点的存在简化了对链表的某些操作，如插入和删除节点。在头结点后面插入或删除节点时，不需要单独处理空表的情况。
3. 提高安全性：在某些情况下，头结点可以防止对空链表的非法访问。例如，如果链表为空，那么所有操作都应该在头结点之后进行，而不是直接访问数据域。
4. 方便实现：在某些链表实现中，头结点可以包含链表的长度信息，或者指向链表尾部的指针，这样可以快速地获取链表的长度或进行尾部操作。
5. 提高效率：在某些算法中，如归并排序，头结点可以方便地链接两个已排序的链表。
6. 保护数据：如果链表的节点是通过指针访问的，头结点可以防止在删除第一个节点时丢失对链表的引用。
总的来说，头结点提供了一个统一的接口来处理链表的各种操作，使得链表的实现更加灵活和安全。
具象一点理解：
想象一下，你正在一家图书馆，图书馆的书架上摆满了书籍，每本书都像链表中的一个节点，而书架的开始处有一个特殊的牌子或者标志，我们称之为“头结点”。这个头结点并不存储任何书籍，但它标志着书架的开始，让读者知道从哪里开始查找书籍。
1. 统一的起点：无论书架上有多少书，读者总是从这个头结点开始查找，这就像无论链表中有多少节点，我们总是从头结点开始访问。
2. 简化查找：如果书架上没有书（空链表），头结点依然存在，它告诉读者书架是空的。这避免了读者直接去书架上找书时可能会遇到的困惑。
3. 安全访问：如果有人想借阅第一本书，他们需要从头结点开始，然后移动到下一本书（第一个节点）。如果没有头结点，读者可能会错误地认为书架的开始就是书籍的开始，这可能会导致对空书架的非法访问。
4. 方便管理：图书馆管理员可以在头结点上记录书架上书籍的总数，或者在需要时快速找到书架的末尾。这类似于链表头结点可以存储链表长度或指向尾部的指针。
5. 提高效率：当需要将两排书架上的书籍合并时，管理员可以从两个头结点开始，快速地将书籍按顺序排列。这类似于链表操作中的归并排序。
6. 保护资源：如果书架上的第一本书被借走了，头结点确保了书架的其余部分仍然可以被访问。这避免了因为移除第一个节点而导致对整个链表的访问丢失。
通过这个比喻，我们可以看到头结点在单链表中的作用就像图书馆的头结点牌子一样，它提供了一个清晰的起点，简化了操作，提高了安全性和效率。
对比图
2.3.2 单链表上基本操作的实现
-
带头结点的单链表初始化
bool InitList(LinkList &L){
L=(LNode*)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //头结点之后暂时还没有元素结点
return true;
}-
不带头结点的单链表初始化
bool InitList(LinkList &L){
L=NULL; //头结点之后暂时还没有元素结点
return true;
}-
求表长操作
int Length(LinkList L){
int len=0; //计数变量，初始为0
LNode *p=L;
while(p->next!=NULL){
p=p->next;
len++; //每访问一个结点，计数加1
}
return len;
}时间复杂度为O(n).PS:因为单链表的长度是不包括头结点的，因此不带头结点和带头结点的单链表在求表长操作上会略有不同。
-
插入-按位序插入（带头结点）
Listinsert(&L,i,e): 插入操作，在表L中的第i个位置上插入指定元素e.
找到第i-1个结点，将新结点插入其后
#include <stdio.h>
#include<stdlib.h>
typedef struct LNode{ //定义单链表结点类型
int data; //数据域
struct LNode *next; //指针域 (为什么next指针域要定义为struct LNode呢，)
}LNode, *LinkList;
//(为什么next指针域要定义为struct LNode呢?)
//next指针用来指向链表的下一个结点，该结点同样为一个LNode结构体，
//因此next要声明为指向LNode结构体的指针struct LNode*
bool InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e){
//判断i的合法性, i是位序号(从1开始)
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后会等于NULL
p = p->next; //p指向下一个结点
j++;
}
if (p==NULL) //i值不合法
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
s->data = e;
s->next = p->next;
p->next = s; //将结点s连到p后,后两步千万不能颠倒qwq
return true;
}
void test()
{
LinkList L;
if(InitList(L))
printf("true");
printf("\n");
ListInsert(L,1,3);
ListInsert(L,2,5);
LNode *s = L->next;
while(s)
{
printf("%d ",s->data);
s = s->next;
}
return;
}
int main(void)
{
test();
return 0;
}平均时间复杂度：O(n)
-
插入-按位序插入（不带头结点）
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL; //初始化为空表
return true;
}
//判断单链表是否为空
bool Empty(LinkList L){
if(L == NULL)
return true;
else
return false;
}
//在第i个位置插入结点（不带头结点）
bool ListInsert(LinkList &L, int i, int e){
if(i<1) //判断插入位置是否在合理范围内
return false;
if(i==1){ //插入第1个结点的操作与其它结点不同,需要特殊处理
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s; //头指针指向新结点
return true;
}
LNode *p; //定义指针p，指向当前扫描到的结点
int j=1; //j为当前p指向第几个结点
p = L; //p指向第1结点（不是头结点）
while(p!=NULL && j< i-1){
p = p->next;
j++;
}
if(p==NULL) //i值不合法（超出队尾）
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
}由于带头结点和不带头结点的按序插入的代码对比；不带头结点的单链表每次编写时都要对插入第一个结点操作情况时进行单独处理；而有头结点的单链表时，则不用（头结点的作用显现出来了）
-
指定结点的后插操作
InsertNextNode(LNode *p, ElemType e)；
给定一个结点p，在其之后插入元素e; 根据单链表的链接指针只能往后查找，故给定一个结点p，那么p之后的结点我们都可知，但是p结点之前的结点无法得知
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool InsertNextNode(LNode *p, ElemType e)
{
if(p==NULL){
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
//某些情况下分配失败，比如内存不足
if(s==NULL)
return false;
s->data = e; //用结点s保存数据元素e
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
} //平均时间复杂度 = O(1)
//有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成：
bool ListInsert(LinkList &L, int i, ElemType e)
{
if(i<1)
return False;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后4鸟会等于NULL
p = p->next; //p指向下一个结点
j++;
}
return InsertNextNode(p, e)
}
- 指定结点的前插操作
第一种方法思路
第二种方法思路（腾窝操作）
-
删除-按序删除（带头结点）
ListDelete(&L, i, &e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值;头结点视为“第0个”结点；
思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool ListDelete(LinkList &L, int i, ElenType &e){
if(i<1) return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后会等于NULL
p = p->next; //p指向下一个结点
j++;
}
if(p==NULL)
return false;
if(p->next == NULL) //第i-1个结点之后已无其他结点
return false;
LNode *q = p->next; //令q指向被删除的结点
e = q->data; //用e返回被删除元素的值
p->next = q->next; //将*q结点从链中“断开”
free(q) //释放结点的存储空间
return true;
}
-
指定结点的删除
时间复杂度：O(1)
bool DeleteNode(LNode *p){
if(p==NULL)
return false;
LNode *q = p->next; //令q指向*p的后继结点
p->data = p->next->data; //让p和后继结点交换数据域
p->next = q->next; //将*q结点从链中“断开”
free(q);
return true;
} //时间复杂度 = O(1)考虑一个情况：如果删除的就是最后一个参数，p->data = p->next->data;这行代码就会报错，唯一的方法就是只能从表头开始依次寻找p的前驱（时间复杂度O(n)）
这里这个问题暴露了单链表的局限性（无法逆向检索，有时候不太方便）
-
单链表的查找-按位查找
GetElem(L, i): 按位查找操作，获取表L中第i个位置的元素的值;
平均时间复杂度O(n)
LNode * GetElem(LinkList L, int i){
if(i<0) return NULL;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点,头结点是第0个结点(不存数据)
while(p!=NULL && j<i){ //循环找到第i个结点
p = p->next;
j++;
}
return p; //返回p指针指向的值
}-
单链表的查找-按值查找
LocateElem(L, e):按值查找操作，在表L中查找具有给定关键字值的元素;
平均时间复杂度:O(n)
LNode * LocateElem(LinkList L, ElemType e){
LNode *P = L->next; //p指向第一个结点
//从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data != e){
p = p->next;
}
return p; //找到后返回该结点指针，否则返回NULL
}-
单链表的建立-尾插法
平均时间复杂度O(n)
思路：每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。好处：生成的链表中结点的次序和输入数据的顺序会一致。
// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){
int x; //设ElemType为整型int
L = (LinkList)malloc(sizeof(LNode)); //建立头结点(初始化空表)
LNode *s, *r = L; //r为表尾指针
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表示结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指针指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}-
单链表的建立-头插法（和输入值逆序）
平均时间复杂度O(n)
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
L->next = NULL; //初始为空链表,这步不能少！
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表结束
s = (LNode *)malloc(sizeof(LNode)); //创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}2.3.3 双链表
- 来由、作用：为了克服单链表在访问某个结点的前驱（插入、删除操作时），只能从头开始遍历的问题，引入双链表
双链表结点中有两个指针prior和next,分别指向其直接前驱和直接后驱。
- 双链表的结点类型
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后驱指针
}DNode,*DLinklist;- 双链表的初始化
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinklist;
//初始化双链表
bool InitDLinkList(Dlinklist &L){
L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->prior = NULL; //头结点的prior指针永远指向NULL
L->next = NULL; //头结点之后暂时还没有结点
return true;
}
void testDLinkList(){
//初始化双链表
DLinklist L; // 定义指向头结点的指针L
InitDLinkList(L); //申请一片空间用于存放头结点，指针L指向这个头结点
//...
}
//判断双链表是否为空
bool Empty(DLinklist L){
if(L->next == NULL) //判断头结点的next指针是否为空
return true;
else
return false;
}- 双链表的插入操作
过程图
1. s->next=p->next;
2. p->next->prior=s;
3. s->prior=p;
4. p->next=s;- 双链表的删除操作
过程图
1. p->next=q->next;
2. q->next->prior=p;
free(q); //释放结点空间- 双链表的实现
#include<bits/stdc++.h>
using namespace std;
typedef struct DNode{
int data;
struct DNode *prior,*next;
}DNode, *DLinkList;
//初始化
void InitList(DLinkList &L){
L = (DNode *)malloc(sizeof(DLinkList));
L->prior = NULL;
L->next = NULL;
}
//遍历操作
void PrintList(DLinkList L){
DNode *p = L->next;
while(p){
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
//求双链表的长度
int Length(DLinkList L){
DNode *p = L->next;
int len = 0;
while(p){
len++;
p = p->next;
}
return len;
}
//头插法建立双链表
DLinkList HeadInsert(DLinkList &L){
InitList(L); //初始化
int x;
cin>>x;
while(x!=9999){
DNode *s = (DNode *)malloc(sizeof(DNode));
s->data = x;
if(L->next == NULL){
s->next = NULL;
s->prior = L;
L->next = s;
}else{
s->next = L->next;
L->next->prior = s;
s->prior = L;
L->next = s;
}
cin>>x;
}
return L;
}
//尾插法建立双链表
DLinkList TailInsert(DLinkList &L){
InitList(L);
DNode *s,*r=L;
int x;
cin>>x;
while(x!=9999){
s = (DNode *)malloc(sizeof(DNode));
s->data = x;
s->next = NULL;
s->prior = r;
r->next = s;
r = s;
cin>>x;
}
return L;
}
//按值查找：查找x在L中的位置
DNode *LocateElem(DLinkList L, int x){
DNode *p = L->next;
while(p && p->data != x){
p = p->next;
}
return p;
}
//按位查找：查找在双链表L中第i个位置的结点
DNode *GetElem(DLinkList L, int i){
int j=1;
DNode *p = L->next;
if(i==0)return L;
if(i<1)return NULL;
while(p && j<i){
p = p->next;
j++;
}
return p; //如果i大于表长，p=NULL,直接返回p即可
}
//将x插入到双链表L中*p结点的下一个结点
void Insert(DLinkList &L, DNode *p, int x){
DNode *s = (DNode *)malloc(sizeof(DNode));
s->data = x;
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
//删除操作:将双链表中的第i个结点删除
void Delete(DLinkList &L, int i){
if(i<1 || i>Length(L)){
cout<<"delete failed: index is wrong."<<endl;
return;
}
DNode *p = GetElem(L,i-1);
DNode *q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
}
//判空操作
bool Empty(DLinkList L){
if(L->next == NULL){
cout<<"L is null"<<endl;
return true;
}else{
cout<<"L is not null"<<endl;
return false;
}
}
int main(){
//尾插法建立双链表，并遍历单链表
DLinkList L = TailInsert(L);
cout<<"L: ";
PrintList(L);
DNode *p;
//按值查找
p = LocateElem(L,2);
cout<<"值为2的结点的下一个结点值是："<<p->next->data<<endl;
cout<<"值为2的结点的上一个结点值是："<<p->prior->data<<endl;
//按位查找
p = GetElem(L,3);
cout<<"第三个结点值是："<<p->data<<endl;
//插入操作
Insert(L,p,7);
cout<<"在第三个结点后面插入值为7的结点后L： ";
PrintList(L);
//删除操作
Delete(L, 5);
cout<<"删除第五个结点后L： ";
PrintList(L);
//求表长
cout<<"表长为："<<Length(L)<<endl;;
//判空
Empty(L);
return 0;
}2.3.4 循环链表
-
循环单链表
在单链表的基础上，最后一个结点的指针不是NULL,而是指向头结点
typedef struct LNode{
ElemType data;
struct LNode *next;
}DNode, *Linklist;
/初始化一个循环单链表
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->next = L; //头结点next指针指向头结点
return true;
}
//判断循环单链表是否为空（终止条件为p或p->next是否等于头指针）
bool Empty(LinkList L){
if(L->next == L)
return true; //为空
else
return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
if(p->next == L)
return true;
else
return false;
}单链表和循环单链表的区别
单链表：从一个结点出发只能找到该结点后续的各个结点；对链表的操作大多都在头部或者尾部；设立头指针，从头结点找到尾部的时间复杂度=O(n)，即对表尾进行操作需要O(n)的时间复杂度;
循环单链表：从一个结点出发，可以找到其他任何一个结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾进行操作都只需要O(1)的时间复杂度
循环单链表优点：从表中任一节点出发均可找到表中其他结点。
-
循环双链表
在双链表的基础上，表头结点的prior指向表尾结点，表尾结点的next指向头结点
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinklist;
//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
L = (DNode *) malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->prior = L; //头结点的prior指向头结点
L->next = L; //头结点的next指向头结点
}
void testDLinkList(){
//初始化循环单链表
DLinklist L;
InitDLinkList(L);
//...
}
//判断循环双链表是否为空
bool Empty(DLinklist L){
if(L->next == L)
return true;
else
return false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){
if(p->next == L)
return true;
else
return false;
}-
循环链表的插入（双链表的演示）
//在p指针后，插入s指针指向的内容
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;-
循环链表的删除（双链表的演示）
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);2.3.5 静态链表
定义：用数组的方式实现的链表，其指针域的指针指向的是其数组的下标，和顺序表一样，静态链表也要预先分配一块连续的内存空间。
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始找；容量固定不可变
PS:0号结点充当“头结点” 游标为-1表示已经到达表尾 用一个特殊的数值来标记空闲结点
适用场景：1.不支持指针的低级语言
2.数据元素数量固定不变的场景（如操作系统的文FAT）
代码演示：
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标(游标)
};
//用数组定义多个连续存放的结点
void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表, 每一个数组元素的类型都是struct Node
//...
}创建一个链表，并且用数组来存放，每一个数组元素都是struct Node 侧重点为a是一个Node类型的数组
还有一种定义方式
#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ELemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
}这种方式的侧重点为运用SLinkList定义了一个长度为MaxSize的Node型数组
(两种方式的差距可以参考LinkList LNode*的区别，便于理解)
2.3.6 顺序表和链表的比较（开放式问题答题思路）
-
逻辑结构
都属于线性表，都是线性结构
-
存储结构
-
数据的运算/基本操作
