搜索
1.需求分析1.1创建结点（旅游景点）创建该旅游景点是在顺序表中完成的，在顺序表中，首先要创建结点结构体，将该结构体命名为SeqList，成员变量有数组list和size，分别用来表示最大元素个数（即旅游景点的最大个数）和顺序表中当前存储的数据元素个数，顺序表可以完成的功能有求当前数据元素个数，插入数据元素，删除数据元素，取数据元素。1.2创建图在构造图的操作中包括结点的插入（实参包括AdjMGraph*G，DataTypv[],n,RowColWeightE[],e）分别表示在该*G的结构体中的SeqlistVertices[]中插入结点，在*G的结构体中的edge[MaxVertices][MaxVertices]的边数组中插入边信息结点分别为行下标、列下标、权值，该*G的结构体中numOfEdges，e表示边的条数，即将e的值给它。结点的顺序表初始化，在该函数中也应包括一个结构体边信息结构体：成员包括行下标、列下标、权值。并将该结构体命名为RowColWeight。1.3图的实现在该函数中要使用SeqList头文件，在该文件中要真正进行插入边和结点。首先在该函数中应该定义一个结构体AdjMGraph，在该结构体的成员变量包括存放结点的顺序表定义为SeqlistVertices[]、存放边的邻接矩阵用edge[MaxVertices][MaxVertices]表示，边的条数numOfEdges。初始化AdjMGraph中的成员变量线性表和边数及存放边的邻接矩阵。然后在顺序表中插入结点，在邻接矩阵中插入边，删除边，删除结点。取序号为V的结点的第一个邻接结点，取序号为V1的邻接结点V2结点的下一个邻接结点1.4求最短路径在该函数中，应该有四个参数，两个位输入参数，分别为带权图G和源点（景点起点）序号v0，两个为输出参数，分别为distance[]和path[],distance[]用来存放达到的从源点v0到其余各结点的最短距离，path[]用来存放最短路径的下标。1、从江西农业大学的平面地图中选取出6个有代表性的景点。2、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。3、为来访客人推荐参观最短路线。2.概要设计1．首先用邻接矩阵存储校园图。2．用数据结构知识创建校园图。3．手动给校园图赋上相关信息（景点名称、代号、简介），路径及路径长度。4．利用C语言知识编写查找景点相关信息的程序。5．利用迪杰斯特拉算法计算任意两点之间的最短路径。6．最后用一个主函数main输出各项结果。1．创建校园图：（1）先定义节点个数N，边的最大值（Maxweight），节点（景点名称、景点信息），邻接点，边，顶点向量，当前顶点数和边数。（2）先给一个节点赋上其相关信息，然后再用p=(Node)malloc(sizeof(edgenode))语句申请下一结点，再给所申请的节点赋上相关信息，直到节点数为N=6为止。（3）读入道路的起始点，为邻接矩阵的边赋相应的值。时（4）节点和边的相关信息都弄好了后，校园图也就创建好了。2．利用函数Name给10个节点赋上相应的名称，利用函数Information给各节点添加相应的介绍信息。3．利用函数travgraph来查找景点信息，要查找景点名称时调用Name函数，要查找景点介绍信息时调用Information函数。4．手动创建一个校园图AdjMGraphgcreat(AdjMGgrph*G)，然后为相应的边赋上真正的值。5．用distance[]数组来存放任意两景点之间的最短路径。6．用main函数来输出结果：用switch语句分别输出，要创建校园图时调用AdjMGraphgraphcreat函数；查找景点相关信息时调用search函数；要查找任意两景点之间的最短路径时，先输入你目前所在的位置，再输入你的目的地，最后调用path函数。3.详细设计#defineN10#defineMAXSize20//图中顶点数的最大值#defineMAXedg30//图中边数的最大值#includestdio.h#includestring.h#includestdlib.h#includeconio.htypedefintAdjMGraph[MAXSize][MAXSize];//存放邻接矩阵的权值信息typedefstruct{intvexs[MAXSize];AdjMGraphs;//}Matrix_Graph;//图的邻接矩阵表示法。typedefstructnumofedge//{intadjvex;//邻接矩阵结点序号intlength;//定义道路长度charinfo[10];//定义景点名称charinfo2[100];//定义景点详细信息structnumofedge*next;//定义指向下一个结点的指针}numofedge,*Node;//将该结构体重新命名为*Nodetypedefstruct{charname[10];//存储景点的名称数组charinformation[100];//具体的介绍此景点信息数组structnumofedge*link;//指向下一个景点的指针}vextices;//创建景点及其信息结构体typedefstructEdge{intlengh;//边的权值，表示路径长度.intivex,jvex;//表示两个连接的结点的位置变量structEdge*next;//指向下一条边的指针变量}EdgeType;//边及其信息.typedefstruct{intnum;//结点编号。charname[10];//结点名称}vertex;//存放结点信息结构体typedefstruct{vertexvexs[MAXSize];//存放结点数组元素信息intedges[MAXSize][MAXSize];//存放边的邻接矩阵}adjmax,adj;//表示图的结构体FILE*fp;//文件的读取voidclrscr()//清屏{system(cls);}voidcreatgraph(vexticesg[],int*n,EdgeTypee[],adjmax*adj)//创建校园图vexticesg[]表示存放景点信息数组，n表示下一个景点，EdgeTypee[]表示存放边的信息数组，adjmax*adj表示下一条边的信息数组{intb,i,s,d,len;//b代表结点之间的边数structnumofedge*p,*q;//定义图的结构体if((fp=fopen(file.txt,r))==NULL)//打开文件,对文件进行读的操作{printf(文件打开错误！\n);getchar();//获取景点信息exit(0);}fscanf(fp,%d%d\n,n,&b);//读入景点个数和边数for(i=1;i=*n;i++){fscanf(fp,%s%s\n,&g[i].name,&g[i].information);//读入文件中结点（景点）的名字和详细介绍信息strcpy(adj-vexs[i].name,g[i].name);//将景点的名字赋给图中的结点信息g[i].link=NULL;//初始化节点的下一个结点信息}for(i=1;i=b;i++){fscanf(fp,%d%d%d\n,&e[i].lengh,&e[i].ivex,&e[i].jvex);//读入道路长度和边的行下标和列下标s=e[i].ivex;//将边的行号记录给S，将边的列号记录下来。d=e[i].jvex;len=e[i].lengh;//将各个边的长度值记录下来adj-edges[s][d]=e[i].lengh;//为邻接矩阵中相应的边赋值adj-edges[d][s]=e[i].lengh;//该矩阵为对称矩阵故edges[d][s]=edges[s][d]；p=(Node)malloc(sizeof(numofedge));//为一个新的结点开辟动态空间。p-next=NULL;//初始化开辟空间的下一个结点q=(Node)malloc(sizeof(numofedge));//为一个新的结点开辟动态空间q-next=NULL;//初始化开辟空间的下一个结点p-adjvex=d;//将边的列号给结点信息的结构体中记录邻接矩阵的序号成员p-length=len;//将边的长度值给结点信息的结构体中的道路成员strcpy(p-info,g[d].name);//为景点赋名称strcpy(p-info2,g[d].information);//为景点赋介绍信息q-adjvex=s;//为景点赋序号，道路长度q-length=len;strcpy(q-info,g[s].name);//为景点赋名称strcpy(q-info2,g[s].information);//为景点赋介绍信息p-next=g[s].link;//使p指针指向第s行的下一行，头插法建立邻接表g[s].link=p;//使p指针指向第s行的下一行的下一行q-next=g[d].link;//使q指针指向第d列的下一列，头插法建立邻接表g[d].link=q;//使q指针指向第d列的下一列，头插法建立邻接表}printf(校园旅游图已经建立！\n);getchar();}voidName(inti){switch(i)//为景点添加具体的名字地点{case1:printf(1:一教\n);break;case2:printf(2:二教\n);break;case3:printf(3:五教\n);break;case4:printf(4:新图书馆\n);break;case5:printf(5:老图书馆\n);break;case6:printf(6:北区食堂\n);break;case7:printf(7:南区食堂\n);break;case8:printf(8:大学生活动中心\n);break;case9:printf(9:圆形报告厅\n);break;case10:printf(10:体育馆\n);break;default:printf(景点编号输入错误！请输入1-10的数字编号！\n\n);break;}}/*Name*/voidInformation(inti){/*景点介绍*/switch(i)//为景点添加介绍信息{case1:printf(一教:这是一栋比较古老的建筑楼，但是当你路过这里，会听到朗朗的读书声，很励志的地方\n);break;case2:printf(二教:这栋楼真的很令人不满意，，不看平面图很难找到，其次，它就是一个2的形状\n);break;case3:printf(五教:这栋教学楼应该是新建的，总体看上去还令人比较满意，周边环境也挺好的\n);break;case4:printf(新图书馆:虽然很小，但是还过的去，学习环境很好，还有自修室，阅览室等学习场所\n);break;case5:printf(老图书馆:很少去，听说藏的书一般是艺术类的书籍，建筑学，美术还有音乐方面等书籍\n);break;case6:printf(北区食堂:有时候味道太重，太咸，但是平时味道不错，是学生就餐的主要餐厅。\n\n);break;case7:printf(南区食堂:味道偏清淡，三楼的南昌风味的快餐店味道较好\n);break;case8:printf(大学生活动中心:在体育馆旁边，举办活动的主要场所，每次晚上路过那里都会听到在举办活动，很热闹\n);break;case9:printf(圆形报告厅:太小了，如果要求全院的人都参加专业类的报告，则会有很多晚来的人站在后面，没有足够的座位\n);break;case10:printf(体育馆:上体育课的主要场地，比较空旷，平时会有很多学生在那里训练，打羽毛球的时候和练