夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 208 页PDF · 2.9MB
下载

文档在线预览

公开展示前 10 页
100%
1
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《002-第二讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 208 页 剩余 198 页未展示,请下载后查阅

下载

文档文本内容

第二讲:线性表
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考纲框架
定义 n个数据元素的有限且有序序列
数组实现
顺序结构 特点:空间连续;查找容易;增删难
线性表
操作:插入,删除,查找,遍历
单链表
操作:插入,删除,
查找,遍历
单循环链表
不要断链
双链表
链式结构
特点:空间按需;查找难;
双循环链表
增删容易
静态链表CON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考点一:基本定义和逻辑结构
线性表(表):n(n≥0)个具有相同类型的数据元素的有限序列
a (1≤i≤n)称为数据元素
i
(a , a , … , a , … , a )
1 2 i n
下角标 i 表示该元素在线性表中的位置或序号
线性表的长度:线性表中数据元素的个数
空表:长度等于零的线性表考点一:基本定义和逻辑结构
线性表的逻辑表示为:
( a a …,a a …,a )
1, 2, i, i+1, n
a(1≤i≤n)表示第i(i表示逻辑位序)个元素。
i
表头元素 表尾元素
( a a …,a a …,a )
1, 2, i, i+1, n考点一:基本定义和逻辑结构
线性表是一个具有相同特性的数据元素的有限序列。
⚫ 相同特性:所有元素属于同一数据类型。
⚫ 有限:数据元素个数是有限的。
⚫ 序列:数据元素由逻辑序号唯一确定。一个线性表中可以有相同
值的元素。考点一:基本定义和逻辑结构
线性表是客观事物的抽象
 一个汽车线性表
 一个星座线性表考点一:基本定义和逻辑结构
