迷宫问题 有源代码.doc

西安郵電大學数据结构课程设计报告题 目：迷宫问题院系名称：计算机学院 专业名称：软件工程班 级：1101班 学生姓名：付添学号（8位）：04113035指导教师： 李培 设计起止时间：2012年12月3日2012年12月14日一. 设计目的仅仅认识到队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法，是同学们栈的运用更得心应手，为以后就业打下很好的基础。2. 设计内容主要包括哈1.从键盘输入迷宫。2.从文件读出迷宫。3.走迷宫。4以坐标形式输出迷宫路径。5.以形象的矩阵输出路径。三概要设计1功能模块图；从文件读入字符从键盘输入迷宫从文件读出迷宫走迷宫选择输出东边有通路西边有通路北边有通路南边有通路选择一个走以形象矩阵输出以坐标形式输出输入数字选择1, 2 3;2各个模块详细的功能描述。（1）savefile();/从键盘输入迷宫从键盘输入迷宫1表示墙0表示通路，并把01存入结构体m1中用flag表示通路初始化通路的标志域。（2）inread();/从文件读出迷宫事先已将迷宫存入文件中，从文件读出迷宫1表示墙0表示通路，并把01存入结构体m1中用flag表示通路初始化通路的标志域。（3）zoumigong();/走迷宫根据m1判断该坐标四周如果为墙并且标志域为0则可走，将该坐标入栈，将其标志域更改为1，更新坐标，继续判断，知道更新坐标等于出口坐标.栈中存放就是通路的逆序坐标。(4)print1()/以坐标形式输出将栈中坐标出栈，存入数组中以坐标形式输出。（5）print2（）/以矩阵形式输出将栈中坐标出栈，存入数组中以矩阵形式输出。四详细设计1 功能函数的调用关系Savefile(),inread()选择一个输入图走迷宫zoumigong();Print1()坐标形式输出。Print2()矩阵形式输出。2各功能函数的数据流程图走迷宫判断哪个方向可走。该坐标西边可有通路，该坐标入站，标志域赋1，更新坐标该坐标西边可有通路，该坐标入站，标志域赋1，更新坐标该坐标西边可有通路，该坐标入站，标志域赋1，更新坐标该坐标西边可有通路，该坐标入站，标志域赋1，更新坐标3重点设计及编码typedef structint mg200;int top;seqstack;typedef struct migongint m1;/存放墙int flag;/标志域smaze2020;int empty(seqstack &s)/判栈空if(s.top=-1)return 0;elsereturn 1;void pop(seqstack &s,int &x1)/出栈if(s.top=-1)return ;x1=s.mgs.top;s.top-;void push(seqstack &s,int y1,int x1)/入栈if(s.top=20)return ;s.top+;s.mgs.top=y1;s.top+;s.mgs.top=x1;void zumigong(seqstack &stack,smaze &maze,int &m,int &n)/走迷宫int i,j,cout;int x1,a,b,y1,x,y,x2,y2;printf(输入入口的横纵坐标，空格隔开n);scanf(%d %d,&x,&y);printf(输入出口的横纵坐标，空格隔开n);scanf(%d %d,&x2,&y2);for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)if(mazeij.m1=1)printf();elseprintf();printf(n);x1=x;y1=y;if(mazex1y1.m1=1)printf(此路不通：n);return ;if(mazex2y2.m1=1)printf(入口为墙。请重新输入n);elsewhile(x1!=x2|y1!=y2)if(mazex1y1+1.m1=0&mazex1y1+1.flag=0)cout=0;elseif(mazex1+1y1.m1=0&mazex1+1y1.flag=0)cout=1;elseif(mazex1-1y1.m1=0&mazex1-1y1.flag=0)cout=2;elseif(mazex1y1-1.m1=0&mazex1y1-1.flag=0)cout=3;elsecout=4;switch(cout)case 0:a=x1;b=y1;mazex1y1.flag=1;y1=y1+1;push(stack,b,a);/列先入break;case 1:a=x1;b=y1;mazex1y1.flag=1;x1=x1+1;push(stack,b,a);break;case 2:a=x1;b=y1;mazex1y1.flag=1;x1=x1-1;push(stack,b,a);break;case 3:a=x1;b=y1;mazex1y1.flag=1;y1=y1-1;push(stack,b,a);break;case 4: mazex1y1.flag=1; if(empty(stack)!=0)pop(stack,x1);pop(stack,y1);break;elseprintf(此路没有通路：n);return ;push(stack,y2,x2);五测试数据及运行结果1.正常测试数据和运行结果1测试数据2,运行结果1.坐标形式2.矩阵形式3文件保存结果2. 异常测试数据及运行结果六调试情况，设计技巧及体会1改进方案设置标志域使访问判断坐标更方便。2.体会通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和请教老师，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在这段时间里，我对for、while等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。在这次短短的课程实践里，我们得到了李培老师的关心和帮助。她给了我们很多的信息，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解决的问题时，她就会指导我们解决问题7 参考文献数据结构C语言描述耿国华主编，高等教育社出版。#include#includetypedef structint mg200;int top;seqstack;typedef struct migongint m1;int flag;smaze2020;void inista(seqstack &s)s.top=-1;int empty(seqstack &s)if(s.top=-1)return 0;elsereturn 1;void pop(seqstack &s,int &x1)if(s.top=-1)return ;x1=s.mgs.top;s.top-;void push(seqstack &s,int y1,int x1)if(s.top=20)return ;s.top+;s.mgs.top=y1;s.top+;s.mgs.top=x1;void inread(smaze &maze,int m,int n)char name20;int i,j;printf(输入存放迷宫的文件名n);scanf(%s,name);FILE *fp=fopen(name,rt);if(fp=NULL)printf(n打开文件%s失败n);exit(1);for(i=1;im+1;i+) for(j=1;jn+1;j+)fscanf(fp,%d ,&mazeij.m1);if(mazeij.m1=0)mazeij.flag=0;elsemazeij.flag=1;fclose(fp);for(i=0;i=m+1;i+) mazei0.m1=1;mazei0.flag=1;/加两堵列墙 mazein+1.m1=1;mazein+1.flag=1; for(j=0;j=n+1;j+) /加两堵行墙 maze0j.m1=1; mazem+1j.m1=1;maze0j.flag=1;mazem+1j.flag=1; for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)if(mazeij.m1=1)printf();elseprintf();printf(n);void zumigong(seqstack &stack,smaze &maze,int &m,int &n)int i,j,cout;int x1,a,b,y1,x,y,x2,y2;printf(输入入口的横纵坐标，空格隔开n);scanf(%d %d,&x,&y);printf(输入出口的横纵坐标，空格隔开n);scanf(%d %d,&x2,&y2);for(i=0;i=m+1;i+)for(j=0;j=1;i-)printf( ,s1i,s2i);printf(n,s10,s20);printf(请输入要保存路径的文件名n);scanf(%s,name);FILE *fp=fopen(name,wb);if(fp=NULL)printf(n打开文件%s失败n,name);exit(1);fprintf(fp,迷宫路径：n);for(i=n-1;i=0;i-)fprintf(fp, ,s1i,s2i);fclose(fp);printf(已成功保存于%s文件中,name);void print2(seqstack &stack,smaze &maze,int &m,int &n)int s120,s220,i=0,j=0,n1,n2;while(stack.top!=-1)pop(stack,s1i);pop(stack,s2j);n1=s1i;n2=s2j;mazen1n2.flag=2;i+;j+;printf(以形象的矩阵形式输出迷宫路径 表示走过的痕迹 表示迷宫路径n);printf(如下所示n);for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)if(mazeij.m1=1)printf();if(mazeij.m1=0&mazeij.flag=0)printf();if(mazeij.m1=0&mazeij.flag=1)printf();if(mazeij.m1=0&mazeij.flag=2)printf();printf(n);void savefile(smaze maze,int &m,int &n) int i,j;char name20;printf(输入迷宫：n);for(i=1;i=m;i+)for(j=1;j=n;j+)scanf(%d,&mazeij.m1);if(mazeij.m1=1)mazeij.flag=1;elsemazeij.flag=0;for(i=0;i=m+1;i+) mazei0.m1=1;mazei0.flag=1;/加两堵列墙 mazein+1.m1=1;mazein+1.flag=1; for(j=0;j=n+1;j+) /加两堵行墙 maze0j.flag=1; mazem+1j.flag=1;maze0j.m1=1;mazem+1j.m1=1; printf(请输入保存的文件名：n);scanf(%s,name);FILE *fp=fopen(name,wt);if(fp=NULL)printf(n打开文件%s失败n,name);exit(1);for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)if(mazeij.m1=1)printf();elseprintf();printf(n);fprintf(fp,迷宫路径：n);for(i=1;i=m;i+) for(j=1;j=n;j+)fprintf(fp,%d ,mazeij.m1);fputc(n,fp); fclose(fp);int print()int i;printf( n);printf( n);printf( n);printf( 软件1班 n);printf( 付 n);printf( 添 n);printf( n);printf( n);printf(