1、西安邮电大学数据结构校园导游系统课程设计报告西安郵電大學数据结构课程设计报告书系部名称计算机学院学生姓名崔斌专业名称计算机科学与技术专业班 级计科1106学号04111185指导教师 衡 霞时间2012年12月15日 至 2012年12月21日 实验题目：校园导游系统一、实验目的：为了让非本校的同学们，家长们能够充分了解本校-西安邮电大学。：实践数据结构所学知识。 二、实验内容：学校简易的俯视图。 ：各个景点的简单介绍。 ：任意两景点之间的所有路径。 ：任意两景点之间的最少中转景点路径。 ：任意两景点之间的带权路径长度。 三、需求分析Init();初始化两个顺序栈Menu();进行选择的模块函
2、数；Intro();景点介绍函数；Search();判断是否有此编号的景点；Findallpath();找路径函数；Findallway();找任意两个景点之间的所有路径；（存在栈里面）Shortestway();任意两个景点之间中转次数最少的路径；（从栈里面读取出来）Niceway();任意两个景点之间总权值最小的路径；（从栈里面读取出来）Calculate();（从栈里面读取出来相关数据），进行分析运算；Byebye(); 你懂得！四、概要设计1、方案设计 对系统进行分析，给出景区图重点：1：/思想；递归结合循环，然后，找到终点时还要回溯；void findallway(adjlist *
3、G,int m,int n)/两点之间的所有路径 int i,t,k; arcnode *p; pa_th rp; push(s,m); G-vertexm-1.flag=1; if(m=n) rp.sumweight=k=calculate(G); rp.sum=s-top; rp.num=(y+1); push1(&z,rp); printf( 路径%3d为(途径%2d个景点 ,长度为%3d)：,y+1,s-top,k); for(i=0;itop;i+) printf(-%d,s-elemi); printf(n); G-vertexm-1.flag=1; y+;/外部全局变量 else
4、 for(p=G-vertexm-1.firstarc;p!=NULL;p=p-nextarc) t=p-num; if(G-vertext-1.flag=0) findallway(G,t,n); G-vertexs-elems-top-1.flag=0;/两句顺序不可以调换 pops(s); 2：/从文件里读取数据；错误1；不知道此节点有几个邻接点，因为%s的原因，就会只把第一个节点的相关数据读出来，从第二个节点的相关信息处，开始读出错误（即烫烫烫烫烫烫烫烫烫烫烫）；为此，我在文件里面加了此节点的邻接点个数m，readnet（）里面又有count相加以监视不超过m;错误2；读文件时，因为有
5、链表的部分，就按照单链表的创建些写，结果总是此节点的最后一个邻接点没被读到内存里，究其原因，是最后一个p1没有连接到此条链表的尾部，（不仅我把p2-nextarc=NULL;还把free(p1);）void readnet(adjlist *G) int i,count,m; arcnode *head,*p2,*p1; FILE *fp; fp=fopen(U,rt); if(fp=NULL) printf(文件打开失败！);exit(0); for(i=0;ivertexi.num,G-vertexi.name,G-vertexi.introduce,&G-vertexi.sum,&G-v
6、ertexi.flag);/fprintf() 的后面不加第一个空格也可以。 m=G-vertexi.sum; p2=H;head=p2; p1=H; fscanf(fp,%d %d,&p1-num,&p1-weight);/fprintf() 的后面不加第一个空格也可以。 count=1; while(countnextarc=p1; p2=p1; p1=H; fscanf(fp,%d %d,&p1-num,&p1-weight);/fprintf() 的后面不加第一个空格也可以。 count+; p2-nextarc=p1;/千万不能忘掉此语句，令人蛋碎一地呀 p2=p1;/千万不能忘掉此
7、语句，令人蛋碎一地呀，否则会丢掉每个节点的最后一个邻接点 p2-nextarc=NULL; /free(p1);/千万不能有此语句，令人蛋碎一地呀 G-vertexi.firstarc=head-nextarc; fclose(fp); 2、数据结构说明程序中定义的数据类型结构体（各个成员的作用）；表定义：typedef struct Arcnode int num;/顶点编号 int weight;/顶点与此点之间路径的权值 struct Arcnode *nextarc;arcnode;typedef struct Vertexnode int num;/顶点编号 char name20;
8、/顶点景点名称 char introduce40;/景点简介 int sum;/与其他连接的景点个数 /令人蛋疼的读文件呀 int flag;/默认为0，刚好可以标志。 arcnode *firstarc;vertexnode;typedef struct AA vertexnode vertexMAX_vertex_num;/顶点数组 int other;/备用adjlist; 编号名称简介邻接点个数Flagfirstarc 五、详细设计及运行结果 六、调试情况，设计技巧及体会（重点） 1、测试数据 包括合法与非法的测试数据、预期结构和实测结果（最好用表格列出）读文件后本应为：1 超市 同学
9、们购物的天堂！ 2 02 1003 150 2 宿舍楼 同学们就寝，玩游戏的宝地。 2 01 1005 303 体育馆 锻炼身体，高校的体育交流之地。 2 01 1506 704 旭日苑 就餐之地1. 3 05 906 3007 1205 网吧 锻炼大脑，手指灵活性的地方。 3 02 304 907 1206 图书馆 书的海洋。 3 03 704 3008 407 美广 就餐之地2. 3 04 1205 2010 1108 大活 娱乐晚会举办地。 3 06 409 3012 2009 喷泉 哈哈，你懂得！ 3 08 3010 7013 4010 实验楼 下一个产生钱学森的圣地！ 3 07 11
10、09 7011 3011 教学楼 园丁与花朵！ 2 010 3013 10012 行政楼 学校领导办公之地。 2 08 20013 9013 北门 学校的正门。 2 011 10012 90但确只有：（每个邻接点的邻接点都少一个）1 超市 同学们购物的天堂！ 2 02 1002 宿舍楼 同学们就寝，玩游戏的宝地。 2 01 1003 体育馆 锻炼身体，高校的体育交流之地。 2 01 1504 旭日苑 就餐之地1. 3 05 906 3005 网吧 锻炼大脑，手指灵活性的地方。 3 02 304 906 图书馆 书的海洋。 3 03 704 3007 美广 就餐之地2. 3 04 1205 20
11、8 大活 娱乐晚会举办地。 3 06 409 309 喷泉 哈哈，你懂得！ 3 08 3010 7010 实验楼 下一个产生钱学森的圣地！ 3 07 1109 7011 教学楼 园丁与花朵！ 2 010 3012 行政楼 学校领导办公之地。 2 08 20013 北门 学校的正门。 2 011 100非法数据： 2、对调试中主要问题进行总结错误1；（读文件时）不知道此节点有几个邻接点，因为%s的原因，就会只把第一个节点的相关数据读出来，从第二个节点的相关信息处，开始读出错误（即烫烫烫烫烫烫烫烫烫烫烫）；为此，我在文件里面加了此节点的邻接点个数m，readnet（）里面又有count相加以监视不
12、超过m;错误2；读文件时，因为有链表的部分，就按照单链表的创建些写，结果总是此节点的最后一个邻接点没被读到内存里，究其原因，是最后一个p1没有连接到此条链表的尾部，（不仅我把p2-nextarc=NULL;还把free(p1);）还有，由于findallway()是循环与递归的结合，所以调试过程相当累。 3、对自己设计进行评价，指出合理和不足之处，提出改进的方案自己编写的，就有一份自豪感，但是也有问题；比如，找最小中转路径时，如果有相同的几个，那么就只能打印出一条路径。带权路径也一样。由于时间问题，没有改进，以后会改进的。 4、在设计过程中的感受感觉循环与递归的结合短小精悍，对于程序员分析问题
13、来说，就，你懂得！七、源程序清单(略，详见电子版实验报告)：#includecommon.h#includeseqstacki.h#includeschooltravel.h#define MAX_vertex_num 30#define H (arcnode *)malloc(sizeof(arcnode)#define U daoyou1.txt#define O (linkstacknode *)malloc(sizeof(linkstacknode)typedef struct Arcnode int num;/编号 int weight;/顶点与此点之间路径的权值 struct Ar
14、cnode *nextarc;arcnode;typedef struct Vertexnode int num;/编号 char name20;/顶点景点名称 char introduce40;/景点简介 int sum;/与他连接的景点个数 /令人蛋疼的读文件呀 int flag;/默认为0，刚好可以标志。 arcnode *firstarc;vertexnode;typedef struct AA vertexnode vertexMAX_vertex_num;/顶点数组 int other;/备用adjlist;void menu(adjlist *G);void intro(adjl
15、ist *G);int search(adjlist *G,int s);void findallpath(adjlist *G);void findallway(adjlist *G,int m,int n);void byebye();void readnet(adjlist *G);void Map();void shortestway(adjlist *G);int calculate(adjlist *G);void niceway(adjlist *G);void findweight(adjlist *G,int m,int n);seqstacki w,*s=&w;seqsta
16、ckpath z;int vnum=13;main() adjlist q,*G=&q; initstack(s); initstack1(&z); readnet(G);/读出文件 Map(); /printf(%dn,G-vertex4.firstarc-nextarc-nextarc-weight); menu(G);void menu(adjlist *G) int choice; Map(); printf(n n); printf(n 查看景点信息 ); printf(n 查寻两景点之间的路径 ); printf(n 一 退出系统 ); printf(n n); printf(nt
17、t你想选择？请选择(1-3): ); scanf(%d,&choice); while(choice3) printf(ntt输入错误，重新选择(1-3): ); scanf(%d,&choice); switch(choice) case 1:intro(G);break; case 2:findallpath(G);break; case 3:byebye();exit(0);break; void intro(adjlist *G)/景点信息 int choice; int k;/接收返回的数组下标值 Map(); printf(nt你想查看哪个景点的详细介绍呢？请按照本校平面图输入-标
18、号: ); scanf(%d,&choice); if(k=search(G,choice)+1)/判断是否存在此景点 printf(n%d号景点：nt%s-%s,choice,G-vertexk-1.name,G-vertexk-1.introduce);/k要-1,否则向后偏移一个景点 printf(nt(任意键返回主菜单)n);getch();menu(G);exit(0); else printf(nt不存在此景点！(任意键返回主菜单)n);getch();menu(G);exit(0); int search(adjlist *G,int s) int i; for(i=0;iver
19、texi.num=s) return(i); return(-1);/没有就返回-1int y=0;void findallpath(adjlist *G) int i,j;/两景点编号 Map(); printf(n你想查寻哪两个景点之间的路线呢？( - 间隔)请按照本校平面图输入-标号: ); scanf(%d-%d,&i,&j); if(0i=vnum&0j=vnum&i!=j)/景点编号大于景点树木，必然不存在次景点 findallway(G,i,j);/所有路径 printf(nt共有%d条路径！ n,y); y=0;/很重要，否则查询几次，她就一直叠加。 shortestway(G
20、);/最短路径 广度优先 niceway(G);/最佳访问路径 地界斯科拉算法 initstack(s);/找完所有路径后，必须初始化栈，否则 栈可能满而溢出 initstack1(&z);/找完所有路径后，必须初始化栈，否则 栈可能满而溢出 else printf(不存在此景点或者 起点和终点是同一点！(任意键返回主菜单); getch(); menu(G); exit(0); printf(n (任意键返回主菜单); getch();menu(G); exit(0);void shortestway(adjlist *G) int i,max,min,k,t;/不可以直接 int max=
21、min=z.elem0; max=min=z.elem0.sum; for(i=1;i=z.elemi.sum) min=z.elemi.sum; k=i; if(max=z.elemi.sum) max=z.elemi.sum; t=i; if(min=z.elem0.sum) k=0; if(max=z.elem0.sum) t=0; printf(nt最短路径为： %3d号路径，途径%2d个景点!n,z.elemk.num,min); printf(nt最长路径为： %3d号路径，途径%2d个景点!n,z.elemt.num,max); void niceway(adjlist *G)
22、int i,max,min,k,t;/不可以直接 int max=min=z.elem0; max=min=z.elem0.sumweight; for(i=1;iz.elemi.sumweight) min=z.elemi.sumweight; k=i; if(maxvertexm-1.flag=1; if(m=n) rp.sumweight=k=calculate(G); rp.sum=s-top; rp.num=(y+1); push1(&z,rp); printf( 路径%3d为(途径%2d个景点 ,长度为%3d)：,y+1,s-top,k); for(i=0;itop;i+) pri
23、ntf(-%d,s-elemi); printf(n); G-vertexm-1.flag=1; y+; else for(p=G-vertexm-1.firstarc;p!=NULL;p=p-nextarc) t=p-num; if(G-vertext-1.flag=0) findallway(G,t,n); G-vertexs-elems-top-1.flag=0;/两句顺序不可以调换 pops(s); int calculate(adjlist *G) int i; int sum=0; for(i=0;itop;i+) findweight(&sum,G,search(G,s-elem
24、i),i); return(sum); void findweight(int *sum,adjlist *G,int m,int n) arcnode *p; for(p=G-vertexm.firstarc;p!=NULL;p=p-nextarc) if(p-num=s-elemn+1) *sum+=p-weight;break; void byebye() system(cls); printf(nnnn); printf(tt/*$ . n); printf(tt./ 圣诞 .快乐 * $ * n); printf(tt/ . * $ * n); printf(tt.田田 | .* $ * n); printf(tt& | * $ * n); printf(tt 愿你圣诞快乐| nnnn); printf( 制作人:崔斌 n); printf(=n); printf( Bye-Byen); printf(n); printf( n); printf(n); printf( n); printf( n); printf(n); printf( n); print
