北大数据结构与算法课件02线性表、栈和队列

第二章线性表、栈和队列信息科学与技术学院“数据结构与算法”教学小组北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3nextback大纲„2.1线性表(linearlist)„2.2顺序表—向量(Sequentiallist—vector)„2.3链表(Linkedlist)„2.4线性表实现方法的比较„2.5栈(Stack)„2.6队列(Queue)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4nextback线性结构分类线性结构目录索引型顺序访问型直接访问型向量记录散列表字典队列栈广义表顺序文件北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5nextback2.1线性表(linearlist)„„逻辑定义：逻辑定义：由结点集由结点集NN，以及定义在结点集，以及定义在结点集NN上的线性关系上的线性关系rr所组成的线性结构所组成的线性结构„„结点：线性表的元素结点：线性表的元素„„唯一的起点：没有前驱，有一个唯一的后继唯一的起点：没有前驱，有一个唯一的后继„„唯一的终点：有一个唯一的前驱而没有后继唯一的终点：有一个唯一的前驱而没有后继„„内部结点：有唯一的前驱，唯一的后继内部结点：有唯一的前驱，唯一的后继„„结点个数：线性表的长度结点个数：线性表的长度„„线性表的关系线性表的关系rr，简称前驱关系，简称前驱关系„„反对称性、传递性反对称性、传递性北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6nextbacktemplateclassELEMclasslist//线性表类模板list，模板参数ELEM{list();//创建一个空的新线性表~list();//从计算机存储空间删去整个线性表voidclear();//将该线性表的全部元素清除，成为空表voidappend(ELEMvalue);//尾附函数，在表尾加新元素voidinsert(inti,ELEMvalue);//插入函数，在第i号位插入voidremove(inti);//删除函数，删去第i号元素ELEMfetch(inti);//读取，返回第i个元素的值}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7nextback2.2顺序表—向量„采用定长的一维数组存储结构„主要特性:„元素的类型相同„元素顺序地存储在连续存储空间中„通过下标读写即可指定位置元素北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8nextback顺序表类定义constintMax_length=100;//假定昀大长度为100classlist{//顺序表，向量private:intmsize;//顺序表昀大长度intcurr_len;//顺序表当前长度ELEM*nodelist;//私有变量，存储顺序表实例的向量public://以下列出成员函数（顺序表的函数集)intcurr;//当前下标，顺序表的公共变量list(constintsize);//constructor函数,创建新表~list();//destructor函数，将该表实例删去voidclear();//清除内容，成为空表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9nextbackvoidsetFirst();//第一个元素位置赋予当前下标currvoidnext();//curr下移一格，即curr+1voidprev();//将curr上移一格，即curr-1boolisInList();//若curr位置有值时，返回truevoidappend(constELEM&);//在表尾增添新元素voidinsert(constELEM&);//在当前下标curr插入ELEMremove();//返回curr的位置元素值，并删除boolisEmpty();//当线性表为空时，返回trueELEMcurrValue();//返回curr位置的元素值。intlength();//返回此表的当前实际长度}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10nextbacknodelistnodelisti01tk-1msizei01tkmsizenodelistnodelisti01tk-2msizei01tk-1msize(a)在t位置插入元素item(b)删除t位置的元素北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11nextback插入算法执行时间„元素总个数为n，各个位置插入的概率相等为p＝1/n„平均移动元素次数为„总时间开销估计为O（n）n-1i01/(-)2nnni=•≈∑北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12nextback删除算法时间代价„与插入操作相似，O(n)„顺序表存取元素方便，时间代价为O(1)„但插入、删除操作则付出时间代价O(n)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13nextback2.3链表(linkedlist)„单链表„双链表„循环链表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14nextback„first指向特殊的头结点„引入头结点有利于特殊情况的处理„空链表„链表头„i按照C/C++数组下标编号的规则„从0到n-1„链表的第0个结点为first-link北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15nextback单链表的存储结构a0a1a2an-1firstlast单链表空的单链表firstlastdata字段link字段北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16nextback单链表结点类型以及变量说明structListNode{ELEMdata；ListNode*link;};typedefListNode*ListPtr;ListPtrfirst,last;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17nextback单链表插入算法//插入数据内容为value的新结点,为第i个结点。ListNode*Insert(ELEMvalue,inti){ListNode*p，*q;p=FindIndex(i-1);if(p==NULL)returnNULL;q=newListNode;//需要时才newq-link=p-link;q-data=value;p-link=q;if(q-link==NULL)last=q;returnq;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18nextback202310121515headcurrtail不带头结点20231215headcurrtail202312headfencetail带头结点15202312headfencetail10不带头结点vs带头结点北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19nextback//带头结点//不带头结点templateclassElemboolNHListElem::insert(constElem&item){if(head==NULL)head=curr=tail=newLinkElem(item,NULL);else{LinkElem*temp=head;if(temp==curr){head=newLinkElem(item,head);curr=head;}else{while(temp-next!=curr)temp=temp-next;temp-next=newLinkElem(item,curr);curr=temp-next;}}rightcnt++;returntrue;}templateclassElemboolLListElem::insert(constElem&item){fence-next=newLinkElem(item,fence-next);if(tail==fence)tail=fence-next;rightcnt++;returntrue;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20nextback2.3.2双链表(doublelinkedlist)„单链表的主要不足之处是：„link字段仅仅指向后继结点，不能有效地找到前驱„双链表弥补了上述不足之处„增加一个指向前驱的指针北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21nextback双链表示意图firstlasta0a1an-1双向链表北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22nextback双链表及其结点类型的说明structDblListNode{ELEMdata;DblListNode*rlink;DblListNode*llink;};structDoubleList{DblListNode*first，*last;};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23nextback插入过程（注意顺序）在p所指结点后面插入一个新结点pqq-rlink=p-rlinkq-llink=p(注意，教材p-rlink-llink)p-rlink=qq-rlink-llink=qnewq;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24nextback删除过程„如果马上删除p„则可以不赋空删除p所指的结点pp-llink-rlink=p-rlinkp-rlink-llink=p-llinkp-rlink=NULLp-llink=NULL北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25nextback2.3.3循环链表(circularlylinkedlist)„单链表或双链表的头尾结点链接起来„给不少操作带来了方便„从循环表中任一结点出发，都能访问到表中其他结点„不增加额外存储花销北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26nextback几种主要链表比较a0a1a2an-1firstlast单链表空的单链表firstlasta0a1a2an-1firstlast循环链表空的循环链表firstlastfirstlasta0a1an-1双向链表循环双向链表firstlasta0a1an-1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27nextback注意指针变量的有效性„记得使用new„使用新指针变量，或要生成一个新结点前先执行new操作„不要引用NULL指针„使用指针前，先用if语句（或while循环条件中的语句）判断它非空„不用引用Delete了的指针北京大学信息学院张铭编写©版权所有，转载或翻印必究Page28nextback注意链表的边界处理„几个特殊点的处理„头指针处理„非循环链表尾结点的指针域保持为NULL„循环链表尾结点的指针回指头结点„链表处理„空链表的特殊处理„插入或删除结点时指针勾链的顺序„指针移动的正确性„插入„查找或遍历北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29nextback2.4线性表实现方法的比较„顺序表的主要优点„没用使用指针，不用花费附加开销„线性表元素的读访问非常简洁便利„链表的主要优点„无需事先了解线性表的长度„允许线性表的长度有很大变化„能够适应经常插入删除内部元素的情况北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30nextback应用场合的选择„不要使用顺序表的场合„经常插入删除时，不宜使用顺序表„线性表的昀大长度也是一个重要因素„不要使用链表的场合„当读操作比插入删除操作频率大时，不应选择链表„当指针的存储开销，和整个结点内容所占空间相比其比例较大时，应该慎重选择北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31nextback2.5栈(stack)栈：限制访问端口的线性表LIFO表„Push：元素插入，‘压入’„Pop