部分習(xí)題參考的答案教學(xué)課件

練習(xí)題習(xí)題2.2、2.3、2.4、2.5和2.6。22設(shè)計一個算法,將x插入到一個有序(從小到大排序)的線性表(順序存儲結(jié)構(gòu))的適當(dāng)位置上,并保持線性表的有序性voidInsert(SqList"&L,ElemTypex)tinti=0,j;while(<L->length&L->data[i]<x)i++for(j=L->length-l:j>=i:j--)L→>data[j+1]=L→>data[j];L->datai]=x:L->length++;23設(shè)計一個算法,將一個帶頭結(jié)點的數(shù)據(jù)域依次為a1,a2,…,an(n≥3)的單鏈表的所有結(jié)點逆置,即第一個結(jié)點的數(shù)據(jù)域變?yōu)閍n,最后一個結(jié)點的數(shù)據(jù)域為a1voidReverse(LinkList*&L)LinkList*p=L->next,"'q;L->nextENULL:while(p!=NULL)∥掃描所有的結(jié)點tq=p->next∥讓q指向p結(jié)點的下一個結(jié)點∥總是將中結(jié)點作為第一個數(shù)據(jù)結(jié)點L->next=p;∥}p指向下一個結(jié)點24設(shè)有一個雙鏈表,每個結(jié)點中除有pror、data和next三個域外,還有一個訪問頻度域req,在鏈表被起用之前,其值均初始化為零。每當(dāng)進(jìn)行LocateNode(h,x)運算時,令元素值為x的結(jié)點中freq域的值加1,并調(diào)整表中結(jié)點的次序,使其按訪問頻度的遞減序排列,以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的Locatenode運算的算法。boolLocateNode(LinkList"h,ElemTypex)iDLinkList"p=h->next,q:while(p!=NULL&p->data=Xp=p->next;∥找data域值為x的節(jié)點中pif(P==NULL)∥未找到的情況returnfalse∥找到的情況p->freq++∥頻度增1(Ep->priorq為p前驅(qū)節(jié)點while(qt=h&g->freq<p->freg)p->prior=q->prior;p->prior->next=p;∥交換*p和q的位置q->next=p->next:if(q->next!=NULL)∥p不為最后一個節(jié)點時g->next->prior=q:p->next=q:q->prior=p:4=p->pr/重指向中p的前趨節(jié)點returntrue:25設(shè)ha=(a1,a2,an)和hb=(b1b2…,bm)是兩個帶頭結(jié)點的循環(huán)單鏈表,編寫將這兩個表合并為帶頭結(jié)點的循環(huán)單鏈表hc的算法。voidMerge(LinkListha,LinkListhb,LinkList*&hc)LinkList*p=ha->next;hc=ha;while(p->next!=ha)∥找到ha的最后一個節(jié)點中pp=p->next:p->next=hb->next;∥將ha的最后一個節(jié)點的next指向hb的第一個數(shù)據(jù)節(jié)點while(p->next:=