校园导游程序报告.doc

《校园导游程序报告.doc》由会员分享，可在线阅读，更多相关《校园导游程序报告.doc（16页珍藏版）》请在三一文库上搜索。

1、校园导游程序报告一、 问题分析和任务定义1、 题目与要求 校园导游程序题目：用无向网表示你所在学校的校园景点平面图，图中定点表示主要景点，存放 景点的编号、名称、简介等信息。要求能够回答有关景点介绍、游览路经等问题。要求：(1)查询各景点相关信息； (2)查询图中任意两个景点的最短路径。 (3)查询图中任意两个景点的所有路径。.选作内容：求多个景点的最佳游览路经。根据设计的基本要求，可知本系统应实现以下几个功能： (1)景点查询：景点查询，输出所查询景点的相关信息 (2)景点之间最佳路径查询功能：输出所选择的两点之间的最短路径及路径长度。(3)两景点间所有路径：输出两点间存在的所有路径。2、

2、问题分析确定以无向图为数据结构的校园地图如图1：体育场7南校门1行政楼2礼堂6东校门3主教 学区4图书馆5食堂8宿舍区9荷塘10图1校园地图图的信息以邻接矩阵形式存储，邻接矩阵以二维数组的数据结构存储。costij； 当i=j时及i点与j点无直接连通时，其值为无穷大，定义一个很大的整数Maxint代替无穷大。当i与j点邻接时，其值为两点间的权值即两景点距离。（1）、查询景点信息 将相应景点信息存入文本文档中，依据需要调用读取文件，并显示在屏幕上。（2）、两点间最短路径 利用迪杰斯特拉（Dirjstra）算法求两点之间最短路径。（3）、两点间所有路径 利用邻接矩阵转换为邻接表，以邻接表的遍历查找

3、路径，并将路径暂时存储，最后一次将各路径输出。3、 任务定义设计creat （）；函数存入图的矩阵信息。设计infor （）；函数查询景点信息。设计DJ_shortestpath （）；函数利用迪杰斯特拉算法求最短路径。设计Allpath （）；函数求两点间所有路径。4、 程序实现功能查询某景点信息。查找两景点间最短路径。查找两景点间所有路径。二、 数据结构的选择和概要设计1、 数据结构的定义图的定义：图的信息以邻接矩阵存储，利用二维数组作为矩阵坐标，二维数组的值表示图的两点间的距离，即无向图的权值，若两点间无直接路径，则以无穷大为权值。 景点相关信息： 景点相关信息以文本文档存储，利用函数直

4、接读取文本输出。 景点名称输出 以结构体存储各个景点编号及相对的名称，以便于输出显示。 struct PlaceName char name10; Place11;2、 概要设计主函数：调用各子函数完成选择功能。 主函数中以switch语句选择操作。查询景点信息1查找路径2查找所有路径3退出程序4 程序框架图如图2主函数Dirjstra算法最短路径邻接矩阵转换邻接表创建图输入临接矩阵遍历输出所有路径查询景点相关信息图2程序框架图三、 详细设计和编码迪杰斯特拉算法核心思想：把图的顶点集合V分成两个子集，第一个子集包含已确定了最短路径的顶点，令其为S，第二个子集（V-S）包含尚未确定最短路径的顶点

5、。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v出发可以到达的所有顶点都包含在S中。在这个过程中，总保持从v到S中各顶点的最短路径的长度都不大于从v到V-S中的任何顶点的最短路径的长度。另外，每个顶点对应一个距离值，S中的定点的距离值就是从v到此顶点的最短路径的长度，V-S中的顶点的距离值是从v到此顶点的只包括S中的顶点的最短路径长度。当然，每当把一个顶点从V-S移到S中去后，必须对V-S中剩余的顶点的距离值进行调整。算法步骤如下： 初始时，S只包括顶点v，即S= v ，V-S包括其他所有顶点，v的距离值为0，V-S中的顶点的距离值是这样确定的：对V-S中的任意顶点w，若图中

