2.1 线性表的定义和基本操作

要点：

线性表的基本操作——创销、增删、改查
传入参数时，何时要用引用 &

线性表是具有相同数据类型的 $n$ 个数据元素的有限序列。 $n$ 表示表长，当 $n = 0$ 时线性表是一个空表。若用 $L$ 命名线性表，则一般表示为 $L = (a_{1}, a_{2}, \dots, a_{i}, \dots, a_{n})$ ，其中 $i$ 表示元素在线性表中的位序，从一开始。

存在唯一的第一个元素，即表头元素。
存在唯一的最后一个元素，即表尾元素。
除第一个元素（表头元素）之外，每个元素均只有一个直接前驱。
除最后一个元素（表尾元素）之外，每个元素均只有一个直接后继。

线性表的基本操作

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。

物理结构

顺序存储结构：顺序表。
链式存储结构：链表。

2.1.3 本节习题精选

选择题：题目、答案

2.2 线性表的顺序表示

2.2.1 顺序表的定义

顺序表的定义.pdf

顺序表：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来实现。 $i$ 是元素 $a_{i}$ 在线性表中的位序。顺序表有以下特点：

随机访问，可以在 $O (1)$ 时间内找到对应元素。
存储密度高，只用存储数据本身，不需要存储指针。
拓展容量不方便。
插入删除操作不方便。
表中元素的逻辑地址与物理地址顺序相同。

静态分配

顺序表的实现———静态分配

#include <stdio.h>
#define MaxSize 10	//定义最大长度
typedef struct{
	int data[MaxSize];	//用静态的“数组”存放数据元素 ElemType:int
	int Length;			//顺序表的当前长度
}SqList;	//顺序表的类型定义
 
//基本操作——初始化一个顺序表
void InitList(SqList &L){
	for(int i = 0; i < MaxSize; i++){
		L.data[i] = 0;//将所有数据元素设置为默认初始值0,如果没有这一步，内存中会有遗留的“脏数据”
	}
	L.Length = 0;		//顺序表初始长度为0
}
 
int main(){
	SqList L;	//声明一个顺序表
	//在内存里分配存储顺序表L的空间
	//包括MaxSize*sizeof(ElemType)和存储length的空间
	InitList(L);	//初始化这个顺序表
	//...
	return 0;
}

Q- 如果“数组”存满了怎么办？

A- 存储空间是静态的，顺序表的表长确定后就无法更改。

动态分配

顺序表的实现——动态分配

malloc函数：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize) 其中(ElemType*)可强制转换数据类型
free函数

#include <stdlib.h>	//包含malloc,free函数的头文件
#define InitSize 10	//默认的最大长度
 
typedef struct{
	int *data;		//指示动态分配数组的指针，指向第一个元素
	int MaxSize;	//顺序表的最大容量
	int length;		//顺序表的当前长度
}SeqList;
 
void InitSize(SeqList &L){
	L.data = (int*)malloc(sizeof(int)*InitSize);	//用malloc函数申请一片连续的存储空间
	L.length = 0;
	L.MaxSize = InitSize;
}
 
int main(){
	SeqList L;
	InitSize(L);
	//...其余操作
	IncreaseSize(L,5);
	return 0;
}
 
//增加动态数组的长度
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);	//释放原来的内存空间
}

2.2.2 顺序表上基本操作的实现

顺序表的插入删除.pdf

插入操作

顺序表基本操作——插入：ListInsert(&L, i, e)

基于静态分配的代码实现

//个人理解：插入位置之后的元素从后往前依次后移一位，给插入的元素腾出位置
 
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int Length;
}SqList;
 
//基本操作——在L的位序i处插入元素e
bool ListInsert(SqList &L, int i, int e){
	//判断i的范围是否有效
	if(i < 1 || i > L.length + 1)	//越界
		return false;
	if(L.length > MaxSize)			//存储空间已满
		return false;
 
	for(int j = L.length; j > i; j--){	//将第i个元素及其之后的元素后移
		L.data[j] = L.data[j - 1];	//注意数组下标从零开始，而位序从1开始
	}
	L.data[i - 1] = e;	//在位置i处放入e
	L.length++;			//长度加1
	return true;
}
 
