文档介绍：目录
《线性表》算法设计题答案 1
《栈和队列》算法设计题答案 26
《串》算法设计题答案 37
《数组和广义表》算法设计题答案 43
《树和二叉树》算法设计题答案 54
《图》算法设计题答案 83
《集合》算法设计题答案 101
《排序》算法设计题答案 114
《线性表》算法设计题答案
1.[题目分析]因为两链表已按元素值递增次序排列,将其合并时,均从第一个结点起进行比较,将小的链入链表中,同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时,将链表结点逆置。
LinkedList Union(LinkedList la,lb)
∥la,lb分别是带头结点的两个单链表的头指针,链表中的元素值按递增序排列,本算法将两链表合并成一个按元素值递减次序排列的单链表。
{ pa=la->next; pb=lb->next;∥pa,pb分别是链表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
语句,不可能执行两个,只能二者取一,即哪个表尚未到尾,就将其逆置到结果表中,即将剩余结点依次前插入到结果表的头结点后面。
与本题类似的其它题解答如下:
(1)[问题分析]与上题类似,不同之处在于:一是链表无头结点,为处理方便,给加上头结点,处理结束再删除之;二是数据相同的结点,不合并到结果链表中;三是hb链表不能被破坏,即将hb的结点合并到结果链表时,要生成新结点。
LinkedList Union(LinkedList ha, hb)
∥ha和hb是两个无头结点的数据域值递增有序的单链表,本算法将hb中并不出现在ha中的数据合并到ha中,合并中不能破坏hb链表。
{LinkedList la;
la=(LinkedList)malloc(sizeof(LNode));
la->next=ha;∥申