else if(pa->data>pb->data)∥处理hb中数据 r=( Linkedlist) malloc( sizeof( L Node);∥/申请空间 r->data=pb->data; pre->next=r pre=r;∥将新结点链入结果链表 pb=pb->next;∥hb链表中工作指针后移 else∥/处理pa->data=pb->dat ipre->next=pa: pre=pa pa=pa->next;∥两结点数据相等时,只将ha的数据链入。 pb=pb->next;∥不要hb的相等数据 if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表 free(la);∥释放头结点.ha,hb指针未被破坏 }∥算法nion结束 2)本题与上面两题类似,要求结果指针为lc,其核心语句段如下: pa=la->next: pb=hb->next Ic=(LinkedList )malloc(sizeof(LNode)) pc=lc;∥pc是结果链表中当前结点的前驱 while(pa&&pb) if(pa->data<pb->data) Ipc->next=pa: pc=pa; pa=pa->next: I else [pc->next=pb; pc=pb; pb=pb->next: 1 if(pa)pc->next=pa; else pc->next=pb free(la);free(lb);∥释放原来两链表的头结点。 算法时间复杂度为0(m+n),其中m和n分别为链表1a和1b的长度。 2.[题目分析]本组题有6个,本质上都是链表的合并操作,合并中有各种条件。与前 组题不同的是,叙述上是用线性表代表集合,而操作则是求集合的并、交、差(AUB,A ∩B,A-B)等。 本题与上面1.(2)基本相同,不同之处1.(2)中链表是“非递减有序”,(可能包含 相等元素),本题是元素“递增有序”(不准有相同元素)。因此两表中合并时,如有元素值 相等元素,则应删掉一个。 LinkedList Union (LinkedList ha, hb) ∥线性表A和B代表两个集合,以链式存储结构存储,元素递增有序。ha和hb分别 是其链表的头指针。本算法求A和B的并集AUB,仍用线性表表示,结果链表元 素也是递增有序。 pa=ha->next;pb=hb->next;∥设工作指针pa和pb pc=ha;∥pc为结果链表当前结点的前驱指针 while(pa&&pb) if(pa->data<pb->data) (pc->next=pa: pc=pa; pa=pa->next: I lse if(pa->data>pb->data) Ipc->next=pb; pc=pb; pb=pb->next: I else∥处理pa-data=pb->data.else if(pa->data>pb->data)∥处理 hb 中数据。 {r=(LinkedList)malloc(sizeof(LNode));∥申请空间 r->data=pb->data; pre->next=r; pre=r;∥将新结点链入结果链表。 pb=pb->next;∥hb 链表中工作指针后移。 } else∥处理 pa->data=pb->data; {pre->next=pa; pre=pa; pa=pa->next;∥两结点数据相等时，只将 ha 的数据链入。 pb=pb->next;∥不要 hb 的相等数据 } if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。 else pre->next=pb; free(la);∥释放头结点.ha,hb 指针未被破坏。 }∥算法 nion 结束。 (2)本题与上面两题类似，要求结果指针为 lc，其核心语句段如下： pa=la->next;pb=hb->next; lc=(LinkedList )malloc(sizeof(LNode)); pc=lc;∥pc 是结果链表中当前结点的前驱 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;} if(pa)pc->next=pa; else pc->next=pb; free(la);free(lb);∥释放原来两链表的头结点。 算法时间复杂度为 O（m+n），其中 m 和 n 分别为链表 la 和 lb 的长度。 2．[题目分析]本组题有 6 个，本质上都是链表的合并操作，合并中有各种条件。与前 组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差（A∪B，A ∩B，A-B）等。 本题与上面 1．（2）基本相同，不同之处 1．（2）中链表是“非递减有序”，（可能包含 相等元素），本题是元素“递增有序”（不准有相同元素）。因此两表中合并时，如有元素值 相等元素，则应删掉一个。 LinkedList Union(LinkedList ha,hb) ∥线性表 A 和 B 代表两个集合，以链式存储结构存储，元素递增有序。ha 和 hb 分别 是其链表的头指针。本算法求 A 和 B 的并集 A∪B，仍用线性表表示，结果链表元 素也是递增有序。 { pa=ha->next;pb=hb->next;∥设工作指针 pa 和 pb。 pc=ha;∥pc 为结果链表当前结点的前驱指针。 while(pa&&pb) if(pa->data<pb->data) {pc->next=pa;pc=pa;pa=pa->next;} else if(pa->data>pb->data) {pc->next=pb;pc=pb;pb=pb->next;} else∥处理 pa->data=pb->data