6、有边，则w的距离为此边上的权值，否则w的距离值为（或用一个很大的数表示，程序中用Maxint=9999表示）。 然后从V-S中选择一个距离值最小的顶点k加入到S中去，此时k的距离值恰好就是从v到它的最短路径的长度。 S中加入一个顶点k后，对V-S中的各个顶点的距离值进行一次修正。对V-S中的任意顶点w，若k的距离值加上边上的权值小于w的原距离值，则将w的距离值调整为k的距离值与边上的权值之和，否则w的距离值保持不变。 重复步骤和，知道所有顶点都已包括在S中为止，即知道S=V为止。 在函数 DJ_shortestpath （）；中实现了迪杰斯特拉算法。 图的大家邻接矩阵存储在二维数组cost中，

7、数组dist存放各顶点的当前距离值。程序中用Maxint=9999表示。数组path存放各定点在最短路径中的直接前驱。算法执行完毕后，dist中的值即为最短路径的长度，最短路径可以从path求得。数组dianji记录了顶点是否在S中，dianjii=1表示顶点i在S中，dianjii=0表示顶点i不在S中。 输出最短路径：由path中的各定点的直接前驱倒序遍历最短路径并存入临时数组temp中，然后倒序输出temp并以temp的值为下标调用景点名称数组Place以直接显示景点名称（将景点编号转换为字符名称输出）。dist中的值为两景点最短路径的路径长度。 景点信息查询： 将景点信息预先写入文本文

8、档A1.txt A10.txt中，输入要查询的景点标号x。 switch （x） case 1： 读取A1.txt中信息；case 2： 读取A2.txt中信息；case 3： 读取A3.txt中信息；case 4： 读取A4.txt中信息；case 5： 读取A5.txt中信息；case 6： 读取A6.txt中信息；case 7： 读取A7.txt中信息；case 8： 读取A8.txt中信息；case 9： 读取A9.txt中信息；case 10： 读取A10.txt中信息；各文件内容如下图图3各文件内容两点间所有路径： 定义临时存储用栈。邻接矩阵转换为邻接表。 对邻接矩阵进行遍历，将遍

9、历路径存入栈中。 输出栈中元素。 回溯再遍历。直到完全遍历整个邻接表。四、 上机调试首先遇到的难题是图的定义，对于本程序，常规的图的创建已经不利于算法的优化，经过考虑，最后决定定义全局变量二维数组，直接存储图的邻接矩阵。其次，从未接触过的迪杰斯特拉算法让我开始时手足无措，去图书馆借了资料从头学习了迪杰斯特拉算法的核心思想，并对书本的案例程序进行了分块结构化，最后确定的迪杰斯特拉算法的具体实现方法。对于景点查询一块，本来想法是将景点相关信息存入图的顶点信息结构体中，后来发现这样会将图信息的初始化复杂化，后来决定将相关信息写入文本文档，利用函数调用读取文件信息完成景点查询。最难的就是所有路径问题，

10、在经过一本一本书的搜索淘汰，一个网页一个网页的搜索淘汰，最后在同学的帮助下完成了算法，但是觉得这个算法太复杂，应该有更好的，却觉得已经力不从心了。经常出现的错误： 初始化函数creat （）；未调用，使得邻接矩阵无数据，最后无运算结果输出。 对文件的读取格式不规范，显示的只是文件的片段或乱码。 输出路径的临时存储数组的输出接点起始错误，逆序的初始状态为非空结点的最大下标开始至0结束，下标变量i不能再次被赋值，否则会出错。程序中存在的问题： 程序部分算法扔有待改进优化。 在路径的输出结果中会出现错误输出。 若两点间有两条长度相同的路径，且为最短路径，程序只能输出其中之一。经验体会 相对于其他同学

11、的课程设计题目，这个题目的难度高了很多，同样含金量也很高，思索，写代码，画算法，改错，删除、删除、再删除，难题接踵而至，未遇到的算法，未曾想过的问题都出现了。两个星期做一个程序还未能尽善尽美的完成它，让我深感对数据结构一门课程学习的不足。也让我对课程设计这门课有了新的认识。数据结构刚开始时老师说，我教给你们的不是编程。当初想，这整本书都是说编程的，怎么会“不是编程”？现在明白了算法一词的重要性，编程的核心是算法的掌握。以前的程序语言的学习只是像学外语学了单词一样，会使用了编程的工具，认识了编程的单词，真正的编程是算法的学习，就像是外语的语法的掌握一样重要。这个程序所涉及的图的知识及迪杰斯特拉算

