數(shù)據(jù)結(jié)構(gòu)課程課后習(xí)題答案

1、數(shù)據(jù)結(jié)構(gòu)課程-課后習(xí)題答案數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程練習(xí)題及參考答案練習(xí)題11 .單項(xiàng)選擇題（1）線性結(jié)構(gòu)中數(shù)據(jù)元素之間是（）關(guān)系。A.一對(duì)多B.多對(duì)多C.多對(duì)一D.一對(duì)一答：D（2）數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A.存儲(chǔ)B.物理C.邏輯D.物理和存儲(chǔ)答：C（3）算法分析的目的是（）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性答：C（4）算法分析的兩個(gè)主要方面是（）。練習(xí)題及參考答案A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性答：A(5)計(jì)算機(jī)算法指的是()。A.計(jì)算方法B

2、.排序方法C.求解問題的有限運(yùn)算序列D.調(diào)度方法答：C(6)計(jì)算機(jī)算法必須具備輸入、輸出和()等5個(gè)特性。A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性答：B2 .填空題(1)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的工、數(shù)據(jù)的二和數(shù)據(jù)的這三個(gè)方面的內(nèi)容。答：邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算(2)數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是，和q。答：線性結(jié)構(gòu)非線性結(jié)構(gòu)(3)數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D是一的有限集合.R是D上的有限集合。答：數(shù)據(jù)元素關(guān)系(4)在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)工后繼結(jié)點(diǎn)，其余每個(gè)

3、結(jié)點(diǎn)有且只有1個(gè)后繼結(jié)點(diǎn)。答：沒有沒有(5)在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有,結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)可以是工。答：前驅(qū)1后繼任意多個(gè)(6)在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以是()。答：任意多個(gè)(7)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有四種，它們分別是工、旦、和其存儲(chǔ)結(jié)構(gòu)。答：順序鏈?zhǔn)剿饕?8)一個(gè)算法的效率可分為效率和口效率。答：時(shí)間空間3.簡(jiǎn)答題(1)數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素的集合。數(shù)據(jù)類型不僅定義了一組數(shù)據(jù)元素，而且還在其上定義了一組操作。(2)簡(jiǎn)述線性結(jié)構(gòu)

4、、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，樹形線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)多的，圖在結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。(3)設(shè)有采用二元組表示的數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R),其中D=a,b,i,R=(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)問相對(duì)于關(guān)系R,哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：該邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)，其中a結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，b、e、g、i結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，是終端結(jié)點(diǎn)，也稱為葉子結(jié)點(diǎn)。(4)以下各函數(shù)是算法中語(yǔ)句的執(zhí)行頻度，n為問題規(guī)模，給出對(duì)應(yīng)的時(shí)間復(fù)雜度：Ti(n)=nl

5、og2n-1000log2nT2(n戶nlog23-1000log2nT3(n)=n2-100010g2nT4(n)=2n1og2n-100010g2nlogr3答：T1(n)=O(n10g2n),T2(n)=O()T3(n)=O(n2)T4(n)=O(n1og2n)o(5)分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)。intj=0,s=0,n=100;doj=j+1；s=s+10*j;whi1e(j<n&&s<n);答：j=0,第1次循環(huán)：j=1,s=10o第2次循環(huán):j=2)s=30。第3次循環(huán)：j=3)s=60o第4次循環(huán):j=4)s=100owhile條件不再滿足。所

6、以)其中循環(huán)語(yǔ)句的執(zhí)行次數(shù)為4。(6)執(zhí)行下面的語(yǔ)句時(shí))語(yǔ)句s+的執(zhí)行次數(shù)為多少？ints=0;for(i=1;i<n-1;i+)for(j=n;j>=i;j-)s 的執(zhí),(n 3)(n 2)'2°行次數(shù)s+;答：語(yǔ)句n2in21(ni1)n(n1)i1jni1(7)設(shè)n為問題規(guī)模，求以下算法的時(shí)間復(fù)雜度。5練習(xí)題及參考答案voidfun1(intn)intx=0,i;for(i=1;i<=n;i+)for(j=i+1;j<=n;j+)x+;答：其中x+語(yǔ)句屬基本運(yùn)算語(yǔ)句)nnnT(n)1(ni)，=O(n2)。i1ji1i12(8)設(shè)n為問題規(guī)模，是

7、一個(gè)正偶數(shù)，試計(jì)算以下算法結(jié)束時(shí)m的值，并給出該算法的時(shí)間復(fù)雜度。voidfun2(intn)intm=0;for(i=1;i<=n;i+)for(j=2*i;j<=n;j+)m+;答：由于內(nèi)循環(huán)j的取值范圍，所以iWn/2,則n/2 n n/2m(n (2ii 1 j 2i i 1O(n2)。1)/4,該程序段的時(shí)間復(fù)雜度為上機(jī)實(shí)驗(yàn)題1有一個(gè)整型數(shù)組a,其中含有n個(gè)元素，設(shè)計(jì)盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測(cè)試。解：maxs算法用于返回?cái)?shù)組a0.n-1中的最大元素值max1和次大元素值max2)max1和max2設(shè)計(jì)為引用類型。對(duì)應(yīng)的程序如下：#inclu

8、de<stdio.h>voidmaxs(inta,intn,int&max1,int&max2)inti；max1=max2=a0;for(i=1;i<n;i+)if(ai>max1)max2=max1;max1=ai;elseif(ai>max2)max2=ai;voidmain()inta=1,4,10,6,8,3,5,7,9,2;intn=10;intmax1,max2;maxs(a,n,max1,max2);printf("最大元素值=%d,次大元素值=%dn",max1,max2);練習(xí)題21.單項(xiàng)選擇題(1)數(shù)據(jù)在計(jì)

9、算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相對(duì)順序相同并且是連續(xù)的，稱之為()。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)答：C(2)在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是()。A.訪問第i個(gè)結(jié)點(diǎn)(1WiWn)和求第i(2WiWn)個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)#J練習(xí)題及參考答案B.在第i(iwiwn)個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i個(gè)結(jié)點(diǎn)(iwiwn)D.將n個(gè)結(jié)點(diǎn)從小到大排序答：A(3)向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)()個(gè)元素。A.8B.63.5C.63D.7答：B(4)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間()。A.分兩部分，一部分存放結(jié)點(diǎn)

10、值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B.只有一部分，存放結(jié)點(diǎn)值C.只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答：A(5)線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答：D（6）一個(gè)線性表在（）情況下適用于采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。A.需經(jīng)常修改其中的結(jié)點(diǎn)值B.需不斷對(duì)其進(jìn)行刪除插入C.其中含有大量的結(jié)點(diǎn)D.其中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答：B（7）單鏈表的存儲(chǔ)密度（）A.大于1B.等于1C.小于1D.不能確定答：C2 .填空題（1）在順序表中插入或刪除一個(gè)元素時(shí)，需

11、要平均移動(dòng)（）元素，具體移動(dòng)的元素個(gè)數(shù)與（）有關(guān)。答：表中一半表長(zhǎng)和該元素在表中的位置（2）向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素（1<i<n+1）之前插入一個(gè)元素時(shí)）需向后移動(dòng)（）個(gè)元素。答：n-i+1（3）向一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（iwiwn）時(shí)）需向前移動(dòng)（）個(gè)元素。答：n-i（4）在順序表中訪問任意一個(gè)元素的時(shí)間復(fù)雜度均為（）因此順序表也稱為（）的數(shù)據(jù)結(jié)構(gòu)。答：0（1）隨機(jī)存?。?）順序表中邏輯上相鄰的元素的物理位置（）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（）相鄰。答：一定不一定（6）在帶頭結(jié)點(diǎn)的單鏈表中，除頭結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示。答：其前驅(qū)結(jié)

12、點(diǎn)的鏈域的值（7）在含有n個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,需找到它的（），其時(shí)間復(fù)雜度為（）。答：前驅(qū)結(jié)點(diǎn)的地址0（n）（8）含有n（n>1）個(gè)結(jié)點(diǎn)的循環(huán)雙向鏈表中）為空的指針域數(shù)為（）。答：03 .簡(jiǎn)答題（1）試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：順序存儲(chǔ)結(jié)構(gòu)中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。其優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。其優(yōu)點(diǎn)是插入或刪除元

13、素時(shí)很方便，使用靈活；缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。(2)對(duì)于表長(zhǎng)為n的順序表，在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為多少？刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為多少？答：插入一個(gè)元素所需要移動(dòng)的元素的平均個(gè)數(shù)為(n-1)/2,刪除一個(gè)元素所需要移動(dòng)的平均個(gè)數(shù)為n/2。練習(xí)題及參考答案(3)在鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：在鏈表中設(shè)置頭結(jié)點(diǎn)后，不管鏈表

14、是否為空表，頭結(jié)點(diǎn)指針均不空，并使得對(duì)鏈表的操作(如插入和刪除)在各種情況下統(tǒng)一，從而簡(jiǎn)化了算法的實(shí)現(xiàn)過程。(4)對(duì)于雙鏈表和單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)需修改的指針各為多少個(gè)？答：對(duì)于雙鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需修改前驅(qū)結(jié)點(diǎn)的next域、后繼結(jié)點(diǎn)的prior域和新插入結(jié)點(diǎn)的next、prior域。所以共修改4個(gè)指針。對(duì)于單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí))需修改前一結(jié)點(diǎn)的next域)新插入結(jié)點(diǎn)的next域。所以共修改兩個(gè)指針。(5)某含有n(n>1)結(jié)點(diǎn)的線性表中，最常用的操作是在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用以下哪種存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

15、單鏈表；僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表；雙鏈表；僅有尾指針的循環(huán)單鏈表。答：在單鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1)。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為0(n)。在僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度0(n),因?yàn)閯h除第一個(gè)結(jié)點(diǎn)后還要將其改為循環(huán)單鏈表；在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度也為O(n)o在雙鏈表中，刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1);在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，也需找到尾結(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為0(n)。在僅有尾指針的循環(huán)單鏈表中，通過該尾指針可以直接找到第一個(gè)結(jié)點(diǎn)，所以刪除第一個(gè)結(jié)點(diǎn)的時(shí)間

16、復(fù)雜度為0(1);在尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)也就是在尾指針?biāo)附Y(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)，時(shí)間復(fù)雜度也為0(1)。因此最節(jié)省運(yùn)算時(shí)間。4 .算法設(shè)計(jì)題(1)設(shè)計(jì)一個(gè)高效算法，將順序表的所有元素逆置，要求算法空間復(fù)雜度為0(1)。解：遍歷順序表L的前半部分元素，對(duì)于元素L.datai(0WivL.length/2)將其與后半部分對(duì)應(yīng)元素L.dataL.length-i-1進(jìn)行交換。#JJ練習(xí)題及參考答案對(duì)應(yīng)的算法如下：voidreverse(SqList&L)inti；ElemTypex;for(i=0;i<L.length/2;i+)x=L.datai;/L.datai與L.dataL.

17、length-i-1交換L.datai=L.dataL.length-i-1;L.dataL.length-i-1=x;本算法的時(shí)間復(fù)雜度為O(n)。(2)設(shè)計(jì)一個(gè)算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。解：對(duì)于順序表L,用i從1開始遍歷其元素)設(shè)L.data0.j(j的初值為0)中沒有重復(fù)的元素。檢測(cè)L.datai(j<i<L.length)若L.datai和L.data0.j中任何一個(gè)元素都不相同,則將L.datai存入L.dataj+1中。對(duì)應(yīng)的算法如下：voiddelsame(SqList&L)/L為引用型參數(shù)inti,j=0,k;for(i

18、=1;i<L.length;i+)k=0;while(k<=j&&L.datak!=L.datai)k+;if(k>j)/表示L.datai和L.data0.j中所有元素都不相同j+;L.dataj=L.datai;L.length=j+1;/順序表長(zhǎng)度置新值本算法的時(shí)間復(fù)雜度為O(n2),空間復(fù)雜度15為0(1)。(3)設(shè)計(jì)一個(gè)算法從有序順序表中刪除重復(fù)的元素，并使剩余元素間的相對(duì)次序保持不變。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出現(xiàn)的元素個(gè)數(shù)，先將不重復(fù)的有序區(qū)看成是L.data0.0,置e=L.data0)用i從1開始遍歷L

19、的所有元素：當(dāng)L.datai#e時(shí))將它放在L.datak中)k增1)置e=L.datai)最后將L的length置為ko對(duì)應(yīng)的算法如下:void delsame1(SqList &L) int i,k=1;ElemType e;e=L.data0;for (i=1;i<L.length;i+) if (L.datai!=e) L.datak=L.datai;k+;e=L.datai;L.length=k;/L為引用型參數(shù)/k保存不重復(fù)的元素個(gè)數(shù)/只保存不重復(fù)的元素/順序表長(zhǎng)度置新值本算法是一個(gè)高效算法，其時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。如果每次遇到重復(fù)的元素，都通過

20、移動(dòng)其后所有元素來刪除它，這樣的時(shí)間復(fù)雜度會(huì)變成O(n2)。(4)設(shè)計(jì)一個(gè)算法刪除單鏈表L中第一個(gè)16值為x的結(jié)點(diǎn)。解：用p、q遍歷整個(gè)單鏈表)p指向*q前驅(qū)結(jié)點(diǎn)，q用于查找第一個(gè)值為x的結(jié)點(diǎn)，找到后將*q結(jié)點(diǎn)刪除，返回1;否則返回0o應(yīng)的算法如下：int delx(SLink *&L,ElemType x) SLink *p=L,*q=p->next;while (q!=NULL && q->data!=x) p=q;q=q->next;if (q!=NULL) p->next=q->next;free(q);return 1;else

