第2章 线性表2-链式表示和实现

例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
存储地址
头指针 H 31 1 7 13 19 25 31 37 43
数据域 LI QIAN SUN
指针域 43 13 1
WANG WU ZHAO ZHENG ZHOU
NULL 37 7 19 25
H ZHAO ZHOU QIAN SUN ZHENG
的结点。
例： 一个线性表的逻辑结构为：
（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存 储结构用单链表表示如下，请问其头指针的值是多少？
答：头指针是指向 链表中第一个结点 的指针，因此关键 是要寻找第一个 存储地址 1 7 13 19 25 31 37 43 数据域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 指针域 43 13 1 NULL 37 7 19 25
2.3.3双向链表
双向链表(Double linked list):在单链表 的每个结点里再增加一个指向其直接前趋 的指针域prior。这样就形成的链表中有两 个方向不同的链，故称为双向链表。形式 描述为： typedef struct DuLNode{ Elemtype data; struc DuLNode *prior，*next; } DuLNode,* DuLinkList;
用链表可表示为：
La 头结点
3
Lb
5 6
8 8
11 9
/\
2
11
/\
Lc
2 8
8
3
9
5
11
6
11
/\
算法分析：
算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表；
比较：比较结点数据域中数据的大小；
插入：将两个结点中数据小的结点插入新链表。
Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点 La
和单链表类似，双链表一般也是由头指 针唯一确定的，增加头指针也能使双链表 上的某些运算变得方便，将头结点和尾结 点链接起来也能构成循环链表，并称之为 双向链表。 设指针p指向某一结点，则双向链表结构 的对称性可用下式描述： (p—>prior)—>next=p=(p—>next)—>prior 即结点*p的存储位置既存放在其前趋结点 *(p—>prior)的直接后继指针域中，也存放 在它的后继结点*(p—>next)的直接前趋指 针域中。
LI
WANG ^
WU
与链式存储有关的术语：
1、结点：数据元素的存储映像。由数据域和指针域两部分组成； 2、链表： n 个结点由指针链组成一个链表。它是线性表的链式 存储映像，称为线性表的链式存储结构。 3、单链表、双链表、多链表、循环链表： • 结点只有一个指针域的链表，称为单链表或线性链表； • 有两个指针域的链表，称为双链表； • 有多个指针域的链表，称为多链表； • 首尾相接的链表称为循环链表。 循环链表示意图：
head
a1
….
an
⑴ 非空表
⑵ 空表 在用头指针表示的单链表中，找开始结点a1 的时间是O(1)，然而要找到终端结点an，则需 从头指针开始遍历整个链表，其时间是O(n)
在很多实际问题中，表的操作常常是在 表的首尾位置上进行，此时头指针表示的 单循环链表就显得不够方便.如果改用尾指 针rear来表示单循环链表，则查找开始结点 a1和终端结点an都很方便，它们的存储位置 分别是(rear–>next) —>next和rear，显然， 查找时间都是O(1)。因此，实际中多采用尾 指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及 遍历操作时，其终止条件就不再像非循环 链表那样判断p或p—>next是否为空，而是 判断它们是否等于某一指定指针，如头指 什或尾指针等。
教材P28对于单链表的抽象描述:
typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode, *LinkList; //数据域 //指针域 // *LinkList为Lnode类型的指针
介绍三个有用的库函数（都在<stdlib.h> 中）： sizeof(x)——计算变量x的长度； malloc(m) —开辟m字节长度的地址空间，并返回这 段空间的首地址； free(p) ——释放指针p所指变量的存储空间，即彻底 删除一个变量。
Pa
3
Pa 5 Pb
Pa 8
Pa
11 ^ Pb
Lb
Pb
2
Pc 2 Pc
6 Pc
3
8
9
11 ^
Lc
Pc 5 … 11 ^
算法实现： Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { //按值排序的单链表LA,LB，归并为LC后也按值排序
点的数据域中不存储线性表的数据元素，其作用是为了对链表 进行操作时，可以对空表、非空表的情况以及对首元结点进行 统一处理，编程更方便。
讨论2. 如何表示空表？ 答：无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表。
头指针
^
头指针
头结点
^
无头结点
有头结点
结构类型的C语言表示法
head
a1

a2
……
an
head
何谓头指针、头结点和首元结点？
头指针 头结点 首元结点
a1
头指针是指向链表中第一个结点（或为头结点或为
首元结点）的指针。 单链表可由一个头指针唯一确定。
头结点是在链表的首元结点之前附设的一个结点；
数据域内只放空表标志和表长等信息;
首元结点是指链表中存储线性表第一个数据元素a1
数据结构讲义 第2章 线性表
- 链式表示和实现
2.3 线性表的链式表示和实现
2.3 .1 链表的表示 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑 上相邻的元素 每个数据元素ai，除存储本身信息外，还需存 储其直接后继的信息 结点 – 数据域：元素本身信息 – 指针域：指示直接后继的存储位置
例、在链表上实现将两个线性表(a1，a2， a3，…an)和(b1，b2，b3，…bn)链接成一个线 性表的运算。 linklist connect(linklist heada，linklist headb) { linklist p=heada—>next; heada—>next=(headb—next)—>next free(headb—>next); headb—>next=p; return(headb); }
2. 单链表的删除
在链表中删除某元素的示意图如下： p a × b × c
p->next 删除步骤（即核心语句）：
(p->next) -> next
q = p->next; //保存b的指针，靠它才能指向c p->next=q->next; //a、c两结点相连 free(q) ； //删除b结点，彻底释放 思考： 省略free(q)语句行不行？
H
讨论2： 单链表只能查找结点的直接后继， 能不能查找直接前驱？如何实现？
答：能。只要把单链表再多开一个指针域即可(例 如用*next和*prior;) 。 prior data next 这种有两个指针的链表称为双向链表。其特点是 可以双向查找表中结点。参见教材P35—39。
双向链表在非线性结构（如树结构）中将大量使用。
while(p&&j<i-1){p=p->next; ++j;}//寻找第i-1 个结点 if(!p||j>i-1)return ERROR;//i小于1或者大于表长 S=(LinkList)malloc(sizeof(Lnode));//生成新结点 S->data=x; S->next=p->next; 单链表结点插入的演示 P->next=s; return OK;}
Status ListDelete(LinkList &L, int i, ElemType &e) /
在带头结点的单链表L中删除第i个元素，由e返回其值
{p=L->next; j=1; while(p&&j<i-1){p=p->next; ++j;} if(!p||j>i-1)return ERROR;//删除位置不合理 q=p->next; p->next=q->next; e=q->data; free(q); 单链表结点的删除演示 return OK;}
free(Lb); } //MergeList_L //释放Lb的头结点
其它链表形式
讨论1： 链表能不能首尾相连？怎样实现？ 答：能。只要将表中最后一个结点的指针域指向头结 点即可 (P->next=head;) 。这种形成环路的链表称 为循环链表。 参见教材P35
特点：
1、从任一结点出发均可找到表中其他结点。 2、操作仅有 一 点与单链表不同：循环条件 单链表 ----- p = NULL 或 p ->next =NULL 循环链表----- p= head 或 p->next = head 特别：带头结点的 空循环链表样式
pa=La-->next; pb=Lb-->next; Lc=pc=La； //初始化 while(pa&&pb) //将pa 、pb结点按大小依次插入C中 { if(pa->data<=pb->data) {pc->next=pa; pc=pa; pa=pa->next;} else {pc->next=pb; pc=pb; pb=pb->next} } pc->next = pa?pa:pb ; //插入剩余段