实验7 无向图
一、问题描述
创建一个无向图,实现图的深度优先遍历和广度优先遍历等功能。
二、需求分析
1、简述程序的基本功能
本程序可以直接进行对图中元素的输入、输出、插入顶点、删除顶点、插入边、删除边、寻找邻接点以及深度优先遍历和广度优先遍历等功能。
2、输入的形式和输入值的范围
提供了一个功能选择界面,可以输入0~9进行功能的选择。
3、输出的形式
用户选择1选项时,程序会输出图的顶点数目和边的数目以及各条边顶点及权值;
用户选择2选项时,程序会提示输入创建图的顶点数和边数,然后逐个输入顶点,以及各条边;
用户选择3选项时,程序会提示输入顶点,然后输出该顶点的第一个邻接顶点;
用户选择4选项时,程序会提示输入顶点以及当前的邻接顶点,然后输出该顶点的下一个邻接顶点;
用户选择5选项时,程序会提示输入所要插入边的顶点以及权重;
用户选择6选项时,程序会提示输入所要插入的顶点;
用户选择7选项时,程序会提示输入所要删除的边的两个顶点;
用户选择8选项时,程序会提示输入所要删除的顶点
用户选择9选项时,程序提示输入遍历的起始顶点,然后输出深度遍历的结果;
用户选择0选项时,程序提示输入遍历的起始顶点,然后输出广度遍历的结果;
用户选择q选项时,程序结束。
4、测试数据要求
1)、选择选项时,不论输入几个字符,只读取第一个字符;
2)、选择选项时,输入的字符不能过多,若输入过多的字符就会出现异常;
3)、输入顶点时,每个元素只能是一个字符,输入多个字符会出错;
4)、在查找、插入、删除顶点或边时,会有容错提示;
5)、在查找和删除顶点或边时,若没有此元素,会给出提示;
三、概要设计
1、抽象数据类型
在该程序中,定义了一个类模板template class Graph,在该类中有*Vertices、**Edge、numEdges、numVertices 和maxVertices五个私有成员分别表示该类的顶点集、边集、现有边数、现有顶点数和顶点最大数目;自
己定义了构造函数Graph(int size)和析构函数~Graph(),还有对图进行输入、输出、查找邻接点、插入顶点或边、删除顶点或边以及两种遍历等操作的函数;并在主函数中对该类模板进行实例化。
2
四、详细设计(要求主要变量和语句加注释)
1、抽象数据类型的实现:
Graph.h文件的实现:
#include
#include"SeqQueue.h"
const int maxWeight=100;
template
class Graph
{
friend istream& operator>>(istream& in,Graph
friend ostream& operator<<(ostream& out,Graph
public:
Graph(int size);
~Graph();
bool IsEmpty()
{
if(numEdges==0)return true;
else return false;
}
bool IsFull()
{
if(numVertices==maxVertices*(maxVertices-1)/2)return true;
else return false;
}
int NumberOfVertices(){return numVertices;}
int NumberOfEdges(){return numEdges;}
T getValue(int i){return i>=0&&i<=numVertices?Vertices[i]:NULL;}
E getWeight(int v1,int v2){return v1!=-1&&v2!=-1?Edge[v1][v2]:0;}
int getFirstNeighbor(int v);
int getNextNeighbor(int v,int w);
bool insertVertex(T vertex);
bool insertEdges(int v1,int v2,E cost);
bool removeVertex(int v);
bool removeEdges(int v1,int v2);
int getVertexPos(T vertex)
{
for(int i=0;i if(Vertices[i]==vertex)return i; return -1; } private: T *Vertices; E **Edge; int maxVertices; int numEdges; int numVertices; }; template Graph { int i; maxVertices=size; numEdges=0; numVertices=0; Vertices=new T[maxVertices]; Edge=new E*[size]; for(i=0;i Edge[i]=new E[size]; for(i=0;i for(int j=0;j Edge[i][j]=(i==j)?0:maxWeight; } template Graph { delete []Vertices; for(int i=0;i delete[]Edge[i]; delete []Edge; } template int Graph { if(v!=-1) { for(int vol=0;vol if(Edge[v][vol]>0&&Edge[v][vol] return -1; } template int Graph { if(v!=-1&&w!=-1) { for(int vol=w+1;vol if(Edge[v][vol]>0&&Edge[v][vol] } return -1; } template bool Graph { if(numVertices==maxVertices){cout<<"空间已满,插入顶点失败!"< { for(int i=0;i if(Vertices[i]==vertex) {cout<<"已有此顶点,插入失败!"< } Vertices[numVertices++]=vertex;cout<<"插入成功!"< return true; } template bool Graph { int i; if(v<0||v>numVertices){cout<<"无此顶点,删除失败!"< if(numVertices==1){cout<<"仅剩一个顶点,不能删除!"< Vertices[v]=Vertices[numVertices-1]; for(i=0;i if(Edge[i][v]>0&&Edge[i][v] for(i=0;i Edge[i][v]=Edge[i][numVertices]; numVertices--; for(i=0;i Edge[v][i]=Edge[numVertices][i]; cout<<"删除顶点成功!"< return true; } template bool Graph { if(v1>-1&&v1 { Edge[v1][v2]=cost;Edge[v2][v1]=cost; numEdges++; cout<<"插入边成功!"< return true; } else {cout<<"顶点或权重出错,无法插入!"< } template bool Graph { if(v1>-1&&v1 Edge[v1][v2]=Edge[v2][v1]=maxWeight; numEdges--; cout<<"删除边成功!"< return true; } else {cout<<"顶点或权重出错,无法删除!"< } template istream& operator>>(istream& in,Graph { int i,j,k,m,n; T e1,e2; E weight; cout<<"输入顶点数和边数:"; in>>n>>m; for(i=0;i { cout<<"输入第"< in>>e1; G.insertVertex(e1); } i=0; while(i { cout<<"输入第"< in>>e1>>e2>>weight; j=G.getV ertexPos(e1); k=G.getVertexPos(e2); if(j==-1||k==-1) cout<<"边两端点信息有误,重新输入!"< else { G.insertEdges(j,k,weight); i++; } } return in; } template ostream& operator<<(ostream& out,Graph { int i,j,m,n; T e1,e2; E w; n=G.NumberOfVertices(); m=G.NumberOfEdges(); out< for(i=0;i for(j=i;j { w=G.getWeight(i,j); if(w>0&&w { e1=G.getValue(i); e2=G.getValue(j); out<<"("< } } return out; } template void DFS(Graph { int i,loc,n=G.NumberOfVertices(); bool *visited=new bool[n]; for(i=0;i visited[i]=false; loc=G.getVertexPos(v); DFS(G,loc,visited); delete[]visited; } template void DFS(Graph cout< visited[v]=true; int w=G.getFirstNeighbor(v); while(w!=-1) { if(visited[w]!=true) DFS(G,w,visited); w=G.getNextNeighbor(v,w); } } template void BFS(Graph { int i,w,loc,n=G.NumberOfVertices(); bool *visited=new bool[n]; for(i=0;i visited[i]=false; loc=G.getVertexPos(v); cout< visited[loc]=true; SeqQueue Q.EnQueue(loc); while(!Q.IsEmpty()) { Q.DeQueue(loc); w=G.getFirstNeighbor(loc); while(w!=-1) { if(visited[w]!=true) { cout< visited[w]=true; Q.EnQueue(w); } w=G.getNextNeighbor(loc,w); } } delete[]visited; } 2、现所用到的顺序表SeqQueue.h实现 #include template class SeqQueue { public: SeqQueue(int max); ~SeqQueue(){delete[]m_element;}; bool EnQueue(R x); bool DeQueue(R &x); bool IsEmpty(){return length==0?true:false;}; bool IsFull(){return length==maxsize?true:false;}; private: int length,maxsize,first; R *m_element; }; template SeqQueue { first=0; maxsize=max; length=0; m_element=new R[max]; } template bool SeqQueue { if(IsFull())return false; m_element[(first+length)%maxsize]=x; length++; return true; } template bool SeqQueue { if(IsEmpty())return false; x=m_element[first]; first=(first+1)%maxsize; length--; return true; } 3、主程序的实现 #include #include "Graph.h" void main() { char i[20]; bool flag=true; int num=20,cost=2,m,n; Graph char v,w,v1,v2; while(flag) { cout< cout<<"*********************************************************"< cout<<" 1 输出无向图 2 输入无向图"< cout<<" 3 顶点的第一个邻接顶点 4 顶点的下一个邻接顶点"< cout<<" 5 插入边 6 插入顶点"< cout<<" 7 删除边8 删除顶点"< cout<<" 9 深度遍历0 广度遍历"< cout<<" q 退出"< cout<<"*********************************************************"< cout<<"请输入选择: "; cin>>i; switch(i[0]) { case '1':cout< case '2':cin>>G1;break; case '3':cout<<"顶点: "; cin>>v; m=G1.getVertexPos(v); n=G1.getFirstNeighbor(m); if(n==-1)cout<<"该顶点无邻接顶点。"< else cout< case '4':cout<<"顶点: "; cin>>v; cout<<"当前邻接点:"; cin>>w; m=G1.getVertexPos(v); n=G1.getVertexPos(w); n=G1.getNextNeighbor(m,n); if(n==-1)cout<<"该顶点无下一个邻接顶点。"< else cout< case '5':cout<<"要插入的边及权值:"; cin>>v1>>v2>>cost; m=G1.getVertexPos(v1); n=G1.getVertexPos(v2); G1.insertEdges(m,n,cost);break; case '6':cout<<"要插入的顶点: "; cin>>v; G1.insertVertex(v);break; case '7':cout<<"要删除的边:";cin>>v1>>v2; m=G1.getVertexPos(v1);n=G1.getVertexPos(v2); G1.removeEdges(m,n);break; case '8':cout<<"要删除的节点:";cin>>v; m=G1.getVertexPos(v); G1.removeVertex(m);break; case '9':cout<<"输入遍历起始顶点:"; cin>>v; DFS(G1,v);break; case '0':cout<<"输入遍历起始顶点:"; cin>>v; BFS(G1,v);break; case 'q':flag=false;break; default:cout<<"输入有误!"< } } } 五、调试分析 1、设计与调试过程中遇到的问题及分析、体会 1)、刚刚编写完程序是,总是无法正常退出程序,我一直认为是摸一个功能函数出问题了。所以一直没有 找到问题,最后发现是内存空间泄露,析构函数中有两个语句顺序写反了,导致无法正常释放动态开辟的空间; 2)、无向图输出时,每一条边总是输出两次,在分析完后发现时重载输出运算符时,有一层循环的起始条 件弄错了; 3)、还有就是好几个功能函数总是无法正常运行,原来都是同一类错误:把边和边的编号弄混了,把顶点 和顶点的编号弄混了,导致参数调用错误,无法实现其功能。 4)、最后一个问题就是在删除顶点时,有些其他顶点的边找不到了,就怀疑是删除盖该顶点时,尾部顶点的各条边没有复制过来,导致输出时找不到那些边了,检查发现是因为在移动边时,输入了一个无效地址,导致这些边移动到了一个找不到的空间中,更改之后,一切顺利,程序终于完成了。 六、测试结果 列出几组输入和输出结果,输入集应多于需求分析的数据。 1)、打开程序,出现工作界面: 2)、然后输入功能选项,输入1时,开始时为空图 3)、输入2时,进行图的输入: 4)、再次输入1时,输出现有图: 5)、输入3时,可以查找第一个邻接点:6)、输入4时,查找下一个邻接点: 7)、输入5时,进行插入边,若边已存在或是顶点出错或是权重出错会提示错误: 8)、输入6时,进行插入顶点,若改顶点已存在,或空间已满,提示错误: 9)、输入7时,删除边,若无此边,则会提示出错: 10)、输入8时,删除顶点,若无此顶点,则提示出错: 11)、输入9时,进行深度遍历,输入0时进行广度遍历: 12)、输入q时,退出程序: 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、程序清单 (程序过长,可附主要部分) 数据结构应用设计设计报告题目名称:___基于哈夫曼编码的文件压缩器_ 设计环境:____ __VC6.0 ____________ 指导教师:_____ _蔡茂蓉______________ 专业班级:______软件工程0601班__ ___ 姓名:__ _ __杨文辉_____________ 学号:___ ____ _____ 联系电话:_ _ 电子邮件: 设计日期:年月日至年月日 设计报告日期:年月日 1 .题目................................................................................................... 错误!未定义书签。 2 .需求分析........................................................................................... 错误!未定义书签。 2.1文件压缩过程:......................................................................... 错误!未定义书签。 2.2文件解压过程:......................................................................... 错误!未定义书签。 2.3压缩文件的存储结构设计图:................................................. 错误!未定义书签。 2.4HAF文件示例:...................................................................... 错误!未定义书签。 3 .详细设计........................................................................................... 错误!未定义书签。 3.1压缩流程图:............................................................................. 错误!未定义书签。 3.2解压流程图:............................................................................. 错误!未定义书签。 3.3节点类设计:............................................................................. 错误!未定义书签。 3.4编码和译码时的控制结构的实现............................................. 错误!未定义书签。 4.调试分析........................................................................................... 错误!未定义书签。 6 .测试结果........................................................................................... 错误!未定义书签。 6.1文件压缩..................................................................................... 错误!未定义书签。 6.2文件解压..................................................................................... 错误!未定义书签。 7.实验总结........................................................................................... 错误!未定义书签。 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开始)。于是,他请你帮助计算一下,旅游完上述的城市最短需要多少路程。 输入 第4章 1.简述需求分析中现行系统调查、新系统逻辑方案的提出等活动的详细内容、关键问题、主要成果及其描述方法。 系统调查 (1)组织机构的调查 了解组织的机构状况。即各部门的划分及其相互关系、人员配备、业务分工、信息流和物流的关系等等。组织机构状况可以通过组织结构图来反映。所谓组织机构图就是把组织分成若干部分,同时标明行政隶属关系,信息流动关系和其他关系。 (2)业务处理状况调查 为了弄清楚各部门的信息处理工作,哪些与系统建设有关,哪些无关,就必须了解组织的业务流程。系统分析人员应按照业务活动中信息流动过程,逐个调查所有环节的处理业务、处理内容、处理顺序和对处理时间的要求,弄清楚各个环节需要的信息内容、信息来源、去向、处理方法、提供信息的时间和信息形态等。 (3)现行系统的目标、主要功能和用户需求调查 只有充分了解现行系统的目标和功能以及用户需求,才能发现存在的问题,寻找解决问题的途径,也使新系统开发成为可能。 (4)信息流程调查 开发信息系统必须了解信息流程。业务流程虽然在一定程度上表达了信息的流动和存储情况,但仍含有物资、材料等内容。为了用计算机对组织的信息进行控制,必须舍去其他内容,把信息的流动、加工、存储等过程流抽象出来,得出组织中信息流的综合情况。描述这种情况的就是数据流图。 (5)数据及功能分析 有了数据流图后,要对图中所出现的数据和信息的属性进一步分析,包括编制数据词典、数据存储情况分析及使用情况分析。同时还要对数据流图中的各个加工逻辑进行描述。可用的工具有决策树、决策表、结构化语言等。 (6)系统运营环境分析 目前我国许多企业组织的信息系统处于停滞状态的主要原因是系统对环境环境的适 应性而非技术问题。因此,必须对系统的应用环境进行认真地调查分析,充分考虑各种可能发生的变化,以提高系统开发的质量。 新系统逻辑方案的提出 (1) 现行系统的薄弱环节 (2) 新系统的总体功能需求 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师(签名)日期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 #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 1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求: ⑴能根据输入的顶点、边/弧的信息建立图; ⑵实现图中顶点、边/弧的插入、删除; ⑶实现对该图的深度优先遍历; ⑷实现对该图的广度优先遍历。 备注:单号基于邻接矩阵,双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构:图状结构 存储结构:顺序存储结构、链式存储结构 4.算法设计 #include int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_NUM+10]; int front; int rear; }queue; int visited[MAX_VERTEX_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v)); int PrintElement(ALGraph G,ArcNode v); void menu(); void depthfirstsearch(ALGraph *g,int vi); void travel(ALGraph *g); void breadfirstsearch(ALGraph *g); int i; G.arcnum = G.vexnum = 0; while(1) { menu(); do { printf ( "请输入要进行的操作\n" ); scanf ("%d",&i); if (i<1||i>6) printf("错误数字,请重新输入\n"); }while (i<1||i>6); switch (i) { case 1: CreateUDG(G); 附件2: 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 实验题目图及其应用实验时间 2011.5.10 一、实验目的、意义 (1)熟悉图的邻接矩阵(或邻接表)的表示方法; (2)掌握建立图的邻接矩阵(或邻接表)算法; (3)掌握图的基本运算,熟悉对图遍历算法; (4)加深对图的理解,逐步培养解决实际问题的编程能力 二、实验内容及要求 说明1:学生在上机实验时,需要自己设计出所涉及到的函数,同时设计多组输入数据并编写主程序分别调用这些函数,调试程序并对相应的输出作出分析;修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解。 具体要求: (1)建立图的邻接矩阵(或邻接表); (2)对其进行深度优先及广度优先遍历。 三、实验所涉及的知识点 1.创建一个图: CreateUDN(MGraph &G) 2.查找v顶点的第一个邻接点: FirstAdjVex(MGraph G,int v) 3. 查找基于v顶点的w邻接点的下一个邻接点: NextAdjVex(MGraph G,int v,int w) 4.图的矩阵输出: printArcs(MGraph G) 5:顶点定位: LocateVex(MGraph G,char v) 6. 访问顶点v输出: printAdjVex(MGraph G,int v) 7. 深度优先遍历: DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 8. 广度优先遍历BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v)) 9. DFS,从第v个顶点出发递归深度优先遍历图G: DFS(MGraph G,int v) 四、实验记录 1.对顶点的定位其数组下标,利用了找到之后用return立即返回,在当图顶点 多的情况下节省了搜索时间,程序如下 //对顶点v定位,返回该顶点在数组的下标索引,若找不到则返回-1 int LocateVex(MGraph G,char v){ for (int i=0;i数据结构作业系统第七章答案
数据结构 图的基本操作实现
数据结构应用设计设计报告
数据结构作业电子版
数据结构图的建立和应用代码
数据结构图的应用报告
数据结构 图的应用
数据结构课程设计报告,含菜单
数据结构--图的应用及其实现
数据流图的构成与绘制步骤
数据结构实验图的基本操作
数据结构实验报告--图实验
数据结构中图的全部操作
数据结构图的存储结构及
数据结构实验六 图的应用及其实现
数据结构图实验报告
数据结构图的存储结构及基本操作
数据结构图及其应用实验报告+代码