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

第一章

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

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、

記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。

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

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

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

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

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

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

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

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

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

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

趨和直接后繼。

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

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

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

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

由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。

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

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

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

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

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

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

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

x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y-;}

elsex++;

?T(n)=O(l)

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

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

的函數(shù)。

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

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

關(guān)，但在最壞的情況下，其時間復雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復

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

增長率由小至大的順序排列下列各函數(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)...就相當于n次方階；25是指

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

大的順序可排列如下：

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

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

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

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

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

輸入：有0個或多個輸入

輸出：有一個或多個輸出

設(shè)計算法的要求(追求的目標)

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

算法原地工作：當空間復雜度為0(1)時，稱算法為就地工作(原地工作)。

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

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

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

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

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

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

邏輯結(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ù)列計算的時間復雜度是O(n)

第二章

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

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

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

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

來確定。

何時選用順序表、何時選用鏈表作為線性表的存儲結(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)鏈表為宜。

第三章

例如：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ù)之間的相對次序相同”；

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

2.三式中的“運算符之間的的相對次序不同”；

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

（而前綴和后綴運算只需要一個存儲操作數(shù)的棧，而中綴求值需要兩個棧，符號棧和操

作數(shù)棧）

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

一個最小表達式；

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

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

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

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

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

如果是運算符。這與當前棧頂比較。個如果比當前棧頂高，則入棧，如果低則說明當前

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

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

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

中綴表達式直接求值算法：

OPNDTypeEvalueExpression()

{//OPTR和OPND分別為運算符棧和操作數(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〃如果是運算符，則與當前的棧頂比較

(

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

(

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

c=getchar();

break;

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

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

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

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

Case〉，：〃比當前棧頂?shù)?，則要把棧頂先運算完(先規(guī)約)

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

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

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

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

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

Break;

[//Switch

}//else

}//whild

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

)

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

{//E[n]是中綴表達式、B[n]是后綴表達式存儲的空間

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

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

do{

x=Efi++l;〃掃描當前表達式分量〃

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

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

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

〃輸出棧頂運算符，并退棧直到遇見棧底的開始放進去的那個井〃

elseif(isdigit(x))

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

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

(

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

B|j++]=pop(S);〃輸出棧頂，并退棧〃

pop(S);〃退掉‘(力

}

else//x為運算符〃

(

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

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

Push(S,x);〃01<x時x進?！?/p>

)

}while(x!='#')；

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

雙端隊列：

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

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

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

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

要用到隊列，因為隊列可以用在廣度優(yōu)先中，隊列中的元素表示離中心點依次越來越遠。

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

鏈式棧:

鏈式隊列:

N個結(jié)點的不同二叉樹有：=-等于不同的進出?？倲?shù)

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

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

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

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

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

列)，則在輸出序列中不可能出現(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候，Pj和Pk一定都同時被壓入棧中，那么

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

用兩個棧來模擬一個隊列

棧的特點是后進先出，隊列的特點是先進先出。所以，用兩個棧si和s2模擬一個隊列

時，si作輸入棧，逐個元素壓棧，以此模擬隊列元素的入隊。當需要出隊時，將棧si

退棧并逐個壓入校s2中，si中最先入棧的元素，在s2中處于棧頂。s2退棧，相當于隊

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

第四章

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

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

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

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

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

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

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

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

匹配的成功，因為S2s3..…Si-1==T2T3……41,而T213....!>1是不等于丁建2....!>2。除

非next[j]=j-l；因為next定義的是最長的。所以任何挪動小于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)退到起點了說明在這個位置徹底不可能了，

{++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)是

最長的序列，所以k+1也是next[j+l]最長的

若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表示當前求的next

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

