作业答案优质课件市公开课金奖市赛课一等奖课件

1.将两个非递减有序链表合并为一个非递减有序链表。要求结果链表仍使用原来两个链表存放空间,不另外占用其它存放空间。表中不允许有重复数据。作业北京林业大学信息学院第1页参考讲稿和教材中算法2.12要单独考虑

pa->data==pb->data

La(Lc)12467881011北京林业大学信息学院第2页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(pa->data<pb->data){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头结点}北京林业大学信息学院第3页2.将两个非递减有序链表合并为一个非递增有序链表。要求结果链表仍使用原来两个链表存放空间,不另外占用其它存放空间。表中允许有重复数据。

作业北京林业大学信息学院第4页(1)Lc指向La(2)依次从La或Lb中“摘取”元素值较小结点插入到Lc表表头结点之后，直至其中一个表变空为止(3)继续将La或Lb其中一个表剩下结点插入在Lc表表头结点之后(4)释放Lb表表头结点参考讲稿和教材中算法2.12，步骤以下：北京林业大学信息学院第5页12233445561132434854LaLbLc∧papbqpb∧qpaqpaq第2题实现过程动态演示北京林业大学信息学院第6页voidunion(LinkList&La,LinkList&Lb,LinkList&Lc,){LinkListpa,pb,q;pa=La->next;pb=Lb->next;//初始化Lc=La;//用La头结点作为Lc头结点Lc->next=NULL;while(pa||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(Lb);//释放Lb头结点}

北京林业大学信息学院第7页3.设计一个算法，经过一趟遍历在单链表中确定值最大结点。

作业思想类似于求n个数中最大数，可假设第一个结点最大，用指针pmax指向，然后用pmax依次和后面结点进行比较，发觉大者则用pmax指向该结点，这么将链表从头到尾遍历一遍时，pmax所指向结点就是最大者。其中比较语句形式以下：if(p->data>pmax->data)pmax=p;北京林业大学信息学院第8页ElemType

Max(LinkListL){ LinkListpmax,p; if(L->next==NULL)returnNULL; pmax=L->next;//假定第一个结点中数据含有最大值 p=L->next->next; while(p!=NULL){//假如下一个结点存在 if(p->data>pmax->data)pmax=p; p=p->next; } returnpmax->data;}北京林业大学信息学院第9页4.设计一个算法，经过遍历一趟，将链表中全部结点链接方向逆转，仍利用原表存放空间。作业算法思想：从首元结点开始，逐一地把链表L当前结点p插入新链表头部(1)标志后继结点(2)修改指针（将p插入在头结点之后）(3)重置结点p（p重新指向原表中后继）北京林业大学信息学院第10页a1a2a3LLpsucca1psucca2psucca3p(1)标志后继结点(2)修改指针（将p插入在头结点之后）(3)重置结点p（p重新指向原表中后继）北京林业大学信息学院第11页voidinverse(LinkList&L){//逆置带头结点单链表LLinkListp,succ;p=L->next;L->next=NULL;while(p){succ=p->next;