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

．[题目分析] 将具有两个链域的单循环链表改造成双向循环链表关键是控制给每个结点均置上指向前驱的指针而且每个结点的前驱指针置且仅置一次

void StoDouble(LinkedList la)∥la是结点含有predatalink三个域的单循环链表其中data为数据域pre为空指针域link是指向后继的指针域本算法将其改造成双向循环链表

{while(la>link>pre==null)

{la>link>pre=la;∥将结点la后继的pre指针指向la

la=la>link;∥la指针后移

}

}∥算法结束

[算法讨论] 算法中没有设置变量记住单循环链表的起始结点至少省去了一个指针变量当算法结束时la恢复到指向刚开始操作的结点这是本算法的优点所在

．[题目分析] 求两个集合A和B的差集AB即在A中删除A和B中共有的元素由于集合用单链表存储问题变成删除链表中的结点问题因此要记住被删除结点的前驱以便顺利删除被删结点两链表均从第一元素结点开始直到其中一个链表到尾为止

void Difference(LinkedList AB*n)∥A和B均是带头结点的递增有序的单链表分别存储了一个集合本算法求两集合的差集存储于单链表A中*n是结果集合中元素个数调用时为

{p=A>next;∥p和q分别是链表A和B的工作指针

q=B>next; pre=A;∥pre为A中p所指结点的前驱结点的指针

while(p!=null && q!=null)

if(p>data<q>data){pre=p;p=p>next;*n++;}∥A链表中当前结点指针后移

else if(p>data>q>data)q=q>next;∥B链表中当前结点指针后移

else {pre>next=p>next;∥处理AB中元素值相同的结点应删除

u=p; p=p>next; free(u);}∥删除结点

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