数据结构 第2章-2.3线性表的链式存储结构及其运算

计算机数据结构的课件。

2.3 线性表的链式存储结构及其运算一、单链表的存储结构 二、 单 链表的操作实现 三、链表的运算效率分析

计算机数据结构的课件。

2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的 邻接关系来表示结点间的逻辑关系，这一特点 使我们可以随机存取表中的任一结点，但它也 使得插入和删除操作会移动大量的结点.为避免 大量结点的移动，我们介绍线性表的另一种存 储方式， 链式存储结构，简称为链表(Linked List)。

计算机数据结构的课件。

2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性 表的结点， 特点：这组存储单元即可以是连续的，也可以是 不连续的，甚至是零散分布在内存中的任意位置 上的。链表中结点的逻辑次序和物理次序不一定 相同。 为了能正确表示结点间的逻辑关系，在存储每 个结点值的同时，还必须存储指示其后继结点的 地址(或位置)信息，这个信息称为指针 (pointer)或链(link)。这两部分组成了链表中 的结点结构： data link3

计算机数据结构的课件。

其中：data域是数据域，用来存放结点的值。 next是指针域(亦称链域),用来存放结点的直接 后继的地址(或位置)。 链表正是通过每个结点的链域将线性表的n个结 点按其逻辑次序链接在一起的。由于上述链表的每 一个结只有一个链域，故将这种链表称为单链表 (Single Linked)。

计算机数据结构的课件。

一、 单链表的存储结构1、单链式及表示方法 (1)单链表 构成链表的结点只有一个指向直接后继结点 单链表:构成链表的结点只有一个指向直接后继结点 单链表 的指针。其结构特点： 的指针。其结构特点：逻辑上相邻的数据元素在物理上 不一定相邻。 不一定相邻。 通过指针 指针来实现！ 指针 如何实现？ 让每个存储结点都包含两部分： 让每个存储结点都包含两部分：数据域和指针域

样式： 样式：

数据域

指针域

或

data

next

数据域： 数据域：存储 元素数值数据

指针域： 指针域：存储直接后继的 存储位置

设计思想：牺牲空间效率换取时间效率 设计思想：5

计算机数据结构的课件。

定义单链表结点的结构体如下: 定义单链表结点的结构体如下 typedef struct Node { DataType data; struct Node *next; }SLNode; 其中,data域用来存放数据元素,next域 其中,data域用来存放数据元素,next域用来存放指向下 一个结点的指针。 一个结点的指针。

计算机数据结构的课件。

链表存放示意图如下： 链表存放示意图如下： head a1 a2 …… an/\

请画出26个英文字母表的链式存储结构。 26个英文字母表的链式存储结构 例：请画出26个英文字母表的链式存储结构。 z) 该字母表的逻辑结构为： 解：该字母表的逻辑结构为：( a, b, … ,y, z)该字母表在内存中链式存放的样式举例如下： 该字母

表在内存中链式存放的样式举例如下：

指针域(链域 链域) 讨论1 每个存储结点都包含两部分： 讨论 ：每个存储结点都包含两部分：数据域和 指针域 链域 。 讨论2:在单链表中，除了首元结点外， 讨论 ：在单链表中，除了首元结点外，任一结点的存储位置 指示。 由 其直接前驱结点的链域的值 指示。7

计算机数据结构的课件。

(2) 与链式存储有关的术语： 与链式存储有关的术语： 1)结点：数据元素的存储映像。由数据域和指针域两部分组成； )结点：数据元素的存储映像。由数据域和指针域两部分组成； 2)链表： n 个结点由指针链组成一个链表。它是线性表的链 )链表： 个结点由指针链组成一个链表。 式存储映像，称为线性表的链式存储结构 称为线性表的链式存储结构。 式存储映像 称为线性表的链式存储结构 3)单链表、双链表、多链表、循环链表： )单链表、双链表、多链表、循环链表 结点只有一个指针域的链表，称为单链表或线性链表； 结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链表，称为双链表(但未必是双向链表); 有两个指针域的链表，称为双链表(但未必是双向链表); 有多个指针域的链表，称为多链表； 有多个指针域的链表，称为多链表； 首尾相接的链表称为循环链表。 首尾相接的链表称为循环链表。

循环链表示意图： 循环链表示意图： head a1 a2 …… an

head

计算机数据结构的课件。

4)头指针、头结点和首元结点的区别 )头指针、 示意图如下： 示意图如下： head info a1 a2 … an ^

头指针

头结点

首元结点

头指针是指向链表中第一个结点 或为头结点、 是指向链表中第一个结点( 头指针是指向链表中第一个结点(或为头结点、或为首元 结点)的指针； 结点)的指针； 头结点是在链表的首元结点之前附设的一个结点； 头结点是在链表的首元结点之前附设的一个结点；数据域 是在链表的首元结点之前附设的一个结点 内只放空表标志和表长等信息，它不计入表长度。 内只放空表标志和表长等信息，它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a 的结点。 首元结点是指链表中存储线性表第一个数据元素a0的结点。 是指链表中存储线性表第一个数据元素9

计算机数据结构的课件。

讨论1. 在链表中设置头结点有什么好处？ 在链表中设置头结点有什么好处？ 头结点即在链表的首元结点之前附设的一个结点， 即在链表的首元结点之前附设的一个结点 答：头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息， 表长度等附加信息 点的数据域可以为空，也可存放

表长度等附加信息，其作用是 数据域可以为空 为了对链表进行操作时，可以对空表、 为了对链表进行操作时，可以对空表、非空表的情况以及对首 元结点进行统一处理，编程更方便。 元结点进行统一处理，编程更方便。

讨论2. 如何表示空表？ 如何表示空表？ 答：无头结点时，当头指针的值为空时表示空表； 无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表。 有头结点时，当头结点的指针域为空时表示空表。 头指针^

头指针

头结点^

无头结点

有头结点

头结点不计入链 表长度！ 表长度！

计算机数据结构的课件。

2、带头结点单链表和不带头结点单链表的比较 一个线性表的逻辑结构为： 一个线性表的逻辑结构为： 例： ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG), ),其存储结构用 (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

答：头指针是指向链 表中第一个结点的指 针，因此关键是要寻 找第一个结点的地址。 找第一个结点的地址。H 31 ZHAO 7

的值是31 称：头指针H的值是 头指针 的值是

计算机数据结构的课件。

上例链表的逻辑结构示意图有以下两种形式： 上例链表的逻辑结构示意图有以下两种形式： 两种形式 H ①ZHAO ZHOU WU QIAN SUN ZHENG LI WANG/\

②

H ZHAO QIAN SUN LI

ZHOU

WU

ZHENG

WANG