西安郵電大學
数据结构课程设计报告书
系部名称 学生姓名 专业名称 班 级 学
号
计算机学院
崔斌
计算机科学与技术专业
计科1106 04111185
指导教师
衡 霞
2012年12月15日 至
时间
2012年12月21日
实验题目：校园导游系统
一、实验目的
①：为了让非本校的同学们，家长们能够充分了解本校---西安邮电大学。 ②：实践数据结构所学知识。
二、实验内容
①：学校简易的俯视图。 ②：各个景点的简单介绍。
③：任意两景点之间的所有路径。
④：任意两景点之间的最少中转景点路径。 ⑤：任意两景点之间的带权路径长度。
三、需求分析
Main(); Init(); Menu(); Intro SearchFinallpath(); Byebye(); Finfallway Shortestway() Niceway() CalculaInit();初始化两个顺序栈
Menu();进行选择的模块函数； Intro();景点介绍函数；
Search();判断是否有此编号的景点； Findallpath();找路径函数；
Findallway();找任意两个景点之间的所有路径；（存在栈里面） Shortestway();任意两个景点之间中转次数最少的路径；（从栈里面读取出来） Niceway();任意两个景点之间总权值最小的路径；（从栈里面读取出来）
Calculate();（从栈里面读取出来相关数据），进行分析运算； Byebye(); 你懂得！
四、概要设计
1、方案设计
对系统进行分析，给出景区图
重点：
① ：
//思想；递归结合循环，然后，找到终点时还要回溯；
void findallway(adjlist *G,int m,int n)//两点之间的所有路径 { int i,t,k; arcnode *p; pa_th rp; push(s,m);
G->vertex[m-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)：\ for(i=0;i<=s->top;i++) printf(\"->%d\ printf(\"\\n\"); G->vertex[m-1].flag=1; y++;//外部全局变量 }
}
else for(p=G->vertex[m-1].firstarc;p!=NULL;p=p->nextarc) { t=p->num; if(G->vertex[t-1].flag==0) findallway(G,t,n); }
G->vertex[s->elem[s->top]-1].flag=0;//两句顺序不可以调换 pops(s);
② ：
//从文件里读取数据；
错误1；不知道此节点有几个邻接点，因为%s的原因，就会只把第一个节点的相关数据读出来，从第二个节点的相关信息处，开始读出错误（即烫烫烫烫烫烫烫烫烫烫烫）；为此，我在文件里面加了此节点的邻接点个数m，readnet（）里面又有count相加以监视不超过m;
错误2；读文件时，因为有链表的部分，就按照单链表的创建些写，结果总是此节点的最后一个邻接点没被读到内存里，究其原因，是最后一个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;i 2、数据结构说明 程序中定义的数据类型——结构体（各个成员的作用）； 表定义： typedef struct Arcnode { int num;//顶点编号 int weight;//顶点与此点之间路径的权值 struct Arcnode *nextarc; }arcnode; typedef struct Vertexnode { int num;//顶点编号 char name[20];//顶点景点名称 char introduce[40];//景点简介 int sum;//与其他连接的景点个数 //令人蛋疼的读文件呀 int flag;//默认为0，刚好可以标志。 arcnode *firstarc; }vertexnode; typedef struct AA { vertexnode vertex[MAX_vertex_num];//顶点数组 int other;//备用 }adjlist; 编名简邻号 称 介 接点个数 Flag f irstarc 五、详细设计及运行结果 六、调试情况，设计技巧及体会（重点） 1、测试数据 包括合法与非法的测试数据、预期结构和实测结果（最好用表格列出） 读文件后本应为： 1 超市 同学们购物的天堂！ 2 0 2 100 3 150 2 宿舍楼 同学们就寝，玩游戏的宝地。 2 0 1 100 5 30 3 体育馆 锻炼身体，高校的体育交流之地。 2 0 1 150 6 70 4 旭日苑 就餐之地1. 3 0 5 90 6 300 7 120 5 网吧 锻炼大脑，手指灵活性的地方。 3 0 2 30 4 90 7 120 6 图书馆 书的海洋。 3 0 3 70 4 300 8 40 7 美广 就餐之地2. 3 0 4 120 5 20 10 110 8 大活 娱乐晚会举办地。 3 0 6 40 9 30 12 200 9 喷泉 哈哈，你懂得！ 3 0 8 30 10 70 13 40 10 实验楼 下一个产生钱学森的圣地！ 3 0 7 110 9 70 11 30 11 教学楼 园丁与花朵！ 2 0 10 30 13 100 12 行政楼 学校领导办公之地。 2 0 8 200 13 90 13 北门 学校的正门。 2 0 11 100 12 90 但确只有：（每个邻接点的邻接点都少一个） 1 超市 同学们购物的天堂！ 2 0 2 100 2 宿舍楼 同学们就寝，玩游戏的宝地。 2 0 1 100 3 体育馆 锻炼身体，高校的体育交流之地。 2 0 1 150 4 旭日苑 就餐之地1. 3 0 5 90 6 300 5 网吧 锻炼大脑，手指灵活性的地方。 3 0 2 30 4 90 6 图书馆 书的海洋。 3 0 3 70 4 300 7 美广 就餐之地2. 3 0 4 120 5 20 8 大活 娱乐晚会举办地。 3 0 6 40 9 30 9 喷泉 哈哈，你懂得！ 3 0 8 30 10 70 10 实验楼 下一个产生钱学森的圣地！ 3 0 7 110 9 70 11 教学楼 园丁与花朵！ 2 0 10 30 12 行政楼 学校领导办公之地。 2 0 8 200 13 北门 学校的正门。 2 0 11 100 非法数据： 2、对调试中主要问题进行总结 错误1；（读文件时）不知道此节点有几个邻接点，因为%s的原因，就会只把第一个节点的相关数据读出来，从第二个节点的相关信息处，开始读出错误（即烫烫烫烫烫烫烫烫烫烫烫）；为此，我在文件里面加了此节点的邻接点个数m，readnet（）里面又有count相加以监视不超过m; 错误2；读文件时，因为有链表的部分，就按照单链表的创建些写，结果总是此节点的最后一个邻接点没被读到内存里，究其原因，是最后一个p1没有连接到此条链表的尾部，（不仅我把p2->nextarc=NULL;还把free(p1);） 还有，由于findallway()是循环与递归的结合，所以调试过程相当累。 3、对自己设计进行评价，指出合理和不足之处，提出改进的方案 自己编写的，就有一份自豪感，但是也有问题；比如，找最小中转路径时，如果有相同的几个，那么就只能打印出一条路径。带权路径也一样。由于时间问题，没有改进，以后会改进的。 4、在设计过程中的感受 感觉循环与递归的结合短小精悍，对于程序员分析问题来说，就，你懂得！ 七、源程序清单(略，详见电子版实验报告) ❶： #include\"common.h\" #include\"seqstacki.h\" #include\"schooltravel.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 Arcnode *nextarc; }arcnode; typedef struct Vertexnode { int num;//编号 char name[20];//顶点景点名称 char introduce[40];//景点简介 int sum;//与他连接的景点个数 //令人蛋疼的读文件呀 int flag;//默认为0，刚好可以标志。 arcnode *firstarc; }vertexnode; typedef struct AA { vertexnode vertex[MAX_vertex_num];//顶点数组 int other;//备用 }adjlist; void menu(adjlist *G); void intro(adjlist *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; seqstackpath z; int vnum=13; main() { adjlist q,*G=&q; initstack(s); initstack1(&z); readnet(G);//读出文件 Map(); //printf(\"%d\\n\ menu(G); } void menu(adjlist *G) { int choice; Map(); printf(\"\\n ┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳\\n\"); printf(\"\\n ┣┃ ●① ◣查看景点信息 ┃┫\"); printf(\"\\n ┣┃ ●② ◣查寻两景点之间的路径 ┃┫\"); printf(\"\\n ┣┃ ︻┳═一 ●③ ◣退出系统 ┃┫\"); printf(\"\\n ┻┻┻┻┻┻┻┻︷︷︷︷︷︷︷︷︷︷︷︷︷︷︷┻┻┻┻┻┻┻\\n\"); printf(\"\\n\\你想选择？请选择(1-3):\" ); scanf(\"%d\ while(choice<1||choice>3) { printf(\"\\n\\输入错误，重新选择(1-3):\" ); scanf(\"%d\ } 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(\"\\n\你想查看哪个景点的详细介绍呢？请按照本校平面图输入--标号:\" ); scanf(\"%d\ if((k=search(G,choice)+1))//判断是否存在此景点 { printf(\"\\n%d号景点：\\n\%s--%s\要-1,否则向后偏移一个景点 printf(\"\\n\(任意键返回主菜单)\\n\");getch();menu(G);exit(0);; } else { printf(\"\\n\不存在此景点！！(任意键返回主菜单)\\n\");getch();menu(G);exit(0); } } int search(adjlist *G,int s) { int i; for(i=0;i int y=0; void findallpath(adjlist *G) { int i,j;//两景点编号 Map(); printf(\"\\n你想查寻哪两个景点之间的路线呢？( - 间隔)请按照本校平面图输入--标号: \" ); scanf(\"%d-%d\ if(0 void shortestway(adjlist *G) { int i,max,min,k,t;//不可以直接 int max=min=z.elem[0]; max=min=z.elem[0].sum; for(i=1;i<=z.top;i++) { if(min>=z.elem[i].sum) { min=z.elem[i].sum; k=i; } if(max<=z.elem[i].sum) { max=z.elem[i].sum; t=i; } } if(min==z.elem[0].sum) k=0; if(max==z.elem[0].sum) t=0; printf(\"\\n\最短路径为： %3d号路径，途径%2d个景点!!\\n\ printf(\"\\n\最长路径为： %3d号路径，途径%2d个景点!!\\n\ } void niceway(adjlist *G) { int i,max,min,k,t;//不可以直接 int max=min=z.elem[0]; max=min=z.elem[0].sumweight; for(i=1;i<=z.top;i++) { if(min>z.elem[i].sumweight) { min=z.elem[i].sumweight; k=i; } if(max push(s,m); G->vertex[m-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)：\ for(i=0;i<=s->top;i++) printf(\"->%d\ printf(\"\\n\"); G->vertex[m-1].flag=1; y++; } else for(p=G->vertex[m-1].firstarc;p!=NULL;p=p->nextarc) { t=p->num; if(G->vertex[t-1].flag==0) findallway(G,t,n); } G->vertex[s->elem[s->top]-1].flag=0;//两句顺序不可以调换 pops(s); } int calculate(adjlist *G) { int i; int sum=0; for(i=0;i<=s->top;i++) { findweight(&sum,G,search(G,s->elem[i]),i); } return(sum); } void findweight(int *sum,adjlist *G,int m,int n) { arcnode *p; for(p=G->vertex[m].firstarc;p!=NULL;p=p->nextarc) if(p->num==s->elem[n+1]) { *sum+=p->weight;break; } } void byebye() { system(\"cls\"); printf(\"\\n\\n\\n\\n\"); printf(\"\\ /\\~~~~~~~~~~~~~\\ ▓ ^*^ ☆ $$ .☆ \\n\"); printf(\"\\ ./ \\~~~▓~ ~~~~\\ ◆ 圣诞 .快乐 * $◢◣$ * \\n\"); printf(\"\\ / ^^ \\ ══════\\.◆ * * * $◢★◣$ * \\n\"); printf(\"\\ ..▎[] ▎田 田 ▎ |┃◆ . * $◢■■◣$ * \\n\"); printf(\"\\ &&▎ ▎ ▎'|'▎ @ * $◢■■■◣$ * \\n\"); printf(\"\\＃ ■■■■■■■■■■〓▄▃▂▁愿你圣诞快乐︸︸||︸︸ \\n\\n\\n\\n\"); printf(\" 制作人:崔斌 \\n\"); printf(\"================================================================================\\n\"); printf(\" ●☆☆Bye-Bye☆☆●\\n\"); printf(\"\\n\"); printf(\" ★★★★★★★★★★★★★★ ★★★★★★★★★★★★★★\\n\"); printf(\"\\n\"); printf(\" \\n\"); printf(\" ☆☆☆☆☆☆☆☆☆☆☆\\n\"); printf(\"\\n\"); printf(\" ★★★★★★★★★★★\\n\"); printf(\" 西 ★ 计 \\n\"); printf(\" 安 ★ 算 \\n\"); printf(\" 邮 ★ 机 \\n\"); printf(\" 电 ★ 科 \\n\"); printf(\" 大 ★ 学 \\n\"); printf(\" 学 ★ 与 \\n\"); printf(\" ★ 技 \\n\"); printf(\" ★ 术 \\n\"); printf(\" ★ 11 \\n\"); printf(\" ★ 级 \\n\"); printf(\" ★ 6 \\n\"); printf(\" ★ 班 \\n\"); printf(\" ◆谢谢使用◆\\n\\n\\n\"); printf(\"\\\\\\\\-----感谢学姐\\n\\n\\n\"); } void Map() { system(\"cls\"); printf(\"\\n\\n\"); printf(\"\\┏┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┳┓\\n\\n\"); printf(\"\\┣ 西安邮电学院校园图 ┫\\n\\n\"); printf(\"\\┣╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬┫\\n\"); printf(\"\\┣ ┏━━━┓ ┫\\n\"); printf(\"\\┣ ╔═══════┫①超市┣════┳━━━┓ ┫\\n\"); printf(\"\\┣ ║ ┗━━━┛ ┃②宿舍┃ ┫\\n\"); printf(\"\\┣ ║ ┗━━┳┛ ┫\\n\"); printf(\"\\┣ ┏③┓ ┏━━━━━┓ ║ ┫\\n\"); printf(\"\\┣ ┃体┃ ┃ 旭 ┃ ║ ┫\\n\"); printf(\"\\┣ ┃育┃ ┃ ④ ┃ ┏⑤━┓┫\\n\"); printf(\"\\┣ ┃馆┃ ┣━━日━━┣ ════┫网吧┃┫\\n\"); printf(\"\\┣ ┗┳┛ ┃ ┃ ┗┳━┛┫\\n\"); printf(\"\\┣ ║ ┃ 苑 ┃ ║ ┫\\n\"); printf(\"\\┣ ║ ┗┳━━┳━┛ ║ ┫\\n\"); printf(\"\\┣ ║┏━━━━━┓ ║ ║ ┏━━┓ ║ ┫\\n\"); printf(\"\\┣ ┗┫ ⑥图书馆 ┣ ┛ ┗ ══⑦美广┣═╝ ┫\\n\"); printf(\"\\┣ ┣━━━━━┛ ┗━┳┛ ┫\\n\"); printf(\"\\┣┏⑧━┫ ┏━━━┻━┓ ┫\\n\"); printf(\"\\┣┃大学┃ ┃ 实 ┃ ┫\\n\"); printf(\"\\┣┃生活┃ ┏━━┓ ┃ ⑩ 验 ┃ ┫\\n\"); printf(\"\\┣┃动中┣════ ⑨喷泉┣══ ┫ 楼 ┃ ┫\\n\"); printf(\"\\┣┃ 心 ┃ ┗ ┳ ┛ ┗━━┳━━┛ ┫\\n\"); printf(\"\\┣┗━┳┛ ║ ║ ┫\\n\"); printf(\"\\┣ ║ ║ ┏━━┻━━┓ ┫\\n\"); printf(\"\\┣ ║ ║ ┃ ⑾教学楼 ┃ ┫\\n\"); printf(\"\\┣ ║ ║ ┗━━┳━━┛ ┫\\n\"); printf(\"\\┣┏━⑿━┓ ║ ║ ┫\\n\"); printf(\"\\┣┃行政楼┃ ║ ║ ┏━━━┓ ┫\\n\"); printf(\"\\┣┗━━━┻══┳━━⒀━━┳════┛ ┃东╬西┃ ┫\\n\"); printf(\"\\┣ ┗ 北门 ┛ ┗━━━┛ ┫\\n\"); printf(\"\\┗┻┻┻┻┻┻┻┻┻ ┻┻┻┻┻┻┻┻┻┻┻┻┻┛\\n\"); printf(\"\\n\\n\\n\"); } 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;i printf(\"================================================================================\\n\"); printf(\" ●☆☆WelComE☆☆●\\n\"); getchar(); fclose(fp); } ❷： Common.h里的内容： #include （长的为：编号 简介 邻接点个数 flag标志—短的为：邻接点编号 上面顶点到此的权值） Daoyou1.txt里的内容： 1 超市 同学们购物的天堂！ 2 0 2 100 3 150 2 宿舍楼 同学们就寝，玩游戏的宝地。 2 0 1 100 5 30 3 体育馆 锻炼身体，高校的体育交流之地。 2 0 1 150 6 70 4 旭日苑 就餐之地1. 3 0 5 90 6 300 7 120 5 网吧 锻炼大脑，手指灵活性的地方。 3 0 2 30 4 90 7 120 6 图书馆 书的海洋。 3 0 3 70 4 300 8 40 7 美广 就餐之地2. 3 0 4 120 5 20 10 110 8 大活 娱乐晚会举办地。 3 0 6 40 9 30 12 200 9 喷泉 哈哈，你懂得！ 3 0 8 30 10 70 13 40 10 实验楼 下一个产生钱学森的圣地！7 110 9 70 11 30 11 教学楼 园丁与花朵！ 2 0 10 30 13 100 12 行政楼 学校领导办公之地。 2 0 8 200 13 90 13 北门 学校的正门。 2 0 11 100 12 90 ❹： schooltravel.h里的内容： #define MAX 100 typedef struct SSS { int num;//接收编号y int sum;//接收路径条数t int sumweight; }pa_th; typedef struct MM//顺序栈 { pa_th elem[MAX]; int top; }seqstackpath;//sequence-stack-int void initstack1(seqstackpath *s) { 3 0 s->top=-1; } void push1(seqstackpath *s,pa_th ch)//进栈 { if(s->top==MAX-1) { printf(\"栈已满！\");exit(0); } s->top++; s->elem[s->top].sum=ch.sum; s->elem[s->top].num=ch.num; s->elem[s->top].sumweight=ch.sumweight; } ❺： seqstacki.h里的内容： #define MAX 100 typedef struct Node//顺序栈 { int elem[MAX]; int top; }seqstacki;//sequence-stack-int void initstack(seqstacki *s) { s->top=-1; } void push(seqstacki *s,char ch)//进栈 { if(s->top==MAX-1) { printf(\"栈已满！\");exit(0); } s->top++; s->elem[s->top]=ch; } void pop(seqstacki *s,char *ch)//出栈 { if(s->top==-1) { printf(\"栈已空！\");exit(0); } else { *ch=s->elem[s->top]; s->top--; } } void pops(seqstacki *s)//出栈 { if(s->top==-1) { printf(\"栈已空！\");exit(0); } else s->top--; } void gettop(seqstacki *s,char *ch)//取栈顶 { if(s->top==-1) { printf(\"栈已空！\");exit(0); } else *ch=s->elem[s->top]; } int isempty(seqstacki *s)//空栈 { if(s->top==-1) return(1); else return(0); } int isfull(seqstacki *s)//满栈 { if(s->top==MAX-1) return(1); else return(0); } void clearstack(seqstacki *s)//清空栈 { s->top=-1; } 注：关于.h文件的创建，只需要把上述相关内容复制到同名的文本文档中，然后把.txt改为.h 因篇幅问题不能全部显示，请点此查看更多更全内容