∥A,B和C均是带头结点的递增有序的单链表,本算法实现A=AU(B∩C),使求解结 构保持递增有序 pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针 pre=A;∥pre指向结果链表中当前待合并结点的前驱。 if(pa->data<pb-> datal lpa->data<pc-data)∥A中第一个元素为结果表的第一元 素 else while(pb&&pc) ∥找B表和C表中第一个公共元素。 if(pb->data<pc->data)pb=pb->next else if (pb->data)pc->data)pc=pc->next else break;∥找到B表和C表的共同元素就退出 while循环 if(pb&&pc)∥因共同元素而非B表或C表空而退出上面 while循环。 if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素,先将B 表元素链入 pre->next=pb;pe=pb;pb=pb->next;pc=pc->next;}∥B,C公共元素为结果 表第一元素。 }∥结東了结果表中第一元素的确定 while(pa&&pb&& Iwhile(pb&&pc) if(pb->data<pc->data) pb=pb->next else if(pb->data>pc->data)pc=pc->next else break;∥B表和C表有公共元素。 if(pb&&pc) while(pa&&pa->data<pb->data)∥先将A中小于B,C公共元素部分链入。 (pre->next=pa pre=pa; pa=pa->next; 1 if(pre->data!=pb->data)pre->next=pb; pre=pb; pb=pb->next: pc=pc->next: K ese{pb=pb->next;pc=pc->next;}∥若A中已有B,C公共元素,则不再存 入结果表 }∥ while(pa&pb&pc) if(pa)pre-next=pa;∥当B,C无公共元素(即一个表已空),将A中剩余链入。 }∥算法 Union结東 [算法讨论]本算法先找结果链表的第一个元素,这是因为题目要求结果表要递増有序 (即删除重复元素)。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A (头结点的头指针),这时的data域无意义,不能与后继比较元素大小,因此就需要确定第 一个元素。当然,不要这样作,而直接进入下面循环也可以,但在链入结点时,必须先判断 pre是否等于A,这占用了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为0(A|+|B|+C)。这就要求各个表的工作指 针只能后移(即不能每次都从头指针开始査找)。本算法满足这一要求 最后一个问题是,当B,C有一表为空(即B和C已无公共元素时),要将A的剩余部分 链入结果表。 3.[题目分析]循环单链表L1和L2数据结点个数分别为m和n,将二者合成一个循环 单链表时,需要将一个循环链表的结点(从第一元素结点到最后一个结点)插入到另一循环∥A,B 和 C 均是带头结点的递增有序的单链表，本算法实现 A= A∪（B∩C），使求解结 构保持递增有序。 {pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。 pre=A; ∥pre 指向结果链表中当前待合并结点的前驱。 if(pa->data<pb->data||pa->data<pc->data)∥A 中第一个元素为结果表的第一元 素。 {pre->next=pa;pre=pa;pa=pa->next;} else{while(pb&&pc) ∥找 B 表和 C 表中第一个公共元素。 if(pb->data<pc->data)pb=pb->next; else if(pb->data>pc->data)pc=pc->next; else break; ∥找到 B 表和 C 表的共同元素就退出 while 循环。 if(pb&&pc)∥ 因共同元素而非 B 表或 C 表空而退出上面 while 循环。 if(pa->data>pb->data)∥A 表当前元素值大于 B 表和 C 表的公共元素，先将 B 表元素链入。 {pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B，C 公共元素为结果 表第一元素。 }∥结束了结果表中第一元素的确定 while(pa&&pb&&pc) {while(pb&&pc) if(pb->data<pc->data) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; ∥B 表和 C 表有公共元素。 if(pb&&pc) {while(pa&&pa->data<pb->data) ∥先将 A 中小于 B，C 公共元素部分链入。 {pre->next=pa;pre=pa;pa=pa->next;} if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;} else{pb=pb->next;pc=pc->next;}∥ 若 A 中已有 B，C 公共元素，则不再存 入结果表。 } }∥ while(pa&&pb&&pc) if(pa) pre->next=pa; ∥当 B，C 无公共元素（即一个表已空），将 A 中剩余链入。 }∥算法 Union 结束 [算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序 （即删除重复元素）。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始 pre=A （头结点的头指针），这时的 data 域无意义，不能与后继比较元素大小，因此就需要确定第 一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断 pre 是否等于 A，这占用了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为 O（|A|+|B|+|C|）。这就要求各个表的工作指 针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。 最后一个问题是，当 B，C 有一表为空（即 B 和 C 已无公共元素时），要将 A 的剩余部分 链入结果表。 3．[题目分析]循环单链表 L1 和 L2 数据结点个数分别为 m 和 n ，将二者合成一个循环 单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环