数据结构实验报告模板.doc

数据结构实验报告班级： 计应班 姓名： 孙海金 学号： 20117195 学期： 2010-2011学年第一学期 指导教师： 杨华莉 成绩： 实验六 图的操作一、 实验目的二、 实验要求。三、 实验内容和实验结果1. 问题描述。 2. 问题分析。3. 问题的求解。（设计一个具体的待求问题）1) 具体问题的逻辑结构图。2) 设计数据结构。a) 数据元素类型定义 typedef struct VertexType vertexMAX_VERTEX_NUM; /顶点数组， /VertexType为顶点类型 AdjMatrix arcs; /邻接矩阵 int vexnum, arcnum; /顶点数、弧(边)数 GraphKind kind; /图的种类 Graph;b) 图的存储结构定义/图的邻接矩阵存储结构定义typedef int VRType;/顶点关系类型typedef char VertexType20; /顶点类型*typedef char InfoType; /边或弧所代表的信息类型#define INFINITY 32767 /最大值*#define MAX_VERTEX_NUM 20 /最大顶点数typedef enum DG, DN, AG, AN GraphKind;/有向图, 有向网, 无向图, 无向网typedef struct Arc VRType adj; /VRType是顶点关系类型。对图而言，是int型， /用1或0表示是否相邻；对网络而言，则为权值的类型InfoType *info; /指向边或弧所代表的信息的指针 Arc, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vertexMAX_VERTEX_NUM; /顶点数组， /VertexType为顶点类型AdjMatrix arcs; /邻接矩阵int vexnum, arcnum; /顶点数、弧(边)数GraphKind kind; /图的种类 Graph;c) 文件结构定义 /有向图, 有向网, 无向图, 无向网 typedef struct Arc VRType adj; /VRType是顶点关系类型。对图而言，是int型， /用1或0表示是否相邻；对网络而言，则为权值的类型 InfoType *info; /指向边或弧所代表的信息的指针 Arc, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vertexMAX_VERTEX_NUM; /顶点数组， /VertexType为顶点类型 AdjMatrix arcs; /邻接矩阵 int vexnum, arcnum; /顶点数、弧(边)数 GraphKind kind; /图的种类 Graph; 3.程序结构d) 函数说明/基本操作的说明void CreateAN(Graph &G,FILE *in);/建立无向网的邻接矩阵void PrintAN(Graph G,FILE *out);/输出无向网的邻接矩阵void Prim(Graph G, int v);/求最小生成树Prim算法e) 函数实现/基本操作的实现/建立无向网的邻接矩阵void CreateAN(Graph &G,FILE *in) int i,j,k,w,n,e;InfoType *info=NULL; fscanf(in,%d %d,&n,&e);G.vexnum=n;/顶点个数G.arcnum=e;/边数G.kind=AN;/图的种类for(i=0;in;+i) fscanf(in,%s,&G.vertexi);for(i=0; in; +i)for(j=0; jn; +j)/邻接矩阵的初始化G.arcsij.adj=INFINITY;G.=NULL;for(k=0; kijw;/输入边(i,j)、权值wfscanf(in,%d %d %d,&i,&j,&w);G.arcsij.adj=G.arcsji.adj=w;/输出无向网的邻接矩阵void PrintAN(Graph G,FILE *out)int i,j;if(G.kind!=AN)fprintf(out,图G不是无向网n);else fprintf(out,图G为无向网n);fprintf(out,顶点个数为:G.vexnum=%dn,G.vexnum);fprintf(out,边数为:G.arcnum=%d.n,G.arcnum);fprintf(out,顶点序列G.vertex为：n);for(i=0;iG.vexnum;i+)coutsetw(6)G.vertexi;coutendl;printf(邻接矩阵G.arcs为：n);fprintf(out, );printf( );for(i=0;iG.vexnum;i+)coutsetw(6)G.vertexi;fprintf(out,%6s,G.vertexi);coutendl;fprintf(out,n);for(i=0;iG.vexnum;i+)coutsetw(6)G.vertexi;fprintf(out,%6s,G.vertexi);for(j=0;jG.vexnum;j+)if(G.arcsij.adj=INFINITY)/无穷大coutsetw(6); fprintf(out, );else coutsetw(6)G.arcsij.adj;/非无穷大 fprintf(out,%6d,G.arcsij.adj);coutendl;fprintf(out,n);/求最小生成树Prim算法struct minside int adjvex; /距离每个顶点最近的顶点 VRType lowcost; /最近顶点间的权值，0表示顶点已在U集中 closedgeMAX_VERTEX_NUM;int min(minside closedgeMAX_VERTEX_NUM,int n) int k; VRType min=closedge0.lowcost; if(min=0) min=INFINITY; k=0; for(int i=1;iclosedgei.lowcost) min=closedgei.lowcost; k=i; return k;/求最小生成树Prim算法void Prim(Graph G,int v)int i,j,k;int total=0;closedgev.lowcost=0; for (i=0; iG.vexnum; +i)if (i!=v)closedgei.adjvex=v;closedgei.lowcost= G.arcsvi.adj; for (i=1; iG.vexnum; +i) k=min(closedge,G.vexnum); /k为最短边的另一端顶点total+=closedgek.lowcost;cout(G.vertexclosedgek.adjvex,G.vertexk)w=closedgek.lowcostendl;closedgek.lowcost=0; /k进入U集for(j=0; jG.vexnum; +j) /重新调整集中的顶点的最短边if (G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=k;closedgej.lowcost=G.arcskj.adj;printf(总路程为:%dn,total);f) 主函数void main()int v;Graph G;FILE *in;FILE *out;if(in=fopen(D:input.txt,r)=NULL)printf(cannot open the filen);exit(0);if(out=fopen(D:output.txt,w)=NULL)printf(cannot open the filen);exit(0);printf(建立无向网的邻接矩阵n);CreateAN(G,in); printf(n输出建立的无向网的邻接矩阵：n);PrintAN(G,out);fclose(in);fclose(out);printf(n用Prim算法求最小生成树：n);L1:printf(n输入起始点名称：n);/*char ch20;/*scanf(%s,ch);/*for(v=0;(strcmp(ch,G.vertexv)!=0