4書和筆記數(shù)據(jù)結(jié)構(gòu)學(xué)生演示

1、第1節(jié) 數(shù)據(jù)結(jié)構(gòu)概述 棧和隊列 棧的應(yīng)用舉例 棧在表達式計算過程中的應(yīng)用 ：建立操作數(shù)棧和運算符棧。運算符有優(yōu)先級。規(guī)則： 自左至右掃描表達式，凡是遇到操作數(shù)一律進操作數(shù)棧。當(dāng)遇到運算符時，如果它的優(yōu)先級比運算符棧棧頂元素的優(yōu)先級高就進棧。反之，取出棧頂運算符和操作數(shù)棧棧頂?shù)倪B續(xù)兩個操作數(shù)進行運算，并將結(jié)果存入操作數(shù)棧，然后繼續(xù)比較該運算符與棧頂運算符的優(yōu)先級。左括號一律進運算符棧，右括號一律不進運算符棧，取出運算符棧頂運算符和操作數(shù)棧頂?shù)膬蓚€操作數(shù)進行運算，并將結(jié)果壓入操作數(shù)棧，直到取出左括號為止。 自左至右掃描表達式，凡是遇到操作數(shù)一律進操作數(shù)棧。當(dāng)遇到運算符時，如果它的優(yōu)先級比運算符棧棧

2、頂元素的優(yōu)先級高就進棧。反之，取出棧頂運算符和操作數(shù)棧棧頂?shù)倪B續(xù)兩個操作數(shù)進行運算，并將結(jié)果存入操作數(shù)棧，然后繼續(xù)比較該運算符與棧頂運算符的優(yōu)先級。左括號一律進運算符棧，右括號一律不進運算符棧，取出運算符棧頂運算符和操作數(shù)棧頂?shù)膬蓚€操作數(shù)進行運算，并將結(jié)果壓入操作數(shù)棧，直到取出左括號為止例如 ：計算 ( 48 )23 ;操作數(shù)棧 ：4 8 | 12 2|24 3|21運算符棧 ：( |操作數(shù)棧運算符棧( 48 )2348 )23(8 )2348 )23)238234+8=12122332312X2=2424324-3=21 棧和隊列循環(huán)隊列Q.front=0Q.rear=0123450隊空12

3、3450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針front,rear,約定：Q.rear指示隊尾元素的下一個位置；Q.front指示隊頭元素初值Q.front=Q.rear=0空隊列條件：front=rear入隊列：sqrear+=x;出隊列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront ABCDEFGHK例如：先序序列：中序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K

4、G F E A 二叉樹的遍歷先序遍歷算法若二叉樹為空樹，則空操作；否則訪問根結(jié)點先序遍歷左子樹先序遍歷右子樹 二叉樹的遍歷先序遍歷算法void PREORDER ( bitree *r) if ( r = = NULL ) return ; /空樹返回printf ( “ %c ”,r-data ) /先訪問當(dāng)前結(jié)點PREORDER( r-lchild ); /再訪問該結(jié)點的左子樹PREORDER( r-rchild ); /最后訪問該結(jié)點右子樹 PREORDER ( bitree *r) if ( r = = NULL ) return ; printf ( %c ,r-data ); PR

5、EORDER ( r-lchild ); PREORDER ( r-rchild ); 主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C二叉樹的遍歷 深度優(yōu)先搜索算法深度優(yōu)先搜索（Depth First Search，簡稱DFS）1.算法思路類似樹的先根遍歷。設(shè)初始時，

6、圖中各頂點均未被訪問，從圖中某頂點（設(shè)為V0）出發(fā)，訪問V0，然后搜索V0的一個鄰接點Vi，若Vi未被訪問，則訪問之，再搜索Vi的一個鄰接點（深度優(yōu)先）。若某頂點的鄰接點全部訪問完畢，則回溯（Backtracking）到它的上一頂點，然后再從此頂點又按深度優(yōu)先的方法搜索下去，直到能訪問的頂點都訪問完畢為止。 深度優(yōu)先搜索算法例5-9 設(shè)有一無向圖G10，其DFS搜索過程如圖5.20所示。 514426V53V720V6V2V0V1V3V4V5V8V2V6V71V40V3V1V8V0圖5. 20由遍歷過程產(chǎn)生的“生成樹”DFS：V0 V1 V3 V4 V5 V8 V2 V6 V7V0V1V2V3

7、V4V6V7V8V5000000000111111111 深度優(yōu)先搜索算法2.算法描述 設(shè)標(biāo)志數(shù)組Visitedn（n為當(dāng)前圖中的頂點數(shù)）的初值為False（或0）；圖采用鄰接表表示法（或數(shù)組表示法）存儲。void DFS(int Gnn, int v) 對圖G從序號為v的頂點出發(fā)，按DFS方法搜索 int u; / int aN = 0; visit(G, v); 訪問v號頂點 visitedv = True; 置標(biāo)志位為True或1 u = firstadj(G, v); 取v的第一鄰接點序號u while (u = 0) 當(dāng)u存在時 if(visitedu = False) DFS(G,

8、 u);若u未訪問,調(diào)用函數(shù)遍歷從u 出發(fā)的子圖 u = nextadj(G, v, u); 取v關(guān)于當(dāng)前u的下一鄰接點序號 uvDFS(G,u)uDFS(G,u)u=-1( 結(jié)束） 廣度優(yōu)先搜索算法廣度優(yōu)先搜索（Breadth First Search），簡稱BFS。 1.算法思路 類似樹的按層次遍歷。初始時，圖中各頂點均未被訪問，從圖中某頂點（設(shè)V0）出發(fā)，訪問V0，并依次訪問V0的各鄰接點（廣度優(yōu)先）。然后，分別從這些被訪問過的頂點出發(fā)，仍按照廣度優(yōu)先的策略搜索其它頂點，直到能訪問的頂點都訪問完畢為止。 為控制廣度優(yōu)先的正確搜索，要用到隊列技術(shù)，即訪問完一個頂點后，讓該頂點的序號進隊。然

9、后取相應(yīng)隊頭（出隊），考察訪問過的頂點的各鄰接點，將未訪問過的鄰接點訪問后再依次進隊，直到隊空為止。 廣度優(yōu)先搜索算法對例5-9中G10，從V0出發(fā)，按BFS方法搜索的過程及生成樹如圖5.21所示。 V0V1V2V3V4V6V7V8V500000000011111111427264V835V6V701V4V3V50V2V1V011圖5. 21BFS：V0 V1 V2 V3 V5 V6 V7 V4 V8 廣度優(yōu)先搜索算法2.算法描述void BFS(int Gnn, int v)對圖G從序號為v的頂點出發(fā)，按BFS遍歷 int u; qtype Q； Clearqueue(Q); 置隊Q為空 v

10、isit(G, v); visitedv = True; 訪問頂點、置標(biāo)志為“真” Enqueue(Q, v); v進隊 while( !Emptyqueue(Q) ) 隊非空時 v = Delqueue(Q); 出隊，隊頭送v u = firstadj(G, v); 取v的第一鄰接點序號 while (u = 0) if (visitedu = False) 若u未訪問，則訪問后進隊 visit(G, u); visitedu = True; Enqueue(Q, u); u = nextadj(G, v, u);取v關(guān)于u的下一鄰接點 訪問：隊列：AAGGBBEECCDDFFACDBFGE

11、例： Dijkstra算法各向量的狀態(tài)： 從dist中看出，第一條最短路徑長度為dist2=15，最短路徑為(v0,v2)。V2求出后，修改各向量狀態(tài)：原來v0到v5的路徑長度dist5=，v2求出后，現(xiàn)v0經(jīng)過v2到v5的路徑長度為25，所以令： dist5=dist2+上的權(quán)=25（而v0到v1、v3、v4的路徑長度不會改變），并將路徑（0,2）賦給path5（即從v0到v5可能要經(jīng)過v2）。 再求第二條最短路徑長度（找滿足Sw=0且distw最小的），并改變各向量狀態(tài)。最后，從v0到各頂點的最短路徑存于向量path中，最短路徑長度存于dist中。0 12345V4V5V2V3V01015

12、202V11510441030S100000dist02015 path00000015V20,22520V10,20,1300,11110,2,5V5290,2,50,2,5,31V310,1,4V4 Dijkstra算法2.算法描述typedef struct int pin; 存放v到vi的一條最短路徑，n為圖中頂點數(shù) int end; pathtype;pathtype pathn; v到各頂點最短路徑向量int distn; v到各頂點最短路徑長度向量void Dijkstra(int Gnn, pathtype path, int dist, int v)/求G(用鄰接矩陣表示)中

13、源點v到其他各頂點最短路徑,n為G中頂點數(shù)/ int i, count, sn, m, u, w; for (i=0; ikj，則k1有可能落在kj位置，將kjk1位置，即key比基準(zhǔn)（k1）小的記錄向左移。（2）正序比較：k1k2，若k1k2，則k1不可能在k2位置，k1k3，直到有個ki，使得k1ki，則k1有可能落在ki位置，將ki kj位置（原kj已送走），即key比基準(zhǔn)大的記錄向右移。反復(fù)逆序、正序比較，當(dāng)i=j時，i位置就是基準(zhǔn)k1的最終落腳點（因為比基準(zhǔn)小的key統(tǒng)統(tǒng)在其“左部”，比基準(zhǔn)大的統(tǒng)統(tǒng)在其“右部”，作為基準(zhǔn)的key自然落在排序后的最終位置上），并且k1將原文件分成了兩部

14、分：對k和k”，套用上述排序過程(可遞歸)，直到每個子表只含有一項時，排序完畢。 kk”k1左部右部 快速排序例6 設(shè)記錄的key集合k=50，36，66，76，36，12，25，95，每次以集合中第一個key為基準(zhǔn)的快速排序過程如下： k= 50 36 66 76 36 12 25 95 X(基準(zhǔn))ijj25ii66j12i76j36i 25 36 12 36 50 76 66 95 iXjj12i36j 12 25 36 36 jiXj36 36 ijXj66i 66 76 95 排序完畢 快速排序算法描述typedef struct 棧元素類型 int low, high; 當(dāng)前子表的上下界 stacktype;int qkpass(sqfile F, int low, int high) 對子表(RlowRhigh)一趟快排算法 int i = low, j = high; keytype