第2章作业答案

《第2章作业答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。作业北京林业大学信息学院参考讲稿和教材中的算法2.12要单独考虑pa->data==pb->dataLa(Lc)12467881011北京林业大学信息学院voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){LinkListpc,p；pa=La->next;pb=Lb->next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(

2、pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{//相等时取La的元素，删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;p=pb;pb=pb->next;free(p);}pc->next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}北京林业大学信息学院2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链

3、表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。作业北京林业大学信息学院(1)Lc指向La(2)依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的表头结点之后，直至其中一个表变空为止(3)继续将La或Lb其中一个表的剩余结点插入在Lc表的表头结点之后(4)释放Lb表的表头结点参考讲稿和教材中的算法2.12，步骤如下：北京林业大学信息学院12233445561132434854LaLbLc∧papbqpb∧qpaqpaq第2题实现过程动态演示北京林业大学信息学院voidunion(LinkList&La,LinkList&Lb,LinkLis

4、t&Lc,){LinkListpa,pb,q;pa=La->next;pb=Lb->next;//初始化Lc=La;//用La的头结点作为Lc的头结点Lc->next=NULL;while(pa

5、

6、pb){if(!pa){q=pb;pb=pb->next;}//pa=NULLelseif(!pb){q=pa;pa=pa->next;}//pb=NULLelseif(pa->data<=pb->data){q=pa;pa=pa->next;}else{q=pb;pb=pb->next;}q->next=Lc->next;Lc->next=q;//插入}free(

7、Lb);//释放Lb的头结点}北京林业大学信息学院3.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。作业思想类似于求n个数中的最大数，可假设第一个结点最大，用指针pmax指向，然后用pmax依次和后面的结点进行比较，发现大者则用pmax指向该结点，这样将链表从头到尾遍历一遍时，pmax所指向的结点就是最大者。其中的比较语句形式如下：if(p->data>pmax->data)pmax=p;北京林业大学信息学院ElemTypeMax(LinkListL){LinkListpmax,p;if(L->next==NULL)returnNULL;pmax=L-

8、>next;//假定第一个结点中数据具有最大值p=L->next->next;while(p!=NULL){//如果下一个结点存在if(p->data>pmax->data)pmax=p;p=p->next;}returnpmax->data;}北京林业大学信息学院4.设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。作业算法的思想：从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部(1)标志后继结点(2)修改指针（将p插入在头结点之后）(3)重置结点p（p重新指向原表中后继）北京林业大学信息学院a1a2a3LLps

9、ucca1psucca2psucca3p(1)标志后继结点(2)修改指针（将p插入在头结点之后）(3)重置结点p（p重新指向原表中后继）北京林业大学信息学院voidinverse(LinkList&L){//逆置带头结点的单链表LLinkListp,succ;p=L->next;L->next=NULL;while(p){succ=p->next;//succ指向*p的后继p->next=L->next;L->next=p;//*p插入在头结点之后p=succ;}}北京林业大学信息学院