算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

第一章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1.1簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、

邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

?數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載

體。

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)

元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由

若干數(shù)據(jù)項(xiàng)組成。

?數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組

操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語(yǔ)言中已實(shí)

現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織

形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)

構(gòu)和數(shù)據(jù)的運(yùn)算。

?邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。

?存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示,

稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu).

?線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)

為非空集，則該結(jié)構(gòu)有且只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)

點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后

繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是

線性結(jié)構(gòu)。

?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特

征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義

表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

.2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、

運(yùn)算三個(gè)方面的內(nèi)容。

答：例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)

生的身高、體重等各項(xiàng)體檢信息。這張登記表中，每個(gè)學(xué)生

的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每

個(gè)記錄（有姓名，學(xué)號(hào)，身高和體重等字段）就是一個(gè)結(jié)點(diǎn)，

對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)（它的前面無(wú)記錄）和一

個(gè)終端結(jié)點(diǎn)（它的后面無(wú)記錄），其他的結(jié)點(diǎn)則各有一個(gè)也只

有一個(gè)直接前趨和直接后繼（它的前面和后面均有且只有一

個(gè)記錄）。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)是線性結(jié)

構(gòu)。

這個(gè)表中的數(shù)據(jù)如何存儲(chǔ)到計(jì)算機(jī)里，并且如何表示數(shù)

據(jù)元素之間的關(guān)系呢？即用一片連續(xù)的內(nèi)存單元來(lái)存放這

些記錄（如用數(shù)組表示）還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針

進(jìn)行鏈接呢？這就是存儲(chǔ)結(jié)構(gòu)的問(wèn)題。

在這個(gè)表的某種存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對(duì)這張表中的

記錄進(jìn)行查詢，修改，刪除等操作。對(duì)這個(gè)表可以進(jìn)行哪些

操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問(wèn)題了。

1.3常用的存儲(chǔ)表示方法有哪幾種？

答：常用的存儲(chǔ)表示方法有四種:

?順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理

位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰

接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，通

常借助程序語(yǔ)言的數(shù)組描述。

?鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位

置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示。

由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，通常借助于程序語(yǔ)

言的指針類型描述。

?索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加

的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。組成索引表的索引項(xiàng)由結(jié)點(diǎn)的

關(guān)鍵字和地址組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引

項(xiàng)，則該索引表稱之為稠密索引(DenseIndex)。若一組結(jié)

點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索

引。

?散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該

結(jié)點(diǎn)的存儲(chǔ)地址。

1.4設(shè)三個(gè)函數(shù)f,g,h分別為f(n)=100n3+n2+1000,

g(n)=25n3+5000n2,h(n)=n1",+5000nlgn請(qǐng)判斷下列關(guān)系是

否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))

(3)h(n)=0(nL5)(4)h(n)=0(nlgn)

分析：數(shù)學(xué)符號(hào)〃0〃的嚴(yán)格的數(shù)學(xué)定義:

若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T

(n)=0(f(n))表示存在正的常數(shù)C和n0,使得當(dāng)nNnO

時(shí)都滿足OWT(n)WC?f(n)o

通俗地說(shuō)，就是當(dāng)n-8時(shí)，f(n)的函數(shù)值增長(zhǎng)速度與

T(n)的增長(zhǎng)速度同階。一般，一個(gè)函數(shù)的增長(zhǎng)速度與該函

數(shù)的最高次階同階。

即：即f(n))=i?

0(g(n))=n3

0(h(n))=n';)

所以答案為：

答：?(1)成立。?(2)成立。?(3)

成立。?(4)不成立。

1.5設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為

100/和21要使前者快于后者，n至少要多大？

分析：要使前者快于后者，即前者的時(shí)間消耗低于后者,

即：100/<才求解上式，可得

答:n=15

1.6設(shè)n為正整數(shù)，利用大〃0〃記號(hào)，將下列程序段的執(zhí)行

時(shí)間表示為n的函數(shù)。

(1)i=l；k=0;

while(i<n)

