数据结构实验报告图的遍历

第三组实验报告数据结构试验报告实验4图的记忆与应用实验主题：图的扫描问题专业班：计科系1405班组长：张纪远()船员：周振军()朱新祥梁丽蓉()段慧娟2016年6月1日实验报告实验类型_综合设计_实验室_软件实验室3_一、实验主题图的记忆与应用二、实验的目的和要求1 .把握图的记忆思想及其记忆实现2 .把握图的深度、广度，优先实现算法思想及其程序3 .掌握图的一般应用算法思想及其程序实现三、需求分析1 .问题的说明使用菜单实现图的关联算法，例如用键盘输入太原、成都、北京、上海、天津、大连、河北，生成具有定向图或无向图(自定义)的邻接表，根据输出其邻接表的图的邻接表计算各顶点的角度， 使用实现基于具有输出的有向图的邻接表进行输出的拓扑排序序列的邻接表存储器，实现无向图的深度优先扫描的邻接表存储器，使用实现无向图的宽度优先扫描的邻接矩阵存储器，实现无向图的最小生成树的PRIM算法2 .设计分析调用菜单项，调用各自对应的子函数。 注意在顶点记忆地名，用字符排列来实现。3 .定义结构类型typedef char vextype10； /*顶点数据类型*/typedef int edgetype； /*边缘数据类型*/typedef structvextype vexMAXSIZE；edgetype arcMAXSIZEMAXSIZE；int vexnum，arcnum；Mgraph；typedef struct nodeint adjvex；结构节点*下一个节点；typedef struct nodevextype vex；EdgeNode * firstedge； VexNode；typedef structVexNode adjvexMAXSIZE；int n，e； ALGraph；四、概要设计为了实现上述程序功能，代码如下：#include#include#includetypedef struct node/边表节点int adj； /边表节点数据区域结构节点*下一步；node；typedef struct vnode/顶点表节点char name20；node *fnext；vnode，AList20；typedef structAList List； /邻接表int v，e； /顶点树和边数*Graph；/不创建相邻表graphcreadg ()； 表示不满Graph G；int i、j、k；节点* s；g=malloc (20 * sizeof (节点) )printf (请输入以空格分隔的图顶点数和边数):；scanf (“% d”d，G-v，G-e )； /读取顶点数和边数for(i=0； ； 表示I )printf (请输入图中的%d元素： .i 1scanf(%s”，G-L) /读取顶点信息G-Listi.fnext=NULL； /把边表留空以下称为for(k=0； ke； k )为printf(%d”边的两个顶点编号之间用空格分隔):k 1scanf (“% d”d，I，j )； /读取边(Vi，Vj )的顶点对号码s=(node *)malloc(sizeof(node ) )； /生成边表节点s-adj=j；s-next=G-Listi.fnext；G-Listi.fnext=s； /将新节点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node ) )；s-adj=i； /邻接点编号为Is-next=G-Listj.fnext；G-Listj.fnext=s； /将新节点*s插入顶点Vj的边表头部以下称为return G；以下称为/有向邻接图graphcreatag ()； 中所述方法的备选方法Graph G；int i、j、k；节点* q；g=malloc (20 * sizeof (节点) )printf (图顶点数和边数【空格分隔符】:);scanf (“% d”d，G-v，G-e )；for (i=0； ； 表示I )printf (请输入图中的%d元素： .i 1scanf(%s”，G-L) /读取顶点信息G-Listi.fnext=NULL；以下称为for (k=0； ke； k )为printf (第%d边的双顶点编号【空格分隔符】:，k 1)；scanf (“% d”d，I，j )；q=(node *)malloc(sizeof(node ) )； /生成新的边表节点sq-adj=j； /邻接点编号为jq-next=G-Listi.fnext；G-Listi.fnext=q；以下称为return G；以下称为/输出图邻接表把void Print(Graph G) )int i；节点* p；printf (t=n )；for(i=0； ； 表示I )p=G-Listi.fnext；printf (“% d”% 3s”，I，G-L )while(p)printf(-%3s ，G-L；printf(-%d ，p-adj )；p=p-next；以下称为printf(n )；以下称为以下称为typedef struct char vex20；Lists20；typedef structLists l；int edge2020； /邻接矩阵int v1，e1； /顶点数和弧数容量图typedef structint data； /*某个顶点与已经构筑的部分生成树的顶点之间的权重值最小的顶点*/int lowcost； /*某个顶点与已经构筑的子树顶点之间的最小权重*/ClosEdge20； /*用棱镜算法求最小生成树时的辅助数组*/void CreateAN(AGraph *G1)/*构成相邻矩阵结构的图G */int i、j、k、w；printf (请输入以空格分隔的图顶点数和边数):；scanf (“% d”d，G1-v1，G1-e1 )； /读取顶点数和边数for(i=1； i=G1-v1； 表示I )printf (请输入图%d号元素： .I scanf(%s”，G1-li.vex )； /读取顶点信息以下称为for(i=1； i=G1-v1； i )/初始化相邻矩阵for(j=1； j=G1-v1； j )G1-edgeij=9；for(k=1； k=G1-e1； k )为printf (输入两个顶点和边的权重，用空格分隔):；scanf (“% d”d % d，I，j，w )；G1-edgeij=w；G1-edgeji=w；以下称为以下称为void PrintAN(AGraph *G1)int i，j；printf (t=邻接矩阵=n )；for(i=1； i=G1-v1； 表示I )for(j=1； j=G1-v1； j )printf(=， G1-edgeij )printf(n )；以下称为以下称为/输出各顶点的度数把voidu (图形)int i，j；节点* p；printf(n-每个点的度数-n )；for(i=0； ； 表示I )p=G-Listi.fnext；printf (顶点%2s的度： .G-L； ）j=0；while(p)j；p=p-next；以下称为printf(%dn”，j )；以下称为以下称为/栈敷typedef结构堆栈int x；结构堆栈*下一步；堆栈；int push(stack *s，int i) )堆叠* p；p=(堆叠* ) malloc (堆叠)；p-x=i；p-next=s-next；s-next=p；return 1；以下称为int pop (堆叠* s，int j) )堆栈* p=s-next； /保存堆栈顶部指针j=p-x；s-next=p-next； /拆下堆栈最上面的要素free(p) /释放堆栈顶层空间return j；以下称为/拓扑排序void topo (图形g，堆栈* s )int i，k，count；int j=0；int indegree20=0；节点* p；for(i=0； ； 表示I )p=G-Listi.fnext； 灬while(p！=NULL) )indegreep-adj；p=p-next；以下称为以下称为for(i=0； ； I )if(indegreei=0)推(s，I )count=0；while(s-next！=NULL) )i=pop(s，j )printf(%2s”，G-L )count；for(p=G-Listi.fnext； p！=NULL； p=p-next)k=p-adj；if！ (-indegreek )推(s，k )以下称为以下称为if(countv) printf (有电路！ )；以下称为将void DFS(Graph G，int i，int flag) )节点* p；printf(%2s”，G-L )flagi=1；p=G-Listi.fnext；while(p)if！ flagp-adj )DFS(G，p-adj，flag )p=p-next；以下称为以下称为/深度优先导线测量评估void DFSTravel(Graph G) )int i；int flag20； /标志排列for(i=0； ； I )flagi=0；for(i=0； ； I )if！ flagi )DFS(G，I，flag )以下称为/创建队列typedef structint *elem；int front，rear；*Queue；/队列初始化使用voidsinitqueue(queueq )q-elem=(int * ) malloc (20 * sizeof (int ) )if！ Q-elem )exit(0)Q-front=Q-rear=0；以下称为/入队void Enter(Queue Q，int e) )if(Q-rear 1)！=Q-front )Q-elemQ-rear =e；elseprintf (队列已满！ n )；Q-rear=(Q-rear 1)以下称为/离开球队void Leave(Queue Q，int e) )if(Q-rear！=Q-front