提交检查作业课件

提交检查作业2024/8/51网址：ftp:/10.2.210.170:22/登陆用户与密码：CL2007作业路径：地信06级=数据结构2008 地信07级=数据结构2008文件夹设置：个人文件夹命名：姓名-学号个人文件夹内的作业文件夹：用习题名称命名 例如：Huffman，环队提交内容：06级要求环队、迷宫、Huffman要求同时提交设计说明书，TXT或DOC格式，内容包括：问题说明，算法说明（伪代码），基本存储结构说明，算法基本状态逻辑分析。07级要求程序内加入清晰注释，说明函数功能、存储结构。2024/8/52练习1.对指定数据序列构建二叉排序树：6，3，8，9，7，2，4，1，5，2.对构建的排序二叉树写出：n先序遍历结果n后序遍历结果n中序遍历结果n画出后序遍历的线索二叉树 2024/8/53第七章 图n 图的定义n 基本术语n 图的存储n 图的遍历2024/8/54第七章 图 1.图的定义n 认识图的逻辑形式654132结点结点与结点之间的关系关系表现为“边”带有方向的边：有向边由结点和有向边构成的由结点和有向边构成的图，称为图，称为“有向图有向图”2024/8/55第七章 图 1.图的定义n 认识图的逻辑形式654132结点结点与结点之间的关系关系表现为“边”没有方向的边：无向边由结点和无向边构成的由结点和无向边构成的图，称为图，称为“无向图无向图”2024/8/56第七章 图 1.图的定义n G=V,E n V:非空顶点的集合（表示为V(G)）n E:建立在顶点集合V上的二元关系集合 即边的集合(表示为E(G)2024/8/57第七章 图 1.图的定义nE:建立在顶点集合V上的二元关系集合 即边的集合(表示为E(G)n 关系用“顶点对”表示n 无序对记为（v1,v2），表示无向图的边n 有序对记为，表示有向图的边2024/8/58第七章 图 1.图的定义无向图n G=V,E n V=v1,v2,v3,v4,v5,v6n E=(v1,v2),(v1,v5),(v2,v5),/无序对n (v3,v5),(v3,v6),(v4,v6),(v5,v6)v2v1v3v5v4v62024/8/59第七章 图 1.图的定义有向图n G=V,E n V=v1,v2,v3,v4,v5,v6n E=,/有序对n ,v2v1v3v5v4v62024/8/510第七章 图 2.图的基本术语n 端点端点:顶点顶点 vi vi 与与 vj vj 之间存在一条边之间存在一条边,vi vi、vjvj是边的两个端点。是边的两个端点。n n 邻接点邻接点:一条边的两端点互为邻接点。一条边的两端点互为邻接点。V=v1,v2,v3,v4,v5,v6E=(v1,v2),(v1,v5),(v2,v5),/无序对 (v3,v5),(v3,v6),(v4,v6),(v5,v6)2024/8/511第七章 图 2.图的基本术语n 入边与出边：有向图中，由顶点vi到vj的边，对于终点顶点vj该边为入边入边，对于起始顶点 该边为出边出边。v2v1v3v5v4v62024/8/512第七章 图 2.图的基本术语n 入度与出度：有向图中，顶点入边的总数，称为“入度”，顶点出边的总数称为“出度”。v2v1v3v5v4v6V5的入度为 3，出度为：12024/8/513第七章 图 2.图的基本术语n 顶点的度：无向图中，顶点k 的度是指与该顶点相连的边的总数。v2v1v3v5v4v6V5的入度为 3，出度为：12024/8/514第七章 图 2.图的基本术语n 完全图：n n个结点无向图，若具有n*(n-1)/2条边，在称为无向完全图。n n个结点有向图，若具有n*(n-1)条边，在称为有向完全图。n即任意两结点间都存在双向边2024/8/515第七章 图 2.图的基本术语n 稀疏图与稠密图：n n个结点无向图n边的总数en*log2n，称为稀疏图n边的总数较高的图，称为稀疏图2024/8/516第七章 图 2.图的基本术语n 路径：图中从顶点vi到vk的顶点序列。n v1 到 v6:v1，v2，v5，v6v2v1v3v5v4v62024/8/517第七章 图 2.图的基本术语n 路径：图中从顶点vi到vk的顶点序列。n v1 到 v6:v1v2v5v6v2v1v3v5v4v6（对有向图路径中的相邻结点存在：对有向图路径中的相邻结点存在：vi,vj属于图中关系集合属于图中关系集合E)E)2024/8/518第七章 图 2.图的基本术语n 路径：图中从顶点vi到vk的顶点序列。n v1 到 v6:v1v2v5v6（对无向图路径中的相邻结点存在对无向图路径中的相邻结点存在（vi,vjvi,vj）属于图中关系集合属于图中关系集合E)E)v2v1v3v5v4v6(v1,v2)(v2,v5)(v5,v6)2024/8/519第七章 图 2.图的基本术语n 简单路径：除路径的起点和终点外，所有结点均不重复的路径称为简单路径。v2v1v3v5v4v6(v1,v2)(v2,v5)(v5,v6)2024/8/520第七章 图 2.图的基本术语n 环路：路径的起点和终点为同一结点的路径。n 环路：V1,v2,v5,v3,v6,v5,v1v2v1v3v5v4v6(v1,v2)(v2,v5)(v5,v1)(v5,v3)(v3,v6)(v6,v5)2024/8/521第七章 图 2.图的基本术语n 简单环路：路径的起点和终点为同一结点的简单路径:v1,v2,v5,v1v2v1v3v5v4v6(v1,v2)(v2,v5)(v5,v1)2024/8/522第七章 图 2.图的基本术语n 连通图：无向图无向图中vi,vj之间存在路径，则称vi与vj连通，如果G图中任意两顶点连通，则称G为连通图。n图的最大连通分量：无向图中连通的子图称为图的连通分量。显然，在连通图中最大的连通分量是连通图本身。2024/8/523第七章 图 2.图的基本术语n强连通图：有向图有向图 G 图中若任意两顶点连通，则称G为强连通图。n最大强连通分量：有向图中，连通的子图称为图的强连通分量。其中最大的强连通分量是连通图本身。n网络：每条边带权的图，称为网络。2024/8/524基本概念n图的定义G=V，E n端点，边，邻接点n结点的入度与出度n稀疏图与稠密图n路径与路径的长度（简单路径、环路）n连通、强连通图与连通、强连通分量n边的权重与网络2024/8/525第七章 图 3.图的存储n 图的存储方法：1、图的顺序存储方式 基于数组的存储方式。2、图的链接存储方式 基于链表的存储方式。2024/8/526第七章 图 3.图的存储n 常用存储形式：1、图的邻接矩阵存储（顺序）2、图的邻接表存储（链接）3、图的边集数组存储（顺序）2024/8/527第七章 图 3-1.图的邻接矩阵存储n邻接矩阵存储讨论中，需要考虑：1.邻接矩阵的存储原则2.无向图的邻接矩阵3.有向图的邻接矩阵4.网络的邻接矩阵2024/8/528第七章 图 3-1.图的邻接矩阵存储n邻接矩阵的建立原则：设图：G=V,E a.由图中结点的数目决定矩阵的阶，若图G中含有n 个结点，则邻接矩阵为n*n阶 b.矩阵M中元素值的确定：1 存在（vi,vj）属于E M i j =0 vi,vj之间无边 2024/8/529第七章 图 3-1.图的邻接矩阵存储n注意：在无向图中，如果边集 E 中存在无序对 (Vi,Vj),则意味着：结点vi与vj之间存在一条边，同时，结点 Vj与Vi之间也存在一条边。这种性质如何体现在存储结构之中？2024/8/530第七章 图 3-1.图的邻接矩阵存储n 图的邻接矩阵存储方式实例v2v1v3v5v41234510 01 10 00 01 121 10 00 00 01 130 00 00 01 11 140 00 01 10 01 151 11 11 11 10 02024/8/531第七章 图 3-1.图的邻接矩阵存储n网络的邻接矩阵存储方式 邻接矩阵的建立原则：设网络：G=V,E a.由图中结点的数目决定矩阵的阶，若图G中含有n各结点，则邻接矩阵为n*n阶 b.矩阵M中元素值的确定：w（i,j）存在（vi,vj）属于E，M i j =且边的权重值为：w 0 vi,vj之间无边 2024/8/532第七章 图 3-1.图的邻接矩阵存储n 网络的邻接矩阵存储方式实例v2v1v3v5v41234510 05 50 00 08 825 50 00 00 0121230 00 00 015153 340 00 015150 05 558 812123 35 50 0512851532024/8/533第七章 图 3-1.图的临街矩阵存储n图的特征在邻接矩阵中的表现 a.无向连通图的邻接矩阵：对称 b.有向连通图的邻接矩阵：不一定对称 2024/8/534第七章 图 3-1.图的临街矩阵存储n 有向网络的邻接矩阵存储方式实例v2v1v3v5v41234510 05 50 00 00 020 00 00 00 0121230 00 00 015150 040 00 00 00 05 558 80 03 30 00 0512851532024/8/535第七章 图 3-1.图的临街矩阵存储n邻接矩阵存储结构的定义 typedef strusct vertex int adjvex；/结点的编号 vertextype data;/结点信息内容 VType；/结点数据类型 typedef struct graph /图的存储结构 int n,e;/结点总数与边总数 VType vexsMaxV;/结点信息 int edgesMaxVMaxV;adjMatix;2024/8/536第七章 图 3-2.图的邻接表存储n 图的邻接表存储原则n 无向图的邻接表n 有向图的邻接表 2024/8/537第七章 图 3-2.图的邻接表存储n图的邻接表存储原则 a.每个结点vi对应一个头结点 b.将所有与vi邻接的结点作为以vi为头的单链表。2024/8/538第七章 图 3-2.图的邻接表存储n图的邻接表存储方式v1v2v3v4v1v2v4v3v2v3v4 v1v3v1v2v4 v1v2无向图邻接表的逻辑结构v4 v3 2024/8/539第七章 图 3-2.图的邻接表存储n图的邻接表存储方式v1v2v3v4v1v2v4v3v2v3v4 v1v3v1v2v4 v1v2无向图邻接表的逻辑结构v4 v3 0123存储对应结点下标存储对应结点下标2024/8/540第七章 图 3-2.图的邻接表存储n有向图的邻接表v1v1v2v2v3v3v4v4v5v5有向图每个结点相关的边，分为两类：出边、入边我们需要用两个邻接表来描述一个图：出边邻接表 入边邻接表（逆表）2024/8/541第七章 图 3-2.图的邻接表存储n有向图出边邻接表v1v1v2v2v3v3v4v4v1v1v2v2v4v4v3v3v2v2v4v4 v3v3 v3v3v5v5 v5v5有向图出边邻接表的逻辑结构v5v5v2v2 2024/8/542第七章 图 3-2.图的邻接表存储n有向图入边邻接表v1v2v3v4v1v2v4v3v1v1v5有向图入边邻接表的逻辑结构v5v4v5v2v42024/8/543第七章 图 3-2.图的邻接表存储n完成有向图出、入边邻接表的逻辑图v1v2v3v4v1v2v4v3v5v52024/8/544第七章 图 3-3.边集数组存储方式n图的边集数组v1v2v3v4v525861012需要存储的信息：以边为单位 起始点，终止点，权重起始点，终止点，权重起始点，终止点，权重起始点，终止点，权重122145238436451252102024/8/545第七章 图 3-3.边集数组存储方式n有向图边集数组12513723122432583463520451512345571220638152024/8/546第七章 图 3.图的存储方式n图有3种常见的存储方式n不同的存储方式的使用，与问题及处理方式相关2024/8/547第七章 图 4.图的遍历n4.1、遍历的定义n遍历：从图的某一结点出发，按一定的方法 对图中所有的结点各进行一次访问的过程。n图遍历与树遍历的比较：图的遍历比较复杂，原因在于树中各个结点的前驱结点是唯一的。2024/8/548第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：在遍历中，优先选择结点的所有邻接点的遍历过程。n2、深度优先遍历：在遍历过程中，优先选择结点某一未遍历过的邻接点的遍历过程。2024/8/549第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1982345671234567892024/8/550第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 9按次序记录每个数据结点，直到该结点的所有邻接点被遍历完为止。2024/8/551第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 91 12 2 3 32024/8/552第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 94 42 2 3 35 52024/8/553第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 94 43 35 5 6 67 72024/8/554第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 94 4 5 5 6 67 72024/8/555第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 95 5 6 67 78 8 9 92024/8/556第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 96 67 78 8 9 92024/8/557第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 97 78 8 9 92024/8/558第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 898 8 9 92024/8/559第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 712 23 34 45 56 67 78 89 99 92024/8/560第七章 图 4.图的遍历n4.1、遍历的基本形式n1、广度优先遍历：1 19 98 82 23 34 45 56 67 71 12 23 34 45 56 67 78 89 9按先进先出的控制方式按先进先出的控制方式完成了广度优先的遍历完成了广度优先的遍历2024/8/561第七章 图 4.图的遍历n4.1、遍历的基本形式n2、深度优先遍历：1 19 98 82 23 34 45 56 67 71 12 25 58 89 94 43 36 67 72024/8/562图遍历的程序设计1.存储形式2.存储形式中数据的组织是遍历的基础3.不同存储形式可以形成不同的遍历结果4.遍历的基本指导思想是不变的5.广度优先：优先处理当前结点的所有邻接点，直到当前结点不存在尚未访问的节点为止6.深度优先：优先处理当前结点的下一级尚未访问的邻接点，直到当前结点无法再前进，则回溯，处理结点的下一级尚未访问的邻接点。2024/8/563第七章 图 图遍历部分实验题目n以图的遍历为基础，完成 农夫、狼、白菜、羊过河谜题的操作过程。n一个农夫带一只狼、一棵白菜和一只羊，处于河南岸，需要将所有的物品带到河北岸。只有一条小船，只有农夫能划船，小船一次只能承载农夫和一件物品。需要注意的是，如果农夫不在场，狼会吃掉羊、羊可能吃掉白菜。搜索可能的过河方案，安全而没有损失的将所有物品带到对岸。2024/8/564第七章 图 4.图的遍历n程序设计过程提示：n模拟过河的操作过程，将问题抽象为计算机表达方式。n操所对象：4位n对象的可能状态：两种状态，在南岸、在北岸n对象状态描述：以四位二进制位表示四个操作对象 每个对象只有两种状态0（南岸）和 1（北岸）2024/8/565第七章 图 4.图的遍历n以四位二进制位表示四个操作对象（次序为农夫、狼、白菜、羊）n每个对象只有两种状态0（南岸）和 1（北岸）n0000 四个对象都在南岸，1111 四个对象都在北岸n1001 农夫和羊在北岸，狼和白菜在南岸n理解与描述所有可能的合理状态，由所有的状态构成了问题的求解空间n确定所有可能的且合理的操作以及操作能够进行的前提条件，并完成操作函数，实现 状态的转换2024/8/566第七章 图 4.图的遍历n确定所有可能的合理的操作以及操作能够进行的前提条件，并完成操作函数，实现 状态的转换n设变量location 记录当前状态：location=0 在南岸n location=9（即1001）农夫和羊在北岸n 状态确认函数状态确认函数(确认右侧第二位的数据是否为1)n int cabbage(int location)return(0!=(location&0 x02);按位与运算16进制数据0000001 10运算对象的当前状态2024/8/567第七章 图 4.图的遍历n状态确认函数状态确认函数：n int cabbage(int location)return(0!=(location&0 x02);n 状态改变函数n 农夫状态必须改变，同时又一个物体的状态改变n 安全状态判定函数n 狼与羊处于同一状态，且农夫处于不同状态，不安全n 羊与菜处于同一状态，且农夫处于不同状态，不安全 2024/8/568第七章 图 4.图的遍历n 练习n 实验报告：总结归纳深度优先进行图 遍历的控制方式。说明使用的图的存储结构、辅助存储结 构以及基本控制方式，用伪代码说明算法