第02章 单链表

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

线性表的基本操作(逻辑）
➢ 构造一个空表L ➢ 获取L的长度（即元素个数） ➢ 访问L中第i个数据元素的值 ➢ 访问L中第i个数据元素的前驱/后继的值 ➢ 在L中第i个元素之前插入新的元素e ➢ 删除L的第i个数据元素
➢ 注意在插入或者删除之后，线性表的长度应 能随之改变
一 顺序存储
➢ 线性表的顺序表示：用一组地址连续的存储单 元依次存储线性表的数据元素。
否
将Temp_b插入到 LC的第k个位置上
Temp_a ≤ Temp_b
是 将Temp_a插入到 LC的第k个位置上
否 i ≤ LA.len 否
j← j + 1
i← i + 1
j ≤ LB.len
Temp_a = Temp_b
是
否
否
j← j + 1
k← k + 1
结束
是
将LA表的第i个元 素插入到LC表的
插入操作的时间复杂度 O(n/2) 链表中的插入、删除操作没有上溢的情况， 并且节省内存资源
思考：若现已知道指向某元素节点的指针 p，希望能在该节点之前插入元素x，该如 何操作？其算法时间复杂度是多少？
3) 单链表的删除
p
删除第i个元素，由e返回值 删除b
a
Hale Waihona Puke bc … 1) 寻找第i-1个结点
2) 保留结点b的地址
9 SHI 5
0
1
1 ZHAO 2
2 QIAN 3
3 SUN 4
4 LI
9
5 ZHOU 6
6 WU 8
7 ZHENG 8
8 WANG 0
9 SHI 5
i=s[i].cur 指针后移

2.4 一元多项式的表示
ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } { 称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系：
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
{ 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。}
i = 1; found = TRUE; while ( i<= La_len && found ) {
GetElem(LA, i, e); // 取得LA中一个元素
if (LocateElem(LB, e, equal( ))
i++;
// 依次处理下一个
else found = FALSE;
// LB中没有和该元素相同的元素
{加工型操作} ClearList( &L ) ( 线性表置空 ) PutElem( &L, i, &e ) ( 改变数据元素的值 ) ListInsert( &L, i, e ) ( 插入数据元素 ) ListDelete( &L, i, &e ) ( 删除数据元素 )
ClearList( &L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 PutElem( &L, i, e ) 初始条件： 线性表 L 已存在， 且 1≤i≤LengthList(L)。 操作结果：L 中第 i 个元素赋值和 e 相同。
线性结构的基本特征: 线性结构 是 一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素” 2．集合中必存在唯一的一个 “最后元素”

return ;
}
if ( L -> length >= ListSize ){
printf (" overflow ");
return ;
}
for ( j - L -> length -1; j >= i -1; j --)
L ->data [ j +1]= L -> data [ j ]; //从最后一个元素开始逐一后移
线性表的基本运算
上述运算仅仅是线性表的基本运算，不是其全部运 算。因为对不同问题的线性表，所需要的运算可能不同。 因此，对于实际问题中涉及其他更为复杂的运算，可用 基本运算的组合来实现。
线性表的基本运算
【例2.1】假设有两个线性表 LA 和 LB 分别表示两个 集合 A 和 B ，现要求一个新集合 A = A∪B 。
线性表的逻辑定义
数据元素“一个接一个的排列”的关系叫做 线性关系，线性关系的特点是“一对一”，在计 算机领域用“线性表”来描述这种关系。另外， 在一个线性表中数据元素的类型是相同的，或者 说线性表是由同一类型的数据元素构成的，如学 生情况信息表是一个线性表，表中数据元素的类 型为学生类型；一个字符串也是一个线性表：表 中数据元素的类型为字符型等等。
,
a2
i
,…,
ai-1
,
a．aii++1．1 , ．…,
an
)
an
线性表n的-1逻辑结an构和存储结构都发…生了相应的变化， 与插入运算相反，插…入是向后移动元素，而删除运算则
是向前移M动AX元-1 素，除非i=n 时直接删除终端元素，不需移
动元素。
删除前
删除后