作業(yè)答案優(yōu)質課件市公開課金獎市賽課一等獎課件

1.將兩個非遞減有序鏈表合并為一個非遞減有序鏈表。要求結果鏈表仍使用原來兩個鏈表存放空間,不另外占用其它存放空間。表中不允許有重復數據。作業(yè)北京林業(yè)大學信息學院第1頁參考講稿和教材中算法2.12要單獨考慮

pa->data==pb->data

La(Lc)12467881011北京林業(yè)大學信息學院第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頭結點}北京林業(yè)大學信息學院第3頁2.將兩個非遞減有序鏈表合并為一個非遞增有序鏈表。要求結果鏈表仍使用原來兩個鏈表存放空間,不另外占用其它存放空間。表中允許有重復數據。

作業(yè)北京林業(yè)大學信息學院第4頁(1)Lc指向La(2)依次從La或Lb中“摘取”元素值較小結點插入到Lc表表頭結點之后，直至其中一個表變空為止(3)繼續(xù)將La或Lb其中一個表剩下結點插入在Lc表表頭結點之后(4)釋放Lb表表頭結點參考講稿和教材中算法2.12，步驟以下：北京林業(yè)大學信息學院第5頁12233445561132434854LaLbLc∧papbqpb∧qpaqpaq第2題實現(xiàn)過程動態(tài)演示北京林業(yè)大學信息學院第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頭結點}

北京林業(yè)大學信息學院第7頁3.設計一個算法，經過一趟遍歷在單鏈表中確定值最大結點。

作業(yè)思想類似于求n個數中最大數，可假設第一個結點最大，用指針pmax指向，然后用pmax依次和后面結點進行比較，發(fā)覺大者則用pmax指向該結點，這么將鏈表從頭到尾遍歷一遍時，pmax所指向結點就是最大者。其中比較語句形式以下：if(p->data>pmax->data)pmax=p;北京林業(yè)大學信息學院第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;}北京林業(yè)大學信息學院第9頁4.設計一個算法，經過遍歷一趟，將鏈表中全部結點鏈接方向逆轉，仍利用原表存放空間。作業(yè)算法思想：從首元結點開始，逐一地把鏈表L當前結點p插入新鏈表頭部(1)標志后繼結點(2)修改指針（將p插入在頭結點之后）(3)重置結點p（p重新指向原表中后繼）北京林業(yè)大學信息學院第10頁a1a2a3LLpsucca1psucca2psucca3p(1)標志后繼結點(2)修改指針（將p插入在頭結點之后）(3)重置結點p（p重新指向原表中后繼）北京林業(yè)大學信息學院第11頁voidinverse(LinkList&L){//逆置帶頭結點單鏈表LLinkListp,succ;p=L->next;L->next=NULL;while(p){succ=p->next;