算法设计题答案打印部分

《算法设计题答案打印部分》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录《线性表》算法设计题答案1《栈和队列》算法设计题答案26《串》算法设计题答案37《数组和广义表》算法设计题答案43《树和二叉树》算法设计题答案54《图》算法设计题答案83《集合》算法设计题答案101《排序》算法设计题答案114《线性表》算法设计题答案1．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。LinkedListUnion(LinkedListla,lb)∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序

2、排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。{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的后继结点暂存

3、于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),两递增有序表合并成递减有序表时，上述算法是边合并边逆置

4、。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while126语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。　与本题类似的其它题解答如下：　（１）［问题分析］与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。　LinkedListUnion(LinkedListha,hb)∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现

5、在ha中的数据合并到ha中，合并中不能破坏hb链表。　｛LinkedListla;la=(LinkedList)malloc(sizeof(LNode));la->next=ha;∥申请头结点，以便操作。pa=ha;∥pa是ha链表的工作指针pb=hb;∥pb是hb链表的工作指针pre=la;∥pre指向当前待合并结点的前驱。while(pa&&pb)if(pa->datadata)∥处理ha中数据{pre->next=pa;pre=pa;pa=pa->next;}elseif(pa->data>pb->data)∥处理hb中数据。{r=(LinkedList)mallo

6、c(sizeof(LNode));∥申请空间r->data=pb->data;pre->next=r;pre=r;∥将新结点链入结果链表。pb=pb->next;∥hb链表中工作指针后移。}　　　　else∥处理pa->data=pb->data;{pre->next=pa;pre=pa;pa=pa->next;∥两结点数据相等时，只将ha的数据链入。pb=pb->next;∥不要hb的相等数据}if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。elsepre->next=pb;free(la);∥释放头结点.ha,hb指针未被破坏。}∥算法nio

7、n结束。(2)本题与上面两题类似，要求结果指针为lc，其核心语句段如下：pa=la->next;pb=hb->next;lc=(LinkedList)malloc(sizeof(LNode));pc=lc;∥pc是结果链表中当前结点的前驱while(pa&&pb)if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}if(pa)pc->next=