《提交检查作业》由会员分享，可在线阅读，更多相关《提交检查作业（68页珍藏版）》请在金锄头文库上搜索。
1、提交检查作业,2018/10/21,1,网址：ftp:/10.2.210.170:22/ 登陆用户与密码：CL2007 作业路径：地信06级=数据结构2008地信07级=数据结构2008 文件夹设置：个人文件夹命名：姓名-学号 个人文件夹内的作业文件夹：用习题名称命名例如：Huffman，环队 提交内容：06级要求环队、迷宫、Huffman要求同时提交设计说明书，TXT或DOC格式，内容包括：问题说明，算法说明（伪代码），基本存储结构说明，算法基本状态逻辑分析。 07级要求程序内加入清晰注释，说明函数功能、存储结构。,2018/10/21,2,练习,对指定数据序列构建二叉排序树：6，3，8，9
2、，7，2，4，1，5，对构建的排序二叉树写出： 先序遍历结果 后序遍历结果 中序遍历结果 画出后序遍历的线索二叉树,2018/10/21,3,第七章 图,图的定义基本术语图的存储图的遍历,2018/10/21,4,第七章 图 1. 图的定义,认识图的逻辑形式,6,5,4,1,3,2,结点 结点与结点之间的关系 关系表现为“边” 带有方向的边：有向边 由结点和有向边构成的 图，称为“有向图”,2018/10/21,5,第七章 图 1. 图的定义,认识图的逻辑形式,6,5,4,1,3,2,结点 结点与结点之间的关系 关系表现为“边” 没有方向的边：无向边 由结点和无向边构成的 图，称为“无向图”,
3、2018/10/21,6,第七章 图 1. 图的定义,G = V, E V: 非空顶点的集合（表示为V(G)）E: 建立在顶点集合V上的二元关系集合即边的集合 (表示为E(G),2018/10/21,7,第七章 图 1. 图的定义,E: 建立在顶点集合V上的二元关系集合即边的集合 (表示为E(G)关系用 “顶点对” 表示无序对记为（v1,v2），表示无向图的边有序对记为 ，表示有向图的边,2018/10/21,8,第七章 图 1. 图的定义无向图,G= V, E V=v1, v2, v3, v4, v5, v6E=(v1,v2),(v1,v5),(v2,v5), /无序对(v3,v5),(v3
4、,v6),(v4,v6),(v5,v6) ,v2,v1,v3,v5,v4,v6,2018/10/21,9,第七章 图 1. 图的定义有向图,G= V, E V=v1, v2, v3, v4, v5, v6E=, /有序对, ,v2,v1,v3,v5,v4,v6,2018/10/21,10,第七章 图 2. 图的基本术语,端点: 顶点 vi 与 vj 之间存在一条边, vi、vj是边的两个端点。邻接点: 一条边的两端点互为邻接点。,V=v1, v2, v3, v4, v5, v6 E=(v1,v2),(v1,v5),(v2,v5), /无序对(v3,v5),(v3,v6),(v4,v6),(v5
5、,v6) ,2018/10/21,11,第七章 图 2. 图的基本术语,入边与出边：有向图中，由顶点vi到vj的边，对于终点顶点vj该边为入边，对于起始顶点该边为出边。,v2,v1,v3,v5,v4,v6,2018/10/21,12,第七章 图 2. 图的基本术语,入度与出度：有向图中，顶点入边的总数，称为“入度”，顶点出边的总数称为“出度”。,v2,v1,v3,v5,v4,v6,V5的入度为 3，出度为：1,2018/10/21,13,第七章 图 2. 图的基本术语,顶点的度：无向图中，顶点k 的度是指与该顶点相连的边的总数。,v2,v1,v3,v5,v4,v6,V5的入度为 3，出度为：1
6、,2018/10/21,14,第七章 图 2. 图的基本术语,完全图：n个结点无向图，若具有n*(n-1)/2条边，在称为无向完全图。n个结点有向图，若具有n*(n-1)条边，在称为有向完全图。 即任意两结点间都存在双向边,2018/10/21,15,第七章 图 2. 图的基本术语,稀疏图与稠密图：n个结点无向图 边的总数en*log2n，称为稀疏图 边的总数较高的图，称为稀疏图,2018/10/21,16,第七章 图 2. 图的基本术语,路径：图中从顶点vi到vk的顶点序列。v1 到 v6: v1，v2，v5，v6,v2,v1,v3,v5,v4,v6,2018/10/21,17,第七章 图
7、2. 图的基本术语,路径：图中从顶点vi到vk的顶点序列。v1 到 v6: v1v2v5v6,v2,v1,v3,v5,v4,v6,（对有向图路径中的相邻结点存在：属于图中关系集合E),2018/10/21,18,第七章 图 2. 图的基本术语,路径：图中从顶点vi到vk的顶点序列。v1 到 v6: v1v2v5v6,（对无向图路径中的相邻结点存在（vi,vj）属于图中关系集合E),v2,v1,v3,v5,v4,v6,(v1,v2),(v2,v5),(v5,v6),2018/10/21,19,第七章 图 2. 图的基本术语,简单路径：除路径的起点和终点外，所有结点均不重复的路径称为简单路径。,v
8、2,v1,v3,v5,v4,v6,(v1,v2),(v2,v5),(v5,v6),2018/10/21,20,第七章 图 2. 图的基本术语,环路：路径的起点和终点为同一结点的路径。环路：V1, v2, v5, v3, v6, v5, v1,v2,v1,v3,v5,v4,v6,(v1,v2),(v2,v5),(v5,v1),(v5,v3),(v3,v6),(v6,v5),2018/10/21,21,第七章 图 2. 图的基本术语,简单环路：路径的起点和终点为同一结点的简单路径: v1,v2,v5,v1,v2,v1,v3,v5,v4,v6,(v1,v2),(v2,v5),(v5,v1),2018
9、/10/21,22,第七章 图 2. 图的基本术语,连通图：无向图中vi,vj之间存在路径，则称vi与vj连通，如果G图中任意两顶点连通，则称G为连通图。 图的最大连通分量：无向图中连通的子图称为图的连通分量。显然，在连通图中最大的连通分量是连通图本身。,2018/10/21,23,第七章 图 2. 图的基本术语,强连通图：有向图 G 图中若任意两顶点连通，则称G为强连通图。 最大强连通分量：有向图中，连通的子图称为图的强连通分量。其中最大的强连通分量是连通图本身。 网络：每条边带权的图，称为网络。,2018/10/21,24,基本概念,图的定义G= V，E 端点，边，邻接点 结点的入度与出度
10、 稀疏图与稠密图 路径与路径的长度（简单路径、环路） 连通、强连通图与连通、强连通分量 边的权重与网络,2018/10/21,25,第七章 图 3. 图的存储,图的存储方法：1、图的顺序存储方式基于数组的存储方式。2、图的链接存储方式基于链表的存储方式。,2018/10/21,26,第七章 图 3. 图的存储,常用存储形式：1、图的邻接矩阵存储（顺序）2、图的邻接表存储（链接）3、图的边集数组存储（顺序）,2018/10/21,27,第七章 图 3-1. 图的邻接矩阵存储,邻接矩阵存储讨论中，需要考虑： 邻接矩阵的存储原则 无向图的邻接矩阵 有向图的邻接矩阵 网络的邻接矩阵,2018/10/2
11、1,28,第七章 图 3-1. 图的邻接矩阵存储,邻接矩阵的建立原则：设图：G = V, E a. 由图中结点的数目决定矩阵的阶，若图G中含有n 个结点，则邻接矩阵为n*n阶b. 矩阵M中元素值的确定：1 存在（vi,vj）属于EM i j = 0 vi,vj之间无边,2018/10/21,29,第七章 图 3-1. 图的邻接矩阵存储,注意：在无向图中，如果边集 E 中存在无序对(Vi,Vj),则意味着：结点vi与vj之间存在一条边，同时，结点Vj与Vi之间也存在一条边。 这种性质如何体现在存储结构之中？,2018/10/21,30,第七章 图 3-1. 图的邻接矩阵存储,图的邻接矩阵存储方式
12、实例,v2,v1,v3,v5,v4,2018/10/21,31,第七章 图 3-1. 图的邻接矩阵存储,网络的邻接矩阵存储方式邻接矩阵的建立原则：设网络：G = V, E a.由图中结点的数目决定矩阵的阶，若图G中含有n各结点，则邻接矩阵为n*n阶b. 矩阵M中元素值的确定：w（i,j） 存在（vi,vj）属于E，M i j = 且边的权重值为：w0 vi,vj之间无边,2018/10/21,32,第七章 图 3-1. 图的邻接矩阵存储,网络的邻接矩阵存储方式实例,v2,v1,v3,v5,v4,5,12,8,5,15,3,2018/10/21,33,第七章 图 3-1. 图的临街矩阵存储,图的
13、特征在邻接矩阵中的表现a. 无向连通图的邻接矩阵：对称b. 有向连通图的邻接矩阵：不一定对称,2018/10/21,34,第七章 图 3-1. 图的临街矩阵存储,有向网络的邻接矩阵存储方式实例,v2,v1,v3,v5,v4,5,12,8,5,15,3,2018/10/21,35,第七章 图 3-1. 图的临街矩阵存储,邻接矩阵存储结构的定义typedef strusct vertex int adjvex； /结点的编号vertextype data; /结点信息内容 VType； /结点数据类型typedef struct graph /图的存储结构 int n,e; /结点总数与边总数VT
14、ype vexsMaxV; /结点信息int edgesMaxVMaxV; adjMatix;,2018/10/21,36,第七章 图 3-2. 图的邻接表存储,图的邻接表存储原则无向图的邻接表有向图的邻接表,2018/10/21,37,第七章 图 3-2. 图的邻接表存储,图的邻接表存储原则a. 每个结点vi对应一个头结点b. 将所有与vi邻接的结点作为以vi为头的单链表。,2018/10/21,38,第七章 图 3-2. 图的邻接表存储,图的邻接表存储方式,v1,v2,v4,v3,v4,v4,无向图邻接表的逻辑结构,v4,v3,2018/10/21,39,第七章 图 3-2. 图的邻接表存
15、储,图的邻接表存储方式,v1,v2,v4,v3,无向图邻接表的逻辑结构,0,1,2,3,存储对应结点下标,2018/10/21,40,第七章 图 3-2. 图的邻接表存储,有向图的邻接表,有向图 每个结点相关的边， 分为两类：出边、入边 我们需要用两个邻接表 来描述一个图：出边邻接表入边邻接表（逆表）,2018/10/21,41,第七章 图 3-2. 图的邻接表存储,有向图出边邻接表,v1,v2,v3,v4,v1,v2,v4,v3,v4,v3,v5,v5,有向图 出边邻接表的逻辑结构,v5,v2,2018/10/21,42,第七章 图 3-2. 图的邻接表存储,有向图入边邻接表,v1,v2,v3,v4,v1,v2,v4,v3,v1,v5,有向图 入边邻接表的逻辑结构,
