课设（救护车模拟系统）.txt

(本人今年的数据结构课程设计为方便大家特次上传

// CHD2.cpp : 定义控制台应用程序的入口点。
//

// CHD.cpp : 定义控制台应用程序的入口点。
//
#include<stdafx.h>
#include<stdio.h> 
#include<stdlib.h> 
typedef int Status; 
typedef Status ** Node; 
#define MaxNum 10000; 
#define FALSE 0; 
#define TRUE 1; 

/*建一个带权的邻接矩阵来存放无向图*/ 
Node Build (Status num , Status num2 ) 
{ 
	int i,j,k,h; 
	Node a; 
	a=(Node) malloc( num * sizeof (Status *)); 
	printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
	printf("   	★                    请输入图的相关信息                    ★\n");
	printf("   	★如:0 2 10表示边的两个顶点分别v0、v2，且权(权表示时间)为10 ★\n");
	printf("   	★在这里顶点是从v0算起，当然这并不是表示要从v0出发找最短路径★\n");
	printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
	printf("\n        当然也可以从其他点出发找最短路径:\n"); 
	for(i=0;i<num;i++) 
	{ 
		a[i]=(Status *) malloc( num * sizeof (Status)); 
		for(j=0;j<num;j++) 
		{ 
			a[i][j]=MaxNum; 
		} 
	} 
	for(h=0;h<num2;h++) 
	{ 
		scanf_s("%d %d %d",&i,&j,&k); 
		/*防止输入过界*/ 
		if( i>=num || j>=num ) 
		{ 
			printf("        无效的输入!请重新输入!!"); 
			exit(1); 
		} 
		a[i][j]=a[j][i]=k; 
	} 
	return a; 
} 

/*迪杰斯特拉算法求最短路径*/ 
void ShortestPath_DIJ( Node a ,Status i ,Status v0 ,Status *D ,Status *pre ) 
{ 
	int v,w,j,l=1; 
	Status *final;/*final[v]为TRUE表示已经求得最短路径*/ 
	Status min; 
	final=(Status *)malloc( sizeof(Status)*i ); 
	for(v=0;v<i;v++) 
	{ 
		final[v]=FALSE;/*设空路径*/ 
		pre[v]=FALSE; 
		D[v]=a[v0][v]; 
		if(D[v]<10000) 
			pre[v]=v0; 
	}//for  
	for(v=0;v<i;v++) 
	{ 
		if( a[v0][v]==10000 ) 
			l++; 
	} 
	if(l>i) 
	{ 
		printf("        \n从v%d出发没有最短路径到其他端点!\n",v0); 
		exit(1); 
	} 
	D[v0]=0; final[v0]=TRUE;//初始化,v0顶点确定 
	for( j=0 ; j<i ; ++j ) 
	{ 
		/*找出距离顶点最近的顶点*/ 
		min=MaxNum; 
		for( w=0 ; w<i ; w++) 
		{ 
			if( !final[w] )//w顶点还没确定 
			{ 
				if( D[w]<min ) 
				{ 
					v=w;min=D[w];/*w顶点离v0更近*/ 
					//printf("wozaizhe"); 
				} 
			} 
		} 
		final[v]=TRUE; 
		/*更新当前最短路径及距离*/ 
		for( w=0 ; w<i ; w++ ) 
		{ 
			if( !final[w] && ( (min+a[v][w])<D[w]) ) 
			{ 
				D[w]=min+a[v][w]; 
				pre[w]=v; 
			}//if 
		} 
	}//for 
}//ShortestPath_DIJ 



void Show(Status *D , Status *pre ,int i ,int v0) 
{ 
	int j,k,m,n; 
	int *temp; 
	temp=(int *)malloc(sizeof(int)*i);
	for(j=0;j<i;j++) 
	{ 
		printf("\n        v%d路径长度为:%d " ,j,D[j]); 
		n=j; 
		if(D[j]!=10000) 
			for(k=0;k<i;k++) 
			{ 
				temp[k]=pre[n]; 
				if(temp[k]!=v0) 
					n=temp[k];
				if(temp[k]==v0) 
					break; 
			} 
			if( k==0&&D[j]!=10000&&D[j]!=0 ) 
			{ 
				printf("v%d->v%d",v0,j);
			} 
			if( k!=0 &&D[j]!=10000&&D[j]!=0) 
			{ 
				for(m=k;m>=0;m--) 
				{ 
					printf("v%d->",temp[m]); 
				} 
				printf("v%d",j); 
			} 
			if(D[j]==10000) 
			{ 
				printf("        从v%d出发没有最短路径!",v0); 
			} 
			if(D[j]==0) 
			{ 
				printf("v%d",v0); 
			} 
	} 
	printf("\n");
} 

int main() 
{ 
	int i,j,v0; 
	Node a; 
	Status *D,*pre;
	printf("\n\n\n\n\n\n");
	printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                ★欢迎进入救护车调度模拟系统★            ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                     姓 名:迟浩东                         ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                     班 级：0791132                       ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                     学 号:1079113221                     ★\n");
	printf("   	★                                                          ★\n");
	printf("   	★                                                          ★\n");
	printf("	★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n"); 
	printf("\n");
	system("pause");
    printf("\n");
	printf("        请输入无向图的顶点数!   "); 
	scanf_s("%d",&i); 
	printf("        再输入无向图的有效数!   "); 
	scanf_s("%d",&j); 
	D=(Status *)malloc(sizeof(Status)*i); 
	pre=(Status *)malloc(sizeof(Status)*i); 
	a=Build(i,j);
    loop:
	printf("\n        请输入起始点(病人所在地): ",j); 
	scanf_s("%d",&v0);
	if(v0>i) 
	{ 
		printf("        输入错误!不存在这样的起始点!"); 
		goto loop;
	} 
	ShortestPath_DIJ( a ,i ,v0 ,D , pre );
	int w,A,B,C,E;
	printf("        医院数目为:");
	scanf_s("%d",&w);
	switch(w)
	{
	case 1:
		printf("        医院所在地为:");
		scanf_s("%d",&A); 	
		printf("        v%d\n" ,A); 
		printf("        离病发地最近的医院为v%d最短时间为%d分钟",A,D[A]);break;
	case 2:
		printf("        医院所在地为:");
		scanf_s("%d%d",&A,&B);
		printf("        v%d v%d\n " ,A,B); 
		if(D[A]<=D[B]) 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟",A,D[A]);
		else 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟",B,D[B]);
		break;
	case 3:
		printf("        医院所在地为:");
		scanf_s("        %d%d%d",&A,&B,&C);
		printf("        v%d v%d v%d\n " ,A,B,C);
		if(D[A]<=D[B]&&D[A]<=D[C]) 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟!",A,D[A]);
		else if(D[B]<=D[C]) 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟!",B,D[B]);
		else 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟!",C,D[C]);
		break;
	case 4:
		printf("        医院所在地为:");
		scanf_s("        %d%d%d%d",&A,&B,&C,&E);
		printf("        v%d v%d v%d v%d v%d\n " ,A,B,C,E);
		if(D[A]<=D[B]&&D[A]<=D[C]&&D[A]<=D[E]) 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟",A,D[A]);
		else if(D[B]<=D[C]&&D[B]<=D[E])
				printf("        离病发地最近的医院为v%d最短时间为%d分钟",B,D[B]);
		else if(D[C]<=D[E])
			printf("        离病发地最近的医院为v%d最短时间为%d分钟",C,D[C]);
		else 
			printf("        离病发地最近的医院为v%d最短时间为%d分钟",E,D[E]);
		break;
	}
	Show( D, pre, i, v0 );
}