北大數(shù)據(jù)結(jié)構(gòu)課講義

會計學1北大數(shù)據(jù)結(jié)構(gòu)課講義4.1

棧

棧的定義

棧（stack）又稱堆棧，是限定只在表尾進行插入或刪除操作的線性表。棧S=(a1,a2,…，an)

是按a1,a2,…，an次序進棧的，a1為棧底元素，an為棧頂元素。第1頁/共65頁棧與遞歸 遞歸可使問題及求解步驟的描述變得簡潔而清晰。特別是對于復雜問題，用遞歸方法分析描述，比較自然，利于理解。遞歸包括遞歸步驟和終止出口。

遞歸問題轉(zhuǎn)化為非遞歸往往要用棧來實現(xiàn),把在遞歸中用到的變量入棧出棧,如書上【習題4-4】之9,10第2頁/共65頁4.7

隊列

隊列是一種先進先出（FIFO）線性表。只允許在其一端刪除元素，即隊頭（front），只允許在其另一端插入元素，即隊尾（rear）。第3頁/共65頁圖4-10順序隊列的插入和刪除操作第4頁/共65頁……01234……

M-2M-101234M-1M-2::

循環(huán)隊列

把隊列(數(shù)組)設(shè)想成頭尾相連的循環(huán)表，使得數(shù)組前部由于刪除操作而導致的無用空間盡可能得到重復利用，這樣的隊列稱為循環(huán)隊列。入隊時需先修改入隊指針（隊尾指針）

rear==(rear+1)%QueueMaxSize出隊時需要修改隊頭指針front==(front+1)%QueueMaxSize第5頁/共65頁

初始時,隊列為空,有

front=0rear=0測試隊列為空的條件是

front=rear1Mabcdfrontrearad約定

rear指出實際隊尾元素所在的位置,front指出實際隊頭元素所在位置的前一個位置.第6頁/共65頁

隊列的靜態(tài)數(shù)組一般是循環(huán)使用的。 為了判別隊列滿和隊列空的指針狀況，令front指向隊首元素的前一個位置。 入隊時需先修改入隊指針（隊尾指針）

rear==(rear+1)%QueueMaxSize

然后判斷隊列滿的條件

(rear+1)%QueueMaxSize==front

最后將元素入隊。 出隊時先 判斷隊列空的條件

front==rear

然后修改隊頭指針

front==(front+1)%QueueMaxSize

最后將元素出隊。第7頁/共65頁第8頁/共65頁在順序隊列中插入和刪除，不需要比較和移動任何元素，只需修改隊尾和隊首指針，并向隊尾寫入元素或從隊首取出元素時間復雜度為：O(1)若存儲隊列的數(shù)組的長度為N，則隊列長度（即所含元素個數(shù)）為:(N+rear-front)%N第9頁/共65頁（2）隊列的鏈式存儲結(jié)構(gòu)

structLinkQueue{ LNode*front; LNode*rear; }; structLNode{ ElmeTypedata; LNode*next; };structLNode{ElemType data;//數(shù)據(jù)域

Lnode* next;//指針域

};

第10頁/共65頁第11頁/共65頁在鏈隊中插入和刪除，不需要比較和移動任何元素，只需修改個別相關(guān)指針和進行結(jié)點的動態(tài)分配或回收操作時間復雜度為：O(1)第12頁/共65頁4.4.4

隊列運算的實現(xiàn)1.隊列運算在順序存儲結(jié)構(gòu)上的實現(xiàn) （1）初始化隊列

voidInitQueue(Queue&Q) { Q.MaxSize=10; Q.queue=newElemType[Q.MaxSiize]; Q.front=Q.rear=0; }

第13頁/共65頁

（2）將隊列清空,并釋放動態(tài)存儲空間

voidClearQueue(Queue&Q) { if(Q.queue!=NULL)delete[]Q.queue; Q.front=Q.rear=0; Q.queue=NULL; Q.MaxSize=0; }

第14頁/共65頁（3）檢查隊列是否為空

intQueueEmpty(Queue&Q) { returnQ.front==Q.rear; }（4）讀取隊頭元素//讓front指針不是指向隊首元素，而是指向它的前一個位置即：隊首元素是隊首指針front的下一個位置中的元素

ElemTypePeekQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"QueueisEmpty."<<endl; exit(1);} returnQ.queue[(Q.front+1)%QueueMaxSize]; }第15頁/共65頁（5）向隊列插入新元素-1voidEnQueue(Queue&Q,constElemType&item){ intk=(Q.rear+1)%QueueMaxSize;//隊尾的下一位置

if(k==Q.front){ cerr<<"Queueisoverflow."<<endl; exit(1); } Q.rear=k; Q.queue[k]=item;}入隊時需先修改入隊指針（隊尾指針）

rear==(rear+1)%QueueMaxSize然后判斷隊列滿的條件

(rear+1)%QueueMaxSize==front最后將元素入隊。第16頁/共65頁（5）向隊列插入新元素-2voidEnQueue(queue&Q,constElemType&item){ if((Q.rear+1)%QueueMaxSize==Q.front)

{//擴大2倍的存儲空間

intk=sizeof(ElemType); Q.queue=(ElemType*)realloc(Q.queue, 2*Q.MaxSize*k); //把原隊列尾部內(nèi)容后移MaxSize個位置

if(Q.rear!=Q.MaxSize-1) 第17頁/共65頁{ for(inti=0;i<=q.rear;i++) Q.queur[i+Q.MaxSize]=Q.queur[i]; Q.rear+=Q.MaxSize; } Q.MaxSize=2*Q.MaxSize;

} //求出隊尾的下一個位置

Q.rear=(Q.rear+1)%Q.MaxSize; //把item的值賦給新的隊尾位置

Q.queue[Q.rear]=item;}入隊時需先修改入隊指針（隊尾指針）

rear==(rear+1)%QueueMaxSize然后判斷隊列滿的條件

(rear+1)%QueueMaxSize==front最后將元素入隊。第18頁/共65頁（6）從隊列中刪除元素ElemTypeOutQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"Queueisempty."<<endl; exit(1); } Q.front=(Q.front+1)%QueueMaxSize;//隊頭指向下一位置

returnQ.queue[Q.front];}（7）檢查隊列是否已滿intQueueFull(Queue&Q){ return(Q.rear+1)%QueueMaxSize==Q.front;}出隊時先判斷隊列空的條件

front==rear然后修改隊頭指針

front==(front+1)%QueueMaxSize最后將元素出隊。第19頁/共65頁

2.隊列運算在鏈接存儲結(jié)構(gòu)上的實現(xiàn)（1）初始化鏈隊voidInitQueue(LinkQueue&HQ){ HQ.front=HQ.rear=NULL;}（2）清空鏈隊voidClearQueue(LinkQueue&HQ){ LNode*p=HQ.front; while(p!=NULL){ HQ.front=HQ.front->next; deletep; p=HQ.front; } HQ.rear=NULL;}structLNode{ElemType data;//數(shù)據(jù)域

Lnode* next;//指針域

};

