数据结构严蔚敏课件.docxVIP

数据结构严蔚敏ppt课件

数据结构（严蔚敏）版

●资料上传者：安徽大学研究生

●资料使用范围：各大学考研及本科教学●欢迎报考安徽大学研究生

●“星光考研书屋”祝您学习愉快

[学习目标]

掌握线性表的顺序存储结构和抽象数据类型中定义的每一种操作的含义，在顺序存储方式下

每一种操作的具体实现和相应的时间复杂度；

掌握链接存储的概念，线性表的单、双链接存储结构，对它们进行插入和删除结点的方法

，循环单、双链表和带表头附加结点的单、双

链表的结构和操作特点；

掌握每一种线性表操作在由动态结点构成的单链表上具体实现的算法以及相应的时间复杂度。

2

第2章线性表

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

①存在一个唯一的被称为“第一个”的数据元素；

②存在一个唯一的被称为“最后一个”的数据元素；

③除第一个元素外，每个元素均有唯一一个直接前

驱；

④除最后一个元素外，每个元素均有唯一一个直接

后继。

3

2.1线性表的逻辑结构

线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

当n=0时，称为空表。

当n0时，将非空的线性表记作：(a1，a2，…an)a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。2.1.1线性表的定义

4

a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱;

ai+1，ai+2，…an都是ai(1≦i≦n-1)的后继，其中ai+1是ai的直接后继。

2.1.2线性表的逻辑结构

线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。

◆线性表中的结点可以是单值元素(每个元素只有一

个数据项)。

例1:26个英文字母组成的字母表：(A，B，C、…、Z）

5

例2：某校从1978年到1983年各种型号的计算机拥有量

的变化情况：(6，17，28，50，92，188）

例3：一副扑克的点数(2，3，4，…，J，Q，K，A)

◆线性表中的结点可以是记录型元素，每个元素含

有多个数据项，每个项称为结点的一个域。每个元

素有一个可以唯一标识每个结点的数据项组，称为

关键字。

例4：某校2001级同学的基本情况：{(‘2001414101’，

‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’，08/12/1984)…，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}

◆若线性表中的结点是按值(或按关键字值)由小到

大(或由大到小)排列的，称线性表是有序的。6

2.1.3线性表的抽象数据类型定义ADTList{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R={|ai-1,ai∈D,i=2,3,…,n}基本操作：

InitList(L)

操作结果：构造一个空的线性表L；◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。

◆对线性表的数据元素可以访问、插入和删除。

7

ListEmpty(L)

初始条件：线性表L已存在；

操作结果：若L为空表，则返回TRUE，否则返回

FALSE；

….

GetElem(L,i,e)

初始条件：线性表L已存在，1≦i≦ListLength(L)；

操作结果：用e返回L中第i个数据元素的值；

ListInsert(L,i,e)

初始条件：线性表L已存在，1≦i≦ListLength(L)；

操作结果：在线性表L中的第i个位置插入元素e；

…

}ADTList8

2.2线性表的顺序存储

顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

顺序存储的线性表的特点：

◆线性表的逻辑顺序与物理顺序一致;◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

设有非空的线性表：(a1，a2，…an)。顺序存储如图

2-1所示。

2.2.1线性表的顺序存储结构9

Loc(a1)Loc(a1)+(i-1)*l

…a1a2…ai…an…

图2-1线性表的顺序存储表示

在具体的机器环境下：设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则有以下关系：

LOC(ai