int main(){
	SqList L;		//声明一个顺序表
	InitList(L);	//初始化这个顺序表
	//...插入几个元素
	ListInsert(L, 3, 3);
	return 0;
}

时间复杂度分析

关注最深层循环语句——L.data[j] = L.data[j - 1]的执行次数与问题规模 $n$ ——L.length的关系；
最好情况：插入表尾，不需要移动元素， $i = n + 1$ ，循环 $0$ 次；最好时间复杂度 $= O (1)$
最坏情况：插入表头，需要将原有的 $n$ 个元素全都向后移动， $i = 1$ ，循环 $n$ 次；最坏时间复杂度 $= O (n)$
平均情况：假设新元素插入到任何一个位置的概率 $p_{i}$ 相同，即 $p_{i} = \frac{1}{n + 1}$
- 平均循环次数 $= n p + (n - 1) p + (n - 2) p + \dots + 1 \times p = \frac{n ( n + 1 )}{2} \times \frac{1}{n + 1} = \frac{n}{2}$
- 平均时间复杂度 $= O (n)$

插入到第 $i$ 个位置	循环次数
$1$	$n$
$2$	$n - 1$
$3$	$n - 2$
$\dots$	$\dots$
$n + 1$	$0$

删除操作

顺序表基本操作——删除

ListDelete(&L, i, e)：删除表 $L$ 中的第 $i$ 个位置的元素，并用 e 返回删除元素的值

基于静态分配的代码实现

//个人理解：删除位置之后的元素从前往后依次前移一位，填补删除元素后的位置空缺
 
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int Length;
}SqList;
 
bool LisDelete(SqList &L, int i, int &e){	// e用引用型参数
	if(i < 1 || i > L.length)	//判断i的范围是否有效
		return false;
 
	e = L.data[i - 1]			//将被删除的元素赋值给e
 
	for(int j = i; j < L.length; j--){	//将第i个后的元素前移
		L.data[j - 1] = L.data[j];
	}
	L.length--;	//长度减1
	return true;
}
 
int main(){
	SqList L;	//声明一个顺序表
	InitList(L);//初始化这个顺序表
	//...插入几个元素
	int e = -1;	//用变量e把删除的元素“带回来”
	if(LisDelete(L, 3, e))
		printf("已删除第三个元素，删除元素值=%d\n",e);
	else
		printf("位序i不合法，删除失败\n");
	return 0;
}

时间复杂度分析

关注最深层循环语句——L.data[j - 1] = L.data[j]的执行次数与问题规模 $n$ ——L.length的关系；
最好情况：删除表尾元素，不需要移动元素， $i = n$ ，循环 $0$ 次；最好时间复杂度 $= O (1)$ ；
最坏情况：删除表头元素，需要将后续的 $n - 1$ 个元素全都向前移动， $i = 1$ ，循环 $n - 1$ 次；最坏时间复杂度 = $O (n)$ ；
平均情况：假设删除任何一个元素的概率 $p_{i}$ 相同，即： $p_{i} = \frac{1}{n}$

删除第 $i$ 个元素	循环次数
$1$	$n - 1$
$2$	$n - 2$
$3$	$n - 3$
$\dots$	$\dots$
$n$	$0$

平均循环次数 $= (n - 1) p + (n - 2) p + \dots + 1 \times p = \frac{n ( n - 1 )}{2} \times \frac{1}{n} = \frac{n - 1}{2}$
平均时间复杂度 $= O (n)$

顺序表的查找.pdf

按位查找

顺序表基本操作——按位查找

GetElem(L, i) ：按位查找操作——获取表L中第i个位置元素的值

基于静态分配的代码实现

//个人理解：直接返回对应位置上的数据
 
#define MaxSize 10	//定义最大长度
typedef struct{
	ElemType data[MaxSize];
	int Length;
}SqList;
 
ElemType GetElem(SqList L, int i){
	// ...判断i的值是否合法
	return L.data[i - 1];	// 注意是i-1
}

基于动态分配的代码实现

//个人理解：直接返回对应位置上的数据
 
#define InitSize 10
 
typedef struct{
	ElemType *data;
	int MaxSize;
	int length;
}SeqList;
 
ElemType GetElem(SqList L, int i){
	// ...判断i的值是否合法
	return L.data[i - 1];	// 就算是指针也能用数组下标哦!
}

时间复杂度分析 $= O (1)$
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第 $i$ 个元素———“随机存取”特性；

按值查找

顺序表基本操作——按值查找

LocateElem(L, e)：按值查找操作，在表 $L$ 中查找具有给定关键字值的元素；

基于动态分配的代码实现

//个人理解：从前往后依次比较，找到第一个值等于e的元素，返回其位序
 
#define InitSize 10
typedef struct{
	ElemTyp *data;
	int MaxSize;
	int Length;
}SqList;
 
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, ElemType e){
	for(int i = 0; i < L.length; i++)
		if(L.data[i] == e)
			return i + 1;	//数组下标为i的元素值等于e，返回其位序i+1
	return 0;	//退出循环，说明查找失败
}

注意

Q: 如果顺序表里存放的是结构类型的数据元素，可不可以用 == 进行比较？

A: 不能！结构类型的比较，需要依次对比各个分量来判断两个结构体是否相等；

例：

 

//结构类型的数据需要自己定义相等

typedef struct{

int num;

int people;

}Customer;

void test(){

Customer a;

Customer b;

//…

if (a.num b.num && a.people b.people){

  printf("相等");

}else{

  printf("不相等");

}

时间复杂度分析

最深处循环语句: if(L.data[i] == e) 与问题规模 $n =$ L.length(表长)的关系；
最好情况：查找目标元素在表头，循环 $1$ 次，最好时间复杂度 $= O (1)$
最坏情况：查找目标元素在表尾，循环 $n$ 次，最好时间复杂度 $= O (n)$
平均情况：假设目标元素出现在任何一个位置的概率 $p_{i}$ 相同，即 $p_{i} = \frac{1}{n}$
- 平均循环次数 $= 1 \times \frac{1}{n} + 2 \times \frac{1}{n} + \dots + n \times \frac{1}{n} = \frac{n ( n + 1 )}{2} \times \frac{1}{n} = \frac{n + 1}{2}$
- 平均时间复杂度 $= O (n)$

目标元素所在位置 $i$	循环次数
$1$	$1$
$2$	$2$
$3$	$3$
$\dots$	$\dots$
$n$	$n$

2.2.4 本节习题精选

选择题：题目、解析

综合题：题目、解析

2.3 线性表的链式表示

顺序表可以随时存取表中的任意一个元素，但插入和删除需要移动大量元素。

链式存储线性表时，通过“链”建立起数据元素之间的逻辑关系，插入和删除只需要修改指针。

2.3.1 单链表的定义

LeetCode707. 设计链表

单链表的定义.pdf

什么是单链表？

链式存储
每个结点存储：数据元素自身信息 & 指向下一个结点(后继)的指针
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

代码定义单链表

struct LNode{	//定义单链表节点类型  LNode:结点
	ElemType data;		//每个结点存放一个数据元素 data:数据域
	struct LNode *next;	//指针指向下一个结点 next:指针域
};

增加一个新的结点：在内存中申请一个结点所需的空间，并用指针p指向这个结点

struct LNode* p = (struct LNode*) malloc(sizeof(struct LNode));

如果每次都要写struct很麻烦，所以可以利用typedef关键字——数据类型重命名：type <数据类型> <别名>，如：

typedef int zhengshu;			//int→zhengshu
typedef int *zhengshuzhizhen;	//int*→zhengshuzhizhen

上面操作可以化简为:

typedef struct LNode LNode;		//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;  // 声明一个指向单链表第一个结点的指针

LNode *强调这是结点
LinkList强调这是链表
合适的地方使用合适的名字，代码可读性更高

不带头结点的单链表

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){
	if (L == NULL)
		return true;
	else
		return false;
}

带头结点的单链表

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;
}

不带头结点 V.S. 带头结点