第20頁/共65頁（3）判斷鏈隊是否為空intQueueEmpty(LinkQueue&HQ){ returnHQ.front==NULL;}（4）讀取隊首元素ElemTypePeekQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } returnHQ.front->data;}第21頁/共65頁（5）向鏈隊中插入一個元素voidEnQueue(LinkQueue&HQ,constElemType&item){ LNode*newptr=newLNode; if(newptr==NULL){ cerr<<“Memoryalocationfailure."<<endl; exit(1); } newptr->data=item; newptr->next=NULL; if(HQ.rear==NULL) HQ.front=HQ.rear=newptr; elseHQ.rear=HQ.rear->next=newptr;}//不妨與書上P78的算法9(ppt4,算法9)：向單鏈表的末尾插入一個元素“相對照學習//思考與書上P137的算法2(ppt6,算法5)：向鏈棧中插入一個元素“的不同第22頁/共65頁（6）從隊列中刪除一個元素ElemTypeOutQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } ElemTypetemp=HQ.front->data; Lnode*p=HQ.front; HQ.front=p->next; if(HQ.front==NULL) HQ.rear=NULL; deletep; returntemp;}//不妨與書上P79的算法10(ppt4,算法12)：從單鏈表中刪除表頭元素“相對照學習//也可對照書上P137的算法3(ppt6,算法6)：從鏈棧中刪除一個元素”第23頁/共65頁4.4.6

隊列應(yīng)用簡介第一：解決主機與外設(shè)之間速度不匹配的問題如： 打印輸出。設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，用隊列存儲待輸出的數(shù)據(jù)，解決主機與外設(shè)速度不匹配的問題。第二：解決多用戶引起的資源競爭問題如： 多用戶CPU資源競爭。操作系統(tǒng)通常按照每個請求在時間上的先后順序，把它們排成一個隊列第24頁/共65頁1.

熟悉棧的含義，掌握基本概念、存儲結(jié)構(gòu)和運算的實現(xiàn)。2.熟悉隊列的含義，掌握基本概念、存儲結(jié)構(gòu)和運算的實現(xiàn)。本章學習要點第25頁/共65頁本章習題(第173－177頁)(!!)4.1.1~4.1.4請獨立完成該題4個問題(!!)4.2請獨立完成該題(#)4.3課外思考該題(!)4.4.1~2,7能在書上程序的基礎(chǔ)上編寫程序?qū)崿F(xiàn)(#)4.4.3~6,8~11有興趣者課外思考第26頁/共65頁

書面回答,請以紙面形式上交課代表,要求整潔清楚，

時間期限:5月10日[格式提頭:學號/序號/姓名/第四章]1、對于一個棧，如果輸入項序列由A，B，C組成，給出全部可能和不可能的輸出序列。2、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通過棧S，一個元素出棧后立即進入隊列Q，若8個元素出隊列的次序是a3,a6,a7,a5,a8,a4,a2,a1，則棧S的容量至少應(yīng)該是多少？（即至少應(yīng)該容納多少個元素？）3、設(shè)有算術(shù)表達式x+a*(y-b)-c/d，將其轉(zhuǎn)換為后綴表達式。4、有字符串序列為3*-y-a/y↑2,試利用棧給出將次序改變?yōu)?y-*ay2↑/-的操作步驟。（用X代表掃描字符串函數(shù)中順序取一字符進棧的操作，S代表從棧中取出一個字符加入到新字符串尾的出棧操作。）例如，ABC變?yōu)锽CA，則操作步驟為XXSXSS。5、假設(shè)Q[0..10]是一個線性隊列，初始狀態(tài)為front=rear=0，畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。（要求明確標出各元素在隊列中的位置序號，頭、尾指針）

(a)d,e,b,g,h入隊

(b)d,e出隊

(c)i,j,k,l,m入隊

(d)b出隊

(e)n,o,p入隊課后作業(yè)第四章第27頁/共65頁約定:進棧X,出棧S4個元素依次進棧,任何時候都可以出棧,請寫出所有可能的出棧序列XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSXSXXSSXSXSXSXXSS方法提示第28頁/共65頁第五章樹

5.1樹的概念

5.2二叉樹

5.3二叉樹的遍歷

5.4二叉樹的其他運算

5.5樹的存儲結(jié)構(gòu)和運算退出第29頁/共65頁校長一系二系三系六系教務(wù)處科研處總務(wù)處601602教務(wù)科603ABCD…………張三李四王五…例1…工廠第30頁/共65頁(根目錄)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………第31頁/共65頁例3第32頁/共65頁例4

au

ee

cn

edutsinghua

cspandabuaapku………………第33頁/共65頁一個數(shù)據(jù)元素:一個結(jié)點A數(shù)據(jù)元素(結(jié)點)之間的關(guān)系:分支AB第34頁/共65頁5.1樹的概念

5.1.1

樹的定義

樹Tree：是由n0個結(jié)點組成的有窮集合以及結(jié)點之間關(guān)系組成的集合構(gòu)成的結(jié)構(gòu)。

遞歸的數(shù)據(jù)結(jié)構(gòu)樹的遞歸定義： （1）樹由具有相同特性的數(shù)據(jù)元素（稱為結(jié)點）組成，結(jié)點個數(shù)為0時，稱為空樹； （2）在一棵非空樹中有且僅有一個根root結(jié)點，除根結(jié)點外，其余結(jié)點可分為m(m≥0)個互不相交的子集，每個子集也是一棵樹，稱為子樹SubTree。第35頁/共65頁第36頁/共65頁tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r} ElemType是具有相同特性的數(shù)據(jù)元素。 關(guān)系r滿足： （1）有且僅有一個結(jié)點沒有前驅(qū)，這個結(jié)點即樹根； （2）除樹根外，其余結(jié)點有且僅有一個前驅(qū)； （3）包括根結(jié)點在內(nèi)的所有結(jié)點都可以有任意個(含0個)后繼。如上圖：K={A，B，C，D，E，F(xiàn)，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}第37頁/共65頁JIHGFEACXBA的第1棵子樹A的第3棵子樹A的第2棵子樹樹(邏輯上)的特點1.有且僅有一個結(jié)點沒有前驅(qū)結(jié)點,該結(jié)點為樹的根結(jié)點。2.除了根結(jié)點外,每個結(jié)點有且僅有一個直接前驅(qū)結(jié)點。3.包括根結(jié)點在內(nèi)，每個結(jié)點可以有多個后繼結(jié)點。第38頁/共65頁

5.1.2

樹的表示 樹有五種表示方式： （1）樹形表示， （2）二元組表示， （3）集合圖表示， （4）凹入表表示， （5）廣義表表示。第39頁/共65頁JIHGFEACXB1.

樹形表示法

借助自然界中一棵倒置的樹的形狀來表示數(shù)據(jù)元素之間層次關(guān)系的方法。第40頁/共65頁tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r}如上圖：K={A，B，C，D，E，F(xiàn)，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}2.

二元組表示法

第41頁/共65頁第42頁/共65頁1.

結(jié)點的度：2.

樹的度：3.

葉結(jié)點：4.

分支結(jié)點:5.

層次的定義:JIHGFEACXB該結(jié)點擁有的子樹的數(shù)目。樹中結(jié)點度的最大值。度為0的結(jié)點.度非0的結(jié)點.

根結(jié)點為第一層,若某結(jié)點在第i層,

則其孩子結(jié)點(若存在)為第i+1層.5.1.3樹的基本術(shù)語第1層第2層第3層第43頁/共65頁7.

樹林(森林):m0棵不相交的樹組成的樹的集合.8.

樹的有序性:ABCDEABCDEFF6.

樹的深度:樹中結(jié)點所處的最大層次數(shù).

若樹中結(jié)點的子樹的相對位置不能隨意改變,則稱該樹為有序樹，否則稱該樹為無序樹。JIHGFEACXB有序樹？無序樹？深度為3的樹第44頁/共65頁5.1.4

樹的性質(zhì)性質(zhì)1

樹中結(jié)點個數(shù)等于所有結(jié)點的度數(shù)加1。性質(zhì)2

度為k的樹中第i層上至多有ki-1個結(jié)點（i≥1）。性質(zhì)3

深度為h的k叉樹中至多有(kh-1)/(k-1)結(jié)點。

滿k叉樹：結(jié)點個數(shù)等于(kh-1)/(k-1)的k叉樹。性質(zhì)4

具有n個結(jié)點的k叉樹的最小深度為logk(n(k-1)+1)。JIHGFEACXB第45頁/共65頁5.2二叉樹

5.2.1

二叉樹的定義

二叉樹為度為2的有序樹。第46頁/共65頁

遞歸定義：或者是一棵空樹，或者是一棵由根結(jié)點和兩棵互不相交的左、右子樹組成的非空樹。左、右子樹同樣也是二叉樹。 左孩子leftchild，左子樹的根結(jié)點。 右孩子rightchild，右子樹的根結(jié)點。第47頁/共65頁二叉樹的基本形態(tài)：(空)根根左子樹根右子樹根左子樹右子樹

(a)空二叉樹；

(b)僅有一個根結(jié)點的二叉樹；

(c)右子樹為空的二叉樹；

(d)左右子樹均非空的二叉樹；

(e)左子樹為空的二叉樹。

第48頁/共65頁

1.度為2的樹是二叉樹。下面兩種說法正確與否?應(yīng)該怎樣說才合適?

2.具有三個結(jié)點的樹可以有以下五種形態(tài):結(jié)論:子樹有嚴格的左右之分的度為2的樹是二叉樹。

結(jié)論:具有三個結(jié)點的樹只有兩種形態(tài)。第49頁/共65頁兩種特殊形態(tài)的二叉樹

若一棵二叉樹中的結(jié)點,或者為葉結(jié)點，或者具有兩棵非空子樹,并且葉結(jié)點都集中在二叉樹的最下面一層.這樣的二叉樹為滿二叉樹.1.滿二叉樹

