迷宫问题 火车车厢重排问题 实验报告材料

word实验报告实验名称：数据结构实验二实验名称：栈和队列班级：000学号：000某某：神刀公子时间：一、问题描述1迷宫问题问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。此题设置的迷宫如图1所示。图1 迷宫示意图迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。根本要求l 设计迷宫的存储结构。l 设计通路的存储结构。l 设计求解通路的算法。l 设计迷宫显示和通路的显示方式。l 输入：迷宫、入口与出口可在程序中设定，也可从键盘输入。l 输出：迷宫、入口、出口与通路路径。思考l 假如每个点有8个试探方向东、东南、南、西南、西、西北、北、东北，如何修改程序？l 如何求得所有通路？l 如何求得最短通路？2火车车厢重排问题问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号一样，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。根本要求l 设计存储结构表示n个车厢、k个缓冲轨以与入轨和出轨；l 设计并实现车厢重排算法；l 分析算法的时间性能。思考l 如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？二、 数据结构设计迷宫问题和火车重排问题可以通过栈与队列实现的。迷宫的进出和车厢的出入轨和缓冲轨主要是对栈与队列的判断和操作。 int empty( STLink top,int n) /*判断是否为空*/ return (topn=NULL); int push(STLink top,int A,int m) /*入栈*/ STLink p;if(!(p=(STLink)malloc(LEN)return 0;else p-data=A;p-link=topm;topm=p;return 1; int pop(STLink top,int m) /*出栈*/ int A;STLink p;p=topm; A=p-data;topm=topm-link;free(p);return A;struct Node /定义队列int data;Node* next;三、算法设计1.迷宫问题：进入格子后，需要判断此时格子位置周围障碍物的位置，对其进展压栈，判断，然后看是否满足条件，满足就进栈，不满足就弹出，然后输出不能通过建立迷宫：typedef struct LStack Element elem;struct LStack *next;*PLStack;int InitStack(PLStack &S)S=NULL;return 1;int StackEmpty(PLStack S)if(S=NULL)return 1;elsereturn 0;int Push(PLStack &S, Element e)PLStack p;p=(PLStack)malloc(sizeof(LStack);p-elem=e;p-next=S;S=p;return 1;int Pop(PLStack &S,Element &e) PLStack p;if(!StackEmpty(S)e=S-elem;p=S;S=S-next;free(p);return 1;elsereturn 0;1迷宫线路的判断和寻找方法void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42)int i,j,d;int a,b;Element elem,e;PLStack S1, S2;InitStack(S1);InitStack(S2);mazestart.xstart.y=2;elem.x=start.x;elem.y=start.y;elem.d=-1;Push(S1,elem);while(!StackEmpty(S1)Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1; while(d(%d,%d,%d),e.x,e.y,e.d);return; if(mazeab=0) mazeab=2; elem.x=i;elem.y=j;elem.d=d;Push(S1,elem); i=a; j=b;d=-1;d+;printf(没找到走出此迷宫的路径n);2.火车重排问题1建立火车车厢的队列 LinkQueue:LinkQueue()Node* s=new Node;s-next=NULL;front=rear=s;LinkQueue:LinkQueue()Node* p=front;while(p!=NULL) Node*q=p; p=p-next; delete q; void LinkQueue:EnQueue(int x)Node* s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;int LinkQueue:DeQueue()if(!empty() /队列不空才能出队Node* p=new Node;p=front-next;int x=p-data;if(p-next=NULL)rear=front;delete p;return x;void LinkQueue:Trans()Node* p=front-next;while(p) if(p=NULL) break;elsecoutdatanext;2火车进入缓冲轨的判断 void PermuteTrans(int* arr,LinkQueue* a,int n,int k)int i=0;bool flag=true; /设置标志，初始为真while(in & flag) /当还有车厢没有进入缓冲轨时flag=false; /改变标志for(int j=0;jk;j+)if(aj.GetRear()next=NULL)/如果某条缓冲轨道的第一个车厢的编号小于即将进来的车厢编号，那么他就可以进入轨道/或者某条缓冲轨道空置的时候也可以进入轨道aj.EnQueue(arri); /入队列flag=true; /改变标志i+; /下标加一break;if(flag) /如果全部进入轨道，说明可以排cout1endl; for (int j=0;jk;j+) cout第(j+1)个缓存轨中的列车排序为endl; aj.Trans(); coutendl; else /否如此排不了cout0endl;四、界面设计1.对迷宫入口的提示输入，对迷宫路径的输出printf(输入入口的横坐标,纵坐标逗号隔开n);scanf(%d,%d,&start.x,&start.y);printf(n0=东 1=南 2=西 3=北 4为走出迷宫n通路为:(行坐标,列坐标,方向)n)；cout请输入车厢数n和缓冲轨数k：n;cout请输入列车排序：k;cout第(j+1)个缓存轨中的列车排序为endl; aj.Trans(); coutendl;五、运行测试与分析（1） 建立迷宫2.输出路径六、实验收获与思考通过本次实验，进一步增强了对栈和队列的理解，明白的栈的先进后出和队列先进先出的方式，对压栈和出入栈与队列有了深刻认识。教师评分：教师签字：9 / 9