您的位置: 首页  >  文章  >  数据结构——线性表的链式表示和实现（链表总览）

数据结构——线性表的链式表示和实现（链表总览）

分类: 文章 • 2024-06-05 09:43:22

线性表的链式表示和实现

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像。

如何实现？

数据结构——线性表的链式表示和实现（链表总览）

相关术语

数据结构——线性表的链式表示和实现（链表总览）

  • 各结点由两个域组成：

    • 数据域：存储元素数值数据
    • 指针域：存储直接后继结点的存储位置

  • 结点：数据元素的存储映像。由数据域和指针域两部分组成

  • 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

  • 单链表、双链表、循环链表：
    结点只有一个指针域的链表，称为单链表或线性链表
    有两个指针域的链表，称为双链表
    首尾相接的链表称为循环链表

循环链表示意图：

数据结构——线性表的链式表示和实现（链表总览）

  • 头指针、头结点和首元结点
    数据结构——线性表的链式表示和实现（链表总览）
    头指针是指向链表中第一个结点的指针
    首元结点是指链表中存储第一个数据元素a1的结点
    头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息

上例链表的逻辑结构示意图有以下两种形式：

数据结构——线性表的链式表示和实现（链表总览）

问题讨论

如何表示空表？

有头结点时，当头结点的指针域为空时表示空表
数据结构——线性表的链式表示和实现（链表总览）

在链表中设置头结点有什么好处？

  1. 便于首元结点的处理
    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
  2. 便于空表和非空表的统一处理
    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
数据结构——线性表的链式表示和实现（链表总览）

链表（链式存储结构）的特点

（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

链表的优缺点

优点

  • 数据元素的个数可以*扩充
  • 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

缺点

  • 存储密度小
  • 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

free (a) 可利用存储空间
a0 a2 a1 a3 
free first
(b) 经过一段运行后的单链表结构
例如：画出26个英文字母表的链式存储结构
链式存储结构：
逻辑结构：（ a, b, … ,y, z）
head a b …… z /
各结点由两个域组成：
数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置
数据 指针
与链式存储有关的术语
1、结点：数据元素的存储映像。由数据域和指针域
两部分组成
2、链表：n个结点由指针链组成一个链表。它是线性
表的链式存储映像，称为线性表的链式存储结构。
head a1 a2 …… an head
循环链表示意图：
3、单链表、双链表、循环链表： • 结点只有一个指针域的链表，称为单链表或线性链表
• 有两个指针域的链表，称为双链表
• 首尾相接的链表称为循环链表
4、头指针、头结点和首元结点
头指针 头结点 首元结点
head info a1 a2 … an ^
头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素a1的结点
头结点是在链表的首元结点之前附设的一个结点；数据域内
只放空表标志和表长等信息
上例链表的逻辑结构示意图有以下两种形式
： ①
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG /
H ②
ZHAO QIAN SUN LI
ZHOU WU ZHENG WANG /
H
区别：① 无头结点 ② 有头结点
讨论1. 如何表示空表？
有头结点时，当头结点的指针域为空时表示空表
非空表 空表
head a0 an 0 head ^
表头结点
第一个结点
讨论2. 在链表中设置头结点有什么好处
？⒈便于首元结点的处理
首元结点的地址保存在头结点的指针域中,所以在链表的
第一个位置上的操作和其它位置一致，无须进行特殊处理; ⒉便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，
因此空表和非空表的处理也就统一了。
讨论3. 头结点的数据域内装的是什么？
头结点的数据域可以为空，也可存放线性表长度等
附加信息，但此结点不能计入链表长度值。
H
头结点的数据域
链表（链式存储结构）的特点
（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在
物理上不一定相邻
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域向
后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时
间不等
　这种存取元素的方法被称为顺序存取法
链表的优缺点
优点
Ø 数据元素的个数可以*扩充
Ø 插入、删除等操作不必移动数据，只需修改链
接指针，修改效率较高
链表的优缺点
缺点
•存储密度小
•存取效率不高，必须采用顺序存取，即存取数据元素时
，只能按链表的顺序进行访问（顺藤摸瓜）
2.5.1 单链表的定义和实现
非空表
空表
ü单链表是由表头唯一确定，因此单链表可以用头指针的
名字来命名
ü若头指针名是L，则把链表称为表L
typedef struct LNode{
ElemType data; // 数据域
struct LNode *next; // 指针域
}LNode,*LinkList; // *LinkList为Lnode类型的指针
单链表的存储结构定义
LNode *p LinkList p
data next
LNode p
注意区分指针变量和结点变量两个不同的概念
•指针变量p：表示结点地址
•结点变量p：表示一个结点
若p->data=ai, 则p->next->data=ai+1

2.5.2 单链表基本操作的实现
1、初始化
2、取值
3、查询
4、插入
5、删除
1.初始化(构造一个空表 ) 【算法步骤】 （1）生成新结点作头结点，用头指针L指向头结点。
（2）头结点的指针域置空。
【算法描述】
Status InitList_L(LinkList &L){
L=new LNode;
L->next=NULL; 　　　　
return OK;
}
p L a1 a2 …… ^
i 10 p p 2 p n ==NULL
an
求链表长度
p=L->next;
i=0;
while§{i++;p=p->next;}
“数”结点：
•指针p依次指向各个结点
•从第一个元素开始“数” • 一直“数”到最后一个结点
int ListLength_L(LinkList L){
//返回L中数据元素个数
LinkList p;
p=L->next; //p指向第一个结点
i=0;
while§{ //遍历单链表,统计结点数
i++;
p=p->next; }
return i;
}
“数”结点：
•指针p依次指向各个结点
•从第一个元素开始“数” • 一直“数”到最后一个结点
判断表是否为空
int ListEmpty(LinkList L){
//若L为空表，则返回1，否则返回0
if(L->next) //非空
return 0;
else
return 1;
}
2. 取值
（根据位置i获取相应位置数据元素的内容）
• 思考：链表里如何找到第i个元素？
• 链表的查找：
要从链表的头指针出发，顺着链域next逐个结点往下
搜索，直至搜索到第i个结点为止。因此，链表不是随
机存取结构。
L
21 18 30 75 42 56 ∧ j
i=3 i=5
例：分别取出表中i=3和i=5的元素
从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，
p初值p = L->next。 j做计数器，累计当前扫描过的结点数，j初值为1。 当p指向扫描到的下一结点时，计数器j加1。 当j = i时，p所指的结点就是要找的第i个结点。
【算法步骤】 p
//获取线性表L中的某个数据元素的内容
Status GetElem_L(LinkList L,int i,ElemType &e){
p=L->next;j=1; //初始化
while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空
p=p->next; ++j;
}
if(!p || j>i)return ERROR; //第i个元素不存在
e=p->data; //取第i个元素
return OK;
}
2. 取值
（根据位置i获取相应位置数据元素的内容）
ü从第一个结点起，依次和e相比较。
ü如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址; ü如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。 L
21 18 30 75 30 56 ∧
x=30
p p
找到，返回i
x=51
p p
未找到，返回0
3.查找
（根据指定数据获取数据所在的位置）
【算法描述】
//在线性表L中查找值为e的数据元素
LNode LocateELem_L (LinkList L，Elemtype e) {
//返回L中值为e的数据元素的地址，查找失败返回NULL
p=L->next;
while(p &&p->data!=e)
p=p->next;
return p;
}
【算法描述】
//在线性表L中查找值为e的数据元素
int LocateELem_L (LinkList L，Elemtype e) {
//返回L中值为e的数据元素的位置序号，查找失败返回0
p=L->next; j=1;
while(p &&p->data!=e)
{p=p->next; j++;}
if§ return j;
else return 0;
}
4. 插入（插在第 i 个结点之前）
• 将值为x的新结点插入到表的第i个结点的位置上，即插入
到ai-1与ai之间
s->next=p->next; p->next=s
思考：步骤4和5能互换么？
【算法步骤】 （1）找到ai-1存储位置p （2）生成一个新结点s （3）将新结点s的数据域置为x （4）新结点s的指针域指向结点ai （5）令结点p的指针域指向新结点s
//在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L;j=0;
while(p&&j<i−1){p=p->next;++j;} //寻找第i−1个结点
if(!p||j>i−1)return ERROR; //i大于表长 + 1或者小于1
s=new LNode; //生成新结点s
s->data=e; //将结点s的数据域置为e
s->next=p->next; //将结点s插入L中
p->next=s;
return OK;
}【算法描述】
5. 删除（删除第 i 个结点）
• 将表的第i个结点删去
• 步骤：
（1）找到ai-1存储位置p （2）保存要删除的结点的值
（3）令p-＞next指向ai的直接后继结点
（4）释放结点ai的空间
p->next = p->next->next ???
    ai-1
ai-1
ai ai ai+1
ai+1
p q
删除前
删除后
【算法步骤】 （1）找到ai-1存储位置p （2）临时保存结点ai的值在r中，以备释放
（3）令p->next指向ai的直接后继结点
（4）释放ai的空间
//将线性表L中第i个数据元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
p=L;j=0;
while(p->next &&j<i-1){ //寻找第i个结点，并令p指向其前驱
p=p->next; ++j;
}
if(!(p->next)||j>i-1) return ERROR; //删除位置不合理
q=p->next; //临时保存被删结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q; //释放删除结点的空间
return OK;
}【算法描述】
链表的运算时间效率分析

  1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，
    查找的时间复杂度为 O(n)。
  2. 插入和删除: 因线性链表不需要移动元素，只要修改指针，一般
    情况下时间复杂度为 O(1)。

但是，如果要在单链表中进行前插或删除操作，由于要从头查找
前驱结点，所耗时间复杂度为 O(n) 。
单链表的建立（前插法）
n 从一个空表开始，重复读入数据：
u 生成新结点
u 将读入数据存放到新结点的数据域中
u 将该新结点插入到链表的前端
void CreateList_F(LinkList &L,int n){
L=new LNode;
L->next=NULL; //先建立一个带头结点的单链表
for(i=n;i>0;–i){
p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;
L->next=p; //插入到表头
}
}【算法描述】
n 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表尾结点。
n 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点
插入到尾结点后，r指向新结点。
单链表的建立（尾插法）
void CreateList_L(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->next=NULL; r->next=p; //插入到表尾
r=p; //r指向新的尾结点
}
}【算法描述】

相关推荐