若一棵二叉樹中只有最下面兩層的結(jié)點的度可以小于2,并且最下面一層的結(jié)點(葉結(jié)點)都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.2.完全二叉樹第50頁/共65頁1.一棵非空二叉樹的第i層最多有2i–1個結(jié)點(i1)。證明(采用歸納法)(1).當i=1時,結(jié)論顯然正確。非空二叉樹的第1層有且僅有一個結(jié)點,即樹的根結(jié)點.(2).假設(shè)對于第j層(1ji–1)結(jié)論也正確,即第j層最多有2j-1個結(jié)點.(3).有定義可知,二叉樹中每個結(jié)點最多只能有兩個孩子結(jié)點。若第i–1層的每個結(jié)點都有兩棵非空子樹,則第i層的結(jié)點數(shù)目達到最大.而第i–1層最多有2i–2個結(jié)點已由假設(shè)證明,于是,應(yīng)有

22i–2=2i–1證畢.5.2.2二叉樹的性質(zhì)第51頁/共65頁2.

深度為h的非空二叉樹最多有2h-1個結(jié)點.證明:

由性質(zhì)1可知,若深度為h的二叉樹的每一層的結(jié)點數(shù)目都達到各自所在層的最大值,則二叉樹的結(jié)點總數(shù)一定達到最大。即有

20+21+22+…+2i-1+…+2h-1=2h-1證畢.第52頁/共65頁3.

若非空二叉樹有n0個葉結(jié)點,有n2個度為2的結(jié)點,

則n0=n2+1

證明:

設(shè)該二叉樹有n1個度為1的結(jié)點,結(jié)點總數(shù)為n,有

n=n0+n1+n2

--------(1)

設(shè)二叉樹的分支數(shù)目為B,有

B=n-1

--------(2)這些分支來自度于為1的結(jié)點與度度為2結(jié)點,即

B=n1+2n2

--------(3)聯(lián)列關(guān)系(1),(2)與(3),可得到

n0=n2+1證畢.4.

具有n個結(jié)點的完全二叉樹的深度h=log2n+1.證明:(略)推論：

n0=n2+2n3+3n4++(m-1)nm+1第53頁/共65頁5.若對具有n個結(jié)點的完全二叉樹按照層次從上到下,每層從左到右的順序進行編號,則編號為i的結(jié)點具有以下性質(zhì):(1)若編號為i的結(jié)點有左孩子,則左孩子結(jié)點的編號為2i;

若編號為i的結(jié)點有右孩子,則右孩子結(jié)點的編號為2i+1.(2)除樹根結(jié)點外,若一個結(jié)點的標號為i,則它的雙親結(jié)點的 編號為i/2,也就是說,當i為偶數(shù)時,其雙親結(jié)點的編號為i/2,

它是雙親結(jié)點的左孩子,當i為奇數(shù)時,其雙親結(jié)點的編號 為(i-1)/2,它是雙親結(jié)點的右孩子.(3)若i≦|_n/2_|,即2i≦n,則編號為i的結(jié)點為分支結(jié)點,

否則為葉子結(jié)點.(4)若n為奇數(shù),則每個分支結(jié)點都既有左孩子,又有右孩子;

若n為偶數(shù),則編號最大的分支結(jié)點(編號為n/2)只有 左孩子,沒有右孩子,其余分支結(jié)點左、右孩子都有.第54頁/共65頁12345678910n=10第55頁/共65頁換個說法5.若對具有n個結(jié)點的完全二叉樹按照層次從上到下,每層從左到右的順序進行編號,則編號為i的結(jié)點具有以下性質(zhì):(1)當i=1,則編號為i的結(jié)點為二叉樹的根結(jié)點;

若i>1,則編號為i的結(jié)點的雙親結(jié)點的編號為i/2.(2)若2i>n,則編號為i的結(jié)點無左子樹;

若2in,則編號為i的結(jié)點的左子樹的根的編號為2i.(3)若2i+1>n,則編號為i的結(jié)點無右子樹;

若2i+1n,則編號為i的結(jié)點的右子樹的根的編號為2i+1.第56頁/共65頁5.2.3

二叉樹的抽象數(shù)據(jù)類型

ADTBinaryTree Data：存儲類型BTreeType，用BT標識符表示

Operations：

voidInitBTree(BTreeType&BT); //初始化一棵二叉樹，即置為空樹

voidCreateBTree(BTreeType&BT,char*a); //根據(jù)字符串a(chǎn)建立一棵二叉樹

intBTreeEmpty(BTreeTypeBT); //判斷一棵二叉樹是否為空樹

voidTraverseBTree(BTreeTypeBT); //按照一定次序遍歷二叉樹

intBTreeDepth(BTreeTypeBT); //求一棵二叉樹的深度

voidPrintBTree(BTreeTypeBT); //按照一種表示方法輸出二叉樹