数据结构课程设计导航图

西安邮电大学（计算机学院）数据结构设计报告题目：导航图专业名称：软件工程班级：班学生姓名：学号（8位）：指导教师：设计起止时间：2014年12月15日—2014年12月26日一.设计目的1.数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发2.通过课程设计，使学生通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。3.学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力二.设计内容我设计的是旅游查询系统，是用于校园的，任何景区都可以用。对于游客来说，游客可以查询要游览的景点，可以显示出该景点的相关信息，景点等级。也可以输入起点和终点，找到一条最短路径，或者这两点之间所有路径。或者输入起点，自动生成一个全程最短的游览路线。当然游客也可以查看校园的平面图。对于管理员来说，管理员可以增，删，改景点和道路信息。三．概要设计1．功能模块图；旅游查询系统2．各个模块详细的功能描述。1.浏览全景显示校园的平面图，让游客大概的了解校园的形貌，以及各个景点的位置。浏览全景显示所有景点和路线最短行程查询最佳全景路线查询两点之间所有路线系统管理2.显示所有景点和路线将所有景点和路线以列表的形式显示出来，包括景点名称，景点等级，景点描述；路线也有道路名称，道路距离，道路的起点终点。3.最短行程查询输入起点，显示该起点到其它所有景点的最短路径。4.最佳游览全景路线输入起点，生成一个最小联通路径，这样游客便能以最少的行程来游览所有景点。5.两点之间所有路线输入起点和终点，显示出这两点之间的所有路线供游客选择。四．详细设计1．功能函数的调用关系图2．各功能函数的数据流程图Mian()Map()showall()seekspotmin()bestroad()pathall()System()Dijkstra()prim()init_SeqStack()DFS()pop()push()changes()add()del()changel()creatgrahp()Mian()Map()showall()seekspotmin()bestroad()pathall()System()Dijkstra()prim()init_SeqStack()DFS()pop()push()changes()add()del()changel()creatgrahp()3．重点设计及编码用DFS得出两点之间所有路线，首先输入起点和终点名称，找到其名称的下标，以起点下标开始进行深度优先遍历，每遍历到下一个邻接点让其进栈，并判断其下标是否和终点下标相同，如果相同则输出栈内所有元素，并将栈顶出栈，若不相同，继续遍历。直至找完所有的路线。在这里栈的作用是存储将要找到的路线。五．测试数据及运行结果1．正常测试数据和运行结果六．调试情况设计技巧及体会在求两点之间所有路径和最小联通路径的算法中，需要将邻接表转化为矩阵去做。对于prim算法所得出的结果并不是游客所要按照的走法，只是单纯的最小生成树，若要得到一个节省的且能游览所有的景点的走法，那么需要遍历所得到的最小生成树，但并没有一个普遍的遍历方法去得到，完全需要游客自己主观的去判断怎样走才最短。在系统管理这一功能中，只有管理员才能使用，所以必须设置密码，这样就避免了游客的操作。对于邻接表要存储无向图，我们需要该顶点的邻接点个数，输完该顶点，再输入这些邻接点。那么输入以某个邻接点为顶点时，之前已经输过的顶点就是它的邻接点，我们又要去输一遍它，这样太麻烦了。那么有什么办法呢？经过我的思考和研究，我们再输入完一个顶点（和它携带的邻接点）后，加一个算法，让这些邻接点和这个顶点关系一并接到这些以邻接点为顶点的邻接表上。具体处理如下：for(p=a-vertex[i].head;p!=NULL;p=p-next)/*无向图在邻接表中相互指向*/{if(p-adjvexi){if(a-vertex[p-adjvex].head==NULL)q=a-vertex[p-adjvex].head=(anode*)malloc(sizeof(anode));else{for(q=a-vertex[p-adjvex].head;q-next!=NULL;)q=q-next;q-next=(anode*)malloc(sizeof(anode));q=q-next;}q-next=NULL;q-adjvex=i;strcpy(q-rname,p-rname);q-weight=p-weight;}}七、源代码及相关文件主程序代码：#includestdio.h#includestring.h#includestdlib.h#defineinfinity32767#definemaxsize50typedefstruct{intstack[maxsize];inttop;}SeqStack;typedefstructarcnode//邻接表结构体{charrname[20];/*路名*/intadjvex;/*相邻景点序号*/intweight;/*路长*/structarcnode*next;}anode;typedefstructvertexnode{intvisit;/*访问标志*/charvexdata[20];/*景点名称*/charlv[10];/*景点等级*/chardiscribe[100];/*景点描述*/intin;/*入度*/intout;/*出度*/anode*head;}vnode;typedefstruct{vnodevertex[maxsize];intvexnum;/*景点数*/intarcnum;/*路数*/}adjlist;typedefstruct{intarcs[maxsize][maxsize];charspotname[maxsize][100];//景点名称intvexnum;//景点数}adjmartrix;voidestablish(adjlist*a)//把创建的图写入文件，放到creatgrahp(adjlist*a)中{inti,j;anode*p;FILE*sfp,*rfp;sfp=fopen(school.txt,wt);//创建新景点文件rfp=fopen(road.txt,wt);fprintf(sfp,%d%d\n,a-vexnum,a-arcnum);/*景点数和路数写到school中*/for(i=1;i=a-vexnum;i++)fprintf(sfp,%s%s%s%d%d\n,a-vertex[i].vexdata,a-vertex[i].lv,a-vertex[i].discribe,a-vertex[i].out,a-vertex[i].in);for(i=1;i=a-vexnum;i++)/*道路信息写到road中*/{p=a-vertex[i].head;if(a-vertex[i].out!=0){fprintf(rfp,%s%d%d\n,p-rname,p-adjvex,p-weight);p=p-next;}for(j=1;ja-vertex[i].out;j++){fprintf(rfp,%s%d%d\n,p-rname,p-adjvex,p-weight);p=p-next;}}fclose(sfp);//关闭文件fclose(rfp);//关闭文件}voidchurudu(adjlist*a)/*计算出度和入度*/{inti,n;anode*p;for(i=1;i=a-vexnum;i++)/*计算出度*///问题{p=a-vertex[i].head;if(p!=NULL){n=1;p=p-next;}elsen=0;while(p!=NULL){n++;p=p-next;}a-vertex[i].out=n;}for(i=1;i=a-vexnum;i++)a-vertex[i].in=0;/*在调用churudu()之前，原有景点入度变为0*/for(i=1;i=a-vexnum;i++)/*计算入度*/{p=a-vertex[i].head;while(p!=NULL){a-vertex[p-adjvex].in=a-vertex[p-adjvex].in+1;/*入度自增1*/p=p-next;}}}voidcreatgrahp(adjlist*a)/*创建图*/{inti,n,j;intflag=1;anode*p,*q;while(flag){printf(请输入景点数，路线数:\n);scanf(%d%d,&a-vexnum,&a-arcnum);if(a-arcnum(a-vexnum-1)*a-vexnum/2||a-arcnum==0)/*判断输入的景点数和路线数是否能构成一个图*/printf(输入有误，请重新输入:\n);elseflag=0;}flag=1;getchar();for(i=1;i=a-vexnum;i++)/*输入景点*/{printf(请输入第%d个景点名称:\n,i);scanf(%s,a-vertex[i].vexdata);printf(请输入该景点等级:\n);scanf(%s,a-vertex[i].lv);printf(请描述景点:\n);scanf(%s,a-vertex[i].discribe);a-vertex[i].head=NULL;/*头结点置空*/a-vertex[i].out=0;/*出度初始为0*/}for(i=1;i=a-vexnum;i++)/*输入相邻景点*/{getchar();printf(请输入剩余的%s的相邻景点个数:\n,a-vertex[i].vexdata);scanf(%d,&n);if(n0){p=a-vertex[i].head;if(p==NULL){p=a-vertex[i].head=(anode*)malloc(sizeof(anode));/*第一次要把邻接点和头结点链接*/while(flag){printf(请输入第1个相邻景点序号和距离:\n);scanf(%d%d,&p-adjvex,&p-weight);if(p-adjvex==i)printf(输入有误，请重新输入\n);elseflag=0;}flag=1;printf(请输入路名:\n);scanf(%s,p-rname);p-next=NULL;}else{for(;p-next!=NULL;p=p-next)//如果头结点不为空，则p向后移动，防止在邻接表中相互指向时头结点被篡改{;}n=n+1;//因为下面的for只适用于if完成之后的操作，为了适应else完成之后的操作，需要n自增1flag=0;}}for(j=1;jn;j++){q=(anode*)malloc(sizeof(anode));q-next=NULL;p-next=q;p=q;if(flag==1)printf(请输入第%d个相邻景点序号和距离:\n,j+1);elseprintf(请输入第%d个相邻景点序号和距离:\n,j);scanf(%d%d,&p-adjvex,&p-weight);printf(请输入路名:\n);scanf(%s,p-rname);}for(p=a-vertex[i].head;p!=NULL;p=p-next)/*无向图在邻接表中相互指向*/{if(p-adjvexi){if(a-vertex[p-adjvex].head==NULL)q=a-vertex[p-adjvex].hea