辛运帏全套配套课件数据结构与算法 DSChapter03.ppt

《辛运帏全套配套课件数据结构与算法 DSChapter03.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性表3.1线性表的定义和基本运算3.2线性表的实现3.3线性表的应用3.1线性表的定义和基本运算为了引入线性表的概念，我们先举几个例子。例3.1（2，6，8，3，9，4）是一个线性表，其中的数据元素是整数，按表中列出的顺序排列，表中共有6个数据元素。例3.2（A，B，C，D，E，…，X，Y，Z）是一个线性表，其中的数据元素是英文大写字母，按字母表的顺序排列，共有26个数据元素。示例例3.3图3.1所表示的学生入学成绩表也是一个线性表。其中的数据元素是每个学生在表中所占的一行，包括姓名、准考证号、性别、年龄和总分等共5个数据项。通常把这种数据元素称为纪录。表中所列出的学生人数就

2、是表中数据元素的个数。姓名准考证号性别年龄总分陈义平030010023男18589陆东030010025男19568王晓敏030010037女18574┇┇┇┇┇李志强030010123男19617图3.1学生入学成绩表线性表的定义线性表一个线性表（list）是由同类型数据元素构成的有限序列，记作（a0,a1,…,an-1）。这个定义中强调两个特性，一个是强调每个数据元素ai（i=0，…，n-1）必须是同类型的数据，不能将不同类型的数据并列在一个线性表内。另一个是强调表中数据元素的有序性，也就是说每个元素在表中都有自己的位置术语当线性表中不包含任何元素时，称之为空表，记作（）。表中具

3、有元素的个数称为线性表的长度。线性表的第一个元素称为表头，最后一个元素称为表尾。对于表中第i个元素ai来说，第i-1个元素ai-1称为它的直接前趋（简称前趋），第i+1个元素ai+1称为它的直接后继（简称后继）。当然，表头没有直接前趋，表尾没有直接后继。下面就根据线性表的一组操作来定义该对象的抽象数据类型（ADT）。我们借助于C++的类（class）来描述线性表的抽象数据类型。这里ELEM类型表示线性表中数据元素所具有的任何数据类型。用户在实际应用中，可以用具体的数据类型来代替，如整型int，或用户自定义的复杂结构等。线性表类的ADTclasslist{//线性表类的ADTpubli

4、c:list(constintsz=LIST_SIZE);//构造函数~list()；//析构函数voidclear();//从表中清除所有元素voidinsert(constELEM&);//在当前位置插入一个元素ELEMremove()；//删除并返回当前元素的值voidsetFirst();//置光标于第一个位置voidprev();//移动光标到前一位置voidnext();//移动光标到下一位置intlength()const;//返回表的当前长度voidsetPos(constint);//置光标于指定位置voidsetValue(constELEM&);//置当前元素的

5、值ELEMcurrValue()const;//返回当前元素的值boolisEmpty()const;//如果表为空则返回TRUEboolisInList()const;//如果光标在表内则返回TRUEboolfind(constELEM&);//从当前位置开始找到某个值第一次出现的地方};3.2线性表的实现上一节提出的线性表的基本操作还是抽象的，如何具体实现这些操作首先依赖于线性表的存储结构。常用的存储结构有两种，分别是顺序存储结构和链式存储结构。3.2.1顺序存储结构基本思想用一组连续的存储单元依次存放线性表中各个元素。在C++表示中，只要用一个一维数组就可以了。但是，由于线性表

6、的长度可以改变，只用固定长度的数组是不足以表示线性表的实际情况的。因此，线性表的当前长度也必须要用一个整数来记录。顺序表把表中的元素存储在数组中相邻的位置，数组下标与线性表元素的位置相对应。换句话说，就是表中第i个元素存在数组的第i个位置。表头总是在第0个位置，这就使得对表中任意一个元素的随机访问非常容易。只要给出表中元素的序号，它在数组中对应的位置很容易确定，该元素的值就可以直接获取。因此用setPos()函数访问表中任一元素只需O(1)时间。既然顺序表把表中的元素存储在数组的相邻单元中，insert()和remove()函数就必须支持这个约定。在表尾插入和删除元素是比较容易的，只

7、需花费O(1)的时间。但是，如果我们想在表头插入一个元素，那么当前表中所有元素都必须向表尾方向移动一个位置以腾出空间（插入过程如图3.2所示）。平均说来，插入和删除要移动表中一半元素，即需要O(n)时间。示例插入27图3.2在顺序表的表头插入一个元素需要表中所有元素向表尾方向移动一个位置示意图115231960123456789115231960123456789(a)(b)27115231960123456789(c)顺序存储实现线性表类私有部分中包括了