21、return 0;/p指向*q的前驅(qū)結(jié)點(diǎn)/找到值為x的結(jié)點(diǎn)/未找到值為x的結(jié)點(diǎn)(5)設(shè)計(jì)一個(gè)算法判定單鏈表L是否是遞增的。解：判定鏈表L從第2個(gè)結(jié)點(diǎn)開始的每個(gè)結(jié)點(diǎn)的值是否比其前驅(qū)的值大。若有一個(gè)不成立，則整個(gè)鏈表便不是遞增的；否則是遞增的。對(duì)應(yīng)的算法如下：int increase(SLink *L) SLink *pre=L->next,*p;p=pre->next;while (p!=NULL) if (p->data>=pre->data) pre=p;p=p->next;else return 0;/pre指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)/p指向*pre結(jié)點(diǎn)的后繼結(jié)

22、點(diǎn)/若正序則繼續(xù)判斷下一個(gè)結(jié)點(diǎn)/pre 、 p同步后移17練習(xí)題及參考答案return1;(6)有一個(gè)整數(shù)元素建立的單鏈表A,設(shè)計(jì)一個(gè)算法，將其拆分成兩個(gè)單鏈表A和B,使得A單鏈表中含有所有的偶數(shù)結(jié)點(diǎn)，B單鏈表中所有的奇數(shù)結(jié)點(diǎn)，且保持原來的相對(duì)次序。解：采用重新單鏈表的方法，由于要保持相對(duì)次序，所以采用尾插法建立新表A、B。用p遍歷原單鏈表A的所有數(shù)據(jù)結(jié)點(diǎn)，若為偶數(shù)結(jié)點(diǎn)，將其鏈到A中，若為奇數(shù)結(jié)點(diǎn)，將其鏈到B中。對(duì)應(yīng)的算法如下：voidSplit(SLink*&A,SLink*&B)SLink*p=A->next,*ra,*rb;/建立頭結(jié)點(diǎn)/r總是指向B鏈表的尾結(jié)點(diǎn)/偶

23、數(shù)結(jié)點(diǎn)/將*p結(jié)點(diǎn)車連到A中/奇數(shù)結(jié)點(diǎn)/將*p結(jié)點(diǎn)車到B中ra=A;B=(SLink*)malloc(sizeof(SLink);rb=B;while(p!=NULL)if(p->data%2=0)ra->next=p;ra=p;p=p->next;elserb->next=p;rb=p;p=p->next;ra->next=rb->next=NULL;本算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。(7)有一個(gè)有序單鏈表(從小到大排列)表頭指針為L(zhǎng),設(shè)計(jì)一個(gè)算法向該單鏈表中插入一個(gè)元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然有序。解：先建立一個(gè)待插入的結(jié)點(diǎn)

24、，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置，最后插入該結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：voidinorderList(SLink*&L,ElemTypex)SLink*s,*p,*q;建立一個(gè)待插入的結(jié)點(diǎn)s->data=x;s->next=NULL; if (L=NULL | x<L->data) s->next=L;s=(SLink*)malloc(sizeof(SLink);/若單鏈表為空或x小于第1個(gè)結(jié)點(diǎn)date域/把*s結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后L=s;elseq=L;/尋找插入位置，p指向待比較的結(jié)點(diǎn)，q指向p的前驅(qū)結(jié)點(diǎn)p=q->ne

25、xt;while(p!=NULL&&x>p->data)/若x小于p所指結(jié)點(diǎn)的data域值if(x>p->data)q=p;p=p->next;s->next=p;/將s結(jié)點(diǎn)插入到*q和*p之間q->next=s;(8)有一個(gè)單鏈表L,其中可能出現(xiàn)值域重復(fù)的結(jié)點(diǎn)，設(shè)計(jì)一個(gè)算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時(shí)間復(fù)雜度。解：用p遍歷單鏈表)用r遍歷*p結(jié)點(diǎn)之后的結(jié)點(diǎn)，q始終指向*r結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，19練習(xí)題及參考答案若r->data=p->data)則刪除*r結(jié)點(diǎn))否貝Uq、r同步后移一個(gè)結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：voidde

26、ls1(SLink*&L)SLink*p=L->next,*q,*r,*t;while(p!=NULL)q=p;r=q->next;while(r!=NULL)if(r->data=p->data)/r指向被刪結(jié)點(diǎn)t=r->next;q->next=t;free(r);r=t;elseq=r;r=r->next;p=p->next;本算法的時(shí)間復(fù)雜度為O(n2)。(9)有一個(gè)遞增有序單鏈表(允許出現(xiàn)值域重復(fù)的結(jié)點(diǎn))，設(shè)計(jì)一個(gè)算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時(shí)間復(fù)雜度。解：由于是有序表，所以相同值域的結(jié)點(diǎn)都是相鄰的。用p遍歷遞增單鏈表，

27、若*p結(jié)點(diǎn)的值域等于其后結(jié)點(diǎn)的值域，則刪除后者。對(duì)應(yīng)的算法如下：voiddels(SLink*&L)SLink*p=L->next,*q;while(p->next!=NULL)if(p->data=p->next->data)/找到重復(fù)值的結(jié)點(diǎn)q=p->next;/q指向這個(gè)重復(fù)值的結(jié)點(diǎn)p->next=q->next;/刪除*q結(jié)點(diǎn)free(q)；elsep=p->next;本算法的時(shí)間復(fù)雜度為O(n)。(10)有一個(gè)雙鏈表L,設(shè)計(jì)一個(gè)算法查找第一個(gè)元素值為x的結(jié)點(diǎn)，將其與后繼結(jié)點(diǎn)進(jìn)行交換。解：先找到第一個(gè)元素值為x的結(jié)點(diǎn)*p,q

28、指向其后繼結(jié)點(diǎn)，本題是將*p結(jié)點(diǎn)移到*q結(jié)點(diǎn)之后，實(shí)現(xiàn)過程是：刪除*p結(jié)點(diǎn)，再將其插入到*q結(jié)點(diǎn)之后。對(duì)應(yīng)的算法如下：intswap(DLink*L,ElemTypex)DLink*p=L->next,*q;while(p!=NULL&&p->data!=x)p=p->next;if(p=NULL)return0;elseq=p->next;if(q!=NULL)p->prior->next=q;q->prior=p->prior;p->next=q->next;if(q->next!=NULL)q->ne

