北京大学课件数据结构与算法ds02listcol

《北京大学课件数据结构与算法ds02listcol》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表、栈和队列张铭赵海燕王腾蛟http://db.pku.edu.cn/mzhang/DS/北京大学信息科学与技术学院“数据结构与算法”教学小组©版权所有，转载或翻印必究大纲¢2.1线性表(linearlist)¢2.2顺序表—向量(sequentiallist—vector)¢2.3链表(linkedlist)¢2.4线性表实现方法的比较¢2.5栈¢2.6队列北京大学信息学院©版权所有，转载或翻印必究Page2线性结构分类线性结构直接访问型顺序访问型目录索引型向量记录字典散列表顺序文件广义表栈队列北京大学信息学院©版权所有，转载或翻印必究Page3

2、2.1线性表(linearlist)¢2.1.1线性表的抽象数据类型¢2.1.2线性表的存储结构¢2.1.3线性表运算分类北京大学信息学院©版权所有，转载或翻印必究Page4线性表的抽象数据类型¢线性表定义：¢由结点集N，以及定义在结点集N上的线性关系r所组成的线性结构。这些结点称为线性表的元素。北京大学信息学院©版权所有，转载或翻印必究Page5线性表的性质¢线性表（N,r）：¢（a）结点集N中有一个唯一的开始结点，它没有前驱，但有一个唯一的后继；¢（b）对于有限集N,它存在一个唯一的终止结点，该结点有一个唯一的前驱而没有后继；¢（c）其它的结点皆称为内部

3、结点，每一个内部结点既有一个唯一的前驱，也有一个唯一的后继；北京大学信息学院©版权所有，转载或翻印必究Page6线性表的性质（续）¢线性表（N,r）：¢（d）线性表所包含的结点个数称为线性表的长度，它是线性表的一个重要参数；长度为0的线性表称为空表；¢（e）线性表的关系r，简称前驱关系，应具有反对称性和传递性。北京大学信息学院©版权所有，转载或翻印必究Page7线性表的抽象数据类型¢取值空间¢运算集北京大学信息学院©版权所有，转载或翻印必究Page8线性表类模板templateclasslist//线性表类模板list，模板参数ELEM

4、{//1.线性表的取值类型：//元素的类型为ELEM，是本list类模板的模板//参数ELEM。//本线性表用的最大长度为Max_length；北京大学信息学院©版权所有，转载或翻印必究Page9//2.运算集：请参看下面的成员函数private://私有变量，线性表的存储空间//Max_length用于规定所存储线性表的最大长度public:intcurr_len;//公共变量，该线性表的当前长度intcurr;//公共变量，该线性表的当前指针，游标list();//constructor算子，创建一个空的新线性表北京大学信息学院©版权所有，转载或翻印必究

5、Page10//destructor算子,//从计算机存储空间删去整个线性表~list();//将该线性表的全部元素清除，成为空表voidclear();//尾附算子，在表的尾部添加一个新元素，参//数value作为元素内容（数据类型为//ELEM），表的长度加1voidappend(ELEMvalue);北京大学信息学院©版权所有，转载或翻印必究Page11//插入算子，整数i指出第i号位置，参数value//作为元素内容（数据类型为T），该位置上//插入一个新结点，表的长度加1。第i号位置后//的元素后移voidinsert(inti,ELEMvalue

6、);//删除算子，删去第i号元素，表的长度减1，其//后元素前移voidremove(inti);//读取，返回第i个元素的值ELEMfetch(inti);}北京大学信息学院©版权所有，转载或翻印必究Page122.1.2线性表的存储结构¢定长的一维数组结构¢又称向量型的顺序存储结构¢变长的线性表存储结构¢链接式存储结构¢串结构、动态数组、以及顺序文件北京大学信息学院©版权所有，转载或翻印必究Page132.1.3线性表运算分类¢创建线性表的一个实例list(-)¢线性表消亡（即析构函数）~list()¢获取有关当前线性表的信息¢访问线性表并改变线性表的内

7、容或结构¢线性表的辅助性管理操作北京大学信息学院©版权所有，转载或翻印必究Page142.2顺序表—向量¢采用定长的一维数组存储结构¢主要特性:¢元素的类型相同¢元素顺序地存储在连续存储空间中，每一个元素唯一的索引值¢使用常数作为向量长度北京大学信息学院©版权所有，转载或翻印必究Page152.2.1向量的类定义¢数组存储¢读写其元素很方便，通过下标即可指定位置北京大学信息学院©版权所有，转载或翻印必究Page16顺序表类定义enumBoolean{False,True};//假定最大长度为100//并假定顺序表的元素类型T为ELEMconstintMax_

8、length=100;classlist{//顺序表