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

練習(xí)題2習(xí)題2.2、23、24、2.5和2.6。2.2設(shè)計(jì)一個(gè)算法,將x插入到一個(gè)有序(從小到大排序)的線性表(順序存儲(chǔ)結(jié)構(gòu))的適當(dāng)位置上,并保持線性表的有序性voidInsert(sqList*&L,ElemTypex)iinti=0,j;while(i<L->length&L>datai<x)i++for(=L>length-l:j>=i:j--)L>dataLj+1=L->datal;L->datad=xL->length++23設(shè)計(jì)一個(gè)算法,將一個(gè)帶頭結(jié)點(diǎn)的數(shù)據(jù)域依次為a1,a2,…,an(n>3)的單鏈表的所有結(jié)點(diǎn)逆置,即第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域變?yōu)閍n,…,最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閍1voidReverse(LinkList"&L)iLinkList"p=L->next,qL->nextENULLwhile(p=NULL)∥掃描所有的結(jié)點(diǎn)q=p->next;∥讓q指向中p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)p->next=L->next∥總是將中結(jié)點(diǎn)作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)p=gE∥p指向下一個(gè)結(jié)點(diǎn)24設(shè)有一個(gè)雙鏈表,每個(gè)結(jié)點(diǎn)中除有pror、data和nxt三個(gè)域外,還有一個(gè)訪問頻度域freq,在鏈表被起用之前,其值均初始化為零。每當(dāng)進(jìn)行Locatenode(h,x)運(yùn)算時(shí),令元素值為x的結(jié)點(diǎn)中freq域的值加1,并調(diào)整表中結(jié)點(diǎn)的次序,使其按訪問頻度的遞減序排列,以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的Locatenode運(yùn)算的算法。boolLocateNode(DLinklisth,ElemTypex)IDLinkListp=h->next,q:while(p=NULL&p->data!=x)p=p->next;∥找data域值為x的節(jié)點(diǎn)中pif(p==NULL)∥.找到的情況returnfalse:∥找到的情況Ip->freq+∥煩度增1g=p->prior,∥~q為p前驅(qū)節(jié)點(diǎn)while(ql=h&q->freq<p->freq)(p->prior=q>prior;p->prior>next=p;∥/交換ψp和咚q的位置g->next=p->next:if(q->next!NULL)∥p不為最后一個(gè)節(jié)點(diǎn)時(shí)q->next->prior=q:p->next=q:q->prior=p;q=p->prior:重指向中p的前趨節(jié)點(diǎn)returntrue25設(shè)ha=(a1a2…,;an)和hb=(b1,b2,…,bm)是兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表,編寫將這兩個(gè)表合并為帶頭結(jié)點(diǎn)的循環(huán)單鏈表hc的算法。voidMerge(*ha,LinkList*hb,LinkList*&hc)ILinkList"p=ha->next;hc=hwhile(p->next!ha)∥找到ha的最后一個(gè)節(jié)點(diǎn)中pp=p->nextp>next=hb->next;∥將ha的最后一個(gè)節(jié)點(diǎn)的nex指向b的第一個(gè)數(shù)據(jù)節(jié)點(diǎn)while(p->next!hb)p=p>next;/找到hb的最后一個(gè)節(jié)點(diǎn)pp->next=hc∥構(gòu)成循環(huán)單鏈表free(hb)∥釋放hb單鏈表的頭節(jié)點(diǎn)26設(shè)非空線性表ha和hb都用帶頭節(jié)點(diǎn)的循環(huán)雙鏈表表示。設(shè)計(jì)一個(gè)算法Insert(ha,hb,i)。其功能是:i=0時(shí),將線性表hb插入到線性表ha的最前面;當(dāng)>0時(shí),將線性表hb插入到線性表ha中第i個(gè)節(jié)點(diǎn)的后面;當(dāng)i大于等于線性表ha的長(zhǎng)度時(shí),將線性表hb插入到線性表ha的最后面。voidInsert(DLinkList*&ha,DLinkList*&hb,inti)DLinklist"p=ha->next,"q:intlena=lj=0;while(p->next!-ha)∥求出ha的長(zhǎng)度lealena++;p=p->nextif(i=0)∥將hb的所有數(shù)據(jù)結(jié)點(diǎn)插入到ha的頭結(jié)點(diǎn)和第1個(gè)數(shù)據(jù)結(jié)點(diǎn)之間p=hb->prior指向hb的最后一個(gè)結(jié)點(diǎn)/p->next=ha->next;∥將中p鏈到ha的第1個(gè)數(shù)據(jù)結(jié)點(diǎn)前面ha->next->prior=p;ha->next=hb->nexthb->next->prior=ha;∥將ha頭結(jié)點(diǎn)與hb的第1個(gè)數(shù)據(jù)結(jié)點(diǎn)鏈起來elseif(i<lena)∥將hb插入到ha中間p=ha->nextwhilegi<i)∥在ha中查找第i個(gè)結(jié)點(diǎn)pp=p->next;q=p->next/指向中結(jié)點(diǎn)的后繼結(jié)點(diǎn)/p->next=hb->next;/hb->prior指向hb的最后一個(gè)結(jié)點(diǎn)hb->next->prior=p;hb->prior->nextq;q->prior=hb->prior;else∥將hb鏈到ha之后ha->prior->next=hb->next;/ha->prior指向ha的最后一個(gè)結(jié)點(diǎn)hb->next->prior=ha->priorhb->prior->next=ha;ha->prior=hb->priorhb);∥釋放hb頭結(jié)點(diǎn)練習(xí)題3習(xí)題3.1、3.2、3.3、3.4和3.6。3有5個(gè)元素,其進(jìn)棧次序?yàn)?A、B、C、D、E,在各種可能的出棧次序中,以元素C、D最先出棧(即C第一個(gè)且D第二個(gè)出棧)的次序有哪幾個(gè)?答:要使C第一個(gè)且D第二個(gè)出棧,應(yīng)是A進(jìn)棧,B進(jìn)棧,C進(jìn)棧,C出棧,D進(jìn)棧,D出棧,之后可以有以下幾種情況:(1)B出棧,A出棧,E進(jìn)棧,E出棧,輸出序列為CDBAE;(2)B出棧,E進(jìn)棧,E出棧,A出棧,輸出序列為CDBEA;(3)E進(jìn)棧,E出棧,B出棧,A出棧,輸出序列為CDEBA所以可能的次序有:CDBAE、CDBEA、CDEBA32假設(shè)以和O分別表示進(jìn)棧和出棧操作,棧的初態(tài)和終棧均為空,進(jìn)棧和出棧的操作序列可表示為僅由I和O組成的序列(1)下面所示的序列中哪些是合法的?AIOIOIOOB.IOOIOIIOC.IIOIOIOD.IIOOIOO(2)通過對(duì)