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

第一章緒論

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)。

1.2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)

容。

答：例如有一張學(xué)生體檢情況登記表，記錄了一個班的學(xué)生的身高、體重等各

項體檢信息。這張登記表中，每個學(xué)生的各項體檢信息排在一行上。這個表就是

一個數(shù)據(jù)結(jié)構(gòu)。每個記錄（有姓名，學(xué)號，身高和體重等字段）就是一個結(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)系是由附加的指針

字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu),通常借助于程序語言的指針類型描述。

?索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。組成索引表的索引

項由結(jié)點的關(guān)鍵字和地址組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引（Dense

Index),若一組結(jié)點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索弓I。

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

1.4設(shè)三個函數(shù)f,g,h分別為f(n)=100n+n2+1000,g(n)=25n3+5000n2,h(n)=n'5+5000nlgn請判斷下列

關(guān)系是否成立：

(1)f(n)=O(g(n))

(2)g(n)=O(f(n))

⑶h(n)=O(n1,s)

(4)h(n)=O(nlgn)

分析：

數(shù)學(xué)符號”0〃的嚴(yán)格的數(shù)學(xué)定義：

若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=0(f(n))表示存在正的常數(shù)C和nO,

使得當(dāng)n>nO時都滿足OWT(n)WC?f(n)。

通俗地說，就是當(dāng)n-8時，f(n)的函數(shù)值增長速度與T(n)的增長速度同階。一般，一個函數(shù)的增長

速度與該函數(shù)的最高次階同階。

即：

O(f(n))=n3

0(g(n))=n3

0(h(n))=n'5

所以答案為：

答：

?(1)成立。

?(2)成立。

?(3)成立。

?(4)不成立。

1.5設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為lOOn"和2",要使前者快于后者，n至少要多大？

分析：

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

100n2<2n

求解上式，可得

答：

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-1

)

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

T(n)-i+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

dot//n

k-k+10*i;//n

i++：//n

while(i<n);//n

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

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

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

(3)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+l)*(y+D)

y++;

分析：

由x=n且x的值在程序中不變,乂while的循環(huán)條件(x>=(y+l)*(y+D)可知：當(dāng)(y+l)*(y+D剛超過n的值時退出循環(huán)。

由(y+】)*(y+l)〈n得：y<n*O.5-1

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

向下取整(rTO.5-1)

(5)x=91;產(chǎn)100;

while(y>0)

if(x>100)

{x=x-10;y-：）

elsex++;

分析：

x=91;//I

y=100;//I

while(y>0)//U01

if(x>100)//1100

(x=x-10;//JOO

y-;//100

)

else

x++：//I000

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

T(n)=O(l)

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

答：

算法的時間史雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的初始狀態(tài)有關(guān)。但在最壞的情況上其時間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)

的,我們在討論時間或雜度時，一般就是以最壞情況下的時間紅雜度為準(zhǔn)的。

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

2KM,(3/2)",(2/3)",n",n0'5,n!,2n,Ign廣八

答：

常見的時間復(fù)雜度按數(shù)量級遞增排列，依次為:常數(shù)階0(1)、對數(shù)階0(1。刎)、線性階0(n)、線性對數(shù)階0(nlog2n).平方階0(眉、立方階0G?)、

k次方階0(右、指數(shù)階0(2").

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

常數(shù)階：2網(wǎng)

對數(shù)階：Ign

K次方階：n°s、產(chǎn)

指數(shù)階(按指數(shù)由小到大排)：［切、(3/2)"、2"、n!、n"

注意：(2/3廠"由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階,

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

n05,eBnn

(2/3)<2倘<Ign<n<n⑶2<n<(3/2)<2<n!<n"

1.9有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大‘0”記號表示。例如，設(shè)

Ti(n)=l.39nlgn+100n+256=l.39nlgn*0(n),T?(n)=2.0nlgn-2n=2.01gn+0(n),這兩個式子表示，當(dāng)n足夠大時TKn)優(yōu)于Tin),因為前者的常數(shù)因

子小于后者。請用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時，哪?個較優(yōu)，哪個較劣？

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

(1)Ti(n)=5nJ-3n+601gn5nJ+0(n)較差

2

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

2

(3)Ts(n)=8n+31gn8n■()(Ign)最差

(4)TNn)=1.5n2+6000nlgn..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.基『空間的號慮.當(dāng)要求存儲的線性表長度變化不大，切「事先確定其大小時，為了節(jié)約存陸空M,宜來川順序表；反之，當(dāng)線性表長度變化

大，難以估計其存儲規(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é)點需平均移動(nT)/2個結(jié)點。具體的移動次數(shù)取決于順序表的

長度n以及需插入或刪除的位置ioi越接近n則所需移動的結(jié)點數(shù)越少。

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

答：

尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾

指針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear->next->nexi和rear,查找時間都是0(1)。

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

2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度

各為多少？

答：

卜.面分別討論三種鏈表的情況。

1.單鏈表，若指針P指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，能夠順后繼指針鏈找到即結(jié)點后的結(jié)點。但是由于不知道其頭指針，

所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。

2.雙鏈表。由于這樣的提表提供雙向指針，根據(jù)*p結(jié)點的前趨指針和后繼指針可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其

時間復(fù)雜度為0(1)。

3.單循環(huán)鏈表根據(jù)已知結(jié)點位置，可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)

點的直接前趨,因此可以刪去p所指結(jié)點。其時間更雜度應(yīng)為0(n).

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

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

ListNodc*Q,*P;

if(L&&L->next){

Q=L:L=L->next：P=L：

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

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

)

returnL;

}//Demo

