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

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

pa->data==pb->data

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

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

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

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

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

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