迷宫课程设计报告

西安郵電大學数据结构课程设计报告题目：迷宫问题院系名称：计算机学院专业名称：软件工程班级：1101学生姓名：武妍娜学号（8位）：04113027指导教师：李培设计起止时间：2021年12月3日~2021年12月14日一.设计目的1.熟悉C语言程序的编辑、编译链接和运行的过程，能够熟练地编辑、编译及调试程序。2.掌握文件和文件指针的概念以及文件的定义方法，学会熟练使用文件打开、关闭、读、写等基本操作。3.熟练掌握结构体、链表、指针的使用，及函数间的调用。4.能够熟练运用所学栈的相关知识及操作，顺利完成题目的要求。二.设计内容迷宫是实验心理学中一个古典问题。用计算机解迷宫路径的程序，就是仿照人走迷宫。计算机解迷宫时，通常用的是"穷举求解"的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。1.功能与数据需求迷宫求解问题描述：以一个M×N的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.1题目要求的功能（1）基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以二元组（i,j）的形式输出，其中：（i,j）指迷宫中对应的坐标。（2）测试数据：左上角（1,1）为入口，右下角（9,8）为出口。左上角（1,1）为入口，右上角（1,8）为出口。如下图所示：1.2扩展功能（1）编写非递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路2.界面需求（1）在菜单中选择要执行的操作（2）输出方阵迷宫（3）用户自己输入迷宫起始位置（4）输出所走的迷宫路径（5）输出方阵路径，并保存到文件中3.开发环境与运行需求MicrosoftVisualC++6.0Ubuntu三．概要设计主模块主模块本程序包含三个模块（1）主程序模块：

