2-数据结构与算法-北京大学2008-张铭-线性表

数据结构与算法第2章线性表本章由赵海燕主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6主要内容线性结构顺序表链表线性表实现方法的比较“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构元素间满足线性关系“一对一”的关系按此关系结构中的所有元素排成一个线性序列二元组B=(K,R),K={a0,a1,…,an-1},R={r}：结点集K中有一个唯一的开始结点，它没有前驱，但有一个唯一的后继；对于有限集K,它存在一个唯一的终止结点，该结点有一个唯一的前驱而没有后继；其它的结点皆称为内部结点，每一个内部结点都有且仅有一个唯一的前驱，也有一个唯一的后继；a0,a1,…,an-1ai,ai+1ai是ai+1的前驱，ai+1是ai的后继“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构特点：均匀性：虽然不同线性表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度有序性：各数据元素在线性表中都有自己的位置，且数据元素之间的相对位置是线性的“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构包括：简单的•线性表•栈•队列•散列表高级的•广义表•多维数组•文件……“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构分类按访问方式划分直接访问型(directaccess)顺序访问型(sequentialaccess)目录索引型(directoryaccess)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性结构分类按操作划分线性表•所有表目都是同一类型结点的线性表•不限制操作形式•根据存储的不同分为：顺序表，链表栈(LIFO,LastInFirstOut)•插入和删除操作都限制在表的同一端进行队列(FIFO,FirstInFirstOut)•插入操作在表的一端，删除操作在另一端“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.62.1线性表(linearlist)三个方面线性表的逻辑结构线性表的存储结构线性表运算分类“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表的逻辑结构线性表：由称为元素（element）的数据项组成的一种有限且有序的序列，这些元素也可称为结点或表目二元组(K,r)：由结点集K，以及定义在结点集K上的线性关系r所组成的线性结构线性表所包含的结点个数称为线性表的长度，它是线性表的一个重要参数；长度为0的线性表称为空表；线性表的关系r，简称前驱/后继关系，具有反对称性和传递性“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表逻辑结构主要属性包括：线性表的长度表头(head)表尾(tail)当前位置(currentposition)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表的存储结构定长的一维数组结构又称为向量型的顺序存储结构变长的线性表存储结构链接式存储结构串结构、动态数组、以及顺序文件“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表的存储结构顺序表按索引值从小到大存放在一片相邻的连续区域紧凑结构，存储密度为1链表单链表双链表循环链表………..“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表运算分类创建线性表的一个实例list(-)清除线性表（即析构函数）~list()获取有关当前线性表的信息访问线性表并改变线性表的内容或结构线性表的辅助性管理操作“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表的运算建立线性表清除线性表插入一个新元素删除某个元素修改某个元素排序检索“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6线性表类模板templateclassTclassList{voidclear();//置空线性表boolisEmpty();//线性表为空时，返回trueboolappend(constTvalue);//在表尾添加一个元素value，表的长度增1boolinsert(constintp,constTvalue);//在位置p上插入一个元素value，表的长度增1booldelete(constintp);//删除位置p上的元素，表的长度减1boolgetPos(int&p,constTvalue)//查找值为value的元素并返回其位置boolgetValue(constintp,T&value);//把位置p的元素值返回到变量value中boolsetValue(constintp,constTvalue);//用value修改位置p的元素值boolgetPos(int&p,constTvalue);//把值为value的元素所在位置返回到变量p中};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.62.2顺序表（array-basedlist）采用定长的一维数组存储结构也称向量主要特性:元素的类型相同元素顺序地存储在连续存储空间中，每一个元素有唯一的索引值使用常数作为向量长度“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序表数组存储读写其元素很方便，通过下标即可指定位置只要确定了首地址，线性表中任意数据元素都可以随机存取。地址计算如下所示：loc(ki)=loc(k0)+c*ic=sizeof(ELEM)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序表逻辑地址(下标)数据元素存储地址数据元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序表类定义classarrList:publicListT{//顺序表，向量private://线性表的取值类型和取值空间T*aList;//私有变量，存储顺序表的实例intmaxSize;//私有变量，顺序表实例的最大长度intcurLen;//私有变量，顺序表实例的当前长度intposition;//私有变量，当前处理位置public://顺序表的运算集arrList(constintsize){//创建一个新的顺序表，参数为表实例的最大长度maxSize=size;aList=newT[maxSize];curLen=position=0;}~arrList(){//析构函数，用于消除该表实例delete[]aList;}voidclear(){//将顺序表存储的内容清除，成为空表delete[]aList;curLen=position=0;aList=newT[maxSize];}}intlength();//返回此顺序表的当前实际长度boolappend(constTvalue);//在表尾添加一个元素value，表的长度增1boolinsert(constintp,constTvalue);//在位置p上插入一个元素value，表的长度增1booldelete(constintp);//删除位置p上的元素，表的长度减1boolsetValue(constintp,constTvalue);//用value修改位置p的元素值boolgetValue(constintp,T&value);//把位置p的元素值返回到变量value中boolgetPos(int&p.constTvalue);//查找值为value的元素，并返回第1次出现的位置};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6顺序表上的运算重点讨论插入元素运算•boolinsert(constintp,constTvalue);删除元素运算•booldelete(constintp);其他运算请大家思考……“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6positionk0k1k2k6k5k4k3k0k1k2k6k5k4k3k0k1k2k6k5k4k3x顺序表的插入图示positionposition“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6插入算法//设元素的类型为T，aList是存储顺序表的数组，maxSize是其最大长度；//p为新元素value的插入位置，插入成功则返回true，否则返回falsetemplateclassTboolarrListT::insert(constintp,constTvalue){inti;if(curLen=maxSize){//检查顺序表是否溢出coutThelistisoverflowendl;returnfalse;}if(p0||pcurLen){//检查插入位置是否合法coutInsertionpointisillegalendl;returnfalse;}for(i=curLen;ip;i--)aList[i]=aList[i-1];//从表尾curLen-1起往右移动直到paList[p]=value;//位置p处插入新元素curLen++;//表的实际长度增1returntrue;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6插入算法的执行时间插入操作的主要代价体现在表中元素的移动k-1i01/(-)2kkki在位置i插入元素，需移动n-i个元素•元素总个数为k，假设各个位置插入的概率相等，为p＝1/k•平均移动元素次数为总时间开销估计为O(k)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6positionk0k1k2k3k4k5k6k0k1k2k4k5k6顺序表的删除图示position“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6删除算法//设元素的类型为T；aList是存储顺序表的数组；p为即将删除元素的位置//删除成功则返回true，否则返回falsetemplateclassT//顺序表的元素类型为TboolarrListT::delete(constintp){inti;if(curLen=0){//检查顺序表是否为空coutNoelementtodelete\nendl;returnfalse;}if(p0||pcurLen-1){//检查删除位置是否合法coutdeletionisillegal\nendl;returnfalse;}for(i=p;icurLen-1;i++)aList[i]=aList[i+1];//从位置p开始每个元素左移直到curLencurLen--;//表的实际长度减1returntrue;}“十一五”国家级规划教材。张铭，王腾蛟