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

算法设计题

．[题目分析]因为两链表已按元素值递增次序排列将其合并时均从第一个结点起进行比较将小的链入链表中同时后移链表工作指针该问题要求结果链表按元素值递减次序排列故在合并的同时将链表结点逆置

LinkedList Union(LinkedList lalb)

∥lalb分别是带头结点的两个单链表的头指针链表中的元素值按递增序排列本算法将两链表合并成一个按元素值递减次序排列的单链表

{ pa=la>next; pb=lb>next;∥papb分别是链表la和lb的工作指针

la>next=null;∥la作结果链表的头指针先将结果链表初始化为空

while(pa!=null && pb!=null)∥当两链表均不为空时作

if(pa>data<=pb>data)

{ r=pa>next;∥将pa 的后继结点暂存于r

pa>next=la>next;∥将pa结点链于结果表中同时逆置

la>next=pa;

pa=r;∥恢复pa为当前待比较结点

}

else

{r=pb>next;∥ 将pb 的后继结点暂存于r

pb>next=la>next;∥将pb结点链于结果表中同时逆置

la>next=pb;

pb=r;∥恢复pb为当前待比较结点

}

while(pa!=null)∥将la表的剩余部分链入结果表并逆置

{r=pa>next; pa>next=la>next; la>next=pa; pa=r; }

while(pb!=null)

{r=pb>next; pb>next=la>next; la>next=pb; pb=r; }

}∥算法Union结束

［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb)两递增有序表合并成递减有序表时上述算法是边合并边逆置也可先合并完再作链表逆置后者不如前者优化算法中最后两个while语句不可能执行两个只能二者取一即哪个表尚未到尾就将其逆置到结果表中即将剩余结点依次前插入到结果表的头结点后面

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