资源描述：
《迷宫问题 火车车厢重排问题 实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验报告实验名称：数据结构实验二实验名称：栈和队列班级：000学号：000姓名：神刀公子时间：一、问题描述（1）迷宫问题①问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。图1迷宫示意图迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个
2、入口，一个出口。设计程序求解迷宫的一条通路。②基本要求l设计迷宫的存储结构。l设计通路的存储结构。l设计求解通路的算法。l设计迷宫显示和通路的显示方式。l输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。l输出：迷宫、入口、出口及通路路径。③思考l若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北），如何修改程序？l如何求得所有通路？l如何求得最短通路？（2）火车车厢重排问题①问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。
3、为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。②基本要求l设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；l设计并实现车厢重排算法；l分析算法的时间性能。③思考l如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？二、数据结构设计迷宫问题和火车
4、重排问题可以通过栈与队列实现的。迷宫的进出和车厢的出入轨和缓冲轨主要是对栈与队列的判断和操作。intempty(STLinktop[],intn)/*判断是否为空*/{return(top[n]==NULL);}intpush(STLinktop[],intA,intm)/*入栈*/{STLinkp;if(!(p=(STLink)malloc(LEN)))return0;else{p->data=A;p->link=top[m];top[m]=p;return1;}}intpop(STLinktop[],intm)/*出栈*/{in
5、tA;STLinkp;p=top[m];A=p->data;top[m]=top[m]->link;free(p);returnA;}structNode{/定义队列intdata;Node*next;};三、算法设计1.迷宫问题：进入格子后，需要判断此时格子位置周围障碍物的位置，对其进行压栈，判断，然后看是否满足条件，满足就进栈，不满足就弹出，然后输出不能通过建立迷宫：typedefstructLStack{Elementelem;structLStack*next;}*PLStack;intInitStack(PLStack&S
6、){S=NULL;return1;}intStackEmpty(PLStackS){if(S==NULL)return1;elsereturn0;}intPush(PLStack&S,Elemente){PLStackp;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return1;}intPop(PLStack&S,Element&e){PLStackp;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);ret
7、urn1;}elsereturn0;（1）迷宫线路的判断和寻找方法voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){inti,j,d;inta,b;Elementelem,e;PLStackS1,S2;InitStack(S1);InitStack(S2);maze[start.x][start.y]=2;elem.x=start.x;elem.y=start.y;elem.d=-1;Push(S1,elem);while(!Stack
8、Empty(S1)){Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;while(d<4){a=i+diradd[d][0];b=j+diradd[d][1];if(a==end.x&&b==end