voidmain（）｛文件模块栈模块迷宫模块初始化；文件模块栈模块迷宫模块do｛接受命令；处理命令；｝while（命令！=“退出”）；｝（2）栈模块——实现栈抽象数据类型迷宫模块——实现迷宫抽象数据类型各个模块详细的功能描述。（1）菜单：从菜单中选择要执行的操作（2）文件模块：实现文件的各项基本操作a）打开文件 b）关闭文件c）从文件读信息 d）向文件中写入内容（3）栈模块：实现栈的各项基本操作a）初始化栈 b）入栈c）出栈 d）取栈顶元素(4）迷宫模块：求解迷宫问题a）显示迷宫 b)获取迷宫路径c）判断当前路径是否走过 d）获得下一个可走的位置e）获得东面，南面，西面，北面相邻的位置详细设计1．功能函数的调用关系图打开源文件打开源文件输出迷宫路径判断当前路径是否走过显示迷宫输出迷宫路径判断当前路径是否走过显示迷宫主函数主函数入栈入栈出栈获得迷宫路径初始化栈菜单出栈获得迷宫路径初始化栈菜单获得下一个可走的位置显示迷宫路线获得下一个可走的位置显示迷宫路线保存迷宫路线保存迷宫路线取栈顶元素取栈顶元素开始2.各功能函数的数据流程图开始MStackElemstart,cur; p2=head;MStackElemstart,cur; p2=head;cur=start;cur=start;dowhile(cur.x!=chukou[0]||cur.y!=chukou[1])当前位置是否走过当前位置是否走过Push(&realPath,cur)Push(&path,cur);cur=GetNext(cur);Push(&realPath,cur)Push(&path,cur);cur=GetNext(cur);cur=GetNext(cur);elseifcur.val==-1cur.val==-1Push(&realPath,cur)Push(&realPath,cur)Push(&path,cur);return1;ifcur.x==chukou[0]&&cur.y==chukou[1]cur.x==chukou[0]&&cur.y==chukou[1]Pop(&realPath);cur=GetTop(&realPath)Pop(&realPath);cur=GetTop(&realPath)开始获得下一个可通行的位置开始GetEast(cur).val==''&&UnPass(path,GetEast(cur))GetWest(cur).val==''&&UnPass(path,GetWest(cur))MStackElemnext;next.x=next.y=next.val=-1;ifelseifGetEast(cur).val==''&&UnPass(path,GetEast(cur))GetWest(cur).val==''&&UnPass(path,GetWest(cur))MStackElemnext;next.x=next.y=next.val=-1;GetNortGetNorth(cur).val==''&&UnPass(path,GetNorth(cur))GetSouth(cur).val==''&&UnPass(path,GetSouth(cur))next=GetSouthnext=GetSouth(cur);next=next=North(cur);next=GetEast(cur);next=GetEast(cur);next=GetEast(cur);next=GetEast(cur);3.重点设计及编码获得迷宫路径的函数：intGetMazePath(){ MStackElemstart,cur; start.x=rukou[0]; start.y=rukou[1];start.val=Maze[rukou[0]][rukou[1]]; cur=start;do{if(UnPass(path,cur)) { Push(&realPath,cur);Push(&path,cur);cur=GetNext(cur);if(cur.x==chukou[0]&&cur.y==chukou[1]) { Push(&realPath,cur); Push(&path,cur);return1;}elseif(cur.val==-1) { Pop(&realPath); cur=GetTop(&realPath); }} else {cur=GetNext(cur);if(cur.val==-1) { Pop(&realPath); cur=GetTop(&realPath); }}}while(cur.x!=chukou[0]||cur.y!=chukou[1]); return0;}五．测试数据及运行结果1．正常测试数据和运行结果2.异常测试数据及运行结果六．调试情况，设计技巧及体会1．改进方案在迷宫问题中，由于走的方向顺序不同，存在着多条路径的结果。因此就出现了一个最大的问题，哪条路径最短，即求最短路径。由于时间有限和难度问题，我没能及时解决这个问题，这也是在这次的迷宫课程设计中，我唯一的不足之处。不过我并没有放弃，课程设计结束后，我还会继续努力，解决掉这个问题。在以后的生活中，我也会不断督促自己，提高编程能力。2．体会刚开始，头脑里没有任何思路，不知道如何下手，经过仔细研读课本和上网查资料后，终于有了思绪。先将整个程序划分为三个大模块：主模块，栈模块和迷宫模块。然后再依次实现每个大模块中的小操作。最后将所有的程序拼接起来，进行调试。我觉得所有模块中最难编的就是查找迷宫路径函数，经过苦思冥想，再加上老师和同学的帮助，总算做出来了，但是非常复杂。在编译的过程中总会出现五花八门的错误，比如：从文件里读不出信息，又或者是存不进去文件，或者是乱码等。后来才发现原来是源文件中存的信息类型和程序中定义的类型不匹配，经过改正之后果然正确了。改正完后，当把所有的小块连接在一起时，虽然没有错误，但是总有许多警告语句，运行的结果也不尽人意。通过上网查资料后，发现这都是一些格式问题。看来编程格式很重要啊！经过两个星期的上机实践学习，我才发现我的C语言上机实践能力还有待加强，有待进步。以后不但要重视课本与习题，更要重视上机实践。七．参考文献1.耿国华主编，《数据结构——C语言描述》，高等教育出版社，2021年2.陈锐，《数据结构（C语言版）》，清华大学出版社2021年八．附录#include<stdio.h>#include<stdlib.h>#include<string.h>#defineM11 //迷宫行数#defineN10 //迷宫列数#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10charMaze[M][N]={0}; //迷宫chars[M][N]={0}; //迷宫路线图intrukou[2],chukou[2];//定义栈元素类型typedefstruct{intx; //x坐标inty; //y坐标charval; //Maze[x][y]的值}MStackElem;//定义栈typedefstruct{MStackElem*base;MStackElem*top;intStackSize;}MStack;//初始化栈InitStack(MStack*S){S->base=(MStackElem*)malloc(STACK_INIT_SIZE*sizeof(MStackElem));if(!S->base) {printf("初始化栈失败!\n");exit(-1); //存储分配失败}S->top=S->base;S->StackSize=STACK_INIT_SIZE;}//入栈Push(MStack*S,MStackEleme){ //向栈中添加元素前先判断栈是否还有空间容纳新元素if(S->top-S->base>=S->StackSize) //栈满,追加元素 {S->base=(MStackElem*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(MStackElem));if(!S->base) { printf("空间不足，入栈失败!\n"); exit(-1); //存储分配失败}S->top=S->base+S->StackSize;//因为是重新分配了空间,所以base的值其实已经改变,所以top的值也就相应的改变,才能指向新的迷宫栈S->StackSize+=STACKINCREMENT;}*(S->top++)=e; //将新元素加到栈顶}//获得栈顶元素MStackElemGetTop(MStack*S){ if(S->top==S->base) { printf("\n对不起，没有出路!\n\n"); exit(0); } else return*(S->top-1);}//出栈Pop(MStack*S){ //若栈不为空,则删除s的栈顶元素if(S->top==S->base) {printf("栈为空，出栈失败!\n");exit(0);}else--(S->top);}MStackrealPath,path; //构造两个栈,一个用来保存探索中的全部路径,一个用来保存有效路径//判断当前位置是否走过intUnPass(MStackpath,MStackElemcur) //这里不能传path的地址,否则在遍历过程中它的top值就被改了{intflag=1; //未走过while(path.top!=path.base){MStackEleme=*(path.top-1);if(e.x==cur.x&&e.y==cur.y) flag=0; //曾走过(path.top)--; //每循环一次令头指针下移一个位置}returnflag;}//获得东面(即右边)相邻的位置MStackElemGetEast(MStackElemcur){ if(cur.y!=N-2) //当y==N-2时已到了迷宫右边界,不能再向东(右)行了 { cur.y+=1;cur.val=Maze[cur.x][cur.y];}returncur; //当y==N-2时返回的是它本身}//获得南面(即下边)相邻的位置MStackElemGetSouth(MStackElemcur){ if(cur.x!=M-2) //当x==M-2时已到了迷宫下边界,不能再向南(下)行了 { cur.x+=1;cur.val=Maze[cur.x][cur.y];}returncur; //当x==M-2时返回的是它本身}//获得西面(即左边)相邻的位置MStackElemGetWest(MStackElemcur){ if(cur.y!=1) //当y==1时已到了迷宫左边界,不能再向西(左)行了 { cur.y-=1;cur.val=Maze[cur.x][cur.y];}returncur; //当y==1时返回的是它本身}//获得北面(即上边)相邻的位置MStackElemGetNorth(MStackElemcur){if(cur.x!=1) //当cur.x==1时表示在迷宫的上边界,不能再向北(上)行了 { cur.x-=1;cur.val=Maze[cur.x][cur.y];}returncur; //当cur.x==1时返回的还是它本身}//获得下一个可通行的位置,按东南西北(即顺时针)的方向试探MStackElemGetNext(MStackElemcur){ MStackElemnext; next.x=next.y=next.val=-1; if(GetEast(cur).val==''&&UnPass(path,GetEast(cur))) next=GetEast(cur); elseif(GetSouth(cur).val==''&&UnPass(path,GetSouth(cur))) next=GetSouth(cur); elseif(GetWest(cur).val==''&&UnPass(path,GetWest(cur))) next=GetWest(cur); elseif(GetNorth(cur).val==''&&UnPass(path,GetNorth(cur))) next=GetNorth(cur); returnnext; //如果当前位置的四面或为墙或已走过,则返回的next的val值为-1}//获得迷宫路径的函数intGetMazePath(){ MStackElemstart,cur; start.x=rukou[0]; start.y=rukou[1];start.val=Maze[rukou[0]][rukou[1]]; //入口坐标的值cur=start;//设定当前位置为"入口位置"do{if(UnPass(path,cur)) //如果当前位置未曾走到过 { Push(&realPath,cur);Push(&path,cur);cur=GetNext(cur);if(cur.x==chukou[0]&&cur.y==chukou[1]) //到达出口 { Push(&realPath,cur); //把出口结点放入路径中Push(&path,cur);return1;}elseif(cur.val==-1) //当前位置的四面都为墙 { Pop(&realPath); //删除真实路径的栈顶元素cur=GetTop(&realPath); //令cur指向栈顶元素}} else //如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向 {cur=GetNext(cur);if(cur.val==-1) { Pop(&realPath); //仍不通,删除真实路径的栈顶元素cur=GetTop(&realPath); //令cur指向栈顶元素}}}while(cur.x!=chukou[0]||cur.y!=chukou[1]); return0;}//输出迷宫路径PrintMazePath(MStack*S) //为了安全,这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了{ MStackEleme; inti,j; for(i=0;i<M;i++) for(j=0;j<N;j++) s[i][j]=Maze[i][j];while(S->base<(S->top-1)) { e=*(S->base); //先指向栈底元素,以后依次向上增1 s[e.x][e.y]='.'; printf("(%d,%d)----->",e.x,e.y); (S->base)++;}//最后一个结点没有后继,所以不再输出"------>"e=*(S->base); s[e.x][e.y]='.';printf("(%d,%d)",e.x,e.y);}//打开文件，获取迷宫OpenFile(){ FILE*fp; inti,j,c; system("cls"); if((fp=fopen("in.txt","rt"))==NULL) //打开迷宫文件in.txt { printf("打开文件失败！\n"); exit(1); } for(i=0;i<M;i++) //将文件中的迷宫存放到Maze[][]中 { for(j=0;j<N;j++) fscanf(fp,"%c",&Maze[i][j]); fscanf(fp,"%c",&c); //换行 } fclose(fp);}//保存迷宫路线图SaveFile() { FILE*fp; inti,j; charstr[M][N+1]; for(i=0;i<M;i++) { for(j=0;j<N;j++) str[i][j]=s[i][j]; str[i][j]='\n'; } str[M-1][N]='\0'; //结束符 if((fp=fopen("out.txt","wt"))==NULL) { printf("存储文件失败！\n"); exit(1); } fputs(str,fp); //保存文件 printf("\n迷宫文件保存成功，文件名为:out.txt。\n\n"); system("pause"); fclose(fp);}//输出迷宫Print1(){ intm,n; printf("\n迷宫('#'代表墙即不通,''代表通路即可通过)\n\n"); for(m=0;m<M;m++) { printf("\t\t"); for(n=0;n<N;n++) printf("%c",Maze[m][n]); printf("\n"); }}//输出迷宫路线图Print2(){ intm,n; printf("\n迷宫路线如下：\n'#'代表不通即墙,''代表通路即可通过，'.'代表行走路线，'>'代表入口，'<'代表出口.\n\n"); s[rukou[0]][rukou[1]]='>'; //入口标志 s[chukou[0]][chukou[1]]='<'; //出口标志 for(m=0;m<M;m++) { printf("\t\t"); for(n=0;n<N;n++) printf("%c",s[m][n]); printf("\n"); }}//菜单函数Menu(){ printf("\t\t******************************************\n"); printf("\t\t***欢迎进入课程设计***\n");printf("\t\t***迷宫求解程序***\n");printf("\t\t******\n"); printf("\t\t***1.显示迷宫***\n"); printf("\t\t***2.进入迷宫***\n"); printf("\t\t***3.打印迷宫***\n"); printf("\t\t***0.退出迷宫***\n"); printf("\t\t******************************************\n");}Flower(){ printf("\t{@}\n"); printf("\t{@}*{@}\n"); printf("\t{@}*{@}*{@}\n"); printf("\t{@}*{@}*{@}*{@}\n"); printf("\t\\{@}*{@}*{@}\/\n"); printf("\t\\\\\\l\/\/\/\n"); printf("\t\\\\\\Y\/\/\/\n"); printf("\t\\\\l\/\/\n"); printf("\t\\\\Y\/\/\n"); printf("\t>=<\n"); printf("\t\/\/*\\\\\n\n");}//主函数intmain(){ intchoice; //x[]用来输入迷宫入口坐标，y[]用来输入迷宫出口坐标 OpenFile(); //打开迷宫文件 do { system("cls"); //清屏 Menu(); //调用菜单函数 printf("\n请输入您的选择:"); scanf("%d",&choice); switch(choice) { case1: system("cls"); Print1(); //显示迷宫 printf("\n"); system("pause"); break; case2: //进入迷宫 system("cls"); printf("\n请输入入口坐标:"); scanf("%d%d",&rukou[0],&rukou[1]); //迷宫入口坐标 printf("\n请输入出口坐标:"); scanf("%d%d",&chukou[0],&chukou[1]); //迷宫出口坐标 if(rukou[0]>M-2||rukou[1]>N-2||chukou[0]>M-2||chukou[1]>N-2||rukou[0]<0||rukou[1]<0||chukou[0]<0||chukou[1]<0) printf("输入的入口或出口坐标错误!\n"); //判断输入坐标是否正确 else { InitStack(&realPath); InitStack(&path); GetMazePath(); printf("\n迷宫路径为:\n\n"); PrintMazePath(&realPath); getchar(); } printf("\n\n"); system("pause"); system("cls"); break; case3: system("cls"); Print2(); //显示迷宫路线图 printf("\n"); SaveFile(); //保存迷宫路线图 break; case0: //退出 system("cls"); printf("\n谢谢您的使用,再见!\n\n"); Flower(); break; default: system("cls"); printf("\n抱歉，您输入错误!\n请重新输入哦!\n\n"); system("pause"); } }while(choice);}

