《大數(shù)據(jù)結(jié)構(gòu)》第二章線性表習(xí)的題目

《《大數(shù)據(jù)結(jié)構(gòu)》第二章線性表習(xí)的題目》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》第二章線性表習(xí)的題目（9頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、實(shí)用標(biāo)準(zhǔn)文案 《數(shù)據(jù)結(jié)構(gòu)》 第二章 線性表習(xí)題 一、單項(xiàng)選擇題 1. 線性表是 ________。 A．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空 C．一個(gè)無限序列，可以為空 D．一個(gè)無限序列，不可以為空 2. 在一個(gè)長(zhǎng)度為 n 的順序表中刪除第 i 個(gè)元素 (0<=i<=n) 時(shí)，需向前移動(dòng) 個(gè)元素。 A． n-i B． n-i+l C． n-i-1 D． i 3. 線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址________。 A．必須是連續(xù)的 B．一定是不連續(xù)的 C．部分地址必須是連續(xù)的 D．連續(xù)與否均可

2、以 4. 從一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于 x 的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較 ________個(gè)元素結(jié)點(diǎn)。 A． n/2 B． n C．（ n+1）/2 D．（ n-1 ）/2 5. 在雙向循環(huán)鏈表中，在 p 所指的結(jié)點(diǎn)之后插入 s 指針?biāo)傅慕Y(jié)點(diǎn)，其操作是 ____。 A． p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C．

3、 p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 設(shè)單鏈表中指針 p 指向結(jié)點(diǎn) m，若要?jiǎng)h除 m之后的結(jié)點(diǎn) （若存在），則需修改指針的操作為 ________。 A． p->next=p->next->next; B ．p=p->next; C ． p=p->next->next; D． p->next=p; 7. 在一個(gè)長(zhǎng)度為 n 的順序表

4、中向第 i 個(gè)元素 (0< inext=p->next; p->next=s B ．q->next=s; s->next=p C． p->next=s->next; s->next=p D ．p->next=s; s->next=q 9. 以下關(guān)于線性表的說法不正確的

5、是______ 。 A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。 B．線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。 C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。 D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 10. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 _______的存儲(chǔ)結(jié)構(gòu)。 A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取 11. 在順序表中，只要知道 _______ ，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。 A．基地址 B ．結(jié)點(diǎn)大小 C ．向

6、量大小 D ．基地址和結(jié)點(diǎn)大小 12. 在等概率情況下，順序表的插入操作要移動(dòng)______結(jié)點(diǎn)。 A．全部 B ．一半 C ．三分之一 D ．四分之一 13. 在 ______運(yùn)算中，使用順序表比鏈表好。 A．插入 B ．刪除 C ．根據(jù)序號(hào)查找 D ．根據(jù)元素值查找 14. 在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是 _______。 A． O(1) B ．O(n) C ． O(n2) D ．O(log 2n) 15. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)? A, B, C, D,

7、 E, 下列是不可能的出棧序列 __________ 。 A．A, B, C, D, E B ．B, C, D, E, A C ．E,A,B,C,D D ．E, D, C, B, A 16. 在一個(gè)具有 n 個(gè)單元的順序棧中，假定以地址低端（即 0 單元）作為棧底，以 top 作為棧頂指針， 當(dāng)做出棧處理時(shí)， top 變化為 ______ 。 A． top 不變 B． top=0 C． top-- D． top++ 17. 向一個(gè)棧頂指針為 hs 的鏈棧中插入一個(gè) s 結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 ____

