数据结构第02章线性表B.pdfVIP

目录

第1章绪论

第2章线性表

第3章栈和队列

第4章串

第5章数组和广义表

第6章树和二叉树

第7章图

第9章查找

第10章排序

1

第2章线性表

第章线性表

2

2.1线性表的逻辑结构

2.1线性表的逻辑结构

2.2线性表的顺序表示和实现

2.2线性表的顺序表示和实现

2.3线性表的链式表示和实现

2.3线性表的链式表示和实现

2.4应用举例

2.4应用举例

2

2.3线性表的链式表示和实现

2.3线性表的链式表示和实现

2.3.1链表的表

2.3.2链表的实现

2.3.3链表的运算效率分析

3

2.3.1链表的表示

2.3.1链表的表示

(1)链式存储结构特点

其结点在存储器中的位置是随意的，即逻辑上

相邻的数据元素在物理上不一定相邻。

如何实现？通过指针来实现！

指针

让每个存储结点都包含两部分：数据域和指针域

数据指针或指针数据指针

样式：数据数据

数据域：存储指针域：存储直接后继或

元素数值数据者直接前驱的存储位置

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

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

4

链表存放示意图：

heada1a2……an/\

例：请画出26个英文字母表的链式存储结构。

例：请画出26个英文字母表的链式存储结构。

解：该字母表的逻辑结构为：（a,b,…,y,z）

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

指针域(链域)

讨论1：每个存储结点都包含两部分：数据域和。

讨论2：在单链表中，除了首元结点外，任一结点的存储位置

其直接前驱结点的链域的值

由指示。

5

(2)与链式存储有关的术语：

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

2）链表：n个结点由指针链组成一个链表。它是线性表的链式

存储映像，称为线性表的链式存储结构。

3）单链表、双链表、多链表、循环链表：

•结点只有一个指针域的链表，称为单链表或线性链表；

•有两个指针域的链表，称为双链表（但未必是双向链表）；

•有多个指针域的链表，称为多链表；

•首尾相接的链表称为循环链表。

循环链表示意图：

heada1a2……anhead