循环链表双向链表ppt课件.ppt

《循环链表双向链表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主讲人：陈红丽知识点回顾单链表的定义与实现指针变量和结点变量的区别单链表基本操作的实现单链表的创建（2种方式）单循环链表双向链表对循环链表，有时不给出头指针，而给出尾指针，可以更方便的找到第一个和最后一个结点reara1ai-1anai如何查找开始结点和终端结点？开始结点：rear->next->next终端结点：rear双向链表结点priordatanext结点指向p->prior->next==p==p->next->priorp->priorp->nextppriornext双向链表的操作特点：“查询”和

2、单链表相同;“插入”和“删除”需要同时修改两个方向上的指针。插入ai-1aiesp先改变要插入的结点的指针域，再改变链表中结点的指针域。s->next=p->next;s->prior=p;p->next=s;s->next->prior=s;ai+1aiai-1删除q=p->next；p->next=q->next;p->next->prior=p;deleteq;q=NULL;qpai-12.6顺序表和链表的比较存储结构比较项目顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或

3、溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为O(1)适用情况①表长变化不大，且能事先确定变化的范围②很少进行插入或删除操作，经常按元素位置序号访问数据元素①长度变化较大②频繁进行插入或删除操作第6讲2.7线性表的应用线性表的合并有序表的

4、合并122.7.1线性表的合并问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=ABLa=(7,5,3,11)Lb=(2,6,3)La=(7,5,3,11,2,6).依次取出Lb中的每个元素，执行以下操作：在La中查找该元素如果找不到，则将其插入La的最后【算法步骤】voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);i

5、f(!LocateElem(La,e))ListInsert(&La,++La_len,e);}}【算法描述】算法时间复杂度：问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列.La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11)2.7.2有序表的合并(1)创建一个空表Lc(2)依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止(3)继续将L

6、a或Lb其中一个表的剩余结点插入在Lc表的最后【算法步骤】－有序的顺序表合并【算法描述】voidMergeList(OrderedListLa,OrderedListLb,OrderedList&Lc){//本算法将非递减的有序表La和Lb归并为Lc}//Merge_Listwhile((i<=La_len)&&(j<=Lb_len)){//La和Lb均不空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){//将ai插入到Lc中ListInsert(Lc,Lc.length+1,

7、ai);++i;}else{//将bj插入到Lc中ListInsert(Lc,Lc.length+1,bj);++j;}}InitList(Lc);//构造空的线性表Lci=j=1;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i<=La_len){//当La不空时GetElem(La,i++,ai);ListInsert(Lc,Lc.length+1,ai);}//插入La表中剩余元素while(j<=Lb_len){//当Lb不空时GetElem(Lb,j++,

8、bj);ListInsert(Lc,Lc.length+1,bj);}//插入Lb表中剩余元素算法时间复杂度：voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){i=1;j=1;//i和j分别指示两个表的第一个元素cLength=La.length+Lb.length;//新表长度为待合并两