【正文】 i++) if([i][k])k=i。 for(i=0。max){ if(==0)return(0)。三、解答題1．編寫一函數(shù)，在線性順序表L中求出最大元素以及該元素在表中的位置（假設(shè)L中的元素不重復(fù)）。⒀ L=Lnext。⑾ Q=Pnext。⑼ while(Pnextnext!=NULL)P=Pnext。}⑺ while(Pnext!=Q)P=Pnext。⑹ while(Qnext!=NULL){P=Q。⑷ P=Pnextnext。⑵ Pnext=P。（ ）。（ ）。（ ）。4．如果系統(tǒng)語(yǔ)言不支持指針類型的變量，并且在元素總數(shù)變化不大的情況下，要求以最快的速度對(duì)線性表執(zhí)行插入和刪除操作，那么線性表應(yīng)該選用（靜態(tài)鏈表）存儲(chǔ)結(jié)構(gòu)。3．順序表中邏輯上相鄰的數(shù)據(jù)元素的物理位置（一定）緊相鄰。}二、填空題1．對(duì)于線性表的兩種基本存儲(chǔ)結(jié)構(gòu)，如果表中元素的總數(shù)基本穩(wěn)定，并且很少進(jìn)行插入和刪除操作，但是要求以最快的速度提取或修改線性表中的元素，應(yīng)該選用（順序）存儲(chǔ)結(jié)構(gòu)。return(1)。Pnext=Q。P=L。Lnext){Q=L。L){ //L是無(wú)表頭結(jié)點(diǎn)的單鏈表if(Lamp。運(yùn)行結(jié)果為：6．間述以下算法的功能。i4。運(yùn)行結(jié)果為：（3）在程序段(2)的基礎(chǔ)上畫出以下程序段運(yùn)行結(jié)果的示意圖。i0。運(yùn)行結(jié)果為：（2）在程序段(1)的基礎(chǔ)上畫出以下程序段運(yùn)行結(jié)果的示意圖。pdata=i*21。i++){ pnext=new LNode。for(i=1。5．畫出執(zhí)行下列各語(yǔ)句后各指針及鏈表的示意圖。（2）在有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表中，刪除結(jié)點(diǎn)p的時(shí)間復(fù)雜度為O(n)。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是：（1）可以統(tǒng)一表示空鏈表和非空鏈表；（2）對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。（3）頭指針：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。（1）首元結(jié)點(diǎn)：是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。（3）插入和刪除操作：對(duì)順序表進(jìn)行插入或刪除操作時(shí)，往往需要向后或向前移動(dòng)大量元素，所以該操作的時(shí)間開銷很大；而對(duì)于鏈表在進(jìn)行插入或刪除操作時(shí)，僅僅是簡(jiǎn)單的指針賦值運(yùn)算即可完成。（2）訪問操作：順序表中的元素存儲(chǔ)在一個(gè)連續(xù)的地址空間中，可以對(duì)表中的元素進(jìn)行隨機(jī)訪問。另一方面，順序表要求較大的連續(xù)存儲(chǔ)空間，這種分配方法會(huì)使系統(tǒng)空間中產(chǎn)生許多不可利用的空閑碎塊，降低了空間資源的利用率。第2章、部分習(xí)題參考答案一、簡(jiǎn)答題1．分別從線性表的存儲(chǔ)密度、訪問操作、插入（修改）和刪除操作，這三個(gè)方面討論其順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？（1）存儲(chǔ)密度：相對(duì)于順序存儲(chǔ)而言，鏈表中的一個(gè)結(jié)點(diǎn)比順序表中的一個(gè)記錄要多一個(gè)指針存儲(chǔ)空間，所以通常情況下，鏈表的存儲(chǔ)密度比順序表的存儲(chǔ)密度低。【實(shí)現(xiàn)提示】程序運(yùn)行后，首先要求用戶輸入人數(shù)n和報(bào)數(shù)上限的初始值m，然后依次讀入n個(gè)人的密碼?！净疽蟆浚?）用順序存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問題，按照出圈的順序依次輸出每人的編號(hào)和密碼；（2）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問題，依次輸出每個(gè)出圈人的編號(hào)和密碼；（3）用靜態(tài)循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問題，依次輸出每個(gè)出圈人原來(lái)的編號(hào)和密碼。讓報(bào)m的人出圈，顯示輸出該人的密碼，并將該密碼作為新的m值，從該位置順時(shí)針方向上的下一個(gè)人開始重新從1開始報(bào)數(shù)，如此下去，直到所有人全部出圈為止。實(shí)驗(yàn)題目 約瑟夫(Joseph)環(huán)【問題描述】約瑟夫(Joseph)問題的一種描述是：編號(hào)為1,2,3,…,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人有一個(gè)密碼（正整數(shù)）。其中，每個(gè)多項(xiàng)式都用單鏈表表示。試用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)，編出求解這一問題的程序。下一個(gè)人（第m+1個(gè)）又從1開始報(bào)數(shù)，再數(shù)到m的人又出列，依次重復(fù)下去，直到最后一個(gè)人出列為止。9．所謂約瑟夫（Josephu）問題是：設(shè)有n個(gè)人圍成一圈并依次進(jìn)行編號(hào)1，2，3，……，n。試設(shè)計(jì)一個(gè)算法刪除表中所有多余的元素（相同元素僅保留第一個(gè)），使刪除后表中的元素各不相同。試分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式下編寫出實(shí)現(xiàn)該算法的程序。7．已知線性表A中的數(shù)據(jù)元素按照值非遞減有序。要求算法中基本操作的次數(shù)越少越好。4．編寫一函數(shù)，將兩個(gè)遞增有序的順序表A和B歸并成一個(gè)順序表C，要求C是按元素值不減有序排列的（允許C中有相同值的元素）。2．編程實(shí)現(xiàn)，逆置順序表L中的所有元素（假設(shè)L中的元素為整數(shù)），并求出所用算法中基本操作的頻度。⒁ delete Q。⑿ P=L。⑽ Q=P。⑻ while(Pnextnext!=Q)P=Pnext。Q=Qnext。⑸ while(P!=NULL)P=Pnext。⑶ Pnext=Pnexenext。 ⑴ P=Pnext。 （ ）。 （ ）。5．已知L是帶頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，試從下面提供的答案中選擇合適的語(yǔ)句序列。單鏈表中邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ）緊相鄰。2．在長(zhǎng)度為n的順序表中插入或刪除一個(gè)元素，分別需要平均移動(dòng)（ ）個(gè)元素，執(zhí)行以上操作時(shí)，移動(dòng)元素的具體個(gè)數(shù)與（ ）有關(guān)。}else return(0)。 Qnext=NULL。while(Pnext)P=Pnext。 L=Lnext。amp。int Func(LinkList amp。i++)Del_LinkList(L,i)。for(i=1。i=1。}Pnext=NULL。P=Pnext。i=4。 P=L。4．在單鏈表、單循環(huán)鏈表、雙鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除掉？若可以，其時(shí)間復(fù)雜度各是多少？5．畫出執(zhí)行下列各語(yǔ)句后各指針及鏈表的示意圖。}程序運(yùn)行結(jié)果為：create p:輸入多項(xiàng)式的系數(shù)和相應(yīng)的指數(shù)(expn=1結(jié)束):2 1 5 8 11 0 0P=+2X^1+5X^^11create p1:輸入多項(xiàng)式的系數(shù)和相應(yīng)的指數(shù)(expn =1結(jié)束):7 0 5 8 11 9 0 0P=+7X^05X^8+11X^9p2=p+p1:P=+7X^0+2X^1+11X^^11p3=pp1:P=7X^0+2X^1+10X^811X^^11p4=p*p1:P=+14X^1+35X^810X^9+22X^^1125X^16+55X^17+^^20 習(xí) 題一、簡(jiǎn)答題1．分別從線性表的存儲(chǔ)密度、訪問操作、修改和刪除操作，這三個(gè)方面討論其順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？2．描述鏈表中，頭結(jié)點(diǎn)、頭指針、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）三個(gè)概念的區(qū)別。 coutp4=p*p1:\n。 DispPoly(p3)。 SubPoly(p3,p1)。 /////p3=pp1////////// InitPoly(p3)。 coutp2=p+p1:\n。 AddPoly(p2,p)。 DispPoly(p1)。 coutcreate p1:\n。 CreatePoly(p)。}9．多項(xiàng)式操作的綜合演示主程序void main(){ Poly p,p1,p2,p3,p4。 pp=ppnext。 InitPoly(pm)。 h=hnext。 +=。 while(h) { dd=hdata。p,Poly p1,PData d){ PData dd。 pp=ppnext。 *=1。 PData data。 }}7．多項(xiàng)式減多項(xiàng)式操作（p=pp1）void SubPoly(Poly amp。 while(pp) { InsertAddPData(p,ppdata)。 }}6．多項(xiàng)式加多項(xiàng)式操作（p=p+p1）void AddPoly(Poly amp。 coutpX^p。 if(p0)cout39。 else { coutP=。 }}5．按指數(shù)形式顯示一個(gè)多項(xiàng)式void DispPoly(Poly poly){ Poly p=poly。 if(==0||0)break。 cout輸入多項(xiàng)式的系數(shù)和相應(yīng)的指數(shù)(expn =1結(jié)束):\n。poly){ PData data。 delete q。 if(fabs(pnext)1e8) //刪除系數(shù)為零的項(xiàng) { q=pnext。 pnext=q。 qdata=data。pnext) //查找插入或相加的對(duì)應(yīng)項(xiàng) p=pnext。 while(pnextamp。算法實(shí)現(xiàn)void InsertAddPData(Poly amp。}3．多項(xiàng)式加單項(xiàng)式的操作（poly=poly+data）算法思想計(jì)算Poly+data的方法是：從前往后將poly，將其插入到poly中的適當(dāng)位置（按指數(shù)expn由小到大）。 pnext=NULL。 //定義指向該結(jié)點(diǎn)PNode的指針類型Poly.2．初始化一個(gè)零多項(xiàng)式的操作void InitPoly(Poly amp。 PNode* next。}。在C++語(yǔ)言中多項(xiàng)式的鏈表結(jié)構(gòu)類型定義如下：includestruct PData //定義多項(xiàng)式中每一項(xiàng)的系數(shù)和指數(shù)結(jié)構(gòu)類型:PData{系數(shù)，指數(shù)}{ double coef。上述多項(xiàng)式S(x)。既然S是線性表，同樣存在其存儲(chǔ)結(jié)構(gòu)的選擇問題。此時(shí)，可表示為：S=((8,0),(,50),(,2500))。為此，我們考慮只儲(chǔ)存多項(xiàng)式的非零系數(shù)，此時(shí)必須連同它所表示的項(xiàng)的指數(shù)一起存放才行。但是，在實(shí)際應(yīng)用中多項(xiàng)式的次數(shù)可能很高，且其中有大量的系數(shù)為零。設(shè)多項(xiàng)式的系數(shù)向量為且mn，則的系數(shù)向量為:。1．多項(xiàng)式的線性表示法在數(shù)學(xué)上，一個(gè)n次多項(xiàng)式Pn(x)可按升冪寫成：，可見，由其n+1個(gè)系數(shù)組成的系數(shù)向量唯一確定。算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(1)。 } } if(q)pnext=q。 pnext=r。q=qnext。q) { if(pnextdataqdata) p=pnext。 while(pnextamp。 L2){ LinkList p=L1,q=L2next,r。算法實(shí)現(xiàn)void Merger_L(LinkListamp?！尽楷F(xiàn)有兩個(gè)遞增有序的帶有頭結(jié)點(diǎn)的單鏈表LL2，要求將L2中的結(jié)點(diǎn)歸并到L1中并保持L1仍然有序，并且在歸并過程中不另設(shè)結(jié)點(diǎn)。 Lnext=q。q=r。 while(r=qnext) { qnext=p。 LinkList p=Lnext,q=pnext,r。算法實(shí)現(xiàn)void Contray_L(LinkList amp。(a)所示，(b)所示。 } coutendl。 //計(jì)算出圈人結(jié)點(diǎn)在鏈表L中的前驅(qū)結(jié)點(diǎn)位置k DeleteList_L(L,k+1,e)。i0。 //置第i個(gè)人的編號(hào)為i cout所求編號(hào)序列為:\n。i=n。 //輸入n、m的值 InitList_L(L)。 //定義線性鏈表L coutinput n m:。 //定義人數(shù)n、間隔數(shù)m、循環(huán)變量i和出圈人前驅(qū)結(jié)點(diǎn)的位置k ElemType e。【方法二】類似[]，通過直接調(diào)用單鏈表的基本操作來(lái)求解。 } coutendl。 coutqdata 。 q=pnext。 p=pnext。km。in。 cout所求編號(hào)序列為:\n。 } pnext=NULL。 p=pnext。i=n。 p=L。 //定義頭指針L指向頭結(jié)點(diǎn)以及結(jié)點(diǎn)指針變量p、q coutinput n m:。算法實(shí)現(xiàn)void main(){ int m,n,i,k。從第一個(gè)人開始報(bào)數(shù)（從1到m報(bào)數(shù)），凡報(bào)到m的人退出圈子并記下此人的排號(hào)，當(dāng)最后一個(gè)人退出圈子時(shí)，按出圈次序依次輸出所有人原來(lái)的排號(hào)序列（用單鏈表編程實(shí)現(xiàn)）。（3）由于假定系統(tǒng)不能使用指針類型變量，即不能動(dòng)態(tài)分配內(nèi)存，因此當(dāng)空間Space中的空閑鏈表為空時(shí)，將使靜態(tài)鏈表的插入操作失敗。 }//end_switch }//end_while}//end_main_S()運(yùn)行結(jié)果為：建立一個(gè)靜態(tài)鏈表，輸入長(zhǎng)度:12輸入12個(gè)結(jié)點(diǎn)的值:100 200 300 400 500 600 700 800 900 1000 1100 1200鏈表的初始內(nèi)容為:100 200 300 400 500 600 700 800 900 1000 1100 12001在第i個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn),2刪除第i個(gè)結(jié)點(diǎn)3顯示當(dāng)前鏈表的內(nèi)容,4顯示可用空間長(zhǎng)度5退出演示程序. 輸入選擇: