計(jì)算機(jī)軟件基礎(chǔ)習(xí)題及參考答案

1、<p><b>　　習(xí)題一</b></p><p>　　1.什么是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)對(duì)算法有什么影響？請(qǐng)舉例說(shuō)明。</p><p>　　2.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式主要有哪兩種？它們之間的本質(zhì)區(qū)別是什么？</p><p>　　3.設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語(yǔ)句的執(zhí)行次數(shù)。</p>

2、<p>　　(1)for (int i = 1; i <= n; i++) </p><p>　　for (int j = 1; j <= n; j++) {</p><p>　　c[i][j] = 0.0; </p><p>　　for (int k = 1; k <= n; k++)</p><p>　　

3、c[i][j] = c[i][j] + a[i][k] * b[k][j];</p><p><b>　　} </b></p><p>　　(2)x = 0; y = 0;</p><p>　　for (int i = 1; i <= n; i++) </p><p>　　for (int j = 1

4、; j <= i; j++)</p><p>　　for (int k = 1; k <= j; k++)</p><p>　　x = x + y;</p><p>　　(3)int i = 1, j = 1; </p><p>　　while (i<=n && j<=n) {</p>

5、<p>　　i = i + 1; j = j + i; </p><p><b>　　} </b></p><p>　　(4)*int i =1;</p><p><b>　　do{</b></p><p>　　for (int j = 1; j <= n; j++) <

6、/p><p>　　i = i + j;</p><p>　　}while(i<100 + n);</p><p>　　4.試編寫(xiě)一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個(gè)數(shù)組元素中，0 n arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)n>arraySize或者對(duì)于某一個(gè)k (0 k n)，使得

7、k!*2k > maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式：</p><p>　　(1) 用printf顯示錯(cuò)誤信息及exit(1)語(yǔ)句來(lái)終止執(zhí)行并報(bào)告錯(cuò)誤；</p><p>　　(2) 用返回整數(shù)函數(shù)值0, 1來(lái)實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；</p><p>　　(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來(lái)區(qū)別是正常返回還是某

8、種錯(cuò)誤返回。</p><p>　　試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。</p><p>　　5.設(shè)有一個(gè)線性表 (a0, a1, …, an-2, an-1) 存放在一個(gè)一維數(shù)組A[arraySize]中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫(xiě)一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為 (an-1, an-2, …, a1, a0)。最后分析此算法的時(shí)間復(fù)雜度

9、及空間復(fù)雜度。</p><p>　　6.順序表的插入和刪除要求仍然保持各個(gè)元素原來(lái)的次序。設(shè)在等概率情形下, 對(duì)有127個(gè)元素的順序表進(jìn)行插入, 平均需要移動(dòng)多少個(gè)元素? 刪除一個(gè)元素, 又平均需要移動(dòng)多少個(gè)元素?</p><p>　　7.利用順序表的操作，實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時(shí)間復(fù)雜度，并分析(2)與(3)的時(shí)間復(fù)雜度出現(xiàn)差異的原因。</p><p&

10、gt;　　(1) 從順序表中刪除具有給定值x的所有元素。</p><p>　　(2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。</p><p>　　(3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。</p><p>　　(4) 將兩個(gè)有序順序表la,lb合并成一個(gè)新的有序順序表lc。</p><p

11、>　　(5) 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。</p><p>　　8.線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：</p><p>　　(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?</p><p>　　(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用哪種存儲(chǔ)表示？為什么？<

12、;/p><p>　　(3) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？</p><p>　　9.試寫(xiě)出計(jì)算線性鏈表長(zhǎng)度的算法。</p><p>　　10.設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最

13、后一個(gè)結(jié)點(diǎn)。</p><p>　　11.設(shè)有一線性鏈表，其結(jié)點(diǎn)值均為整數(shù)。試將該線性鏈表分解為兩個(gè)線性鏈表，其中一鏈表中的結(jié)點(diǎn)值均為負(fù)整數(shù)，而另一鏈表中結(jié)點(diǎn)的值均為正整數(shù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn)。</p><p>　　12．設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間

14、, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。</p><p>　　13．設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。</p><p>　　14.在一個(gè)循環(huán)鏈表中尋找值為x的結(jié)點(diǎn)，并將該結(jié)點(diǎn)移到第一個(gè)結(jié)點(diǎn)之前。

15、</p><p>　　15.對(duì)于下面的每一步，畫(huà)出棧元素和棧頂指針的示意圖：</p><p><b>　　（1）棧初始化；</b></p><p><b>　?。?）元素x入棧；</b></p><p><b>　?。?）元素y入棧；</b></p><p&

16、gt;<b>　?。?）出棧</b></p><p><b>　?。?）棧初始化</b></p><p><b>　?。?）元素z入棧</b></p><p>　　16.鐵路進(jìn)行列車(chē)調(diào)度時(shí), 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問(wèn)：</p><p>　　(1) 設(shè)有編號(hào)

17、為1,2,3,4,5,6的六輛列車(chē), 順序開(kāi)入棧式結(jié)構(gòu)的站臺(tái), 則可能的出棧序列有多少種?</p><p>　　(2) 若進(jìn)站的六輛列車(chē)順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說(shuō)明為什么不能; 如果能, 說(shuō)明如何得到(即寫(xiě)出"進(jìn)棧"或"出棧"的序列)。</p><p>　　1

18、7.試證明：若借助?？捎奢斎胄蛄?, 2, 3, …, n得到一個(gè)輸出序列p1, p2, p3, …, pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)</p><p>　　18.將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1

19、時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top[0]增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top[1]減1得到新的棧頂位置。當(dāng)top[0]+1 == top[1]時(shí)或top[0] == top[1]-1時(shí)，?？臻g滿(mǎn)，此時(shí)不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類(lèi)定義，并實(shí)現(xiàn)判?？铡⑴袟M(mǎn)、插入、刪除算法。&

20、lt;/p><p>　　19.改寫(xiě)順序棧的進(jìn)棧成員函數(shù)Push(x)，要求當(dāng)棧滿(mǎn)時(shí)執(zhí)行一個(gè)stackFull( )操作進(jìn)行棧滿(mǎn)處理。其功能是：動(dòng)態(tài)創(chuàng)建一個(gè)比原來(lái)的棧數(shù)組大二倍的新數(shù)組，代替原來(lái)的棧數(shù)組，原來(lái)?xiàng)?shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。</p><p>　　20.根據(jù)教案中給出的優(yōu)先級(jí)，回答以下問(wèn)題：</p><p>　　(1) 在表達(dá)式求值的過(guò)程中，

21、如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，問(wèn)操作數(shù)棧(NS)中最多可存入多少個(gè)元素？</p><p>　　(2) 如果表達(dá)式e含有n個(gè)運(yùn)算符，且括號(hào)嵌套的最大深度為6層，問(wèn)棧中最多可存入多少個(gè)元素？</p><p>　　21.表達(dá)式的中綴表示為a * x - b / x^2，試?yán)脳⑺臑楹缶Y表示ax * bx2^/ -。寫(xiě)出轉(zhuǎn)換過(guò)程中棧的變化。(^表示乘方運(yùn)算)</p><

22、;p>　　22.設(shè)循環(huán)隊(duì)列的容量為70（序號(hào)從1到70），經(jīng)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，有：</p><p>　?。?）front=15，rear=46；</p><p>　　（2）front=45，rear=10</p><p>　　問(wèn)在上述兩種情況下，循環(huán)隊(duì)列中各有多少個(gè)元素？</p><p>　　23.設(shè)用鏈表表示一個(gè)雙端隊(duì)列，要求

23、可在表的兩端插入，但限制只能在表的一端刪除。試編寫(xiě)基于此結(jié)構(gòu)的隊(duì)列的插入(enqueue)和刪除(dequeue)算法，并給出隊(duì)列空和隊(duì)列滿(mǎn)的條件。</p><p><b>　　習(xí)題2</b></p><p>　　1．列出右圖所示二叉樹(shù)的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)和每個(gè)結(jié)點(diǎn)的層次。</p><p>　　2．使用 (1) 順序表示和 (2) 二叉鏈表表示法

24、，分別畫(huà)出上圖所示二叉樹(shù)的存儲(chǔ)表示。</p><p>　　3．在結(jié)點(diǎn)個(gè)數(shù)為n (n>1)的各棵樹(shù)中，高度最小的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？</p><p>　　4．試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。</p><p>　　5．如果一棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn)

25、, 有n2個(gè)度為2的結(jié)點(diǎn), … , nm個(gè)度為m的結(jié)點(diǎn), 試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)? 試推導(dǎo)之。</p><p>　　6．若用二叉鏈表作為二叉樹(shù)的存儲(chǔ)表示，試針對(duì)以下問(wèn)題編寫(xiě)遞歸算法：</p><p>　　(1) 統(tǒng)計(jì)二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)。</p><p>　　(2) 以二叉樹(shù)為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女。</p><p>　　(3)

26、 求二叉樹(shù)的深度。</p><p>　　7．一棵高度為h的滿(mǎn)k叉樹(shù)有如下性質(zhì): 第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn), 其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù), 如果按層次自頂向下, 同一層自左向右, 順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào), 試問(wèn):</p><p>　　(1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少?</p><p>　　(2) 編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少?</p&

27、gt;<p>　　(3) 編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少?</p><p>　　(4) 編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是什么? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少?</p><p>　　(5) 若結(jié)點(diǎn)個(gè)數(shù)為 n, 則高度h是n 的什么函數(shù)關(guān)系?</p><p>　　8．請(qǐng)畫(huà)出下圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù)。</p><p>

28、;　　9．已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫(huà)出這棵二叉樹(shù)。</p><p>　　10．給定權(quán)值集合{15, 03, 14, 02, 06, 09, 16, 17}, 構(gòu)造相應(yīng)的霍夫曼樹(shù), 并計(jì)算它的帶權(quán)路徑長(zhǎng)度。</p><p><b>　　習(xí)題三</b></p><p>　　1

29、. 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫(huà)出對(duì)其進(jìn)行折半查找時(shí)的二叉查找樹(shù), 并計(jì)算查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。</p><p>　　2. 若對(duì)有n個(gè)元素的有序順序表和無(wú)序順序表進(jìn)行順序查找, 試就下列三種情況分別討論兩者在等查找概率時(shí)的平均查找長(zhǎng)度是否相同?&l

30、t;/p><p><b>　　(1) 查找失敗;</b></p><p>　　(2) 查找成功, 且表中只有一個(gè)關(guān)鍵碼等于給定值k的對(duì)象;</p><p>　　(3) 查找成功, 且表中有若干個(gè)關(guān)鍵碼等于給定值k的對(duì)象, 要求一次查找找出所有對(duì)象。</p><p>　　3. 設(shè)有10000個(gè)記錄對(duì)象, 通過(guò)分塊劃分為若干子表

31、并建立索引, 那么為了提高查找效率, 每一個(gè)子表的大小應(yīng)設(shè)計(jì)為多大? </p><p>　　4. 設(shè)散列表為HT[13], 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對(duì)下列關(guān)鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。</p><p>　　(1) 采用線性探測(cè)法尋找下一個(gè)空位, 畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下

32、查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。</p><p>　　(2) 采用隨機(jī)探測(cè)法尋找下一個(gè)空位, 隨機(jī)數(shù)序列為：5，4，2，7，3，6，…。畫(huà)出相應(yīng)的散列表, 并計(jì)算等概率下查找成功的平均查找長(zhǎng)度。</p><p>　　5. 設(shè)有150個(gè)記錄要存儲(chǔ)到散列表中, 要求利用線性探查法解決沖突, 同時(shí)要求找到所需記錄的平均比較次數(shù)不超過(guò)2次。試問(wèn)散列表需要設(shè)計(jì)多大？ 設(shè)是散列表的裝

33、載因子，則有</p><p>　　6. 設(shè)有15000個(gè)記錄需放在散列文件中，文件中每個(gè)桶內(nèi)各頁(yè)塊采用鏈接方式連結(jié)，每個(gè)頁(yè)塊可存放30個(gè)記錄。若采用按桶散列，且要求查找到一個(gè)已有記錄的平均讀盤(pán)時(shí)間不超過(guò)1.5次，則該文件應(yīng)設(shè)置多少個(gè)桶？ 已知，鏈地址法的平均查找長(zhǎng)度ASL=1+α/2</p><p>　　7. 設(shè)待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*,

34、 20, 6, 18}, 試分別寫(xiě)出使用以下排序方法每趟排序后的結(jié)果。并說(shuō)明做了多少次排序碼比較。</p><p>　　(1) 直接插入排序(2) 希爾排序(增量為5,2,1)(3) 冒泡排序</p><p>　　(4) 快速排序(5) 直接選擇排序(6) 堆排序</p><p>　　(7) 二路歸并排序</p><

35、;p>　　8. 在起泡排序過(guò)程中，什么情況下排序碼會(huì)朝向與排序相反的方向移動(dòng)，試舉例說(shuō)明。在快速排序過(guò)程中有這種現(xiàn)象嗎？</p><p>　　9. 試設(shè)計(jì)一個(gè)算法, 使得在O(n)的時(shí)間內(nèi)重排數(shù)組, 將所有取負(fù)值的排序碼排在所有取正值(非負(fù)值)的排序碼之前。</p><p>　　提示：對(duì)比快速排序的第一趟排序，此處，以0為控制關(guān)鍵字。</p><p>　　10

36、. 手工跟蹤對(duì)以下各序列進(jìn)行堆排序的過(guò)程。給出形成初始堆及每選出一個(gè)排序碼后堆的變化。</p><p>　　(1) 按字母順序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan </p><p>　　(2) 按數(shù)值遞增順序排序：26, 33, 35, 29, 19, 12, 22 </p><p>　　(

37、3) 同樣7個(gè)數(shù)字，換一個(gè)初始排列，再按數(shù)值的遞增順序排序：12, 19, 33, 26, 29, 35, 22</p><p>　　11. 希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說(shuō)明。</p><p>　　12. 在已排好序的序列中，一個(gè)對(duì)象所處的位置取決于具有更小排序碼的對(duì)象的個(gè)數(shù)。基于這個(gè)思想，可得計(jì)數(shù)排序方法。該方法在聲明對(duì)象時(shí)為每個(gè)對(duì)象增加一個(gè)計(jì)數(shù)域

38、count，用于存放在已排好序的序列中該對(duì)象前面的對(duì)象數(shù)目，最后依count域的值，將序列重新排列，就可完成排序。試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)計(jì)數(shù)排序。并說(shuō)明對(duì)于一個(gè)有n個(gè)對(duì)象的序列，為確定所有對(duì)象的count值，最多需要做n(n-1)/2次排序碼比較。</p><p><b>　　習(xí)題解答</b></p><p>　　3.設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語(yǔ)句的執(zhí)

39、行次數(shù)。</p><p>　　(1)for (int i = 1; i <= n; i++) </p><p>　　for (int j = 1; j <= n; j++) {</p><p>　　c[i][j] = 0.0; </p><p>　　for (int k = 1; k <= n; k++)</p>

40、;<p>　　c[i][j] = c[i][j] + a[i][k] * b[k][j];</p><p><b>　　} </b></p><p>　　(2)x = 0; y = 0;</p><p>　　for (int i = 1; i <= n; i++) </p><p>　　

41、for (int j = 1; j <= i; j++)</p><p>　　for (int k = 1; k <= j; k++)</p><p>　　x = x + y;</p><p>　　(3)int i = 1, j = 1; </p><p>　　while (i<=n && j<=n

42、) {</p><p>　　i = i + 1; j = j + i; </p><p><b>　　} </b></p><p>　　(4)*int i =1;</p><p><b>　　do{</b></p><p>　　for (int j = 1; j <

43、= n; j++) </p><p>　　i = i + j;</p><p>　　}while(i<100 + n);</p><p><b>　　【解答】</b></p><p><b>　　(1) </b></p><p><b>　　(2) </

44、b></p><p>　　(3)i = 1時(shí)，i = 2，j = j + i = 1 + 2 = 2 + 1，</p><p>　　i = 2時(shí)，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，</p><p>　　i = 3時(shí)，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 +

45、2 + 3，</p><p>　　i = 4時(shí)，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，</p><p><b>　　……</b></p><p>　　i = k時(shí)，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4

46、+ … + k )，</p><p>　　解出滿(mǎn)足上述不等式的k值，即為語(yǔ)句i = i + 1的程序步數(shù)。 (4) for語(yǔ)句每執(zhí)行一次，語(yǔ)句i=i+j將執(zhí)行n次，而i的值會(huì)增加</p><p>　　因此，當(dāng)for語(yǔ)句執(zhí)行k次后，i的值將變?yōu)?lt;/p><p>　　故最終for語(yǔ)句的執(zhí)行次數(shù)k為滿(mǎn)足</p><p>　　的最小整數(shù)k，語(yǔ)句i

47、= i + j的程序步數(shù)為n*k。</p><p>　　4.試編寫(xiě)一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個(gè)數(shù)組元素中，0 n arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt，則當(dāng)n>arraySize或者對(duì)于某一個(gè)k (0 k n)，使得k!*2k > maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方式：</p>&l

48、t;p>　　(1) 用printf顯示錯(cuò)誤信息及exit(1)語(yǔ)句來(lái)終止執(zhí)行并報(bào)告錯(cuò)誤；</p><p>　　(2) 用返回整數(shù)函數(shù)值0, 1來(lái)實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；</p><p>　　(3) 在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來(lái)區(qū)別是正常返回還是某種錯(cuò)誤返回。</p><p>　　試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)

49、現(xiàn)它。</p><p><b>　　【解答】</b></p><p>　　#include <stdio.h>const int arraySize = 100;</p><p>　　const int MaxInt = 0x7fffffff;int calc( int T[ ], int n ) {int i, value

