搜索
数据结构与算法第2章线性表本章由赵海燕主写北京大学张铭，王腾蛟，赵海燕高等教育出版社，2012.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;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6删除算法时间代价与插入操作相似，主要的代价在于元素的移动等概率情况下平均时间代价为O(k