a a a a a
1 2 i-1 i n
L = (1, 3, 5, 7, 9)
1. 数据元素个数的有限性
1
2. 数据元素类型的相同性 L = ((Li, 8, 3), (Wang, 7, 4), (Zhang, 5, 5))
3
3. 数据元素类型的抽象性 不确定、任意
4. 相邻数据元素的序偶关系,且 a 无前驱,a 无后继
1 n考点一:基本定义和逻辑结构
ADT List
DataModel
线性表中的数据元素具有相同类型,相邻元素具有前驱和后继关系
Operation
InitList:表的初始化,建一个空表
DestroyList:销毁表,释放表所占用的存储空间
Length:求表的长度
Get:在表中取序号为 i的数据元素
Locate:在线性表中查找值等于 x的元素
Insert:在表的第 i个位置处插入一个新元素 x
Delete:删除表中的第 i个元素
Empty:判断表是否为空
(1)线性表的基本操作根据实际应用而定
endADT (2)复杂的操作可以通过基本操作的组合来实现
(3)对不同的应用,操作的接口可能不同考点一:基本定义和逻辑结构
逻辑特性
线性表的概念
线性表ADT=逻辑结构+基本运算(运算描述)
线性表的存储结构
顺序存储结构 链式存储结构
单链表 双链表 循环链表
顺序表中基本运算
的实现
循环链表中基本运算
单链表中基本运算 双链表中基本运算
的实现
的实现 的实现
线性表的应用THANKSCON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考纲框架考点二:线性表的顺序结构
顺序表的存储结构定义
顺序表的实现——初始化、求长度、判空
顺序表的实现——按位查找和按值查找
顺序表的实现——插入和删除
顺序表的应用——合并和逆置等考点二:线性表的顺序结构
顺序表(向量):线性表的顺序存储结构
用一段地址连续的存储单元
存储要点
依次存储线性表中的数据元素【顺序表的存储结构定义】考点二:线性表的顺序结构
线性表
逻辑结构 (a,a,…,a,…,a)
1 2 i n
直接映射
0 1 n-1 MaxSize-1
i-1
存储结构 a a a a n
… … …
1 2 i n
data length
顺序表考点二:线性表的顺序结构
顺序表(向量):线性表的顺序存储结构
存储空间的起始位置
用什么属性来描述顺序表?
顺序表的容量(最大长度)
顺序表的当前长度考点二:线性表的顺序结构
顺序表:线性表的顺序存储结构
(a , … , a , a, … , a )
1 i-1 i n
0 … i-2 i-1 … n-1 MAXSIZE-1
… …
a a a a 长度
1 i-1 i n
线性表的长度length
数组的长度MAXSIZE
MAXSIZE ≥ length考点二:线性表的顺序结构
0 … i-2 i-1 … n-1 MAXSIZE-1
… …
a a a a 长度
1 i-1 i n
#define MAXSIZE 100 /*假定顺序表最多100个元素*/
typedef int ElemType; /*定义线性表的数据类型,假设为int型*/
typedef struct
{
ElemType data[ M A X S I Z E ]; /*存放数据元素的数组*/
int length; /*线性表的长度*/
} SeqList;考点二:线性表的顺序结构
0 … i-2 i-1 … n-1 MAXSIZE-1
… …
a a a a 长度
1 i-1 i n
L
Loc(a ) Loc(a)
i-1 i
如何求得任意元素的存储地址?
Loc(a) = Loc(a ) + L
i i-1考点二:线性表的顺序结构
0 … i-2 i-1 … n-1 MAXSIZE-1
… …
a a a a 长度
1 i-1 i n
L
Loc(a ) Loc(a)
1 i
如何求得任意元素的存储地址?
Loc(a) = Loc(a ) + (i-1)×L
i 1
随机存取:在O(1)时间内存取数据元素考点二:线性表的顺序结构
0 … i-2 i-1 … n-1 MAXSIZE-1
… …
a a a a 长度
1 i-1 i n
L
Loc(a ) Loc(a)
1 i
如何求得任意元素的存储地址?
Loc(a) = Loc(a ) + (i-1)×L
i 1
不管数据元素在哪个位置,只要给出下标i,都可以O(1)读取或者更
新该元素的值。这个特点就是随机访问,记住一点:只要是顺序结构,
都具备这个特点。【顺序表的初始化】考点二:线性表的顺序结构
建立顺序表
a[0..n-1]  顺序表L ─ 整体创建顺序表。
void CreateList(SeqList &L,ElemType a[],int n) {
L.length = 0;
for(int i = 0; i < n; i++){
传递顺序表
L.data[L.length++] = a[i];
指针
}
}【顺序表的操作】 -按位查找和按值查找考点二:线性表的顺序结构
求某个数据元素值GetElem(& L,i, & e)
返回L中第 i(1≤i≤ListLength(L))个元素的值,存放在e中。
本算法的时间复杂度为O(1)
体现顺序表的随机存取特性考点二:线性表的顺序结构
按元素值查找FindByValue(&L,e)
顺序查找第一个值域与e相等的元素的逻辑位序。若这样的元素不
存在,则返回值为0。
0 … i … n-1 MAXSIZE-1
… …
a e a
1 n
元素的序号
操作接口: int FindByValue(SeqList &L, ElemType e)考点二:线性表的顺序结构
按元素值查找FindByValue(&L,e)
顺序查找第一个值域与e相等的元素的逻辑位序。若这样的元素不
存在,则返回值为0。
int FindByValue(SeqList &L,ElemType e)
{
int i;
for (i = 0; i < L.length; i ++ )
if (L.data[i] == e)
return i + 1;
return 0;
}
按值查找的时间复杂度? O(n)考点二:线性表的顺序结构
按元素值查找FindByValue(&L,e)
性能分析:本算法中的基本操作为for循环中的i++语句。
(1)最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为0(1)。
(2)最坏情况:在表头插入(即i=1),元素后移语句将执行n次,时间复杂度为0(n)。
(3)平均情况:假设p (p=1/n,等概率情况下)是在第i个位置上插入一个结点的概率,则
i i
在长度为n的线性表中插入一个结点时,所需移动结点的平均次数为:
𝑛 𝑛
1 1 𝑛 𝑛 + 1 𝑛 + 1
෍𝑝 𝑖 = ෍ 𝑖 = ∗ =
𝑖
𝑛 𝑛 2 2
𝑖=1 𝑖=1
综上所述,顺序表查找算法的平均时间复杂度为O(n),其中n为顺序表中元素的个数。【顺序表的插入】考点二:线性表的顺序结构
顺序表插入
ListInsert
输入:插入位置 i,待插 e
功能:在表的第 i个位置处插入一个新元素 e
输出:若插入成功,表中增加一个新元素;否则给出失败信息
插入操作是否成功
操作接口:bool ListInsert (SeqList &L, int i, ElemType e)考点二:线性表的顺序结构
对于线性表(35,12,24,42),在 i= 2的位置上插入元素33
0 1 2 3 4
a a a a
1 2 3 4 4
35 12 24 42 5
注意边界条件
33 什么情况下插入无法进行?
表满:length >= MAXSIZE
合理的插入位置:1 ≤ i≤ length + 1(注意:i 指的是元素的序号)考点二:线性表的顺序结构
bool Insert(SeqList &L, int i, ElemType e)
{
if (L.length >= MAXSIZE) {
printf("上溢错误,插入失败\n"); return false;
}
if (i < 1 || i > L.length + 1) {
printf("位置错误,插入失败\n"); return false;
}
for (int j = L.length; j >= i; j--) /* j 表示元素序号*/
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length++;
return true;
}
基本语句?执行多少次?考点二:线性表的顺序结构
最好情况( i= n+1):执行0次,时间复杂度为O(1)
最坏情况( i= 1):执行n次,时间复杂度为O(n)
平均情况(1 ≤ i≤ n+1):时间复杂度为O(n)
for (int j = L.length; j >= i; j--)
L.data[j] = L.data[j - 1];
n
i
+
=
1
1
p
i
( n − i + 1 ) =
n
1
+ 1
n
i
+
=
1
1
( n − i + 1 ) =
n
2
= O ( n )【顺序表的删除】考点二:线性表的顺序结构
顺序表删除(按位置)
ListDelete
输入:删除位置 i
功能:删除表中的第 i个元素
输出:若删除成功,表中减少一个元素;否则给出失败信息
删除操作是否成功
操作接口:bool ListDelete (SeqList &L, int i, ElemType &e)考点二:线性表的顺序结构
对于线性表(35, 33, 12, 24, 42),删除位置 i= 2的数据元素
0 1 2 3 4
a a a a a
1 2 3 4 5 5
35 33 12 24 42 4
请仿照顺序表的插入算法,完成删除算法:
e
1. 分析边界条件
2. 分别给出伪代码和C语言实现
3. 分析时间复杂度
操作接口:bool ListDelete(SeqList &L, int i, ElemType &e)考点二:线性表的顺序结构
bool ListDelete(SeqList &L,int i,ElemType &e)
{
int j;
//参数错误时返回false
if (L.length == 0) return false;
if (i < 1 || i > L.length) return false;
i--; //将顺序表逻辑序号转化为物理序号
e=L->data[i];
for (j=i;j<L.length-1;j++) //将data[i..n-1]元素前移
L.data[j]=L.data[j+1];
L.length--; //顺序表长度减1
return true; //成功删除返回true
}考点二:线性表的顺序结构
最好情况( i= n):执行0次,时间复杂度为O(1)
最坏情况( i= 1):执行n-1次,时间复杂度为O(n)
平均情况(1 ≤ i≤ n):时间复杂度为O(n)
𝑛 𝑛
1 𝑛 − 1
෍𝑝 (𝑛 − 𝑖) = ෍(𝑛 − 𝑖) = = 𝑂(𝑛)
𝑖
𝑛 2
𝑖=1 𝑖=1
for (j=i;j<L.length-1;j++) //将data[i..n-1]元素前移
L.data[j]=L.data[j+1];考点二:线性表的顺序结构
顺序表删除(按值)
ListLocateDelete
输入:删除值为 x
功能:删除表中第一个值为 x的元素
输出:若删除成功,表中减少一个元素;否则给出失败信息
删除操作是否成功
操作接口:bool ListLocateDelete(Seqlist &L, ElemType &e)考点二:线性表的顺序结构
对于线性表(35, 33, 12, 24, 42),删除位置 x= 33的数据元素
0 1 2 3 4
a a a a a
1 2 3 4 5 5
35 33 12 24 42
33
操作接口:bool ListLocateDelete(SeqList &L, ElemType &e)考点二:线性表的顺序结构
对于线性表(35, 33, 12, 24, 42),删除位置 x= 33的数据元素
0 1 2 3 4
a a a a a
1 2 3 4 5 5
35 33 12 24 42
33 33
不等 相等
操作接口:bool ListLocateDelete(SeqList &L, ElemType &e)考点二:线性表的顺序结构
bool ListLocateDelete(Seqlist &L, ElemType &e)
{ // 删除线性表L中值为x的第一个结点
int i = 0;
for(i = 0; i < L.length && L.data[i] != e;i++); //查找元素e的位置
if(i > L.length) return false; //元素不存在
for (int j = i; j < L.length; j ++ )
L.data[j - 1] = L.data[j];
L->length -- ;
return true;
}
基本语句?执行多少次?考点二:线性表的顺序结构
查找时间 平均情况(1 ≤ i≤ n):
𝑛 𝑛
1 𝑛 + 1
෍ 𝑝 (𝑖) = ෍(𝑖) =
𝑖
𝑛 2
𝑖=1 𝑖=1
删除时间,平均情况(1 ≤ i≤ n):
𝑛 𝑛
1 𝑛 − 1
෍ 𝑝 (𝑛 − 𝑖) = ෍(𝑛 − 𝑖) =
𝑖
𝑛 2
𝑖=1 𝑖=1
平均情况(1 ≤ i≤ n):时间复杂度为O(n)
𝑛 + 1 𝑛 − 1
+ = 𝑛 = O(n)
2 2考点二:线性表的顺序结构
顺序表删除(按值)
Locate_Delete_SqListALL
输入:删除值为 x
功能:删除表中所有值为 x的元素
输出:若删除成功,表中减少若干个个元素;否则给出失败信息
删除操作是否成功
操作接口:void Locate_Delete_SqListALL(Seqlist &L, ElemType &e)考点二:线性表的顺序结构
删除顺序表中所有值为x的元素
删除所有x=2的元素(k记录删除的元素个数,初值=0)
0 1 2 3 4 5
length
1 2 1 2 3 2 36
kkkkkk======011223,,,前前前移移移012个个个位位位置置置 顺序表长度=6-k=3考点二:线性表的顺序结构
对应的算法如下:
void Locate_Delete_SqListALL(SqList &L,ElemType x)
{ int k=0, i=0; //k记录值等于x的元素个数
while (i<L.length)
{ if (L.data[i]==x) //当前元素值为x时k增1
k++;
else //当前元素不为x时将其前移k个位置
L.data[i-k] = L.data[i];
i++;
}
L.length-=k; //顺序表L的长度递减k
}【政哥题型总结】考点二:线性表的顺序结构
1、编写算法,将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序
表c, 已知顺序表A 和B 的元素个数分别为m 和n 。其中顺序表采用动态分配空
间,定义如下:
Typedef struct{
ElemType * elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量
}SqList;考点二:线性表的顺序结构
方法一:回溯法
20 25 40 50
15 21 30考点二:线性表的顺序结构
方法一:回溯法
20 25 40 50
15 21 30考点二:线性表的顺序结构
方法一:回溯法
20 25 40 50
时间复杂度是O(m*n)
未充分利用有序的信息
15 21 30考点二:线性表的顺序结构
方法二:归并法
有序合并:合并两个相邻的有序子序列的过程。
s m m+1 t
r[ ]
20 25 40 50 15 21 30
i j
r1[ ] 15
k考点二:线性表的顺序结构
void MergeList(SqList& A, SqList& B, SqList& C) {
C.elem = new ElemType[A.length + B.length];
C.length = 0; // 初始化空表C
C.listsize = A.length + B.length;
int i = 0, j = 0;
// 将A和B中的元素按从小到大的顺序合并到C中
while (i < A.length && j < B.length) {
C.elem[C.length++] = A.elem[i] <= B.elem[j] ? A.elem[i++] : B.elem[j++];
}
while (i < A.length) { // 处理A中剩余的元素
C.elem[C.length++] = A.elem[i++];
}
while (j < B.length) { // 处理B中剩余的元素
C.elem[C.length++] = B.elem[j++];
}
}考点二:线性表的顺序结构
2、试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表
(a ,a ,a ,…,a )逆置为(a ,a ,…a ,a )。
1 2 3 n n n-1 2 1考点二:线性表的顺序结构
方法一:开辟数组法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
时间复杂度是O(n)
空间复杂度是O(n)
0 6 4 3 5 1 7 2 8 3
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是0和9
0 3
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是1和8
8
6
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是2和7
4
2
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是3和6
3 7
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是4和5
5 1
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
下标是0和9
下标是1和8
下标是2和7
下标是3和6
下标是4和5
下标和是9(length-1)
0 6 4 3 5 1 7 2 8 3
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
方法二:对位交换法
0 1 2 3 4 5 6 7 8 9
对位交换:
3 8 2 7 1 5 3 4 6 0
下标是0和9
下标是1和8
下标是2和7
下标是3和6
下标是4和5
时间复杂度是O(n)
0 6 4 3 5 1 7 2 8 3
空间复杂度是O(1)
0 1 2 3 4 5 6 7 8 9考点二:线性表的顺序结构
void ListOppose(SqList &L){
int i;
ElemType x;
// 只需要遍历原表的一半就可以实现数据元素位置的交换
for(i=0; i< L.length/2; i++){
x = L-> data[i];
L->data [i] = L->data[L.length-i-1]; // 数据元素交换->逆置
L.data[L->length-i-1] = x;
}
}考点二:线性表的顺序结构
【改进,部分逆置】试写一算法,实现顺序表的就地逆置,但是要逆置
这个数组那一段的开始下标from,要逆置那一段的结束下标to 。
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
from To考点二:线性表的顺序结构
0 1 2 3 4 5 6 7 8 9
3 8 2 7 1 5 3 4 6 0
from To
需要交换值的元素下表是:
from + i VS to – i
i = (to – from + 1)/2考点二:线性表的顺序结构
/* 这个函数传入的参数为要逆置的数组 要逆置这个数组那一段的
开始下标from 要逆置那一段的结束下标to */
void Reverse(int R[], int from, int to){
int i, temp;//temp为临时变量
for(i=0; i < (to - from + 1)/2; i++){
temp = R[from + i];
R[from + i] = R[to - i];
R[to - i] = temp;
}
}考点二:线性表的顺序结构
3、一个线性表中的元素为全部为正或者负整数,试设计一算法,在尽可能少
的时间内重排该表,将正、负整数分开,使线性表中所有负整数在正整数前面。
x 无序整数序列
负数 x 整数考点二:线性表的顺序结构
◼ base=正负(基准)
◼ j从后向前找偶数元素:前移
◼ i从前向后找奇数元素:后移
base(基准)
0 1 2 3 4 5 6 7 8 9
3 -8 2 7 -1 5 3 4 -6 -1
i j考点二:线性表的顺序结构
void Rearrange(int a[], int n) {
int low = 0, high = n - 1;
int t = a[low]; // 暂存第一个元素,因为后面会被覆盖,不作为比较对象
while (low < high) {
while (low < high && a[high] >= 0) { // 从后向前找第一个负数
--high;
}
a[low] = a[high]; // 负数放到前面
while (low < high && a[low] < 0) { // 从前向后找第一个非负数
++low;
}
a[high] = a[low]; // 非负数放到后面
}
a[low] = t; // 最后将t放到最终位置
}THANKSCON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考纲框架考点三: 线性表的链式结构
单链表的存储结构定义
单链表的实现——基本操作
单链表的实现——建立(头插法和尾插法)
单链表的实现——遍历、求长度、查找
单链表的实现——插入和删除
单链表的应用——去重和逆置【单链表的存储结构定义】考点三: 线性表的链式结构
顺序表 静态存储分配 事先确定容量
单链表 动态存储分配 运行时分配空间
单链表:线性表的链接存储结构
存储思想:用一组任意的存储单元存放线性表
连续
不连续
零散分布考点三: 线性表的链式结构
线性表中每个结点有唯一的前驱结点和后继结点。
设计链式存储结构时,每个逻辑结点存储单独存储,为了表示逻辑关系,
增加指针域。
⚫ 每个物理结点增加一个指向后继结点的指针域  单链表。
⚫ 每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针
域 双链表。考点三: 线性表的链式结构
线性表
(a,a,…,a,…,a )
逻辑结构
1 2 i n
映射
L
存储结构 a a … a ∧
1 2 n
带头结点单链表示意图考点三: 线性表的链式结构 …
0200 a
2
存储特点: 325
0208 a
1
1. 逻辑次序和物理次序不一定相同
0200
2. 元素之间的逻辑关系用指针表示 …
0300 a
例:(a, a, a, a)的存储示意图 4
1 2 3 4
∧
单链表:线性表的链接存储结构 …
存储思想:用一组任意的存储单元存放线性表 0325 a
3
0300
连续
…
不连续
零散分布考点三: 线性表的链式结构 …
0200 a
2
观察1:单链表由若干结点构成 325
0208 a
1
0200
观察2:单链表的结点只有一个指针域
…
0300 a
data:存储数据元素 4
∧
next:存储指向后继结点的地址
…
结点 0325 a 数据域
3
0300
… 指针域
数据域 指针域
单链表的结点结构 data next考点三: 线性表的链式结构
typedef int ElemType; /*定义线性表的数据类型,假设为int型*/
typedef struct LNode
{
ElemType data;
struct LNode *next;
} Lnode,*LinkList;
LNode *head;
head
a a a
1 2 n ∧考点三: 线性表的链式结构
typedef int ElemType; /*定义线性表的数据类型,假设为int型*/
typedef struct LNode {
ElemType data; /*数据域,保存结点的值 */
struct LNode *next; /*指针域*/
} LNode, *LinkList; /*结点的类型 */
data next
typedef struct LNode LNode
typedef struct LNode *LinkList考点三: 线性表的链式结构
存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储
量之比,即:
8个字节 4个字节
例
如
a
1
结点数据本身占用的空间
存储密度 =
结点占用的空间总量 存储密度=8/12=67%
一般地,存储密度越大,存储空间的利用率就越高。显然,顺序表的
存储密度为1(100%),而链表的存储密度小于1。考点三: 线性表的链式结构
单链表的特点
当访问过一个结点后,只能接着访问它的后继结点,而无法访问它
的前驱结点。
p
… a b …考点三: 线性表的链式结构
头指针:指向第一个结点的存储地址
尾标志:终端结点的指针域为空
头结点:在第一个元素结点之前附设一个类型相同的结点
头结点简化了对边界的处理——插入、删除、构造等
空表 Head->next = NULL
head
非空表 a a
1 n ∧考点三: 线性表的链式结构
设指针 p 指向某个Node类型的结点
该结点用 *p 来表示,*p 为结点变量。将“指针 p 所指结点”简称为“结点 p”
如何引用结点 p 的数据域(指针域)?
*p.data *p.next
如何表示结点 p 的下一个结点?
p->data p->next
p
head
a a a
1 2 n ∧
*p *(p->next)【单链表的基本操作】考点三: 线性表的链式结构
…
p
创建结点
Node
LNode *p = NULL;
p = (LNode *)malloc(sizeof(LNode));
…
p -> data = 20;
p -> next = null;考点三: 线性表的链式结构
…
p
如何将一个结点释放给内存?
Node
free(p);
…考点三: 线性表的链式结构
结点的赋值
Q=P,将P的值赋给Q考点三: 线性表的链式结构
赋值为直接后继结点
P=Q-> next,将P赋值为Q的直接后继结点考点三: 线性表的链式结构
指针向后移动
P = P -> next,将指针P向后移动一个位置,指向直接后继结点考点三: 线性表的链式结构
赋值为直接后继结点
P=Q-> next,将P赋值为Q的直接后继结点考点三: 线性表的链式结构
插入一个节点:实现结点a 、x 和 a之间逻辑关系的变化
i-1 i
… a b …
①p->next=s ②s->next=p->next
s
x
操作描述:
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;考点三: 线性表的链式结构
删除一个结点:实现结点a 、a 和 a 之间逻辑关系的变化
i-1 i i+1
p q p q p q
head
a a a a a
∧
1 i-1 i i+1 n
操作描述:
表尾的特殊情况:
q=p->next; x=q->data;
虽然被删结点不存在,但其前驱
p->next=q->next; free(q);
结点却存在!【单链表的实现】
创建(头插法和尾插法)考点三: 线性表的链式结构
头插法
操作接口:LinkList CreateList(ElemType a[], int n)
数组a 35 12 24 33 42
头插法:插在头结点的后面
⚫ 从一个空表开始,创建一个头结点。
⚫ 依次读取字符数组a中的元素,生成新结点
⚫ 将新结点插入到当前链表的表头上,直到结束为止。
s
L …
a a
i-1 1
a
i
注意:链表的结点顺序与逻辑次序相反。考点三: 线性表的链式结构
头插法
操作接口:LinkList CreateList(ElemType a[], int n)
数组a 35 12 24 33 42
头插法:插在头结点的后面
初始化 head = (LNode *)malloc(sizeof(LNode));
head->next = NULL;
head
s = (LNode *)malloc(sizeof(LNode));
∧
s->data = a[0];
s->next = head->next;
head->next = s;
35
∧
s
插入第一个元素结点考点三: 线性表的链式结构
头插法
操作接口:LinkList CreateList(ElemType a[], int n)
数组a 35 12 24 33 42
头插法:插在头结点的后面
依次插入每一个结点
单链表的元素顺序有什么特点?
head
35
∧
s = (LNode *)malloc(sizeof(LNode));
s->data = a[i];
s->next = head->next;
12
s head->next = s;考点三: 线性表的链式结构
// 头插法创建带头结点的单链表,使用数组a中n个元素初始化结点,返回头指针
LinkList CreateList(ElemType a[], int n) {
LinkList head = new LNode; // 创建头结点
head->next = NULL; // 链表初始为空表
for (int i = 0; i < n; ++i) {
LinkList node = new LNode; // 创建新链表结点
node->data = a[i]; // 将数组a中的元素赋值给新结点的数据域
node->next = head->next; // 将新结点插入到头结点之后
head->next = node; // 更新头结点的指针域
}
return head;
}考点三: 线性表的链式结构
头插法的核心代码是:
(1)node = (LNode *)malloc(sizeof(LNode));
(2)node->data = i;
(3)node->next = head->next; ①
(4)head->next = node; ②
第一行的操作是给新的结点分配空间;第二个是给新节点赋值数据域;
第三行和第四行是把新结点插入到头结点第一个数据结点之间。如图所示:考点三: 线性表的链式结构
尾插法
操作接口:LinkList CreateList2(ElemType a[], int n)
数组a 35 12 24 33 42 尾插法:插在尾结点的后面
⚫ 从一个空表开始,创建一个头结点。
⚫ 依次读取字符数组a中的元素,生成新结点
⚫ 将新结点插入到当前链表的表尾上,直到结束为止。
s
L …
a a
1 j
a
rear i
增加一个尾指针rear,使其始终指向当前链表的尾结点
注意:链表的结点顺序与逻辑次序相同。考点三: 线性表的链式结构
尾插法
数组a 35 12 24 33 42 尾插法:插在尾结点的后面
依次插入每一个结点
head s = (LNode *)malloc(sizeof(LNode));
35 12
s s->data = a[i];
rear->next = s; rear = s;
rear
head
35 42 ∧
s
rear考点三: 线性表的链式结构
// 尾插法创建带头结点的单链表,使用数组a中n个元素初始化结点,返回头指针
LinkList CreateList2(ElemType a[], int n) {
LinkList head = new LNode; // 创建头结点
head->next = NULL; // 链表初始为空表
LinkList end = head; // 尾指针指向最后一个结点,用于插入新结点
for (int i = 0; i < n; ++i) {
LinkList node = new LNode; // 创建新链表结点
node->data = a[i]; // 将数组a中的元素赋值给新结点的数据域
end->next = node; // 将新结点插入到尾结点之后
end = node; // 更新尾指针指向新结点
}
end->next = NULL; // 尾结点的指针域置空,此句不可省
return head;
}考点三: 线性表的链式结构
头插法的核心代码是:
(1)Lnode = (LNode *)malloc(sizeof(LNode)); // 为新结点开辟新内存
(2)node->data = i; // 新结点的数据域赋值
(3)end->next = node; ① //新结点赋给end的下一个
(4)end = node; ② //新结点成为新的尾结点
第一行的操作是给新的结点分配空间;第二个是给新节点赋值数据域;
第三行新结点插入到尾结点后面,第四行是把新结点赋值为新的尾结点。如图
所示:【单链表的初始化】考点三: 线性表的链式结构
head
初始化一个单链表 ∧
LNode *InitList( )
{
LNode *head = (LNode *)malloc(sizeof(LNode));
head->next = NULL;
return head;
}
建立一个空的单链表,即创建一个头结点。【单链表的查找】考点三: 线性表的链式结构
按位查找的函数
GetElem
输入:元素的序号 i
功能:在表中取序号为 i的数据元素
输出:若 i合法,输出序号为 i的元素值
head
a a a
1 i n ∧
查找操作是否成功
操作接口: bool GetElem(LinkList head, int i, ElemType& e)考点三: 线性表的链式结构
p p
head
a a a
∧
1 i n
count = i i > n
// 查找成功,返回true
// 查找失败,返回false
bool GetElem(LinkList head, int i, ElemType& e) {
if (i <= 0) {
return false; // 序号不合法,查找失败
}
LinkList p = head; // 指针p指向头结点,即第0个结点
for (int j = 0; p && j < i; ++j) { // 遍历链表,p指向第j个结点
p = p->next;
}
if (!p) {
return false; // 指针p为空,第i个结点不存在,查找失败
}
e = p->data; // 用e返回第i个结点的数据域
return true;
}考点三: 线性表的链式结构
按值查找的函数
LocateElem
输入:元素的x
功能:在表中值为x的数据元素
输出:若 x找到,输出序号为 i
head
a a a
1 i n ∧
查找操作是否成功
操作接口:LinkList LocateElem(LinkList head, ElemType e)考点三: 线性表的链式结构
p
head
a x a
1 ∧
n
LinkList LocateElem(LinkList head, ElemType e) {
if (!head) {
return NULL; // head为空,链表不存在
}
LinkList p = head->next; // 指针p指向第一个结点
while (p && p->data != e) { // 遍历链表,查找数据域等于e的结点
p = p->next;
}
return p; // 返回找到的结点指针,若未找到则返回NULL
}【单链表的插入】考点三: 线性表的链式结构
单链表插入操作的函数
ListInsert
输入:插入位置 i,待插 x
功能:在表的第 i个位置处插入一个新元素 x
输出:若插入成功,表中增加一个新元素;否则给出失败信息
head
a a a a
∧
1 i-1 i n
插入操作是否成功
操作接口:bool ListInsert(LinkList head, int i, ElemType e)考点三: 线性表的链式结构
实现结点a 、x 和 a之间逻辑关系的变化
i-1 i
p
head
a a a a
∧
1 i-1 i n
x
算法描述: s
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;考点三: 线性表的链式结构
注意分析边界情况——表头、表尾?
p p
p
head
a a a a
∧
1 i-1 i n
x x
x
s s ∧
s
s->next = p->next;
p->next = s;考点三: 线性表的链式结构
p p
p
head
a a a a
∧
1 i-1 i n
x x
x
s s ∧
s
算法:ListInsert
输入:单链表的头指针head,插入位置 i,待插值 x
输出:如果插入成功,返回新的单链表,否则返回插入失败信息
1. 工作指针 p 初始化为指向头结点;
2. 查找第i-1个结点并使工作指针 p 指向该结点;
3. 若查找不成功,说明插入位置不合理,返回插入失败信息;
否则,生成元素值为 x 的新结点 s,将结点 s 插入到结点 p 之后;考点三: 线性表的链式结构
// 在带头结点的单链表中的第i个位置上插入数据域为e的新结点
bool ListInsert(LinkList head, int i, ElemType e) {
if (i <= 0) { return false; } // 序号不合法,插入失败
LinkList p = head; // 指针p指向头结点,即第0个结点
for (int j = 0; p && j < i - 1; ++j) { // 遍历链表,p指向第j个结点 ①
p = p->next; // ②
}
if (!p) { return false; }// 指针p为空,第i-1个结点不存在,插入失败
LinkList node = new LNode; // 创建新结点 ③
node->data = e; // 新结点的数据域赋值为e ④
node->next = p->next; // 新结点插入到第i个位置上 ⑤
p->next = node; // 更新第i-1个结点的指针域 ⑥
return true;
}【单链表的删除】考点三: 线性表的链式结构
单链表删除操作的函数
ListDelete
输入:删除位置 i
功能:删除表中的第 i个元素
输出:若删除成功,返回被删元素值;否则给出失败信息
head
a a a a a
∧
1 i-1 i i+1 n
删除操作是否成功
操作接口:bool ListDelete(LinkList head, int i, ElemType& e)考点三: 线性表的链式结构
实现结点a 、a和 a 之间逻辑关系的变化
i-1 i i+1
p q p q p q
head
a a a a a
∧
1 i-1 i i+1 n
注意分析边界情况——删除表头和表尾!
算法描述:
表尾的特殊情况:
q=p->next; x=q->data;
虽然被删结点不存在,但其前驱
p->next=q->next; free(q);
结点却存在!
操作接口: bool ListDelete(LinkList head, int i, ElemType& e)考点三: 线性表的链式结构
p q p q p q
head
a a a a a
∧
1 i-1 i i+1 n
算法: ListDelete
输入:单链表的头指针head,删除的位置 i
输出:如果删除成功,返回被删除的元素值,否则返回删除失败信息
1. 工作指针 p 初始化;累加器count初始化;
2. 查找第i-1个结点并使工作指针 p 指向该结点;
3. 若 p 不存在或 p 的后继结点不存在,则出现删除位置错误,删除失败;
否则,3.1 存储被删结点和被删元素值;
3.2 摘链,将结点 p 的后继结点从链表上摘下;
3.3 释放被删结点;考点三: 线性表的链式结构
// 按序号查找,在带头结点的单链表中删除第i个结点,并用e返回其数据域的值
// 删除成功,返回true
// 删除失败,返回false
bool ListDelete(LinkList head, int i, ElemType& e) {
if (i <= 0) {
return false; // 序号不合法,删除失败
}
LinkList p = head; // 指针p指向头结点,即第0个结点
for (int j = 0; p && j < i - 1; ++j) { // 遍历链表,p指向第j个结点 ①
p = p->next; // ②
}
if (!p || !p->next) {
return false; // 指针p为空或p->next为空,第i-1个结点不存在或第i个结点不存在,删除失败
}
LinkList node = p->next; // 指针node指向第i个结点 ③
p->next = node->next; // 删除第i个结点 ④
e = node->data; // 用e返回第i个结点的数据域 ⑤
delete node; // 释放第i个结点的内存空间 ⑥
return true;
}考点三: 线性表的链式结构
单链表删除操作的函数
ListLocalDelete
输入:删除值为x
功能:删除表中的第1个值值为x元素
输出:若删除成功;否则给出失败信息
head
a a x a a
∧
1 i-1 i+1 n
删除操作是否成功
操作接口:bool ListLocalDelete(LinkList head, ElemType e)考点三: 线性表的链式结构
单链表删除操作的函数
ListLocalDelete
输入:删除值为x
功能:删除表中的第1个值值为x元素
输出:若删除成功;否则给出失败信息
p q p q p q
head
a a a a a
∧
1 i-1 i i+1 n考点三: 线性表的链式结构
// 按值查找,在带头结点的单链表中删除第一个数据域等于e的结点,返回其指针
// 删除成功,返回true
// 删除失败,返回false
bool ListLocalDelete(LinkList head, ElemType e) {
if (!head) {
return false; // head为空,链表不存在
}
LinkList p = head; // 指针p指向头结点,即第0个结点
while (p->next && p->next->data != e) { // 遍历链表,查找数据域等于e的结点
p = p->next;
}
if (!p->next) {
return false; // 指针p->next为空,未找到数据域等于e的结点,删除失败
}
LinkList node = p->next; // 指针node指向数据域等于e的结点
p->next = node->next; // 删除结点
delete node; // 释放结点的内存空间
return true;
}【单链表的遍历】考点三: 线性表的链式结构
遍历操作的函数
PrintList
输入:无
功能:遍历操作,按序号依次输出线性表的元素
输出:线性表的各个数据元素
head
a a a
∧
1 2 n
操作接口:void PrintList(LNode *head)考点三: 线性表的链式结构
p
p
head
a a a
∧
1 2 n
如何实现工作指针后移
p p++ p->next
a a
1 2
p = p->next
核心操作:工作指针后移考点三: 线性表的链式结构
p
p
head
a a a
∧
1 2 n
// 遍历带头结点的单链表,依次输出每个结点的数据域
void PrintList(LinkList head) {
if (!head) {
return; // head为空,链表不存在
}
for (LinkList p = head->next; p; p = p->next) { // 遍历链表
printf("%d ", p->data); // 输出结点的数据域
}
printf("\n");
}【政哥题型总结】考点三: 线性表的链式结构
1.在一个单链表中,如果q所指的结点是p所指的结点的前驱结点,若
在q与p之间插入一个s所指的结点,则执行( )。
A.s->next=p->next;p->next=s;
B.p->next=s->next;s->next=p;
C.p->next=s;s->next=q;
D.q->next=s;s->next=p;考点三: 线性表的链式结构
D【解析】我们举一个简单的例子,如图所示的单链表中,q指针指向p
指针所指的结点的前驱结点,现在要在q、p之间插入一个由指针s指向
的新结点,只需要让新结点的指针域指向p(s->next=p),再更新q的后
继结点为s指向的结点(q->next=s),这两个操作顺序颠倒也可以,不会
出现链表断开的现象。考点三: 线性表的链式结构
2.已知指针p和q分别指向某单链表中的第一个结点和最后一个结点。
假设指针s指向另一个单链表中的某个结点,则在s所指的结点之后插入
上述链表,应执行的语句为( )。
A.q->next=s->next;s->next=p;
B.s->next=p;q->next=s->next;
C.p->next=s->next;s->next=q;
D.s->next=q;p->next=s-next;考点三: 线性表的链式结构
A【解析】在指针s指向的结点之后插入一段以p和q分别指向第一个结
点和最后一个结点的链表,只需要令q的指针域指向s的后继结点(q->
next=s->next),再调整s的指针域,使其指向新的后继结点p(s->
next=p)即可,如图所示。考点三: 线性表的链式结构
3.给定键值按升序排列的带头结点的单链表La和Lb,将其合并成升序
排列的单链表,并返回新链表的表头指针。要求利用原表的结点数据空
间。
pa
La
Lc
……
-7 3 12 23 ⋀
pc
Lb
……
-2 4 9
pb
两个有序的单链表La ,Lb的初始状态考点三: 线性表的链式结构
第一种想法 (暴力法):
pa
La
Lc
……
-7 3 12 23 ⋀
pc
Lb
……
-2 4 9
pb考点三: 线性表的链式结构
第二种想法 (排序法)考点三: 线性表的链式结构
第三种想法 (双指针法:前世的500次回眸):
合并了值为-7,-2的结点后示意图如图所示。
pa
La
Lc ……
-7 3 12 23 ⋀
Lb
……
-2 4 9 15 ⋀
p pb
合并了值为-7 ,-2的结点后的状态考点三: 线性表的链式结构
pa
La
Lc
……
-7 3 12 23 ⋀
p
Lb
……
-2 4 9
pb
LinkList MergeList(LinkList a, LinkList b){
// 合并以La, Lb为头结点的两个有序单链表
LinkList p = a; // p指向合并后的链表的尾结点
LinkList pa = a->next, pb = b->next;考点三: 线性表的链式结构
pa
La
Lc
……
-7 3 12 23 ⋀
p
Lb
……
-2 4 9
pb
LinkList MergeList(LinkList a, LinkList b){
if (!a && !b) {
return NULL; // 链表a,b都不存在
}
if (!a) {
return b; // 链表a不存在,合并结果为链表b
}
if (!b) {
return a; // 链表b不存在,合并结果为链表a
}考点三: 线性表的链式结构
LinkList MergeList(LinkList a, LinkList b){
while (pa != NULL && pb != NULL)
{
// 将pa所指的结点合并,pa指向下一个结点
if (pa->data < pb->data) {p->next = pa; p = pa; pa = pa->next;}
pa
La
Lc
……
-7 3 12 23 ⋀
p
Lb
……
-2 4 9
pb考点三: 线性表的链式结构
LinkList MergeList(LinkList a, LinkList b){
while (pa && pb)
{
// 将pa所指的结点合并,pa指向下一个结点
if (pa->data < pb->data) {p->next = pa; p = pa; pa = pa->next;}
p pa
La
Lc
……
-7 3 12 23 ⋀
pc
Lb
……
-2 4 9
pb考点三: 线性表的链式结构
LinkList MergeList(LinkList a, LinkList b) {
// 合并以La, Lb为头结点的两个有序单链表
else if (pa->data > pb->data) {p->next = pb; p = pb; pb = pb->next; }
pa
La
Lc
……
-7 3 12 23 ⋀
p
Lb
……
-2 4 9
pb考点三: 线性表的链式结构
LinkList MergeList(LinkList a, LinkList b){
// 合并以La, Lb为头结点的两个有序单链表
else {
p->next = pa; p = pa; pa = pa->next; ptr = pb; pb = pb->next; delete ptr;
}
// 将pa所指的结点合并,pb所指的结点删除
}
}
pa
La
Lc ……
-7 3 12 23 ⋀
Lb
……
-2 4 9 15 ⋀
p pb考点三: 线性表的链式结构
LinkList MergeList(LinkList a, LinkList b){
if (!a && !b) {
return NULL; // 链表a,b都不存在
}
if (!a) {
return b; // 链表a不存在,合并结果为链表b
}
if (!b) {
return a; // 链表b不存在,合并结果为链表a
}
LinkList p = a; // p指向合并后的链表的尾结点
LinkList pa = a->next, pb = b->next;考点三: 线性表的链式结构
while (pa && pb) {
if (pa->data < pb->data) {
p->next = pa;
p = pa; // 尾插法,将pa结点插入到c结点之后
pa = pa->next;
} else if (pa->data > pb->data) {
p->next = pb;
p = pb; // 尾插法,将pb结点插入到c结点之后
pb = pb->next;
} else { // 相等的情况
p->next = pa;
p = pa; // 尾插法,将pa结点插入到c结点之后
pa = pa->next;
LinkList node = pb; // 删除pb结点
pb = pb->next;
delete node; // 释放pb结点的空间
}
}
p->next = pa ? pa : pb; // 将剩余的结点插入到c结点之后
delete b; // 释放链表b的头结点空间
return a; // 合并后的链表为a
}考点三: 线性表的链式结构
4、删除单链表中所有值重复的结点,使得所有结点的值都不相同。
基本思想:从单链表的第一个结点开始,对每个结点进行检查:检查链表中该
结点的所有后继结点,只要有值和该结点的值相同,则删除之;然后检查下一
个结点,直到所有的结点都检查。考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
p
head
a a a a a a a
1 2 3 i-1 i i+1 n ∧
q ptr考点三: 线性表的链式结构
// 删除单链表中所有值重复的结点,使得所有结点的值都不相同。
p
void Delete_Node_Value(LNode *L) {
head
// 删除以L为结点的单链表中所有值相同的结点 a a a
1 2 3
LNode *p = L->next, *q, *ptr;
q ptr
while (p != NULL) { // 检查链表中的所有结点
q = p; ptr = p->next;
//检查结点p的所有后继结点ptr
while (ptr != NULL) {
if (ptr->data == p->data)
{q->next = ptr->next; free(ptr); ptr = q->next;}
else {q = ptr ; ptr = ptr->next;}
}
p = p->next;
}
}考点三: 线性表的链式结构
// 删除单链表中所有值重复的结点,使得所有结点的值都不相同。 p
void Delete_Node_Value(LNode *L) {
head
a a a a
// 删除以L为结点的单链表中所有值相同的结点 1 2 3 i-1
LNode *p = L->next, *q, *ptr; q ptr
while (p != NULL) { // 检查链表中的所有结点
q = p; ptr = p->next; p
//检查结点p的所有后继结点ptr
head
a a a
while (ptr != NULL) { 1 2 3
q ptr
if (ptr->data == p->data)
{q->next = ptr->next; free(ptr); ptr = q->next;}
else {q = ptr ; ptr = ptr->next;}
}
p = p->next;
}
}考点三: 线性表的链式结构
// 删除单链表中所有值重复的结点,使得所有结点的值都不相同。 p
void Delete_Node_Value(LNode *L) {
head
a a a a
// 删除以L为结点的单链表中所有值相同的结点 1 2 3 i-1
LNode *p = L->next, *q, *ptr; q ptr
while (p != NULL) { // 检查链表中的所有结点
q = p; ptr = p->next;
//检查结点p的所有后继结点ptr
while (ptr != NULL) {
if (ptr->data == p->data)
{q->next = ptr->next; free(ptr); ptr = q->next;}
else {q = ptr ; ptr = ptr->next;}
}
p = p->next;
}
}考点三: 线性表的链式结构
void DeleteDuplicate(LinkList head) {
if (!head) {
return; // head为空,链表不存在
}
for (LinkList p = head->next; p; p = p->next) {
ElemType e = p->data; // 记录当前结点的数据域,用于比较
for (LinkList q = p; q->next;) {
if (q->next->data == e) { // 找到重复结点,此时q指向重复结点的前驱
LinkList node = q->next;
q->next = node->next; // 删除重复结点,q保持不变
delete node; // 释放重复结点的空间
} else {
q = q->next; // 没有找到重复结点,q向后移动
}
}
}
}考点三: 线性表的链式结构
5、单链表结点的类型定义如下。
typedef struct node{
elemtype data; //数据域
struct node * next; //指针域
}LNode, *Linklist.
假设有一个带头结点的单链表L=(a,a,…,a)。
1 2 n
设计一个算法将所有结点逆置,即:L=(a ,a ,…,a)
n n-1 1考点三: 线性表的链式结构
p
…
a a a ∧
1 2 n
头插法建表
head ∧考点三: 线性表的链式结构
void ReverseList(LinkList head) {
if (!head || !head->next) {
return; // head为空或者只有一个结点,无需反转
}
LinkList p = head->next;
head->next = NULL;
while (p) {
LinkList node = p; // 记录当前结点
p = p->next; // 将p指向下一个结点
node->next = head->next;
head->next = node; // 头插法,将node结点插入到head结点之后
}
}THANKSCON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考纲框架【静态链表的定义】考点四: 线性表的静态链表
用数组来实现链式存储结构,数组的每个元素由data和cur两部分组成,其中cur
相当于链表的next指针,指示节点在数组中的相对位置(下标,游标),这种用
数组描述的链表叫做静态链表。考点四: 线性表的静态链表
实现原理:
1、使用结构体数组,结构体有指针域 cur 和数据域 data
2、一个数组分量表示一个节点,用cur代替指针指示节点在数组中的相对位置
head bat cat eat fat hat ⋀
Data Cur
0
hat -1
head
1
bat 3
2
3
cat 7
4
5 fat 0
6
7 eat 5【静态链表的操作】考点四: 线性表的静态链表
插入操作:静态链表的插入和单链表的插入类似,都是沿着链的顺序,
找到元素的位置,然后修改指针,不同的是静态链表的插入不需要移
动元素,只需要修改游标就可以。考点四: 线性表的静态链表
插入操作:在静态链表中插入duck,其插入到cat和eat之间。其方法
是,从前往后找到第一个空位,其编号是2,将cat的游标改为2,将
duck的游标设置为7。
head bat cat eat fat hat ⋀考点四: 线性表的静态链表
删除操作:静态链表的删除和单链表的删除类似,都是沿着链的顺序,
找到元素的位置,然后修改指针,不同的是静态链表的删除不需要移
动元素,只需要修改游标就可以。考点四: 线性表的静态链表
删除操作:在静态链表中要删除cat。找到cat的位置,将bat的游标改
为7。
head bat cat eat fat hat ⋀THANKSCON T EN T S
目录
考点一 基本定义和逻辑结构
考点二 线性表的顺序结构 ★★★★
考点三 线性表的链式结构 ★★★★★
考点四 线性表的静态链表 ★
考点五 线性表的其他链式结构 ★★考纲框架【双链表的定义】考点五: 线性表的其他链式结构
从结点 p 出发,如何求得结点 p 的直接前驱,时间性能?
p
head
a a a a a
∧
1 i-1 i i+1 n
如何快速求得结点 p 的前驱?
双链表:单链表的每个结点再设置一个指向其前驱结点的指针域
head
∧ a 1 a 2 a 3 a 4 ∧考点五: 线性表的其他链式结构
启示? 时空权衡——空间换取时间 数据表示
typedef int ElemType; /*定义线性表的数据类型,假设为int型*/
typedef struct DNode
{
ElemType data;
struct DNode *prior, *next;
prior data next
} Dnode, *Dlinklist;
head
∧ a a a
1 2 3【双链表的操作及应用】考点五: 线性表的其他链式结构
双链表插入操作
输入:插入位置 i,待插 x
功能:在表的第 i 个位置处插入一个新元素 x
输出:若插入成功,表中增加一个新元素;否则给出失败信息
head
∧ a 1 a i a n ∧考点五: 线性表的其他链式结构
双链表插入(后插入) 在p结点之后插入结点s
p
a a
i i+1
s
x
注意指针修改的相对顺序考点五: 线性表的其他链式结构
p
a a
i i+1
s
x
s = (DNode *)malloc(sizeof(DNode));
s->prior = p;
s->next = p->next;
p->next->prior = s;
注意指针修改的相对顺序
p->next = s;考点五: 线性表的其他链式结构
双链表插入(前插入) 在p结点之前插入结点s
p
a a
i i+1
s
x
注意指针修改的相对顺序考点五: 线性表的其他链式结构
p
a a
i i+1
s
x
s = (DNode *)malloc(sizeof(DNode));
s->prior = p->prior;
s->next = p;
p->prior = s;
注意指针修改的相对顺序
s->prior->next = s;考点五: 线性表的其他链式结构
双链表插入删除
双链表删除(删除自己)删除p结点自身
p
a a a
i-1 i i+1考点五: 线性表的其他链式结构
双链表删除(删除自己)删除p结点自身
p
a a a
i-1 i i+1
(p->prior)->next = p->next;
(p->next)->prior = p->prior;
free(p);
结点 p 的指针是否需要修改?考点五: 线性表的其他链式结构
双链表删除(删除后继)删除p结点的直接后继
p
q
a a a
i-1 i i+1考点五: 线性表的其他链式结构
双链表删除(删除后继)删除p结点的直接后继
p
q
a a a
i-1 i i+1
q = p->next;
p->next = q->next;
(q->next)->prior = p ;
结点 p 的后继q是否需要修改? free(q);考点五: 线性表的其他链式结构
双链表删除(删除前驱)删除p结点的直接前驱
q p
a a a
i-1 i i+1考点五: 线性表的其他链式结构
双链表删除(删除前驱)删除p结点的直接前驱
q p
a a a
i-1 i i+1
q = p->prior;
q->prior->next = p;
p->prior = q->prior;
结点 p 的前驱q是否需要修改? free(q);【循环链表】考点五: 线性表的其他链式结构
p
head
a a a a a
∧
1 i-1 i i+1 n
如何求得结点 p 的前驱?考点五: 线性表的其他链式结构
p
head
a a a a a
∧
1 i-1 i i+1 n
如何求得结点 p 的前驱?
循环链表:将链表的首尾相接
循环单链表:将终端结点的指针由空指针改为指向头结点考点五: 线性表的其他链式结构
循环链表是另一种形式的链式存储结构形式。
⚫ 循环单链表:将表中尾结点的指针域改为指向
结点类型与非循环单链
表头结点,整个链表形成一个环。由此从表中 表的相同
任一结点出发均可找到链表中其他结点。
结点类型与非循环双链
⚫ 循环双链表:形成两个环。
表的相同考点五: 线性表的其他链式结构
循环单链表
线性表
(a,a,…,a,…,a)
1 2 i n
逻辑结构
映射
head
存储结构
a a … a
1 2 n
带头结点循环单链表示意图考点五: 线性表的其他链式结构
与非循环单链表相比,循环单链表:
⚫ 链表中没有空指针域
⚫ p所指结点为尾结点的条件:p->next==head
head
p
…
a a a
1 2 n考点五: 线性表的其他链式结构
循环双链表
逻辑结构
线性表
(a,a,…,a,…,a)
1 2 i n
映射
存储结构
head
…
a a a
1 2 n
带头结点循环双链表示意图考点五: 线性表的其他链式结构
与非循环双链表相比,循环双链表:
⚫ 链表中没有空指针域
⚫ p所指结点为尾结点的条件:p->next==L
⚫ 一步操作即L->prior可以找到尾结点
head
p
a a … a
1 2 n【政哥习题总结】考点五: 线性表的其他链式结构
1.如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后
面插入新元素,那么最好使用( )。
A.只有表头指针没有表尾指针的循环单链表
B.只有表尾指针没有表头指针的循环单链表
C.非循环双链表
D.循环双链表考点五: 线性表的其他链式结构
B【解析】如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素
的后面插入新元素,那么最好使用带表尾指针的没有表头指针的循环单链表。
设表尾指针为rear,则删除第一个元素的操作为
rear->next=rear->next->next
在最后一个元素之后插入新元素s的操作为
s->next=rear->next;rear->next=s考点五: 线性表的其他链式结构
2.在循环双链表的p所指的结点之前插入s所指结点的操作是( )。
A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior
B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior
C.s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s
D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s考点五: 线性表的其他链式结构
p
a a
i i+1
s
x
s = (DNode *)malloc(sizeof(DNode));
s->prior = p->prior;
s->next = p;
p->prior = s;
注意指针修改的相对顺序
s->prior->next = s;考点五: 线性表的其他链式结构
D【解析】双链表的插入和删除,请大家注意,不要出现断链的情况,要在p
的前面插入s结点,说明p的直接前驱依赖于p的prior指针,所以不可以首先操
作p->prior=s;,否则会产生断链,因此A,B错误。C和D选项,前两步一
样,C选项,先操作p->prior=s;,会导致原来的p->prior丢失,产生断链。
因此选D。THANKS