50、 = 1;if ( n != 0 ) {</p><p>　　int edge = MaxInt / n / 2;</p><p>　　for ( i = 1; i < n; i++ ) {</p><p>　　value *= i*2;</p><p>　　if ( value > edge ) return 0;</

51、p><p><b>　　}</b></p><p>　　value *= n * 2;</p><p><b>　　}</b></p><p>　　T[n] = value;</p><p>　　printf("A[ %d ]= %d\n”,n,T[n]);</p

52、><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　void main ( ) {int A[arraySize];</p><p><b>　　int i;</b></p><p>　　for

53、 ( i = 0; i < arraySize; i++ )</p><p>　　if ( !calc ( A, i ) ) {</p><p>　　printf("failed at %d .\n", i );</p><p><b>　　break;</b></p><p><b>

54、;　　}</b></p><p><b>　　}</b></p><p>　　/*---------順序表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-----------</p><p>　　-----------數(shù)據(jù)元素從data[0]處開(kāi)始存儲(chǔ)---------------------------------*/</p

55、><p>　　typedef struct /*注意typedef的使用*/</p><p><b>　　{ </b></p><p>　　int data[MAXSIZE]; /*數(shù)據(jù)域*/</p><p>　　int length; /*表長(zhǎng)*/</p><p>　　}li

56、sttype;</p><p>　　5.設(shè)有一個(gè)線性表 (a0, a1, …, an-2, an-1) 存放在一個(gè)一維數(shù)組A[arraySize]中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫(xiě)一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為 (an-1, an-2, …, a1, a0)。最后分析此算法的時(shí)間復(fù)雜度及空間復(fù)雜度。</p><p><b>　　【解答】</b>

57、;</p><p>　　void inverse (listtype * A) {</p><p><b>　　int tmp;</b></p><p>　　int n= A->length;</p><p>　　for( int i = 0; i <= ( n-1 ) / 2; i++ ){</p&g

58、t;<p>　　tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　時(shí)間復(fù)雜度：需進(jìn)行n/2次循

59、環(huán)，因此時(shí)間復(fù)雜度為O(n)；</p><p>　　空間復(fù)雜度：使用一個(gè)整形輔助存儲(chǔ)單元tmp，因此空間復(fù)雜度為O(1)。</p><p>　　6.順序表的插入和刪除要求仍然保持各個(gè)元素原來(lái)的次序。設(shè)在等概率情形下, 對(duì)有127個(gè)元素的順序表進(jìn)行插入, 平均需要移動(dòng)多少個(gè)元素? 刪除一個(gè)元素, 又平均需要移動(dòng)多少個(gè)元素?</p><p><b>　　【解答

60、】</b></p><p>　　若設(shè)順序表中已有n個(gè)元素。又設(shè)插入或刪除表中各個(gè)元素的概率相等，則在插入時(shí)因有n+1個(gè)插入位置(可以在表中最后一個(gè)表項(xiàng)后面追加)，每個(gè)元素位置插入的概率為1/(n+1)，但在刪除時(shí)只能在已有n個(gè)表項(xiàng)范圍內(nèi)刪除，所以每個(gè)元素位置刪除的概率為1/n。</p><p>　　插入時(shí)平均移動(dòng)元素個(gè)數(shù)AMN(Averagy Moving Number )為&

61、lt;/p><p>　　刪除時(shí)平均移動(dòng)元素個(gè)數(shù)AMN為</p><p>　　7.利用順序表的操作，實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時(shí)間復(fù)雜度，并分析(2)與(3)的時(shí)間復(fù)雜度出現(xiàn)差異的原因。</p><p>　　(1) 從順序表中刪除具有給定值x的所有元素。</p><p>　　(2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的

62、所有元素。</p><p>　　(3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。</p><p>　　(4) 將兩個(gè)有序順序表la,lb合并成一個(gè)新的有序順序表lc。</p><p>　　(5) 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。</p><p><b>　　【解答】</

63、b></p><p>　　(1) 從順序表中刪除具有給定值x的所有元素。</p><p>　　void DelValue(listtype * L, int x ){</p><p>　　int i = 0, j;</p><p>　　while ( i < L->length )/*循環(huán), 尋找具有值x的元素并刪除

64、它*/</p><p>　　if (L->data[i] == x ) { /*刪除具有值x的元素, 后續(xù)元素前移*/</p><p>　　for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1];</p><p>　　L-length--; /*表長(zhǎng)減1*/

65、</p><p><b>　　}</b></p><p><b>　　else i++;</b></p><p><b>　　}</b></p><p>　　(2) 實(shí)現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：</p><p>　

66、　void DelValue_s_to_t (listtype *L,int s, int t){</p><p><b>　　int i,j;</b></p><p>　　if ( L->length == 0 || s >= t ) {</p><p>　　printf(“List is empty or parameters

67、are illegal!\n”); exit(1); }</p><p><b>　　i = 0;</b></p><p>　　while ( i < L->length)/*循環(huán), 尋找具有值x的元素并刪除它*/</p><p>　　if (L->data[i]>=s &&L->data

68、[i]<= t){</p><p>　　/*刪除滿(mǎn)足條件的元素, 后續(xù)元素前移*/</p><p>　　for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1];</p><p>　　L->length--; /*表長(zhǎng)減1*/</p>&l

69、t;p><b>　　}</b></p><p><b>　　else i++;</b></p><p><b>　　}</b></p><p>　　(3) 實(shí)現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下：</p><p>　　void DelValue_

70、s_to_t_1 (listtype *L,int s int t){</p><p>　　int i,j,k;</p><p>　　if ( L->length == 0 || s >= t ){ </p><p>　　printf(“List is empty or parameters are illegal!\n”); exit(1); }&l

71、t;/p><p>　　for (i = 0; i < L->length; i++ ) /*循環(huán), 尋找值 ≥s 的第一個(gè)元素*/</p><p>　　if ( L->data[i] >= s ) break; /*退出循環(huán)時(shí), i指向該元素*/</p><p>　　if ( i < L->length ) {</p&g

72、t;<p>　　for (j = 1; i + j < L->length; j++ )/*循環(huán), 尋找值 > t 的第一個(gè)元素*/</p><p>　　if (L->data[i+j] > t ) break;/*退出循環(huán)時(shí), i+j指向該元素*/</p><p>　　for (k = i+j; k < L->length; k

73、++ ) /*刪除滿(mǎn)足條件的元素, 后續(xù)元素前移*/</p><p>　　L->data[k-j] = L->data[k]; </p><p>　　L->length-= j; /*表長(zhǎng)減j*/</p><p><b>　　}</b></p><p><b>　　}</b

74、></p><p>　　(4) 實(shí)現(xiàn)將兩個(gè)有序順序表合并成一個(gè)新的有序順序表的函數(shù)如下：</p><p>　　listtype * Merge(listtype *LA,listtype *LB ){</p><p>　　/*合并有序順序表LA與LB成為一個(gè)新的有序順序表并由函數(shù)返回</p><p>　　listtype *LC;<

75、;/p><p>　　int value1,value2;</p><p>　　int i,j,k;</p><p>　　initiatelist(LC);</p><p>　　if (LA->length + LB->length > MAXSIZE) { </p><p>　　printf(“表上溢/n

76、”; exit(1); </p><p><b>　　}</b></p><p>　　i = 0, j = 0, k = 0;</p><p>　　value1 = LA->data[i];</p><p>　　value2 = LB->data[j];</p><p>　　whil

77、e (i < LA->length && j < LB->length ) {</p><p>　　/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/</p><p>　　if (value1 <= value2){</p><p>　　LC->data[k] = value1; i++; value1=LA->d

78、ata[i];}</p><p><b>　　else { </b></p><p>　　LC->data[k] = value2; j++; value2=LB->data[j];}</p><p><b>　　k++;</b></p><p><b>　　} </

79、b></p><p>　　while( i < LA->length){/*當(dāng)LA表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/</p><p>　　LC->data[k] = value1; i++; k++; value1 = LA->data[i]; </p><p><b>　　}</b></p

80、><p>　　while( j < LB->length){/*當(dāng)LB表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送*/</p><p>　　LC->data[k] = value2; j++; k++; value2 = LB->data[j];</p><p><b>　　}</b></p><p>　　

81、LC->length = k;</p><p>　　return LC;</p><p><b>　　}</b></p><p>　　(5) 實(shí)現(xiàn)從表中刪除所有其值重復(fù)的元素的函數(shù)如下：</p><p>　　void DelDouble(listtype *L){</p><p>　　int

82、 i,j,k;</p><p><b>　　int tmp;</b></p><p>　　if(L->length == 0 ){ </p><p>　　printf(“表空\(chéng)n”; exit(1); </p><p><b>　　}</b></p><p><

83、b>　　i=0;</b></p><p>　　while ( i < L->length ) {/*循環(huán)檢測(cè)*/</p><p>　　j = i + 1; </p><p>　　tmp = L->data[i];</p><p>　　while( j < L->length ) {/*對(duì)

84、于每一個(gè)i, 重復(fù)檢測(cè)一遍后續(xù)元素*/</p><p>　　if( tmp == L->data[j]) {/*如果相等,刪除此結(jié)點(diǎn)，后續(xù)元素前移*/</p><p>　　for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];</p><p>　　L->leng

85、th--; /*表最后元素位置減1*/</p><p><b>　　}</b></p><p><b>　　else j++;</b></p><p><b>　　} </b></p><p>　　i++;/*檢測(cè)完L->data[i], 檢測(cè)下一個(gè)*/

86、</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　8.線性表可用順序表或鏈表存儲(chǔ)。試問(wèn)：</p><p>　　(1) 兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)?</p><p>　　(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的

87、長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用哪種存儲(chǔ)表示？為什么？</p><p>　　(3) 若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)，應(yīng)采用哪種存儲(chǔ)表示？為什么？</p><p><b>　　【解答】</b></p><p>　　(1) 順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)連續(xù)的存儲(chǔ)空

88、間中，實(shí)現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲(chǔ)效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有次序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。</p><p>　　鏈接存儲(chǔ)表示的存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中動(dòng)態(tài)分配和釋放，且只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出的問(wèn)題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只

89、需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序訪問(wèn)，因此存取效率不高。</p><p>　　(2) 如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)改變、在此情況下，應(yīng)選用鏈接存儲(chǔ)表示。</p><p>　　如果采用順序存儲(chǔ)表示，必須在一個(gè)連續(xù)的可用空間中為這n個(gè)表分配空間。初始時(shí)因不知

90、道哪個(gè)表增長(zhǎng)得快，必須平均分配空間。在程序運(yùn)行過(guò)程中，有的表占用的空間增長(zhǎng)得快，有的表占用的空間增長(zhǎng)得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進(jìn)行元素的插入時(shí)就必須成片地移動(dòng)其他的表的空間，以空出位置進(jìn)行插入；在元素刪除時(shí)，為填補(bǔ)空白，也可能移動(dòng)許多元素。這個(gè)處理過(guò)程極其繁瑣和低效。</p><p>　　如果采用鏈接存儲(chǔ)表示，一個(gè)表的存儲(chǔ)空間可以連續(xù)，可以不連續(xù)。表的增長(zhǎng)通過(guò)動(dòng)態(tài)存儲(chǔ)分配解

91、決，只要存儲(chǔ)器未滿(mǎn)，就不會(huì)有表溢出的問(wèn)題；表的收縮可以通過(guò)動(dòng)態(tài)存儲(chǔ)釋放實(shí)現(xiàn)，釋放的空間還可以在以后動(dòng)態(tài)分配給其他的存儲(chǔ)申請(qǐng)要求，非常靈活方便。對(duì)于n個(gè)表(包括表的總數(shù)可能變化)共存的情形，處理十分簡(jiǎn)便和快捷。所以選用鏈接存儲(chǔ)表示較好。</p><p>　　(3) 應(yīng)采用順序存儲(chǔ)表示。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取表中的元素，這時(shí)采用順序

92、存儲(chǔ)表示較好。</p><p>　　/*---------鏈表結(jié)構(gòu)的定義.為簡(jiǎn)化起見(jiàn)，表元素我們使用整型數(shù)據(jù)-----------</p><p>　　-----------此鏈表帶頭結(jié)點(diǎn)--------------------------------------------*/</p><p>　　typedef struct mynode{</p>

93、<p>　　int data; /*數(shù)據(jù)域：整型*/</p><p>　　struct mynode *next; /*指針域*/</p><p>　　} node, linklisttype;</p><p>　　9.試寫(xiě)出計(jì)算線性鏈表長(zhǎng)度的算法。</p><p>　　int lengthsl(

94、linklisttype *L){</p><p>　　linklisttype * p;</p><p><b>　　int len;</b></p><p>　　if(L == NULL){return –1;}</p><p>　　p = L->next;/* p指向鏈表L的頭結(jié)點(diǎn)*/</p&

95、gt;<p><b>　　len = 0;</b></p><p>　　while(p != NULL){</p><p><b>　　len++;</b></p><p>　　p = p->next;</p><p><b>　　}</b></p&g

96、t;<p>　　return len;</p><p><b>　　}</b></p><p>　　10.設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。</p><p><b>　　【解答】</b&g

97、t;</p><p>　　void LinkListInverse(linklisttype *L){</p><p>　　linklisttype *p, *pre, *next;</p><p>　　if(L == NULL || L->next == NULL ) return; /*表未初始化，或?yàn)榭毡?/</p><p>　　

98、p = L->next;</p><p><b>　　pre = L;</b></p><p>　　while( p != NULL ) {/*循環(huán)修改鏈表中所有結(jié)點(diǎn)的后繼指針的指向*/</p><p>　　next = p->next;/*取當(dāng)前結(jié)點(diǎn)的后繼指針*/</p><p>　　p-&g

99、t;next = pre;/*當(dāng)前結(jié)點(diǎn)的后繼改為指向其原來(lái)的前驅(qū)*/</p><p>　　pre = p , p=next;/*指針后移*/</p><p><b>　　}</b></p><p>　　L->next->next = NULL;/*原第一個(gè)結(jié)點(diǎn)改為最后一個(gè)結(jié)點(diǎn)*/</p><p

100、>　　L->next = pre;/*鏈表的頭結(jié)點(diǎn)指向原最后一個(gè)結(jié)點(diǎn)*/</p><p><b>　　}</b></p><p>　　11.設(shè)有一線性鏈表，其結(jié)點(diǎn)值均為整數(shù)。試將該線性鏈表分解為兩個(gè)線性鏈表，其中一鏈表中的結(jié)點(diǎn)值均為負(fù)整數(shù)，而另一鏈表中結(jié)點(diǎn)的值均為正整數(shù)，并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn)。</p><p><b

101、>　　【解答】</b></p><p>　　void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB){</p><p><b>　　/*</b></p><p>　　將鏈表L分解為L(zhǎng)A、LB兩個(gè)鏈表，其中LA中結(jié)點(diǎn)值均為正，LB中結(jié)點(diǎn)值

102、均為負(fù)，</p><p>　　并刪除結(jié)點(diǎn)值為零的結(jié)點(diǎn),最后釋放L的頭結(jié)點(diǎn)。</p><p><b>　　*/</b></p><p>　　linklisttype *p , *pt , *pa, * pb;</p><p>　　LA = initiatesl();</p><p>　　pa = L

103、A;/*指向LA中的最后一個(gè)結(jié)點(diǎn)*/</p><p>　　LB = initiatesl();</p><p>　　pb = LB;/*指向LB中的最后一個(gè)結(jié)點(diǎn)*/</p><p>　　If(L == NULL || L->next == NUUL) return;/*L為空指針或L為空表*/</p><p&

104、gt;　　p = L->next;/*p指向鏈表L的第一個(gè)結(jié)點(diǎn)*/</p><p>　　while(p != NULL)/*遍歷鏈表L*/</p><p>　　if(p->data > 0){/*將p鏈入鏈表LA的pa后*/</p><p>　　pa->next = p;</p><p>

105、<b>　　pa = p;</b></p><p>　　p = p->next;</p><p><b>　　}</b></p><p>　　elseif(p->data < 0){/*將p鏈入鏈表LB的pb后*/</p><p>　　pb->next = p;<

106、/p><p><b>　　pb = p;</b></p><p>　　p = p->next;</p><p><b>　　}</b></p><p>　　else{/*刪除值為0的結(jié)點(diǎn)*/</p><p>　　pt = p->next;/*記錄

107、當(dāng)前結(jié)點(diǎn)的后繼，以便刪除當(dāng)前結(jié)點(diǎn)*/</p><p><b>　　free(p);</b></p><p><b>　　p = pt;</b></p><p><b>　　}</b></p><p>　　pa->next = NULL;</p><p&

108、gt;　　pb->next = NULL;</p><p><b>　　free(L);</b></p><p><b>　　}</b></p><p>　　12．設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)