不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑；头指针指向的结点用于存放实际数据；
带头结点：头指针指向的头结点不存放实际数据，头结点指向的下一个结点才存放实际数据；

2.3.2 单链表上基本操作的实现

单链表的插入删除.pdf

单链表的插入

按位序插入(带头结点)

ListInsert(&L, i, e)：在表 $L$ 中的第 $i$ 个位置上插入指定元素 $e$ ，即：找到第 $i - 1$ 个结点（前驱结点），将新结点插入其后；其中头结点可以看作第 $0$ 个结点，故 $i = 1$ 时也适用。

代码实现

//个人理解：找到第i-1个结点（前驱结点），将新结点插入其后，其中头结点可以看作第0个结点
 
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
 
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i < 1)		//判断i的合法性, i是位序号(从1开始)
		return False;
 
	LNode *p;	//指针p指向当前扫描到的结点
	int j = 0;	//当前p指向的是第几个结点
	p = L;		//L指向头结点，头结点是第0个结点（不存数据）
 
	//找到第i-1个结点，若第i个结点已经超出了范围，则p为超出范围的第一个结点，即NULL
	while(p != NULL && j < i - 1){
		p = p->next;	//p指向下一个结点
		j++;
	}
 
	if (p == NULL)//i值不合法
		return false;
 
	//在第i-1个结点后插入新结点
	LNode *s = (LNode *)malloc(sizeof(LNode));	//申请一个结点的空间
	s->data = e;
	//后两步千万不能颠倒qwq
	s->next = p->next;
	p->next = s;	//将结点s连到p后
 
	return true;	//插入成功
}

时间复杂度分析

最好情况：插入第 $1$ 个位置 $O (1)$
最坏情况：插入表尾 $O (n)$
平均时间复杂度 $= O (n)$

按位序插入(不带头结点)

ListInsert(&L, i, e)：在表 $L$ 中的第 $i$ 个位置上插入指定元素 $e =$ 找到第 $i - 1$ 个结点（前驱结点），将新结点插入其后; 因为不带头结点，所以不存在第 $0$ 个结点，因此！ $i = 1$ 时，需要特殊处理——插入（删除）第1个元素时，需要更改头指针L；

代码实现

//个人理解：不带头结点时，需要单独处理插入到第一位的情况
 
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
 
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1)
		return false;
 
	//插入到第1个位置时的操作有所不同！
	if(i==1){
		LNode *s = (LNode *)malloc(size of(LNode));
		s->data =e;
		s->next =L;
		L=s;	//头指针指向新结点
		return true;
	}
 
	//i>1的情况与带头结点一样！唯一区别是j的初始值为1
	LNode *p;	//指针p指向当前扫描到的结点
	int j=1;	//当前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;
	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)

平均时间复杂度： $O (1)$

有了后插操作，那么在第 $i$ 个位置上插入指定元素 $e$ 的代码可以改成：

//个人理解：找到第i-1个结点（前驱结点），利用后插操作将新结点插入其后
 
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最后会等于NULL
		p = p->next;	//p指向下一个结点
		j++;
	}
 
	return InsertNextNode(p, e)
}

指定结点的前插操作

实现方法一：传入头指针L。InsertPriorNode(LinkList L, LNode *p, ElemType e)：从头结点开始，循环查找 p 的前驱 p ，再对 p 进行后插操作，时间复杂度为 $O (n)$ ；
实现方法二：套娃，该节点原有值放入该节点的下一节点，把新值放入该节点（类比：指定结点的删除)

//前插操作：在p结点之前插入元素e
//个人理解：在p结点后插入新结点，将p中元素赋给新结点，再将新元素e赋给p结点（无法在P之前插入，就在P之后插入，然后交换两个位置的元素）
 
 
bool InsertPriorNode(LNode *p, ElenType e){
	if(p==NULL)
		return false;
 
	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；
}	//时间复杂度为O(1)

王道书版本代码

bool InsertPriorNode(LNode *p, LNode *s){
	if(p==NULL || S==NULL)
		return false;
 
	s->next = p->next;
	p->next = s;				///s连接到p
	ELemType temp = p->data;	//交换数据域部分
	p->data = s->data;
	s->data = temp;
 
	return true;
}