答：

該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。

2.7設(shè)線性表的n個結(jié)點定義為(如加,...哈|),重寫順序表上實現(xiàn)的插入和刪除算法：InsertList和DeleteList.

解：算法如下：

打efineListSize100//假定表空間大小為100

typedcfintDataType;〃假定DataTypc的類型為int?型

lypedefstruct{

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

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

}Seqlist;

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

voidInsertList(Seqlist*L,Datatypex,inti)

(

〃將新結(jié)點x插入L所指的順序表的第i個結(jié)點ai的位置上，即插入的合法位置為：0<=i<=L->lenglh

intj：

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

Error("positionerror");〃非法位置,退出，該函數(shù)定義見教材P7.

if(L->length>=ListSize)

Error(44overflow*)：

for(j=L->length-l；j>=i：j")

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

L->data[i]=x;

L->lenglh++:

)

voidDeleteList(Seqlist*L,inti)

(//從L所指的順序表中刪除第i個結(jié)點ai,合法的刪除位置為(K=i<=L->length-l

intj：

if(i<0|Ii>=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)將線性表⑸,a“...國)就地逆置的操作,所謂"就地"指輔助空間應(yīng)為0(1)。

答：

1.順序表：

要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互換，笫二.個結(jié)點與倒數(shù)第二個結(jié)點互換，如此反更，就可將整個表逆置了。算法如下:

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

voidReverseList(Seqlist*L)

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

inti;

for(i=0;i<=L->lcngth/2;i++)//L->length/2為整除運算

{temp=〃交換數(shù)據(jù)

L->data[i]=L->data[L->length-l-i]：

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

2.鏈表：

分析：

可以用交換數(shù)據(jù)的方式來達(dá)到逆置的目的。但是由于是單鏈表，數(shù)據(jù)的存取不是隨機的，因此算法效率太低?？梢岳弥羔樃闹竵磉_(dá)到表逆置

的口的。具體情況入下：

(D當(dāng)鏈表為空表或只有一個結(jié)點時，該鏈表的逆置鏈表與原表相同。

(2)當(dāng)鏈表含2個以上結(jié)點時，可將該鏈表處理成只含第一結(jié)點的帶頭結(jié)點鏈表和個無頭結(jié)點的包含該鏈表剩余結(jié)點的鏈表。然后，將該無

頭結(jié)點鏈表中的所有結(jié)點順著使表指針，由前往后將每個結(jié)點依次從無頭結(jié)點鏈表中摘下，作為第一個結(jié)點插入到帶頭結(jié)點鏈表中。這樣就可以得

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

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

typedefcharDalaType;//假設(shè)結(jié)點的數(shù)據(jù)域類型的字符

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

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

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

}ListNode：

typedefListNode*LinkList：

ListNode*p;

LinkListhead;

LinkListReverseList(LinkListhead)

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

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

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

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

p=head->next;

q=p->next;

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

while(q)

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

P=q；

q=q->next;

p->nexl=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之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個小于或等于x的元素位置i時，該位置也空出

來了。

算法如下：

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

voidInsertlncreaseList(Scqlist*L,Datatypex)

|

inti;

if(L->length>=ListSize)

Error("overflow");

for(i=L->length;i>0&&L->data[i-1]>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->lcngth>=ListSize)

Error("overflow");

for(i=L->length;i>0&&I->data[i-1]<x;i—)

L->data[i]=L->data[i];//比較并移動元素

L->data[i]=x:

L->length++：

}

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

解：

由于在單鏈表中只給出個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法如下：

intUstLcngth(LinkListL)

intlen=O:

ListNode*p:

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

while(p->next)

{

p=p->next;

len++：

}

returnlen：

)

2.12己知LI和L2分別指向兩個玳鏈表的頭結(jié)點，且已知其長度分別為m和n。試寫一算法將這兩個鋅我連接在一起，請分析你的算法的時間且雜

度。

解,

分析：

由于要進行的是兩單鏈表的連接，所以應(yīng)找到放在前面的那張表的表尾結(jié)點，再將后表的開始結(jié)點鏈接到前表的終端結(jié)點后即可。該算法的主

要時間消耗是用在尋找第?張表的終端尾結(jié)點上。這兩張單鏈表的連接順序無要求，并且已知兩表的表長，則為了提高算法效率，可選表長小的單

鏈表在前的方式連接.

具體算法如下：

LinkListLink(LinkListLI,LinkListL2,n)

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

ListNode*p,*q,*s;

Z/s指向短表的頭結(jié)點,q指向長表的開始結(jié)點，回收長表頭結(jié)點空間

if(m<=n)

{s=Ll:q=L2->next;frec(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é)點上，所以本算的法時間復(fù)雜度為：

O(min(m,n))

2.13設(shè)A和B是兩個單銖表，其表中元素遞增有序。試寫一算法將A和B歸并成?個按元素位遞減書?序的單鋅表3并要求輔助空間為0(1),詁

分析算法的時間復(fù)雜度。

解：

根據(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->nex廠NULL;〃取A表的表頭建立空的C表

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

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

while(pa&&pb)

{

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

{//當(dāng)B中的元素小于等于A中當(dāng)前元素時，將pa表的開始結(jié)點摘下

q=pa;pa=pa->next;

}

else

{//當(dāng)B中的元素大于A中當(dāng)前元素時,將pb表的開始結(jié)點摘F

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

q->next=C->next;C->nexl=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);

)

該算法的時間更雜度分析如F：

算法中有三個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和

inax之間的結(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;

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

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

p=p->next：

q=p->ncxt;〃p指向第一■個不大于min結(jié)點的直接前趨，q指向第一個大于min的結(jié)點

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

{s=q;q=q-〉next;

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

}

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

I

2.15寫一算法將單鏈表中值重發(fā)的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同。

解：

本題可以這樣考慮，先取開始結(jié)點中的值，將它與其后的所有?結(jié)點值一比較，發(fā)現(xiàn)相同的就刪除掉,然后再取第：結(jié)點的值，重復(fù)上述過程

直到最后一個結(jié)點。

具體算法：

voidDeleteList(LinkListL)

(

ListNode*p,*q,*s;

p=L-next：

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

(

q=p；〃由于要做胴除操作，所以q指針指向要刪除元素的直接前趨

whi1c(q->ncxt)

if(p->data==q->nexl->dala)

{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(LisiNode*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);//釋放空間

I

注意：

若單循環(huán)鏈表f內(nèi)長度等于1,則只要把表刪空即可。

2.17已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線

性表，使每個表中只含同一類的字符，旦利用原表中的結(jié)點空間作為這：?個表的結(jié)點空間，頭結(jié)點可另辟空間。

解：

要解決這樣的問題，只要新建二?個頭結(jié)點，然后在原來的單鏈表中依次杳ifU，找到類字符結(jié)點時，就摘F此結(jié)點鏈接到相應(yīng)頭結(jié)點指明的新

鏈表中就是了。

算法如下：

〃設(shè)已建立三個帶頭結(jié)點的空循環(huán)鏈表A,B,C且A、B、(:分別是尾指針.

voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC)

(

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

while(p)

(

if(p->data>=,a'&&p->data<=,z'IIp->data>=,A'&&p->data<=,Z')

(

q=p->next;

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

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

.\->next=q;A=q;

)

elseif(p->data>=,0'&&p->data<=,9')

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

q=p->ncxt;

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

q->next=B->nexl;〃將數(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,在鏈表被起用之前，其值均初始化為零。每當(dāng)

在鏈表進行一次LocateNode(Lx)運算時，令元素值為x的結(jié)點中freq域的值加I,并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減序樣列，以便

使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。

解：

LocateNode運算的基本思想就是在雙向鏈表中查找值為x的結(jié)點，具體方法與單鏈表中查找一樣。找到結(jié)點*p后給freq域的值加L由于原

來比*P結(jié)點查找頻度高的結(jié)點都排它前面，所以，接下去要順著前趨指針找到第個頻度小于或等于*p結(jié)點頻度的結(jié)點*q后，將*p結(jié)點從原來的

位置刪除，井插入到*q后就可以了.

算法如下：

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

typcdefstructdlistnodc(

DataTypcdata;

structdlistnode*prior,*next;

intfreq;

iDIJstNodc;

LypedefDLisiNode*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->fre(i++：//freqJjll1

q=p->prior;〃以q為掃描指針尋找第?個頻度大于或等于*p頻度的結(jié)點

while(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->ncxt;〃將*p從原來位置摘下

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

q->nexl->prior=p;〃將*p插入*q之后。

p->next=q->next:

q->next=p：

p->prior=q;

}

)

)

第三章棧和隊列

3.1設(shè)將整數(shù)1，2.3,4依次進棧,但只要出棧時技非空，則可將出棧操作按任何次序夾入其中，請回答卜述問題：

⑴若入、出棧次序為Push(l),PopO,PuSh(2).Push(3),Pop().Pop(),Push(4).Pop(),則出找的數(shù)字序列為何(這里Push(i)表示i進棧，Pop()表示出棧)？

(2)能否有到出棧序列1423和1432?并說明為什么不能得到或者如何得到。

(3)請分析-2,3,4的24種排列中，啷些序列是可以通過相應(yīng)的入出棧操作得到的，

答：

(1)出根序列為：1324

(2)不能得到1423序列.因為要得到14的出棧序列,則應(yīng)做Push⑴.Pop0,Push⑵，為sh(3).Push(4),PbpO.這樣，3在枝頂,2在棧底，所以不能得到23的出

找序列。能得到1432的出棧序列.具體操作為：Push(l),PopO,Push(2),Push(3).Push(4),Pop0>PopPbpO.

(3)^的24種排列中,可通過相應(yīng)入出棧操作得到的序列是：

1234.1243,1324,1342,1432.2134,2143,2314,2341.2431,3214,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ū)別隊列的空和滿。二是少用個元素的空間，每次入隊附測試入隊后

頭尾指針是否會重合，如果會重合就認(rèn)為隊列已滿。三是設(shè)置?計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。

3.4設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊出隊操作的時間為何？若只設(shè)尾指針呢？

答：

當(dāng)只設(shè)頭指針時，出隊的時間為1，而入隊的時間需要n,因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若

只設(shè)尾指針，則出入隊時間均為屋因為是循環(huán)鏈表，尾指針?biāo)傅牟?個元素就是頭指針?biāo)冈兀猿鲫爼r不需要遍歷整個隊列。

3.5指出卜述程序段的功能是什么？

(1)voidDemol(SeqStack*S){

inii;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,tnp;

DataTypex:

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

while(!StackEmply(&S1))

(

x-Pop(&S1);

Push(&tmp,x);

)

while(!StackEmpty(&tmp))

(

x=Pop(&tmp);

Push(&Sl,x);

Push(&S2,x);

)

(3)voidDemo2(SeqStack*S,intm)

{//設(shè)DalaType為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);

1

)

(4)voidDemo3(CirQucuc*Q)

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

intx：SeqStackS：

InitStack(&S):

while(!QueucEmpty(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=DcQueuc(&Q1);EnQueuc(&Q2,x)：n++：)

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

{x=DeQueue(&Q2):

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

答：

(D程序段的功能是將一?棧中的元素按反序重新排列，也就是原來在樓頂?shù)脑胤诺綏５祝瑮５椎脑胤诺綏ｍ?。此棧中元素個數(shù)限制在的個

以內(nèi)。

(2)程序段的功能是利用imp棧將一個非空棧si的所有元素按原樣更制到一個棧s2當(dāng)中去。

(3)程序段的功能是利用棧T,將一個非空棧S中值等于m的元素全部刪去。

(4)程序段的功能是將?個循環(huán)隊列Q經(jīng)過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。

(5)這段程序的功能是將隊列I的所有元素復(fù)制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2,然后再把隊列2的元

素復(fù)制到隊列1中.

3.6回文是指正讀反讀均相同的字符序列，如"abba"和"abdba”均是回文，但"good"不是回文。試寫個算法判定給定的字符向量是否為回文。(提

示：將一半字符入棧)

解：

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

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

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

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

typedefstruct(

DataTypedata[StackSize];

inttop;

}SeqStack:

intI