【正文】 iornext==pnextprior D． pnextnext==ppriorprior 18．在循環(huán)鏈表中，將頭指針改設(shè)為尾指針 rear 后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是 ( )。 A．不再需要頭指針了 B．已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū) C．在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi) *D．從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 20．在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是 ( )。 ╳ 2．順序存儲(chǔ)的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话氲脑匦枰苿?dòng)。 ╳ 4．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。 √ 6．在單鏈表中，可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)元素。 √ 8．在線性表的順 序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。 ╳ 10．順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 a1 稱為 _第一個(gè) _結(jié)點(diǎn)， an 稱為 __最后一個(gè) _結(jié)點(diǎn)， i 稱為 ai 在線性表中的 _位置 __。 2．線性結(jié)構(gòu)的基本特征是：若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒(méi)有直接 __前驅(qū) _外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 __前驅(qū) _；除終端結(jié)點(diǎn)沒(méi)有直接 __后繼 _外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 _后繼 __。 4．線性表的邏輯結(jié)構(gòu)是 __線性 _結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的 ___長(zhǎng)度 _。 6．非空的單循環(huán)鏈 表 head 的尾結(jié)點(diǎn) (由指針 p 所指 )滿足 __ pnext= head _____。 8．對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在 p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __O(1)__，在給定值為 x 的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __ O(n)__。 10． 在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng) _一半 _元素，具體移動(dòng)的元素個(gè)數(shù)與 __元素的位置 _有關(guān)。 12．在一個(gè)長(zhǎng)度為 n 的向量中刪除第 i(1≤ i≤ n)個(gè)元素時(shí)，需向前移動(dòng) __ ni __個(gè)元素。 14．在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中， p 指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針 head 可用 p 表示為 head=__ pnextnext ； ___。 16．在單鏈表中，若 p 和 s 是兩個(gè)指針，且滿足 pnext 與 s相同，則語(yǔ)句 pnext=snext的作用是 _刪除 __s 指向的結(jié)點(diǎn)。 19．在雙循環(huán)鏈表中，若要在指 p 所指結(jié)點(diǎn)前插入 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句： snext=p； sprior=pprior； __ ppriornext __=s； pprior=s； 20．在單鏈表中，若要在 p 所指結(jié)點(diǎn)之前插入 s 所指的結(jié)點(diǎn)，可進(jìn)行下列操作： snext=___ pnext __； pnext=s； temp=pdata； pdata=__ sdata ___； sdata=__ temp _； 四、應(yīng)用題 1．描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn) (第一個(gè)元素結(jié)點(diǎn) )。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。 2．何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？ 答：從空間上來(lái)看，當(dāng)線性表的長(zhǎng)度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因 此當(dāng)線性表長(zhǎng)度變化不大、易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。對(duì)于頻繁進(jìn)行插入和刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。具體移動(dòng)的次數(shù)取決于表長(zhǎng)和插入、刪除的結(jié)點(diǎn)的位置。但若設(shè)置的是頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為 O(n)。雙鏈表上刪除 p 所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1)，單循環(huán)鏈表上刪除 p 所指向的結(jié)點(diǎn)的 時(shí)間復(fù)雜度為 O(n)。amp。 while(pnext) p=pnext； pnext=q。 7．如果有 n 個(gè)線性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長(zhǎng)度也會(huì)自動(dòng)地改變。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配，不能隨著線性表長(zhǎng)度的改變而變化。 8．若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 五、 算法設(shè)計(jì)題 假設(shè)算法中用到的順序表和鏈表結(jié)構(gòu)如下： define maxsize 100。 int length } SeqList。 struct node2 *next } LinkedList 。 答： (1)順序表的就地逆置 分析：分別用兩個(gè)整型變量指向順序表的兩端，同時(shí)向中間移動(dòng)，移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示的元素的值。 Ldata[i]=[j]。 } } (2)鏈表的就地逆置 分析：本算法的思想是逐個(gè)地把 L 的當(dāng)前元素 r 插入到新的鏈表頭部。 答 ：分析：先找到 x 的正確插入位置，然后將大于 x 的元素從后向前依次向下移動(dòng)，最后將 x 插入到其位置上，同時(shí)順序表長(zhǎng)度增 1。 while((i=Llength1)amp。(x=Ldata[i])) i++； ／／找正確的插入位置 for(k=Llength1。 答：分析：此問(wèn)題的關(guān)鍵是在鏈表中找到 x 的插入位置，因此需要兩個(gè)指針一前一后地依次向后移動(dòng)。amp。 答：分析：對(duì)不帶頭結(jié)點(diǎn)的鏈表操作時(shí)，要注意對(duì)第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同。 while(p!=NULLamp。ji1) ／／找到第 i1 個(gè)元素 {p=p— next； j++； } if(i=0||p==NULL) printf(”插入位置不正確＼ n” )； else {q=(LinkedList*)malloc(sizeof(LinkedList))； q— data=x； 7 if(i==1) {q— next=L； L=q； } ／／在第一個(gè)元素之前插入 else{q— next=p— next； p— next=q； } ／／在其他位置插入 } } 5．設(shè) A、 B 是兩個(gè)線性表，其表中元素遞增有序，長(zhǎng)度分別為 m 和 n。 答： (1)分析：用三個(gè)變量 i、 j、 k 分別指示 A、 B、 C 三個(gè)順序表的當(dāng)前位置，將 A、 B 表中較小的元素寫入 C 中，直到有一個(gè)表先結(jié)束。 SeqList *Seqmerge(SeqList A， SeqList B， SeqList *C){／／有序順序表 A 和 B 歸并成有序順序表 C i=0； j=0； k=0； ／／ i， i， k 分別為順序表 A， B， C 的下標(biāo) while(imamp。jn) {if([i][j]) ／／ A 中當(dāng)前元素較小 {Cdata[k]=[il； i++； ] else {Cdata[k]=[j]。k++； } ／／ B 表長(zhǎng)度大于 A 表 else for(t=i； tm； t++) {Cdata[k]=[t]； k++； } ／／ A 表長(zhǎng)度大于 B 表 Clength=m+n； return C。amp。 6．設(shè)指針 la 和 lb 分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)，設(shè)計(jì)從表 la 中刪除第 i 個(gè)元素起共 len 個(gè)元素，并將這些元素插入到 lb 中第 j 個(gè)結(jié)點(diǎn)之前的算法。然后在 lb 中找到第 j 個(gè)結(jié)點(diǎn)，將 p 所指向的 la表中的第 i個(gè)及 q所指向的最后一個(gè)共 len個(gè)結(jié)點(diǎn)插入到 lb中。amp。 k++； } if(!p) exit(0)； q=p； k=l； ／／ p 指向 la 表中第 i 個(gè)結(jié)點(diǎn) while(qamp。klen) {q=q— next； k++； } ／／查找 la 表中第 i+len1 個(gè)結(jié)點(diǎn) if(!q) exit(0)； if(pre==la) la=q— next； ／／ i=1 的情況 else pre— next=q— next； ／／完成刪除 ／／將從 la 中刪除的結(jié)點(diǎn)插入到 lb 中 if(j==1) {qnext=lb； lb=p； } ／／ j=1 時(shí) 8 else { r=lb。amp。 答： LinkedList delete(LinkedList *L， int min， int max) {／／刪除遞減有序單鏈表 L 中值大于 min 且小于 max 的結(jié)點(diǎn) q=L； if(minmax) {printf(” minmax＼ n” )； exit(0)； } else p=L— next； ／／ q 始終指向 p 的前驅(qū) while(p— data=max) ／／當(dāng)前元素大于或等于 max，則 p、 q 依次向后移動(dòng) {q=p； p=p— next； } while((p!=NULL)amp。(p 一 datamin)) {／／當(dāng)前元素的值比 min 大同時(shí)比 max 小，刪除 p 指向的結(jié)點(diǎn) q— next=p— next， free(p)； p=q— next； } return L； }． 8．編寫一個(gè)算法將一個(gè)頭結(jié)點(diǎn)指針為 pa 的單鏈表 A 分解成兩個(gè)單鏈表 A 和 B，其頭結(jié)點(diǎn)指針?lè)謩e為 pa和 pb，使得 A 鏈表中含有原鏈表 A 中序號(hào)為奇數(shù)的元素，而 B 鏈表中含有原鏈表 A 中序號(hào)為偶數(shù)的元素，且保持原來(lái)的相對(duì)順序。 void depose(LinkedList *A， LinkedList *B) {／／單鏈表 A 分解成元素序號(hào)為奇數(shù)的單鏈表 A 和元素序號(hào)為偶數(shù)的單鏈表 B p=Anext； B=(LinkedList*)malloc(sizeof(LinkedList))； r=B； while(p!=NULLamp。pnext!=NULL) {q=p— next； ／／ q 指向偶數(shù)序號(hào)的結(jié)點(diǎn) p— next=q— next； ／／將 q 從 A 表中刪除 r— next=q； ／／將 q 結(jié)點(diǎn)鏈接到 B 鏈表的末尾 r=q； ／／ r 總是指向 B 鏈表的最后 — 用順序表實(shí)現(xiàn)并寫出 C 的算法。 SeqLiSt *intersection(SeqList A， SeqList B， SeqList *C) {／／求元素依值遞增有序排列的順序表 A、 B 的交集 C i=0； j=0； k=0； while((i=)amp。(j=)) {if([i]==[j]) ／／找到值相同的元素 {Cdata[k]=[i]； ／／相同元素寫入 C 表中 k++； i++； j++； } else if([i][j]) i++；／／ A、 B 表當(dāng)前元素不等，值較小的下標(biāo)增 1 else j++； } Clength=k； return C； } 9 11．假設(shè)在長(zhǎng)度大于 1 的 單循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。 答：分析：因?yàn)榧炔恢来藛窝h(huán)鏈表的頭指針，也不知道其尾指針，所以找 s 的前驅(qū)就只能從 s 開(kāi)始，順次向后尋找。 答： int number(Linkedlist *head) {／／計(jì)算單循環(huán)鏈表中結(jié)點(diǎn)的個(gè)數(shù) p=head— next； i=0； while(p!=head) {i++； p=pnext； } return i； } 13．已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素 (如：字母字符、數(shù)字字符和其他字符 )，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的 線性表，使得每個(gè)表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。 q 指向 p 的下一個(gè)結(jié)點(diǎn)，根據(jù) *p 的數(shù)據(jù)域的值將其插入到不同的鏈表上。 void change(LinkedList *L， LinkedList *pa， LinkedList *pb， LinkedList *pc) {／／分解含有三類字符的單鏈表為三個(gè)以循環(huán)鏈表表 示的線性表，使其分別含有三類字符 p=L— next； pa=L； pa— next=pa； ／／分別構(gòu)造三個(gè)單循環(huán)鏈表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； pb— next=pb； pc— next=pc； while(p!=L) {q=p— next；amp。amp。試對(duì)順序表編寫實(shí)現(xiàn)上述操作的算法