数据结构（严蔚敏版）——第一章【复数的实现】
数据结构（严蔚敏版）第二章 ——线性表（一）
2.4、线性表的链式存储表示与实现
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
线性表的链式表示又称为非顺序映像或链式映像
链式存储结构特点：
- 用一组物理位置任意的存储单元来存放线性表的数据元素
- 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的
- 链表中元素的逻辑次序和物理次序不一定相同
结点的组成：数据域、指针域
2.4.1、与链式存储有关的术语
- 结点：数据元素的存储映像。由数据域和指针域两部分组成
- 链表：n个结点由==指针链==组成一个链表。
- 单链表：结点只有一个指针域的链表，称为单链表或线性表
- 双链表：结点由两个指针域的链表，称为双链表
- 循环链表：首尾相接的链表称为==循环链表==
- 头指针：是指向链表中第一个结点的指针
- 首元结点：是指链表中存储第一个数据元素$a_1$的结点
- 头结点：是在链表的首元结点之前附设的一个结点
单链表的分类：
- 带头节点
- 不带头节点
2.4.2、单链表的表示
1、存储结构
typedef struct Lnode { // 声明结点的类型和指针结点的指针类型
ElemType data; // 结点的数据域
struct Lnode *next; // 结点的指针域
}Lnode, *LinkList; // LinkList为指向结构体Lnode的指针类型定义链表L: LinkList L;
定义结点指针P: LNode *P 等同于LinkList p;
存储学生学号、姓名成绩的单链表表示：
typedef struct {
char num[8]; // 数据域
char num[8]; // 数据域
int score // 数据域
} ElemType;
typedef struct Lnode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} Lnode, *LinkList;2.4.3、单链表基本操作的实现
1、单链表的初始化（带头结点的单链表）
- 生成新结点作为头结点，用头指针L指向头结点
- 头结点的指针域为空
Status InitList(LinkList &L)
{ // 构造一个空的单链表
L = new LNode; // 生成新结点作为头结点，用头指针L指向头结点
// L = (LinkList) malloc (sizeof(LNode));
L -> next = NULL; // 头结点的指针域为空
return OK;
}2、判断链表是否为空
空表：链表中五元素，称为空链表（头指针和头结点仍然在）
- 判断指针域是否为空
int ListEmpty(LinkList L) // 若L为空表，则返回1，否则返回0
{
if (L -> next ) // 非空
return 0;
else
return 1;
}3、单链表的销毁（销毁后链表不存在）
- 从头指针开始，依次释放所有结点
Status DestroyList(LinkList &L) // 销毁单链表L
{
Lnode *p; // 或LinkList p;
while (L) {
p = L;
L = L -> next;
delete p;
}
return OK;
}3、清空单链表
链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）
- 依次释放所有结点，并将头结点指针与设置为空
Status ClearList(LinkList &L) { // 将L重置为空表
Lnode *p, *q; // 或LinkList p,q;
P = L -> next;
while (p) { // 没到表尾
q = p -> next;
delete p;
p = q;
}
L -> next = NULL; // 头结点指针域
return OK;
}4、求单链表的表长
- 从首元结点开始，依次计数所有结点
int ListLength(LinkList L) { // 返回L中数据元素个数
LinkList *p;
p = L -> next; // p指向第一个结点
i = 0;
while (p) {
i++; // 遍历单链表，统计结点数
p = p -> next;
}
return i;
}
5、单链表的取值
- 用指针p指向首元结点，用j做计数器初值赋为1
从首元结点开始依次开始顺着链域next向下访问，只要指向当前结点的指针P不为空（NULL），并且没有达到序号为i结点，则循环执行以下操作：
- p指向下一个结点
- 计数器j相应加1
- 退出循环时，如果指针p为空，或者计数器j 大于i，说明指定的序号i值不和法（i大于表长n或i小于等于0）取值失败返回ERROR；否则取值成功，此时j = i时，p所指的结点就是要找到的第i个结点，用参数e保存当前结点的数据域，返回OK。
Status GetElem(LinkList L,int i, ElemType &e)
{// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
p = L -> next; j = 1; // 初始化，p指向首元结点，计数器j初值赋为1
while (p && j < 1) { // 顺链域向后扫描，直到p为空或p指向第i个元素
p = p -> next; // p指向下一个结点
++j; // 计数器j相应加1
}
if (!p || j > i) return ERROR; // i值不合法i > n或i <= 0
e = p -> data; // 取第i个结点的数据域
return OK;
}6、单链表的按值查找
- 用指针p指向首元结点
- 从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点
- 返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL
根据指定数据获取该元素数据的地址：
LNode *LocateElem(LinkList L, ElemType e)
{// 在带头结点的单链表L中查找值为e的元素
p = L -> next; // 初始化，p指向首元结点
while (p && p -> data != e) // 顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p = p -> next; // p指向下一个结点
return p; // 查找成功返回值e的结点地址p，查找失败p为NULL
}根据指定数据获取该数据位置序号：
int LocateElem(LinkList L, ElemType e)
{//返回L中值为e的数据元素的位置序号，查找失败返回0
p = L -> next; j = 1;
while (p && p -> data != e) {
p = p -> next ;
j++;
}
if (p) return j;
else return 0;
}7、单链表的插入
- 将值为e的新结点插入到表的第i个结点的位置上，即插入到结点a~i-1~与a~i~之间
- 查找结点a~i-1~并由指针p指向该结点。
- 生成一个新结点*s
- 将新结点*s的数据域置为e，s -> data = e;
- 将新结点*s的指针域指向结点a~i~, s -> next = p -> next;
- 将结点*p的指针域指向新结点*s，p -> next = s;
Status ListInsert(LinkList L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
p = L; j = 0;
while (p && (j < i - 1)) {
p = p -> next; // 查找第i - 1个结点，p指向该结点
++j;
}
if (!p || j > i - 1) return ERROR; // i > n+1 或者 i < 1
s = new LNode; // 生成新结点*s
s -> data = e; // 将结点*s的数据域置为e
s -> next = p -> next; // 将结点*s的指针域指向结点ai
p -> next = s; // 将结点*p的指针域指向结点*s
return OK;
}8、单链表的删除
【算法步骤】：
- 删除单链表的第i个结点a~i~
- 查找结点a~i-1~并由指针p指向该结点
- 临时保存待删除结点a~i~的地址在q中，以备释放
- 将结点*p的指针域指向a~i~的直接后继结点
- 释放结点a~i~的空间
Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中，删除第i个元素
p = L; j = 0;
while ((p -> next) && (j < i - 1)) {
p = p > next; // 查找第i - 1个结点，p指向该结点
++j;
}
if (!(p -> next) || (j > i - 1)) return ERROR; // 当i > n 或 i < 1时删除位置不合理
q = p -> next; // 临时保存被删除结点的地址以备释放
p -> next = p -> next -> next; // 改变删除结点前驱结点的指针域
delete q; // 释放删除结点空间
return OK;
}9、单链表的建立（头插法）
- 创建一个只有头结点的空链表
根据带创建链表包括的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p;
- 输入元素赋值给新结点*p的数据域
- 将新结点*p插入到头结点之后
void CreateList_H(LinkList &L, int n)
{// 逆序位输入n个元素值，建立带头结点的单链表L
L = new LNode;
L -> next = NULL; // 先建立一个带头结点的空链表
for (i = n; i > 0; --i)
{
p = new LNode; // 生成新结点*p
cin >> p -> data; // 输入元素赋给新结点*p的数据域
p -> next = L -> next;
L -> next = p; // 将新结点*p插入到头结点之后
}
}4、单链表的建立（尾插法）
- 创建一个只有头结点的空链表
- 尾指针r初始化，指向头结点
根据创建链表包括的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p
- 输入元素值赋给新结点*p的数据域
- 将新结点*p插入到尾结点*r之后
- 尾指针r指向新的尾结点*p
void CretaeList_R(LinkList &L, int n)
{// 正位序输入n个元素值，建立带头结点的单链表L
L = new LNode;
L->next = NULL; // 先建立一个带头结点的空链表
r = L; // 尾指针r指向头结点
for (i = 0; i < n; ++i)
{
p = new LNode; // 生成新结点
cin >> p -> data; // 输入元素值赋给新结点*p的数据域
p -> next = NULL; r ->next = p; // 将新结点*p插入尾结点*r之后
r = p; // r指向新的尾结点
}
}2.4.4、循环链表
循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）
注意：
- 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件不再是==p或p->next是否为空==而是他们是否等于头指针
- 循环条件
头指针表示单循环链表
- 找a~1~的时间复杂度：$O(1)$
- 找a~n~的时间复杂度：$O(n)$
注意：表的操作常常是在表的首位位置上进行
尾指针表示单循环链表
- a~1~的存储位置是：R -> next -> next
- a~n~的存储位置是：R
- 带==尾指针循环链表的合并==（将T~b~合并在T~a~之后）
p =Ta -> next;
Ta -> next = Tb -> next -> next;
delete Tb -> next;
Tb -> next = p;
【算法描述】：
LinkList Connect(LinkList Ta, LinkList Tb)
{// 假设Ta、Tb都是非空的单循环链表
p = Ta -> next; // p存表头结点
Ta -> next = Tb -> next -> next; // Tb表头连结Ta表尾
delete Tb -> next; // 释放Tb表头结点
Tb -> next = p; // 修改指针
return Tb;
}2.4.5、双向链表
1、双向链表的结构定义如下：
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior; // 前驱指针
struct DuLNode *next; // 后继指针
}DuLNode, *DuLinkList;2、双向链表的插入
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{// 在带头结点的双向循环链表L中第i个位置之前插入元素e
if (!(p = GetElemP_DuL(L,i))) return ERROR;
s = new DuLNode;
s -> data = e;
s -> prior = p -> prior;
p -> prior -> next = s;
s -> next = p;
p -> prior = s;
return OK;
}3、双向链表的删除
算法描述：
Status ListDelete_DuL(DuLinkList &L, int i)
{// 删除带头结点的双向链表L中的第i个元素
if (!(p=GetElem_DuL(L,i))) // 在L中确定第i个元素的位置指针p
return ERROR; // p为NULL时，第i个元素不存在
p -> prior -> next = p -> next; // 修改被删结点的前驱结点的后继指针
p -> next -> prior = p -> prior; // 修改被删除结点的后继结点的前驱指针
delete p; // 释放被删结点的空间
return OK;
}单链表、循环链表和双向链表的时间效率比较
| 查找表头结点 （首元节点） |
查找表尾结点 | 查找结点*p的前驱结点 | |
|---|---|---|---|
| 带头结点的单链表L | L ->next 时间复杂度$O(1)$ |
从L -> next 依次向后遍历<br/>时间复杂度$O(n)$ | 通过p -> next无法找到其前驱 |
| 带头结点仅设尾指针L的循环单链表 | L ->next 时间复杂度$O(1)$ |
从L -> next 依次向后遍历<br/>时间复杂度$O(n)$ | 通过p -> next 可以找到其前驱时间复杂度$O(n)$ |
| 带头结点仅设尾指针R的循环单链表 | R ->next 时间复杂度$O(1)$ |
R<br/>时间复杂度$O(1)$ | 通过p -> next 可以找到其前驱时间复杂度$O(n)$ |
| 带头结点的双向循环链表L | L ->next 时间复杂度$O(1)$ |
L -> prior<br/>时间复杂度$O(1)$ | p -> prior<br/>时间复杂度$O(1)$ |
2.5、顺序表和链表的比较
链式存储结构的优点
- 结点空间可以动态申请和释放
- 数据元素的逻辑次序靠结点的指针来指示，即插入和删除时不需要移动数据元素。
链式存储结构的缺点
- 存储密度小，每个结点的指针域需要额外占用存储空间。
- 链式存储结构是非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点
- 存储密度 = 结点数据本身占用的空间/结点占用的空间总量
顺序表域链表的比较