12、法等知识均是离散数学和图论等数学课程中的知识，对数学知识的学习不足，接触不深，部分数学知识未学习的我难度又加大了一层，使得行动步步都捉襟见肘。知识的学习和应用不是专业局限性的，知识之间是广泛联系的，数学与计算机专业知识之间的联系异常紧密。五、 测试结果及其分析1、主函数及主菜单的输出图42、查询景点信息选择测试数据景点编号5。测试结果如下3、 查找最短路径测试数据 南校门至体育场路径结果如下： 图54、 查找所有路径测试数据 行政楼至主教学区结果如下 （为完全显示）图65、 结束程序结果如下图7六、 用户使用说明1、 主菜单界面程序运行进入主菜单可以看到选择操作菜单如下图图82、 由菜单显示信

13、息选择相应操作（1）、选择1，查询景点信息 输入景点编号。 程序输出景点相关信息。（2）、选择2，查找两点间最短路径 按提示依次输入起点景点编号及终点景点编号。 程序输出建议路径即为两点间最短路径。（3）、选择3，查找所有路径 按提示输入查找的两点。 程序输出两点间所有路径。（4）、选择4，退出程序 程序循环运行结束。 若不选择4操作，程序将继续等待操作选择不结束。3、 程序编译环境为Microsoft Visual C+ 6.0。七、 参考文献：1、谭浩强.C程序设计(第三版).北京：清华大学出版社，2005年7月2、王昆仑。数据结构与算法。北京：中国铁道出版社，2007年6月第1版3、章炯

14、民，窦亮，黄国兴。数据结构与算法教程。上海：华东师范大学出版社，2007年7月第1版4、侯风巍。数据结构要点分析C语言版。北京：北京航空航天大学出版社，2007年3月第1版八、 附录源程序代码： / *校园导游程序#include #include #include #include #define Maxn 20#define Maxint 999int pathMaxnMaxn;int n=10; /顶点数int e=13; /边数int costMaxnMaxn; /邻接矩阵struct PlaceName char name10; Place11;struct PlaceName Pl

15、ace11=,南校门,行政楼,东校门,主教学区,图书馆,礼堂,体育场,食堂,宿舍区,荷塘,; /景点名结构数组void *creat() /输入邻接矩阵 int i,j; for (i=1;i=n;i+) for (j=1;j=n;j+) costij=Maxint; /置空邻接表cost12=cost21=5;cost13=cost31=10;cost14=cost41=5;cost26=cost62=2;cost34=cost43=4;cost37=cost73=7;cost45=cost54=2;cost410=cost104=3;cost56=cost65=3;cost59=cost9

16、5=8;cost69=cost96=5;cost78=cost87=2;cost89=cost98=5;cost910=cost109=3; /赋值邻接表return cost;void infor (int p) /查询景点信息char *st;int flen; FILE *fp; switch (p) /选择文件读取路径 case 1: fp=fopen(A1.txt,r); break; case 2: fp=fopen(A2.txt,r); break; case 3: fp=fopen(A3.txt,r); break; case 4: fp=fopen(A4.txt,r); br

17、eak; case 5: fp=fopen(A5.txt,r); break; case 6: fp=fopen(A6.txt,r); break; case 7: fp=fopen(A7.txt,r); break; case 8: fp=fopen(A8.txt,r); break; case 9: fp=fopen(A9.txt,r); break; case 10: fp=fopen(A10.txt,r); break; fseek (fp,0L,SEEK_END); /文件尾 flen=ftell(fp); /文件长度 st= (char *)malloc (flen+1); fse

