第2章 线性表.ppt

《第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表线性表是最简单、最基本、最常用的一种线性结构。线性表具有以下特点：具有唯一的第一个数据元素和唯一的最后一个数据元素。除第一个和最后一个数据元素，其他外数据元素有且只有一个直接前驱和一个直接后继。线性表的存储结构有两种：顺序存储和链式存储。2.1线性表的概念及抽象数据类型2.1.1线性表的定义一个线性表由有限个类型相同的数据元素组成，数据元素构成一个有序的序列，除了第一个元素和最后一个元素外，其他元素有唯一的直接前驱和唯一的直接后继。线性表的逻辑结构如图2.1所示。2.1线性表的概念及抽象数据类型例如，英文字母表(A，B，…，Z)就是一个简单的线性表，表中的每一个英文字母就是一个数

2、据元素，每个元素之间存在唯一的顺序关系，在英文字母表中字母B前面是字母A，而字母B后面是字母C。在较为复杂的线性表中，数据元素可由若干个数据项构成，例如，表1.1所示的学生成绩表中，每个学生的成绩是由学号、姓名、性别、语文、数学、英语等数据项组成，常常被称为一个记录或数据元素。2.1线性表的概念及抽象数据类型综上所述，线性表可定义为：线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记作(a1,a2,…,ai-1,ai,ai+1,…,an)其中，n为表长。这里的数据元素可以是原子类型也可以是结构类型。表中相邻元素之间存在着顺序关系，ai-1领先于ai，将ai-1称为ai的直接前

3、驱，ai称为ai-1的直接后继。除了第一个元素a1外，每个元素ai有且只有一个被称为直接前驱的元素ai-1；除了最后一个元素an外，每个元素ai有且只有一个被称为直接后继的元素ai+1。当n＝0时线性表被称为空表。2.1线性表的概念及抽象数据类型2.1.2线性表的抽象数据类型线性表的抽象数据类型包括数据对象集合和基本操作集合。其中，数据对象集合定义了线性表的数据元素及元素之间的关系，基本操作集合定义了在该数据对象上的一些基本操作。1.数据对象集合线性表的数据对象集合可以表示为{a1,a2,…,an}，每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前

4、驱，除了最后一个元素an外，每一个元素有且只有一个直接后继。2.1线性表的概念及抽象数据类型2.基本操作集合线性表的基本操作主要以下几个。(1)InitList(&L)初始条件：表L不存在。操作结果：构造一个空的线性表。(2)ListEmpty(L)初始条件：表L已经存在。操作结果：如果线性表L为空，返回1，否则返回0。(3)ListLength(L)初始条件：表L已经存在。操作结果：返回线性表L的元素个数。2.1线性表的概念及抽象数据类型(4)GetElem(L,i,&e)初始条件：表L已经存在，且i值合法，即1≤i≤ListLength(L)。操作结果：返回表L中的第i个位置的元素值给e

5、。(5)LocateElem(L,e)初始条件：表L已经存在，且e为合法元素值。操作结果：如果线性表L中存在数据元素e，则返回在表L中首次出现元素值e的序号或地址表示成功；否则，返回-1表示失败。(6)InsertList(&L,i,e)初始条件：表L已经存在，e为合法元素且1≤i≤ListLength(L)。操作结果：在表L中的第i个位置插入新元素e。(7)DeleteList(&L,i,&e)初始条件：表L已经存在且1≤i≤ListLength(L)。操作结果：删除表L中的第i个位置，用e返回其值，L的长度减1。(8)ClearList(&L)初始条件：表L已经存在。操作结果：表L被置为

6、空。2.2线性表的顺序存储及实现线性表的存储结构主要有两种：顺序存储结构和链式存储结构。2.2.1顺序表线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。假设线性表有n个元素，每个元素占用m个存储单元，如果第一个元素的存储位置记为LOC(a1)，则第i个元素的存储位置记为LOC(ai)，第i个元素的存储位置记为LOC(ai)，第i+1个元素的存储位置记为LOC(ai+1)。2.2线性表的顺序存储及实现第i个元素和第i+1个元素满足以下关系：LOC(ai+1)=LOC(ai)+m线性表的第i个元素的存储位置与第一个元素a1的存储位

7、置满足以下关系：LOC(ai)=LOC(a1)+(i-1)*m其中，第一个元素的位置LOC(a1)称为起始地址或基地址。顺序表是一种随机存取的存储结构。只要知道顺序表的其中一个元素的存储地址，就可以得到顺序表中任何一个元素的存储地址。顺序表的存储结构如图2.2所示。2.2线性表的顺序存储及实现在C语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，我们采用数组描述线性表的顺序存储结构。线性表的