8、__。 A． hs->next=s; B ． s->next=hs; hs=s; C． s->next=hs->next;hs->next=s; D ． s->next=hs; hs=hs->next; 18. 在具有 n 個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定 front 和 rear 分別為隊(duì)頭指針和隊(duì)尾指針， 則判 斷隊(duì)滿的條件為 ________。 A． rear ％n= = front B ．（ front+l ）％ n= = rear C． rear ％n -1= = front D ． (r

9、ear+l) ％ n= = front 19. 在具有 n 個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定 front 和 rear 分別為隊(duì)頭指針和隊(duì)尾指針， 則判 斷隊(duì)空的條件為 ________。 A． rear ％n= = front B ． front+l= rear C ． rear= = front D ． (rear+l) ％ n= front 20. 在一個(gè)鏈隊(duì)列中， 假定 front 和 rear 分別為隊(duì)首和隊(duì)尾指針， 則刪除一個(gè)結(jié)點(diǎn)的操作為 ________。 A． front=front->next B ． rear=rear-

10、>next C． rear=front->next D ． front=rear->next 二、填空題 1. 線性表是一種典型的 _________結(jié)構(gòu)。 2. 在一個(gè)長(zhǎng)度為 n 的順序表的第 i 個(gè)元素之前插入一個(gè)元素，需要后移 ____個(gè)元素。 3. 順序表中邏輯上相鄰的元素的物理位置________。 4. 要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需 _______一個(gè)位置，移動(dòng)過程是 從 _______向 _______依次移動(dòng)每一個(gè)元素。 5. 在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過 _______決定

11、的；在線性表的鏈接存儲(chǔ)中，元 素之間的邏輯關(guān)系是通過 _______決定的。 6. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向 _______ 結(jié)點(diǎn)，另一個(gè)指向 _______結(jié)點(diǎn)。 7. 當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)， 則采用 _______存儲(chǔ)結(jié)構(gòu)為宜。 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用 _______存儲(chǔ)結(jié)構(gòu)為宜。 8. 順序表中邏輯上相鄰的元素， 物理位置 ____相鄰，單鏈表中邏輯上相鄰的元素， 物理位置 ____相鄰。 9.

12、 線性表、棧和隊(duì)列都是 _______結(jié)構(gòu)，可以在線性表的 ______位置插入和刪除元素；對(duì)于棧只能在 _______ 位置插入和刪除元素；對(duì)于隊(duì)列只能在 _______位置插入元素和在 _______位置刪除元素。 10. 根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為 _________和 _______；而根 據(jù)指針的聯(lián)接方式，鏈表又可分為 ________和_________ 。 11. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 ________。 12. 對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn) p 后插入一個(gè)新

13、結(jié)點(diǎn)的時(shí)間復(fù)雜度為 ______，在 給定值為 x 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 _______。 13. 對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)， 應(yīng)先判別棧是否為 _______，作退棧運(yùn)算時(shí)， 應(yīng)先判別棧是否為 _______， 當(dāng)棧中元素為 m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為 _______。為了增加內(nèi)存空間 的利用率和減少發(fā)生上溢的可能性， 由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)， 應(yīng)將兩棧的 _______分別設(shè) 在這片內(nèi)存空間的兩端，這樣只有當(dāng) _______ 時(shí)才產(chǎn)生上溢。 14. 設(shè)有一空棧，現(xiàn)有輸入序列 1， 2，

14、3， 4，5，經(jīng)過 push, push, pop, push, pop, push, push 后， 輸出序列是 _________。 15. 無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為 __________。 三、簡(jiǎn)答題 1. 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。 2. 線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？ 3. 對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)， 如果有 n 個(gè)線性表同時(shí)并存， 而且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā) 生變化，線性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？

15、 4. 對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說明理由。 5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么 ? 6. 假定有四個(gè)元素 A, B, C, D 依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。 7. 什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。 8. 下述算法的功能是什么 ? LinkList *Demo(LinkList *L) { // L是無頭結(jié)點(diǎn)的單鏈表 LinkList *q,*p; if(L&

16、&L->next) { q=L; L=L->next; p=L; while (p->next) p=p->next; p->next=q; q->next=NULL; } return (L); } 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 四、算法設(shè)計(jì)題 1. 設(shè)計(jì)在無頭結(jié)點(diǎn)的單鏈表中刪除第i 個(gè)結(jié)點(diǎn)的算法。 2. 在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng) ListLength(L) 運(yùn)算。 3. 設(shè)計(jì)將帶表頭的鏈表逆置算法。 4. 假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head ，每個(gè)結(jié)點(diǎn)含三個(gè)域：

