會計學1北大數據結構課講義4.1

棧

棧的定義

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

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

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

隊列

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

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

循環隊列

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

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

初始時,隊列為空,有

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

front=rear1Mabcdfrontrearad約定

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

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

rear==(rear+1)%QueueMaxSize

然后判斷隊列滿的條件

(rear+1)%QueueMaxSize==front

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

front==rear

然后修改隊頭指針

front==(front+1)%QueueMaxSize

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

structLinkQueue{ LNode*front; LNode*rear; }; structLNode{ ElmeTypedata; LNode*next; };structLNode{ElemType data;//數據域

Lnode* next;//指針域

};

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

隊列運算的實現1.隊列運算在順序存儲結構上的實現 （1）初始化隊列

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

第13頁/共65頁

（2）將隊列清空,并釋放動態存儲空間

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); //把原隊列尾部內容后移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.隊列運算在鏈接存儲結構上的實現（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;//數據域

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

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

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

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

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

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

(b)d,e出隊

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

(d)b出隊

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

5.1樹的概念

5.2二叉樹

5.3二叉樹的遍歷

5.4二叉樹的其他運算

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

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

au

ee

cn

edutsinghua

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

5.1.1

樹的定義

樹Tree：是由n0個結點組成的有窮集合以及結點之間關系組成的集合構成的結構。

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

5.1.2

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

樹形表示法

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

結點的度：2.

樹的度：3.

葉結點：4.

分支結點:5.

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

根結點為第一層,若某結點在第i層,

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

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

樹的有序性:ABCDEABCDEFF6.

樹的深度:樹中結點所處的最大層次數.

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

樹的性質性質1

樹中結點個數等于所有結點的度數加1。性質2

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

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

滿k叉樹：結點個數等于(kh-1)/(k-1)的k叉樹。性質4

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

5.2.1

二叉樹的定義

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

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

(a)空二叉樹；

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

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

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

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

第48頁/共65頁

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

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

結論:具有三個結點的樹只有兩種形態。第49頁/共65頁兩種特殊形態的二叉樹

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

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

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

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

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

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

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

則n0=n2+1

證明:

設該二叉樹有n1個度為1的結點,結點總數為n,有

n=n0+n1+n2

--------(1)

設二叉樹的分支數目為B,有

B=n-1

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

B=n1+2n2

--------(3)聯列關系(1),(2)與(3),可得到

n0=n2+1證畢.4.

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

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

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

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

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

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

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

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

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

二叉樹的抽象數據類型

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

Operations：

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

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

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

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

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

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