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

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

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

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

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

體。

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

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

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

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

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

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

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

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

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

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

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

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

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

為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)

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

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

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

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

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

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

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

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

答：例如有一張學生體檢情況登記表，記錄了一個班的學

生的身高、體重等各項體檢信息。這張登記表中，每個學生

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

個記錄（有姓名，學號，身高和體重等字段）就是一個結(jié)點，

對于整個表來說，只有一個開始結(jié)點（它的前面無記錄）和一

個終端結(jié)點（它的后面無記錄），其他的結(jié)點則各有一個也只

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

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

構(gòu)。

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

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

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

進行鏈接呢？這就是存儲結(jié)構(gòu)的問題。

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

記錄進行查詢，修改，刪除等操作。對這個表可以進行哪些

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

1.3常用的存儲表示方法有哪幾種？

答：常用的存儲表示方法有四種:

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

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

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

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

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

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

由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)，通常借助于程序語

言的指針類型描述。

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

的索引表來標識結(jié)點的地址。組成索引表的索引項由結(jié)點的

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

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

點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索

引。

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

結(jié)點的存儲地址。

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

g(n)=25n3+5000n2,h(n)=n1",+5000nlgn請判斷下列關(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ù)學符號〃0〃的嚴格的數(shù)學定義:

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

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

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

通俗地說，就是當n-8時，f(n)的函數(shù)值增長速度與

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

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

即：即f(n))=i?

0(g(n))=n3

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

所以答案為：

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

成立。?(4)不成立。

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

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

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

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

答:n=15

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

時間表示為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

}

由以上列出的各語句的頻度，可得該程序段的時間消耗:

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

可表示為T(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

由以上列出的各語句的頻度，可得該程序段的時間消耗：

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

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

⑶i=l;j=0;

while(i+j<=n)

{

if(i>j)j++；

elsei++;

}

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

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

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

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

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))可知：當(y+D*(y+l)剛超過n的值時

退出循環(huán)。

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

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

向下取整下“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í)行時間

為：T(n)=0⑴

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

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

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

是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復雜度時，

一般就是以最壞情況下的時間復雜度為準的。

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

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

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

0⑴、對數(shù)階0(1陽2、線性階0(數(shù)、線性對數(shù)階0(nlog2n)、

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

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

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

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

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

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

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

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

<nn

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

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

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

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

夠大時Z(n)優(yōu)于Tz(n),因為前者的常數(shù)因子小于后者。請

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

哪一個較劣?

函數(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é)點、開始結(jié)點的區(qū)別、并說明頭指

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

答：開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前

趨的那個結(jié)點。

鏈表的頭指針是一指向鏈表開始結(jié)點的指針（沒有頭結(jié)點

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

的名字來命名。

頭結(jié)點是在鏈表的開始結(jié)點之前附加的一個結(jié)點。有了頭

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

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

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

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

為宜？

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

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

慮:

1.基于空間的考慮。當要求存儲的線性表長度變化不大，

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

反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用

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

2.基于時間的考慮。若線性表的操作主要是進行查找，很

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

若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用

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

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

2.3在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)

點?具體的移動次數(shù)取決于哪兩個因素？

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

個結(jié)點。刪除一個結(jié)點需平均移動(n-l)/2個結(jié)點。具體的

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

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

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

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

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

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

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

間都是0(1)。

若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為

0(n)o

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

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

去?若可以，其時間復雜度各為多少？

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

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

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

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

點的直接前趨。因此無法刪去該結(jié)點。

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

點的前趨指針和后繼指針可以查找到其直接前趨和直接后

繼，從而可以刪除該結(jié)點。其時間復雜度為0(1)。

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

后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我

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

所指結(jié)點。其時間復雜度應(yīng)為0(n)。

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

LinkListDemo(LinkListL){//L是無頭結(jié)點單鏈表

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

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

成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)

點，返回新鏈表的頭指針。

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

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

算法如下：

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

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

typedefstruct{

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

intlength;//當前的表長度

}Seqlist;

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

voidInsertList(Seqlist*L,Datatypex,inti)

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

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

intj;

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

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

義見教材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個結(jié)點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é)點前移