17、 data, next 和 prior 。其中 data 為整型數(shù)域， next 和 prior 均為指針域?，F(xiàn)在所有結(jié)點(diǎn)已經(jīng)由 next 域連接起來，試編一個(gè)算法， 利用 prior 域（此域初值為 NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來。 5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。 試編寫一個(gè)刪除表中所有 值大于 min 且小于 max 的元素（若表中存在這樣的元素）的算法。 6. 已知線性表的元素是無序的， 且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。 設(shè)計(jì)一個(gè)刪除表中所有值小于 max 但大于 min 的元

18、素的算法。 7. 假定用一個(gè)單循環(huán)鏈表來表示隊(duì)列（也稱為循環(huán)隊(duì)列） ，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針， 試編寫下列各種運(yùn)算的算法： （ 1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為 x 的結(jié)點(diǎn)； （ 2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。 8. 設(shè)順序表 L 是一個(gè)遞減有序表，試寫一算法，將 x 插入其后仍保持 L 的有序性。

19、 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 習(xí)題 2 參考答案 一、單項(xiàng)選擇題 1．A 2 ．A 3 ．D4．C5．D6．A 7 ．B 8 ．B 9 ．C 10 ．A 11 ．D12．B 13 ．C 14 ．B 15．C 16 ．C 17 ．B 18 ．D 19 ．C 20． A 二、填空題 1．線性2 ． n-i+1 3．相鄰 4 ．前移，前，后 5 ．物理存儲(chǔ)位置，鏈域的指針值 6．前趨，后繼 7 ．順序，鏈接 8 ．一定，不一定 9 ．線性，任何，棧頂，隊(duì)尾，隊(duì)頭 10．單

20、鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表 11．使空表和非空表統(tǒng)一；算法處理一致 12． O(1) ， O(n) 13．棧滿，棧空， m，棧底，兩個(gè)棧的棧頂在棧空間的某一位置相遇 14． 2、 3 15 ．O(1) 三、簡(jiǎn)答題 1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)； 表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。 若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。 2．線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。 線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存

21、取數(shù) 據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。 3．應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。 4．應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)， 因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成

22、正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。 5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表 的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便， 設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表， 其尾指針為 rear ，則開始結(jié)點(diǎn)和終 端結(jié)點(diǎn)的位置分別是 rear->next->next 和 rear, 查找時(shí)間都是 O(1) 。若用頭指針來表示該鏈表， 則查找終端結(jié)點(diǎn)的時(shí)間為 O(n) 。 6．共有 14 種可能的出棧序列，即為

23、： ABCD, ABDC， ACBD, ACDB， BACD，ADCB， BADC， BCAD, BCDA，BDCA,CBAD, CBDA， CDBA, DCBA 7．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為 front ，隊(duì)尾指針為 rear ，隊(duì)列的容量（即存儲(chǔ)的空間大 ?。? maxnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若 rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象， 此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間， 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 但元素卻不能入隊(duì)， 一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)

24、或操作方式的選擇不當(dāng)所致， 可以用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法： （ 1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。 （ 2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使 front 指針指向隊(duì)列中的第一個(gè)位置。 第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前

25、，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。 8．該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。 四、算法設(shè)計(jì)題 1 ．算法思想為： （ 1）應(yīng)判斷刪除位置的合法性，當(dāng)i<0 或 i>n-1 時(shí)，不允許進(jìn)行刪除操作； （ 2）當(dāng) i=0 時(shí)，刪除第一個(gè)結(jié)點(diǎn)： （ 3）當(dāng)０

26、除第i 個(gè)結(jié)點(diǎn) LinkList *p,*s; int j; if(i<0) printf("Can't delete"); else if(i= =0) { s=q; q=q->next; free(s); } else { j=0; s=q; while((jnext; j++; } if (s= =NULL) printf("Cant't delete"); else { p->next=s->next; free(s); } } } 2．

27、由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。 算法描述如下： int ListLength ( LinkList *L ) { // 求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng) 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 int len=0; ListList *p; p=L; while ( p->next!=NULL ) { p=p->next; len++; } return (len); } 3．設(shè)單循環(huán)鏈表的頭指針為 head ，類型為 LinkList 。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，

28、使 其原前趨結(jié)點(diǎn)成為后繼。如要更改 q 結(jié)點(diǎn)的指針域時(shí)，設(shè) s 指向其原前趨結(jié)點(diǎn)， p 指向其原后繼結(jié) 點(diǎn)，則只需進(jìn)行 q->next=s; 操作即可，算法描述如下： void invert(LinkList *head) { // 逆置 head 指針?biāo)赶虻膯窝h(huán)鏈表 linklist *p, *q, *s; q=head; p=head->next; while (p!=head) // 當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; } 4．定義類型 L

29、inkList 如下： typedef struct node { int data; struct node *next,*prior; }LinkList; 此題可采用插入排序的方法，設(shè) p 指向待插入的結(jié)點(diǎn)，用 q 搜索已由 prior 域鏈接的有序表找到合 適位置將 p 結(jié)點(diǎn)鏈入。算法描述如下： insert (LinkList *head) { LinkList *p,*s,*q; p=head->next; //p 指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn) while(p!=NULL) { s=head; // s指向 q

30、 結(jié)點(diǎn)的前趨結(jié)點(diǎn) q=head->prior; //q指向由 prior 域構(gòu)成的鏈表中待比較的結(jié)點(diǎn) while((q!=NULL) && (p->data>q->data)) // 查找插入結(jié)點(diǎn) p 的合適插入位置 { s=q; q=q->prior; } s->prior=p; p->prior=q; // 結(jié)點(diǎn) p 插入到結(jié)點(diǎn) s 和結(jié)點(diǎn) q 之間 p=p->next; } } 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 5．算法描述如下： delete(LinkList *head, int max, i

31、nt min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next; while((p!=NULL) && (p->data<=min)) { q=p; p=p->next;} while((p!=NULL) && (p->datanext; q->next=p; } } 6．算法描述如下： delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head;

32、 p=head->next; while (p!=NULL) if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } } 7．本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下： （ 1）插入（即入隊(duì)）算法： insert(LinkList *rear, elemtype x) { // 設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為re

33、ar,x 為待插入的元素 LinkList *p; p=(LinkList *)malloc(sizeof(LinkList)); if(rear= =NULL) // 如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn) { rear=p; rear->next=p; // 鏈接成循環(huán)鏈表 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 } else // 否則在隊(duì)尾插入 p 結(jié)點(diǎn) { p->next=rear->next; rear->next=p; rear=p; } } （ 2）刪除（即出隊(duì)）算法： delet

34、e(LinkList *rear) { // 設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為 rear if (rear= =NULL) // 空隊(duì) printf("underflow\n"); if(rear->next= =rear) // 隊(duì)中只有一個(gè)結(jié)點(diǎn) rear=NULL; else rear->next=rear->next->next; //rear->next 指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn) } 8．只要從終端結(jié)點(diǎn)開始往前找到第一個(gè)比 x 大 ( 或相等 ) 的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法 描述如下： int Insert

35、DecreaseList( SqList *L, elemtype x ) { int i; if ( (*L).len>= maxlen) { printf( “overflow"); return(0); } for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比較并移動(dòng)元素 (*L).elem[ i ] =x; (*L).len++; return(1); } 精彩文檔