数据结构课程设计——地铁建设问题

数据结构课程设计——地铁建设问题报告书加实现源代码

#include 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFINITY 10000                    //最大值
#define MAXVEX 20                         //最大顶点个数
typedef int Status;
typedef char VertexType;                  // 顶点类型应由用户定义
typedef int EdgeType;                     //边上的权值类型应由用户定义

typedef struct{
	VertexType vexs[MAXVEX];              //顶点向量
    EdgeType arc[MAXVEX][MAXVEX];         //邻接矩阵可看作边表
	int vexnumarcnum;                    //图的当前顶点数和弧数
}MGraph;

//建立无向图的邻接矩阵表示
void CreateMGraph（MGraph *G）
{
	int ijkw;
	printf（“Please enter the number of station and road:\n“）;
	scanf（“%d%d“&G->vexnum&G->arcnum）; //输入车站（顶点）数量和道路（边）数量
	for（i=0;ivexnum;i++）              //读入顶点信息建立顶点表
		scanf（&G->vexs[i]）;
	for（i=0;ivexnum;i++）
		for（j=0;jvexnum;j++）
			G->arc[i][j]=INFINITY;	      //邻接矩阵初始化
	for（k=0;karcnum;k++）              //读入arcnum条边建立邻接矩阵
	{
		printf（“Enter road（vivj）‘s Sign iSign j and Distance w:\n“）;
		scanf（“%d%d%d“&i&j&w）;       //输入边（vivj）上的权w
		G->arc[i][j]=w; 
		G->arc[j][i]= G->arc[i][j];       //因为是无向图矩阵对称
	}
}

//Prim算法生成最小生成树
void MiniSpanTree_Prim（MGraph G）
{
	int min i j ksum=0;
	int adjvex[MAXVEX];		              //保存相关顶点下标
	int lowcost[MAXVEX];	              //保存相关顶点间边的权值
	printf（“The shortest line（By Prim） is:\n“）;
	lowcost[0]=0;                         //初始化第一个权值为0即v0加入生成树
			                              //lowcost的值为0在这里就是此下标的顶点已经加入生成树
	adjvex[0]=0;			              //初始化第一个顶点下标为0
	for（i=1;i	{
		lowcost[i]=G.arc[0][i];	          //将v0顶点与之有边的权值存入数组
		adjvex[i]=0;					  //初始化都为v0的下标
	}
	for（i=1;i	{
		min=INFINITY;	                  //初始化最小权值
		j=1;k=0;
		while（j		{
			if（lowcost[j]!=0&&lowcost[j]			                              //如果权值不为0且权值小于min
			{	
				min=lowcost[j];	          //则让当前权值成为最小值
				k=j;			          //将当前最小值的下标存入k
			}
			j++;
		}
		printf（“（%d%d）\n“adjvex[k]k）;  //打印当前顶点边中权值最小的边
		sum=sum+lowcost[k];               //累加最短路径
		lowcost[k]=0;                     //将当前顶点的权值设置为0表示此顶点已经完成任务
		for（j=1;j		{
			if（lowcost[j]!=0&&G.arc[k][j]			{                             //如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
				lowcost[j]=G.arc[k][j];   //将较小的权值存入lowcost相应位置
				adjvex[j]=k;		      //将下标为k的顶点存入adjvex
			}
		}
	}
	printf（“The whole length is:%d“sum）;
}

int main（void）
{
	MGraph G;
	printf（“Data Structure Design-The Construction of Subway\n“）;
	CreateMGraph（&G）;
	MiniSpanTree_Prim（G）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThe End.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tSoftWare College of LNTU.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tNetWork Engineer Class One LiuDongnan.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThank you.“）;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3329  2013-01-24 00:21  数据结构课程设计报告及源代码\pro.c

     文件     347716  2014-01-13 21:39  数据结构课程设计报告及源代码\数据结构课程设计.doc

     文件      42043  2013-01-23 23:20  数据结构课程设计报告及源代码\课设图\1.jpg

     文件      34633  2013-01-24 00:17  数据结构课程设计报告及源代码\课设图\2.jpg

     文件      35795  2013-01-24 00:13  数据结构课程设计报告及源代码\课设图\3.jpg

     文件      79903  2013-01-23 22:40  数据结构课程设计报告及源代码\课设图\4.jpg

     文件      40940  2013-01-24 00:05  数据结构课程设计报告及源代码\课设图\5.jpg

     文件      29184  2013-01-23 20:23  数据结构课程设计报告及源代码\课设图\Doc1.doc

     文件      24008  2013-01-24 00:52  数据结构课程设计报告及源代码\课设图\文档 1.doc

     目录          0  2013-05-03 13:35  数据结构课程设计报告及源代码\课设图

     目录          0  2014-01-13 21:40  数据结构课程设计报告及源代码

----------- ---------  ---------- -----  ----

               637551                    11