第二章線性表作業(yè)答案公開課一等獎?wù)n件省課獲獎?wù)n件

第二章線性表作業(yè)參照答案第1頁作業(yè)1.1用次序表表達(dá)集合，設(shè)計一種算法實現(xiàn)集合求差集運(yùn)算，即C=A-B。算法分析：C中元素為A中所有不屬于B元素。掃描A中元素，若它與B中所有元素均不相同，表達(dá)是差集元素，將其放到C中。typedefstruct

{ElemType*elem;//存放空間基址intlength;//目前長度intlistsize;//目前分派存放容量}SqList;第2頁Voiddiffence(SqlistA,SqlistB,SqlistC){inti,j,k=0;for(i=0;i<A.length;i++){j=0;while(j<B.length&&B.elem[j]!=A.elem[i])j++;if(j==B.length)//表達(dá)A.elem[i]不在B中，將其放到C中C.elem[k++]=A.elem[i];}C.length=k;}第3頁作業(yè)1.2試寫一種算法，實現(xiàn)次序表就地逆置。typedefstruct

{ElemType*elem;//存放空間基址intlength;//目前長度intlistsize;//目前分派存放容量}SqList;第4頁算法：statusReverse(SqList&L){//對次序表實現(xiàn)就地逆序n=L.lengthfor(i=0;i<n/2;i++){temp=L.elem[i];L.elem[i]=L.elem[n-i-1]；L.elem[n-i-1]=temp;}returnOK;}//Reverse第5頁作業(yè)2.1已知線性表中數(shù)據(jù)元素以值遞增有序排列，并以單鏈表作存放構(gòu)造，試寫一種高效算法，刪除表中所有值大于mink且不大于maxk元素（若表中存在這樣元素），同步釋放被刪除結(jié)點(diǎn)空間typedefstructLnode {elemtypedata;//數(shù)據(jù)域 structLnode*next;//指針域 }Lnode,*linklist;第6頁StatusDELmink_maxk(LinkLlist&L,ElemTypemink,ElemTypemaxk){p=L->next;q=L;//p指向目前鏈結(jié)點(diǎn)，q指向前一種鏈結(jié)點(diǎn)if(!p)returnERROR;//空鏈表while(p!=NULL&&p->data<mink){q=p;p=p->next;}if(!p)retutnERROR;//找不到指定范圍數(shù)據(jù)elsewhile(p->data<=maxk&&p!=NULL){r=p;//刪除鏈結(jié)點(diǎn)pp=p->next;free(r);}q->next=p;//刪除若干鏈結(jié)點(diǎn)后，重新建立鏈接}//DELmink_maxk第7頁作業(yè)2.2設(shè)線性表A=(a1,a2,…,an)，B=(b1,b2,…,bm)，試寫一種按下列規(guī)則合并A、B為線性表C算法，雖然得C=(a1,b1,a2,b2,…,am,bm,bm+1,…,bn)當(dāng)m<=n或C=(a1,b1,a2,b2,…,an,bn,an+1,…,am)當(dāng)m>n線性表A、B和C均為單鏈表作存放構(gòu)造，且C表利用A表和B表中結(jié)點(diǎn)空間構(gòu)表。注意：單鏈表長度值m和n均未顯式存放。第8頁算法：statusCOMBINE(linklistA,linklistB,linklist&C){C=A;a=A->next;b=B->next;If(a==NULL){A->next=B;ReturnOk;}do{p=a->next;q=b->next;a->next=b;b->next=p;a=p;b=q;}while(p->next&&q);if(p->next==NULL)a->next=b;}//COMBINE第9頁作業(yè)3.1假設(shè)某個單向循環(huán)鏈表長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個結(jié)點(diǎn)指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)。算法思緒：首先找到s所指鏈結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)(即將被刪除鏈結(jié)點(diǎn)，算法中由q指出其地址)與直接前驅(qū)結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)(算法中由r指出其地址)，然后做刪除操作。第10頁算法：StatusDelS(Linklist&s){r=s;q=s->n