(

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

(

++i；

++j；

next[i]=j;

)

Elsej=next[jj;

因為next[]在匹配過程中，若T[j]=T[next|jJ]；那么當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）所組成的字符串,其長度等于?格個數(shù)

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

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

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

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

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

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

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

第五章

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

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

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

（1）對稱矩陣

ij從1開始，k從0開始

（2）下（上）三角矩陣

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

當iNj

當i<j

(3)3帶形矩陣

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

,[3(i-l)+j-i+l當+l

k=[0否則

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

例如：Loc(aOO)=b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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個元

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

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

1.頭尾鏈(常用)

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

typedefstructGLnodes{

ElemtagTag;

union{

AtomTypeatom;

Struct{StructGLnode*hp,*tp}Ptr;

)

}*GList;

2.擴展性鏈(不常用)

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

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

空表的深度是1,原子的深度為0,用頭尾鏈作為存儲結(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)復制廣義表

statuscopyGlist(Glist&T,GlistL)〃把L復制到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-的策?的■?用實例

下列程序段search(a,n,k)在數(shù)組a的前n(n>=4)個元素中找出第數(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)置：

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

num[i]表示第i列有多少元素；cpot[i]表示第i列的第一個元素轉(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é)點的出度(0D)：結(jié)點擁有的非空子樹數(shù)目。

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

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

結(jié)點的度：該結(jié)點的出度

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

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

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

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

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

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

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

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

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

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

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

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

有序樹D.每個結(jié)點只有一?棵右子樹E.以上答案都不對

C錯在有序樹不一淀是二叉樹，有序只是子樹的相對保持有序，并沒有嚴格定義具體那顆子

樹就是第幾顆子樹。

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

U

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

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

i=ii=iK-1

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

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

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

K-\K-\

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

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

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

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

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

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

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

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

時都需要重新變換一下。

有：

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

即i結(jié)點雙親的編號為LXJ;

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

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

點。

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

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

2,■3

?A2Wi+l+l2i+l+2.

i=l時，顯然i結(jié)點的左子編號為2,1的右子編號為2+1=3,除非2>11,3>11。

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

i+1時有：

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個結(jié)點，其中葉子結(jié)點的個數(shù)是()【西安交通大學1996

三、2(3分)】

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

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

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

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

22

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

例題3：在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是

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

設(shè)編號為i和j的結(jié)點在順序存儲中的下標為s和t,則結(jié)點i和j在同一層上的條件是

.log2sJ=Llog2tJo

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

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

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

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

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

typedefdatatypesqtree[maxsize];

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

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

2.鏈式存儲結(jié)構(gòu)

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

Ichilddatarchild

遍歷的遞歸算法

voidpreorder(BTptrT)〃對當前根結(jié)點指針為T的二叉樹按前序遍歷〃

(

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

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

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

)

)

voidInorder(BTptrT)〃對當前根結(jié)點指針為T的二叉樹按中序遍歷〃

{

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

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

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

voidpostorder(BTptrT)〃對當前根結(jié)點指針為T的二叉樹按后序遍歷〃

{

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

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

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

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

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

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

遍歷非遞歸算法

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

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

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

問。

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

{BTptrp；stacktypes;

Clearstack(s);

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

while(!Emptystack(s))

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

while(p)

{

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

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

p=p->Lchild;

)〃向左走〃

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

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

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

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

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

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

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

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

{BTptrp;stacktypes;

Clearstack(s);

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

while(!Emptystack(s))

(

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

push(s,p->lchild);//p之左子指針進棧〃

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

if(iEmptystack(s))

{p=pop⑸；〃取當前訪問結(jié)點的指針=>P〃

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

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

說明：和前序不?樣，這里的棧保存的是根結(jié)點的地址(因為中序遍歷先訪問左子樹，而根

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

址而是保存右子樹的地址，因為右子樹還沒有被訪問?？傊?，用棧就是為了幫我們保存還沒

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

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

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

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

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

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

訪問根結(jié)點。

當搜索到某P結(jié)點時.，先要遍歷其左子樹，因而將結(jié)點地址P及tag=O進棧；當P結(jié)

點左子樹遍歷完之后，再遍歷其右子樹，又將地址P及tag=l進校；當P結(jié)點右子樹遍歷完

后(tag=l),便可以對P結(jié)點進行訪問。

棧元素類型：typedefstruct

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

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

}stype;

算法步驟如下：

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

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

③反復以下過程，直到p=A且棧S=A時算法終止：

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

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

P=/\O

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

(

inttag;BTptrp;stypesdata;

Clearstack(s);//置?？铡?/p>

p=T;

do{

while(p)

(

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

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

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

)

sdata=pop(s);〃退棧

p=sdata.q;//取指針

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

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

(

sdata.q=p;

sdata.tag=l;〃這時要進入根的右子樹了，所以將根的tag=l,

〃下次碰到根時就可以訪問了

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

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

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

(

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

p=NULL;〃要再退到上層，因為該棵樹已經(jīng)徹底訪問完了

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

}while(pll!Emptystack(s));

)

例題：假設(shè)二叉樹采用鏈式存儲結(jié)構(gòu)進行存儲，rood為根結(jié)點，p-為任一給定的結(jié)點，

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

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

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

(

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

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

if(q==p)

{printf(q->data);

return;

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

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

(

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

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

{printf(“從根結(jié)點到p結(jié)點的路徑為\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)〃對二叉樹T按層次遍歷〃

{

BTpfrp;qtypeQ;

if(T)

(

Clearqueue(Q);〃置隊Q空〃

Enqueue(Q,T);〃將根指針進隊〃

while(!Emptyqueue(Q))

{

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

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

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

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

)

)

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

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

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

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

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

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

n0++;〃p為葉子〃

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

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

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

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

n0=nl=n2=0;

voidpreorder(BTptrT)〃對當前根結(jié)點指針為T的二叉樹按前序遍歷〃

(

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

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

n0++;〃p為葉子〃