算法程序设计实验报告

-1-《程序设计》课程设计姓名：王学号：20100034班级：软件工程00班指导教师：王会青成绩：2010年6月-2-实验一.构造可以使n个城市连接的最小生成树专业：__软件工程___班级：__软件姓名：_王___学号：_20100034完成日期：_2010/6/26________一、【问题描述】给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2显示出城市间道路网的邻接矩阵。3最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。4输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal算法→执行Prim算法→输出最小生成树二、【问题分析】1.抽象数据类型结构体数组的定义：#ifndefADJACENCYMATRIXED//防止该头文件被重复引用#defineADJACENCYMATRIXED//而引起的数据重复定义#defineINFINITY32767//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefintVRType;//权值，即边的值typedefcharInfoType;//附加信息的类型，后面使用时会定义成一个指针typedefcharVertexType[MAX_VERTEX_NUM];//顶点类型typedefenum{DG=1,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧关系信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];-3-typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;typedefstruct//普里姆算法辅助数组的定义{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];#endif//结束if2程序模块MGraphG;//网G，唯一的全局变量intmain(intargc,char*argv[]);//主函数StatusLocateVex(MGraphG,VertexTypev);//判断城市v在网G中的位置StatusCreateUDN(MGraph&G);//创建网G的邻接矩阵voidDisplayNet(MGraphG);//以邻接矩阵的形式显示网GvoidMiniSpanTree_KRUSKAL(MGraphG);//最小生成树的Kruskal算法voidMiniSpanTree_PRIM(MGraphG,VertexTypeu);//最小生成树的Prim算法StatusMinimum(closedgecloseEdge,intn);//Prim算法中求下一个城市的函数voidDeleteInfo(MGraph&G);//释放堆内存上动态申请的空间3.流程图创建用邻接矩阵表示的城市道路网输入城市数G.vexnum、道路数G.arcnum输入城市名G.vexs[i]-4-输入表示道路的两个城市及道路值G.arcs[i][j].adj返回OKPrim算法化辅助数组closeEdgefor(i=1;iG.vexnum;++i)求下一个城市k=Minimum(closeEdge,G.vexnum)输出找到的道路标记城市，避免重复输出总耗费4.数据类型定义为了用邻接矩阵表示图G，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。-5-4.程序主要模块说明：该程序共含5个模块，本人负责其中2个模块构造：***************LocateVex(MGraphG,VertexTypev)****************StatusLocateVex(MGraphG,VertexTypev);{while(strcmp(G.vexs[i],v)){i++;}返回i；}****************CreateUDN*************************{输入城市数、道路数；for(i=0;i城市数;++i)输入城市名；for(i=0;i城市数;++i)for(j=0;j城市数;++j)初始化邻接矩阵：道路值=INFINITY;for(i=0;i城市数;++i)for(j=0;j城市数;++j)输入两个城市表示道路，输入道路值；}PRIM算法**************************MiniSpanTree_PRIM*********voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){定义辅助数组：closedgecloseEdge;初始化：strcpy(closeEdge[j].adjvex,u);closeEdge[j].lowcost=G.arcs[k][j].adj;-6-for(i=1;iG.vexnum;++i){在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小值；显示找到的道路；标记新找到的城市；}}**********************Minimum*****************StatusMinimum(closedgecloseEdge,intn){在辅助数组中找到道路值最小的道路的两点城市：if((closeEdge[i].lowcost!=0)&&(minTempcloseEdge[i].lowcost))返回该城市在G中的位置}三、【功能实现】#includeiostream.h#includestdio.h#includestring.h#includewindows.h#includeTypeDefine.h#includeAdjacencyMatrix.h#includeInitializeFunction.h#includeMiniSpanTree_KRUSKAL.h#includeMiniSpanTree_PRIM.h#includeDisplayNet.h#includeDeleteInfo.h-7-MGraphG;//全局变量Gintmain(intargc,char*argv[]);//主函数StatusLocateVex(MGraphG,VertexTypev);//判断城市v在网G中的位置StatusCreateUDN(MGraph&G);//创建网G的邻接矩阵voidDisplayNet(MGraphG);//以邻接矩阵的形式显示网GvoidMiniSpanTree_KRUSKAL(MGraphG);//最小生成树的Kruskal算法voidMiniSpanTree_PRIM(MGraphG,VertexTypeu);//最小生成树的Prim算法StatusMinimum(closedgecloseEdge,intn);//Prim算法中求下一个城市的函数voidDeleteInfo(MGraph&G);//释放堆内存上动态申请的空间intmain(intargc,char*argv[]){CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G,G.vexs[0]);DeleteInfo(G);coutendlendl;system(pause);return0;}//intializeFunction.hStatusCreateDG(MGraph&G){return0;};StatusCreateDN(MGraph&G){return0;};StatusCreateUDG(MGraph&G){return0;};StatusCreateUDN(MGraph&G);-8-StatusLocateVex(MGraphG,VertexTypev){//判断输入的顶点v在G中的位置。//根据顶点的类型，可重载此函数。目前为charinti=0;while(strcmp(G.vexs[i],v)){i++;}returni;}StatusCreateGraph(MGraph&G){//采用数组（邻接矩阵）表示法，构造图G.G.kind=UDN;//默认构造无向网/*printf(+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n);printf(|1:有向图2:无向图3:有向网4:无向网\n);printf(|请选择:[]\b\b);scanf(%d,&G.kind);printf(+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n);*/switch(G.kind){caseDG:returnCreateDG(G);//构造有向图GcaseDN:returnCreateDN(G);//构造有向网GcaseUDG:returnCreateUDG(G);//构造无向图GcaseUDN:returnCreateUDN(G);//构造无向网Gdefault:returnERROR;}}//CreateGraph-9-StatusCreateUDN(MGraph&G){//采用数组（邻接矩阵）表示法，构造图G.inti,j,k;VertexTypev1,v2;VRTypew;printf(构造可以使N个城市连接的最小生成树\n);printf(请输入城市数、道路数(至少6个城市，10条道路)：);cinG.vexnumG.arcnum;for(i=0;iG.vexnum;++i)//构造顶点向量{printf(请输入第%d个城市名（共%d个）:,i+1,G.vexnum);cinG.vexs[i];}for(i=0;iG.vexnum;++i)//初始化邻接矩阵{for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;//G.arcs[i][j].info=NULL;}}printf(请输入一条道路连接的两个城市名及权值:\n);for(k=0;kG.arcnum;++k)//构造邻接矩阵{printf(共%3d条道路，第%3d条道路：,G.arcnum,k+1);-10-cinv1v2w;//输入一条边依附的顶点及权值i=LocateVex(G,v1);//确定v1、v2在G中的位置j=LocateVex(G,v2);G.arcs[i][j].adj=w;//弧v1,v2的权值G.arcs[j][i]=G.arcs[i][j];//置v1,v2的对称弧v2,v1}returnOK;}//CreateUDN//MiniSpanTreePRIM.hStatusMinimum(closedgecloseEdge,intn){inti,flag,minTemp=INFINITY;for(i=0;in;++i){if((closeEdge[i].lowcost!=0)&&(minTempcloseEdge[i].lowcost)){minTemp=closeEdge[i].lowcost;fla