石家庄经济学院本科生课程设计报告书题目校园导游咨询系统姓名学号学院信息工程学院专业计算机指导教师完成日期：2012年7 月5 日校园导游咨询系统1 需求分析需要设计一个校园导游咨询系统，为来访的客人提供各种信息查询服务。

a)基本要求：设计你所在学校的校园平面图,所含景点不少于10个。

以图中顶点表示校内各景点,存放有景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

为来访客人提供图中任意景点相关信息的查询。

为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

b)问题分析：系统要处理的数据有字符型、字符串型、浮点型，如景点的代号使用字符类型、景点名称及简介等信息用字符串型、路径的长度用浮点型等。

它们之间存在并列、包含等关系，采用线性单链表、图的邻接矩阵等数据结构来存储数据。

c)系统完成的功能：来访客人浏览校园全景查询相关景点的信息可查询所有浏览路线来访客人可以查询从某一景点到另一景点的最短路径；d)程序设计分析：构造一个无向带权网G并用邻接矩阵来存储；利用弗洛伊德算法来计算出起点到各个顶点之间的最短路径并进行存储，弗洛伊德算法将找出每一对顶点之间的最短路径；e)系统的输入与输出：键盘输入，磁盘输入、输出等。

f)系统的操作用例：学校北门（0）学生公寓（1）博物馆（2）惠馨园（3）操场（4）图书馆（5）校医院（6）主楼（7）教学楼（8）实验楼（9）校园平面图顶点代码以及各顶点之间的权值所构成的邻接矩阵：校园北门学生公寓校医院博物馆惠馨园操场图书馆教学楼实验楼主楼树校园平面图0 1 2 3 4 5 6 7 8 9 0 0 100 200 4001 03002 0 1003 0 100200 4 0 300250 5 0 350 6 0 50 200 7 0 50 8 0 20 92、概要设计：（1）抽象数据类型：ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={<v,w>|v,w∈V且P（v,w），<v,w>表示v w之间的路径。

}基本操作P：CreateGraph（&G,V,VR）；初始条件：V是校园平面图的顶点集，VR是校园平面图中弧的集合。

操作结果：按V和VR的定义构造校园平面图G。

DestroyGraph（&G）；初始条件：校园平面图G存在。

操作结果：销毁校园平面图G。

LocateVex （G，u）；初始条件：校园平面图G存在，u和G中顶点有相同特征。

操作结果：若校园平面图G中存在顶点u，则返回该顶点在图中的位置，否则返回其他信息。

list()；初始条件：校园平面图存在操作结果：查询校园全部景点。

introduce()；初始条件：校园平面图存在操作结果: 查询每个景点的详细信息shortestdistance(MGraph &G)初始条件：校园平面图G存在，v和w是G中两个顶点。

