作業(yè)答案優(yōu)質(zhì)課件市公開課金獎市賽課一等獎?wù)n件

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

pa->data==pb->data

La(Lc)12467881011北京林業(yè)大學(xué)信息學(xué)院第2頁voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

LinkListpc,p；pa=La->next;pb=Lb->next;Lc=pc=La;//用La頭結(jié)點作為Lc頭結(jié)點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頭結(jié)點}北京林業(yè)大學(xué)信息學(xué)院第3頁2.將兩個非遞減有序鏈表合并為一個非遞增有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表存放空間,不另外占用其它存放空間。表中允許有重復(fù)數(shù)據(jù)。

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

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

作業(yè)思想類似于求n個數(shù)中最大數(shù)，可假設(shè)第一個結(jié)點最大，用指針pmax指向，然后用pmax依次和后面結(jié)點進行比較，發(fā)覺大者則用pmax指向該結(jié)點，這么將鏈表從頭到尾遍歷一遍時，pmax所指向結(jié)點就是最大者。其中比較語句形式以下：if(p->data>pmax->data)pmax=p;北京林業(yè)大學(xué)信息學(xué)院第8頁ElemType

Max(LinkListL){ LinkListpmax,p; if(L->next==NULL)returnNULL; pmax=L->next;//假定第一個結(jié)點中數(shù)據(jù)含有最大值 p=L->next->next; while(p!=NULL){//假如下一個結(jié)點存在 if(p->data>pmax->data)pmax=p; p=p->next; } returnpmax->data;}北京林業(yè)大學(xué)信息學(xué)院第9頁4.設(shè)計一個算法，經(jīng)過遍歷一趟，將鏈表中全部結(jié)點鏈接方向逆轉(zhuǎn)，仍利用原表存放空間。作業(yè)算法思想：從首元結(jié)點開始，逐一地把鏈表L當(dāng)前結(jié)點p插入新鏈表頭部(1)標(biāo)志后繼結(jié)點(2)修改指針（將p插入在頭結(jié)點之后）(3)重置結(jié)點p（p重新指向原表中后繼）北京林業(yè)大學(xué)信息學(xué)院第10頁a1a2a3LLpsucca1psucca2psucca3p(1)標(biāo)志后繼結(jié)點(2)修改指針（將p插入在頭結(jié)點之后）(3)重置結(jié)點p（p重新指向原表中后繼）北京林業(yè)大學(xué)信息學(xué)院第11頁voidinverse(LinkList&L){//逆置帶頭結(jié)點單鏈表LLinkListp,succ;p=L->next;L->next=NULL;while(p){succ=p->next;