{k=k+10*i;i++;

分析:

i=l;//I

k=0;//I

while(i<n)//n

{k=k+10*i;//n-1

i++;//n-l

}

由以上列出的各語(yǔ)句的頻度，可得該程序段的時(shí)間消耗:

T(n)=l+l+n+(n-l)+(n-l)=3n

可表示為T(mén)(n)=0(n)

(2)i=0;k=0;

do{

k=k+10*i;i++;

}

while(i<n);

分析：

i=0;//I

k=0;//I

do(//n

k=k+10*i;//n

i++；//n

while(i<n);//n

由以上列出的各語(yǔ)句的頻度，可得該程序段的時(shí)間消耗：

T(n)=1+1+n+n+n+n=4n+2

可表示為T(mén)(n)=O(n)

⑶i=l;j=0;

while(i+j<=n)

{

if(i>j)j++；

elsei++;

}

分析：通過(guò)分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次

數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主

要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以

該程序段的執(zhí)行時(shí)間為：

T(n)=O(n)

(4)x=n;//n>l

while(x〉=(y+1)*(y+1))

y++;

分析：由x=n且x的值在程序中不變，又while的循環(huán)條

件(x>=(y+l)*(y+l))可知：當(dāng)(y+D*(y+l)剛超過(guò)n的值時(shí)

退出循環(huán)。

由(y+l)*(y+l)<n得:y<n0.5-1

所以，該程序段的執(zhí)行時(shí)間為：

向下取整下“0.5-1)

(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y一;)

elsex++;

分析：

x=91;//I

y=100;//I

while(y>0)//1101

if(x>100)//1100

{x=xTO;//100

y—;//100

}

else

x++;//1000

以上程序段右側(cè)列出了執(zhí)行次數(shù)。該程序段的執(zhí)行時(shí)間

為：T(n)=0⑴

1.7算法的時(shí)間復(fù)雜度僅與問(wèn)題的規(guī)模相關(guān)嗎？

答：算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模相關(guān)，還與輸入實(shí)

例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時(shí)間復(fù)雜度就

是只與求解問(wèn)題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)雜度時(shí)，

一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。

1.8按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100,

(3/2)",(2/3)n,nn,n05,n!,2n,Ign,nlgn,n(3/2)

答：常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列，依次為：常數(shù)階

0⑴、對(duì)數(shù)階0(1陽(yáng)2、線性階0(數(shù)、線性對(duì)數(shù)階0(nlog2n)、

平方階0(r)、立方階0(冒)、k次方階0(1?)、指數(shù)階0(2")。

先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對(duì)數(shù)

階：IgnK次方階：n*n(3/2)

指數(shù)階(按指數(shù)由小到大排)：1二(3/2)\指n!、nn

注意：(2/3)、由于底數(shù)小于1,所以是一個(gè)遞減函數(shù)，其數(shù)

量級(jí)應(yīng)小于常數(shù)階。

根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：

(2/3)n<2100<Ign<n05<n(3/2)<nlgn<(3/2)n<2n<n!

<nn

1.9有時(shí)為了比較兩個(gè)同數(shù)量級(jí)算法的優(yōu)劣，須突出主項(xiàng)的

常數(shù)因子，而將低次項(xiàng)用大〃0〃記號(hào)表示。例如，設(shè)

Ti(n)=1.39nlgn+100n+256=l.39nlgn+0(n),

T2(n)=2.0nlgn-2n=2.01gn+0(n),這兩個(gè)式子表示，當(dāng)n足

夠大時(shí)Z(n)優(yōu)于Tz(n),因?yàn)榍罢叩某?shù)因子小于后者。請(qǐng)

用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu),

哪一個(gè)較劣?

函數(shù)大〃0〃表示優(yōu)劣

(1)Ti(n)=5n"-3n+601gn5n2+0(n)較差

22

(2)T2(n)=3n+1000n+31gn3n+0(n)其次

22

(3)T3(n)=8n+31gn8n+0(Ign)最差

(4)T,i(n)=l.5n-+6000nlgn1.5n2+0(nlgn)最優(yōu)

第二章線性表

2.1試描述頭指針、頭結(jié)點(diǎn)、開(kāi)始結(jié)點(diǎn)的區(qū)別、并說(shuō)明頭指

針和頭結(jié)點(diǎn)的作用。

答：開(kāi)始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，也就是沒(méi)有直接前

趨的那個(gè)結(jié)點(diǎn)。

鏈表的頭指針是一指向鏈表開(kāi)始結(jié)點(diǎn)的指針（沒(méi)有頭結(jié)點(diǎn)

時(shí)），單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針

的名字來(lái)命名。

頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭

結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總

是非空。而且頭指針的設(shè)置使得對(duì)鏈表的第一個(gè)位置上的操

作與在表其他位置上的操作一致（都是在某一結(jié)點(diǎn)之后）。

2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)

為宜？

答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)選擇順

序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下兒方面的考

慮:

1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，

易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表;

反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用

動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。

2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很

少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之,

若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用

鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表

的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。

2.3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)

點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素？

答：在等概率情況下，順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2

個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)(n-l)/2個(gè)結(jié)點(diǎn)。具體的

移動(dòng)次數(shù)取決于順序表的長(zhǎng)度n以及需插入或刪除的位置i。

i越接近n則所需移動(dòng)的結(jié)點(diǎn)數(shù)越少。

2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？

答：尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈

表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一

帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear,則開(kāi)始結(jié)點(diǎn)和終

端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)

間都是0(1)。

若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為

0(n)o

2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指

向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*P從相應(yīng)的鏈表中刪

去?若可以，其時(shí)間復(fù)雜度各為多少？

答：下面分別討論三種鏈表的情況。

1.單鏈表。若指針P指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針

找到其直接后繼，能夠順后繼指針鏈找到*p結(jié)點(diǎn)后的結(jié)點(diǎn)。

但是由于不知道其頭指針，所以無(wú)法訪問(wèn)到P指針指向的結(jié)

點(diǎn)的直接前趨。因此無(wú)法刪去該結(jié)點(diǎn)。

2.雙鏈表。由于這樣的鏈表提供雙向指針，根據(jù)*p結(jié)

點(diǎn)的前趨指針和后繼指針可以查找到其直接前趨和直接后

繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為0(1)。

3.單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，可以直接得到其

后相鄰的結(jié)點(diǎn)位置(直接后繼)，又因?yàn)槭茄h(huán)鏈表，所以我

們可以通過(guò)查找，得到p結(jié)點(diǎn)的直接前趨。因此可以刪去p

所指結(jié)點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為0(n)。

2.6下述算法的功能是什么？

LinkListDemo(LinkListL){//L是無(wú)頭結(jié)點(diǎn)單鏈表

ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

)

returnL;

}//Demo

答：該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后

成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)

點(diǎn)，返回新鏈表的頭指針。

2.7設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,ab...,重寫(xiě)順序表

上實(shí)現(xiàn)的插入和刪除算法：InsertList和DeleteList.解：

算法如下：

ttdefineListSize100//假定表空間大小為100

typedefintDataType;〃假定DataType的類型為int型

typedefstruct{

DataTypedata[ListSize];//向量data用于存放表結(jié)點(diǎn)

intlength;//當(dāng)前的表長(zhǎng)度

}Seqlist;

〃以上為定義表結(jié)構(gòu)

voidInsertList(Seqlist*L,Datatypex,inti)

(〃將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位

置上，即插入的合法位置為：0<=i<=L->length

intj;

if(i<0||i>L->length)

Error("positionerror");〃非法位置，退出，該函數(shù)定

義見(jiàn)教材P7.

if(L->length>=ListSize)

Error("overflow");

for(j=L->length-l;j>=i;j—)

L->data[j+l]=L->data[j];

L->data[i]=x;

L->length++;

}

voidDeleteList(Seqlist*L,inti)

{//從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai,合法的刪除位

置為0〈二i〈二L->length-l

intj;

if(i<0||i>=L->length)

Error(〃positionerror");

for(j=i;j<L->length;j++)

L->data[j]=L->data[j+1]；〃結(jié)點(diǎn)前移

L->length一;〃表長(zhǎng)減小

}

2.8試分別用順序表和單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表

(a0,.aQ就地逆置的操作，所謂〃就地〃指輔助空間應(yīng)為

0(l)o

答：1.順序表:

要將該表逆置，可以將表中的開(kāi)始結(jié)點(diǎn)與終端結(jié)點(diǎn)互

換，第二個(gè)結(jié)點(diǎn)與倒數(shù)第二個(gè)結(jié)點(diǎn)互換，如此反復(fù)，就可將

整個(gè)表逆置了。算法如下：

//順序表結(jié)構(gòu)定義同上題

voidReverseList(Seqlist*L)

(

DataTypetemp;〃設(shè)置臨時(shí)空間用于存放data

inti;

for(i=0;i<=L->length/2;i++)〃L->length/2為整

除運(yùn)算

{temp=L->data[i];〃交換數(shù)據(jù)

L->data[i]=L->data[L->length--i];

L->data[L->length-1-i]=temp;

)

}

2.鏈表：

分析：可以用交換數(shù)據(jù)的方式來(lái)達(dá)到逆置的目的。但是

由于是單鏈表，數(shù)據(jù)的存取不是隨機(jī)的，因此算法效率太低。

可以利用指針改指來(lái)達(dá)到表逆置的目的。具體情況入下：

(1)當(dāng)鏈表為空表或只有一個(gè)結(jié)點(diǎn)時(shí)，該鏈表的逆置鏈

表與原表相同。

(2)當(dāng)鏈表含2個(gè)以上結(jié)點(diǎn)時(shí)，可將該鏈表處理成只含第

一結(jié)點(diǎn)的帶頭結(jié)點(diǎn)鏈表和一個(gè)無(wú)頭結(jié)點(diǎn)的包含該鏈表剩余

結(jié)點(diǎn)的鏈表。然后，將該無(wú)頭結(jié)點(diǎn)鏈表中的所有結(jié)點(diǎn)順著鏈

表指針，由前往后將每個(gè)結(jié)點(diǎn)依次從無(wú)頭結(jié)點(diǎn)鏈表中摘下，

作為第一個(gè)結(jié)點(diǎn)插入到帶頭結(jié)點(diǎn)鏈表中。這樣就可以得到逆

置的鏈表。算法是這樣的：

結(jié)點(diǎn)結(jié)構(gòu)定義如下：

typedefcharDataType;〃假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類

型的字符

typedefstructnode{〃結(jié)點(diǎn)類型定義

DataTypedata;〃結(jié)點(diǎn)的數(shù)據(jù)域

structnode*next;〃結(jié)點(diǎn)的指針域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

LinkListReverseList(LinkListhead)

{//將head所指的單鏈表(帶頭結(jié)點(diǎn))逆置

ListNode*p,*q；〃設(shè)置兩個(gè)臨時(shí)指針變量

if(head->next&&head->next->next)

{〃當(dāng)鏈表不是空表或單結(jié)點(diǎn)時(shí)

p=head->next;

q=p->next;

p->next=NULL;〃將開(kāi)始結(jié)點(diǎn)變成終端結(jié)點(diǎn)

while(q)

{〃每次循環(huán)將后一個(gè)結(jié)點(diǎn)變成開(kāi)始結(jié)點(diǎn)

PF；

q=q->next;

p->next=head->next;

head->next=p;

}

returnhead;

)

returnhead;〃如是空表或單結(jié)點(diǎn)表，直接返回

head

2.9設(shè)順序表L是一個(gè)遞增有序表，試寫(xiě)一算法，將x插入

L中，并使L仍是一個(gè)有序表。

答：因已知順序表L是遞增有序表，所以只要從順序表終

端結(jié)點(diǎn)(設(shè)為i位置元素)開(kāi)始向前尋找到第一個(gè)小于或等

于x的元素位置i后插入該位置即可。

在尋找過(guò)程中，由于大于x的元素都應(yīng)放在x之后，所

以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于X的元

素位置i時(shí)，該位置也空出來(lái)了。

算法如下：

〃順序表存儲(chǔ)結(jié)構(gòu)如題2.7

voidInsertlncreaseList(Seqlist*L,Datatype

x)

(

inti;

if(L->length>=ListSize)

Error("overflow");

for(i=L->length;i>0&&L->data[i-l]>

x;i—)

L->data[i]=L->data[i];//比較并

移動(dòng)元素

L->data[i]=x;

L->length++;

}

2.10設(shè)順序表L是一個(gè)遞減有序表，試寫(xiě)一算法，將x插

入其后仍保持L的有序性。

答：與上題相類似，只要從終端結(jié)點(diǎn)開(kāi)始往前找到第一個(gè)比

x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。(邊尋

找，邊移動(dòng))算法如下:

voidInsertDecreaseList(Seqlist*L,Datatypex)

inti;

if(L->length>=ListSize)

Error("overflow");

for(i=L->length;i>0&&L->data[i-l]<

x;i—)

L->data[i]=L->data[i];//比較并移動(dòng)

元素

L->data[i]=x;

L->length++;

)

2.11寫(xiě)一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)

算。

解：由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的

方法來(lái)數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法如下：

intListLength(LinkListL)

(

intlen=0;

ListNode*p;

P二L;〃設(shè)該表有頭結(jié)點(diǎn)

while(p->next)

p=p->next;

len++;

returnlen;

)

2.12已知LI和L2分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且已知其

長(zhǎng)度分別為m和no試寫(xiě)一算法將這兩個(gè)鏈表連接在一起，

請(qǐng)分析你的算法的時(shí)間復(fù)雜度。

解：

分析：由于要進(jìn)行的是兩單鏈表的連接，所以應(yīng)找到放

在前面的那張表的表尾結(jié)點(diǎn)，再將后表的開(kāi)始結(jié)點(diǎn)鏈接到前

表的終端結(jié)點(diǎn)后即可。該算法的主要時(shí)間消耗是用在尋找第

一張表的終端尾結(jié)點(diǎn)上。這兩張單鏈表的連接順序無(wú)要求，

并且已知兩表的表長(zhǎng)，則為了提高算法效率，可選表長(zhǎng)小的

單鏈表在前的方式連接。

具體算法如下：

LinkListLink(LinkListLI,LinkListL2,intm,int

n)

{〃將兩個(gè)單鏈表連接在一起

ListNode*p,*q,*s;

〃s指向短表的頭結(jié)點(diǎn),q指向長(zhǎng)表的開(kāi)始結(jié)點(diǎn)，回

收長(zhǎng)表頭結(jié)點(diǎn)空間

if(m<=n)

{s=Ll;q=L2->next;free(L2);}

else{s=L2;q=Ll->next;free(LI);}

P二s;

while(p->next)p=p->next;〃查找短表終端

結(jié)點(diǎn)

p->next=q;〃將長(zhǎng)表的開(kāi)始結(jié)點(diǎn)鏈接在短表終

端結(jié)點(diǎn)后

returns;

}

本算法的主要操作時(shí)間花費(fèi)在查找短表的終端結(jié)點(diǎn)上，

所以本算的法時(shí)間復(fù)雜度為：0(min(m,n))

2.13設(shè)A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫(xiě)

一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C,

并要求輔助空間為0(1),請(qǐng)分析算法的時(shí)間復(fù)雜度。

解：根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以可以先

取A表的表頭建立空的C表。然后同時(shí)掃描A表和B表，將

兩表中最大的結(jié)點(diǎn)從對(duì)應(yīng)表中摘下，并作為開(kāi)始結(jié)點(diǎn)插入C

表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A

表或B表中的結(jié)點(diǎn)依次摘下并作為開(kāi)始結(jié)點(diǎn)插入C表中。這

時(shí)，得到的C表就是由A表和B表歸并成的一個(gè)按元素值遞

減有序的單鏈表C。并且輔助空間為0(1)。

算法如下：

LinkListMergeSort(LinkListA,LinkListB)

{//歸并兩個(gè)帶頭結(jié)點(diǎn)的遞增有序表為一個(gè)帶頭結(jié)

點(diǎn)遞減有序表

ListNode*pa,*pb,*q,*C;

pa=A->next;//pa指向A表開(kāi)始結(jié)點(diǎn)

C=A;C->next=NULL;〃取A表的表頭建立空的C表

pb=B->next;//pb指向B表開(kāi)始結(jié)點(diǎn)

free(B);〃回收B表的頭結(jié)點(diǎn)空間

while(pa&&pb)

{

if(pb->data<=pa->data)

{〃當(dāng)B中的元素小于等于A中當(dāng)前元素

時(shí)，將pa表的開(kāi)始結(jié)點(diǎn)摘下

q=pa;pa=pa->next;

}

else

{//當(dāng)B中的元素大于A中當(dāng)前元素時(shí)，將

pb表的開(kāi)始結(jié)點(diǎn)摘下

q=pb;pb=pb->next;}

q->next=C->next;C->next=q;〃將摘下的結(jié)

點(diǎn)q作為開(kāi)始結(jié)點(diǎn)插入C表

}

〃若pa表非空，則處理pa表

while(pa){

q=pa;pa=pa->next;

q->next=C->next;C->next=q;}

〃若pb表非空，則處理pb表

while(pb){

q=pb;pa=pb->next;

q->next=C->next;C->next=q;}

return(C);

該算法的時(shí)間復(fù)雜度分析如下：

算法中有三個(gè)while循環(huán)，其中第二個(gè)和第三個(gè)循環(huán)只

執(zhí)行一個(gè)。每個(gè)循環(huán)做的工作都是對(duì)鏈表中結(jié)點(diǎn)掃描處理。

整個(gè)算法完成后，A表和B表中的每個(gè)結(jié)點(diǎn)都被處理了一遍。

所以若A表和B表的表長(zhǎng)分別是m和n,則該算法的時(shí)間復(fù)

雜度O(m+n)

2.14已知單鏈表L是一個(gè)遞增有序表，試寫(xiě)一高效算法，

刪除表中值大于min且小于max的結(jié)點(diǎn)(若表中有這樣的結(jié)

點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min和max是兩個(gè)給

定的參數(shù)。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。

解：要解這樣的問(wèn)題，我們首先想到的是拿鏈表中的元素一

個(gè)個(gè)地與max和min比較，然后刪除這個(gè)結(jié)點(diǎn)。由于為已知

其是有序鏈表，則介于min和max之間的結(jié)點(diǎn)必為連續(xù)的一

段元素序列。所以我們只要先找到所有大于min結(jié)點(diǎn)中的最

小結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)*P后，依次刪除小于max的結(jié)點(diǎn)，直

到第一個(gè)大于等于max結(jié)點(diǎn)*q位置，然后將*p結(jié)點(diǎn)的直接

后繼指針指向*q結(jié)點(diǎn)。

算法如下：

voidDeleteList(LinkListL,DataTypemin,

DataTypemax)

(

ListNode*p,*q,*s;

P=L;

whi1e(p->next&&p->next->data<=min)

〃找比min大的前一個(gè)元素位置

p=p->next;

q=p->next;//p指向第一個(gè)不大于min結(jié)點(diǎn)的直接

前趨，q指向第一個(gè)大于min的結(jié)點(diǎn)

while(q&&q->data<max)

{s=q;q=q->next;

free(s);〃刪除結(jié)點(diǎn)，釋放空間

p->next=q;〃將*p結(jié)點(diǎn)的直接后繼指針指向*q結(jié)

點(diǎn)

2.15寫(xiě)一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)

果表中各結(jié)點(diǎn)值均不相同。

解：本題可以這樣考慮，先取開(kāi)始結(jié)點(diǎn)中的值，將它與其后

的所有結(jié)點(diǎn)值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取第

二結(jié)點(diǎn)的值，重復(fù)上述過(guò)程直到最后一個(gè)結(jié)點(diǎn)。

具體算法：

voidDeleteList(LinkListL)

(

ListNode*p,*q,*s;

p=L-next;

while(p->next&&p->next->next)

{

q二p；〃由于要做刪除操作，所以q指針指向

要?jiǎng)h除元素的直接前趨

while(q->next)

if(p->data==q->next->data)

{s=q->next;q->next=s->next;free(s);〃刪除與*p的值相

同的結(jié)點(diǎn)

elseq=q->next;

p=p->next;

)

)

2.16假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭

指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法刪除結(jié)

點(diǎn)*s的直接前趨結(jié)點(diǎn)。

解：已知指向這個(gè)結(jié)點(diǎn)的指針是*s,那么要?jiǎng)h除這個(gè)結(jié)點(diǎn)的

直接前趨結(jié)點(diǎn)，就只要找到一個(gè)結(jié)點(diǎn)，它的指針域是指向*s

的直接前趨，然后用后刪結(jié)點(diǎn)法，將結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)

刪除即可。

算法如下：

voidDeleteNode(ListNode*s)

{〃刪除單循環(huán)鏈表中指定結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)

ListNode*p,*q;

P=s;

while(p->next->next!=s)

p=p->next;

〃刪除結(jié)點(diǎn)

q=p->next;

p->next=q->next;

free(p);〃釋放空間

注意：若單循環(huán)鏈表的長(zhǎng)度等于1,則只要把表刪空即

可。

2.17已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)

元素(如：字母字符、數(shù)字字符和其它字符)，試編寫(xiě)算法構(gòu)

造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的

字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，

頭結(jié)點(diǎn)可另辟空間。

解：要解決這樣的問(wèn)題，只要新建三個(gè)頭結(jié)點(diǎn)，然后在原

來(lái)的單鏈表中依次查詢，找到一類字符結(jié)點(diǎn)時(shí)，就摘下此結(jié)

點(diǎn)鏈接到相應(yīng)頭結(jié)點(diǎn)指明的新鏈表中就是了。

算法如下：

〃設(shè)已建立三個(gè)帶頭結(jié)點(diǎn)的空循環(huán)鏈表A,B,C且A、B、

C分別是尾指針.

voidDivideList(LinkListL,LinkListA,LinkList

B,LinkListC)

(

ListNode*p=L->next,*q;

while(p)

if(p->data>=，a'&&p->data<=，z'

p->data>='A'&&p->data<=，Z')

q=p->next;

p=p->next;〃指向下一結(jié)點(diǎn)

q->next=A->next;〃將字母結(jié)點(diǎn)鏈到A表

中

A->next=q;A=q;

}

elseif(p-〉data>='O'&&p->data<=，)

{//分出數(shù)字結(jié)點(diǎn)

q=p->next;

p=p->next;〃指向下一結(jié)點(diǎn)

q->next=B->next;〃將數(shù)字結(jié)點(diǎn)鏈

到B表中

B->next=q;B=q;

}

else{〃分出其他字符結(jié)點(diǎn)

q=p->next;

p=p->next;〃指向下一結(jié)點(diǎn)

q->next=C->next;〃將其他結(jié)

點(diǎn)鏈到C表中

C->next=q;C=q;

}

}〃結(jié)束

2.18設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next

三個(gè)域外，還有一個(gè)訪問(wèn)頻度域freq,在鏈表被起用之前，

其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,x)

運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1,并調(diào)整表

中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減序排列，以便使頻繁

訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一符合上述要求的

LocateNode運(yùn)算的算法。

解：LocateNode運(yùn)算的基本思想就是在雙向鏈表中查找值

為x的結(jié)點(diǎn)，具體方法與單鏈表中查找一樣。找到結(jié)點(diǎn)*p后

給freq域的值加1。由于原來(lái)比*p結(jié)點(diǎn)查找頻度高的結(jié)點(diǎn)都

排它前面，所以，接下去要順著前趨指針找到第一個(gè)頻度小

于或等于*P結(jié)點(diǎn)頻度的結(jié)點(diǎn)*q后，將*P結(jié)點(diǎn)從原來(lái)的位置

刪除，并插入到*q后就可以了。

算法如下：

〃雙向鏈表的存儲(chǔ)結(jié)構(gòu)

typedefstructdlistnode(

DataTypedata;

structdlistnode*prior,*next;

intfreq;

}DListNode;

typedefDListNode*DLinkList;

voidLocateNode(LinkListL,DataTypex)

{

ListNode*p,*q;

p=L->next;〃帶有頭結(jié)點(diǎn)

while(p&&p->data!=x)

p=p->next;

if(!p)ERRORCxisnotinL〃)；〃雙鏈表中

無(wú)值為x的結(jié)點(diǎn)

else{p->freq++;〃freq加1

q=p->prior;〃以q為掃描指針尋找第一

個(gè)頻度大于或等于*P頻度的結(jié)點(diǎn)

while(q!=L&&q->freq<p->freq)

q=q->prior;

if(q->next!=p)〃若*q結(jié)點(diǎn)和*p結(jié)點(diǎn)

不為直接前趨直接后繼關(guān)系,

〃則將*P結(jié)點(diǎn)鏈到*q

結(jié)點(diǎn)后

{p->prior->next=p->next;〃將*p從

原來(lái)位置摘下

p->next->prior=p->prior;

q-〉next->prior=p;〃將*p插入*q之

后。

p->next=q->next;

q-〉next=p;

p->prior=q;

第三章

3.1設(shè)將整數(shù)1,2,3,4依次進(jìn)棧，但只要出棧時(shí)棧非

空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問(wèn)題：

(1)若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),

Pop(),Pop(),Push(4),Pop(),則出棧的數(shù)字序列為何(這

里Push⑴表示i進(jìn)棧，Pop()表示出棧)？

(2)能否得到出棧序列1423和1432?并說(shuō)明為什么不能

得到或者如何得到。

(3)請(qǐng)分析1,2,3,4的24種排列中，哪些序列是

可以通過(guò)相應(yīng)的入出棧操作得到的。

答：(1)出棧序列為：1324

(2)不能得到1423序列。因?yàn)橐玫?4的出棧序列，則應(yīng)做

Push(1),Pop(),Push(2),Push(3),Push(4),Pop()o這樣,

3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432

的出棧序列。具體操作為：Push(l),

Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1,2,3,4的24種排列中，可通過(guò)相應(yīng)入出棧

操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3

214,3241,3421,4321

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

3.2鏈棧中為何不設(shè)置頭結(jié)點(diǎn)？

答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)

行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)

行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可

以了。3.3循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？

答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的〃假上溢〃現(xiàn)

象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)

隊(duì)列的〃空〃或〃滿〃不能以頭尾指針是否相等來(lái)確定，一般是

通過(guò)以下幾種方法：一是另設(shè)一布爾變量來(lái)區(qū)別隊(duì)列的空和

滿。二是少用一個(gè)元素的空間，每次入隊(duì)前測(cè)試入隊(duì)后頭尾

指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一

計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得

到隊(duì)列中元素的個(gè)數(shù)。

3.4設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則

入隊(duì)出隊(duì)操作的時(shí)間為何？若只設(shè)尾指針呢？

答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1,而入隊(duì)的時(shí)間需要n,

因?yàn)槊看稳腙?duì)均需從頭指針開(kāi)始查找，找到最后一個(gè)元素時(shí)

方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。

因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)?/p>

元素，所以出隊(duì)時(shí)不需要遍歷整個(gè)隊(duì)列。3.5指出下述程序

段的功能是什么？

(1)voidDemol(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}//Demol

(2)SeqStackSI,S2,tmp;

DataTypex;

...〃假設(shè)棧tmp和S2已做過(guò)初始化

while(!StackEmpty(&S1))

