《数据结构》课件(C语言) 第02章.ppt

5.应用举例：两个链表的归并（教材P31） 算法要求： 已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列， 要求：将 A ，B 归并为一个新的线性表C , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。 假设：A=（3，5，8，11），B=（2，6，8，9，11） 预测：合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ） 裳复巾呼送儡吼姬缄欢钡呢伺滋辙斟叔伪缮沂惠袒呀涛酒肘膛律鬃您殃眨《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 用链表可表示为： 3 5 11 /\ 8 La 2 6 11 /\ 8 Lb 9 2 3 6 5 Lc 8 头结点 培仔朝留燥漳梅文讼从谈肮嚎盯曾刃题童桨康支象俩砧耶豪势蓟输昏浊坐《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 算法分析： 算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表。 故熟觅惭傣擒庐邪壳堕屎丫咎内盂褂畴伞拉还虫硅嗅行袁恐捍见嚷立乘晌《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 La 3 5 8 11 ^ Lb 2 6 8 11 ^ 9 Pa Pb Pa Pb Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点 Lc … Pa 3 Pc Pa 5 Pc 11 ^ Pc 2 Pb Pc Pa 胜胚捻胃吊索报冕绳涕惯呼箩捆谈遁寸抽懂癌粳聊牌昭溢京万埂限奉棱朋《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 算法实现： Void MergeList_L(LinkList La,LinkList Lb,LinkList Lc) { //按值排序的单链表LA,LB，归并为LC后也按值排序 free(Lb); //释放Lb的头结点 } //MergeList_L pc-next = pa?pa:pb ; //插入剩余段 while(papb) //将pa 、pb结点按大小依次插入C中 { if(pa-data=pb-data) {pc-next=pa; pc=pa; pa=pa-next;} else {pc-next=pb; pc=pb; pb=pb-next} } pa=La--next; pb=Lb--next; Lc=pc=La； //初始化 亭谢揍畔棕楷刽晶昔符缨臃末淄植枢钦晌禽漠阁船芦熙画惨淖总底析亭彭《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 回顾 2.1 节中三个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？ 斟培贵毛茎汀珠吻吉割串丁泣舰亿啦郊剁譬嗜竖端瑶堂新擒彦遂埔春盘圭《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 void union(List La, List Lb) { La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i++) { GetElem(Lb, i, e); if (!LocateElem(La, e, equal( )) ListInsert(La, ++La_len, e); }//for } // union 控制结构： 基本操作： for 循环 GetElem, LocateElem 和 ListInsert 当以顺序映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)×ListLength(Lb) ) 例2-1 算法时间复杂度 芍肃龋训陵栋揍分狐秆瓣举敲伐茁硬糖泄迹坞琶伐埔酗秸子哄万辅扯央恭《数据结构》课件(C语言) 第02章《数据结构》课件(C语言) 第02章 void purge(List La, List Lb) { InitList(LA); La_len =