第四讲 线性表（三） 1/.

Presentation on theme: "第四讲 线性表（三） 1/."— Presentation transcript:

1 第四讲 线性表（三） 1/

2 教学目标 掌握应用线性表的基本操作表示和实现一些更复杂的基本操作。 2/13

3 线性表的应用 线性表的合并 有序表的合并 1 2

4 线性表的合并 问题描述： 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合 A=AB
.

5 【算法步骤】 依次取出Lb 中的每个元素，执行以下操作： 在La中查找该元素 如果找不到，则将其插入La的最后
.

6 【算法描述】 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)) ListInsert(&La,++La_len,e); }

7 有序表的合并 问题描述： 已知线性表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) .

8 【算法步骤】－有序的顺序表合并 (1) 创建一个空表Lc
(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) .

9 【算法描述】－有序的顺序表合并 else *pc++=*pb++; } T(n)=
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素 LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和 LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间 pc=LC.elem; //指针pc指向新表的第一个元素 pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素 pb_last=LB.elem+LB.length-1; //指针pb_last指向LB表的最后一个元素 while(pa<=pa_last && pb<=pb_last){ //两个表都非空 if(*pa<=*pb) *pc++=*pa++; //依次“摘取”两表中值较小的结点 else *pc++=*pb++; } while(pa<=pa_last) *pc++=*pa++; //LB表已到达表尾 while(pb<=pb_last) *pc++=*pb++; //LA表已到达表尾 }//MergeList_Sq T(n)= S(n)= O(ListLength(LA)+ ListLength(LB))

10 有序链表合并－－重点掌握 将这两个有序链表合并成一个有序的单链表。 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。 表中允许有重复的数据。

11 有序链表合并－－重点掌握 La 1 7 8 Lb 2 4 6 8 10 11 La 1 2 4 6 7 8 10 11 合并后

12 【算法步骤】－有序的链表合并 (1)Lc指向La
(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 (4) 释放 Lb 表的表头结点

13 有序链表合并（初始化） La 1 7 8 Lc = pc pa Lb 2 4 6 8 10 11 pb

14 有序链表合并( pa->data < ＝pb->data )
La(Lc ,pc) 1 7 8 pa Lb 2 4 6 8 10 11 pb pc->next = pa;

15 有序链表合并( pa->data < ＝pb->data )
La(Lc) 1 1 7 8 Pc Pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa;

16 有序链表合并( pa->data < ＝pb->data )
La(Lc) 1 1 7 8 Pc pa = pa->next; Pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa;

17 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 Pc pa Lb 2 4 6 8 10 11 pb pc->next = pb;

18 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 Pc pc= pb; pb pc->next = pb;

19 有序链表合并( pa->data >pb->data )
La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 Pc pc= pb; pb =pb->next; pb pc->next = pb;

20 pc-> next=pa?pa:pb;
有序链表合并 La(Lc) 1 7 8 pa(NULL) 2 4 6 8 10 11 pc pb pc-> next=pa?pa:pb;

21 有序链表合并 合并后 La(Lc) 1 7 8 delete Lb; 2 4 6 8 10 11

22 【算法描述】－有序的链表合并 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; pc=Lc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb; pc=pb; pb=pb->next;} pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点} T(n)= S(n)= O(1)

23 思考：要求合并后的表无重复数据，如何实现？
La(Lc) 1 7 8 2 4 6 8 10 11 提示：要单独考虑 pa->data = =pb->data

24 作业 1. 已知集合A、B，求集合C=AUB算法，要求集合A、B和C均用采用链式和顺序存储结构表示。
2. 已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式和顺序存储结构表示。 实验一：线性表的基本操作及其应用 24/