咖啡店创业计划书第一部分：背景在中国，人们越来越爱喝咖啡。随之而来的咖啡文化充满生活的每个时刻。无论在家里、还是在办公室或各种社交场合，人们都在品着咖啡。咖啡逐渐与时尚、现代生活联系在一齐。遍布各地的咖啡屋成为人们交谈、听音乐、休息的好地方，咖啡丰富着我们的生活，也缩短了你我之间的距离，咖啡逐渐发展为一种文化。随着咖啡这一有着悠久历史饮品的广为人知，咖啡正在被越来越多的中国人所理解。第二部分：项目介绍第三部分：创业优势目前大学校园的这片市场还是空白，竞争压力小。而且前期投资也不是很高，此刻国家鼓励大学生毕业后自主创业，有一系列的优惠政策以及贷款支持。再者大学生往往对未来充满期望，他们有着年轻的血液、蓬勃的朝气，以及初生牛犊不怕虎的精神，而这些都是一个创业者就应具备的素质。大学生在学校里学到了很多理论性的东西，有着较高层次的技术优势，现代大学生有创新精神，有对传统观念和传统行业挑战的信心和欲望，而这种创新精神也往往造就了大学生创业的动力源泉，成为成功创业的精神基础。大学生创业的最大好处在于能提高自己的潜力、增长经验，以及学以致用;最大的诱人之处是透过成功创业，能够实现自己的理想，证明自己的价值。第四部分：预算1、咖啡店店面费用咖啡店店面是租赁建筑物。与建筑物业主经过协商，以合同形式达成房屋租赁协议。协议资料包括房屋地址、面积、结构、使用年限、租赁费用、支付费用方法等。租赁的优点是投资少、回收期限短。预算10-15平米店面，启动费用大约在9-12万元。2、装修设计费用咖啡店的满座率、桌面的周转率以及气候、节日等因素对收益影响较大。咖啡馆的消费却相对较高，主要针对的也是学生人群，咖啡店布局、格调及采用何种材料和咖啡店效果图、平面图、施工图的设计费用，大约6000元左右3、装修、装饰费用具体费用包括以下几种。(1)外墙装饰费用。包括招牌、墙面、装饰费用。(2)店内装修费用。包括天花板、油漆、装饰费用，木工、等费用。(3)其他装修材料的费用。玻璃、地板、灯具、人工费用也应计算在内。整体预算按标准装修费用为360元/平米，装修费用共360*15=5400元。4、设备设施购买费用具体设备主要有以下种类。(1)沙发、桌、椅、货架。共计2250元(2)音响系统。共计450(3)吧台所用的烹饪设备、储存设备、洗涤设备、加工保温设备。共计600(4)产品制造使用所需的吧台、咖啡杯、冲茶器、各种小碟等。共计300净水机，采用美的品牌，这种净水器每一天能生产12l纯净水，每一天销售咖啡及其他饮料100至200杯，价格大约在人民币1200元上下。咖啡机，咖啡机选取的是电控半自动咖啡机，咖啡机的报价此刻就应在人民币350元左右，加上另外的附件也不会超过1200元。磨豆机，价格在330―480元之间。冰砂机，价格大约是400元一台，有点要说明的是，最好是买两台，不然夏天也许会不够用。制冰机，从制冰量上来说，一般是要留有富余。款制冰机每一天的制冰量是12kg。价格稍高550元，质量较好，所以能够用很多年，这么算来也是比较合算的。5、首次备货费用包括购买常用物品及低值易耗品，吧台用各种咖啡豆、奶、茶、水果、冰淇淋等的费用。大约1000元6、开业费用开业费用主要包括以下几种。(1)营业执照办理费、登记费、保险费;预计3000元(2)营销广告费用;预计450元7、周转金开业初期，咖啡店要准备必须量的流动资金，主要用于咖啡店开业初期的正常运营。预计2000元共计： 120000+6000+5400+2250+450+600+300+1200+1200+480+400+550+1000+3000+450+2000=145280元第五部分：发展计划1、营业额计划那里的营业额是指咖啡店日常营业收入的多少。在拟定营业额目标时，必须要依据目前市场的状况，再思考到咖啡店的经营方向以及当前的物价情形，予以综合衡量。按照目前流动人口以及人们对咖啡的喜好预计每一天的营业额为400-800，根据淡旺季的不同可能上下浮动2、采购计划依据拟订的商品计划，实际展开采购作业时，为使采购资金得到有效运用以及商品构成达成平衡，务必针对设定的商品资料排定采购计划。透过营业额计划、商品计划与采购计划的确立，我们不难了解，一家咖啡店为了营业目标的达成，同时有效地完成商品构成与灵活地运用采购资金，各项基本的计划是不可或缺的。当一家咖啡店设定了营业计划、商品计划及采购计划之后，即可依照设定的采购金额进行商品的采购。经过进货手续检验、标价之后，即可写在菜单上。之后务必思考的事情，就是如何有效地将这些商品销售出去。3、人员计划为了到达设定的经营目标，经营者务必对人员的任用与工作的分派有一个明确的计划。有效利用人力资源，开展人员培训，都是我们务必思考的。4、经费计划经营经费的分派是管理的重点工作。通