单链表的删除

单链表按位序删除

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 (n)$
最好时间复杂度： $O (1)$
平均时间复杂度： $O (n)$

单链表指定结点的删除

LeetCode237. 删除链表中的节点

删除某个结点，需要修改其前驱结点的 next 指针

//个人理解：交换结点与其后继结点的值，然后删除后继结点
//注意先用中间变量指向要删除的结点，再断开连接
 
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* temp = node->next;
        node->val = temp->val;
        node->next = temp->next;
        delete temp;
    }
};

时间复杂度： $O (1)$
空间复杂度： $O (1)$

局限性：该过程实际上删除的是所给结点的后继结点，所以如果要删除链表中最后一个结点，就只能从表头开始依次寻找结点的前驱，时间复杂度为 $O (n)$ ；这就是单链表的局限性——无法逆向检索。

单链表的查找.pdf

单链表的查找

单链表按位查找

单链表不具备“随机访问”的特性，只能依次扫描
GetElem(L, i)：按位查找操作，获取表 $L$ 中第 $i$ 个位置的元素的值;

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指针指向的结点
}

平均时间复杂度 $= O (n)$

王道书版本代码

LNode * GetElem(LinkList L, int i){
	int j=1;	//从第一个结点开始
	LNode *p = L->next	//p先指向第一个结点
 
	if(i==0)
		return L;
	if(i<1)
		return NULL;
 
	while(p!=NULL && j<i){	//循环找到第i个结点
		p = p->next;
		j++;
	}
 
	return p;	//返回p指针指向的值
}

那么上一节的按位插入和按位删除就可以封装了！

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
 
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
	//判断i的合法性, i是位序号(从1开始)
	if(i<1)
		return False;
 
	LNode *p = GetElem(L,i-1);//找到第i-1个结点
/*
	LNode *p;	//指针p指向当前扫描到的结点
	int j=0;	//当前p指向的是第几个结点
	p = L;	//L指向头结点，头结点是第0个结点（不存数据）
 
	//循环找到第i-1个结点，若第i个结点已经超出了范围，则p为超出范围的第一个结点
	while(p!=NULL && j<i-1){	//如果i>lengh, p最后会等于NULL
		p = p->next;	//p指向下一个结点
		j++;
	}
*/
 
	return InsertNextNode(p,e);	//后插操作
