迷宫最短路径.doc

湖南工业大学课 程 设 计 计算机与通信 学院（系、部） 2012 2013 学年第 2 学期 课程名称 数据结构课程设计 指导教师 xxxx 职称 副教授 学生姓名 xxx 专业班级 计算机科学与技术 学号 xxxxxx 题 目 迷宫最短路径求法 成 绩 起止日期 2013 年 6 月 26 日 2013 年 6 月 27 日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13张456湖南工业大学课程设计任务书2012 2013 学年第 2 学期 计算机与通信学院 （系、部） 计算机科学与技术 专业 1203 班级课程名称： 数据结构课程设计 设计题目： 求迷宫问题的最短路径 完成期限：自 2013 年 6 月 25 日至 2013 年 6 月 27 日共 周内容及任务一：设计的主要技术参数1、函数的调用 2、公用体、结构体3、循环语句和选择语句4、队列5、指针与数组的应用6、结构体的应用7：遍历三、设计工作量1、函数编码设计2、函数的调试及运行3、系统的调试一、设计内容：迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到一条迷宫的最短路径。 二、任务：掌握结构化程序设计的主体思想，以自顶向下逐步求精的方法编制程序解决一些实际的问题，为将来编写软件积累一些典型的案例处理经验。1. 设计正确，方案合理。2. 界面友好，使用方便。3. 程序精炼，结构清晰。4. 设计报告，含程序设计说明，用户使用说明，源程序清单及程序框图。5. 上机演示。6. 按学号顺序选课题号，并在规定的时间内独自完成相关课题的C源程序编写、调整和运行。源程序及编译生成各文件均保存在软盘中；7.按本任务书的要求，按附录的要求编写课程设计报告（Word文档格式）。并用A4的复印纸打印并装订。进度安排起止日期工作内容2013.06.252013.06.27选题及组内成员分任务，开始熟悉课题并进行构思2013.06.25编写源程序、运行、修改2013.06.26编写文档并打印文稿主要参考资料1 谭浩强. C语言程序设计（第三版）. 北京：清华大学出版社，20052 数据结构实验教程. 北京：高等教育出版社，20053 刘振鹏 罗文劼 石强 .数据结构（第三版）中国铁道出版社指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日3数据结构课程设计设计说明书 求迷宫的最短路径 起止日期： 2013 年 6 月 25 日 至 2013 年 6 月 27 日学生姓名xxx班级计算机科学与技术1203学号xxxx成绩指导教师(签字)计算机与通信学院（部）2013年 6 月 26 日目录1 课程设计简介11.1 课程设计的目的11.2 课程设计内容12 数据结构的设计23 功能模块（或算法）描述34 程序运行结果45心得体会5参考文献6.41.1 课程设计简介1.1 课程设计的目的通过实验，掌握如下内容： 1：进一步掌握指针、模板类、异常处理的使用；2：掌握队列的操作和实现方法；3：学习使用队列解决实际问题的能力；4：学习使用图的广度优先搜索解决实际问题的能力。1.2 课程设计内容 2利用数据结构的队列遍历求出迷宫问题的最短路径。迷宫求解问题如下：迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到一条迷宫的最短路径。测试算法的迷宫由使用者设置，例如设置的迷宫如下图所示 1.3程序功能 打印老鼠走出迷宫的最短路径 2.程序算法及功能分析2.1存储结构： 队列顺序存储示意图如下：2.2 关键算法分析核心算法思想：1：如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径，为了改变算法，达到输出最短路径的目的，采用队列的实现方式。2：为查找最短路径，使用了图中的广度搜索。算法的基本思路为：从迷宫入口点（1,1）出发，向四周搜索，几下所有一步能到达的坐标点；然后依次再从这些点出发，再几下所有一步能到达的坐标点；依此类推，直到到达迷宫的出口点（m,n）为止，然后从出口点沿着搜索路径回溯到入口。typedef struct int x,y; / 行、列坐标int pre; / 链域sqtype;sqtype sqr; /作为队列的存储空间，记录被访问过的点关键算法思想的描述和实现：为寻求最短路径，采用广度优先搜索方法，使用队列实现路径存储，队列中每个元素用结构存储体系，包含迷宫坐标，队列中的序号，队首指针front,队尾指针rear,最后采用回溯的方法将路径打印出来。算法1：int SHORTPATH(int mazem2n2) /找迷宫maze的最短路径int i,j,v,front,rear,x,y; sq1.x=1; /设定入口的行坐标sq1.y=1; /设定入口的纵坐标sq1.pre=0;front=1; /进入迷宫时的队首指针rear=1; /进入迷宫时的队尾指针maze11=-1; /标记入口点已经到达算法2：遍历每个位置的四周，将没有走过的位置入队，形成树形的队列，通过出队操作就能找出最短路径x=sqfront.x; y=sqfront.y; /(x，y)为出发点for(v=0;v8;v+) /搜索(x,y)的8个相邻点(i,j)是否可到达i=x+movev.x;j=y+movev.y;if(mazeij=0) /(i,j)为可到达点，将其入队rear+;sqrear.x=i; sqrear.y=j;sqrear.pre=front;mazeij=-1; /标记(i,j)已到达过的点算法3：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层次遍历，如下图：在迷宫地图中，关键算法三通过不断调用算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到的最浅深度即为最短路径。if(mazeij=0) /(i,j)为可到达点，将其入队rear+;sqrear.x=i; sqrear.y=j;sqrear.pre=front;mazeij=-1; /标记(i,j)已到达过的点if(i=m)&(j=n) /到达出口PRINTPATH(sq,rear); /打印路径/RESTORE(maze); /恢复迷宫return 1; /成功，返回1算法4：使用队列指针查找队首指针的方式，从队尾回溯到队首，标记出最短路径。队列的元素示意如图：int SHORTPATH(int mazem2n2) /找迷宫maze的最短路径int i,j,v,front,rear,x,y;sq1.x=1; sq1.y=1; sq1.pre=0;front=1; rear=1;maze11=-1; /标记入口点已经到达while(front=rear) /队列非空x=sqfront.x; y=sqfront.y; /(x，y)为出发点for(v=0;v8;v+) /搜索(x,y)的8个相邻点(i,j)是否可到达i=x+movev.x;j=y+movev.y;if(mazeij=0) /(i,j)为可到达点，将其入队rear+;sqrear.x=i; sqrear.y=j;sqrear.pre=front;mazeij=-1; /标记(i,j)已到达过的点if(i=m)&(j=n) /到达出口PRINTPATH(sq,rear); /打印路径/RESTORE(maze); /恢复迷宫return 1; /成功，返回1front +; /出队，front指向新的出发点 / 队空循环结束return 0; /迷宫无路径，返回0时间复杂度和空间复杂度算法一盒二的时间复杂度与空间复杂度均为O（1）。算法三占用空间为迷宫边长n的平方，故空间复杂度为O（n*n）.最多走n*n步，最少走1步，故时间复杂度为O（n*n/2）。4 程序运行结果1用代码创建3个文件夹，用于存放数据。main() if(fp=fopen(c:book.txt,rb+)=NULL)printf(在c盘根目录下没有找到储存图书信息的book.txt文件n请选择 1-手动导入！ 2-创建此文件n);scanf(%d,&xuan);switch(xuan)case 2:if(fp=fopen(c:book.txt,wb+)!=NULL) printf(创建成功nn);break;case 1:printf(请把名为book.txt的文件复制到c盘根目录下nn);if(fpj=fopen(c:jieyue.txt,rb+)=NULL)printf(在c盘根目录下没有找到储存借阅信息的jieyue.txt文件n请选择 1-手动导入！ 2-创建此文件n);scanf(%d,&xuan);switch(xuan)case 2:if(fpj=fopen(c:jieyue.txt,wb+)!=NULL) printf(创建成功nn);break;case 1:printf(请把名为jieyue.txt的文件复制到c盘根目录下nn);if(fps=fopen(c:student.txt,rb+)=NULL)printf(在c盘根目录下没有找到储存学生信息的student.txt文件n请选择 1-手动导入！ 2-创建此文件n);scanf(%d,&xuan);switch(xuan)case 2:if(fps=fopen(c:student.txt,wb+)!=NULL) printf(创建成功nn);break;case 1:printf(请把名为student.txt的文件复制到c盘根目录下nn);2,。进入界面void menu()/菜单 system(cls);printf(nn);printf( * 欢迎进入图书管理查询系统 *n);for(i=0;i80;i+)printf(#);printf(n);printf(tt1-图书录入ttt);printf(2-图书浏览nn);printf(tt3-图书查询ttt);printf(4-修改删除图书nn);printf(tt5-借阅图书ttt);printf(6-归还图书nn);printf(tt7-借阅查询tttn);printf(ntttt输入其他任意键退出n);printf(n);for(i=0;i80;i+)printf(#);printf(nn);2录入图书，输入图书的8种信息，图书名，图书编号，图书作者，出版日期，价格，出版社，类别，入库，成功后返回主菜单。void end()/录入图书 system(cls);bo boo,booq;printf(请输入图书名(最多十个字符)：);scanf(%s,);doi=1;printf(请输入图书编号(最多十个字符)：);scanf(%s,boo.num);fread(&booq,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(booq.num,boo.num)=0)printf(n该编号已存在请重新输入nn);i=0;break;fread(&booq,sizeof(bo),1,fp);rewind(fp);while(i=0);printf(请输入图书作者(最多十个字符)：);scanf(%s,boo.writer);printf(请输入图书出版日期（例如2001年5月3日出版则输入20010503）：);scanf(%d,&boo.date);printf(请输入图书价格：);scanf(%f,&boo.price);printf(请输入图书出版社(最多十个字符)：);scanf(%s,boo.press);printf(请输入图书类别(最多十个字符)：);scanf(%s,boo.leibie);printf(请输入图书入库数：);scanf(%d,&boo.kucun);boo.jiechu=0;getchar();fseek(fp,0,2);fwrite(&boo,sizeof(bo),1,fp);printf(n录入成功！回到主菜单);system(pause); 9 其他键自动退出5心得体会学了一个学期的C语言，功底还不扎实，再说C语言学的也并不好，刚做课程实际时，觉得自己肯定无法完成这项工作的，但经过慢慢的尝试探索，不断的发现错误改正错误，还是将其完成了，虽然并不完美近一个礼拜中,我们有过山穷水尽的困惑；有过柳暗花明的惊喜；有过唇枪舌剑的辩论；有过相互鼓励的安慰。一个多礼拜的时间我们经历了很多，也收获了很多。与其说它是体力与脑力的作业，不如说它是合作精神和毅力的考验。经过这次课程设计，我学到了很多知识和技能，并学会了用所学的知识解决实际问题。同过本次的课程设计，巩固了我的C语言知识，发现了自身的诸多不足之处，总之，这是一次很好的锻炼机会参考文献4 谭浩强. C语言程序设计（第三版）. 北京：清华大学出版社，20055 廖雷、罗代忠. C语言程序设计基础实验教程. 北京：高等教育出版社，20056 谭浩强. C程序设计解题与上机指导(第三版) . 北京：清华大学出版社，20057 廖雷等. C语言程序设计基础. 北京：高等教育出版社，20048 谭浩强，张基温，唐永炎. C语言程序设计教程. 北京: 高等教育出版社，2003附源代码#include#include#includeFILE *fp,*fpj,*fps;int i,xuan;typedef struct bookchar name10;char num10;char writer10;int date;char press10;float price;char leibie10;int kucun;int jiechu;bo;typedef struct studentchar name10;char num10;int jie;st;typedef struct jieyuechar snum10;char bnum10;ji;void menu()/菜单 system(cls);printf(nn);printf( * 欢迎进入图书管理查询系统 *n);for(i=0;i80;i+)printf(#);printf(n);printf(tt1-图书录入ttt);printf(2-图书浏览nn);printf(tt3-图书查询ttt);printf(4-修改删除图书nn);printf(tt5-借阅图书ttt);printf(6-归还图书nn);printf(tt7-借阅查询tttn);printf(ntttt输入其他任意键退出n);printf(n);for(i=0;i80;i+)printf(#);printf(nn);void end()/录入图书 system(cls);bo boo,booq;printf(请输入图书名(最多十个字符)：);scanf(%s,);doi=1;printf(请输入图书编号(最多十个字符)：);scanf(%s,boo.num);fread(&booq,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(booq.num,boo.num)=0)printf(n该编号已存在请重新输入nn);i=0;break;fread(&booq,sizeof(bo),1,fp);rewind(fp);while(i=0);printf(请输入图书作者(最多十个字符)：);scanf(%s,boo.writer);printf(请输入图书出版日期（例如2001年5月3日出版则输入20010503）：);scanf(%d,&boo.date);printf(请输入图书价格：);scanf(%f,&boo.price);printf(请输入图书出版社(最多十个字符)：);scanf(%s,boo.press);printf(请输入图书类别(最多十个字符)：);scanf(%s,boo.leibie);printf(请输入图书入库数：);scanf(%d,&boo.kucun);boo.jiechu=0;getchar();fseek(fp,0,2);fwrite(&boo,sizeof(bo),1,fp);printf(n录入成功！回到主菜单);system(pause);void print()/浏览图书 system(cls);bo boo;printf(书名 编号 作者 价格 出版社 类别 原始库存 借出n);fread(&boo,sizeof(bo),1,fp);while(feof(fp)=0)printf(%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);fread(&boo,sizeof(bo),1,fp);printf(n浏览图书完毕！回到主菜单);system(pause);int dui(char *p,char *p1)/对比两个字符串的相关度（用于精确搜索）int bao=0,fan=1;for(i=0;i(int)strlen(p1)-bao+1)return 0;elsefor(i=0;i(int)strlen(p);i+)if(pi!=p1bao+i)fan=0;return fan;void find()/查询图书 system(cls);char hao10;int fan=1;int bian=1;bo boo;printf(请选择查询类型：nntt1-按图书编号模糊查询 2-按图书名关键字查询n);printf( ntt3-按图书编号精确查询 4-按图书名精确查询nn代码：);scanf(%d,&xuan);if(xuan=1)printf(请输入编号(最多十个字符)：);scanf(%s,hao);printf(序号 书名 编号 作者 价格 出版社 类别 原始库存 借出n);fread(&boo,sizeof(bo),1,fp);while(!feof(fp)fan=dui(hao,boo.num);if(fan=1)printf(%-5d%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,bian,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);bian+;fread(&boo,sizeof(bo),1,fp);else if(xuan=2)printf(请输入图书名关键字(最多十个字符)：);scanf(%s,hao);printf(序号 书名 编号 作者 价格 出版社 类别 原始库存 借出n);fread(&boo,sizeof(bo),1,fp);while(!feof(fp)fan=dui(hao,);if(fan=1)printf(%-5d%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,bian,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);fread(&boo,sizeof(bo),1,fp);else if(xuan=4)printf(请输入图书名(最多十个字符)：);scanf(%s,hao);printf(序号 书名 编号 作者 价格 出版社 类别 原始库存 借出n);while(!feof(fp)if(strcmp(hao,)=0)printf(%-5d%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,bian,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);fread(&boo,sizeof(bo),1,fp);else if(xuan=3)printf(请输入图书编号(最多十个字符)：);scanf(%s,hao);printf(序号 书名 编号 作者 价格 出版社 类别 原始库存 借出n);while(!feof(fp)if(strcmp(hao,boo.num)=0)printf(%-5d%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,bian,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);fread(&boo,sizeof(bo),1,fp);elseprintf(输入错误，正在退出！);system(pause);return;printf(n查询图书完毕！ );system(pause);void del()/修改删除图书 system(cls);FILE *p;ji jie;int j=0;char num10;bo boo,booq;int xu;char or;char cha10;printf(n删除修改图书只能通过图书编号来完成！n是否调用图书查询来查询你要操作的图书编号（Y/N）n);getchar();scanf(%c,&or);if(or=Y|or=y)find();rewind(fp);printf(n请输入你要操作的图书的编号（如果输入错误的编号，将不做任何操作）：);scanf(%s,cha);fread(&jie,sizeof(ji),1,fpj);while(!feof(fpj)if(strcmp(jie.bnum,cha)=0)printf(n这本书已有人借阅，不能操作！n正在退出 );system(pause);return;fread(&jie,sizeof(ji),1,fpj);printf(nn1-删除图书 2-修改图书nn);printf(请选择操作类型：);scanf(%d,&xuan);fread(&boo,sizeof(bo),1,fp);p=fopen(c:books1.txt,wb+);while(!feof(fp)j+;if(strcmp(boo.num,cha)=0)if(xuan=2)printf(nn1-书名 2-编号 3-作者 4-价格 5-出版社 6-类别 7-库存nn);printf(请选择要修改的项目:);scanf(%d,&xu);if(xu=1)printf(你要把%s改为：,);scanf(%s,);else if(xu=2)doi=1;printf(你要把%s改为：,boo.num);scanf(%s,num);rewind(fp);fread(&booq,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(booq.num,num)=0)printf(n该编号已存在请重新输入nn);i=0;break;fread(&booq,sizeof(bo),1,fp);while(i=0);rewind(fp);for(i=0;ij;i+)fread(&boo,sizeof(bo),1,fp);strcpy(boo.num,num);else if(xu=3)printf(你要把%s改为：,boo.writer);scanf(%s,boo.writer);else if(xu=4)printf(你要把%.2f改为：,boo.price);scanf(%f,&boo.price);else if(xu=5)printf(你要把%s改为：,boo.press);scanf(%s,boo.press);else if(xu=6)printf(你要把%s改为：,boo.leibie);scanf(%s,boo.leibie);else if(xu=7)printf(你要把%d改为：,&boo.kucun);scanf(%d,&boo.kucun);fwrite(&boo,sizeof(bo),1,p);elsefwrite(&boo,sizeof(bo),1,p);fread(&boo,sizeof(bo),1,fp);fclose(p);p=fopen(c:books1.txt,rb+);fclose(fp);fp=fopen(c:book.txt,wb+);fread(&boo,sizeof(bo),1,p);while(!feof(p)fwrite(&boo,sizeof(bo),1,fp);fread(&boo,sizeof(bo),1,p);fclose(fp);printf(操作成功 回到主菜单);system(pause);void lend()/借阅图书 system(cls);bo boo;FILE *p;st stu;ji jie;int j=0;char or,num10,xnum10;printf(n借阅图书只能通过图书编号完成！n是否调用图书查询来查询你要操作的图书编号（Y/N）n);getchar();scanf(%c,&or);if(or=Y|or=y)find();printf(n请输入你要借阅的图书的编号：);scanf(%s,num);fread(&boo,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(num,boo.num)=0)j=1;break;fread(&boo,sizeof(bo),1,fp);if(j=0)printf(n书库没有该图书 正在退出n);system(pause);return;printf(n你需要借阅的图书是：n);printf(书名 编号 作者 价格 出版社 类别 原始库存 借出n);printf(%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,,boo.num,boo.writer,boo.price,boo.press,boo.leibie,boo.kucun,boo.jiechu);if(boo.kucun=boo.jiechu)printf(n该册图书已全部借出！正在退出n);system(pause);return;printf(n请输入你的学号：);scanf(%s,xnum);j=0;fread(&jie,sizeof(ji),1,fpj);while(!feof(fpj)if(strcmp(jie.bnum,num)=0)&(strcmp(jie.snum,xnum)=0)j=1;break;fread(&jie,sizeof(ji),1,fpj);if(j=1)printf(n你已经借阅过该书 正在退出n);system(pause);return;fread(&stu,sizeof(st),1,fps);j=0;while(!feof(fps)if(strcmp(xnum,stu.num)=0)j=1;break;fread(&stu,sizeof(st),1,fps);if(j=0)printf(n你是第一次借阅图书，为了方便管理请输入你的姓名：);scanf(%s,);strcpy(stu.num,xnum);stu.jie=1;fseek(fps,0,2);fwrite(&stu,sizeof(st),1,fps);elseif(stu.jie=5)/这里可以控制每个学生最多借几本书printf(n你已经借了5本书，不能再借n);system(pause);return;p=fopen(c:jie.txt,wb+);rewind(fps);fread(&stu,sizeof(st),1,fps);while(!feof(fps)if(strcmp(xnum,stu.num)=0)stu.jie+;fwrite(&stu,sizeof(st),1,p);fread(&stu,sizeof(st),1,fps);fclose(p);fclose(fps);p=fopen(c:jie.txt,rb+);fps=fopen(c:student.txt,wb+);fread(&stu,sizeof(st),1,p);while(!feof(p)fwrite(&stu,sizeof(st),1,fps);fread(&stu,sizeof(st),1,p);strcpy(jie.bnum,num);strcpy(jie.snum,xnum);fseek(fpj,0,2);fwrite(&jie,sizeof(ji),1,fpj);rewind(fp);p=fopen(c:jie.txt,wb+);fread(&boo,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(num,boo.num)=0)boo.jiechu+;fwrite(&boo,sizeof(bo),1,p);fread(&boo,sizeof(bo),1,fp);fclose(p);p=fopen(c:jie.txt,rb+);fclose(fp);fp=fopen(c:book.txt,wb+);fread(&boo,sizeof(bo),1,p);while(!feof(p)fwrite(&boo,sizeof(bo),1,fp);fread(&boo,sizeof(bo),1,p);printf(n借阅成功！回到主菜单);system(pause);void huan()/归还图书system(cls);FILE *p;bo boo;ji jie;st stu;int j=0;char snum10,bnum10;i=0;printf(n请输入你的学号：);scanf(%s,snum);printf(n你借阅了以下图书n);fread(&jie,sizeof(ji),1,fpj);printf(书名 编号 作者 价格 出版社 类别 原始库存 借出n);while(!feof(fpj)if(strcmp(jie.snum,snum)=0)fread(&boo,sizeof(bo),1,fp);while(!feof(fp)if(strcmp(jie.bnum,boo.num)=0)printf(%-10s%-10s%-10s%-10.2f%-10s%-10s%-10d%-4dn,,boo.num,boo.writer,