【正文】 q。 while(pnextamp。 } } if(q)pnext=q。但是，在實(shí)際應(yīng)用中多項(xiàng)式的次數(shù)可能很高，且其中有大量的系數(shù)為零。上述多項(xiàng)式S(x)。 //定義指向該結(jié)點(diǎn)PNode的指針類(lèi)型Poly.2．初始化一個(gè)零多項(xiàng)式的操作void InitPoly(Poly amp。 while(pnextamp。 if(fabs(pnext)1e8) //刪除系數(shù)為零的項(xiàng) { q=pnext。 if(==0||0)break。 coutpX^p。 PData data。 while(h) { dd=hdata。 pp=ppnext。 DispPoly(p1)。 SubPoly(p3,p1)。4．在單鏈表、單循環(huán)鏈表、雙鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除掉？若可以，其時(shí)間復(fù)雜度各是多少？5．畫(huà)出執(zhí)行下列各語(yǔ)句后各指針及鏈表的示意圖。}Pnext=NULL。int Func(LinkList amp。 Qnext=NULL。5．已知L是帶頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，試從下面提供的答案中選擇合適的語(yǔ)句序列。⑶ Pnext=Pnexenext。⑽ Q=P。4．編寫(xiě)一函數(shù)，將兩個(gè)遞增有序的順序表A和B歸并成一個(gè)順序表C，要求C是按元素值不減有序排列的（允許C中有相同值的元素）。試設(shè)計(jì)一個(gè)算法刪除表中所有多余的元素（相同元素僅保留第一個(gè)），使刪除后表中的元素各不相同。其中，每個(gè)多項(xiàng)式都用單鏈表表示。【實(shí)現(xiàn)提示】程序運(yùn)行后，首先要求用戶(hù)輸入人數(shù)n和報(bào)數(shù)上限的初始值m，然后依次讀入n個(gè)人的密碼。（3）插入和刪除操作：對(duì)順序表進(jìn)行插入或刪除操作時(shí)，往往需要向后或向前移動(dòng)大量元素，所以該操作的時(shí)間開(kāi)銷(xiāo)很大；而對(duì)于鏈表在進(jìn)行插入或刪除操作時(shí)，僅僅是簡(jiǎn)單的指針賦值運(yùn)算即可完成。（2）在有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表中，刪除結(jié)點(diǎn)p的時(shí)間復(fù)雜度為O(n)。pdata=i*21。i4。P=L。3．順序表中邏輯上相鄰的數(shù)據(jù)元素的物理位置（一定）緊相鄰。（ ）。}⑺ while(Pnext!=Q)P=Pnext。三、解答題1．編寫(xiě)一函數(shù)，在線(xiàn)性順序表L中求出最大元素以及該元素在表中的位置（假設(shè)L中的元素不重復(fù)）。i++) if([i][k])k=i。⒀ L=Lnext。⑹ while(Qnext!=NULL){P=Q。（ ）。}二、填空題1．對(duì)于線(xiàn)性表的兩種基本存儲(chǔ)結(jié)構(gòu)，如果表中元素的總數(shù)基本穩(wěn)定，并且很少進(jìn)行插入和刪除操作，但是要求以最快的速度提取或修改線(xiàn)性表中的元素，應(yīng)該選用（順序）存儲(chǔ)結(jié)構(gòu)。Lnext){Q=L。運(yùn)行結(jié)果為：（3）在程序段(2)的基礎(chǔ)上畫(huà)出以下程序段運(yùn)行結(jié)果的示意圖。i++){ pnext=new LNode。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是：（1）可以統(tǒng)一表示空鏈表和非空鏈表；（2）對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。（2）訪問(wèn)操作：順序表中的元素存儲(chǔ)在一個(gè)連續(xù)的地址空間中，可以對(duì)表中的元素進(jìn)行隨機(jī)訪問(wèn)?！净疽蟆浚?）用順序存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問(wèn)題，按照出圈的順序依次輸出每人的編號(hào)和密碼；（2）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問(wèn)題，依次輸出每個(gè)出圈人的編號(hào)和密碼；（3）用靜態(tài)循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬約瑟夫問(wèn)題，依次輸出每個(gè)出圈人原來(lái)的編號(hào)和密碼。試用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)，編出求解這一問(wèn)題的程序。試分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式下編寫(xiě)出實(shí)現(xiàn)該算法的程序。2．編程實(shí)現(xiàn)，逆置順序表L中的所有元素（假設(shè)L中的元素為整數(shù)），并求出所用算法中基本操作的頻度。⑻ while(Pnextnext!=Q)P=Pnext。 ⑴ P=Pnext。單鏈表中邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ）緊相鄰。while(Pnext)P=Pnext。i++)Del_LinkList(L,i)。P=Pnext。}程序運(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．分別從線(xiàn)性表的存儲(chǔ)密度、訪問(wèn)操作、修改和刪除操作，這三個(gè)方面討論其順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有哪些優(yōu)缺點(diǎn)？2．描述鏈表中，頭結(jié)點(diǎn)、頭指針、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）三個(gè)概念的區(qū)別。 /////p3=pp1////////// InitPoly(p3)。 coutcreate p1:\n。 InitPoly(pm)。p,Poly p1,PData d){ PData dd。 }}7．多項(xiàng)式減多項(xiàng)式操作（p=pp1）void SubPoly(Poly amp。 if(p0)cout39。 cout輸入多項(xiàng)式的系數(shù)和相應(yīng)的指數(shù)(expn =1結(jié)束):\n。 pnext=q。算法實(shí)現(xiàn)void InsertAddPData(Poly amp。 PNode* next。既然S是線(xiàn)性表，同樣存在其存儲(chǔ)結(jié)構(gòu)的選擇問(wèn)題。設(shè)多項(xiàng)式的系數(shù)向量為且mn，則的系數(shù)向量為:。 pnext=r。 L2){ LinkList p=L1,q=L2next,r。q=r。(a)所示，(b)所示。 //置第i個(gè)人的編號(hào)為i cout所求編號(hào)序列為:\n。 //定義人數(shù)n、間隔數(shù)m、循環(huán)變量i和出圈人前驅(qū)結(jié)點(diǎn)的位置k ElemType e。 q=pnext。 cout所求編號(hào)序列為:\n。 p=L。（3）由于假定系統(tǒng)不能使用指針類(lèi)型變量，即不能動(dòng)態(tài)分配內(nèi)存，因此當(dāng)空間Space中的空閑鏈表為空時(shí)，將使靜態(tài)鏈表的插入操作失敗。 k++。 cini。 while(1) { cout“輸入選擇:”。i++) { cine。 InitSpace_S(SS)。}（4）靜態(tài)鏈表p的遍歷操作TraverseList_S(Space,p)該操作按序顯示鏈表p中每一個(gè)結(jié)點(diǎn)的值。ki) { h=Space[h].cur。e)該操作刪除p中第i個(gè)結(jié)點(diǎn)將data值賦值給e,并將資源歸還給Space。 if(!(q=NewSNode(Space)))//獲取一個(gè)結(jié)點(diǎn) return 0。算法設(shè)計(jì)代碼如下：int InsertList_S(SLinkList amp。Space,int amp。 Space[0].cur=p。Space){ int p。in1。其中，SNode為靜態(tài)鏈表的結(jié)點(diǎn)類(lèi)型（相當(dāng)于鏈表的結(jié)點(diǎn)類(lèi)型），數(shù)據(jù)域data中存放元素的數(shù)據(jù)，下標(biāo)（游標(biāo)）域cur中存放下一個(gè)元素（直接后繼）的下標(biāo)；SLinkList為靜態(tài)鏈表存儲(chǔ)空間Space的定義類(lèi)型（相當(dāng)于鏈表中堆空間的類(lèi)型）。雙向鏈表的特點(diǎn)是可以直接求得鏈表中任意一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。其原因是在結(jié)點(diǎn)中只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針，而不含指向直接前驅(qū)結(jié)點(diǎn)的指針信息。本節(jié)給出的循環(huán)鏈表可以部分彌補(bǔ)以上缺陷。但是，相對(duì)于順序表而言雖然插入和刪除操作的時(shí)間復(fù)雜度相同，由于其基本操作中，鏈表僅僅是簡(jiǎn)單的指針賦值運(yùn)算而順序表要移動(dòng)整個(gè)記錄，所以順序表實(shí)際花費(fèi)的時(shí)間較多。 case 6: TraverseList_L(L)。 if(!DeleteList_L(L,i,e)) cout刪除位置不合理,操作失敗\n。 if(!SetElem_L(L,i,e)) cout輸入的位置不合理,修改不成功\n。 cinnum。 }}2．單鏈表的綜合演示主程序void main_L(){ LinkList L。 cout建立鏈表L:\n。 while(p) { coutpdata 。 LinkList p=Lnext。 if(i1||!pnext)return 0。L,int i,ElemType amp。e)操作的功能是將單鏈表L中第i個(gè)結(jié)點(diǎn)的值賦值給e，并將該結(jié)點(diǎn)從鏈表中刪除。 //查找L中第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的指針p if(i1||ki)return 0。算法實(shí)現(xiàn)int InsertList_L(LinkList amp。}5．插入操作InsertList_L(amp。 return 1。 LinkList p=Lnext。 if(i1||!p)return 0。算法實(shí)現(xiàn)int GetElem_L(LinkList L,int i,ElemType amp。L)該操作是構(gòu)造一個(gè)只含有頭結(jié)點(diǎn)的空鏈表L。為了對(duì)單鏈表的各種操作進(jìn)行統(tǒng)一處理和方便表示，在鏈表的開(kāi)頭增設(shè)一個(gè)結(jié)點(diǎn)稱(chēng)為頭結(jié)點(diǎn)，它的結(jié)構(gòu)與鏈表中其他結(jié)點(diǎn)的結(jié)構(gòu)一樣，但在data域中不存放數(shù)據(jù)。為了能正確表示線(xiàn)性表中的每個(gè)數(shù)據(jù)元素以及它們之間存在的邏輯關(guān)系（前驅(qū)與后繼關(guān)系），對(duì)于一個(gè)數(shù)據(jù)元素來(lái)說(shuō)，除了要存儲(chǔ)它本身的信息之外，還需要存儲(chǔ)指示其直接后繼元素的指針（地址）信息。 i++,j?！尽吭嚲帉?xiě)一算法，實(shí)現(xiàn)對(duì)線(xiàn)性順序表L的逆置操作。 for(i=0。 //定義線(xiàn)性順序表L coutinput n m:。L)來(lái)批量移動(dòng)記錄，從而浪費(fèi)大量的時(shí)間；如果選取的值較大，但是在實(shí)際運(yùn)行時(shí)很少進(jìn)行插入操作，這將導(dǎo)致存儲(chǔ)空間的大量浪費(fèi)；（3）順序存儲(chǔ)要求一次分配足夠大的連續(xù)的內(nèi)存空間，如果當(dāng)前系統(tǒng)中沒(méi)有連續(xù)的足夠大的空閑空間可用，這將導(dǎo)致內(nèi)存分配失敗。 break。 break。 case 3: cout輸入插入位置i和值e:。 cini。 cout順序表的初始數(shù)據(jù)為:\n。 for(i=1。 }}在前面順序表的結(jié)構(gòu)定義及其基本操作算法的基礎(chǔ)上，本節(jié)給出順序表的各個(gè)基本操作的綜合演示程序代碼以及運(yùn)行結(jié)果。算法實(shí)現(xiàn)int Length_Sq(SqList L){ return 。 //置e的值為L(zhǎng)中第i個(gè)元素的值 while(i) //將L中第i個(gè)以后的所有元素都依次向前移動(dòng)一個(gè)位置 { [i1]=[i]。L,i,amp。k) [k]=[k1]。 // =a。L),；(2) 如果插入的位置i不合理返回0，表示插入不成功；(3) ，則調(diào)用函數(shù)IncSize(amp。 else return 0。 else { [i1]=e。算法實(shí)現(xiàn)int GetElem_Sq(SqList L,int i,ElemType amp。 //一次增補(bǔ)的容量值 }。2．順序表的結(jié)構(gòu)定義順序表的存儲(chǔ)結(jié)構(gòu)和一維數(shù)組的存儲(chǔ)結(jié)構(gòu)極為相近；但是由于在線(xiàn)性表中允許執(zhí)行插入和刪除等操作，也就是說(shuō)一個(gè)線(xiàn)性表的長(zhǎng)度是可變的，為適應(yīng)這種情況在C++語(yǔ)言中用以下結(jié)構(gòu)類(lèi)型來(lái)表示順序表。L,i,amp。（2）提取GetElem(L,i,amp。按表中的排列順序，元素1是第一個(gè)元素沒(méi)有前驅(qū)，元素10是最后一個(gè)元素沒(méi)有后繼。本章將具體給出線(xiàn)性表的定義、存儲(chǔ)結(jié)構(gòu)、基本操作及其算法實(shí)現(xiàn)，最后給出線(xiàn)性表的應(yīng)用實(shí)例。第2章 線(xiàn)性表及其應(yīng)用第2章 線(xiàn)性表及其應(yīng)用本章學(xué)習(xí)要點(diǎn)◆掌握線(xiàn)性表的邏輯結(jié)構(gòu)及相關(guān)概念。線(xiàn)性表的基本操作主要有插入、刪除和查找等。其中的數(shù)據(jù)元素是整數(shù)，該線(xiàn)性表的長(zhǎng)度為10。L）：構(gòu)造一個(gè)空線(xiàn)性表L的運(yùn)算。（6）刪除DeleteList(amp。設(shè)順序表中元素的首地址為，每個(gè)元素需要占用的字節(jié)數(shù)為，則表中任一元素的存儲(chǔ)位置可用下面的公式算出：。 //當(dāng)前表的存儲(chǔ)容量 int incsize。（3）置表的當(dāng)前容量listsize為動(dòng)態(tài)分配時(shí)的大??；（4）置容量擴(kuò)充值incsize的大小為INCSIZE。e)該操作將順序表L中第i個(gè)元素的值賦值到e中，如果提取成功返回1否則返回0。L,int i,ElemType e){ if(i1||i)return 0。 if(i)return i+1。算法思想(1) 先編寫(xiě)函數(shù)IncSize(amp。 // delete[]。ki。6．刪除操作DeleteList_Sq(amp。 //如果刪除的位置i不合理返回0 e=[i1]。7．求表長(zhǎng)的操作Length_Sq(L)該操作的功能是返回順序表L的長(zhǎng)度，如果當(dāng)前L是空表則返回0。 //輸出元素的值和一個(gè)空格 coutendl。 cout輸入n個(gè)元素的值:\n。 Create_Sq(L)。 switch(num) { case 1: cout輸入位置i