L->length一;〃表長減小

}

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

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

0(l)o

答：1.順序表:

要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互

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

整個表逆置了。算法如下：

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

voidReverseList(Seqlist*L)

(

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

inti;

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

除運算

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

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

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

)

}

2.鏈表：

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

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

可以利用指針改指來達到表逆置的目的。具體情況入下：

(1)當鏈表為空表或只有一個結(jié)點時，該鏈表的逆置鏈

表與原表相同。

(2)當鏈表含2個以上結(jié)點時，可將該鏈表處理成只含第

一結(jié)點的帶頭結(jié)點鏈表和一個無頭結(jié)點的包含該鏈表剩余

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

表指針，由前往后將每個結(jié)點依次從無頭結(jié)點鏈表中摘下，

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

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

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

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

型的字符

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

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

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

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

LinkListReverseList(LinkListhead)

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

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

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

{〃當鏈表不是空表或單結(jié)點時

p=head->next;

q=p->next;

p->next=NULL;〃將開始結(jié)點變成終端結(jié)點

while(q)

{〃每次循環(huán)將后一個結(jié)點變成開始結(jié)點

PF；

q=q->next;

p->next=head->next;

head->next=p;

}

returnhead;

)

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

head

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

L中，并使L仍是一個有序表。

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

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

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

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

以可邊尋找，邊后移元素，當找到第一個小于或等于X的元

素位置i時，該位置也空出來了。

算法如下：

〃順序表存儲結(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];//比較并

移動元素

L->data[i]=x;

L->length++;

}

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

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

答：與上題相類似，只要從終端結(jié)點開始往前找到第一個比

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

找，邊移動)算法如下:

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];//比較并移動

元素

L->data[i]=x;

L->length++;

)

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

算。

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

方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法如下：

intListLength(LinkListL)

(

intlen=0;

ListNode*p;

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

while(p->next)

p=p->next;

len++;

returnlen;

)

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

長度分別為m和no試寫一算法將這兩個鏈表連接在一起，

請分析你的算法的時間復雜度。

解：

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

在前面的那張表的表尾結(jié)點，再將后表的開始結(jié)點鏈接到前

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

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

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

單鏈表在前的方式連接。

具體算法如下：

LinkListLink(LinkListLI,LinkListL2,intm,int

n)

{〃將兩個單鏈表連接在一起

ListNode*p,*q,*s;

〃s指向短表的頭結(jié)點,q指向長表的開始結(jié)點，回

收長表頭結(jié)點空間

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é)點

p->next=q;〃將長表的開始結(jié)點鏈接在短表終

端結(jié)點后

returns;

}

本算法的主要操作時間花費在查找短表的終端結(jié)點上，

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

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

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

并要求輔助空間為0(1),請分析算法的時間復雜度。

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

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

兩表中最大的結(jié)點從對應(yīng)表中摘下，并作為開始結(jié)點插入C

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

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

時，得到的C表就是由A表和B表歸并成的一個按元素值遞

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

算法如下：

LinkListMergeSort(LinkListA,LinkListB)

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

點遞減有序表

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

pa=A->next;//pa指向A表開始結(jié)點

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

pb=B->next;//pb指向B表開始結(jié)點

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

while(pa&&pb)

{

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

{〃當B中的元素小于等于A中當前元素

時，將pa表的開始結(jié)點摘下

q=pa;pa=pa->next;

}

else

{//當B中的元素大于A中當前元素時，將

pb表的開始結(jié)點摘下

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

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

點q作為開始結(jié)點插入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);

該算法的時間復雜度分析如下：

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

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

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

所以若A表和B表的表長分別是m和n,則該算法的時間復

雜度O(m+n)

2.14已知單鏈表L是一個遞增有序表，試寫一高效算法，

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

點)，同時釋放被刪結(jié)點的空間，這里min和max是兩個給

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

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

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

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

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

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

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

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

算法如下：

voidDeleteList(LinkListL,DataTypemin,

DataTypemax)

