数据结构-chap2 (2)单链表

2.3 线性表的链式存储和实现

2.3.1 线性链表 一 线性链表的概念

二 线性链表的基本操作算法

三 静态链表 四 线性链表的其它操作 2.3.2 循环链表 2.3.3 双向链表 一 双向链表的概念 二 双向链表的基本操作算法

2.3.1 线性链表

一、线性链表的概念 1、线性链表 用一组任意的存储单元存储线性表中的数据元素，对每个数据

元素除了保存自身信息外，还保存了直接后继元素的存储位置。

1010 1012 1014 1016 1018 1020 1022 1024 1026

a4 a3 a1

a2

NULL 1010

可以认为利用小的零散空间“串”起来，表示线性表 ，即把线性表的元素分散插入到系统所控制的零散空 间中，然后用“指针”串起来，组成一个有序的线性

1024 1014

表，用指针表示数据元素的逻辑关系。 元素的存储，可以是连续的，也可以不是连续的。 结点至少包括数据元素和指针两个区域。

2、线性链表结构图示

结点：数据元素及直接后继的存储位置组成一个数据元素的 存储结构，称为一个结点。

ai

链表

next

a1

next

a2

next

…

an

NULL

箭头：表示链域中的指针，即相应单元中保存的是它所指向结点的存储地址。

结点：数据元素及直接后继的存储位置组成一个数据元素的存储结构，

称为一个结点。

结点的数据域：结点中用于保存数据元素的部分。 结点的指针域：结点中用于保存数据元素直接后继存储地址的部分。 存储后继结点 地址 数据域 指针域

存储数据元素

结点

线性链表结点的类型定义

typedef struct LNode { ElemType data ；

struct LNode

} Lnode,

* next ；

* LinkList ；

a1

a2

ai-1

ai

ai+1

an n

自测题1

线性表的链接存储，表中元素的逻辑顺序与物理顺序一定 相同。（ ）

顺序表中逻辑上相邻的元素物理位置__________相邻，

单链表中逻辑上相邻的元素物理位置_________相邻。 顺序存储结构是通过______________________表示元素 之间的关系的；链式存储结构是通过________表示元素之间 的关系的。

3、线性链表有关术语

头指针：用于存放线性链表中第一个结点的存储地址。 空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针(NULL或0)。

头结点：线性链表的第一元素结点（首元结点）前面的一个附加结点。 带头结点的线性链表：第一元素结点前面增加头结点的线性链表。 L是头指针

L

a1

头结点

a2

ai-1

ai

ai+1

an n

空指针

带头结点的线性链表图示

自测题2

试述头指针、头结点、元素结点、首元结点的区别。

指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。“头指

针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如“链表 L

本文来源：https://www.bwwdw.com/article/r0l4.html