基本信息

---

下载

   友情提示：（无需注册或充值，赞助后即可获取资源下载链接）

---

     嘿，亲！知识可是无价之宝呢，但咱这精心整理的资料也耗费了不少心血呀。小小地破费一下，绝对物超所值哦！如有下载和支付问题，请联系我们QQ(微信同号)：813200300

本次赞助数额为： 5 元　

支付宝支付

微信支付

   源码介绍

---

#include<stdio.h>		
#include <string.h>
#include <stdlib.h>
#define Max 100000
#define NUM 11



typedef struct ArcCell    //弧的信息
{
	int adj;              //弧长 
	char *info;
}ArcCell;
typedef struct VertexType //顶点的信息
{
	int number;           //顶点代表的数字
	char *sight;          //顶点代表的地点
}VertexType;
typedef struct            //定义图的结构体
{
	VertexType vex[NUM];  //顶点数组
	ArcCell arcs[NUM][NUM];//弧的数组
	int vexnum,arcnum; 
}MGraph;
MGraph G;
int P[NUM][NUM];
long int D[NUM],m;
//int x[13]={0};
void CreateUDN(int v,int a);
void Display();
void ShortestPath(int num);
void output(int sight1,int sight2);
char Menu();
void NextValue(int);

void main() // 主函数
{ 
	int v0,v1;
	char xuhao;
	int v=16;
	CreateUDN(NUM,11);
	do
	{
		xuhao=Menu();
		switch(xuhao)
		{
			case '1':
			Display();
			printf("\n\n\t\t\t请选择出发地序号（1～10）：");
			scanf("%d",&v0);
			printf("\t\t\t请选择目的地序号（1～10）：");
			scanf("%d",&v1);
			ShortestPath(v0);
			output(v0,v1);
			printf("\n\n\t\t\t\t请按回车键继续...\n");
			getchar();
			getchar();
			break;
			case'2':
			printf("该系统是本人通过在数据结构的第七章图，在这章中通过迪杰特斯拉法，求出最短路径，通过图的建立，来建立出整张地图\n");
			printf("通过这一系列的计算，算出的计算路径是理论的，数据纯属于我估计，没有实际的参考价值\n");
			getchar();
			getchar();
			break;
		};
	}while(xuhao!='3');
}




char Menu() // 主菜单
{
	char c;
	int bug;
	do
	{
		bug=1;
		Display();
		printf("\n\t\t\t****************************************\n");
		printf("\t\t\t欢迎进入长江大学导航图系统\n");
		printf("\t\t\t 1.查询地点路径 \n");
		printf("\t\t\t 2.系统简介\n");
		printf("\t\t\t 3.退出 \n");
		printf("\t\t\t****************************************\n");
		printf("\t\t\t请输入您的选择：");
		scanf("%c",&c);
		if(c=='1'||c=='2'||c=='3')
		bug=0;
	}while(bug);
	return c;
}


void CreateUDN(int v,int a) // 创建一个无向图函数
{
	int i,j;
	G.vexnum=v;
	G.arcnum=a;
	for(i=1;i<G.vexnum;  i) 
	G.vex[i].number=i; 
		G.vex[0].sight="各个地点名字";
		G.vex[1].sight="大西门";
		G.vex[2].sight="小西门";
		G.vex[3].sight="主教";
		G.vex[4].sight="行政楼";
		G.vex[5].sight="十三教";
		G.vex[6].sight="十二教";
		G.vex[7].sight="十一教";
		G.vex[8].sight="足球场";
		G.vex[9].sight="新风宿舍";
		G.vex[10].sight="文科楼";
	for(i=1;i<G.vexnum;  i)//初始化
	{
		for(j=1;j<G.vexnum;  j)
		{
			G.arcs[i][j].adj=Max;
		}
	}
	G.arcs[1][2].adj=G.arcs[2][1].adj=200;
		G.arcs[2][5].adj=G.arcs[5][2].adj=50;
		G.arcs[2][9].adj=G.arcs[9][2].adj=300;
		G.arcs[5][10].adj=G.arcs[10][5].adj=50;
		G.arcs[6][10].adj=G.arcs[10][6].adj=50;
		G.arcs[3][6].adj=G.arcs[6][3].adj=50;
		G.arcs[3][7].adj=G.arcs[7][3].adj=50;
		G.arcs[7][8].adj=G.arcs[8][7].adj=200;
		G.arcs[4][8].adj=G.arcs[8][4].adj=500;
		G.arcs[3][4].adj=G.arcs[4][3].adj=400;
		G.arcs[4][5].adj=G.arcs[5][4].adj=700;
		G.arcs[1][4].adj=G.arcs[4][1].adj=600;
		G.arcs[4][10].adj=G.arcs[10][4].adj=600;
		G.arcs[1][5].adj=G.arcs[5][1].adj=150;
}


void Display() // 输出函数
{
	int i;
	printf("\n\t\t\t****************************************\n");
	printf("                               长江大学校园地图\n");
	for(i=1;i<NUM;i  )
	{
		printf("\t\t\t\t(%2d)%-20s\t\t\t",i,G.vex[i].sight);//图的顶点代表的地点
	}
}



//v0顶点到其余某个v顶点的最短路径p及其带权长度D[v]
void ShortestPath(int num) // 迪杰斯特拉算法最短路径
{
	int v,w,i,t;
	int final[NUM];
	int min;
	for(v=1;v<NUM;v  )
	{
		final[v]=0; //FALSE
		D[v]=G.arcs[num][v].adj;
		for(w=1;w<NUM;w  ) 
		P[v][w]=0;//设空路径
		if(D[v]<Max)
		{
			P[v][num]=1;//TRUE
			P[v][v]=1;//TRUE
		}
	}

	D[num]=0;//初始化，V0顶点属于S集
	final[num]=1;
	//开始主循环，每次求得v0到某个V顶点的最短路径，并将V加到S集中
	for(i=1;i<NUM;  i)
	{//其余的num-1个顶点
		min=Max;      //当前所知离V0顶点最近的距离
		for(w=1;w<NUM;  w)
			if(!final[w])
				if(D[w]<min)
				{
					v=w;   //w顶点在V-S中
					min=D[w];
				}
				final[v]=1;
				//离V0顶点最近的V加入S集
				for(w=1;w<NUM;  w)//更新当前最短路径及距离
					if(!final[w]&&((min G.arcs[v][w].adj)<D[w]))//修改D[w]和P[w]
					{
						D[w]=min G.arcs[v][w].adj;
						for(t=0;t<NUM;t  )
							P[w][t]=P[v][t];
						P[w][w]=1;
					}
	}
}


void output(int sight1,int sight2) // 输出函数
{
	int a,b,c,d,q=0;
	a=sight2; 
	if(a!=sight1)
	{
		printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);
		printf("\t(最短距离为 %dm.)\n\n\t",D[a]); 
		printf("\t%s",G.vex[sight1].sight); 
		d=sight1;
		for(c=0;c<NUM;  c)
		{
			gate:;
			P[a][sight1]=0;
			for(b=0;b<NUM;b  )
			{
				if(G.arcs[d][b].adj<32767&&P[a][b])
				{
					printf("-->%s",G.vex[b].sight); 
					q=q 1;
					P[a][b]=0;
					d=b;
					if(q%8==0) printf("\n");
					goto gate;
				}
				
			}
		}
	}
}