(

ListNode*p,*q,*s;

P=L;

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

〃找比min大的前一個元素位置

p=p->next;

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

前趨，q指向第一個大于min的結(jié)點

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

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

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

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

點

2.15寫一算法將單鏈表中值重復的結(jié)點刪除，使所得的結(jié)

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

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

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

二結(jié)點的值，重復上述過程直到最后一個結(jié)點。

具體算法：

voidDeleteList(LinkListL)

(

ListNode*p,*q,*s;

p=L-next;

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

{

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

要刪除元素的直接前趨

while(q->next)

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

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

同的結(jié)點

elseq=q->next;

p=p->next;

)

)

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

指針。s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)

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

解：已知指向這個結(jié)點的指針是*s,那么要刪除這個結(jié)點的

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

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

刪除即可。

算法如下：

voidDeleteNode(ListNode*s)

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

ListNode*p,*q;

P=s;

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

p=p->next;

〃刪除結(jié)點

q=p->next;

p->next=q->next;

free(p);〃釋放空間

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

可。

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

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

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

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

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

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

來的單鏈表中依次查詢，找到一類字符結(jié)點時，就摘下此結(jié)

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

算法如下：

〃設(shè)已建立三個帶頭結(jié)點的空循環(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é)點

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

中

A->next=q;A=q;

}

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

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

q=p->next;

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

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

到B表中

B->next=q;B=q;

}

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

q=p->next;

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

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

點鏈到C表中

C->next=q;C=q;

}

}〃結(jié)束

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

三個域外，還有一個訪問頻度域freq,在鏈表被起用之前，

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

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

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

訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的

LocateNode運算的算法。

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

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

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

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

于或等于*P結(jié)點頻度的結(jié)點*q后，將*P結(jié)點從原來的位置

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

算法如下：

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

typedefstructdlistnode(

DataTypedata;

structdlistnode*prior,*next;

intfreq;

}DListNode;

typedefDListNode*DLinkList;

voidLocateNode(LinkListL,DataTypex)

{

ListNode*p,*q;

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

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

p=p->next;

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

無值為x的結(jié)點

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

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

個頻度大于或等于*P頻度的結(jié)點

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

q=q->prior;

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

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

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

結(jié)點后

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

原來位置摘下

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依次進棧，但只要出棧時棧非

空，則可將出棧操作按任何次序夾入其中，請回答下述問題：

(1)若入、出棧次序為Push(1),Pop(),Push(2),Push(3),

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

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

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

得到或者如何得到。

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

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

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

(2)不能得到1423序列。因為要得到14的出棧序列，則應(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種排列中，可通過相應(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é)點？

答：鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進

行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進

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

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

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

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

隊列的〃空〃或〃滿〃不能以頭尾指針是否相等來確定，一般是

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

滿。二是少用一個元素的空間，每次入隊前測試入隊后頭尾

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

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

到隊列中元素的個數(shù)。

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

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

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

因為每次入隊均需從頭指針開始查找，找到最后一個元素時

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

因為是循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指

元素，所以出隊時不需要遍歷整個隊列。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已做過初始化

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已初始化過

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)程序段的功能是將一棧中的元素按反序重新排列，

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

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

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

元素按原樣復制到一個棧s2當中去。

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

m的元素全部刪去。

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

反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。

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

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

列2,然后再把隊列2的元素復制到隊列1中。

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

〃abdba〃均是回文，但〃good〃不是回文。試寫一個算法判定

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

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

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

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

個元素

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

typedefstruct(

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

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

回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

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

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

Push(&s,t[i]);

while(!EmptyStack(&s))

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

temp=Pop(&s);

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

elsei++;

)

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

}

3.7利用棧的基本操作，寫一個將棧S中所有結(jié)點均刪去的

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

為指針參數(shù)？

解：算法如下

voidClearStack(SeqStack*S)

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

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

)

因為要置空的是棧S,如果不用指針來做參數(shù)傳遞，那

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

存中開辟另外的單元來對形參進行函數(shù)操作。結(jié)果等于什么

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

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

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

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

數(shù)？

解：算法如下：

intStackSize(SeqStackS)

{〃計算棧中結(jié)點個數(shù)

intn=0;

if(!EmptyStack(&S))

(

Pop(&S);

n++;

)

returnn;

)

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

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

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

