数据结构考研分类复习真题 第二章 答案[18]

[算法讨论]本算法先找结果链表的第一个元素这是因为题目要求结果表要递增有序(即删除重复元素)这就要求当前待合并到结果表的元素要与其前驱比较由于初始pre=A(头结点的头指针)这时的data域无意义不能与后继比较元素大小因此就需要确定第一个元素当然不要这样作而直接进入下面循环也可以但在链入结点时必须先判断pre是否等于A这占用了过多的时间因此先将第一结点链入是可取的

算法中的第二个问题是要求时间复杂度为O(|A|+|B|+|C|)这就要求各个表的工作指针只能后移(即不能每次都从头指针开始查找)本算法满足这一要求

最后一个问题是当BC有一表为空(即B和C已无公共元素时)要将A的剩余部分链入结果表

．[题目分析]循环单链表L和L数据结点个数分别为m和n 将二者合成一个循环单链表时需要将一个循环链表的结点(从第一元素结点到最后一个结点)插入到另一循环链表的第一元素结点前即可题目要求用最快速度将两表合并因此应找结点个数少的链表查其尾结点

LinkedList Union(LinkedList LL;int mn)∥L和L分别是两循环单链表的头结点的指针m和n分别是L和L的长度本算法用最快速度将L和L合并成一个循环单链表

{if(m<||n<) {printf(表长输入错误\n);exit();}

if(m<n)∥若m<n则查L循环单链表的最后一个结点

{if(m==)return(L);∥L为空表

else{p=L;

while(p>next!=L) p=p>next;∥查最后一个元素结点

p>next=L>next;∥将L循环单链表的元素结点插入到L的第一元素结点前

L>next=L>next;

free(L);∥释放无用头结点

}

}∥处理完m<n情况

else∥ 下面处理L长度小于等于L的情况

{if(n==)return(L);∥L为空表

else{p=L;

while(p>next!=L) p=p>next;∥查最后元素结点

p>next=L>next;∥将L的元素结点插入到L循环单链表的第一元素结点前

L>next=L>next;

free(L);∥释放无用头结点

}

}∥算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []