考研數(shù)據(jù)結(jié)構(gòu),各種算法的經(jīng)解分析

第一章

?數(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è)值的集合以及在這些值上定義的一組操作的總稱。

在高級(jí)語言程序中又分為：非結(jié)構(gòu)的原子類型和結(jié)構(gòu)類型

?抽象數(shù)據(jù)類型(ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。

一個(gè)抽象的數(shù)據(jù)類型的軟件模塊通常包含定義和表示和實(shí)現(xiàn)

用三元組(D,S,P)：數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系、基本操作

?數(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ù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)。

?線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一

個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性

表就是一個(gè)典型的線性結(jié)構(gòu)。

?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前

趨和直接后繼。

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

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

邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。

?鏈接存儲(chǔ)方法：它不要求邏輯匕相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是

由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

?索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。

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

漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n)),這里的“0"是數(shù)學(xué)符號(hào)，它的嚴(yán)格定義是"若T(n)和

f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=0(f(n))表示存在正的常數(shù)C和nO，使得當(dāng)n

2no時(shí)都滿足OWT(n)<C?f(n)。"用容易理解的話說就是這兩個(gè)函數(shù)當(dāng)整型自變量n趨向

于無窮大時(shí)，兩者的比值是?個(gè)不等于0的常數(shù)。這么一來，就好計(jì)算了吧。

求某?算法的時(shí)間復(fù)雜度是關(guān)于N的統(tǒng)計(jì)，下面的例子很有反面意義

x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y-;}

elsex++;

?T(n)=O(l)

?這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒有？沒。

O這段程序的運(yùn)行是和n無關(guān)的，就算它再循環(huán)?萬年，我們也不管他，只是一個(gè)常數(shù)階

的函數(shù)。

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

?No,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相

關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)

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

增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2A100,(2/3)An,(3/2)An,nAn,,n!,2An,Ign,nAlgn,

nA(3/2)

O分析如下：2700是常數(shù)階；(2/3)~和(3/2)他是指數(shù)階,其中前者是隨n的增大而減小

的；Mn是指數(shù)方階；Vn是方根階,n!就是n(n-l)(n-2)...就相當(dāng)于n次方階；25是指

數(shù)階，Ign是對(duì)數(shù)階，nNgn是對(duì)數(shù)方階,M(3/2)是3/2次方階。根據(jù)以上分析按增長(zhǎng)率由小至

大的順序可排列如下：

?(2/3)An<2A100<Ign<Vn<nA(3/2)<nAlgn<(3/2)An<2An<n!<nAn

算法：是對(duì)特定的問題求解步驟地一種描述，是指令的有限序列。有五個(gè)基本的特性

有窮性、確定性、可行性、輸入、輸出

確定性：每條指令不能有二義性，對(duì)于同樣的輸入有同樣的輸出

可行性：算法中所用到的操作都是已經(jīng)實(shí)現(xiàn)的基本運(yùn)算或通過有限次能實(shí)現(xiàn)的

輸入：有0個(gè)或多個(gè)輸入

輸出：有一個(gè)或多個(gè)輸出

設(shè)計(jì)算法的要求(追求的目標(biāo))

正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求

算法原地工作：當(dāng)空間復(fù)雜度為0(1)時(shí)，稱算法為就地工作(原地工作)。

多型數(shù)據(jù)類型：是指其值的成分不確定的數(shù)據(jù)類型。從抽象數(shù)據(jù)類型的角度看，具有相同的

數(shù)學(xué)抽象特性，故稱之為多型數(shù)據(jù)類型。

數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？

研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及他們之間的關(guān)系和操作等學(xué)科

對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？

數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。

邏輯結(jié)構(gòu)有線形結(jié)構(gòu)(1),樹型結(jié)構(gòu)(2),(3)網(wǎng)狀結(jié)構(gòu),集合(4)

四種。

平方和公式：1~+2~+3一+=n*(n+l)*(2n+l)/6

斐波那契數(shù)列計(jì)算的時(shí)間復(fù)雜度是O(n)

第二章

循環(huán)鏈表是一種首尾相接的鏈表。也就是終端結(jié)點(diǎn)的指針域不是指向NULL空而是指向開

始結(jié)點(diǎn)（也可設(shè)置一個(gè)頭結(jié)點(diǎn)），形成一個(gè)環(huán)。采用循環(huán)鏈表在實(shí)用中多采用尾指針表示單循

環(huán)鏈表。這樣做的好處是查找頭指針和尾指針的時(shí)間都是0（1）,不用遍歷整個(gè)鏈表了。

判別鏈表終止的條件也不同于單鏈表，它是以指針是否等于某一指定指針如頭指針或尾指針

來確定。

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

答：

在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(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)鏈表為宜。

第三章

例如：Exp=a*b+（c-d/e）*f

若Exp=a*b+（c-d/e）*f則它的

前綴式為：+*ab*-c/def

中綴式為：a*b+c-d/e*f

后綴式為：ab*cde/-fx+

綜合比較它們之間的關(guān)系可得下列結(jié)論：

1.三式中的“操作數(shù)之間的相對(duì)次序相同”；

（二叉樹的三種訪問次序中，葉子的相對(duì)訪問次序是相同的）

2.三式中的“運(yùn)算符之間的的相對(duì)次序不同”；

3.中綴式丟失了括弧信息，致使運(yùn)算的次序不確定"

（而前綴和后綴運(yùn)算只需要一個(gè)存儲(chǔ)操作數(shù)的棧，而中綴求值需要兩個(gè)棧，符號(hào)棧和操

作數(shù)棧）

4.前綴式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成

一個(gè)最小表達(dá)式；

5.后綴型號(hào)算規(guī)則&________________________

?運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序；

?每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式；

6.中綴求值的運(yùn)算規(guī)則：

如果是操作數(shù)直接入棧。

如果是運(yùn)算符。這與當(dāng)前棧頂比較。個(gè)如果比當(dāng)前棧頂高，則入棧，如果低則說明當(dāng)前

棧頂是最高的必須把他先運(yùn)算完了。用編譯原理的話就是說當(dāng)前棧頂已經(jīng)是最左素短語了）

其實(shí)中綴表達(dá)式直接求值和把中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式在求值的過程驚人的相似，只不

過是直接求值是求出來，而轉(zhuǎn)化成后綴是輸出來。

中綴表達(dá)式直接求值算法：

OPNDTypeEvalueExpression()

{//OPTR和OPND分別為運(yùn)算符棧和操作數(shù)棧

InitStack(OPTR);Push(OPTR,#);

InitStack(OPND);c=getchar();

While(c!=,#'llGetTop(OPTR)!=^#^)

(

If(!IN(c,OP))〃如果是操作數(shù)，直接入操作數(shù)棧

{push(OPND,c);

c=getchar();

)

Else〃如果是運(yùn)算符，則與當(dāng)前的棧頂比較

(

Switch(Precede(GetTop(OPTR),c))

(

CaseV:push(OPTR,c);〃比當(dāng)前棧頂高，這入棧

c=getchar();

break;

Case*=\Pop(OPTR,x)；〃在我們?cè)O(shè)計(jì)的優(yōu)先級(jí)表中，

c=getchar();//只有'('和')'存在相等的情況，

break;//而在規(guī)約中間只存在

〃所以我們直接把'('彈出就可以了

Case〉，：〃比當(dāng)前棧頂?shù)停瑒t要把棧頂先運(yùn)算完(先規(guī)約)

pop(OPTR,theta);//把棧頂運(yùn)算符彈出

Pop(OPND,b);〃取出操作數(shù)，并且是前操作數(shù)

Pop(OPND.a);〃在下面(棧的先進(jìn)后出)

Push(OPND,Operate(a,theta,b));〃運(yùn)算的結(jié)果入棧

//(他是其他運(yùn)算符的操作數(shù))

Break;

[//Switch

}//else

}//whild

ReturnGetTop(OPND);//操作數(shù)棧中最后剩下的就是整個(gè)表達(dá)式的結(jié)果了。

)

voidtrans-post(charE[n],charB[n])〃中、后綴表達(dá)式轉(zhuǎn)換〃

{//E[n]是中綴表達(dá)式、B[n]是后綴表達(dá)式存儲(chǔ)的空間

inti=0,j=0;charx;stypeS;

Clearstack(S);Push(S,'#')；〃‘#‘入?！?/p>

do{

x=Efi++l;〃掃描當(dāng)前表達(dá)式分量〃

if(x=ir)〃到了中綴表達(dá)式最后了

while(!Emptystack(S))〃全部退棧,#和#是優(yōu)先級(jí)最低的，

B[j++]==pop(S);//所以當(dāng)前棧的所有運(yùn)算都要規(guī)約

〃輸出棧頂運(yùn)算符，并退棧直到遇見棧底的開始放進(jìn)去的那個(gè)井〃

elseif(isdigit(x))

B|j++]=x;〃操作數(shù)直接輸出〃

elseif(x=))〃遇到)那么就一定要找到(

(

while(Getstop(S)!=*(')

B|j++]=pop(S);〃輸出棧頂，并退?！?/p>

pop(S);〃退掉‘(力

}

else//x為運(yùn)算符〃

(

while(precede(Getstop(S),x))〃棧頂(01)與x比較〃

B[j++]=pop(S);〃01>=x時(shí)，輸出棧頂符并退?！?/p>

Push(S,x);〃01<x時(shí)x進(jìn)棧〃

)

}while(x!='#')；

)〃置表達(dá)式結(jié)束符〃

雙端隊(duì)列：

兩端都可以插入和刪除，但實(shí)際應(yīng)用中通常是輸出受限的雙端對(duì)列和輸入受限的雙端隊(duì)列

輸入受限的雙端隊(duì)列指的是：-端可以輸入輸出另一端只能輸出不能輸入

輸出受限的雙端隊(duì)列指的是：-端可以輸入輸出另一端只能輸入不能輸出

求從迷宮入口到出口的??條最短路徑

要用到隊(duì)列，因?yàn)殛?duì)列可以用在廣度優(yōu)先中，隊(duì)列中的元素表示離中心點(diǎn)依次越來越遠(yuǎn)。

所以第一次找到出口肯定是半徑最短的。

鏈?zhǔn)綏?

鏈?zhǔn)疥?duì)列:

N個(gè)結(jié)點(diǎn)的不同二叉樹有：=-等于不同的進(jìn)出棧總數(shù)

有n個(gè)數(shù)順序(依次)進(jìn)棧，出棧序列有Cn種,Cn=El/(n+1)]*(2n)!/[(n!)*(n!)]。

尾遞歸和單向遞歸的消除不需要借用棧

單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過程

其他情形必須借助棧實(shí)現(xiàn)非遞歸過程。

證明：若借助棧由輸入序列1,2,…,n得到輸出序列為Pi,P2,…,P"(它是輸入序列的一個(gè)排

列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著使PKPKP,。

i<j若Pi<Pj說明小的先于大的數(shù)出棧，那么也就是Pi出棧在Pj入棧前面

若Pi>Pj說明大的數(shù)先于小的數(shù)出棧，那么在Pi出棧前Pj一定在棧中

證明：1)j<k且Pj<Pk說明Pj出棧在Pk入棧的前面；

2)i<k且Pi>Pk說明Pi出棧前，Pk在棧中

3)i<j且Pi>Pj說明Pi出棧前Pj在棧中

而Pi是最先出棧的那么在Pi為棧頂?shù)臅r(shí)候，Pj和Pk一定都同時(shí)被壓入棧中，那么

就與1矛盾了，1要求Pj要在Pk入棧前出棧，而此時(shí)PkPj都在棧中所以假設(shè)不成立。

用兩個(gè)棧來模擬一個(gè)隊(duì)列

棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧si和s2模擬一個(gè)隊(duì)列

時(shí)，si作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)，將棧si

退棧并逐個(gè)壓入校s2中，si中最先入棧的元素，在s2中處于棧頂。s2退棧，相當(dāng)于隊(duì)

列的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧s2為空且si也為空，才算是隊(duì)列空。

第四章

KMP算法利樸素的匹配算法的關(guān)鍵區(qū)別就是解決了主串指針i的回溯，原理如下

設(shè)主串S口和模式串T[],如比較到模式串的第j個(gè)字符。S?52S3.............Si-2SS；

r■Tr■Tr■rr■Tr■Tr■T

1\L213.............1j-217-11j

當(dāng)主串指針i和模式串指針j比較時(shí)，說明他們前面的所有字符都已經(jīng)對(duì)應(yīng)相等了。而

Next[j]=k的定義是TlT2...Tk-l==Tj-k+lTj-k+2....Tj-l且k是最大了，沒有更長(zhǎng)的了。

所以Si和Tj比較失敗時(shí)Si和Tk去比較。不可能有§?§2S3?……S1-2SSiSM這種

T\12......................1j-21j-\Tj

匹配的成功，因?yàn)镾2s3..…Si-1==T2T3……41,而T213....!>1是不等于丁建2....!>2。除

非next[j]=j-l；因?yàn)閚ext定義的是最長(zhǎng)的。所以任何挪動(dòng)小于next|j]的串的匹配都是不能成功

的?！钡絋next[j]和S[i]相比是才是最早有可能成功的。

IntKMP_Index(SstringS,SstringT,intpos)

(

i=pos;j=l;

while(i<=S[0]&&j<=T[0])

{

IfU=OIIS[i]=T[j])//j=O表示模式串已經(jīng)退到起點(diǎn)了說明在這個(gè)位置徹底不可能了，

{++i；++j；}//i必須下移,j回到1開始

Elsej=next[j];

If(j>T[O])returni-T[O];

Elsereturn0;

}

求nexl[j]的方法和原理

設(shè)k=next[j];那么TlT2...Tk-l==Tj-k+l....Tj-2Tj-1;

若Tj==Tk,那么T1T2…Tk-lTk==Tj-k+l....Tj-2Tj-lTj;

所以next[j+l]=k+l=next[j]+l;且T1T2…Tk-l==Tj-k+l....lj-2Tj-l已經(jīng)是

最長(zhǎng)的序列，所以k+1也是next[j+l]最長(zhǎng)的

若Tj不等于Tk,那么就需要重找了。即…Tj-lTj?,

T1T2....

所以next[j+l]首先=k=next[j];即…Tj-lTj?,

TlT2...Tk-l.

若不相等，則next[j+l]=next[k];即…Tj-lTj?,

TlT2....Tnext[k]-l

直到找到這樣的序列，即…Tj-lTj?,

T1T2...To

那么,next[j+ll=next[nextfj]]=next[next[next[j]]]...=o+l;

Voidget_next(SstringT,intnextf])

(

i=l;nextfl]=0;j=0;〃i表示當(dāng)前求的next

While(i<T[0])//總共求T[0]-l個(gè)

(

if(j=OHT[i]=T[j])

(

++i；

++j；

next[i]=j;

)

Elsej=next[jj;

因?yàn)閚ext[]在匹配過程中，若T[j]=T[next|jJ]；那么當(dāng)S[i]不等于T[j],

S[i]肯定也不等于T[k=next[j]];

所以S[i]應(yīng)直接與T[next[k]]比較，而我們通過將next|jl修正

為nextval[j]=next[next[j]];這樣能使比較更少。

Voidget_nextval(SstringT,intnextval[J)

i=1;nextval[l]=0;j=0;

while(i<T[O])

if(j=OIIT[i]=Tfj])

++i；

++j；

if(T[i]!=T|j])