18、ek (fp,0L,SEEK_SET); /文件尾 fread (st,flen,1,fp); stflen=0; printf (%s,st); printf (n); fclose (fp); free (st); /由文本提取景点信息void DJ_shortestpath(int v0,int v1) /最短路径函数（dirjstra算法）int tempMaxn;int t=0;int i,j,k;int min,pre;int distMaxn; /存放顶点i的当前最短路径长度int pathMaxn; /存放顶点i的最短路径上的前驱顶点int dianjiMaxn; /若 dia

19、njii=1,则顶点属于在最短路径顶点集合中for (i=1;i=n;i+)/初始化disti,pathidisti=costv0i;if (distiMaxint)pathi=v0;else pathi=-1;for (i=1;i=n;i+) dianjii=0;dianjiv0=1; distv0=0; for(i=1;in;i+) min=Maxint; for(j=1;j=n;j+) if(!dianjij)&(distjmin) min=distj; k=j; dianjik=1; for(j=1;j=10;j+) if(!dianjij) & (distk+costkj%s最短距离

20、是%d00米nn,Placev0.name,Placev1.name,distv1); printf (建议路径：n);pre=pathv1;while(pre!=-1) /路径倒序存入临时数组 tempt+=pre; pre=pathpre; for (i=t-1;i=0;i-)printf (%s=,Placetempi.name); /倒序输出临时数组printf (%s,Placev1.name);printf(nn);typedef struct st1int adjvex; struct st1 *nextarc; Arcnode; /结点类型typedef struct Vexn

21、odeArcnode *firstarc;Vexnode,Adjlist11; /表头结点typedef structAdjlist vextices;int vexnum,arcnum;Algraph; /邻接表类型Algraph alg; /定义邻接表typedef struct /栈结构 int dataMaxn; int top;Seqstack;Seqstack *setstack() /创建栈Seqstack *S;S=(Seqstack *)malloc(sizeof(Seqstack);S-top=-1;return S;int stackempty(Seqstack *S)

22、/判栈空if(S-top=0) return 0;else return 1;void push(Seqstack *S,int x) /入栈if(S-toptop=-1)S-top+;S-dataS-top=x;else printf(error);void pop(Seqstack *S) /出栈if(S-top=0) S-top-;else printf(error!);Seqstack *S;Algraph creat_Adjlistgraph() /转换邻接表int i,j;Arcnode *p,*q;Adjlist al; for(i=0;i=n;i+) /初始化表头结点数组ali

23、.firstarc=NULL; for(i=0;i=n;i+) for(j=0;jadjvex=j; p-nextarc=ali.firstarc; ali.firstarc=p; q=(Arcnode *)malloc(sizeof(Arcnode); q-adjvex=i; q-nextarc=alj.firstarc; alj.firstarc=q; for(i=0;idataS-top; p=alg.vexticesk.firstarc; /栈初始化 while(p!=NULL) if(visitp-adjvex=0) if(p-adjvex=j) /输出栈中元素 for(i=0;it

24、op+1;i+) if (S-datai!=0) printf(%s=,PlaceS-datai.name); printf(%sn,Placej.name); else visitp-adjvex=1; push(S,p-adjvex); PathSearch(j); p=p-nextarc; visitS-dataS-top=0; pop(S);void Allpath() /两点之间的所有路径 int i,j;S=setstack();for(i=0;i%s 所有路径如下：n,Placei.name,Placej.name);push(S,i);visiti=1;while(stacke

25、mpty(S)!=1)PathSearch(j); /调用路径函数 main () /主函数 int s,o; int w,x,p; Algraph alg; creat (); printf (tt=校园地图=n); printf (景点编号如下n); for (w=0;w10;w+) printf (%dt%stt,w+1,Placew+1.name); if (w%2=1) printf (n); for (; ;) printf (nt查询景点信息1nt查找路径2nt查找所有路径3nt退出程序4n); printf (请选择操作：); scanf (%d,&x); switch (x) case 1: printf (输入待查询景点编号：);scanf (%d,&p);infor (p);printf (n);break; case 2: printf (输入起点编号：); scanf (%d,&s); printf (输入终点编号：); scanf (%d,&o); DJ_shortestpath(s,o);printf (n);break; case 3: alg=creat_Adjlistgraph(); Allpath();break; case 4: printf (结束程序！); if (x=4) break;