数据结构课程设计——校园导游咨询系统.doc

数据结构课程设计校园导游咨询系统1：需求分析： (1)任务：编制一个为来访客人进行最短路径导游的程序 (2)要求：从学校的平面上选取n个有代表性的景点，根据用户指定的起点和终点输出相应路径。2：概要设计：(1) 1)a) AdjMGraph.h图操作的函数所放的头文件b) AdjMGraphCreate.h图的创建函数所放的头文件c) Dijkstra.h狄克斯特拉函数设计所放的头文件d) SeqList.h存放顺序表的头文件2)SchoolGuide.c文件包括以下三个函数 void SgPrint(AdjMGraph g,int n,int distance,int path,int j)函数，其功能是将源点到各个结点的最短距离和最短路径的结果输出； void Sgblueprint()函数，其功能是将校园平面图输出； void main(void)函数，主函数，功能是调用测试数据值，显示主菜单，根据用户输入的i进行不同功能操作，随后根据用户输入的ch值进行不同功能操作。(2)该程序所使用的存储结构是顺序存储；(3)流程图：调用函数CreatGraph输入i值输出有关标题和菜单选项的提示信息char chint i，j,n=6，e=9初始化结构体g和rcw,以及数组a，distance和path开始 i 3 1 2 清除屏幕清除屏幕调用函数Sgblueprint调用函Sgblueprint输出用户选择起点的提示信息输入j值调用Dijkstra输出是否继续操作的提示信息输出有关景点代码问题提示信息输入ch值 调用函数SgPrint ch=y|ch=Y T F结束图1-1主函数main()流程图开始初始化i值输出从源结点到其他各结点的最短路径及其距离分别为：输出换行符i=0isize=0; /*定义初始化数据元素个数*/ int ListLength(SeqList L) /*返回顺序表L的当前数据元素个数*/return L.size;int ListInsert(SeqList *L,int i,DataType x)/*在顺序表L的第i(0isize)个位置前插入数据元素值x*/*插入成功返回1，插入失败返回0*/ int j; if(L-size=MaxSize) printf(顺序表已满无法插入！n); return 0; else if(iL-size) printf(参数i不合法！n); return 0; else /*为插入做准备*/ for(j=L-size;ji;j-) L-listj=L-listj-1; L-listi=x;/*插入x*/ L-size+;/*元素个数加1*/ return 1; int ListDelete(SeqList *L,int i,DataType *x) /*删除顺序表L中位置为i(0isize-1)的数据元素并存放到x中*/ /*删除成功返回1，删除失败返回0*/ int j; if(L-size=0) printf(顺序表已空无数据元素可删！n); return 0; else if(iL-size-1) printf(参数i不合法); return 0; else *x=L-listi; /*保存删除的元素到x中*/ /*依次前移*/ for(j=i+1;jsize-1;j+) L-listj-1=L-listj; L-size-; return 1; int ListGet(SeqList L,int i,DataType *x)/*取顺序表L中第i个数据元素存于x中，成功返回1.失败返回0*/if(iL.size-1)printf(参数i不合法！n);return 0;else*x=L.listi;return 1;(2)/* AdjMGraph.h图操作的函数所放的头文件*/#includeSeqlist.h/*包含顺序表头文件*/typedef struct SeqList Vertices;/*存放结点的顺序表*/ int edgeMaxVerticesMaxVertices;/*存放边的邻接矩阵*/ int numOfEdges;/*边的条数*/AdjMGraph;/*图的结构体定义*/void Initiate(AdjMGraph *G,int n)/*初始化*/ int i,j; for(i=0;in;i+) for(j=0;jedgeij=0; else G-edgeij=MaxWeight; G-numOfEdges=0;/*边的条数置为0*/ ListInitiate(&G-Vertices);/*顺序表初始化*/void InsertVertex(AdjMGraph *G,DataType vertex)/*在图G中插入结点vertex*/ ListInsert(&G-Vertices,G-Vertices.size,vertex); /*顺序表尾插入*/void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/*在图G中插入边,边的权为weight*/ if(v1G-Vertices.size|v2G-Vertices.size) printf(参数v1或v2越界出错！n); exit(1); G-edgev1v2=weight; G-numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)/*在图G中删除边*/ if(v1G-Vertices.size|v2G-Vertices.size) printf(参数v1或v2越界出错！n); exit(1); G-edgev1v2=MaxWeight; G-numOfEdges-;void DeleteVerten(AdjMGraph *G,int v)/*删除结点V*/ int n=ListLength(G-Vertices),i,j; DataType x; for(i=0;in;i+)/*计算删除后的边数*/ for(j=0;jedgeij0&G-edgeijnumOfEdges-;/*计算被删除边*/ for(i=v;in;i+) /*删除第v行*/ for(j=0;jedgeij=G-edgei+1j; for(i=0;in;i+) /*删除第v列*/ for(j=v;jedgeij=G-edgeij+1; ListDelete(&G-Vertices,v,&x);/*删除结点v*/int GetFirstVex(AdjMGraph G,int v)/*在图G中寻找序号为v的结点的第一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/ int col; if(vG.Vertices.size) printf(参数v越界出错n); exit(1); for(col=0;col0&G.edgevcolMaxWeight)return col; return -1;int GetNextVex(AdjMGraph G,int v1,int v2)/*在图G中寻找v1结点的邻接结点v2的下一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/*v1和v2都是相应结点的序号*/ int col; if(v1G.Vertices.size|v2G.Vertices.size) printf(参数v1或v2越界出错！n); exit(1); for(col=v2+1;col0&G.edgev1colMaxWeight) return col; return -1;(3)/* AdjMGraphCreate.h图的创建函数所放的头文件*/typedef struct int row;/*行下标*/ int col;/*列下标*/ int weight;/*权值*/RowColWeight;/*边信息结构体定义*/void CreatGraph(AdjMGraph *G,DataType V,int n,RowColWeight E,int e)/*在图G中插入n个结点信息V和e条边信息E*/ int i,k; Initiate(G,n);/*结点顺序表初始化*/ for(i=0;in;i+) InsertVertex(G,Vi);/*结点插入*/ for(k=0;ke;k+) InsertEdge(G,Ek.row,Ek.col,Ek.weight);/*边插入*/(4)/* Dijkstra.h狄克斯特拉函数设计所放的头文件*/void Dijkstra(AdjMGraph G,int v0,int distance,int path)/*带权图G从下标v0结点到其他结点的最短距离distance*/*和最短路径下标path*/ int n=G.Vertices.size; int *s=(int *)malloc(sizeof(int)*n); int minDis,i,j,u; /*初始化*/ for(i=0;in;i+) distancei=G.edgev0i; si=0; if(i!=v0&distanceiMaxWeight) pathi=v0; else pathi=-1; sv0=1;/*标记结点v0已从集合T加入到集合S中*/ /*在当前还未到最短路径的结点集中选取具有最短距离的结点u*/ for(i=1;in;i+) minDis=MaxWeight; for(j=0;jn;j+) if(sj=0&distancejminDis) u=j; minDis=distancej; /*当已不再存在最短路径时算法结束；此语句对非连通图是必须的*/ if(minDis=MaxWeight)return; su=1;/*标记结点u已从集合T加入到集合S中*/ /*修改从v0到其他结点的最短距离和最短路径*/ for(j=0;jn;j+) if(sj=0&G.edgeujMaxWeight&distanceu+G.edgeujdistancej) /*结点v0经结点u到其他结点的最短距离和最短路径*/ distancej=distanceu+G.edgeuj; pathj=u; (5)/* SchoolGuide.c文件*/#include#include#includetypedef char DataType;#define MaxSize 100#define MaxVertices 10#define MaxWeight 10000#includeAdjMGraph.h#includeAdjMGraphCreate.h#includeDijkstra.hvoid SgPrint(AdjMGraph g,int n,int distance,int path,int j) /*输出源点到其他各结点的最短距离和最短路径*/ int i; /*从源结点到其他各结点的最短路径及其距离分别为：*/ printf(从该结点%c到其他各结点的最短路径及其距离分别为：n,g.Vertices.listj); printf(n);/输出换行符 for(i=0;in;i+) /*从源结点到当前结点的最短路径为*/ printf(从结点%c到结点%c的最短路径为:,g.Vertices.listj,g.Vertices.listi); printf();/输出左括号 if(pathi!=-1)/源点到其他结点的最短路径的前一结点判断 if(pathpathi!=-1)/该前一结点的前一结点进行判断 if(pathpathpathi!=-1)/该前一结点的前一结点的前一结点进行判断 printf(%c,g.Vertices.listpathpathpathi);/输出相应存在的前一结点 printf(%c,g.Vertices.listpathpathi);/输出应存在的前一结点 printf(%c,g.Vertices.listpathi);/输出应存在的前一结点 printf(%c,g.Vertices.listi);/输出当前结点 printf();/输出换行符右括号 printf(，其最短距离为%d；n,distancei);/输出源点到其他结点的最短距离 printf(n);/输出换行符 void Sgblueprint()/*显示校园平面图*/ printf( 校园平面图 n); printf( B(学生宿舍)E(商业街)n); printf( / / | n); printf( / / | n); printf( / (B到D) / | n); printf( / / | n); printf( / / | n); printf(A(校门口) D(学校食堂和 | n); printf(| 学校田径场(学校田径场在学校食堂后面) | n); printf(| (D到F) | n); printf(| | n); printf(C(第一、第二教学楼和校办) F(第三教学楼和实验楼)n);void main(void) AdjMGraph g; char a=A,B,C,D,E,F; RowColWeight rcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7,4,3,4,5,3,10,5,4,18; int i,j,n=6,e=9;/i为控制控制菜单项的数值，j为选取源点的数值 char ch; int distance6,path6; printf( 校园导游咨询系统-您身边的导游 n); printf(n); printf(n); printf(n); /*菜单选项*/ printf( 1:请求校园导游帮组(即咨询校园各景点最短路径)n); printf( 2:显示校园平面图n); printf( 3:退出校园导游咨询系统n); printf(请输入你所想进行的功能选项：n); scanf(%d,&i); /输入控制控制菜单项的数值i的值 CreatGraph(&g,a,n,rcw,e);/创建图 switch(i) /选择菜单项的操作 case 1:system(cls); /*调用输出校园平面图函数并输出校园平面图*/ Sgblueprint(); /*提示用户输入起点的序列号*/ printf(请输入你所在地或起点的序列号(A-F的序列号为依次0，1,2,3,4，5)：n); scanf(%d,&j);/用户输入起点的序列号i的值 /*调用狄克斯特拉函数计算源点的其他各结点的最短路径及其距离*/ Dijkstra(g,j,distance,path); /*提示用户参照校园平面图以了解各景点的代号的含义*/ printf(提示：下列A、B、C等均是各景点的代号，如有问题，请参考上面的校园平面图n); /*调用输出源点到其他各结点的最短距离和最短路径函数并输出相应的最短路径和最短距离*/ SgPrint(g,n,distance,path,j); break; case 2:system(cls); Sgblueprint();/调用输出校园平面图函数并输出校园平面图 break; case 3:exit(1);break;/退出程序 while(3)/判断程序是否继续运行 printf(n您是否还想进行其他操作(y/n):n);/提示用户是否还需继续进行其他操作 scanf(%s,&ch);/用户输入y/n以选择是否仍需进行其他操作 if(ch=Y|ch=y)/判断用户所输入的ch值是否为y/Y，以判断用户是否进行其他操作 system(cls); printf( 校园导游咨询系统-您身边的导游 n); printf(n); printf(n); printf(n); /*菜单选项*/ printf( 1:请求校园导游帮组(即咨询校园各景点最短路径)n); printf( 2:显示校园平面图n); printf( 3:退出校园导游咨询系统n); printf(请输入你所想进行的功能选项：n); scanf(%d,&i); switch(i) /选择菜单项的操作 case 1:system(cls); /*调用输出校园平面图函数并输出校园平面图*/ Sgblueprint(); /*提示用户输入起点的序列号*/ printf(请输入你所在地或起点的序列号(A-F的序列号为依次0，1,2,3,4，5)：n); scanf(%d,&j);/用户输入起点的序列号i的值 /*调用狄克斯特拉函数计算源点的其他各结点的最短路径及其距离*/ Dijkstra(g,j,distance,path); /*提示用户参照校园平面图以了解各景点的代号的含义*/ printf(提示：下列A、B、C等均是各景点的代号，如有问题，请参考上面的校园平面图n); /*调用输出源点到其他各结点的最短距离和最短路径函数并输出相应的最短路径和最短距离*/ SgPrint(g,n,distance,path,j); break; case 2:system(cls); Sgblueprint();/调用输出校园平面图函数并输出校园平面图 break; case 3:exit(1);bre