(

x=Pop(&S1);

Push(&tmp,x);

while(!StackEmpty(&tmp))

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

(3)voidDemo2(SeqStack*S,intm)

{//設(shè)DataType為int型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

(

i=Pop(&T);Push(S,i);

}

}

(4)voidDemo3(CirQueue*Q)

{//設(shè)DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x二DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

(5)CirQueueQI,Q2;//設(shè)DataType為int型

intx,i,n=0;

...//設(shè)QI已有內(nèi)容，Q2已初始化過(guò)

while(!QueueEmpty(&Q1))

{x二DeQueue(&Q1);EnQueue(&Q2,x);n++;}

for(i=0;i<n;i++)

{x二DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);)

答：(1)程序段的功能是將一棧中的元素按反序重新排列，

也就是原來(lái)在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂?/p>

此棧中元素個(gè)數(shù)限制在64個(gè)以內(nèi)。

(2)程序段的功能是利用tmp棧將一個(gè)非空棧si的所有

元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。

(3)程序段的功能是利用棧T,將一個(gè)非空棧S中值等于

m的元素全部刪去。

(4)程序段的功能是將一個(gè)循環(huán)隊(duì)列Q經(jīng)過(guò)S棧的處理,

反向排列，原來(lái)的隊(duì)頭變成隊(duì)尾，原來(lái)的隊(duì)尾變成隊(duì)頭。

(5)這段程序的功能是將隊(duì)列1的所有元素復(fù)制到隊(duì)列2

中去，但其執(zhí)行過(guò)程是先把隊(duì)列1的元素全部出隊(duì)，進(jìn)入隊(duì)

列2,然后再把隊(duì)列2的元素復(fù)制到隊(duì)列1中。

3.6回文是指正讀反讀均相同的字符序列，如〃abba〃和

〃abdba〃均是回文，但〃good〃不是回文。試寫(xiě)一個(gè)算法判定

給定的字符向量是否為回文。(提示：將一半字符入棧)

解：根據(jù)提示，算法可設(shè)計(jì)為：

〃以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義

^defineStackSize100〃假定預(yù)分配的?？臻g最多為100

個(gè)元素

typedefcharDataType;〃假定棧元素的數(shù)據(jù)類型為字符

typedefstruct(

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

{〃判斷t字符向量是否為回文，若是，返回1,否則返

回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);〃求向量長(zhǎng)度

for(i=0;i<len/2;i++)〃將一半字符入棧

Push(&s,t[i]);

while(!EmptyStack(&s))

{//每彈出一個(gè)字符與相應(yīng)字符比較

temp=Pop(&s);

if(temp!=S[i])return0;//不等則返回0

elsei++;

)

return1;//比較完畢均相等則返回1

}

3.7利用棧的基本操作，寫(xiě)一個(gè)將棧S中所有結(jié)點(diǎn)均刪去的

算法voidClearStack(SeqStack*S),并說(shuō)明S為何要作

為指針參數(shù)？

解：算法如下

voidClearStack(SeqStack*S)

{//刪除棧中所有結(jié)點(diǎn)

S->Top=-1;〃其實(shí)只是將棧置空

)

因?yàn)橐每盏氖菞,如果不用指針來(lái)做參數(shù)傳遞，那

么函數(shù)進(jìn)行的操作不能對(duì)原來(lái)的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)

存中開(kāi)辟另外的單元來(lái)對(duì)形參進(jìn)行函數(shù)操作。結(jié)果等于什么

也沒(méi)有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就

只能用指針來(lái)做參數(shù)傳遞了。

3.8利用棧的基本操作，寫(xiě)一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法

intStackSize(SeqStackS),并說(shuō)明S為何不作為指針參

數(shù)？

解：算法如下：

intStackSize(SeqStackS)

{〃計(jì)算棧中結(jié)點(diǎn)個(gè)數(shù)

intn=0;

if(!EmptyStack(&S))

(

Pop(&S);

n++;

)

returnn;

)

上述算法的目的只要得到S棧的結(jié)點(diǎn)個(gè)數(shù)就可以了。并

不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對(duì)原來(lái)

的棧中元素進(jìn)行任何改變。系統(tǒng)會(huì)把原來(lái)的棧按值傳遞給形

參，函數(shù)只對(duì)形參進(jìn)行操作，最后返回元素個(gè)數(shù)。

3.9設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì)。

(提示：對(duì)表達(dá)式進(jìn)行掃描，凡遇到‘('就進(jìn)棧，遇就退

掉棧頂?shù)摹?’，表達(dá)式被掃描完畢，棧應(yīng)為空。

解：根據(jù)提示，可以設(shè)計(jì)算法如下：

intPairBracket(char*SR)

{〃檢查表達(dá)式ST中括號(hào)是否配對(duì)

inti;

SeqStackS;〃定義一個(gè)棧

InitStack(&s);

for(i=0;i<strlen(SR);i++)

(

if(S[i]='(')Push(&S,〃遇'('

時(shí)進(jìn)棧

if(S[i]==))〃遇')’

if(!StackEmpty(S))〃棧不為空時(shí),將棧頂

元素出棧

Pop(&s);

elsereturn0;〃不匹配,返回0

)

ifEmptyStack(&s)return1;//匹配，返回1

elsereturn0;〃不匹配,返回0

}

3.10一個(gè)雙向棧S是在同一向量空間內(nèi)實(shí)現(xiàn)的兩個(gè)棧，它

們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計(jì)初

始化InitStack(S)、入棧Push(S,i,x)和出棧Pop(S,

i)等算法，其中i為0或1,用以表示棧號(hào)。

解：雙向棧其實(shí)和單向棧原理相同，只是在一個(gè)向量空間內(nèi)，

好比是兩個(gè)頭對(duì)頭的棧放在一起，中間的空間可以充分利

用。雙向棧的算法設(shè)計(jì)如下：

〃雙向棧的棧結(jié)構(gòu)類型與以前定義略有不同

ttdefineStackSize100//假定分配了100個(gè)元素的向量

空間

#definecharDataType

typedefstruct(

DataTypeData[StackSize]

inttopO;〃需設(shè)兩個(gè)指針

inttopi;

}DblStack

voidInitStack(DblStack*S)

{〃初始化雙向棧

S->topO=-1;

S->topl=StackSize;〃這里的top2也指出了向量

空間，但由于是作為棧底，因此不會(huì)出錯(cuò)

}

intEmptyStack(DblStack*S,inti)

{〃判?？?棧號(hào)i)

return(i==0&&S->topO==-1||i==1&&

S->topl==StackSize)

intFullStack(DblStack*S)

{〃判棧滿,滿時(shí)肯定兩頭相遇

return(S->topO==S-topl-l);

voidPush(DblStack*S,inti,DataTypex)

{〃進(jìn)棧(棧號(hào)i)

if(FullStack(S))

Error(''Stackoverflow");〃上溢、退出運(yùn)行

if(i==0)S->Data[++S->topO]=x;〃棧0入

棧

if(i==1)S->Data[-S->topl]=x;//棧1入

棧

}

DataTypePop(DblStack*S,inti)

{〃出棧(棧號(hào)i)

if(EmptyStack(S,i))

Error("Stackunderflow");〃下溢退出

if(i==0)

return(S->Data[S->topO-])；〃返回棧頂元

素，指針值減1

if(i==l)

return(S->Data[S->topl++]);〃因?yàn)檫@個(gè)棧

是以另一端為底的，所以指針值加1。

3.11Ackerman函數(shù)定義如下：請(qǐng)寫(xiě)出遞歸算法。

nn+1當(dāng)m=0時(shí)

AKM(m,n)=|AKM(m-1,1)當(dāng)mWO,n=0時(shí)

LAKM(m-1,AKM(m,n-l))當(dāng)mWO,nW

0時(shí)

解：算法如下

intAKM(intm,intn)

{if(m==0)returnn+1;

if(m<>0&&n==0)returnAKM(m-1,1);

if(m<>0&&n<>0)returnAKM(m-1,AKM(m,

n-1));

}

3.12用第二種方法，即少用一個(gè)元素空間的方法來(lái)區(qū)別循

環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試為其設(shè)計(jì)置空隊(duì)，判隊(duì)空，判隊(duì)滿、

出隊(duì)、入隊(duì)及取隊(duì)頭元素等六個(gè)基本操作的算法。

解：算法設(shè)計(jì)如下：

〃循環(huán)隊(duì)列的定義

#defineQueueSize100

typedefcharDatatype;〃設(shè)元素的類型為char型

typedefstruct{

intfront;

intrear;

DataTypeData[QueueSize];

}CirQueue;

(1)置空隊(duì)

voidInitQueue(CirQueue*Q)

{//置空隊(duì)

Q->front=Q->rear=0;

)

⑵判隊(duì)空

intEmptyQueue(CirQueue*Q)

{〃判隊(duì)空

returnQ->front==Q->rear;

}

⑶判隊(duì)滿

intFullQueue(CirQueue*Q)

{//判隊(duì)滿〃如果尾指針加1后等于頭指針，則認(rèn)為

滿

return(Q->rear+l)%QueueSize==Q->front;

4）出隊(duì)

DataTypeDeQueue(CirQueue*Q)

{〃出隊(duì)

DataTypetemp;

if(EmptyQueue(Q))

Error(〃隊(duì)已空，無(wú)元素可以出隊(duì)〃)；

teInp=Q->Data[Q->front];〃保存元素值

Q->front=(Q->front+l)%QueueSize;〃循環(huán)意

義上的加1

returntemp;〃返回元素值

)

⑸入隊(duì)

voidEnQueue(CirQueue*Q,DataTypex)

{//入隊(duì)

if(FullQueue(Q))

Error(〃隊(duì)已滿，不可以入隊(duì)〃)；

Q->Data[Q->rear]=x;

Q->rear=(Q->rear+l)%QueueSize;//rear指向下

一個(gè)空元素位置

}

(6)取隊(duì)頭元素

DataTypeFrontQueue(CirQueue*Q)

{〃取隊(duì)頭元素

if(EmptyQueue(Q))

Error(〃隊(duì)空，無(wú)元素可取〃);

returnQ->Data[Q->front];

3.13假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)

指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針)，試編寫(xiě)相應(yīng)的

置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。

解：算法如下：

〃先定義鏈隊(duì)結(jié)構(gòu)：

typedefstructqueuenode(

Datatypedata;

structqueuenode*next;

}QueueNode;〃以上是結(jié)點(diǎn)類型的定義

typedefstruct{

queuenode*rear;

}LinkQueue;〃只設(shè)一個(gè)指向隊(duì)尾元素的指針

(1)置空隊(duì)

voidInitQueue(LinkQueue*Q)

{〃置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素

QueueNode*s;

Q->rear=Q->rear->next;〃將隊(duì)尾指針指向頭結(jié)

點(diǎn)

while(Q->rear!=Q->rear->next)〃當(dāng)隊(duì)列非空，

將隊(duì)中元素逐個(gè)出隊(duì)

{s=Q->rear->next;

Q->rear->next=s->next;

free(s);

"/回收結(jié)點(diǎn)空間

}

⑵判隊(duì)空

intEmptyQueue(LinkQueue*Q)

{〃判隊(duì)空

〃當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì)

returnQ->rear->next->next==Q->rear->next;

)

⑶入隊(duì)

voidEnQueue(LinkQueue*Q,Datatypex)

{〃入隊(duì)

〃也就是在尾結(jié)點(diǎn)處插入元素

QueueNode*p=(QueueNode*)malloc

(sizeof(QueueNode));〃申請(qǐng)新結(jié)點(diǎn)

p->data=x;p->next=Q->rear->next;〃初始化新

結(jié)點(diǎn)并鏈入

Q-rear->next=p;

Q->rear=p;〃將尾指針移至新結(jié)點(diǎn)

}

⑷出隊(duì)

DatatypeDeQueue(LinkQueue*Q)

{〃出隊(duì)把頭結(jié)點(diǎn)之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflo