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

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

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

3、3450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個(gè)指針front,rear,約定：Q.rear指示隊(duì)尾元素的下一個(gè)位置；Q.front指示隊(duì)頭元素初值Q.front=Q.rear=0空隊(duì)列條件：front=rear入隊(duì)列：sqrear+=x;出隊(duì)列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出隊(duì)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é)點(diǎn)先序遍歷左子樹先序遍歷右子樹 二叉樹的遍歷先序遍歷算法void PREORDER ( bitree *r) if ( r = = NULL ) return ; /空樹返回printf ( “ %c ”,r-data ) /先訪問當(dāng)前結(jié)點(diǎn)PREORDER( r-lchild ); /再訪問該結(jié)點(diǎn)的左子樹PREORDER( r-rchild ); /最后訪問該結(jié)點(diǎn)右子樹 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，簡(jiǎn)稱DFS）1.算法思路類似樹的先根遍歷。設(shè)初始時(shí)，

6、圖中各頂點(diǎn)均未被訪問，從圖中某頂點(diǎn)（設(shè)為V0）出發(fā)，訪問V0，然后搜索V0的一個(gè)鄰接點(diǎn)Vi，若Vi未被訪問，則訪問之，再搜索Vi的一個(gè)鄰接點(diǎn)（深度優(yōu)先）。若某頂點(diǎn)的鄰接點(diǎn)全部訪問完畢，則回溯（Backtracking）到它的上一頂點(diǎn)，然后再從此頂點(diǎn)又按深度優(yōu)先的方法搜索下去，直到能訪問的頂點(diǎn)都訪問完畢為止。 深度優(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)前圖中的頂點(diǎn)數(shù)）的初值為False（或0）；圖采用鄰接表表示法（或數(shù)組表示法）存儲(chǔ)。void DFS(int Gnn, int v) 對(duì)圖G從序號(hào)為v的頂點(diǎn)出發(fā)，按DFS方法搜索 int u; / int aN = 0; visit(G, v); 訪問v號(hào)頂點(diǎn) visitedv = True; 置標(biāo)志位為True或1 u = firstadj(G, v); 取v的第一鄰接點(diǎn)序號(hào)u while (u = 0) 當(dāng)u存在時(shí) if(visitedu = False) DFS(G,

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

9、后取相應(yīng)隊(duì)頭（出隊(duì)），考察訪問過的頂點(diǎn)的各鄰接點(diǎn)，將未訪問過的鄰接點(diǎn)訪問后再依次進(jìn)隊(duì)，直到隊(duì)空為止。 廣度優(yōu)先搜索算法對(duì)例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)對(duì)圖G從序號(hào)為v的頂點(diǎn)出發(fā)，按BFS遍歷 int u; qtype Q； Clearqueue(Q); 置隊(duì)Q為空 v

10、isit(G, v); visitedv = True; 訪問頂點(diǎn)、置標(biāo)志為“真” Enqueue(Q, v); v進(jìn)隊(duì) while( !Emptyqueue(Q) ) 隊(duì)非空時(shí) v = Delqueue(Q); 出隊(duì)，隊(duì)頭送v u = firstadj(G, v); 取v的第一鄰接點(diǎn)序號(hào) while (u = 0) if (visitedu = False) 若u未訪問，則訪問后進(jìn)隊(duì) visit(G, u); visitedu = True; Enqueue(Q, u); u = nextadj(G, v, u);取v關(guān)于u的下一鄰接點(diǎn) 訪問：隊(duì)列：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的路徑長度不會(huì)改變），并將路徑（0,2）賦給path5（即從v0到v5可能要經(jīng)過v2）。 再求第二條最短路徑長度（找滿足Sw=0且distw最小的），并改變各向量狀態(tài)。最后，從v0到各頂點(diǎn)的最短路徑存于向量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為圖中頂點(diǎn)數(shù) int end; pathtype;pathtype pathn; v到各頂點(diǎn)最短路徑向量int distn; v到各頂點(diǎn)最短路徑長度向量void Dijkstra(int Gnn, pathtype path, int dist, int v)/求G(用鄰接矩陣表示)中

13、源點(diǎn)v到其他各頂點(diǎn)最短路徑,n為G中頂點(diǎn)數(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，直到有個(gè)ki，使得k1ki，則k1有可能落在ki位置，將ki kj位置（原kj已送走），即key比基準(zhǔn)大的記錄向右移。反復(fù)逆序、正序比較，當(dāng)i=j時(shí)，i位置就是基準(zhǔn)k1的最終落腳點(diǎn)（因?yàn)楸然鶞?zhǔn)小的key統(tǒng)統(tǒng)在其“左部”，比基準(zhǔn)大的統(tǒng)統(tǒng)在其“右部”，作為基準(zhǔn)的key自然落在排序后的最終位置上），并且k1將原文件分成了兩部

14、分：對(duì)k和k”，套用上述排序過程(可遞歸)，直到每個(gè)子表只含有一項(xiàng)時(shí)，排序完畢。 kk”k1左部右部 快速排序例6 設(shè)記錄的key集合k=50，36，66，76，36，12，25，95，每次以集合中第一個(gè)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) 對(duì)子表(RlowRhigh)一趟快排算法 int i = low, j = high; keytype