main.cpp

清华大学 严蔚敏《数据结构》实验 图的操作：Shortest Path

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

/////////////////////////////////////////////////////////////////////
// Define some macros
/////////////////////////////////////////////////////////////////////

#define INFINITY 1000000000
#define MAX_VERTEX_NUM 30					// 顶点的最大个数
#define NAME_LEN 36							// 顶点名的长度
#define INFO_LEN 100						// 顶点信息的长度



/////////////////////////////////////////////////////////////////////
// Define the struct of VertexTye
/////////////////////////////////////////////////////////////////////

typedef struct
{
	char *name;
	char *info;
} VertexType;

/////////////////////////////////////////////////////////////////////
// Define the struct of MGraph
/////////////////////////////////////////////////////////////////////

typedef struct
{
	VertexType vex[MAX_VERTEX_NUM];
	int vexnum;
	int edgnum;
	int mtrx[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
} MGraph;

/////////////////////////////////////////////////////////////////////
// Define the struct of Path
/////////////////////////////////////////////////////////////////////

typedef struct
{
	int pre[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
} Path;



/////////////////////////////////////////////////////////////////////
// function: initMGraph(MGraph &G)
//           init the MGraph
// param: G - MGraph
// return: void
/////////////////////////////////////////////////////////////////////

void initMGraph(MGraph &G)
{
	int i, j;

	for (i = 0; i < MAX_VERTEX_NUM; ++i)
		for (j = 0; j < MAX_VERTEX_NUM; ++j)
			G.mtrx[i][j] = INFINITY;

	G.vexnum = 0;
	G.edgnum = 0;
}



/////////////////////////////////////////////////////////////////////
// function: resetMGraph(MGraph &G)
//           reset the MGraph to null
// param: G - MGraph
// return: void
/////////////////////////////////////////////////////////////////////

void resetMGraph(MGraph &G)
{
	int i, j;

	for (i = 0; i < G.vexnum; ++i)
		for (j = 0; j < G.vexnum; ++j)
			G.mtrx[i][j] = INFINITY;

	for (i = 0; i < G.vexnum; ++i)
	{
		if (G.vex[i].name != NULL)
		{
			free(G.vex[i].name);
		}
		if (G.vex[i].info != NULL)
		{
			free(G.vex[i].info);
		}
	}

	G.vexnum = 0;
	G.edgnum = 0;
}



/////////////////////////////////////////////////////////////////////
// fuction: readData
//          read the map information from text-file
// param: G -  MGraph
// return: void
/////////////////////////////////////////////////////////////////////

void readData(MGraph &G)
{
	FILE *fp;
	char filename[NAME_LEN];
	char infoStr[INFO_LEN];
	int i, u, v, w;

	printf("\n=== 请导入地图路径和文件名 ===\n");
	fflush(stdin);
	scanf("%s", filename);

	if ((fp = fopen(filename, "r")) == NULL)
	{
		printf("ERROE! Cannot open this file\n");
		exit(0);
	}

	fgets(infoStr, INFO_LEN, fp);
	printf("\n");
	puts(infoStr);

	fscanf(fp, "%d %d", &G.vexnum, &G.edgnum);
	fgetc(fp);

	for (i = 0; i < G.vexnum; ++i)
	{
		if ((G.vex[i].name = (char *)malloc(NAME_LEN * sizeof(char))) == NULL)
		{
			printf("malloc failure\n");
			exit(0);
		}
		if ((G.vex[i].info = (char *)malloc(INFO_LEN * sizeof(char))) == NULL)
		{
			printf("malloc failure\n");
			exit(0);
		}

		fgets(G.vex[i].name, NAME_LEN, fp);
		fgets(G.vex[i].info, INFO_LEN, fp);

		//printf("%s", G.vex[i].name);
		//puts(G.vex[i].info);
	}

	for (i = 0; i < G.vexnum; ++i)
		G.mtrx[i][i] = 0;						// 顶点到自身的距离设为0

	for (i = 0; i < G.edgnum; ++i)
	{
		fscanf(fp, "%d %d %d", &u, &v, &w);
		G.mtrx[u][v] = w;
		G.mtrx[v][u] = w;
	}

	/*for (u = 0; u < G.vexnum; ++u)
	{
		for (v = 0; v < G.vexnum; ++v)
			printf(" %2d", G.mtrx[u][v]);
		printf("\n");
	}
	*/

	fclose(fp);
}



/////////////////////////////////////////////////////////////////////
// function: viewAll
//           view all the scenics first
// param: G - MGraph
// return: void
/////////////////////////////////////////////////////////////////////

void viewAll(MGraph &G)
{
	int i;

	printf("\t        Scenic List 景点一览表           \n");
	printf("\t***************************************************\n");
	for (i = 0; i < G.vexnum; ++i)
	{
		printf("\t %2d: %s", i, G.vex[i].name);
	}
	printf("\t***************************************************\n");
}



/////////////////////////////////////////////////////////////////////
// function: findPath
//           find the shortest path between every two vex using Floyd Algorithm
// param: G - MGraph
//        P - Path
// return: void
/////////////////////////////////////////////////////////////////////

void findPah(MGraph &G, Path &P)
{
	int i, j, k;

	for (i = 0; i < G.vexnum; ++i)
		for (j = 0; j < G.vexnum; ++j)
		{
			P.dis[i][j] = G.mtrx[i][j];
			if ((P.dis[i][j] < INFINITY) && (P.dis[i][j] != 0))
			{
				P.pre[i][j] = i;
			}
		}

	for (k = 0; k < G.vexnum; ++k)
		for (i = 0; i < G.vexnum; ++i)
			for (j = 0; j < G.vexnum; ++j)
			{
				if (P.dis[i][k] + P.dis[k][j] < P.dis[i][j])
				{
					P.dis[i][j] = P.dis[i][k] + P.dis[k][j];
					P.pre[i][j] = P.pre[k][j];
				}
			}
}



/////////////////////////////////////////////////////////////////////
// function: getInfo
//           get the information 
// param: G - MGraph
// return: void
/////////////////////////////////////////////////////////////////////

void getInfo(MGraph &G)
{
	int i, flag;
	char ch;

	viewAll(G);
	printf("\n=== 请输入景点序号以查询该景点的信息 ===\n");
	while (1)
	{		
		printf("\n=== 景点号: ");
		i = 0;
		flag = 1;
		fflush(stdin);
		while ((ch = getchar()) != '\n')
		{
			if ((ch < '0') || (ch > '9'))
			{
				printf("=== 错误，输入应为数字 ===\n");
				flag = 0;
				break;
			}
			i = i * 10 + (ch - '0');
		}
		if (flag == 0)
			continue;
		if (i >= G.vexnum)
		{
			printf("=== 错误，景点号应为 i < %d ===\n", G.vexnum);
			continue;
		}

		// 显示景点信息
		printf("\n%s", G.vex[i].name);
		printf("%s", G.vex[i].info);

		while (1)
		{
			printf("=== 是否继续查询? (y/n): ");
			fflush(stdin);
			ch = getchar();
			if (ch == 'y' || ch == 'n')
				break;
		}
		if (ch == 'n')
			break;
	}
}



/////////////////////////////////////////////////////////////////////
// function: getPath
//           get the shortest path from here to destination
// param: G - MGraph
//        P - Path
// return: void
/////////////////////////////////////////////////////////////////////

void getPath(MGraph G, Path P)
{
	int s, t, k, m, flag;
	int path[MAX_VERTEX_NUM];
	char ch;

	viewAll(G);
	printf("\n=== 请输入出发点与目的地序号以寻找最短路径 ===\n");
	while (1)
	{
		// 输入出发点
		printf("\n=== 出发点: ");
		s = 0;
		flag = 1;
		fflush(stdin);
		while ((ch = getchar()) != '\n')
		{
			if ((ch < '0') || (ch > '9'))
			{
				printf("=== 错误，输入应为数字 ===\n");
				flag = 0;
				break;
			}
			s = s * 10 + (ch - '0');
		}
		if (flag == 0)
			continue;
		if (s >= G.vexnum)
		{
			printf("=== 错误，景点号应为 s < %d ===\n", G.vexnum);
			continue;
		}

		// 输入目的地
		printf("=== 目的地: ");
		t = 0;
		flag = 1;
		fflush(stdin);
		while ((ch = getchar()) != '\n')
		{
			if ((ch < '0') || (ch > '9'))
			{
				printf("=== 错误，输入应为数字 ===\n");
				flag = 0;
				break;
			}
			t = t * 10 + (ch - '0');
		}
		if (flag == 0)
			continue;
		if (t >= G.vexnum)
		{
			printf("=== 错误，景点号应为 t < %d ===\n", G.vexnum);
			continue;
		}

		m = 0;
		k = t;
		while (k != s)
		{
			++m;
			path[m] = k;
			k = P.pre[s][k];
		}

		printf("出发点: %s", G.vex[s].name);
		printf("目的地: %s", G.vex[t].name);
		printf("\n最短路径: %s", G.vex[s].name);
		for (k = m; k > 0; --k)
		{
			printf("\t  ---> %s", G.vex[path[k]].name);
		}
		printf("\n路径距离: %d\n", P.dis[s][t]);
		printf("\n");

		while (1)
		{
			printf("=== 是否继续查询? (y/n): ");
			fflush(stdin);
			ch = getchar();
			if (ch == 'y' || ch == 'n')
				break;
		}
		if (ch == 'n')
			break;
	}
}



// interface function
void MainUI()
{
	printf("\t*************************************************************\n");
	printf("\t*                 欢迎使用校园导游咨询系统！                *\n");
	printf("\t*                                                           *\n");
	printf("\t*         1. 导入地图 Import Map ------------- i/I          *\n");
	printf("\t*         2. 景点一览 View ------------------- v/V          *\n");
	printf("\t*         3. 查询景点信息 Scenic Info -------- s/S          *\n");
	printf("\t*         4. 查询路径信息 Path Info ---------- p/P          *\n");
	printf("\t*         5. 退出系统 Suit ------------------- q/Q          *\n");
	printf("\t*************************************************************\n");
}

// quit interface
void goodbye()
{
	printf("\n");
	printf("\t*************************************************************\n");
	printf("\t*          退出演示程序，谢谢您的使用！                     *\n");
	printf("\t*************************************************************\n");
}



// main function
int main()
{
	MGraph G;
	Path P;
	char ch;
	int quit;

	MainUI();
	initMGraph(G);
	quit = 0;
	while(quit != 1)
	{
		printf("\n# 请输入指令(i/I, v/V, s/S, p/P, q/Q): ");
		fflush(stdin);
		ch = getchar();
		switch (tolower(ch))
		{
			case 'i':	if (G.vexnum != 0)
							resetMGraph(G);
						readData(G);
						break;
			case 'v':	if (G.vexnum == 0)
						{
							printf("=== 未导入地图信息，请加载地图 ===\n");
							readData(G);
						}
						viewAll(G);
						break;
			case 's':	if (G.vexnum == 0)
						{
							printf("=== 未导入地图信息，请加载地图 ===\n");
							readData(G);
						}
						getInfo(G);
						break;
			case 'p':	if (G.vexnum == 0)
						{
							printf("=== 未导入地图信息，请加载地图 ===\n");
							readData(G);
						}
						findPah(G, P);
						getPath(G, P);
						break;
			case 'q':	quit = 1;
						break;
			default:	break;
		}
	}
	goodbye();

	return 0;
}