nextval[i]=j;

else

nextval[i]=next[j];

j=nextval[j];

H格半是指由空格字符（ASCII值32）所組成的字符串,其長(zhǎng)度等于?格個(gè)數(shù)

在模試匹配KMP算法中所用失敗函數(shù)f的定義中，為何要求pg……prs為p.p2……Pj兩頭匹

配的真子串？且為最大真子串？

失敗函數(shù)（即next）的植只取決于模式串自身,若第j個(gè)字符與■串第i個(gè)字符失配時(shí)，

主串不回溯，模式串用第k（即next，］）個(gè)字符與第i個(gè)相比，有‘pl…pk-I,*p.jk+1

pj-r,為了不因模式串右■與I..第i個(gè)字符比較而丟失可能的匹配，對(duì)?上式中存在的

多個(gè)k，.應(yīng)取■中?大的-個(gè).這樣，因j-k最小，即模式■,向右滑動(dòng)的?數(shù),小，避免

因右移造成的可能匹配的丟失.

第五章

線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。

之所以這么說是因?yàn)閿?shù)組結(jié)構(gòu)中若數(shù)組元素蛻化成原子了，那么就成了線性表了。

?種特殊矩陣的壓縮方法：

（1）對(duì)稱矩陣

ij從1開始，k從0開始

（2）下（上）三角矩陣

i,j從1開始，k從1開始

當(dāng)iNj

當(dāng)i<j

(3)3帶形矩陣

i,j從1開始，k從1開始

,[3(i-l)+j-i+l當(dāng)+l

k=[0否則

數(shù)組元素的地址計(jì)算

例如：Loc(aOO)=b

Loc(aiO)=b+(aiO前元素個(gè)數(shù))?L=b+(i?n)?L

Loc(aij)=b+(aij前元素個(gè)數(shù))?L=b+[iXn+j]XL

有一個(gè)二維數(shù)組A[0:8,1:5],每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，假

設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是100,存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字

節(jié)的地址是(①)。若按行存儲(chǔ)，則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址是(②)

和(③)。若按列存儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址是(④)和(⑤)o

解：顯然A[0,l]是該數(shù)組的第一個(gè)元素。數(shù)組共有9X5=45個(gè)元素，最后一個(gè)元素前面共

有44個(gè)元素，loc(A[8,5])=loc(A[0,l])+44*L=100+44*4=276;若按行存儲(chǔ)，A[3,5]前面的第

。行，第1行，第2行肯定存滿了。第三行有人[3,1]6[3,2]八[3,3]八[3,4]在他前面，所以此

時(shí)在A[3,5]前面有3X5+4=19個(gè)元素，loc(A[3,5])=loc(A[0,l])+19*L=100+19X4=176；

同理A[5,3]前面的第0行，第1行，第2行。…第4行肯定存滿了。第5行有A[5,1],A[5,2]

在他前面，所以此時(shí)在A[5,3]前面有5X5+2=27個(gè)元素，loc(A[5,3])=k)c(A[0,l])+27*L=

100+27X4=208；若按列存儲(chǔ)，A[7,l]前面的列肯定已經(jīng)存滿了，而A[7,l]在最前面的列

上，在同列且在他前面的有所以在A[7,l]前面共有0+7個(gè)元素

loc(A[7,lj)=loc(A[0,l])+7*L=100+7X4=128；同理A[2,4],在他前面的列第1列第2列

第3列已經(jīng)存滿，同列且在他前面的有A[0,4],A[l,4],所以A[2,4]前面共有3X9+2=29個(gè)元

素1OC(A[2,4])=1OC(A[0,1])+29*L=100+29X4=216

廣義表兩種存儲(chǔ)結(jié)構(gòu)：

1.頭尾鏈(常用)

結(jié)點(diǎn)的定義：typedefenum{ATOM,LIST}ElemTag;

typedefstructGLnodes{

ElemtagTag;

union{

AtomTypeatom;

Struct{StructGLnode*hp,*tp}Ptr;

)

}*GList;

2.擴(kuò)展性鏈(不常用)

關(guān)于廣義表的一些遞歸算法

1)求廣義表的深度(最大的嵌套的括號(hào)數(shù))

空表的深度是1,原子的深度為0,用頭尾鏈作為存儲(chǔ)結(jié)構(gòu)

intGlistDepth(GlistL)

(

if(!L)return1;

elseif(L->tag=ATOM)return0;

else

max=0;

for(pp=L;PP!=null;pp=pp->ptr.tp)

{

dep=GlistDepth(pp->ptr.hp);

if(max<dep)max=dep;

)

)

2)復(fù)制廣義表

statuscopyGlist(Glist&T,GlistL)〃把L復(fù)制到T

(

if(!L)T=null;

else

(

if(!(T=malloc(sizeofGnode)))

exit(OVERFLOW);

T->tag=L->Tag;

if(L->Tag=ATOM)

T->atom=L->atom;

else

(

copyGlist(T->ptr.hp,L->ptr.hp);

copyGlist(T->ptr.tp,L->ptr.tp);

)

)

returnOK;

)

快速排I?中的分治區(qū)I-的策?的■?用實(shí)例

下列程序段search(a,n,k)在數(shù)組a的前n(n>=4)個(gè)元素中找出第數(shù)l<=k<=n)小的值。這里

假設(shè)數(shù)組a中各元素的值都不相同。

#defineMAXN100

inta[MAXN],n,k;

intsearch_c(inta[],intn,intk)

{intlow,high,i,j,m,t;

k一,;low=0;high=n-l;

do{i=low;j=high;t=a[low];

do(while(i<j&&t<a[j])j-;

if(i<j)a[i++]=a[j];

while(i<j&&t>=a[i])i++

if(i<j)a[j—]=a[i];

}while〃一次分割

if(1)i==kbreak;

if(i<k)low=(2)i+1;elsehigh=⑶i—1

}while⑷low<high;

return(a[k]);

)

矩陣的轉(zhuǎn)置：

用了兩個(gè)數(shù)組num[],cpot[]

num[i]表示第i列有多少元素；cpot[i]表示第i列的第一個(gè)元素轉(zhuǎn)置后的位置。

cpot[l]=l;

cpot[col]=cpot[col-1]+num[col-1];

statusFastTrans(TSMatrixM,TSMatrix&T)

(

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu=0)returnOK;

for(col=1;col<=M.nu;col++)

num[col]=0;

for(t=l;t<=M.tu;t++)

num[M.data[t].j]++;

cpotf1]=0;

for(col=2;col<=M.nu;col++)

cpot[col]=cpot[col-11+num[col-1];

for(p=1;p<=M.tu;p++)

(

col=M.data[p].j;

q=cpotfcol];

T.data[q].i=M.data[p].j;

T.data[q].j=M.data[p].i;

T.data[q].value=M.data[pJ.value;

++cpos[col];

)

returnOK;

)

第六章

結(jié)點(diǎn)的出度(0D)：結(jié)點(diǎn)擁有的非空子樹數(shù)目。

結(jié)點(diǎn)的入度（ID）：指向結(jié)點(diǎn)的分支（或有向弧、指針）的數(shù)目。

樹的度（TD）：樹中結(jié)點(diǎn)一度的最大值。

結(jié)點(diǎn)的度：該結(jié)點(diǎn)的出度

例如在下述結(jié)論中，正確的是（D）【南京理工大學(xué)1999一、4（1分）】

①只有一個(gè)結(jié)點(diǎn)的二義樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換;

④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。

A.①②③B.②③④C.②④D.①④

有關(guān)二叉樹下列說法正確的是（B）【南京理工大學(xué)2000一、11（1.5分）】

A.二叉樹的度為2B.一棵二叉樹的度可以小于2

C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2

若樹中任一結(jié)點(diǎn)的各子樹從左到右有序，則該樹為有序樹（強(qiáng)調(diào)子樹的次

序），否則為無序樹。（只強(qiáng)調(diào)各子樹之間相對(duì)有序，而并不像二叉樹那樣，當(dāng)只有一個(gè)子樹

是要么是左子樹要么是右子樹。而在有序樹中，只有一個(gè)子樹的有序樹就不唯一了。）

例題：在下列情況中，可稱為二叉樹的是（B）

A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹B.哈夫曼樹C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的

有序樹D.每個(gè)結(jié)點(diǎn)只有一?棵右子樹E.以上答案都不對(duì)

C錯(cuò)在有序樹不一淀是二叉樹，有序只是子樹的相對(duì)保持有序，并沒有嚴(yán)格定義具體那顆子

樹就是第幾顆子樹。

■（或樹林）：m（m2O）棵互不相交的有序樹的有序集合。

U

深度=h（h，l）的K（K>1）叉樹至多有（K-D/（K-1）個(gè)結(jié)點(diǎn)。

s='（第i層最大結(jié)點(diǎn)數(shù)）=t

i=ii=iK-1

，i「logk（w（k-l）+l）]

證:設(shè)有n個(gè)結(jié)點(diǎn)的K叉樹的深度為h,若該樹h-1層都是滿的,即每層有最大結(jié)點(diǎn)數(shù)K‘-1

（lWiWh-1）,且其余結(jié)點(diǎn)都落在第h層，則該樹的深度達(dá)最小，如圖6.11所示：

K-\K-\

或：(Kh-1-1)<n(K-l)W(Kh-l)

即:Kh-l<n(k-i)+l=^Kh

取對(duì)數(shù)：(h-1)<logk(n(K-l)+l)^h

因?yàn)閔為正整數(shù)，所以：h=flog*（n（fc-1）+1）1

含有n（nNl）個(gè)結(jié)點(diǎn)的完全二叉樹的深度〃=[log2〃」+l

n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度是「logml+1。（最下層結(jié)點(diǎn)數(shù)>=2）。

設(shè)完全二義樹BT結(jié)點(diǎn)數(shù)為n,結(jié)點(diǎn)按層編號(hào)。對(duì)BT中第i結(jié)點(diǎn)（IWiWn）,

■■若題目已然確定從0開始，則在計(jì)算孩子父親結(jié)點(diǎn)

時(shí)都需要重新變換一下。

有：

(1)若i=l,則i結(jié)點(diǎn)(編號(hào)為i的結(jié)點(diǎn))是BT之根,無雙親;否則(i>l),parent(i)=,

即i結(jié)點(diǎn)雙親的編號(hào)為L(zhǎng)XJ;

(2)若2i>n,則i結(jié)點(diǎn)無左子，否則Lchild⑴=2i,即i結(jié)點(diǎn)的左子位于第2i號(hào)結(jié)點(diǎn);

(3)若2i+l>n,則i結(jié)點(diǎn)無右子,否則Rchild(i)=2i+1,即i結(jié)點(diǎn)的右子位于第2i+l號(hào)結(jié)

點(diǎn)。

證明：采用數(shù)學(xué)歸納法，先證(2)和(3)。

設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹如圖所示。

2,■3

?A2Wi+l+l2i+l+2.

i=l時(shí)，顯然i結(jié)點(diǎn)的左子編號(hào)為2,1的右子編號(hào)為2+1=3,除非2>11,3>11。

設(shè)對(duì)i結(jié)點(diǎn)，命題(2)、(3)成立，即Lchild⑴=2i,Rchild(i)=2i+l0根據(jù)按層編號(hào)規(guī)則，

i+1時(shí)有：

Lchild(i+1)=(2i+1)+1=2(i+1),除非2(i+l)>n,

Rchild(i+l)=(2i+l)+l+l=2(i+1)+1,除非2(i+l)+l>n,

故(2)、(3)得證。

再證(1),它可看作是(2)、(3)的推廣。

因Lchild(j)=2j,所以Parent(2j月，令2j=i，有Parent(i)=i/2=院」(i/2為正整數(shù));

又：Rchild(j)=2j+1,所以Parent(2j+l)=j,令2j+l=i(i=3,5,7…)，有：

Parent(i)=(i-l)/2=,證畢。

例題:一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是()【西安交通大學(xué)1996

三、2(3分)】

A.250B.500C.254D.505E.以上答案都不對(duì)501

例題1：由二叉樹結(jié)點(diǎn)的公式：n=n0+nl+n2=n0+nl+(nO-1)=2n0+nl-l,因?yàn)閚=1001,所以

1002=2n0+nl,在完全二叉樹樹中,nl只能取0或1,在本題中只能取0,故n=501,因此選E。

例題2：高度為K的完全二叉樹至少有2"2_個(gè)葉子結(jié)點(diǎn)。(剛好第K上只有一個(gè)葉子時(shí),

22

高度為K,N=2K*-I+I=2K"

例題3：在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是

用順序存儲(chǔ)二叉樹時(shí)，要按完全二叉樹的形式存儲(chǔ)，非完全二叉樹存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。

設(shè)編號(hào)為i和j的結(jié)點(diǎn)在順序存儲(chǔ)中的下標(biāo)為s和t,則結(jié)點(diǎn)i和j在同一層上的條件是

.log2sJ=Llog2tJo

二叉樹的存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)結(jié)構(gòu)

用一組連續(xù)的存儲(chǔ)單元(一維數(shù)組)存儲(chǔ)二叉樹中元素，稱為二叉樹的順序存

儲(chǔ)結(jié)構(gòu)。描述如下：

#definemaxsige1024〃二叉樹結(jié)點(diǎn)數(shù)最大值〃

typedefdatatypesqtree[maxsize];

若說明sqtreebt;則(bt[o]bt[l]...明[maxsize-1])為二叉樹的存儲(chǔ)空間。每個(gè)單元

bt[i]可存放類型為datatype的樹中元素。

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二又結(jié)中結(jié)點(diǎn)的?般形式為：

Ichilddatarchild

遍歷的遞歸算法

voidpreorder(BTptrT)〃對(duì)當(dāng)前根結(jié)點(diǎn)指針為T的二叉樹按前序遍歷〃

(

if(T){visit(T);//訪問T所指結(jié)點(diǎn)〃

preorder(T->Lchild);//前序遍歷T之左子樹〃

preorder(T->Rchild);//前序遍歷T之右子樹〃

)

)

voidInorder(BTptrT)〃對(duì)當(dāng)前根結(jié)點(diǎn)指針為T的二叉樹按中序遍歷〃