109、鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。</p><p><b>　　【解答】</b></p><p>　　void linklistMerge(linklisttype *LA,linklisttype *LB ){</p><p>　　/*合并有序鏈表LA與LB,結(jié)果存入LA中，并釋放LB的頭結(jié)點(diǎn) */</p

110、><p>　　linklisttype *pa, *pb , *pre ,*pn;</p><p>　　if(LA == NULL || LB == NULL ||) return;</p><p>　　if(LA->next == NULL){/*LA為空表，則直接將LB鏈入LA即可*/</p><p>　　LA->next

111、 = LB->next;</p><p><b>　　free(LB);</b></p><p><b>　　retrun;</b></p><p><b>　　}</b></p><p>　　if(LB->next == NULL) return;/*LB為

112、空表，則直接返回即可*/</p><p>　　pa = LA->next, pb = LB->next ,pre=LA;</p><p>　　while (pa != NULL && pb != NULL)/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/</p><p>　　if(pa->data > pb->next){

113、/*將pb鏈入LA，然后pb指針后移*/</p><p>　　pre->next = pb;</p><p>　　pn = pb->next;</p><p>　　pb->next = pa;</p><p><b>　　pb = pn;</b></p><p>　　pre

114、 = pre->next</p><p><b>　　}</b></p><p>　　else{/*pa指針后移*/</p><p>　　pa = pa->next;</p><p>　　pre = pre->next;</p><p><b>　　}&

115、lt;/b></p><p>　　if(pb != NULL)/*將pb剩余結(jié)點(diǎn)鏈入LA*/</p><p>　　pre->next = pb;</p><p><b>　　free(LB);</b></p><p><b>　　}</b></p><p

116、>　　13．設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針, 試設(shè)計(jì)一個(gè)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。</p><p><b>　　【解答】</b></p><p>　　Linklisttype * linklistMerge_inv

117、erse(linklisttype *LA,linklisttype *LB ){</p><p>　　/*合并有序鏈表LA與LB,結(jié)果存入LC中，并釋放LA、LB的頭結(jié)點(diǎn) ,函數(shù)返回LC*/</p><p>　　linklisttype *pa, *pb , *p;</p><p>　　if(LA == NULL || LB == NULL ||) return;

118、</p><p>　　LC = initiatesl();</p><p>　　pa = LA->next, pb = LB->next;</p><p>　　while (pa != NULL && pb != NULL)/*循環(huán), 兩兩比較, 大者存入LC*/</p><p>　　if(pa->dat

119、a > pb->next){/*將pa鏈為L(zhǎng)C的第一個(gè)結(jié)點(diǎn)*/</p><p>　　p = pa->next;</p><p>　　pa->next = LC->next;</p><p>　　LC->next = pa;</p><p><b>　　pa = p;</b><

120、;/p><p><b>　　}</b></p><p>　　else{/*將pa鏈為L(zhǎng)C的第一個(gè)結(jié)點(diǎn)*/</p><p>　　p = pb->next;</p><p>　　pb->next = LC->next;</p><p>　　LC->next = pb

121、;</p><p><b>　　pb = p;</b></p><p><b>　　}</b></p><p>　　while(pa != NULL){/*將pa剩余結(jié)點(diǎn)鏈入LC*/</p><p>　　p = pa->next;</p><p>　　pa

122、->next = LC->next;</p><p>　　LC->next = pa;</p><p><b>　　pa = p;</b></p><p><b>　　}</b></p><p>　　while(pb != NULL){/*將pb剩余結(jié)點(diǎn)鏈入LC*/&

123、lt;/p><p>　　p = pb->next;</p><p>　　pb->next = LC->next;</p><p>　　LC->next = pb;</p><p><b>　　pb = p;</b></p><p><b>　　}</b>&

124、lt;/p><p><b>　　free(LA);</b></p><p><b>　　free(LB);</b></p><p><b>　　}</b></p><p>　　14.在一個(gè)循環(huán)鏈表中尋找值為x的結(jié)點(diǎn)，并將該結(jié)點(diǎn)移到第一個(gè)結(jié)點(diǎn)之前。</p><p&

125、gt;　　【解答】設(shè)此循環(huán)鏈表為單鏈表，則其類(lèi)型定義與一般單鏈表相同</p><p>　　typedef struct mynode cyclelisttype;</p><p>　　void search_movefirst(cyclelisttype *CL, int x){</p><p>　　cyclelisttype * p , *pre;</p&g

126、t;<p>　　if(CL == NULL) return;</p><p>　　p = CL->next;</p><p><b>　　pre = CL;</b></p><p>　　while(p != CL)</p><p>　　/*查找x，注意與普通單鏈表在判斷是否到表尾上的不同*/</