操作结果：若v和w之间存在路径，则以Path返回两点之间的最短路径，返回其他信息。

} ADT Graph（2）设计系统原型：主程序模块void main(){初始化：邻接矩阵接受命令；处理命令；}存储无向带权图模块（3）操作界面:石家庄经济学院导游图1.浏览校园全景2.查看所有游览路线3.选择出发点和目的地，查找最短旅游路线4.查看景点信息5.退出系统Option-:3、详细设计：1. 存储结构typedef struct ArCell{int adj; //路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];\typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{char name[30];int num;char introduction[100];//简介}infotype;typedef struct{infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;MGraph b;1.基本操作函数声明：Status CreateGraph（&G,V,VR）;//按V和VR的定义构造校园平面图G Status DestroyGraph（&G）;//销毁校园平面图GStatus LocateVex （G，u）;//若校园平面图G中存在顶点u，则返回该顶点在//图中的位置，否则返回其他信息Status list();//查询校园全部景点Status introduce();//查询每个景点的详细信息Status shortestdistance(MGraph &G) ;//若v和w之间存在路径，则以Path返回两点//之间的最短路径，返回其他信息void cmd(void);MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DIJ(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);int LocateVex(MGraph *G,char* v);MGraph * CreatUDN(MGraph *G);void print(MGraph *G);3.操作函数的伪码算法如下:Status CreateGraph（&G,V,VR）//按V和VR的定义构造校园平面图G{int V;cin(V);cin(VR);}Status DestroyGraph（&G）//销毁校园平面图G{if(G)T.length==0;free(G);}Status LocateVex （G，u）//若校园平面图G中存在顶点u，则返回该顶点在//图中的位置，否则返回其他信息{int i;if(G.u[i])return i;elsereturn false;}Status list()//查询校园全部景点{if(G)visit(vexnum);}Status introduce()//查询每个景点的详细信息{if(G)visit(introduction);}Status shortestdistance(MGraph &G) //若v和w之间存在路径，则以Path返回两点//之间的最短路径，返回其他信息{if(G)if(<v.w>)int path；path=length. <v.w>;return path;elsereturn false;}void cmd(void){InitGraph();//构造校园景点图Menu();scanf(i);while(i!=5){switch(i){case 1: 浏览校园全景case 2: 查看所有游览路线case 3: 选择出发点和目的地，查找最短旅游路线case 4:查看景点信息case 5: 退出系统}}}MGraph InitGraph(void) //各景点信息及最短距离void Menu()//操作界面{printf("\n 石家庄经济学院导游图\n");printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n");printf(" ┃ 1.浏览校园全景┃\n");printf(" ┃ 2.查看所有游览路线┃\n");printf(" ┃ 3.选择出发点和目的地，查找最短旅游路线┃\n");printf(" ┃ 4.查看景点信息┃\n");printf(" ┃ 5.退出系统┃\n");printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n");printf("请选择1-4来了解您需要的信息，5退出系统:");}void Browser(MGraph *G) //浏览校园全景{printf("┏━━┳━━━━━━┳━━━━━━━━┓\n");printf("┃编号┃景点名称┃简介┃\n");if(i<顶点数)printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction);printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}迪杰斯特拉算法求最短路径：void ShortestPath_DIJ(MGraph * G) // 迪杰斯特拉算法来计算出起点到各个//顶点之间的最短路径,v0为起点{int v,w,i,min,t=0,x,flag=1,v0;int final[20], D[20], p[20][20];while(flag){scanf (一个起始景点编号);if(v0<0||v0>G->vexnum){printf("景点编号不存在!请重新输入景点编号:");scanf(&v0);}if(v0>=0&&v0<G->vexnum)flag=0;}for(v=0;v<G->vexnum;v++) //各对结点之间初始已知路径及距离{final[v]=0;D[v]=G->arcs[v0][v].adj;for(w=0;w<G->vexnum;w++)p[v][w]=0; // v到w设空路径if(D[v]<INFINITY)p[v][v0]=1;p[v][v]=1;}D[v0]=0;final[v0]=1; //初始化，v0顶点属于S集// 开始主循环，每次求得v0 到某个v顶点的最短路径，并加v到S集for(i=1;i<G->vexnum;i++){ //其余G.vexnum - 1 个顶点min=INFINITY; //当前所知离v0顶点的最近距离for(w=0;w<G->vexnum;w++)if(!final[w]) // w顶点在V-S集中if(D[w]<min){v=w;min=D[w];} //w顶点离v0顶点更近final[v]=1; //离v0顶点最近的V加入S集for(w=0;w<G->vexnum;w++) //更新当前最短路径及距离if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) //修改D[w]和P[w],w∈V-S{D[w]=min+G->arcs[v][w].adj;for(x=0;x<G->vexnum;x++)p[w][x]=p[v][x];p[w][w]=1; // P[w]= P[v]+[w]}}void Search(MGraph *G) //查询景点信息{int k,flag=1;while(flag){scanf(k);if(k<0||k>G->vexnum){printf(景点编号不存在!请重新输入景点编号);scanf(k);}if(k>=0&&k<G->vexnum)flag=0;}printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("┃编号┃景点名称┃简介┃\n");printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}int LocateVex(MGraph *G,char* v){int c=-1,i;for(i=0;i<G->vexnum;i++)if(strcmp(v,G->vexs[i].name)==0){c=i;break;}return c;}4.主函数的伪码算法如下：void main(void){system("color 5f");system("mode con: cols=140 lines=130");cmd();}4、编码调试：操作界面：操作界面图选择操作步骤进行下一步操作：浏览校园全景：校园全景图查看各个景点的旅游路线，测试数据2（博物馆）、9(实验楼)：2号景点的旅游路线图9号景点的旅游路线图查看两个景点的最短路线,测试数据1（学生公寓）-7（主楼）、 4（操场）-6（校医院）、 3（惠馨园）-8（教学楼）：1号景点到7号景点的最短路径4号景点到6号景点的最短路径3号景点到8号景点的最短路径查看各景点的具体信息,测试数据3（惠馨园）、6（校医院）：3号景点的具体信息6号景点的具体信息数据输入错误时：数据输入错误时的界面分析：当输入的景点代号超过最大值时，提示“景点编号不存在，请重新输入：”这个课程设计题目的难点在于熟悉无向图、领结矩阵、迪杰斯特拉算法、弗洛伊德算法、图的遍历等数据结构知识。