第二讲线性表

第二讲线性表第1页，课件共40页，创作于2023年2月2课程内容逻辑结构线性表存储结构顺序表—向量链表典型运算第2页，课件共40页，创作于2023年2月32.1线性表线性表的抽象数据类型ADT线性表的存储结构线性表的典型操作第3页，课件共40页，创作于2023年2月4线性表的概念线性表定义：由有限结点集N，以及定义在结点集N上的线性关系r

所组成的线性结构。这些结点称为线性表的元素“地址相邻的顺序”和“指针指向相邻的顺序”线性表（N,r）的数学定义唯一的开始结点：没有前驱，但有一个唯一的直接后继唯一的终止结点：没有后继，但有一个唯一的直接前驱内部结点：有一个唯一的直接前驱，也有一个唯一的直接后继线性表的长度(包含的结点个数)为0的线性表称为空表线性表的关系r是前驱关系，应具有反对称性和传递性第4页，课件共40页，创作于2023年2月5举例开始节点（首结点）终止节点（尾结点）内部节点n2的前驱n1的后继长度为k要求：内部结点具有相同的数据类型

每个元素都有自己的位置第5页，课件共40页，创作于2023年2月6线性表运算分类list(-)：创建线性表的一个实例~list()：线性表消亡（即析构函数）获取有关当前线性表的信息

