课程设计数据结构课程设计交通资讯系统.doc

数据结构课程设计交通咨询系统目录一、实验目的:3二、实验要求：3三、总体设计：3四、详细设计：4五、程序代码：5六、测试17七、总结:23参考文献23交通咨询系统一、实验目的:1、充分了解并掌握最短路径问题及其应用。学习迪杰斯特拉算法和弗洛伊德算法。2、根据有向图的存储结构解决实际问题。3、了解程序模块化的过程。4、给用户提供路径咨询。实现了帮助用户了解全国各大城市间往来的最短路径问题。5、可以提供用户查询各大城市的相关信息。二、实验要求：设计一个交通咨询系统，能让旅客在任一个城市顶点到另一个城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。（城市名称用数字代替）。本程序可以在TC2.0和VC6.0中运行。三、总体设计：本程序页面清晰，功能明确，主要分为两个部分，即交通查询部分和管理员管理部分。交通查询部分又分为城市信息、城市路径、最短路径查询3个模块，而其中最短路径查询系统又分为2个城市之间的最短路径和1个城市到其它各城市之间路径的查询。而管理员管理的部分则包括交通查询里面的功能以及添加城市、添加城市间的路径、删除城市以及删除两个城市之间的路径等部分。四、详细设计：详细设计全国交通信息咨询系统的存储结构: struct city_info /*城市信息结构*/ char name20;char info100;citiesSIZE_city; struct way_info /*路径信息结构*/ int start_id;int end_id;int dist;waysSIZE_way;struct path_info /*路径查询结构*/ int count;int pathSIZE_city;typedef struct Graph char vexsSIZE_city;/*顶点*/ int arcsSIZE_citySIZE_city;/*邻接矩阵*/ int vexnum;/*顶点数*/ int arcnum; /*弧数*/ Graph;划分本程序采用自顶向下的编程模式 ，分为7个主模块，即考虑到7种算法的实现：1、显示全国各地城市相关信息的算法；void ShowCity()；初始条件：void ReadCitiesFile();void ReadWaysFile();读取数据成功，操作结果：根据用户查询城市的名字，输出城市的特色；2、添加城市及城市相关信息的算法；void AddView();初始条件：构造了结构体数组viewsVIEW_SIZE；操作结果：添加一个城市顶点到views数组中，并将数据输出到VIEWS文件中保存。3、删除一个城市的算法；void DelView(); 初始条件：存在viewsVIEW_SIZE；操作结果：从views数组中删除一个城市顶点，并重新将数组中数据输出到VIEWS文件中保存。4、是查询城市之间的路径的算法；void ShowWay(); 初始条件：构造了结构体数组waysWAY_SIZE;操作结果：添加一个城市顶点到ways数组中，并将数据输出到WAYS文件中保存。 5、添加城市之间的路径的算法；void AddWay（）；初始条件：构造了结构体数组waysVIEW_SIZE；操作结果：添加一条城市间的路径到ways数组中，并将数据输出到WAYS文件中保存。6、删除城市间的路径的算法；void DelWay(); 初始条件：存在waysVIEW_SIZE；操作结果：从ways数组中删除一个城市顶点，并重新将数组中数据输出到WAYS文件中保存。7、查询两个城市间最短路径的算法void SearchWay();初始条件：存在城市信息及路径的存储结构操作结果：根据用户输入，输出两个城市间的最短路径ATD Graph五、程序代码：#include stdio.h#include string.h#define SIZE_city 20#define SIZE_way 300#define INFINITY 32768#define TRUE 1 #define FALSE 0 struct city_info /*城市信息结构*/ char name20; char info100;citiesSIZE_city; struct way_info /*路径信息结构*/ int start_id; int end_id; int dist;waysSIZE_way;struct path_info /*路径查询结构*/ int count; int pathSIZE_city;typedef struct Graph char vexsSIZE_city; /*顶点*/ int arcsSIZE_citySIZE_city; /*邻接矩阵*/ int vexnum; /*顶点数*/ int arcnum; /*弧数*/ Graph; int city_count, way_count;int commenu2,commenu3;/*函数的声明*/void counseling();void Login();void modify();void ReadCitiesFile();void ReadWaysFile();void ShowCity();void AddCity();void DelCity();void ShowWay();void AddWay();void DelWay();void SearchWay();void main()system(cls);printf(nn); printf(*n); printf(* *n); printf(* The traffic counseling system *n);printf(* made by zhengyanran *n);printf(*n); printf(n);ye(); printf(Quiting.n); printf(nn); return;ye()int commenu1;commenu1=1;while(commenu1!=0)printf(n);printf( Welcome! You can choose as follow:nn);printf( 1 - The traffic counseling.nn); /*显示景点信息*/printf( 2 - The Administrator Login in.nn); /*增加景点方便系统后台管理*/printf( 0 - Quit.nn);printf( What will you do:);scanf(%d, &commenu1);switch(commenu1)case 1:system(cls);counseling();break;case 2: Login();break;void counseling()ReadCitiesFile();ReadWaysFile();commenu2=1;while (commenu2!= 0)printf(nn);printf( Welcome! You can do:nn);printf( 1 - Show the info of cities.nn); /*显示景点信息*/printf( 2 - Show the info of ways.nn); /*显示路径信息*/printf( 3 - Search the best way.nn); /*寻找最佳路径*/printf( 0 - Quitnn);/*退出系统查询系统*/printf( What will you do: );scanf(%d, &commenu2);switch(commenu2)case 1: ShowCity();break;case 2: ShowWay();break;case 3: SearchWay();break;void Login()char hit6;char prehit6=yanran;int i;printf(n Please input the hit number(6bit):);scanf(%s,&hit);while(strcmp(&hit6,&prehit6) system(cls);modify();void modify()ReadCitiesFile();ReadWaysFile();commenu3=1;printf(nn);printf( Welcome! You can do:nn);printf( 1 - Show the info of cities.nn); /*显示景点信息*/printf( 2 - Add a city.nn); /*增加景点方便系统后台管理*/printf( 3 - Delete a city.nn); /*删除景点方便系统后台管理*/printf( 5 - Add a way.nn); /*增加路径 方便系统后台管理*/printf( 4 - Show the info of ways.nn); /*显示路径信息*/printf( 6 - Delete a way.nn); /*删除路径方便系统后台管理*/printf( 7 - Search the best way.nn); /*寻找最佳路径*/printf( 0 - Quitnn);/*退出系统查询系统*/printf( What will you do: );scanf(%d, &commenu3);while (commenu3 != 0)switch(commenu3)case 1: ShowCity();break;case 2: AddCity();break;case 3: DelCity();break;case 4: ShowWay();break;case 5: AddWay();break;case 6: DelWay();break;case 7: SearchWay();break;return ye();void ReadCitiesFile()int i;FILE *fp;city_count = 0;if (fp = fopen(CITIES, rb) = NULL) /*打开CITIES文件，进行读写操作*/ return; for (i = 0; i SIZE_city; i+)if (fread(&citiesi, sizeof (struct city_info), 1, fp) = 1)city_count = city_count + 1;elsebreak;fclose(fp);void ReadWaysFile()int i; FILE *fp; way_count = 0;if (fp = fopen(WAYS, rb) = NULL) /*读取WAYS文件*/ return; for (i = 0; i SIZE_way; i+)if (fread(&waysi, sizeof (struct way_info), 1, fp) = 1)way_count = way_count + 1;elsebreak;fclose(fp);void AddCity()FILE *fp;struct city_info new_city;printf(Adding a city.n);if (fp = fopen(CITIES, ab) = NULL)printf( Open file CITIES failed.n);exit(0);printf(n The name of new city: );scanf(%s, new_);printf(n The info of new city: );scanf(%s, new_);if (fwrite(&new_city, sizeof (struct city_info), 1, fp)=1 )/*将num个城市写入文件中*/citiescity_count = new_city;city_count = city_count + 1;printf(Add a city successfully.n);elseprintf( Write error.n);fclose(fp);printf(nn);return modify();/*删除城市的同时，遍历路径表，将大于所删序号的编号减小1*/void DelCity()int i, select_id; FILE *fp;printf(Deleting a city.n); select_id = 1;while (select_id != 0)if (city_count = 0)printf(n There is not any city. You cant delete any city.nnn);return modify();printf(n All cities in the school:n);for (i = 0; i 0 & select_id = city_count)city_count = city_count - 1;for (i = select_id - 1; i city_count; i+)citiesi = citiesi+1; fp = fopen(CITIES, wb+);for (i = 0; i city_count; i+)fwrite(&citiesi, sizeof (struct city_info), 1, fp);fclose(fp);printf(nn);return; void ShowCity() int i, select_id; printf(n Showing the info of cities.n); if (city_count = 0) printf(n There is not any city.nnn); return modify(); printf(n All cities in the school:n); for (i = 0; i 0 & select_id = city_count) printf(n %s: %sn, citiesselect_, citiesselect_); printf(nn); return counseling(); void AddWay()int i; int tmp_num; FILE *fp;struct way_info new_way;printf(nAdding a way.n);if (city_count = 0)printf(n There is not any view. You cant add a way.nnn);return modify();printf(n All cities in the school:n);for (i = 0; i 0 & tmp_num 0 & tmp_num 0)new_way.dist = tmp_num;break;elseprintf(n Error! Please input positive whole number, or 0 to cancel.n);if (fwrite(&new_way, sizeof (struct way_info), 1, fp) = 1)waysway_count = new_way;way_count = way_count + 1;printf(nAdd a view successfully.);elseprintf(n Write error.n);fclose(fp);printf(nn);return modify();void DelWay()int i, select_id; FILE *fp;printf(nDeleting a way.n);select_id = 1;while (select_id != 0)if (way_count = 0)printf(n There is not any way. You cant delete any way.nnn);return modify();printf(n All ways in the school:n);for (i = 0; i 0 & select_id = way_count)way_count = way_count - 1;for (i = select_id - 1; i way_count; i+)waysi = waysi+1;fp = fopen(WAYS, wb+);for (i = 0; i way_count; i+)fwrite(&waysi, sizeof (struct way_info), 1, fp);fclose(fp);printf(nn);return;void ShowWay()int i; printf(nShowing the info of ways.n);if (way_count = 0)printf(n There is not any way.nnn);return counseling();printf(n All ways in the school:n);for (i = 0; i way_count; i+)printf(n %d: from %s to %s, distance is %dn, i+1, citieswaysi.start_,citieswaysi.end_, waysi.dist);printf(nn);return counseling();void SearchWay() void Dijkstra();void Floyed(); int select_id;printf(n Searching the best way.n);if (city_count = 0)printf(n There is not any city.nnn);return modify();if (way_count = 0)printf(n There is not any way.nnn);return;printf( Algorithms:n);printf( 1: The city to all the other cities nearest way: n); /*用狄克斯特拉（Dijkstra）算法求取最佳路径*/printf( 2: The nearest way of two cities:n); /*用弗洛伊德（Floyed）算法求取最佳路径*/ printf( 0: Canceln); /*退出求取最佳路径*/ select_id = 1;while (1) printf( You will do: );scanf(%d, &select_id);switch (select_id)case 0:return;break;case 1: Dijkstra();return;break;case 2:Floyed();return;break;void Dijkstra()/*n为定点个数*/*迪杰斯特拉算法求最短路径，g为图的邻接矩阵，v0为起始顶点，pvw储存v0到v路径上w的后继顶点(无后继置-1)，dv为路径v0到v的带权长度*/ int i, j,k; Graph g; int pSIZE_citySIZE_city; int dSIZE_city; int v0,v, w, min; int finalSIZE_city; /*finalv=TRUE当且仅当v属于S*/ /*初始化图g*/ for(i=0;icity_count;i+)g.vexsi=;for (i = 0; i city_count; i+)for (j = 0; j city_count; j+)if (i = j)g.arcsij = 0;/*城市自己与自己之间的距离视为0*/continue; g.arcsij=INFINITY; ;/*任意两个不同的城市之间的距离初始化为无穷大*/for (k = 0; k way_count; k+)if (waysk.start_id = i) for(j=0;jway_count;j+)g.arcsij= waysk.dist; break; g.vexnum=city_count; g.arcnum=way_count; for(i=0;icity_count;i+) printf(%ct,g.vexsi); for(j=0;jcity_count;j+) printf(%5d ,g.arcsij); printf(n); printf(n); /*输出图的有关信息*/ for(i=0;icity_count;i+) printf(%ct,g.vexsi); for(j=0;jcity_count;j+) printf(%5d ,g.arcsij); printf(n); printf(n); v0 = 0; /*初始化数组*/ for (v = 0; v g.vexnum; v+) finalv = FALSE; dv = g.arcsv0v; for (w = 0; w g.vexnum; w+) pvw = -1; if (dv INFINITY) pv0 = v0; pv1 = v; /*初始化，顶点v0属于S集合*/ dv0 = 0; finalv0 = TRUE; /*循环n-1次求最短路径*/ for (i = 1; i g.vexnum; i+) min=INFINITY; for (w = 0; wg.vexnum; w+) if (!finalw) /* w属于V-S */ if (dw min) /* w顶点离v0更近 */ v=w; min=dw; finalv = TRUE; /*离v0顶点最近的v加入S集*/ for (w = 0; wg.vexnum; w+) /*更新当前最短路径及距离*/ if (!finalw & (min+g.arcsvw -1 & j city_count; j+) pwj = pvj; /* pw=pv */ pwj = w; /* pw=pv+w */ /*输出最短路径*/ for (i = 0; i g.vexnum; i+) printf(Path %c to %c:n,g.vexsv0,g.vexsi);if ( piv0 != -1 ) /*存在路径则输出*/ for (j = 0; pij!=-1; j+) if (j != 0) printf(); printf( %c,g.vexspij); printf(n); printf(Length:%dn,di); printf(n); /*狄克斯特拉（Dijkstra）算法*/void Floyed() /*弗洛伊德（Floyed）算法*/int i, j, k, m,start_num,end_num;int dist_listSIZE_citySIZE_city;/*由一个城市到另一个城市之间的长度*/struct path_info path_listSIZE_citySIZE_city;/*定义了一个结构体的数组，数组中的每一个数为由一个城市到另一个城市之间的信息包括数目和路径*/for (i = 0; i city_count; i+)for (j = 0; j city_count; j+) if (i = j) dist_listij = 0;/*城市自己与自己之间的距离视为0*/continue; dist_listij = -1;/*任意两个不同的城市之间的距离初始化为-1*/ path_listij.count = 0; for (k = 0; k way_count; k+) if (waysk.start_id = i & waysk.end_id = j) dist_listij = waysk.dist;path_listij.count = 2;path_listij.path0 = i;path_listij.path1 = j;break; for (k = 0; k city_count; k+)for (i = 0; i city_count; i+)for (j = 0; j city_count; j+)if (i = k | j = k | i = j)continue;if (dist_listik = -1 | dist_listkj = -1) continue;if (dist_listij = -1) | (dist_listij != -1) &(dist_listik + dist_listkj dist_listij)dist_listij = dist_listik + dist_listkj;path_listij.count = path_listik.count + path_listkj.count - 1;for (m = 0; m path_listik.count; m+)path_listij.pathm = path_listik.pathm;for (m = 0; m path_listkj.count; m+)path_listij.pathm+path_listik.count = path_listkj.pathm+1; printf( Floyed table:n);for (i = 0; i city_count; i+)for (j = 0; j city_count; j+)if(j%city_count=0)printf(n);printf(t%d, dist_listij); print