最小生成树问题中北大学数据结构课程设计_第1页
最小生成树问题中北大学数据结构课程设计_第2页
最小生成树问题中北大学数据结构课程设计_第3页
最小生成树问题中北大学数据结构课程设计_第4页
最小生成树问题中北大学数据结构课程设计_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

中北大学数据结构与算法课程设计说 明 书学 院 、 系 : 软件学院专 业 : 软件工程班 级 :学 生 姓 名:学 号:设 计 题 目 : 最小生成树问题起 迄 日 期 : 2015 年 1 月 12 日- 2015 年 1 月 29 日指 导 教 师 : 王秀娟12015 年 1 月 29 日1 需求分析1.1 已知一个无向连通网表示 n 个城市以及城市间可能设置的通信网络线路,其中网的顶点表示城市,边表示两个城市之间的线路,赋于边上的权值表示相应的代价。对于 n 个点的连通网能建立许多不同的生成树,每一棵生成树都可以是一个通信网。我们要选择一棵生成树,使总的耗费最小。1.2 该无向连通图的建立需要使用两种存储结构,即邻接表和邻接矩阵。1.3 实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。1.4 程序通过人机交互实现数据的输入和输出。2 选题要求设计内容:在 n 个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用(邻接表和邻接矩阵)两种,采用课本上的两种求解算法。设计要求:(1) 符合课题要求,实现相应功能;(2) 要求界面友好美观,操作方便易行;(3) 注意程序的实用性、安全性。3 程序设计方法及主要函数介绍ADT Graph数据对象 V;V 是具有相同特性的数据元素的集合,成为顶点集。数据关系 R:R = VRVR = (v,w)|v,w 为 V 集合中的元素, (v,w)表示 v 和 w 之间存在的路径基本操作 P;CreateMGraph(MGraph *G)2初始条件:V 是图的顶点集,VR 是图的边的集合。操作结果:按 V 和 VR 的定义构造图 G,用邻接矩阵存储。CreateALGraph(ALGraph *G)初始条件:V 是图的顶点集,VR 是图的边的集合。操作结果:按 V 和 VR 的定义构造图 G,用邻接表存储。LocateVex(G,u)初始条件:图 G 存在,u 和 G 中顶点有相同的特征。操作结果:若 G 中存在顶点 u,则返回该顶点在图中的位置;否则返回其他信息。MiniSpanTree_PRIM(G, u)初始条件:图 G 存在,u 是图 G 中的一个顶点。操作结果:用普利姆算法从第 u 个顶点出发构造网 G 的最小生成树 T,输出 T 的各条边。Kriuskal(G)初始条件:图 G 存在操作结果:用克鲁斯卡尔算法构造图 G 的最小生成树 T,输出 T 的各条边。ListToMat(MGraph *G1,ALGraph *G2)初始条件:图 G2 存在操作结果:把图的邻接表存储结构转换为邻接矩阵存储结构,用图 G1 表示。MatToList(MGraph *G1,ALGraph *G2)初始条件:图 G1 存在操作结果:把图的邻接矩阵存储结构转换为邻接表存储结构,用图 G2 表示。LocateVex(MGraph *G,VertexType u)初始条件:图G存在,u和G中顶点有相同特征操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1ADT Graph4 程序源代码(包括注释)#include #include #include #define OK 13#define ERROR 0#define TURE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2typedef int Status;#define INFINITY 0#define MAX_VERTEX_NUM 20#define MAX_NAME 5typedef char VertexTypeMAX_NAME;typedef int VRType;typedef struct ArcCell VRType adj;/*顶点关系类型。对无权图,用 1(是)或 0(否)表示相邻否*/*对带权全图,则为权值类型*/ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct MGraph VertexType vexsMAX_VERTEX_NUM;/*顶点向量*/AdjMatrix arcs;/*邻接矩阵*/int vexnum,arcnum;/*图的当前顶点数和弧数*/MGraph;/* 以下定义邻接表类型 */typedef struct ANode /* 弧的结点结构类型 */ int end;int begin; /* 该弧的终点位置 */4int weight; /* 该弧的相关信息,这里用于存放权值 */struct ANode *nextarc; /* 指向下一条弧的指针 */ANode;typedef struct VNode /* 邻接表头结点的类型 */ VertexType vertex; /* 顶点信息 */int bianhao;ANode *firstarc; /* 指向第一条弧 */VNode,AdjListMAX_VERTEX_NUM; /* AdjList 是邻接表类型 */typedef struct ALGraph AdjList adjlist; /* 邻接表 */int vexnum,arcnum; /* 图中顶点数 n 和边数 e */ALGraph; /* 图的邻接表类型 */int LocateVex(MGraph *G,VertexType u) /*初始条件:图 G 存在,u 和 G 中顶点有相同特征*/*操作结果:若 G 中存在顶点 u,则返回该顶点在图中位置;否则返回-1*/int i;for(i=0;ivexnum;+i)if(strcmp(u,G-vexsi)=0)return i;return -1;5图一/* 建立无向图的邻接表算法 */Status InitALGraph(ALGraph *G)int i ;printf(“请输入城市的数量及城市间的路径数目n“);scanf(“%d%d“,for(i=0;ivexnum;i+)/* 建立顶点表 */printf(“请输入第%d 个城市的名称n“,i);scanf(“%s“, /* 读入顶点信息 */G-adjlisti.firstarc=NULL;/* 边表置为空表 */G-adjlisti.bianhao = i;printf(“每个城市所对应的序号为n“);for(i = 0;ivexnum;i+)printf(“序号:%d-城市:%sn“,G-adjlisti.bianhao, /注意此处的6Status PrintALGraph(ALGraph *G)int i,end,begin,weight;ANode *s;for(i=0;ivexnum;i+)/* 建立顶点表 */printf(“%s -“,s = G-adjlisti.firstarc;while(s!=NULL)printf(“( %s,%s ):%d “,s = s-nextarc;printf(“n“);return OK;void CreateALGraph(ALGraph *G)int i,j,k,weight;ANode *s;InitALGraph(G);for(k=0;k arcnum;k+) /* 建立边表 */printf(“n 请输入第%d 条边的两个城市的编号及路径的架设费用:“,k);scanf(“%d“,scanf(“%d“,scanf( “%d“,/* 读入边(vi,vj)的顶点对序号 */s=(ANode*)malloc(sizeof(ANode); /* 生成边表结点 */7if(!s) printf(“申请空间失败!n“);exit(OVERFLOW);s-begin=j; /* 邻接点序号为 j */s-end = i;s-weight = weight;s-nextarc= G-adjlisti.firstarc; G-adjlisti.firstarc=s; /*将新结点*s 插入顶点 vi 的边表头部 */s=(ANode*)malloc(sizeof(ANode);if(!s) printf(“申请空间失败!n“);exit(OVERFLOW);s-begin=i; /* 邻接点序号为 i */s-end=j;s-weight=weight;s-nextarc=G-adjlistj.firstarc;G-adjlistj.firstarc=s; /* 将新结点*s 插入顶点 vj 的边表头部 */PrintALGraph(G);/* CreateALGraph */Status PrintMGraph(MGraph *G)int a;int i,j;printf(“邻接矩阵表示法为:n“); printf(“t“);for(i=0;ivexnum;+i) 8printf(“t%5s “,printf(“n“);for ( i=0; ivexnum; i+)printf(“t%5s “,for ( j=0; jvexnum; j+)printf(“t%5d “,G-arcsij.adj);printf(“n“);return OK;图二Status InitMGraph(MGraph *G)int i,j;printf(“请输入城市的数量及城市间的路径数目:n“);scanf(“%d%d“,printf(“n 请依次输入城市的名称,字符串类型n“);9for(i=0;ivexnum;+i)/*构造顶点向量*/scanf(“%s“,for(i=0;ivexnum;+i)/*初始化邻接矩阵*/for(j=0;jvexnum;+j)G-arcsij.adj=INFINITY;return OK;Status CreateMGraph(MGraph *G)/*采用数组(邻接矩阵)表示法,构造无向网 G*/int i,j,k,weight,IncInfo;VertexType va,vb;InitMGraph(G);for(k=0;karcnum;+k) printf(“请输入第%

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论