数据结构 图的应用及其实现
实验六图的应用及其实现
（相关知识点：拓扑排序、关键路径、最小生成树和最短路径）
一、实验目的
1．进一步功固图常用的存储结构。
2．熟练掌握在图的邻接表实现图的基本操作。
3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。
二、实验内容
一>.基础题目：(本类题目属于验证性的，要求学生独立完成)
[题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。
测试数据：教材图7.28
[题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。
测试数据：教材图7.29
二>.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)）
【题目三】高速公路
描述
某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。
输入
输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。
输出
输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。
样例输入
1 2 100
2 3 100
1 3 50
2
1 3
2 3
样例输出
100
100
【题目四】最短的旅程
描述
在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland 的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。
一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。 Starhder ——就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。
输入
第一行包含两个整数，上文中的n和k，以一个空格隔开。（2<= n <=50000，1 <= k <=n），下面的n- 1行每行描述一条路，第i + 1行包含3个整数ai，bi，di，相邻两个数用一个空格隔开（1<= ai,bi <= n，1<= di <= 1000），ai 和bi是用道路直接相连的城市编号，di是这条道路的长度。第n + 1行包含一个整数j，是starhder要旅游的城市数（1<= j <= n - 1），接下来一行包含j个不同的整数m1，m2，……，mj，每两个相邻的整数用一个空格隔开，表示starhder想要去的城市。（1<= mt<=n，mt <> k）。
输出
输出只有一行，包含一个整数：starhder旅游的最短路程。
样例输入
4 2
1 2 1
4 2 2
2 3 3
2
样例输出
5
【题目五】连通 OR 不连通
描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作：
D x y 从原图中删除连接x，y节点的边。
Q x y 询问x，y节点是否连通
输入
第一行两个数n,m（5<=n<=40000,1<=m<=100000）
接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。
接下来一行一个整数 q（q<=100000）
以下q行每行一种操作，保证不会有非法删除。
输出
按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D
样例输入
3 3
1 2
1 3
2 3
5
Q 1 2
D 1 2
Q 1 2
D 3 2
Q 1 2
样例输出
C
C
D
【题目六】 Sort Problem
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
【Input】
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
【Output】
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined: y y y… y.
Sorted sequence cannot be determined.
Inconsistency found.
y y y… y is the sorted, ascending sequence.
Sample Input Sample Output
4 6 Sorted sequence determined: A B C D.
A
A B C B A 3 2 A B 26 2 A D 0 0 设计要求：（上述题目可任选一个） 1、上机前，认真学习教材，熟练掌握AOV网、AOE网的构造和拓扑排 序算法。 2、上机前，认真独立地写出本次程序清单，流程图，该程序包括图类 型以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和参考教材事例 图的存储结构定义 #define INFINITY INT_MAX //定义无穷大∞ #define MAX_VERTEX_NUM 20 typedef struct ArcNode // 表结点定义 { int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *nextarc; //链域，指示依附于vi的下一条边或弧的结点， }ArcNode typedef struct VNode //表头结点 { int vexdata; //存放顶点信息 struct ArcNode *firstarc; //指示第一个邻接点 }VNode，AdjList[MAX_VERTEX_NUM]; typedef struct { //图的结构定义 AdjList vertices; //顶点向量 int vexnum, arcnum; GraphKind kind; // 图的种类标志 } MGraph; Int indegree[MAX_VERTEX_NUM]； 相关函数声明： 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 其他相关函数 */ 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 （可用函数的调用关系图说明） ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单 （程序过长，可附主要部分） （注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注） 7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1) 实验五图的遍历及其应用实现 一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示： 输入示例 上图的顶点和边的信息输入数据为： 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]：在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]：寻求最佳旅游线路（ACM训练题） 在一个旅游交通网中，判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路，为节省费用，不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。 输入： 第一行：n //n-旅游城市个数 第2行：A B s1 s2 //s1,s2-金额数 第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用，输入0 0 0 表示结束。 输出： 第一行表示 A到B的旅游线路景点序列 第二行表示沿此线路，从A到B的旅游费用 设计要求： 1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结 构也可使用邻接矩阵等其他结构. 2、上机前，认真独立地写出本次程序清单，流程图。图的构造和遍历算法 分别参阅讲义和参考教材事例 图的存储结构定义参考教材 相关函数声明： 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 （可用函数的调用关系图说明） ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单 （程序过长，可附主要部分） 数据结构应用设计设计报告题目名称：___基于哈夫曼编码的文件压缩器_ 设计环境：____ __ＶＣ6.0 ____________ 指导教师：_____ _蔡茂蓉______________ 专业班级：______软件工程0601班__ ___ 姓名：__ _ __杨文辉_____________ 学号：___ ____ _____ 联系电话：_ _ 电子邮件： 设计日期：年月日至年月日 设计报告日期：年月日 1 ．题目................................................................................................... 错误!未定义书签。 2 ．需求分析........................................................................................... 错误!未定义书签。 2.1文件压缩过程：......................................................................... 错误!未定义书签。 2.2文件解压过程：......................................................................... 错误!未定义书签。 2.3压缩文件的存储结构设计图：................................................. 错误!未定义书签。 2.4ＨＡＦ文件示例：...................................................................... 错误!未定义书签。 3 ．详细设计........................................................................................... 错误!未定义书签。 3.1压缩流程图：............................................................................. 错误!未定义书签。 3.2解压流程图：............................................................................. 错误!未定义书签。 3.3节点类设计：............................................................................. 错误!未定义书签。 3.4编码和译码时的控制结构的实现............................................. 错误!未定义书签。 ４．调试分析........................................................................................... 错误!未定义书签。 6 ．测试结果........................................................................................... 错误!未定义书签。 6.1文件压缩..................................................................................... 错误!未定义书签。 6.2文件解压..................................................................................... 错误!未定义书签。 ７．实验总结........................................................................................... 错误!未定义书签。 8 ．参考文献........................................................................................... 错误!未定义书签。 1数据结构课程研究的主要内容包括（）（）（） 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析 （1）数据 （2）数据元素 （3）数据类型 （4）数据结构 （5）逻辑结构 （6）存储结构 （7）线性结构 （8）非线性结构 第二章作业 一、判断题(在你认为正确的题后的括号中打√，否则打X)。 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二、单项选择题。 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。 #include 数据结构课程设计图的应用个人报告 1979:Red and Black 第一、题目理解 有一个长方形的房间，覆盖平方米瓷砖。每一层的颜色或是红色或黑色。一名男子正站在一个黑色的瓷砖。从瓷砖，他可以转移到四个相邻瓷砖。但是他不能进入红色瓷砖，他只能移动黑砖。写程序的数量黑色瓦片，他可以达到通过重复上述动作。 题目要求只能走黑格子而不能走红格子，从其中一块黑格子开始求出可以到达的黑格子数。 第二、算法思想 用图的深度优先遍历可以解决问题，从开始的位置探索四个方向的格子，用递归直到走完所有黑格子。 建图结构，图的每一个顶点表示瓦片，如果两个相邻顶点都表示黑瓦，则在两个顶点间连线，表示可以从一片黑瓦移到另一片上；对建好的图从给定的起始点开始调用深度优先遍历算法，能访问几个顶点表示重复移动能达到的黑瓦的数目. 第三、如何实现 用一个二维数组来表示房间格子的分布。用变量count来记录可行黑格子的个数。用深度优先遍历算法来遍历整个二维数组。 search(int k,int t){ // Search函数,递归调用. if(k>=0 && k 1915: Knight Moves 第一、题目理解 题目要求要计算国际象棋中骑士从一个指定位置到目的位置的最少步数。因为每一次都有八种走法，要把可行的走法记录下来，直到走到终点为止。输出最少的步数。 第二、算法思想 此问题可利用广度优先遍历算法，用一个数组来记录可行的走法，然后再用另一个数组来记录数组中的每一种情况的可行走法，重复以上步骤，当终点出现在第n数组中则结束。数组的数量n就是最小的步数。 第三、如何实现 数据结构： typedef struct { //定义顶点的结构 int x, y; int direction; }VRType; typedef struct { int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int length; }MGraph; typedef VRType QElemType; //队列定义 #define MAXQSIZE 1000 typedef struct { QElemType *base; int front; int rear; }SqQueue; 实验六图的应用 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、掌握如何应用图解决各种实际问题。 二、实验内容 本次实验提供2个题目，学生可以任选一个！ 题目一：最小生成树问题 [问题描述] 若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 [基本要求] 1．利用克鲁斯卡尔算法求网的最小生成树。 2．要求输出各条边及它们的权值。 ［实现提示］ 通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。 图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。 ［测试数据］ 由学生依据软件工程的测试技术自己确定。 题目二：最短路径问题 [问题描述] 给定一个无向网，可以求得单源最短路径。 [基本要求] 以邻接矩阵为存储结构，用迪杰斯特拉算法求解从某一源点到其它顶点之间的最短路径及最短路径长度。 [测试数据] 由学生依据软件工程的测试技术自己确定。 题目三：拓扑排序问题 [问题描述] 给定一个有向图，判断其有无回路。 [基本要求] 以邻接表为存储结构，用拓扑排序算法判断其有无回路。[测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的各种应用的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 算法与数据结构课程设计 报告 系（院）：计算机科学学院 专业班级：计科11005 姓名：张林峰 学号： 201003784 指导教师：詹泽梅 设计时间：2012.6.11 - 2012.6.18 设计地点：12教机房 目录 一、课程设计目的 (2) 二、设计任务及要求 (2) 三、需求分析 (2) 四、总体设计 .............. 错误！未定义书签。 五、详细设计与实现[含代码和实现界面].. 8 六、课程设计小结 (15) 一．设计目的 1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力。二．设计任务及要求 根据《算法与数据结构》课程的结构体系，设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。比如，主界面是大项，主要是学过的各章的名字诸如线性表、栈与队列、串与数组及广义表等，子菜单这些章中的节或者子节。要求所有子菜单退出到他的父菜单。编程实现时，要用到C++的面向对象的功能。 三．需求分析 菜单运用极其广泛，应用于各行各业。菜单运用起来极其方便。随着社会的发展，社会的行业出现多样化，也就需要各式 实验六图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 二>.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)） 【题目三】高速公路 描述 某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。 输入 输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。 输出 输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。 样例输入 3 3 1 2 100 2 3 100 1 3 50 2 1 3 2 3 样例输出 100 100 【题目四】最短的旅程 描述 在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland 的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。Starhder ——就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。 输入 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现： 建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等） 五.心得体会 程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 编号：XH03JW024-05/0 实训（验）报告 班级：姓名：座号：指导教师：成绩： 课程名称：算法与数据结构实训（验）：实验六图的应用2011年12月9 日 一、实验目的： 1、掌握图的两种存储结构； 2、掌握图深度优先遍历的基本思想； 3、掌握图广度优先遍历的基本思想。 二、实训（验）内容、记录和结果（含数据、图表、计算、结果分析等） 1、程序源代码： // (以下为邻接表的队操作) void init1(linkqueue *q) { q->front=q->rear=(queue)malloc(sizeof(node)); q->front->next=NULL; } void ENQUEUE1(linkqueue *q, int v) { queue P; P=(queue)malloc(sizeof(node)); P->data=ga[v].vertex; P->next=NULL; q->rear->next=P; q->rear=P; } int DEQUEUE(linkqueue *q) { int k=0,u; queue P; P=q->front->next; while(ga[k].vertex!=P->data) k++; u=k; q->front->next=P->next; if(q->rear==P) q->rear=q->front; return u; } int isempty1(linkqueue *q) { if(q->front==q->rear) return 1; else return 0; } void CREATADJLIST(VerNode ga[]) /*建立无向图的邻接表*/ { int i,j,k; EdgeNode *s; getchar(); for(i=0;i #include typedef enum{DG,DN,UDG,UDN} GraphKind;//图的类型 bool visited[MAX_VERTEX_NUM]; //邻接矩阵 typedef struct ArcCell { VRType adj;//权值 InfoType *info; }ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图当前顶点数,弧数 GraphKind Kind; //图的类型 }MGraph; bool VexExist(MGraph G,VertexType v)//判断定点是否在图中{ 数据结构图的存储结构及基本操作 1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4.算法设计 #include }ArcNode; typedef struct VNode { char data[2]; //顶点就设置和书上V1等等一样吧 ArcNode *firstarc; }VNode,AdjList[MAX _VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_ NUM+10]; int front; int rear; }queue; int visited[MAX_VERTE X_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGrap h G, int (*Visit)(ALGraph 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 （一）、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上，着重拓扑排序算法的应用，做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 （二）、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明： typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 （三）、程序调试及运行结果分析 （四）、实验总结 在做本实验的过程中，拓扑排具体代码的实现起着很重要的作用，反复的调试和测试占据着实验大量的时间，每次对错误的修改都加深了对实验和具体算法的理解，自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单： 创建AOE网模块： int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i数据结构作业系统第七章答案
数据结构 图的基本操作实现
数据结构应用设计设计报告
数据结构作业电子版
数据结构图的建立和应用代码
数据结构图的应用报告
数据结构 图的应用
数据结构课程设计报告,含菜单
数据结构--图的应用及其实现
数据结构线性表的应用实验报告
数据结构实验图的基本操作
数据结构实验报告--图实验
算法与数据结构图的应用实验报告
数据结构中图的全部操作
数据结构图的存储结构及
数据结构实验六 图的应用及其实现
数据结构图实验报告