/*
	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;
}

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个结点（不存数据）
 
	LNode *p = GetElem(L,i-1);//找到第i-1个结点	封装的应用
/*
	//循环找到第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;
}

单链表按值查找

LocateElem(L, e)：按值查找操作，在表 $L$ 中查找具有给定关键字值的元素；

//个人理解：重头到尾，依次遍历并与关键字比较
 
LNode * LocateElem(LinkList L, ElemType e){
	LNode *P = L->next;	//p指向第一个结点
	//从第一个结点开始查找数据域为e的结点
	while(p!=NULL && p->data != e){
	//如果ElemType是更复杂的结构类型，则不能直接使用!=来判断
		p = p->next;
	}
	return p;	//找到后返回该结点指针，否则返回NULL
}

注意当ElemType是结构体时的操作

求单链表的长度

Length(LinkList L)

//个人理解：重头到尾，依次遍历各个结点并令表长+1
 
 
int Length(LinkList L){
	int len=0;	//统计表长
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len++;
	}
	return len;
}

平均时间复杂度 $= O (n)$

单链表的建立

单链表的建立.pdf

思路：初始化一个单链表 -> 每取一个数据元素，插入到表尾/表头
核心：初始化操作 and 指定结点的后插操作

尾插法建立单链表

//初始化一个单链表(带头结点)
//...
 
设置变量length记录链表当前的长度
 
while(){
	每次取一个数据元素e;
	ListInsert(L, length+1, e);//插入到尾部
	length++;
}

但是，因为每次都要从头开始遍历，总的时间复杂度为 $O (n^{2})$

while(p!=NULL && j<i-1){
	p = p->next;
	j++;
}

解决方法：设置一个表尾指针 r ，对 r 这个结点进行后插操作InsertNextNode()

最终代码实现

//个人理解：设置表尾指针指向链表最后一个元素，对最后一个元素不断进行后插操作
 
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)$

头插法建立单链表

对头结点进行后插操作 InsertNextNode()

//初始化单链表(带头结点)
 
while(){
	每次取一个数据元素e;
	InsertNextNode(L, e);
}

最终代码实现

//个人理解：对头结点不断进行后插操作
 
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;
 
}

注：建议只要是初始化单链表，都先将头指针指向NULL — L->next = NULL

头插法重要应用：链表的逆置

LeetCode206. 反转链表

CSDN:单链表逆置—头插法图解算法题

//个人理解：迭代时间，利用头插法把原链表中的各个元素从前往后依次插入到一个空链表的表头，使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空，即得逆置链表
class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode* prev = nullptr;	//记录链表逆置后的头结点
		ListNode* curr = head; 		//记录当前处理的结点
		while (curr) {
			ListNode* next = curr->next;//从原链表拆出一个结点
			curr->next = prev;			//拆出的结点加入到链表头
			prev = curr;				//更新链表头
			curr = next;				//更新待处理结点
		}
		return prev;	//返回新链表
	}
};

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。需要遍历链表一次。
空间复杂度： $O (1)$ 。

//个人理解：递归实现，递归函数将以当前结点为头结点的链表逆置，每层递归将当前结点放到链表末尾
//head->next原本指向head的下一个结点，调用递归函数后，head对应的链表逆置，head->next所指结点成为链表最后一个结点
class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (!head || !head->next)	return head;
 
		ListNode* newHead = reverseList(head->next);//反转除头结点外的其余部分
		head->next->next = head;					//将头结点放置到末尾
		head->next = nullptr;
		return newHead;
	}
};

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。需要对链表的每个节点进行反转操作。
空间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 $n$ 层。

2.3.3 双链表

LeetCode707. 设计链表

双链表.pdf

双链表的定义

struct DLinkListNode {
	int val;					//数据
	DLinkListNode *prev, *next;	//前驱指针，后继指针
	DLinkListNode(int _val) : val(_val), prev(nullptr), next(nullptr) {}
};

typedef struct DNode{	//定义双链表结点类型
	ElemType data;				//数据域
	struct DNode *prior, *next;	//前驱和后继指针
}DNode, *DLinklist;		//DLinklist与Dnode*等价，详见单链表的定义

与单链表中一样，DLinklist 强调链表， DNode * 强调结点，二者本质上等价；

双链表的初始化

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;
}

双链表的插入操作

后插操作：InsertNextDNode(p, s)：在 p 结点后插入 s 结点

//个人理解：先建立结点p的原后继结点与新结点的链接，再建立p结点和新结点的链接（注意顺序）
 
bool InsertNextDNode(DNode *p, DNode *s){	//将结点 *s 插入到结点 *p之后
	if(p==NULL || s==NULL)	//非法参数
		return false;
 
	s->next = p->next;	//s结点的后向指针指向p的后继结点
	if (p->next != NULL)	//p不是最后一个结点->p有后继结点
		//如果p是最后一个结点，就不必执行下面的操作
		p->next->prior = s;	//p结点的后继结点的前向指针指向s结点
	s->prior = p;	//s结点的前向指针指向p结点
	p->next = s;	//p结点的后向指针指向s结点
 
	return true;
}

按位序插入操作

思路：从头结点开始，找到某个位序的前驱结点，对该前驱结点执行后插操作；

前插操作

思路：找到给定结点的前驱结点，再对该前驱结点执行后插操作；

//自己写的，还没有验证
//个人理解：先建立结点p的原前驱结点与新结点的链接，再建立p结点和新结点的链接（注意顺序）
 
bool InsertPriorDNode(DNode *p, DNode *s){	//将结点 *s 插入到结点 *p之前
	if(p==NULL || s==NULL)	//非法参数
		return false;
 
	s->prior = p->prior;	//s结点的前向指针指向p的前驱结点
	p->prior->next = s;		//p结点的前驱结点的后向指针指向s结点
	s->next = p;	//s结点的后向指针指向p结点
	p->prior = s;	//p结点的前向指针指向s结点
 
	return true;
}

双链表的删除操作

删除 p 的后继结点 q

//个人理解：依次解除结点的前向指针和后向指针（注意检查结点是否有后向指针）
 
bool DeletNextDNode(DNode *p){//删除p结点的后继结点
	if(p==NULL)
		return false;
 
	DNode *q = p->next;
	if(q==NULL)	//p没有后继结点
		return false;
 
	p->next = q->next;
	if(q->next != NULL)	//q结点不是最后一个结点
		q->next->prior=p;
	free(q);
 
	return true;
}

销毁一个双链表

bool DestoryList(DLinklist &L){
	//循环释放各个数据结点
	while(L->next != NULL){
		DeletNextDNode(L);	//依次删除头结点的后继结点
	}
	free(L);	//释放头结点
	L = NULL;	//头指针指向NULL
}

双链表的遍历操作

后向遍历

while(p!=NULL){
	//对结点p做相应处理，eg:打印
	p = p->next;
}

前向遍历

while(p!=NULL){
	//对结点p做相应处理，eg:打印
	p = p->prior;
}

如果我们不想处理头结点，那就跳过头结点！

while(p->prior!=NULL){
	//对结点p做相应处理
	p = p->prior;
}

注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为 $O (n)$

2.3.4 循环链表

循环链表.pdf

循环单链表

循环单链表中最后一个结点的指针不是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;
}
 
//判断循环单链表是否为空
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;
}

单链表 vs 循环单链表

单链表：从一个结点出发只能找到该结点后续的各个结点；对链表的操作大多都在头部或者尾部；设立头指针，从头结点找到尾部的时间复杂度 $= 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;
}

双链表 vs 循环双链表

插入操作

对于循环双链表，操作 p->next->prior = s 不会出问题辣！因为就算 p 是最后一个结点，也不会出现空指针现象了

//个人理解：①连接新结点与后继结点，②连接新结点与前驱结点
bool InsertNextDNode(DNode *p, DNode *s){
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;

删除操作

和插入操作一样！q->next->prior 对于循环双链表不会出错了

//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);

2.3.5 静态链表

静态链表.pdf

静态链表的含义

单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针（下一个结点在内存中的地址）
静态链表——用数组的方式实现的链表：分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标（游标）
- 其中数组下标为0的结点充当”头结点”
- 游标为 $- 1$ 表示已经到达表尾
- 若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr $+ 8 \times 2$
- 注意：数组下标——物理顺序，位序——逻辑顺序；
- 优点：增、删操作不需要大量移动元素；
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

代码定义一个静态链表

#define MaxSize 10	//静态链表的最大长度
 
struct Node{		//静态链表结构类型的定义
	ElemType data;	//存储数据元素
	int next;		//下一个元素的数组下标(游标)
};
 
//用数组定义多个连续存放的结点
void testSLinkList(){
	struct Node a[MaxSize];	//数组a作为静态链表, 每一个数组元素的类型都是struct Node
	//...
}

也可以这样：

#define MaxSize 10	//静态链表的最大长度
 
typedef struct{		//静态链表结构类型的定义
	ELemType data;	//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];
 
void testSLinkList(){
	SLinkList a;
}

上面这个代码等同于

#define MaxSize 10	//静态链表的最大长度
 
struct Node{	//静态链表结构类型的定义
	ElemType data;	//存储数据元素
	int next;	//下一个元素的数组下标(游标)
};
 
typedef struct Node SLinkList[MaxSize];	//重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组;

PS: SLinkList a 强调 a 是静态链表；struct Node a 强调 a 是一个Node型数组；

静态链表基本操作的实现

初始化静态链表：把 a[0] 的 next 设为 $- 1$
查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序，数组下标是结点的物理上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度 $O = (n)$
在位序为 $i$ 上插入结点：
1. 找到一个空的结点，存入数据元素；
2. 从头结点出发找到位序为 $i - 1$ 的结点；
3. 修改新结点的 next；
4. 修改 $i - 1$ 号结点的next；

Q：如何判断结点为空？（避免脏数据）

A：在初始化时，将空闲结点的next设置为某个特殊值，eg：-2；

删除某个结点：
1. 从头结点出发找到前驱结点；
2. 修改前驱节点的游标；
3. 被删除节点 next 设为 $- 2$ ；

#define MaxSize 10	//静态链表的最大长度
 
typedef struct{		//静态链表结构类型的定义
	ELemType data;	//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];

2.3.6 顺序表和链表的比较

顺序表和链表的比较.pdf

1. 逻辑结构

顺序表和链表都属于线性表，都是线性结构

2. 存储结构

顺序表：顺序存储
- 优点：支持随机存取，存储密度高
- 缺点：大片连续空间分配不方便，改变容量不方便
链表：链式存储
- 优点：离散的小空间分配方便，改变容量方便
- 缺点：不可随机存取，存储密度低

3. 基本操作 - 创建

顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源
- 静态分配：静态数组，容量不可改变
- 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高(malloc(),free())
链表：只需要分配一个头结点或者只声明一个头指针

4. 基本操作 - 销毁

顺序表：修改 Length = 0
- 静态分配：静态数组——系统自动回收空间
- 动态分配：动态数组——需要手动 free

	//创
	L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
	//销
	free(L.data);
	//！malloc() 和 free() 必须成对出现

链表：依次删除各个结点 free()

5. 基本操作 - 增/删

顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度 $= O (n)$ ，时间开销主要来自于移动元素；
链表：插入/删除元素只需要修改指针；时间复杂度 $= O (n)$ ，时间开销主要来自查找目标元素
链表的效率更高

6. 基本操作 - 查

顺序表
- 按位查找： $O (1)$
- 按值查找： $O (n)$ ，若表内元素有序，可在 $O (lo g_{2} n)$ 时间内找到(如折半查找)
链表：
- 按位查找： $O (n)$
- 按值查找： $O (n)$

7. 开放式问题答题思路

Q: 请描述顺序表和链表的balabalabala…实现线性表时，用顺序表还是链表好？

A: 顺序表和链表的存储结构都是线性结构，都属于线性表；

但是二者的存储结构不同，顺序表采用顺序存储…(特点，优缺点)；链表采用链式存储…(特点，优缺点)；

由于采用不同的存储方式实现，因此基本操作的实现效率也不同；当初始化时…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个数据元素时…；

2.3.7 本节习题精选

选择题：题目、解析

综合题：题目、解析

我的 Obsidian 知识库

探索

第2章 线性表

2.1 线性表的定义和基本操作

线性表的基本操作

物理结构

2.1.3 本节习题精选

2.2 线性表的顺序表示

2.2.1 顺序表的定义

静态分配

动态分配

2.2.2 顺序表上基本操作的实现

插入操作

删除操作

按位查找

按值查找

2.2.4 本节习题精选

2.3 线性表的链式表示

2.3.1 单链表的定义

不带头结点的单链表

带头结点的单链表

不带头结点 V.S. 带头结点

2.3.2 单链表上基本操作的实现

单链表的插入

按位序插入(带头结点)

按位序插入(不带头结点)

指定结点的后插操作

指定结点的前插操作

单链表的删除

单链表按位序删除

单链表指定结点的删除

单链表的查找

单链表按位查找

单链表按值查找

求单链表的长度

单链表的建立

尾插法建立单链表

头插法建立单链表

头插法重要应用：链表的逆置

2.3.3 双链表

双链表的定义

双链表的初始化

双链表的插入操作

双链表的删除操作

双链表的遍历操作

2.3.4 循环链表

循环单链表

单链表 vs 循环单链表

循环双链表

双链表 vs 循环双链表

2.3.5 静态链表

静态链表的含义

代码定义一个静态链表

静态链表基本操作的实现

2.3.6 顺序表和链表的比较

1. 逻辑结构

2. 存储结构

3. 基本操作 - 创建

4. 基本操作 - 销毁

5. 基本操作 - 增/删

6. 基本操作 - 查

7. 开放式问题答题思路

2.3.7 本节习题精选

关系图谱

目录

反向链接

第2章线性表