4书和笔记数据结构学生演示

1、第1节 数据结构概述 栈和队列 栈的应用举例 栈在表达式计算过程中的应用 ：建立操作数栈和运算符栈。运算符有优先级。规则： 自左至右扫描表达式，凡是遇到操作数一律进操作数栈。当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。左括号一律进运算符栈，右括号一律不进运算符栈，取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算，并将结果压入操作数栈，直到取出左括号为止。 自左至右扫描表达式，凡是遇到操作数一律进操作数栈。当遇到运算符时，如果它的优先级比运算符栈栈

2、顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。左括号一律进运算符栈，右括号一律不进运算符栈，取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算，并将结果压入操作数栈，直到取出左括号为止例如 ：计算 ( 48 )23 ;操作数栈 ：4 8 | 12 2|24 3|21运算符栈 ：( |操作数栈运算符栈( 48 )2348 )23(8 )2348 )23)238234+8=12122332312X2=2424324-3=21 栈和队列循环队列Q.front=0Q.rear=0123450队空12

3、3450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针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 二叉树的遍历先序遍历算法若二叉树为空树，则空操作；否则访问根结点先序遍历左子树先序遍历右子树 二叉树的遍历先序遍历算法void PREORDER ( bitree *r) if ( r = = NULL ) return ; /空树返回printf ( “ %c ”,r-data ) /先访问当前结点PREORDER( r-lchild ); /再访问该结点的左子树PREORDER( r-rchild ); /最后访问该结点右子树 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二叉树的遍历 深度优先搜索算法深度优先搜索（Depth First Search，简称DFS）1.算法思路类似树的先根遍历。设初始时，

6、图中各顶点均未被访问，从图中某顶点（设为V0）出发，访问V0，然后搜索V0的一个邻接点Vi，若Vi未被访问，则访问之，再搜索Vi的一个邻接点（深度优先）。若某顶点的邻接点全部访问完毕，则回溯（Backtracking）到它的上一顶点，然后再从此顶点又按深度优先的方法搜索下去，直到能访问的顶点都访问完毕为止。 深度优先搜索算法例5-9 设有一无向图G10，其DFS搜索过程如图5.20所示。 514426V53V720V6V2V0V1V3V4V5V8V2V6V71V40V3V1V8V0图5. 20由遍历过程产生的“生成树”DFS：V0 V1 V3 V4 V5 V8 V2 V6 V7V0V1V2V3

7、V4V6V7V8V5000000000111111111 深度优先搜索算法2.算法描述 设标志数组Visitedn（n为当前图中的顶点数）的初值为False（或0）；图采用邻接表表示法（或数组表示法）存储。void DFS(int Gnn, int v) 对图G从序号为v的顶点出发，按DFS方法搜索 int u; / int aN = 0; visit(G, v); 访问v号顶点 visitedv = True; 置标志位为True或1 u = firstadj(G, v); 取v的第一邻接点序号u while (u = 0) 当u存在时 if(visitedu = False) DFS(G,

8、 u);若u未访问,调用函数遍历从u 出发的子图 u = nextadj(G, v, u); 取v关于当前u的下一邻接点序号 uvDFS(G,u)uDFS(G,u)u=-1( 结束） 广度优先搜索算法广度优先搜索（Breadth First Search），简称BFS。 1.算法思路 类似树的按层次遍历。初始时，图中各顶点均未被访问，从图中某顶点（设V0）出发，访问V0，并依次访问V0的各邻接点（广度优先）。然后，分别从这些被访问过的顶点出发，仍按照广度优先的策略搜索其它顶点，直到能访问的顶点都访问完毕为止。 为控制广度优先的正确搜索，要用到队列技术，即访问完一个顶点后，让该顶点的序号进队。然

9、后取相应队头（出队），考察访问过的顶点的各邻接点，将未访问过的邻接点访问后再依次进队，直到队空为止。 广度优先搜索算法对例5-9中G10，从V0出发，按BFS方法搜索的过程及生成树如图5.21所示。 V0V1V2V3V4V6V7V8V500000000011111111427264V835V6V701V4V3V50V2V1V011图5. 21BFS：V0 V1 V2 V3 V5 V6 V7 V4 V8 广度优先搜索算法2.算法描述void BFS(int Gnn, int v)对图G从序号为v的顶点出发，按BFS遍历 int u; qtype Q； Clearqueue(Q); 置队Q为空 v

10、isit(G, v); visitedv = True; 访问顶点、置标志为“真” 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关于u的下一邻接点 访问：队列：AAGGBBEECCDDFFACDBFGE

11、例： Dijkstra算法各向量的状态： 从dist中看出，第一条最短路径长度为dist2=15，最短路径为(v0,v2)。V2求出后，修改各向量状态：原来v0到v5的路径长度dist5=，v2求出后，现v0经过v2到v5的路径长度为25，所以令： dist5=dist2+上的权=25（而v0到v1、v3、v4的路径长度不会改变），并将路径（0,2）赋给path5（即从v0到v5可能要经过v2）。 再求第二条最短路径长度（找满足Sw=0且distw最小的），并改变各向量状态。最后，从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为图中顶点数 int end; pathtype;pathtype pathn; v到各顶点最短路径向量int distn; v到各顶点最短路径长度向量void Dijkstra(int Gnn, pathtype path, int dist, int v)/求G(用邻接矩阵表示)中

13、源点v到其他各顶点最短路径,n为G中顶点数/ int i, count, sn, m, u, w; for (i=0; ikj，则k1有可能落在kj位置，将kjk1位置，即key比基准（k1）小的记录向左移。（2）正序比较：k1k2，若k1k2，则k1不可能在k2位置，k1k3，直到有个ki，使得k1ki，则k1有可能落在ki位置，将ki kj位置（原kj已送走），即key比基准大的记录向右移。反复逆序、正序比较，当i=j时，i位置就是基准k1的最终落脚点（因为比基准小的key统统在其“左部”，比基准大的统统在其“右部”，作为基准的key自然落在排序后的最终位置上），并且k1将原文件分成了两部

14、分：对k和k”，套用上述排序过程(可递归)，直到每个子表只含有一项时，排序完毕。 kk”k1左部右部 快速排序例6 设记录的key集合k=50，36，66，76，36，12，25，95，每次以集合中第一个key为基准的快速排序过程如下： k= 50 36 66 76 36 12 25 95 X(基准)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; 当前子表的上下界 stacktype;int qkpass(sqfile F, int low, int high) 对子表(RlowRhigh)一趟快排算法 int i = low, j = high; keytype