《2022年数据结构知识点 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构知识点 .pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、概念总结第一章概论1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的 逻辑结构、存储结构和运算2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系可以用一组数据 （结点集合K）以及这些数据之间的一组二元关系 （关系集合R）来表示：(K, R) 结点集 K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集 R是定义在集合K上的一组关系，其中每个关系r（rR）都是 KK上的二元关系3.数据类型a.基本数据类型整数类型 (integer)、 实数类型 (real)、 布尔类型 (boolean)、
2、字符类型（ char） 、 指针类型（pointer ）b.复合数据类型复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型4.数据结构的分类：线性结构（一对一）、树型结构（一对多） 、图结构（多对多）5.四种基本存储映射方法：顺序、链接、索引、散列6.算法的特性：通用性、有效性、确定性、有穷性7.算法分析： 目的 是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化8.渐进算法分析a大 分析法：上限，表明最坏情况b分析法：下限，表明最好情况c分析法：当上限和下限相同时，表明平均情况精选学习资料 - - - - -
3、 - - - - 名师归纳总结 - - - - - - -第 1 页，共 22 页第二章线性表1.线性结构的基本特征a.集合中必存在唯一的一个“第一元素 ”b.集合中必存在唯一的一个“最后元素 ”c.除最后元素之外，均有唯一的后继d.除第一元素之外，均有唯一的前驱2.线性结构的基本特点:均匀性、有序性3.顺序表a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （ 设每个元素需占用L个存储单元）c. 线性表的优缺点：优点：逻辑结构与存储结构一致；属于随机存
4、取方式，即查找每个元素所花时间基本一样缺点：空间难以扩充d.检索： ASL=【 （1）】e.插入：插入前检查是否满了，插入时插入处后的表需要复制【（n） 】f.删除：删除前检查是否是空的，删除时直接覆盖就行了【（n） 】4.链表4.1 单链表a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等b.带头结点的怎么判定空表：head 和 tail 指向单链表的头结点c.链表的插入（q-next=p-next; p-next=q; ） 【（n） 】d.链表的删除（ q=p-next; p-next = q-next; delete q; ） 【（n）
5、 】精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 22 页e.不足： next 仅指向后继，不能有效找到前驱4.2 双链表a.增加前驱指针，弥补单链表的不足b.带头结点的怎么判定空表:head 和 tail 指向单链表的头结点c.插入：（q-next = p-next; q-prev = p; p-next = q; q-next-prev = q; ）d.删除： （p-prev-next = p-next; p-next-prev = p-prev; p-prev = p-next = NULL; delete p; ）4.3 顺序
6、表和链表的比较4.3.1 主要优点a.顺序表的主要优点没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利b.链表的主要优点无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况4.3.2 应用场合的选择a.不宜使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素b.不宜使用链表的场合当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择第三章栈与队列1.栈a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈） ；删除：出栈（退栈） ；插入、删
7、除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种b.应用：1）数制转换精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 22 页while (N) N%8 入栈；N=N/8; while (栈非空 ) 出栈；输出； 2）括号匹配检验不匹配情况：各类括号数量不同；嵌套关系不正确算法：逐一处理表达式中的每个字符ch：ch=非括号：不做任何处理ch=左括号：入栈ch=右括号： if (栈空 ) return false else 出栈，检查匹配情况，if (不匹配 ) return false 如果结束后，栈非空，返
8、回false 3）表达式求值3.1 中缀表达式：计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除 /,后加 +、减-；相同优先级依据结合律，左结合律即为先左后右3.2 后缀表达式： := + | | 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 22 页 := * |/| := ? := | = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3 中缀表达式转换为后缀表达式InfixExp 为中缀表达式，PostfixExp 为后缀表达式初始化操作数栈OP，运算符栈OPND；OPND.push
9、(#); 读取 InfixExp 表达式的一项操作数：直接输出到PostfixExp 中；操作符：当 （ ：入 OPND; 当） ：OPND此时若空，则出错；OPND若非空，栈中元素依次弹出，输入PostfixExpz中，直到遇到 （为止；若为 （ ，弹出即可当四则运算符 ：循环（当栈非空且栈顶不是（ & 当前运算符优先级栈顶运算符优先级），反复弹出栈顶运算符并输入到PostfixExp 中，再将当前运算符压入栈3.4 后缀表达式求值初始化操作数栈OP；while （表达式没有处理完) item = 读取表达式一项; 操作数：入栈OP；运算符：退出两个操作数，计算，并将结果入栈 c.递归使用的
10、场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的2.队列a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列b.循环队列判断队满对空：重复精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 22 页队空： front=rear ；队满： (rear+1)%n=front 第五章二叉树1.概念a. 一个结点的子树的个数称为度数b.二叉树的 高度 定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的 深度 定义为二叉树中层数最大的叶结点的层数d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此
11、二叉树称作满二叉树e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树f.当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶组成扩充二叉树 ，扩充二叉树是满二叉树外部路径长度E：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和内部路径长度I：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和2.性质a. 二叉树的第i 层（根为第0 层， i0）最多有2i 个结点b. 深度为 k 的二叉树至多有2k+1-1 个结点c. 任何一颗二叉树，度为0 的结点比度为2 的结点多一个。n0 = n2 +
12、 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针 )数目等于其结点数加1 f. 有 n 个结点（ n0）的完全二叉树的高度为?log2(n+1)?，深度为 ?log2(n+1)?-g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有：1) 如果 i = 0 为根结点；如果i0，其父结点编号是(i-1)/2 2) 当 2i+1n， i 结点的左子结点是2i+1；否则 i 结点没有左子结点3) 当 2i+2n， i 结点的右子结点是2i+2；否则 i 结点没有右子结点精选学习资料 - - - - - - - - -
13、 名师归纳总结 - - - - - - -第 6 页，共 22 页3.周游（ 重点为由前序中序/中序后序求得二叉树）a.深度优先周游二叉树，可以有下列三种周游顺序：（实现：栈）1) 前序周游 (tLR次序 )：访问根结点；前序周游左子树；前序周游右子树2) 中序周游 (LtR次序 )：中序周游左子树；访问根结点；中序周游右子树3) 后序周游 (LRt次序 )：后序周游左子树；后序周游右子树；访问根结点b. 广度周游二叉树：从二叉树的顶层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问（实现：队列）4.存储链式存储结构，顺序存储结构（仅限完全二叉树：因为完全二叉树排
14、列紧凑）5.二叉搜索树（ BST ）a.判定：是一颗空树；或者是具有下列性质的二叉树：对于任何一个结点，设其值为K，则该结点的左子树 (若不空 )的所有结点的值都小于K；右子树 (若不空 )的所有结点的值都大于K；它的左右子树也分别为二叉搜索树b.性质：按照中序周游将各结点打印出来，得到的排列按照由小到大有序c.检索：从根结点开始，在二叉搜索树中检索值K 如果根结点储存的值为K，则检索结束如果 K小于根结点的值，则只需检索左子树如果 K大于根结点的值，则只检索右子树该过程一直持续到找到K或者遇上叶子结点如果遇上叶子结点仍没有发现K，则查找失败* 查找关键码：把查找时所经过的点一次写出精选学习资
15、料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 22 页d.插入 ：用待插入结点与树根比较，若待插入的关键值小于树根的关键值，就进入左子树， 否则进入右子树； 在子树中， 按照同样的方式沿检索路径直到叶结点，将新结点插入到二叉搜索树的叶子结点位置e.创建 ：从空的 BST开始，将关键码按BST定义一次插入f.删除 ：与插入相反， 删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性，删除过程分为如下情况：1）被删除的结点是叶子：直接将其删除即可2）被删除的结点只有左子树或只有右子树：直接将要删除的点删除后，将该
16、点的左（右）孩子和上面结点相连3）被删除结点有左、右子树：若p 有左右子树，则在左子树里找中序周游的最后一个结点r，将 r 的右指针置成指向p 的右子树的根，用结点p 的左子树的根去代替被删除的结点p 6.堆a.最小 /大堆定义：最小堆：是个关键码序列k0, k1 kn-1，具有如下特性(i=0,1,?n/2?-1) k i k 2i+1（左孩子）k i k 2i+2（右孩子）（即父 2 个孩子）类似可以定义最大堆k i k 2i+1 k i k 2i+2 （即父 2 个孩子）b.建“初堆”：按序列建立完全二叉树，从其中最后一个有孩子的结点开始按堆的定义调整c.插入 ：插入点追加到最后，自下而
17、上依次比较父与子，直到满足堆的定义d.删除 ：用最后结点替换被删结点，自上至下调整成堆e.移出最小 /大值：可以将堆中最后一个位置上的元素(数组中实际的最后一个元素)移到根的位置上，利用从左开始向下筛选对堆重新调整7.Huffman 树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 22 页a.概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径结点路径长度：从根结点到该结点的路径上分支的数目树的路径长度：树中每个结点的路径长度之和b.带权的路径长度树中所有叶子结点的带权路径长度之和=其中：权值：结点到根的路径长度c.编
18、码：左0 右 1 d.如何构建：选取序列中最小的相加生成树如此反复第六章树1.概念若N，则称 k 是 k的父结点， k是 k 的子结点若有序对 及 N， 则称 k和 k互为兄弟若有一条由k 到达 ks 的路径，则称 k 是 ks 的祖先， ks 是 k 的子孙2.树/森林与二叉树的相互转换a.树转换成二叉树加线 : 在树中所有兄弟结点之间加一连线抹线 : 对每个结点，除了其最左孩子外，去除其与其余孩子之间的连线旋转 : 以树的根结点为轴心，将整树顺时针转45b.二叉树转化成树加线： 若 p 结点是双亲结点的左孩子，则将 p 的右孩子， 右孩子的右孩子，沿分支找到的所有右孩子，都与p 的双亲用线
19、连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构c.森林转换成二叉树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 22 页将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构d.二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树3.周游a.先根 (次序 )周游若树不空，则先访问根结点，然后依次先根周游各棵子树b.后根 (次序 )周游若树
20、不空，则先依次后根周游各棵子树，然后访问根结点c.按层次周游若树不空，则自上而下自左至右访问树中每个结点4.存储结构“左子 /右兄”二叉链表表示法：结点左指针指向孩子，右结点指向右兄弟，按树结构存储，无孩子或无右兄弟则置空5. “UNION/FIND 算法” （等价类）判断两个结点是否在同一个集合中，查找一个给定结点的根结点的过程称为FIND 归并两个集合，这个归并过程常常被称为UNION “UNION/FIND”算法用一棵树代表一个集合，如果两个结点在同一棵树中，则认为它们在同一个集合中； 树中的每个结点（除根结点以外）有仅且有一个父结点；结点中仅需保存父指针信息，树本身可以存储为一个以其结
21、点为元素的数组6.树的顺序存储结构a. 带右链的先根次序表示法在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 22 页每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为: info 是结点的数据；rlink 是右指针，指向结点的下一个兄弟；ltag 是一个左标记，当结点没有子结点（即对应二叉树中结点没有左子结点时），ltag 为 1，否则为0 b. 带双标记位的先根次序表示法规定当结点没有下一个兄弟（即对应的二叉树中结点没有右子结点时）rtag
22、 为 1，否则为0 c. 带双标记位的层次次序表示法结点按层次次序顺序存储在一片连续的存储单元中第七章图1.定义a.假设图中有n 个顶点， e 条边：含有 e=n(n-1)/2 条边的无向图称作完全图含有 e=n(n-1) 条弧的有向图称作有向完全图若边或弧的个数e nlogn，则称作稀疏图，否则称作稠密图b. 顶点的度 (TD)=出度 (OD)+入度 (ID) 顶点的出度 : 以顶点 v 为弧尾的弧的数目顶点的入度 : 以顶点 v 为弧头的弧的数目c.连通图、连通分量若图 G 中任意两个顶点之间都有路径相通，则称此图为连通图若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量d.强连
23、通图、强连通分量对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图否则，其各个极大强连通子图称作它的强连通分量e.生成树、生成森林精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 22 页假设一个连通图有n 个顶点和e 条边， 其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树对非连通图，则将由各个连通分量构成的生成树集合称做此非连通图的生成森林2.存储结构a.相邻矩阵表示法表示顶点间相邻关系的矩阵若 G 是一个具有n 个顶点的图，则G 的相邻矩阵是如下定义的nn 矩阵：Ai,
24、j=1 ，若 (Vi, Vj)( 或)是图 G 的边Ai,j=0 ，若 (Vi, Vj)( 或)不是图 G 的边b.邻接表表示法为图中每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点Vi 的边（有向图中指以 Vi 为尾的弧）（建立单链表时按结点顺序建立）3.周游a. 深度优先周游：从图中某个顶点V0 出发，访问此顶点，然后依次从V0 的各个未被访问的邻接点出发，深度优先搜索遍历图中的其余顶点，直至图中所有与V0 有路径相通的顶点都被访问到为止b. 广度优先周游：从图中的某个顶点V0 出发， 并在访问此顶点之后依次访问V0 的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次
25、访问它们的邻接点，直至图中所有与V0 有路径相通的顶点都被访问到为止，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止4.拓扑排序拓扑排序的方法是：1）选择一个入度为0 的顶点且输出之2）从图中删掉此顶点及所有的出边3）回到第 1 步继续执行，直至图空或者图不空但找不到无前驱（入度为0）的顶点为止5.单源最短路径（Dijkstra 算法）6.每对顶点间的最短路径（Floyd 算法）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 22 页7.最小生成树a.Prim 算法b.
26、Kruskal 算法c.两种算法比较：Prim 算法适合稠密图，Kruskal算法适合稀疏图第八章内排序算法最大时间平均时间最小时间S( n)稳定性直接插入排序( n2)( n2)( n)(1)稳定冒泡排序( n2)( n2)( n)(1)稳定直接选择排序( n2)( n2)( n2)(1)不稳定Shel l排序( n3 3/ / 2 2)(n3 3/ / 2 2)(n3 3/ / 2 2)(1)不稳定快速排序( n2)( nl og n)( nl og n)( l og n)不稳定归并排序( nl og n)( nl og n)( nl og n)(n)稳定堆排序( nl og n)( nl
27、 og n)( nl og n)(1)不稳定桶式排序( n+m )( n+m )( n+m )( n+m )稳定基数排序(d( n+r ) )(d( n+r ) )(d( n+r ) )( n+r )稳定精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 22 页第十章检索1.平均检索长度（ASL ）是待检索记录集合中元素规模n 的函数，其定义为：ASL = Pi为检索第i 个元素的概率 ;Ci 为找到第i 个元素所需的比较次数2.散列a.除余法用关键码key 除以 M(取散列表长度 )，并取余数作为散列地址散列函数为： hash(key
28、) key mod M b.解决冲突的方法开散列方法：把发生冲突的关键码存储在散列表主表之外（在主表外拉出单链表）闭散列方法：把发生冲突的关键码存储在表中另一个位置上c.线性探查基本思想：如果记录的基位置存储位置被占用，就在表中下移，直到找到一个空存储位置；依次探查下述地址单元：d0+1， d0+2，.，m-1，0， 1，.， d0-1；用于简单线性探查的探查函数是 :p(K, i) = i d.散列表的检索1.假设给定的值为K，根据所设定的散列函数h，计算出散列地址h(K) 2. 如果表中该地址对应的空间未被占用，则检索失败，否则将该地址中的值与K比较3. 若相等则检索成功；否则，按建表时设
29、定的处理冲突方法查找探查序列的下一个地址，如此反复下去，直到某个地址空间未被占用（可以插入），或者关键码比较相等（有重复记录，不需插入）为止e.散列表的删除：删除后在删除地点应加上墓碑（被删除标记）f.散列表的插入：遇到墓碑不停止，知道找到真正的空位置第十一章索引技术1.概念：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 22 页a.主码：数据库中的每条记录的唯一标识b.辅码：数据库中可以出现重复值的码2.B 树a.定义： B树定义：一个m 阶 B树满足下列条件：(1) 每个结点至多有m 个子结点；(2) 除根和叶外其它每个结点至少
30、有?个子结点；(3) 根结点至少有两个子结点例外 (空树， or 独根 ) (4) 所有的叶在同一层,可以有?- 1 到 m-1 个关键码(5) 有 k 个子结点的非根结点恰好包含k-1 个关键码b.查找在根结点所包含的关键码K1， ， Kj中查找给定的关键码值(用顺序检索 (key少)/二分检索 (key多)；找到：则检索成功;否则，确定要查的关键码值是在某个Ki 和 Ki+1 之间，于是取pi 所指结点继续查找;如果 pi 指向外部结点，表示检索失败. c.插入找到的叶是插入位置，若插入后该叶中关键码个数m,插入完成； 否则分裂 ,中间为分界码 (插入到父结点 ),若父结点上溢则继续向上分
31、裂d.删除删除的关键码不在叶结点层：先把此关键码与它在B树里的后继对换位置，然后再删除该关键码 (叶中删 ) 删除的关键码在叶结点层：删除后关键码个数不小于?- 1直接删除关键码个数小于?- 1 ，如果兄弟结点关键码个数不等于?- 1从兄弟结点移若干个关键码到该结点中来(父结点中的一个关键码要做相应变化) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 22 页如果兄弟结点关键码个数等于?- 1合并3.B+树m 阶 B+树的结构定义如下：(1)每个结点至多有m 个子结点；(2)每个结点 (除根外 )至少有?个子结点；(3)根结点至少有
32、两个子结点；(4)叶在同一层，有?.m 个 key，叶包含全部key，B+树的叶结点链接成一个双链表(5)有 k 个子结点的结点必有k 个关键码。第十二章高级数据结构1.广义表a.广义表的结构特点: 1. 广义表中的数据元素有相对次序2. 广义表的长度定义为最外层包含元素个数3. 广义表的深度定义为所含括弧的重数:“原子”的深度为0 ;“空表”的深度为1 4. 广义表可以共享5. 广义表可以是一个递归的表：递归表的深度是无穷值，长度是有限值6. 任何一个非空广义表LS = (1, 2, , n)均可分解为 : 表头 Head( LS ) =1 和表尾Tail( LS )=( 2, , n)两部
33、分b.广义表的各种类型纯表 (pure list)： 从根结点到任何叶结点只有一条路径；也就是说任何一个元素（原子、子表）只能在广义表中出现一次可重入表 ( reentrant list ) ：图示对应于一个DAG；其元素 (包括原子和子表)可能会在表中多次出现，但不会出现回路循环表 ( cyclic list ，递归表 )：有向图中可能包含回路；循环表的深度为无穷大精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 22 页2.平衡的二叉搜索树（AVL）a.平衡因子用 bf(x)来表示结点x 的平衡因子，它被定义为：bf(x)=x 的右
34、子树的高度x 的左子树的高度b.AVL的插入：按BST建立，发现不满足AVL定义即调整，插入时出现的情况：1）LL/RR:中间元素成为双亲，左右各位孩子（满足BST定义）2）LR/RL:最后元素成为双亲，前两个为孩子（满足BST定义）附录：二叉树前序周游template void BinaryTree:PreOrderWithoutRecusion (BinaryTreeNode* root) using std:stack; / 使用 STL (Standard Template Library)中的 stack stackBinaryTreeNode* aStack; BinaryTree
35、Node* p=root; while(p) Visit(p-value( ); / 先访问当前结点if(p-rc !=NULL) aStack.push(p-rc( ); / 右子非空入栈if(p-lc !=NULL) p=p-lc( ); / 继续向左下周游else p = aStack.top( ); / 向左下至空：出栈aStack.pop( ); 二叉树中序周游template 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 22 页void BinaryTree:InOrderWithoutRecusion( Binary
36、TreeNode* root) using std:stack; / 使用 STL (Standard Template Library)中的 stack stackBinaryTreeNode* aStack; / 栈 aStack BinaryTreeNode* p = root; while( ! aStack.empty( ) | p) if(p) / 向左下走到底，不访问只入栈aStack.push( p); / 当前结点地址入栈p=p-leftchild( ); / 指向左孩子else p=aStack.top( ); / 取栈顶aStack.pop( ); / 出栈Visit(p
37、-value( ); / 访问当前结点p = p-rightchild( ); / 右跨一步 (指向右子 )重复 二叉树后序周游enum Tags Left, Right ; / 枚举类型标志位template class StackElement / 栈元素的类型定义public: BinaryTreeNode* pointer; / 指向二叉树结点的指针Tags tag; ; / 标志位template void BinaryTree:PostOrderWithoutRecusion (BinaryTreeNode* root) 精选学习资料 - - - - - - - - - 名师归纳总
38、结 - - - - - - -第 18 页，共 22 页using std:stack;/ 使用 STL栈部分StackElement element; stackStackElement aStack; / 栈声明BinaryTreeNode* p; if( root = NULL) return; / 空树即返回else p = root; while( !aStack.empty( ) | p ) / 进入左子树while( p !=NULL) element.pointer = p; / 准备栈元素element.tag = Left; / 标志置位aStack.push( eleme
39、nt); / 入栈p = p -leftchild(); / 沿左子树向下周游element=aStack.top( ); / 取栈顶元素aStack.pop(); / 出栈p=element.pointer; if ( element.tag = Left ) / 从左子树回来element.tag = Right; aStack.push( element ); p = p-rightchild( ); else Visit(p-value(); / 访问当前结点p = NULL; / 清空为了继续出栈 图的深度周游void DFS(Graph& G, int V) / 深度优先搜索算法实
40、现G.MarkV= VISITED; / 访问顶点V 并标记其标志位精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 22 页Visit(G, V); / 访问 V for(Edge e=G. FirstEdge(V);G.IsEdge(e);e=G. NextEdge(e) / 递归周游与V 邻接未访问过的顶点if ( G.MarkG. ToVertices(e)= UNVISITED) DFS(G, G. ToVertices(e); 图的广度周游void BFS(Graph& G, int V) using std:queue;
41、queue Q; / / 初始化队列G.MarkV= VISITED; Visit(G, V); / 先访问Q.push(V); / 再入队while(!Q.empty() / 如果队列仍然有元素 int V=Q.front( ); Q.pop( ); / 出队/ 将与该点相邻的每一个未访问点都访问完入队for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e) if(G.MarkG.ToVertex(e)= UNVISITED) G.MarkG.ToVertex(e)=VISITED; Visit(G, G.ToVertex(e); Q.pus
42、h(G.ToVertex(e); Floyd 算法void Floyd(Graph& G, Dist* &D) int i, j, v; /i,j,v 作为计数器D=new Dist*G.VerticesNum(); / 创建 D for(i=0; ;iG.VerticesNum();i+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 22 页Di=new DistG.VerticesNum(); for(i=0;iG.VerticesNum();i+) / 初始化 D 数组for(j=0;jG.VerticesNum();j+)
43、 if(i=j) Dij.length=0; Dij.pre=i; / 对角线 0 elseDij.length =INFINITY; Dij.pre=-1;/无路for(v=0;v(Div.length+Dvj.length for(v=0;vG.VerticesNum( );v+) for(i=0;iG.VerticesNum( );i+) for(j=0;j(Div.length+Dvj.length) Dij.length =Div.length+Dvj.length; Dij.pre=Dvj.pre; / 继承顶点v 的 pre Dijkstra 算法class Dist /D 数组
44、元素类 ,存最短路径信息public: int index; / 顶点索引值int length; / 与源 s的距离int pre; / 当前顶点在路径中前驱顶点void Dijkstra(Graph& G,int s, Dist* &D) /s 源D=new Dist G.VerticesNum( ) ;for(int i=0;iG.VerticesNum();i+)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 22 页G.Marki=UNVISITED; / 初始化 Mark 数组 D 数组Di.index = i; Di.l
45、ength= INFINITY; / Di.pre=s; / 初值为源点sDs.length=0; / 源点 s自身不参与选最短，清0MinHeap H(G.EdgesNum( ); / 最小堆用于选最小H.Insert( D s ); / 向堆中插入 D s 初始化for( i=0; i(Dv.length +G.Weight(e) DG.ToVertex(e).length=Dv.length+G.Weight(e);DG.ToVertex(e).pre=v; H.Insert( DG.ToVertex(e) ); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 22 页