{

if(T){Inorder(T->Lchild);〃中序遍歷T之左子樹〃

visit(T);〃訪問T所指結(jié)點(diǎn)〃

Inorder(T->Rchild);〃中序遍歷T之右子樹〃

voidpostorder(BTptrT)〃對(duì)當(dāng)前根結(jié)點(diǎn)指針為T的二叉樹按后序遍歷〃

{

if(T){postorder(T->Lchild);〃后序遍歷T之左子樹〃

postorder(T->Rchild);〃后序遍歷T之右子樹〃

visit(T);〃訪問T所指結(jié)點(diǎn)〃

從上述三個(gè)算法中看出，若抹去visit(T)語句，則三個(gè)算法是一樣的，可以推斷，這三個(gè)

算法的遞歸路線是一致的(走的線路是?樣的，只是對(duì)結(jié)點(diǎn)的訪問時(shí)間不同而已，前序是第

一次碰到就訪問,中序是第一次返回時(shí)訪問，后序是第二次返回時(shí)訪問。

遍歷非遞歸算法

1.前序遍歷二叉樹的非遞歸算法

算法思路：設(shè)一存放結(jié)點(diǎn)指針的棧S。從根開始，每訪問一結(jié)點(diǎn)后，按前序規(guī)則走左子樹,

但若該結(jié)點(diǎn)右子樹存在，則右子指針進(jìn)棧，以便以后能正確地遍歷相應(yīng)放回到該右子樹上訪

問。

算法描述：voidPreoder-l(BTptrT)〃前序非遞歸遍歷二叉樹T//

{BTptrp；stacktypes;

Clearstack(s);

push(s,T);〃置棧S為空、根指針T進(jìn)?！?/p>

while(!Emptystack(s))

{p=pop(s);〃出棧，棧頂二>P〃

while(p)

{

visit(p);〃訪問p結(jié)點(diǎn)〃

if(p->Rchild)push(s,p->Rchild);〃右子存在時(shí)，進(jìn)?！?/p>

p=p->Lchild;

)〃向左走〃

說明：內(nèi)部循環(huán)是從P結(jié)點(diǎn)出發(fā)一直走到最左，走的過程中保存了每一個(gè)右子樹的地址，(因

為右子樹還沒有被訪問)而且是先進(jìn)后出的，即先保存的比后保存的更先被用作返回地址，

所以是用棧。外循環(huán)正好是當(dāng)內(nèi)部循環(huán)不下去的時(shí)候，退一-棧的情形。即換成他的右子樹

2.中序遍歷二叉樹的非遞歸算法

算法思路：同前序遍歷，棧S存放結(jié)點(diǎn)指針。對(duì)每棵子樹(開始是整棵二叉樹)，沿左找到該子

樹在中序下的第一結(jié)點(diǎn)(但尋找路徑上的每個(gè)結(jié)點(diǎn)指針要進(jìn)棧)，訪問之：然后遍歷該結(jié)點(diǎn)的

右子樹，又尋找該子樹在中序下的第一結(jié)點(diǎn).....直到棧S空為止。

算法描述：voidInorder-1(BTptrT)〃中序非遞歸遍歷二叉樹T〃

{BTptrp;stacktypes;

Clearstack(s);

push(s,T);//置棧S空、根指針進(jìn)棧〃

while(!Emptystack(s))

(

while((p=Getstop(s))&&p)//取棧頂且棧頂存在時(shí)〃

push(s,p->lchild);//p之左子指針進(jìn)?！?/p>

p=pop(s);//去掉最后的空指針〃

if(iEmptystack(s))

{p=pop⑸；〃取當(dāng)前訪問結(jié)點(diǎn)的指針=>P〃

visit(p);〃訪問P結(jié)點(diǎn)〃

push(s,p->Rchild);〃遍歷P之右子樹〃

說明：和前序不?樣，這里的棧保存的是根結(jié)點(diǎn)的地址(因?yàn)橹行虮闅v先訪問左子樹，而根

結(jié)點(diǎn)沒有被訪問到。而前序遍歷不一樣，他一開始就訪問根結(jié)點(diǎn)，所以他不保存根結(jié)點(diǎn)的地

址而是保存右子樹的地址，因?yàn)橛易訕溥€沒有被訪問?？傊?，用棧就是為了幫我們保存還沒

有被訪問的地址，以便將來我們能找到返回的地址)

3.后序遍歷二叉樹的非遞歸算法

算法思路：后序非遞歸遍歷較之前序、中序算法要復(fù)雜一些。原因是對(duì)一個(gè)結(jié)點(diǎn)是否能訪問，

要看它的左、右子樹是否遍歷完，所以每結(jié)點(diǎn)對(duì)應(yīng)一個(gè)標(biāo)志位一tag。tag=O,表示該結(jié)點(diǎn)暫

不能訪問；tag=l,表示該結(jié)點(diǎn)可以訪問。其實(shí)是區(qū)分這次返回是遍歷完左子樹返回的還是

遍歷完右子樹返回的，如果是左子樹返回那么就不能訪問根結(jié)點(diǎn)，如果是右子樹返回的就能

訪問根結(jié)點(diǎn)。

當(dāng)搜索到某P結(jié)點(diǎn)時(shí).，先要遍歷其左子樹，因而將結(jié)點(diǎn)地址P及tag=O進(jìn)棧；當(dāng)P結(jié)

點(diǎn)左子樹遍歷完之后，再遍歷其右子樹，又將地址P及tag=l進(jìn)校；當(dāng)P結(jié)點(diǎn)右子樹遍歷完

后(tag=l),便可以對(duì)P結(jié)點(diǎn)進(jìn)行訪問。

棧元素類型：typedefstruct

{BTptrq;〃存放結(jié)點(diǎn)地址〃

inttag;〃存放當(dāng)前狀態(tài)位〃

}stype;

算法步驟如下：

①若二叉樹T=A(空樹)，返回，算法終止；

②初始化：置棧S空，根指針T=>p；

③反復(fù)以下過程，直到p=A且棧S=A時(shí)算法終止：

若p#八,(p,o)進(jìn)棧，p=p->Lchild(遍歷左子樹),...,直到p=A;出棧，棧

頂=>0tag)；若tag=O,(p,l)進(jìn)棧，p=p->Rchild(遍歷右子樹)，否則,訪問p結(jié)點(diǎn),并置

P=/\O

算法描述：voidpostorder-l(BTptrT)//后序非遞歸遍歷二叉樹T〃

(

inttag;BTptrp;stypesdata;

Clearstack(s);//置棧空〃

p=T;

do{

while(p)

(

sdata.q=p;sdata.tag=O;

push(s,sdata);//(p,0)進(jìn)?！?/p>

p=p->Lchild;//遍歷p之左子樹〃

)

sdata=pop(s);〃退棧

p=sdata.q;//取指針

tag=sdata.tag;〃狀態(tài)位〃

if(tag==O)〃從左子樹返回時(shí)，根的tag=O

(

sdata.q=p;

sdata.tag=l;〃這時(shí)要進(jìn)入根的右子樹了，所以將根的tag=l,

〃下次碰到根時(shí)就可以訪問了

push(s,sdata);//(p,I)進(jìn)棧，根還得進(jìn)一次棧

p=p->Rchild;//遍歷右子樹〃

else//tag=l,這時(shí)說明右子樹訪問完了后返回，所以這次要對(duì)根訪問了

(

visit(p);〃訪問p結(jié)點(diǎn)〃

p=NULL;〃要再退到上層，因?yàn)樵摽脴湟呀?jīng)徹底訪問完了

)〃之所以把p=null是不讓他進(jìn)入while

}while(pll!Emptystack(s));

)

例題：假設(shè)二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，rood為根結(jié)點(diǎn)，p-為任一給定的結(jié)點(diǎn)，

寫出求從根結(jié)點(diǎn)到p八之間路徑的非遞歸算法。

[題目分析]采用后序非遞歸遍歷二叉樹，棧中保留從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑上所有結(jié)點(diǎn)。

voidPrintPath(BiTreebt,p)〃打印從根結(jié)點(diǎn)bt到結(jié)點(diǎn)p之間路徑上的所有結(jié)點(diǎn)

(

BiTreeq=bt,s[];〃s是元素為二叉樹結(jié)點(diǎn)指針的棧，容量足夠大

inttop=0;tag[];〃tag數(shù)組元素值為?；?,訪問左、右子樹標(biāo)志，tag和s同步

if(q==p)

{printf(q->data);

return;

)〃根結(jié)點(diǎn)就是所找結(jié)點(diǎn)

while(q!=nu11||top>0)

(

while(q!二null)〃左子女入棧，并置標(biāo)記

if(q=P)〃找到結(jié)點(diǎn)P，棧中元素均為結(jié)點(diǎn)P的祖先

{printf(“從根結(jié)點(diǎn)到p結(jié)點(diǎn)的路徑為\n");

for(i=l;i<=top;i++)

printf(s[i]->data);

printf(q->data);

return;

)

else

{s[++top]=q;

tag[top]=0;

q=q->lchild;

)〃沿左分支向下

while(top>0&&tag[top]==l))

top-；〃本題不要求輸出遍歷序列，這里只退棧

if(top>0)

{q=s[top];

q=q->rchild;

tag[top]=l;

)〃沿右分支向下

}//while(q!=null||top>0)

}〃結(jié)束算法PrintPath

按層次遍歷二叉樹

算法描述：

voidLayerorder(BTptrT)〃對(duì)二叉樹T按層次遍歷〃

{

BTpfrp;qtypeQ;

if(T)

(

Clearqueue(Q);〃置隊(duì)Q空〃

Enqueue(Q,T);〃將根指針進(jìn)隊(duì)〃

while(!Emptyqueue(Q))

{

p=Dequeue(Q);〃出隊(duì)，隊(duì)頭元素np〃

visit(p);〃訪問p結(jié)點(diǎn)〃

if(p->Lchild)Enqneue(Q,p->Lchid);〃左子指針進(jìn)隊(duì)〃

if(p->Rchild)Enqneue(Q,p->Rchid);//右子指針進(jìn)隊(duì)//

)

)

遍歷算法的應(yīng)用

凡是對(duì)二叉樹中各結(jié)點(diǎn)進(jìn)行一次處理的問題，都可以用遍歷算法來完成。

1.利用遍歷算法對(duì)二叉樹中各類結(jié)點(diǎn)計(jì)數(shù)

設(shè)二叉樹中出度=0、1、2的結(jié)點(diǎn)數(shù)分別為n0、nl和n2,初值均為0。

套用遍歷算法(前序、中許、后序均可)，掃描到樹中某p結(jié)點(diǎn)時(shí)，若：

if((p->Lchild==NULL)&&(p->Rchild==NULL))

n0++;〃p為葉子〃

elseif((p->Lchild)&&(p->Rchild))

n2++;//p為出度=2的結(jié)點(diǎn)〃

elsenl++;〃p為出度=1的結(jié)點(diǎn)〃

如：只要把遍歷算法在遍歷時(shí)稍微改變一下。

n0=nl=n2=0;

voidpreorder(BTptrT)〃對(duì)當(dāng)前根結(jié)點(diǎn)指針為T的二叉樹按前序遍歷〃

(

if(T){//visit(T);訪問T所指結(jié)點(diǎn)〃

if((T->Lchild==NULL)&&(T->Rchild==NULL))

n0++;〃p為葉子〃