位置寻内容，内容找位置访问线性表并改变线性表的内容或结构插入、删除、更改等线性表的辅助性管理操作游标管理、当前长度管理第6页，课件共40页，创作于2023年2月7线性表ADTtemplate<classT>classList{//线性表类模板list，模板参数Tvoidclear();//置空线性表 boolisEmpty();//线性表为空返回true；voidappend(ELEMvalue)//表尾添加元素value，表长加1；voidinsert(intp,Tvalue);//在p处插入value，表长加1； voiddelete(intp); //删去第p元素，表的长度减1； boolgetPos(int&p,Tvalue)//查找value，并返回其位置； boolgetvalue(constintp,T&value);//把p位置的值返到value boolsetvalue(constintp,T&value);//用value修改p处值；}第7页，课件共40页，创作于2023年2月8线性表的存储结构定长的静态顺序存储结构又称为向量型的一维数组结构存储在连续的地址区域，随机访问，固定长度缺陷变长的动态线性存储结构链接式存储结构按照前驱关系通过指针将元素链接动态数组提供空间表管理，为长度变化提供方法，长度增大，可申请大空间顺序文件

为存储在磁盘上的线性表所用第8页，课件共40页，创作于2023年2月92.2顺序表—向量顺序表(Sequentiallist)，又称向量(Vector)采用定长的一维数组存储结构主要特性:元素的类型相同

元素顺序存储在连续存储空间中，每一个元素唯一的索引值（下标），读写元素方便使用常数作为向量长度，程序运行时保持不变第9页，课件共40页，创作于2023年2月10逻辑和存储结构第10页，课件共40页，创作于2023年2月11向量的类定义enumBoolean{False,True};constintMax_length=100;Template<classELEM>//假定顺序表的元素类型T为ELEMclasslist{//顺序表，向量private: intmsize;//私有变量，顺序表实例的最大长度 intcurr_len;//私有变量，顺序表实例的当前长度 ELEM*nodelist;//私有变量，存储顺序表实例的向量public: //以下列出成员函数（顺序表的算子集) intcurr;//当前下标，顺序表的公共变量 list(constintsize);//构造算子，实参是表实例的最大长度

~list();//析构算子，用于将该表实例删去第11页，课件共40页，创作于2023年2月12voidclear();//将顺序表存储的内容清除，成为空表 intlength();//返回此顺序表的当前实际长度 boolappend(constELEM&);//表尾增一新元素，表长加1 boolinsert(constELEM&);//在当前下标curr位置插入元素新值 booldelete(constintp);//删去位置p的元素，表长减1； boolsetValue(intp,constTvalue); //用value修改位置p的元素值 //把p位置的值返回到变量value中； boolgetvalue(constintp,T&value); //查找值为value的元素，并返回第1次出现的位置 boolgetPos(int&p,constTvalue); }第12页，课件共40页，创作于2023年2月13查找元素目的:查找某个位置的值或者某个值的位置 template<classT> //假定顺序表的元素类型为T boolarrList<T>::getPos(int&p,constTvalue){ inti;//元素下标 for(i=0;i<n;i++) //依次比较 if(value==aList[i]){ //下标为i的元素与value相等 p=i; //将下标由参数p返回 returntrue; } returnfalse;//顺序表没有元素值为value的元素 }第13页，课件共40页，创作于2023年2月14插入元素运算boolinsert(constintp,constTvlaue)在当前下标p=t位置插入元素新值valuecurr_len=k条件判断：1、当前下标[0，curr_len]；2、当前长度（<msize）第14页，课件共40页，创作于2023年2月15插入算法template<classT> //假定顺序表的元素类型为TboolarrList<T>::insert(intp,constTvalue){ inti; if(curLen>=maxSize) //检查顺序表是否溢出 returnfalse; if(p<0||p>curLen) //检查插入位置是否合法 returnfalse; for(i=curLen;i>p;i--) aList[i]=aList[i-1]; //从表尾curLen-1起往右移动直到p aList[p]=value; //位置p处插入新元素

curLen++;

//表的实际长度增1 returntrue;}第15页，课件共40页，创作于2023年2月16算法执行时间主要代价元素的移动元素总个数为n，各个位置插入的概率相等为p＝1/n

平均移动元素次数为总时间开销估计为O（n）第16页，课件共40页，创作于2023年2月17删除元素运算Delete(constintp)下标t位置值作为返回值，并删去该元素条件判断：1、当前下标[0，curr_len）；2、当前长度（>0）第17页，课件共40页，创作于2023年2月18删除算法template<classT> //顺序表的元素类型为TboolarrList<T>::delete(intp){inti;if(curLen<=0) //检查顺序表是否为空 returnfalse;if(p<0||p>curLen-1)//检查删除位置是否合法 returnfalse;for(i=p;i<curLen-1;i++)aList[i]=aList[i+1]; //从位置p开始每个元素左移直到curLen,curLen--; //表的实际长度减1returntrue;}第18页，课件共40页，创作于2023年2月19算法时间代价与插入操作相似，O(n)

顺序表读取元素方便，时间代价为O(1)但插入、删除操作则付出时间代价O(n)

第19页，课件共40页，创作于2023年2月202.3链表(LinkedList)链表(linkedlist)指针指向保持前驱关系，节点不必物理相邻动态申请/释放空间适合节点的动态的插入/删除，长度变化无常链接存储方法在非线性结构（如树、图）中的应用分类单链表双链表循环链表第20页，课件共40页，创作于2023年2月21单链表结点类型以及变量说明structListNode{ ELEMdata；//存放线性表结点的数据; ListNode*next;//存放指向后继结点的指针；};typedefListNode*ListPtr;ListPtrhead,tail; //head指向单链表开始结点的指针；//tail指向单链表尾结点的指针，指针域null；第21页，课件共40页，创作于2023年2月22运算集查找算法查找单链表中第i个结点算法插入算法插入数据内容为value的新结点，为第i个结点。删除算法删除由参数link所指定的结点求长度算法求单链表中元素的个数第22页，课件共40页，创作于2023年2月23单链表(Con.)HeaderNode不被作为表中的实际元素，值忽略head指向该节点访问必须从head开始查找链表中的元素第23页，课件共40页，创作于2023年2月24链表检索//函数返回值是找到的结点指针template<classT> //线性表的元素类型为TLink<T>*lnkList<T>::setPos(inti){ intcount=0;if(i==-1)returnhead; //i为-1则定位到头结点 Link<T>*p=head->next; while(p!=NULL&&count<i){//若i为0则定位到第1个结点 p=p->next; count++;};returnp;//指向第i结点，i＝0,1,…n-1,当链表中结点数小于i时返回NULL}第24页，课件共40页，创作于2023年2月25插入过程描述pqp＝setPos(i-1)q＝newListNode……pq……pq……q->next=p->nextp->next=q第25页，课件共40页，创作于2023年2月26插入算法ListNode*Insert(ELEMvalue,inti){ ListNode*p，*q; q=newListNode;//产生一个新结点空间q p=setPos(i-1);//找到待插位置的前一个位置p if(p==NULL)returnNULL;q->next=p->next; q->data=value;

p->next=q; if(q->next==NULL) last=q; //当插入元素是最后位置时维护尾指针 returnq;}

指针调整过程第26页，课件共40页，创作于2023年2月27删除结点过程描述

x

ppnext=dnext;dd=pnext;free(d)P节点不能不存在或者为尾节点！！第27页，课件共40页，创作于2023年2月28删除算法template<classT> //线性表的元素类型为TboollnkList<T>::delete((constinti){ Link<T>*p,*d; if((p=setPos(i-1))==NULL||p==tail){//待删结点不存在; cout<<"非法删除点"<<endl;returnfalse; } d=p->next; //d是真正待删结点 if(d==tail){ //待删结点为尾结点，则修改尾指针 tail=p; p->next=NULL: deleted; } else{p->next=d->next;deleted;}//删除结点d并修改链指针 returntrue;}第28页，课件共40页，创作于2023年2月29求长度算法intlength(){ Link<T>*p=head->next; intcount=0; while(p!=NULL){ p=p->next; count++; } returncount;}

第29页，课件共40页，创作于2023年2月30思考题：为什么引入头节点？有利于对空链表进行操作或者在链表表头进行操作等特殊情况的处理。例如单链表为空时的插入；单链表被删除为空表时的处理；插入作为表的第一个节点；删除表的第一个节点第30页，课件共40页，创作于2023年2月31单链表分析单链表的主要不足之处link字段仅仅指向后继结点，不能有效地找到前驱双链表弥补了上述不足之处增加一个指向前驱的指针第31页，课件共40页，创作于2023年2月32双链表类型说明structDblListNode{ ELEMdata;

DblListNode*prev; DblListNode*next;};

structDoubleList{ DblListNode*head，*tail;};指向前驱结点指向后继结点datanextprev第32页，课件共40页，创作于2023年2月33删除结点示意图删除p所指的结点setPos(i)pp->prev->next=p->next;p->next->prev=p->prev;pp->prev=NULL;p->next=NULL;p^^free(p)第33页，课件共40页，创作于2023年2月34插入结点示意图在p所指结点后插入一个新的结点setPos(i-1)pq->next=p->next;q->prev=p;qpp->