29、xt->prior=p;q->next=p;p->prior=q;return1;else/未找到值為x的結(jié)點(diǎn)/找到值為x的結(jié)點(diǎn)*p/q指向*p的后繼結(jié)點(diǎn)/*p結(jié)點(diǎn)不是尾結(jié)點(diǎn)/先刪除*p結(jié)點(diǎn)/將*p結(jié)點(diǎn)插入到*q結(jié)點(diǎn)之后/*p結(jié)點(diǎn)是尾結(jié)點(diǎn)/無(wú)法與后繼結(jié)點(diǎn)交換，返回 0return0;21J練習(xí)題及參考答案(11)對(duì)于有n(n>1)個(gè)數(shù)據(jù)結(jié)點(diǎn)的循環(huán)單鏈表L,設(shè)計(jì)一個(gè)算法將所有結(jié)點(diǎn)逆置。解：采用頭插法重建循環(huán)單鏈表L的思路,先建立一個(gè)空的循環(huán)單鏈表，用p遍歷所有數(shù)據(jù)結(jié)點(diǎn)，每次將*p結(jié)點(diǎn)插入到前端。對(duì)應(yīng)的算法如下：voidReverse(SLink*&L)SLink*

30、p=L->next,*q;L->next=L;/建立一個(gè)空循環(huán)單鏈表while(p!=L)q=p->next;p->next=L->next;/將*p結(jié)點(diǎn)插入到前端L->next=p;p=q;上機(jī)實(shí)驗(yàn)題2有兩個(gè)整數(shù)集合采用有序單鏈表存儲(chǔ)，設(shè)計(jì)盡可能高效的算法求兩個(gè)集合的并集、交集和差集。并用相關(guān)數(shù)據(jù)進(jìn)行測(cè)試。#include<stdio.h>#include"SLink.h"voidUnion(SLink*L1,SLink*L2,SLink*&L3)/求并集SLink*p,*q,*s,*tc;L3=(SLink*)ma

31、lloc(sizeof(SLink);tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL)if(p->data<q->data)s=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;tc=s;p=p->next;elseif(p->data>q->data)s=(SLink*)malloc(sizeof(SLink);s->data=q->data;tc->next=s;tc=s

32、;q=q->next;elses=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;tc=s;p=p->next;q=q->next;while(p!=NULL)s=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;tc=s;p=p->next;while(q!=NULL)s=(SLink*)malloc(sizeof(SLink);s->data=q->data;tc->next=s;tc=s

33、;q=q->next;tc->next=NULL;voidInterSection(SLink*L1,SLink*L2,SLink*&L3)/求交集SLink*p,*q,*s,*tc;L3=(SLink*)malloc(sizeof(SLink);tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL)if(p->data<q->data)p=p->next;elseif(p->data>q->data)q=q->next;elsep->data=

34、q->datas=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;tc=s;p=p->next;q=q->next;tc->next=NULL;voidSubs(SLink*L1,SLink*L2,SLink*&L3)/求差集SLink*p,*q,*s,*tc;L3=(SLink*)malloc(sizeof(SLink);tc=L3;p=L1->next;q=L2->next;while(p!=NULL&&q!=NULL)if(p->data&l

35、t;q->data)s=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;tc=s;p=p->next;elseif(p->data>q->data)q=q->next;else/p->data=q->datap=p->next;q=q->next;while(p!=NULL)s=(SLink*)malloc(sizeof(SLink);s->data=p->data;tc->next=s;23JJ練習(xí)題及參考答案tc=s;p=p->

36、;next;tc->next=NULL;void main() SLink *A,*B,*C,*D,*E;ElemType a=1,3,6,8,10,20;CreateListR(A,a,6);printf("集合 A:");DispList(A);ElemType b=2,5,6,10,16,20,30;CreateListR(B,b,7);printf("集合 B:");DispList(B);printf("求 A、B并集 Cn");Union(A,B,C);printf("集合 C:");DispLi

37、st(C);printf("求 A、B交集 Cn");InterSection(A,B,D);printf("集合 D:");DispList(D);printf("求 A、B差集 En");Subs(A,B,E);printf("集合 E:");DispList(E);DestroyList(A);DestroyList(B);DestroyList(C);DestroyList(D);DestroyList(E);/尾插法建表/尾插法建表/求A、B并集C/求A、B并集D/求A、B差集E練習(xí)題31.單項(xiàng)選擇題(1

38、)棧中元素的進(jìn)出原則是()。A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出答：B(2)設(shè)一個(gè)棧的進(jìn)棧序列是A、B、C、D(即元素AD依次通過該棧)，則借助該棧所得到的輸出序列不可能是()。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C答：D(3)一個(gè)棧的進(jìn)棧序列是a、b、c、d、e>則棧的不可能的輸出序列是()。A.edcbaB.decbaC.dceabD.abcde答：C(4)已知一個(gè)棧的進(jìn)棧序列是1,2,3,n,其輸出序列的第一個(gè)元素是i(1<i<n)則第j(iwjwn)個(gè)出棧元素是()。A.iB.n-iC.j-i+1D.不確定答：D(5)設(shè)順

39、序棧st的棧頂指針top的初始時(shí)為-1)棧空間大小為MaxSize,則判定st棧為?？盏臈l件為()。A.st.top=-1B.st.top!=-1C.st.top!=MaxSizeD.st.top=MaxSize答：A(6)設(shè)順序棧st的棧頂指針top的初始時(shí)25練習(xí)題及參考答案為-1?？臻g大小為MaxSize）則判定st棧為棧滿的條件是。A.st.top!=-1B.st.top=-1C.st.top!=MaxSize-1D.st.top=MaxSize-1答：D隊(duì)列中元素的進(jìn)出原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出答：A（8）元素A、B、C、D順序連續(xù)進(jìn)入隊(duì)列qu后）隊(duì)

40、頭元素是（）隊(duì)尾元素是（）。A.AB.BC.CD.D答：AD。（9）一個(gè)隊(duì)列的入列序列為1234,則隊(duì)列可能的輸出序列是（）。A.4321B.1234C.1432D.3241答：B（10）循環(huán)隊(duì)列qu（隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置）的隊(duì)滿條件是（）。A.(qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontA.qu.rear=qu.front答：C(11)循環(huán)隊(duì)列qu(隊(duì)頭指針front指向隊(duì)首元

41、素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置)的隊(duì)空條件是()。A.(qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontD.qu.rear=qu.front答：D(12)設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0N-1,其頭尾指針分別為f和r(隊(duì)頭指針f指向隊(duì)首元素的前一位置，隊(duì)尾指針r指向隊(duì)尾元素的位置)，則其元素個(gè)數(shù)為()。A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N答：D（13）設(shè)有4個(gè)數(shù)據(jù)元素a、b、c和d,對(duì)其分別進(jìn)行棧

42、操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)）按a、b、c、d次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次）出棧一次）再進(jìn)棧兩次）出棧一次；這時(shí)，第一次出棧得到的元素是（），第二次出棧得到的元素是（）；類似地，考慮對(duì)這4個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是（），第二次出隊(duì)得到的元素是（）。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有（）個(gè)。：A.aB.bC.cD.d：A.1B.2C.3D.0答：BDABB（14）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素ei&依次通過棧S,一個(gè)元素出后即進(jìn)隊(duì)列Q）若6個(gè)元素出隊(duì)的序列是金、&

43、amp;、e3、a、e5、ei）則棧S的容量至少應(yīng)該是（）。A.5B.4C.3D.2答：C2 .填空題（1）棧是一種特殊的線性表，允許插入和29-練習(xí)題及參考答案刪除運(yùn)算的一端稱為（）。不允許插入和刪除運(yùn)算的一端稱為（）。答：棧頂棧底（2） 一個(gè)棧的輸入序列是12345,的輸出序列為12345,其進(jìn)棧出棧的操作為（）。答：1進(jìn)棧）1出棧）2進(jìn)棧）2出棧）3進(jìn)棧）3出棧）4進(jìn)棧）4出棧）5進(jìn)棧）5出棧。（3）有5個(gè)元素，其進(jìn)棧次序?yàn)锳、B、C、D、E,在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有（）。答：CDBAE、CDEBA、CDBEA。（4）順序棧用dat

44、a0.n-1存儲(chǔ)數(shù)據(jù)）棧頂指針為top,其初始值為0,則元素x進(jìn)棧的操作是（）。答：datatop=x;top+;（5）順序棧用data0.n-1存儲(chǔ)數(shù)據(jù)）棧頂指針為top,其初始值為0,則出棧元素x的操作是（）。答：top-;x=datatop;（6）（）是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性答：隊(duì)列(7)設(shè)有數(shù)組A0.m作為循環(huán)隊(duì)列的存儲(chǔ)空間)front為隊(duì)頭指針(它指向隊(duì)首元素的前一位置)，rear為隊(duì)尾指針(它指向隊(duì)尾元素的位置)，則元素x執(zhí)行入隊(duì)的操作是()。答：rear=(rear+1)%(m+1);Arear=x;(8)設(shè)有數(shù)組A0.m作為循環(huán)隊(duì)列的

45、存儲(chǔ)空間)front為隊(duì)頭指針(它指向隊(duì)首元素的前一位置)，rear為隊(duì)尾指針(它指向隊(duì)尾元素的位置)，則元素出隊(duì)并保存到x中的操作是()答：front=(front+1)%(m+1);x=Arear;3 .簡(jiǎn)答題(1)簡(jiǎn)要說明線性表、棧與隊(duì)的異同點(diǎn)。答：相同點(diǎn)：都屬地線性結(jié)構(gòu)，都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)等，隊(duì)

46、列用于多道作業(yè)處理、指31練習(xí)題及參考答案令寄存及其他運(yùn)算等等。(2)順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進(jìn)隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”o采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決循環(huán)隊(duì)列是空還是滿的辦法如下： 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空； 浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長(zhǎng)度)。通常采用法，讓隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置，這樣判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：front=rear,隊(duì)滿標(biāo)志是：(

47、rear+1)%MaxSize=front。4.算法設(shè)計(jì)題(1)假設(shè)采用順序棧存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法，利用棧的基本運(yùn)算返回指定棧中棧底元素，要求仍保持棧中元素不變。這里只能使用棧st的基本運(yùn)算來完成，不能直接用st.data0來得到棧底元素。解：假定采用順序棧結(jié)構(gòu)。先退棧st中所有元素)利用一個(gè)臨時(shí)棧tmpst存放從st棧中退棧的元素，最后的一個(gè)元素即為所求，然后將臨時(shí)棧tmpst中的元素逐一出棧并進(jìn)棧到st中，這樣恢復(fù)st棧中原來的元素。對(duì)應(yīng)算法如下：int GetBottom(SqStack st,ElemType &x) ElemType e;SqStack tmpst;Init

48、Stack(tmpst);if (StackEmpty(st)return 0;while (!StackEmpty(st) Pop(st,x);Push(tmpst,x);while (!StackEmpty(tmpst) Pop(tmpst,e);Push(st,e);return 1;/定義臨時(shí)棧/初始化臨時(shí)棧/空棧返回0/臨時(shí)棧tmpst中包含st棧中逆轉(zhuǎn)元素/恢復(fù)st棧中原來的內(nèi)容/返回1表示成功(2)設(shè)計(jì)一個(gè)算法，采用一個(gè)順序棧逆向輸出單鏈表L中所有元素。解：本題并不需要改變單鏈表L的結(jié)構(gòu)。設(shè)置一個(gè)順序棧st,先遍歷單鏈表并將所有元素進(jìn)棧，然后棧不空循環(huán)并輸出棧中所有元素。對(duì)應(yīng)算法

49、如下：voidReverseDisp(SLink*L)33-J練習(xí)題及參考答案ElemTypex;structnodeElemTypedataMaxSize;inttop;st;/定義一個(gè)順序棧st.top=-1;SLink*p=L->next;while(p!=NULL)/遍歷單鏈表，將所有元素進(jìn)棧st.top+;st.datast.top=p->data;p=p->next;while(st.top!=-1)/棧不空循環(huán)，輸出棧中所有元素x=st.datast.top;st.top-;printf("%d",x);printf("n"

50、;);(3)設(shè)計(jì)一個(gè)循環(huán)隊(duì)列)用front和rear分別作為隊(duì)頭和隊(duì)尾指針，另外用一個(gè)標(biāo)志tag標(biāo)識(shí)隊(duì)列可能空(0)或可能滿(1),這樣加上front=rear可以作為隊(duì)空或隊(duì)滿的條件。要求設(shè)計(jì)隊(duì)列的相關(guān)基本運(yùn)算算法。解：設(shè)計(jì)的隊(duì)列的類型如下：typedefstructElemTypedataMaxSize;intfront,rear;/隊(duì)頭和隊(duì)尾指針inttag;/為0表示隊(duì)空，為1時(shí)表示不空&&&&初始時(shí)：tag=0)front=rear隊(duì)空條件：qu.front=qu.rearqu.tag=0隊(duì)滿條件：qu.front=qu.rearqu.tag=1對(duì)應(yīng)的

51、算法如下：一一初始化隊(duì)列算法一一voidInitQueue1(QueueType&qu)qu.front=qu.rear=0;qu.tag=0;/為0表示隊(duì)空可能為空/一一判隊(duì)空算法一一intQueueEmpty1(QueueTypequ)return(qu.front=qu.rear&&qu.tag=0);/一一判隊(duì)滿算法一一intQueueFull1(QueueTypequ)return(qu.tag=1&&qu.front=qu.rear);/一-進(jìn)隊(duì)算法intenQueue1(QueueType&qu,ElemTypex)if(Queue

52、Full1(qu)=1)/隊(duì)滿return0;qu.rear=(qu.rear+1)%MaxSize;qu.dataqu.rear=x;qu.tag=1;/至少有一個(gè)元素，可能滿return1;/一一出隊(duì)算法一一intdeQueue1(QueueType&qu,ElemType&x)/出隊(duì)if(QueueEmpty1(qu)=1)/隊(duì)空return0;qu.front=(qu.front+1)%MaxSize;x=qu.dataqu.front;qu.tag=0;/出隊(duì)一個(gè)元素，可能空return1;35JJ(4)假設(shè)用一個(gè)循環(huán)單鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針rear指向隊(duì)尾結(jié)

53、點(diǎn)，但不設(shè)頭指針，設(shè)計(jì)出相應(yīng)的隊(duì)初始化、進(jìn)隊(duì)、出隊(duì)和判隊(duì)空的算法。解：假設(shè)鏈隊(duì)是不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，其示意圖如圖3.1所示。隊(duì)空條件：rear=NULL;進(jìn)隊(duì)操作：在*rear結(jié)點(diǎn)之后插入結(jié)點(diǎn)并讓rear指向該結(jié)點(diǎn)；出隊(duì)操作：刪除*rear結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)。對(duì)應(yīng)的算法如下：rear隊(duì)尾* an圖3.1不帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示隊(duì)列typedef struct node ElemType data;struct node *next; QNode;/鏈隊(duì)結(jié)點(diǎn)類型/初始化隊(duì)列void InitQueue(QNode *&rear)rear=NULL;/一-進(jìn)隊(duì)算法void EnQue

54、ue(QNode *&rear,ElemType x) QNode *s;s=(QNode *)malloc(sizeof(QNode);s->data=x;if (rear=NULL) s->next=s;rear=s;else/創(chuàng)建新結(jié)點(diǎn)/原鏈隊(duì)為空/構(gòu)成循環(huán)鏈表練習(xí)題及參考答案 s->next=rear->next;rear->next=s;rear=s;/一一出隊(duì)算法一一int DeQueue(QNode *&rear,ElemType &x) QNode *q;if (rear=NULL)return 0;else if (rea

55、r->next=rear) x=rear->data;free(rear);rear=NULL;else q=rear->next;x=q->data;rear->next=q->next;free(q);return 1;/一一判隊(duì)空算法一一int QueueEmpty(QNode *rear)return(rear=NULL);/將*s結(jié)點(diǎn)插入到*rear結(jié)點(diǎn)之后/讓rear指向這個(gè)新插入的結(jié)點(diǎn)/隊(duì)空/原隊(duì)中只有一個(gè)結(jié)點(diǎn)/原隊(duì)中有兩個(gè)或以上的結(jié)點(diǎn)上機(jī)實(shí)驗(yàn)題337-解：采用一個(gè)鏈棧來判斷操作序列是否合法,練習(xí)題及參考答案其中str為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個(gè)數(shù)(這里的ElemType類型設(shè)定為char)。對(duì)應(yīng)的算法如下：#include<stdio.h>#include<malloc.h>typedefstructn