參，函數(shù)只對形參進行操作，最后返回元素個數(shù)。

3.9設(shè)計算法判斷一個算術(shù)表達式的圓括號是否正確配對。

(提示：對表達式進行掃描，凡遇到‘('就進棧，遇就退

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

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

intPairBracket(char*SR)

{〃檢查表達式ST中括號是否配對

inti;

SeqStackS;〃定義一個棧

InitStack(&s);

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

(

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

時進棧

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

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

元素出棧

Pop(&s);

elsereturn0;〃不匹配,返回0

)

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

elsereturn0;〃不匹配,返回0

}

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

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

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

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

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

好比是兩個頭對頭的棧放在一起，中間的空間可以充分利

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

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

ttdefineStackSize100//假定分配了100個元素的向量

空間

#definecharDataType

typedefstruct(

DataTypeData[StackSize]

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

inttopi;

}DblStack

voidInitStack(DblStack*S)

{〃初始化雙向棧

S->topO=-1;

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

空間，但由于是作為棧底，因此不會出錯

}

intEmptyStack(DblStack*S,inti)

{〃判?？?棧號i)

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

S->topl==StackSize)

intFullStack(DblStack*S)

{〃判棧滿,滿時肯定兩頭相遇

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

voidPush(DblStack*S,inti,DataTypex)

{〃進棧(棧號i)

if(FullStack(S))

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

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

棧

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

棧

}

DataTypePop(DblStack*S,inti)

{〃出棧(棧號i)

if(EmptyStack(S,i))

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

if(i==0)

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

素，指針值減1

if(i==l)

return(S->Data[S->topl++]);〃因為這個棧

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

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

nn+1當m=0時

AKM(m,n)=|AKM(m-1,1)當mWO,n=0時

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

0時

解：算法如下

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用第二種方法，即少用一個元素空間的方法來區(qū)別循

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

出隊、入隊及取隊頭元素等六個基本操作的算法。

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

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

#defineQueueSize100

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

typedefstruct{

intfront;

intrear;

DataTypeData[QueueSize];

}CirQueue;

(1)置空隊

voidInitQueue(CirQueue*Q)

{//置空隊

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

)

⑵判隊空

intEmptyQueue(CirQueue*Q)

{〃判隊空

returnQ->front==Q->rear;

}

⑶判隊滿

intFullQueue(CirQueue*Q)

{//判隊滿〃如果尾指針加1后等于頭指針，則認為

滿

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

4）出隊

DataTypeDeQueue(CirQueue*Q)

{〃出隊

DataTypetemp;

if(EmptyQueue(Q))

Error(〃隊已空，無元素可以出隊〃)；

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

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

義上的加1

returntemp;〃返回元素值

)

⑸入隊

voidEnQueue(CirQueue*Q,DataTypex)

{//入隊

if(FullQueue(Q))

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

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

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

一個空元素位置

}

(6)取隊頭元素

DataTypeFrontQueue(CirQueue*Q)

{〃取隊頭元素

if(EmptyQueue(Q))

Error(〃隊空，無元素可取〃);

returnQ->Data[Q->front];

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

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

置空隊、判隊空、入隊和出隊等算法。

解：算法如下：

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

typedefstructqueuenode(

Datatypedata;

structqueuenode*next;

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

typedefstruct{

queuenode*rear;

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

(1)置空隊

voidInitQueue(LinkQueue*Q)

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

QueueNode*s;

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

點

while(Q->rear!=Q->rear->next)〃當隊列非空，

將隊中元素逐個出隊

{s=Q->rear->next;

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

free(s);

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

}

⑵判隊空

intEmptyQueue(LinkQueue*Q)

{〃判隊空

〃當頭結(jié)點的next指針指向自己時為空隊

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

)

⑶入隊

voidEnQueue(LinkQueue*Q,Datatypex)

{〃入隊

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

QueueNode*p=(QueueNode*)malloc

(sizeof(QueueNode));〃申請新結(jié)點

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

結(jié)點并鏈入

Q-rear->next=p;

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

}

⑷出隊

DatatypeDeQueue(LinkQueue*Q)

{〃出隊把頭結(jié)點之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflo