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

迷宫问题实验报告迷宫问题实验报告引言：迷宫问题一直以来都是计算机科学领域中的研究热点之一。

迷宫是一个具有复杂结构的空间，其中包含了许多死胡同和通道，人们需要找到一条从起点到终点的最短路径。

在这个实验中，我们将通过使用不同的算法和技术来解决迷宫问题，并探讨它们的优缺点。

实验方法：我们首先建立一个虚拟的迷宫模型，使用二维数组来表示。

迷宫包含了墙壁、通道和起点终点。

我们通过设置不同的迷宫大小、起点和终点位置以及障碍物的分布来模拟不同的情况。

1. 广度优先搜索算法：广度优先搜索算法是一种常用的解决迷宫问题的算法。

它从起点开始，逐层地向外扩展搜索，直到找到终点或者遍历完所有的可达点。

在实验中，我们发现广度优先搜索算法能够找到一条最短路径，但是当迷宫规模较大时，算法的时间复杂度会急剧增加，导致搜索时间过长。

2. 深度优先搜索算法：深度优先搜索算法是另一种常用的解决迷宫问题的算法。

它从起点开始，沿着一个方向一直搜索到无法继续前进为止，然后回溯到上一个节点，选择另一个方向进行搜索。

在实验中，我们发现深度优先搜索算法能够快速找到一条路径，但是由于它的搜索策略是“深入优先”，因此无法保证找到的路径是最短路径。

3. A*算法：A*算法是一种启发式搜索算法，它综合了广度优先搜索和深度优先搜索的优点。

在实验中，我们将每个节点的代价定义为从起点到该节点的实际代价和从该节点到终点的预估代价之和。

A*算法通过优先选择代价最小的节点进行搜索，以期望找到一条最短路径。

实验结果表明，A*算法在大多数情况下能够找到最短路径，并且相对于广度优先搜索算法，它的搜索时间更短。

4. 遗传算法：除了传统的搜索算法外，我们还尝试了一种基于进化思想的遗传算法来解决迷宫问题。

遗传算法通过模拟生物进化过程中的选择、交叉和变异等操作来搜索最优解。

在实验中，我们将迷宫路径编码为一个个体，并使用适应度函数来评估每个个体的优劣。

经过多次迭代，遗传算法能够找到一条较优的路径，但是由于算法本身的复杂性，搜索时间较长。

Project1火车车厢重排调度年级：2014级学院：电子与信息工程学院班级：智能科学与技术、自动化姓名：*** 14350046 姓名：*** 14350045 姓名：*** 14350069【题目要求】1.问题：一列火车要将n节车厢分别送往n个车站，车站按照n,n-1,…,1的编号次序经过车站。

假设车厢的编号就是其目的地车站的编号。

2.要求：给定一个任意的车厢排列次序。

重新排列车厢，使其按照从1到n的次序排列。

规定重排调度时车厢只能从入轨到缓冲铁轨，或者从缓冲铁轨到出轨。

【数据结构与算法】本程序将栈的空间设为25（可以通过全局常量maxstack直接修改），栈的最大数量设为100（可以直接修改）。

可以处理任意少于100个任意次序车厢的火车重排调度问题。

流程图如图1：图1 总流程图【测试数据、结果及分析】实验1：顺序输入车厢节数：10车厢顺序：1 2 3 4 5 6 7 8 9 10测试结果如图2。

图2 实验1测试结果测试序列重排成功，使用0个栈，返回值正常，实验程序运行良好。

实验2：倒序输入车厢节数：10车厢顺序：10 9 8 7 6 5 4 3 2 1测试结果如图3。

图3实验2测试结果测试序列重排成功，使用1个栈，实验程序运行良好。

实验3：乱序输入车厢节数：10车厢顺序：3 2 4 5 7 8 9 6 1 10测试结果如图4。

图4实验3测试结果测试序列重排成功，使用7个栈，实验程序运行良好。

实验4：乱序输入车厢节数：25车厢顺序：25 2 6 4 5 3 7 23 9 19 11 12 16 14 15 13 17 18 10 22 21 20 8 24 1测试结果如图5。

图5 实验4测试结果测试序列重排成功，使用13个栈，实验程序运行良好。

实验五：乱序输入车厢节数：50车厢顺序：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48测试结果如下（由于太长无法完全截图，只能粘贴）：请输入火车车厢的个数：50请输入火车车厢次序（中间有间隔）：46 47 50 38 32 29 21 39 1 37 12 22 2 30 11 31 41 3 20 36 19 23 5 14 44 4 45 1335 8 24 40 7 28 43 16 27 34 6 42 15 26 10 17 9 33 18 25 49 48将第46车厢移动到缓冲轨道1将第47车厢移动到缓冲轨道2将第50车厢移动到缓冲轨道3将第38车厢移动到缓冲轨道1将第32车厢移动到缓冲轨道1将第29车厢移动到缓冲轨道1将第21车厢移动到缓冲轨道1将第39车厢移动到缓冲轨道2将第1车厢从入站轨道移动到出站轨道将第37车厢移动到缓冲轨道2将第12车厢移动到缓冲轨道1将第22车厢移动到缓冲轨道2将第2车厢从入站轨道移动到出站轨道将第30车厢移动到缓冲轨道3将第11车厢移动到缓冲轨道1将第31车厢移动到缓冲轨道4将第41车厢移动到缓冲轨道5将第3车厢从入站轨道移动到出站轨道将第20车厢移动到缓冲轨道2将第36车厢移动到缓冲轨道5将第19车厢移动到缓冲轨道2将第23车厢移动到缓冲轨道3将第5车厢移动到缓冲轨道1将第14车厢移动到缓冲轨道2将第44车厢移动到缓冲轨道6将第4车厢从入站轨道移动到出站轨道将第45车厢移动到缓冲轨道7将第5车厢从缓冲轨道1移动到出站轨道将第13车厢移动到缓冲轨道2将第35车厢移动到缓冲轨道5将第8车厢移动到缓冲轨道1将第24车厢移动到缓冲轨道4将第40车厢移动到缓冲轨道6将第7车厢移动到缓冲轨道1将第28车厢移动到缓冲轨道5将第43车厢移动到缓冲轨道7将第16车厢移动到缓冲轨道3将第27车厢移动到缓冲轨道5将第34车厢移动到缓冲轨道6将第6车厢从入站轨道移动到出站轨道将第42车厢移动到缓冲轨道7将第7车厢从缓冲轨道1移动到出站轨道将第15车厢移动到缓冲轨道3将第8车厢从缓冲轨道1移动到出站轨道将第26车厢移动到缓冲轨道5将第10车厢移动到缓冲轨道1将第17车厢移动到缓冲轨道4将第9车厢从入站轨道移动到出站轨道将第33车厢移动到缓冲轨道6将第10车厢从缓冲轨道1移动到出站轨道将第18车厢移动到缓冲轨道5将第11车厢从缓冲轨道1移动到出站轨道将第25车厢移动到缓冲轨道6将第12车厢从缓冲轨道1移动到出站轨道将第49车厢移动到缓冲轨道8将第13车厢从缓冲轨道2移动到出站轨道将第48车厢移动到缓冲轨道8将第14车厢从缓冲轨道2移动到出站轨道将第15车厢从缓冲轨道3移动到出站轨道将第16车厢从缓冲轨道3移动到出站轨道将第17车厢从缓冲轨道4移动到出站轨道将第18车厢从缓冲轨道5移动到出站轨道将第19车厢从缓冲轨道2移动到出站轨道将第20车厢从缓冲轨道2移动到出站轨道将第21车厢从缓冲轨道1移动到出站轨道将第22车厢从缓冲轨道2移动到出站轨道将第23车厢从缓冲轨道3移动到出站轨道将第24车厢从缓冲轨道4移动到出站轨道将第25车厢从缓冲轨道6移动到出站轨道将第26车厢从缓冲轨道5移动到出站轨道将第27车厢从缓冲轨道5移动到出站轨道将第28车厢从缓冲轨道5移动到出站轨道将第29车厢从缓冲轨道1移动到出站轨道将第30车厢从缓冲轨道3移动到出站轨道将第31车厢从缓冲轨道4移动到出站轨道将第32车厢从缓冲轨道1移动到出站轨道将第33车厢从缓冲轨道6移动到出站轨道将第34车厢从缓冲轨道6移动到出站轨道将第35车厢从缓冲轨道5移动到出站轨道将第36车厢从缓冲轨道5移动到出站轨道将第37车厢从缓冲轨道2移动到出站轨道将第38车厢从缓冲轨道1移动到出站轨道将第39车厢从缓冲轨道2移动到出站轨道将第40车厢从缓冲轨道6移动到出站轨道将第41车厢从缓冲轨道5移动到出站轨道将第42车厢从缓冲轨道7移动到出站轨道将第43车厢从缓冲轨道7移动到出站轨道将第44车厢从缓冲轨道6移动到出站轨道将第45车厢从缓冲轨道7移动到出站轨道将第46车厢从缓冲轨道1移动到出站轨道将第47车厢从缓冲轨道2移动到出站轨道将第48车厢从缓冲轨道8移动到出站轨道将第49车厢从缓冲轨道8移动到出站轨道将第50车厢从缓冲轨道3移动到出站轨道共用8个缓冲轨道结果分析：本程序可对少于100个任意次序车厢的火车进行调度。

⽕车车厢重排问题2014-11-04主要数据结构：栈题⽬：⼀列⽕车要将n节车厢分别送往n个车站按1~n的次序编号，⽕车按照n,n-1,…1的编号次序经过车站。

假设车厢的编号就是其⽬的地车站的编号。

要求：给定⼀个任意的车厢排列次序。

重新排列车厢，使其按照从1到n的次序排列。

规定重排时，只能从⼊轨到缓冲铁轨，或者从缓冲铁轨到出轨。

总的思路：⾸先：将所需要重排的车厢编号从左到右依次输⼊数组carrage中；然后：对carrage中的元素进⾏从左往右逐个遍历，如果符合下⼀个输出，则直接将其输出，并且遍历所有的缓冲轨道，查找是否有符合下⼀个输出的车厢，有的话便将其输出，否则将其压⼊缓冲轨道未经优化的代码：1 #include <iostream>2 #include <stack>3using namespace std;45 stack<int> stack_final;678void Output(int& minH, int& minS, stack<int> H[], int k, int n) {9// put the car from the strack to the output line, and change the minH and minS10int index; // the index of the car11//delete the minist car number from the minS12 stack_final.push(H[minS].top());13 H[minS].pop();14 cout << "Move car " << minH << "from holding track " << minS << " to output line" << endl;15//serch all the track's top, find the new minH and minS16 minH = n+2;17for (int i= 0; i < k; i++) {18if (!H[i].empty() && (index = H[i].top()) < minH) {19 minH = index;20 minS = i;21 }22 }23 }2425bool Input(int c, int& minH, int& minS, stack<int> H[], int k, int n) {26// put the new car c into the track27// if there is no available track, then return false, else return true28// find the best track for the car c29// initial30int BestTrack = 0; //the best track now31int BestTop = n+1; //the best track's top car32int index; //the index for the car33// search the k track34for (int i= 0; i < k; i++) {35if (!H[i].empty()) {36 index = H[i].top();37if (c < index && index < BestTop) {38//the top car's number is the smallest39 BestTop = index;40 BestTrack = i;41 }42 } else { // the track is empty43if (!BestTrack) {44 BestTrack = i;45 }46 }47 }48if (!BestTrack) {49return false; //there is available track to use50 }51 H[BestTrack].push(c);52 cout << "Move car " << c << "from input to holding track " << BestTrack << endl;53//if it is essencial, then change the minH and minS54if (c < minH) {55 minH = c;56 minS = BestTrack;57 }58return true;59 }6061bool Railroad(int input[], int n, int k) {62//k63// if it resort succed, then return true, else return false64// create the stack according to the k65 stack<int> *H;66 H = new stack<int> [k];67int NowOut = 1; // the next number of car to putout68int minH = n+1; //the minist number car in the k69int minS; //the minist number's strack70// resort the car71for (int i = n-1; i >= 0; i--) {72int number = input[i];73if (number == NowOut) {74 cout << "Move car " << number << " from the input line to the output line\n";75 stack_final.push(number);76 NowOut++;77while (minH == NowOut) {78 Output (minH, minS, H, k, n);79 NowOut++;80 }81 } else {82int end = 0;83for (int j = i; j > 0; j--) {84if (input[j-1] < input[j]) {85 end = j;86break;87 }88 }89for (int j = end; j <= i; j++) {90if (!Input (input[j], minH, minS, H, k, n)) {91return false;92 }93 }94if (end) {95 i = end;96 }97 }98 }99return true;100 }101102int main() {103int n, *input;104 cin >> n;105 input = new int[n];106for (int i = 0; i < n; i++) {107 cin >> input[i];108 }109if (Railroad(input, n, n-1)) {110 cout << "resort succed!\n";111while (!stack_final.empty()) {112 cout << stack_final.top() << "";113 stack_final.pop();114 }115 } else {116 cout << "failed\n";117 }118 }View Code经过优化之后的代码：增加的条件：车厢可以从排在后⾯的缓冲轨道移到前⾯的缓冲轨道。

实验报告了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。

所以，给定任意次序的车厢，必须重新排列它们。

车厢的重排工作可以通过转轨站完成。

在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。

假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。

②基本要求●设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；●设计并实现车厢重排算法；●分析算法的时间性能。

③思考●如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？二、数据结构设计迷宫问题和火车重排问题可以通过栈与队列实现的。

迷宫的进出和车厢的出入轨和缓冲轨主要是对栈与队列的判断和操作。

int empty( STLink top[],int n) /*判断是否为空*/{return (top[n]==NULL);}int push(STLink top[],int A,int m) /*入栈*/{STLink p;if(!(p=(STLink)malloc(LEN)))return 0;else{p->data=A;p->link=top[m];top[m]=p;return 1;}}int pop(STLink top[],int m) /*出栈*/{int A;STLink p;p=top[m];A=p->data;top[m]=top[m]->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;}（2）.输出路径2.火车车厢排序六、实验收获与思考通过本次实验，进一步增强了对栈和队列的理解，明白的栈的先进后出和队列先进先出的方式，对压栈和出入栈与队列有了深刻认识。

火车车厢重排问题1.1火车车厢重排问题一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1~n,货运列车按照第n站至第1站的顺序经过这些车站。

车厢编号与他们的目的地一样。

为了便于从列车上卸掉相应的车厢，必须重排车厢顺序，使得各车厢从前往后按编号1到n的次序排列。

当所有车厢按照这种次序排列时，在每个车站只需卸掉最后一个车厢即可。

1.2想法一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。

比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排我们在一个转轨站里完成重拍的工作，在转轨站有一个入轨，一个出轨和k个缓冲轨（位于入轨和出轨之间）。

下面的图示就是一个转轨站，其中有3个缓冲轨，H1,H2,H3。

（PPT中有动态演示）1.3算法描述：那么缓冲轨就不是FILO 而是FIFO了那么就要用队列来实现车厢重排了，算法的描述和栈实现的基本一样的，只是OutPut和Hold 函数改了一下，将一截车厢移动到缓冲轨时，车厢c应该移动到这样的缓冲轨中：该缓冲轨中现有各车厢的编号均小于c，如果有多个缓冲轨都满足这一条件，那么选择其中左端车厢编号最大的那个缓冲轨，否则选择一个空的缓冲轨(如果存在的话)1.4代码：#include<iostream>#include<stack>usingnamespace std;template<class T>void PrintfNum(T a[], constint& n);// move cars from holding track to output trackvoid OutPut(stack<int> t[],int n, int totalStack,int& min){//move car from holding trackfor(int x = 0;x <totalStack; ++x){if(!t[x].empty() && t[x].top() == min){cout<<"Move car "<< t[x].top() <<" from holding track "<< x <<" to output"<<endl;t[x].pop();++min;x = -1; // find next car from the first holding track 0}}}// move cars from input track to holding trackbool Hold(stack<int> t[],int n , int totalStack){for(int i = 0;i <totalStack; ++i){if(t[i].empty() || (!t[i].empty() && t[i].top() > n)){cout<<"holding track "<<i<<" hold car "<< n <<endl;t[i].push(n);returntrue; // we already find a holding track, so break the loop. }}returnfalse;}int main(int argc, char* argv[]){constint NUM = 9;constint STACKNUM = 3;stack<int> t[STACKNUM];int min = 1;int a[NUM] = {5,8,1,7,4,2,9,6,3};PrintfNum(a,NUM);for(int i = NUM - 1; i>= 0; --i){if(a[i] == min){// try to move cars from input track or holding track cout<<"Move car "<< a[i] <<" from input to output"<<endl;++min;OutPut(t,a[i],STACKNUM,min);}else{// move cars from input track to holding trackif(!Hold(t,a[i],STACKNUM)){cout<<"Not enough holding track"<<endl;break;}}} getchar();return 0;}template<class T>void PrintfNum(T a[], constint& n){for(int i = 0; i< n; ++i){cout<< a[i] <<",";}cout<<endl;}1.5火车车厢重排问题决策过程H1H2H31.5.1初始数组H1 H2 H31.5.2H1H2H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1H2 H3H1 H2 H3H1 H2 H3H1 H2 H3H1 H2 H3 1．6程序运行截图。

实验2用堆栈解决火车车厢重排问题的编程一、目的通过对本次实验，我们应：1、加深对线性表、堆栈的认识；2、加深接口、类、索引器的认识；3、掌握堆栈数据结构，并应用堆栈编程解决实际问题。

二、实验准备1、软件准备：C#.net。

2、参考数据（示例）：文件夹“…\实验2\示例”中的数据。

三、实验背景描述1、问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。

车厢的编号与它们的目的地相同。

为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。

当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。

图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。

开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。

在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。

图3.1b 给出了按所要求的次序重新排列后的结果。

图2.1根据上面的描述，编写程序实现下面的功能：编写一算法实现火车车箱的重排；编写程序模拟图2.1所示的具有9节车厢的火车入轨和出轨的过程。

程序主界面设计如图2.2所示。

图2.22、问题分析为了重排车厢，需从前至后依次检查入轨上的所有车厢。

如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。

如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。

缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。

当缓冲铁轨上的车厢编号不是按照从顶到底的递增次序排列时，重排任务将无法完成。

新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v>u,且v是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。

计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级 10级计算机工程
02
试验地点 计算机大楼计工教研室
学生学号 1005080222 指导教师 蔡琼 学生姓名 肖宇博
试验时间
2012-4-21
试验项目 算法与数据结构
试验类别
基础性（） 设计性（） 综合性（√） 其它（ ） 试验目的及要求
（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。

成 绩 评 定 表
类 别 评 分 标 准 分值 得分 合 计
上机表现
积极出勤、遵守纪律 主动完成设计任务 30分
程序与报告
程序代码规范、功能正确 报告详实完整、体现收获
70分
goto label2;
}
else if(r!=0)
{
printf("重排前的序列为\n");
for(i=1;i<=k;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
printf("排列后的车厢号为：\n");
reset(q,w1,w2,k);
}
else
{
printf("我也不知道错哪了？'");
}
}
四、测试用例（尽量覆盖所有分支）
1.输入正确的序列后得到结果如图：
2.倒输这几个数如图：
3.顺序输这个序列
4.如果输入的车厢数有误的时候（为负数或零）
5.如果输入的序列不是连续自然数。

火车车厢重排问题栈c语言火车车厢重排问题是一个经典的问题，考验了数据结构和算法的运用。

这个问题可以很好地帮助我们了解如何使用栈这种数据结构来解决实际问题，并且可以通过编写C语言程序对其进行求解。

在本文中，我们将深入探讨火车车厢重排问题，并编写C语言程序实现问题的求解。

首先，让我们来了解一下火车车厢重排问题的具体描述。

假设有一列火车车厢按照编号从1到n的顺序排列在轨道上。

现在我们需要将这些车厢按照特定的顺序重新排列，给定一个目标排列，我们需要找出一种排列车厢的方法，使得最终的排列符合目标排列。

具体而言，对于每一个车厢，我们可以将其从原来的位置移动到一个临时的缓冲轨道中，然后再将其移动到目标位置。

这个问题的关键在于如何确定每个车厢应该如何移动才能满足最终的目标排列。

为了解决这个问题，我们可以使用栈这种数据结构来辅助实现。

栈是一种先进后出的数据结构，这样的特性非常适合用来模拟火车车厢的重排过程。

具体而言，我们可以将原始轨道上的车厢编号序列作为输入，然后使用栈来模拟车辆的移动过程，最终得到目标排列。

下面我们将通过C语言程序来实现这个过程。

首先，我们需要定义一个栈的数据结构，来模拟车厢的移动过程。

我们可以使用数组来实现这个栈，同时需要定义一个栈顶指针来表示当前栈顶元素的位置。

另外，我们还需要定义一个函数来模拟入栈和出栈的过程。

接下来，让我们来具体实现这个栈的数据结构和相关的函数。

```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} Stack;void init(Stack *s) {s->top = -1;}void push(Stack *s, int value) { if (s->top < MAX_SIZE - 1) {s->top++;s->data[s->top] = value;} else {printf("Stack overflow\n");}}int pop(Stack *s) {if (s->top >= 0) {int value = s->data[s->top];s->top--;return value;} else {printf("Stack underflow\n"); return -1;}}int main() {Stack s;init(&s);//对栈进行入栈和出栈操作push(&s, 1);push(&s, 2);push(&s, 3);printf("%d\n", pop(&s)); //输出3printf("%d\n", pop(&s)); //输出2printf("%d\n", pop(&s)); //输出1printf("%d\n", pop(&s)); //输出Stack underflow，表示栈已空return 0;}```在这段代码中，我们定义了一个栈的数据结构，并实现了栈的初始化、入栈和出栈操作。

迷宫问题实验报告引言迷宫问题是一个经典的计算机科学问题，涉及到寻找在迷宫中的一条路径，从入口到出口。

在本次实验中，我们使用了一种称为“step by step thinking”的方法来解决迷宫问题。

步骤一：定义问题在解决迷宫问题之前，我们首先需要明确问题的定义。

迷宫可以被视为一个二维的网格，其中某些单元格被阻塞，表示不能通过的墙壁，而其他单元格则可以通过。

我们的目标是找到一条从迷宫的入口到出口的路径。

步骤二：设计算法为了解决迷宫问题，我们需要设计一个算法。

在本实验中，我们选择了深度优先搜索（DFS）算法，它是一种经典的解决迷宫问题的方法。

深度优先搜索算法的基本思想是从起点开始，沿着一个方向前进，直到无法继续前进为止。

然后，我们回溯到上一个位置，选择下一个可行的方向，继续前进，直到我们找到出口或者所有的路径都被尝试过。

步骤三：实现算法在实现算法之前，我们首先需要将迷宫表示为一个数据结构。

我们可以使用一个二维数组来表示迷宫，其中阻塞的单元格可以用一个特定的值（比如0）表示，可以通过的单元格用另一个值（比如1）表示。

接下来，我们可以使用递归的方式实现深度优先搜索算法。

我们从起点开始，以递归的方式探索迷宫的每一个可能路径。

当我们找到出口时，我们返回一个成功的路径。

如果我们无法找到出口，我们返回一个失败的路径。

步骤四：验证算法为了验证我们的算法是否正确，我们需要进行一些实验。

我们可以选择几个不同的迷宫，包括一些简单的迷宫和一些复杂的迷宫，然后使用我们的算法来找到一条路径。

在实验过程中，我们可以观察到算法找到的路径是否符合我们的预期。

如果算法找到了一条路径，我们可以检查路径是否是从起点到出口，并且没有穿越任何阻塞单元格。

如果算法未能找到一条路径，我们可以检查迷宫是否存在一条路径，或者是否存在问题导致算法无法找到路径。

步骤五：总结和讨论通过实验，我们发现“step by step thinking”的方法可以有效地解决迷宫问题。

数据结构实验报告实验名称：实验二——题目5学生姓名：班级：班内序号：学号：日期：2011年11月7日1．实验要求利用队列结构实现车厢重排问题。

车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。

给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。

转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。

开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。

缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。

2. 程序分析将每个轨道视为一个队列，每一个车厢视为一个结构体的结点，结点存储车厢编号以及下一节车厢的地址。

用尾插法建立队列，并根据队列队尾入队，队头出队的特点实现结点的出队以及入队。

由于车厢在重排过程中将会频繁进行入队以及出队的操作，如果采用顺序存储结构，则在结点出入队时是操作将会十分不方便，还会占用大量多余的空间和时间，故选用链式存储结构，可以直接调动结点，十分简洁。

重排过程比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面。

在把车厢c 移至缓冲轨是，车厢c应该移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择对位车厢编号最大的缓冲轨，否则选择一个空的缓冲轨。

这样，出轨的时候才可以按照从小到大的顺序重新编排。

2.1 存储结构2.2 关键算法分析1. 移动车厢算法（车厢要从a队列移至b队列）·自然语言描述（1）判断a队列是否为空，为空则输出“队列下溢”，提示出错。

（2） 否则，设置工作指针p 指向a 队列的队头元素，（3） 将b 的尾指针指向next 域指向p ；（4） b 队列的尾指针后移，指向p 指向的结点；（5） a 头结点指向p 后一个结点（6） p 的next 域置为空，完成一次车厢的移动（7） a 队列车厢数减1，b 队列车厢数加1·伪代码描述两个队列，车厢要从a 队列移至b 队列；（1）bus* p=a.front->next;（2）if(!p) cout<<"Underflow"<<endl;（3）b.rear->next=p;（4）b.rear=b.rear->next;（5）a.front->next=p->next;（6）p->next=NULL;（7）if(!(a.front->next))a.rear=a.front;（8）a.Number--;b.Number++;图示ab算法时间复杂度O(1)，空间复杂度S(1)。

一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。

二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。

为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。

所以，给定任意次序的车厢，必须重新排列它们。

车厢的重排工作可以通过国转轨站完成。

在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。

假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。

(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：2222(a) 将369、247依次入缓冲轨(b) 将1移至出轨，234移至出轨(c) 将8入缓冲轨，5移至出轨(d) 将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：四、源程序代码#include<iostream>using namespace std;const MS=100;template <class T>struct QNode{T data;QNode<T> *next;};template <class T>class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template <class T>LiQueue<T>::LiQueue( ){QNode <T> *s;s=new QNode<T>;s->next=NULL;front=rear=s;}template <class T>LiQueue<T>::~LiQueue( ){QNode <T> *p;while(front){p=front;front=front->next;delete p;}}template <class T>void LiQueue<T>::EnQueue(T x){QNode<T> *s;s=new QNode<T>;s->data=x; //申请一个数据域为x的结点ss->next=NULL;rear->next=s; //将结点s插入到队尾rear=s;}template <class T>T LiQueue<T>::DeQueue(){QNode <T> *p; int x;if (rear==front) throw "下溢";p=front->next;x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为1delete p;return x;}template <class T>T LiQueue<T>::GetFront(){if (rear!=front)return front->next->data;}template <class T>T LiQueue<T>::GetRear(){if(rear!=front)return rear->data;}template <class T>bool LiQueue<T>::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout<<"请输入火车(货运列车）的车厢个数为："<<endl;cin>>n;cout<<"请输入转轨站的缓冲轨个数为："<<endl;cin>>k;}void Train::ChongPai(){int a[MS];LiQueue<int>*b;b=new LiQueue<int>[k+2];cout<<"请输入车厢入轨编号次序："<<endl;for(int i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<<endl;th=1;while(b[k].Empty()){int xx=b[k].DeQueue();if(xx==th){cout<<th<<"号车厢直接移至出轨"<<endl;b[k+1].EnQueue(th);th++;int j=0;while(b[j].Empty()){int x=b[j].GetFront();if(x==th){cout<<x<<"号车厢从"<<j+1<<"号缓冲轨出轨"<<endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{int j=0,u=5;while(b[j].Empty()&&j<k){if(xx<b[j].GetRear())j++;else{cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&j<k){cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);}if(j==k-1){cout<<"\n缓冲轨不够，重排车厢失败\n";return;}}}cout<<"车厢依次出轨的编号为：";while(b[k+1].Empty())cout<<b[k+1].DeQueue()<<" ";cout<<endl;}void main(){Train a;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。

一、实验目的本实验旨在通过设计并实现一个迷宫求解系统，加深对队列数据结构及其在算法中的应用的理解。

通过使用队列实现迷宫问题的求解，我们可以了解广度优先搜索（BFS）算法的基本原理，并学会如何将实际问题转化为数据结构支持的算法问题。

二、实验内容1. 迷宫定义及表示- 迷宫由一个二维数组表示，其中每个元素代表迷宫的一个单元格。

- 元素0表示通路，元素1表示障碍。

- 迷宫的入口和出口分别用特定的标记表示。

2. 数据结构设计- 使用队列作为存储结构，用于存储待访问的单元格。

- 设计一个辅助函数，用于判断一个单元格是否为障碍、是否已访问过以及是否为相邻单元格。

3. 算法设计- 采用广度优先搜索算法（BFS）进行迷宫求解。

- 从入口单元格开始，将单元格入队，并标记为已访问。

- 当队列不为空时，依次从队列中取出单元格，并探索其四个相邻单元格。

- 如果相邻单元格为通路且未访问过，则将其入队并标记为已访问。

- 当找到出口时，算法结束。

4. 路径输出- 使用一个栈来存储从入口到当前单元格的路径。

- 当找到出口时，将栈中的元素逆序输出，得到从入口到出口的路径。

三、实验步骤1. 初始化迷宫- 输入迷宫的尺寸，生成一个随机迷宫或手动输入迷宫数据。

- 初始化队列和栈。

2. 广度优先搜索- 将入口单元格入队，并标记为已访问。

- 循环执行以下步骤，直到找到出口或队列为空：- 从队列中取出一个单元格。

- 探索该单元格的四个相邻单元格。

- 如果相邻单元格满足条件，将其入队并标记为已访问。

- 将当前单元格加入栈。

3. 输出路径- 如果找到出口，则将栈中的元素逆序输出，得到从入口到出口的路径。

- 如果队列为空，则表示迷宫没有路径。

四、实验结果与分析1. 实验结果- 通过实验，我们成功地使用队列实现了迷宫问题的求解，并得到了从入口到出口的路径。

- 实验过程中，我们观察到BFS算法在迷宫求解中具有较高的效率，尤其是在迷宫规模较大时。

2. 实验分析- 广度优先搜索算法在迷宫求解中具有较高的效率，因为它能够尽快地找到出口。

实验报告1．实验要求利用队列结构实现车厢重排问题。

车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。

给定任意次序的车厢，的车厢编号。

提示：一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。

比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。

2. 程序分析2.1 存储结构本程序采用单链表结构，具体为链队列结构，使用队列结构的先进先出原则可以较好地处理车厢重排问题。

链队列结构示意图如下：2.2 关键算法分析一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下：void TrainPermute():1. 初始化条件:计数器i=0,与非门aa=12. 判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)2.1将aa置空；2.2用for循环，依次取入入轨中的每一个车厢的编号进入合适的缓冲轨；2.2.1如果缓冲轨中尾指针比进入缓冲轨元素小，则进入该缓冲轨；计数器i+1;有合适缓冲轨，将aa变为真;跳出for循环并进入while循环；2.2.2如果缓冲轨中第一个元素为空，则进入缓冲轨成为第一个元素；计数器i+1;有合适缓冲轨，将aa变为真;跳出for循环并进入while循环；2.3 用aa判断是否有进入合适的缓冲轨2.3.1 aa=0即没有合适的缓冲轨，则输出无法排列；2.3.2 aa=1即有合适的缓冲轨，则2.3.2.1遍历缓冲轨，输出每个缓冲轨按顺序存储的车厢；2.3.2.2 按从小到大的顺序出轨for(引入输出轨计数器newOut=1;newOut<n; newOut+1;)newOut与每个队列的头元素比较若相等，则元素出队；输出显示；具体代码如下：void TrainPermute(int arr[],LinkQueue<int> a[],int n,int k){int i=0;bool aa=1;while((i<n)&&(aa)) //当入轨中有车厢时{for(int m=0;m<k;m++){if(a[m].GetRear()<arr[i]){a[m].EnQueue(arr[i]);i++;}if(a[m].front->next==NULL){a[m].EnQueue(arr[i]);aa=1;i++;break;}}}if(aa==0) //当无法将入轨中队头车厢移至合适缓冲轨中时，程序结束{cout<<"车厢无法重排,算法结束"<<endl;}else //当入轨中已经没有车厢时{for(int m=0;m<k;m++){cout<<"第"<<(m+1)<<"个缓冲轨的列车编号";a[m].Trans();cout<<endl;}cout<<"火车车厢出轨顺序为:"<<endl;for(int newOut=1;newOut<=n;newOut++){for(int j=0;j<k;j++) //扫描缓冲轨，将其队头元素依次由小到大输出{if(a[j].GetFront()==newOut){cout<<a[j].DeQueue()<<" ";}}}}}二、主函数伪代码如下：1. 输入n与k值，若输入值错误，则程序结束；2. 通过循环结构为数组array[]赋值，具体分析见代码；3. 输出入轨中火车车厢号码排列；4. 调用TrainPermute()函数；三、为array[]随机赋值的基本思想为：设置计数器count=0，设置数组ifmark[]来标记array[]赋值情况，依次将1至n等n个数随机赋给array[]，其中，若array[t]未被赋值，即ifmark[t]=0，则将值赋给array[t]，计数器加一；若array[t]已被赋值，即ifmark[t]=1，则重新开始循环。

一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。

二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。

假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。

为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。

所以，给定任意次序的车厢，必须重新排列它们。

车厢的重排工作可以通过国转轨站完成。

在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。

假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。

(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：2222(a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨 (d) 将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：四、源程序代码#include<iostream>using namespace std;const MS=100;template <class T>struct QNode{T data;QNode<T> *next;};template <class T>class LiQueue{public:LiQueue( ); //构造函数，初始化一个空的链队列~LiQueue( ); //析构函数，释放链队列中各结点的存储空间void EnQueue(T x); //将元素x入队T DeQueue( ); //将队头元素出队T GetFront( ); //取链队列的队头元素T GetRear();bool Empty( ); //判断链队列是否为空QNode<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template <class T>LiQueue<T>::LiQueue( ){QNode <T> *s;s=new QNode<T>;s->next=NULL;front=rear=s;}template <class T>LiQueue<T>::~LiQueue( ){QNode <T> *p;while(front){p=front;front=front->next;delete p;}}template <class T>void LiQueue<T>::EnQueue(T x){QNode<T> *s;s=new QNode<T>;s->data=x; //申请一个数据域为x的结点ss->next=NULL;rear->next=s; //将结点s插入到队尾 rear=s;}template <class T>T LiQueue<T>::DeQueue(){QNode <T> *p; int x;if (rear==front) throw "下溢";p=front->next;x=p->data; //暂存队头元素front->next=p->next; //将队头元素所在结点摘链if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p;return x;}template <class T>T LiQueue<T>::GetFront(){if (rear!=front)return front->next->data;}template <class T>T LiQueue<T>::GetRear(){if(rear!=front)return rear->data;}template <class T>bool LiQueue<T>::Empty( ){if(front==rear) return 0;else return 1;}class Train{private :int n,k,th;public :Train();void ChongPai();};Train::Train(){cout<<"请输入火车(货运列车）的车厢个数为："<<endl;cin>>n;cout<<"请输入转轨站的缓冲轨个数为："<<endl;cin>>k;}void Train::ChongPai(){int a[MS];LiQueue<int>*b;b=new LiQueue<int>[k+2];cout<<"请输入车厢入轨编号次序："<<endl;for(int i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)b[k].EnQueue(a[i]);cout<<"则进行车厢重排过程如下:"<<endl;th=1;while(b[k].Empty()){int xx=b[k].DeQueue();if(xx==th){cout<<th<<"号车厢直接移至出轨"<<endl;b[k+1].EnQueue(th);th++;int j=0;while(b[j].Empty()){int x=b[j].GetFront();if(x==th){cout<<x<<"号车厢从"<<j+1<<"号缓冲轨出轨"<<endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{int j=0,u=5;while(b[j].Empty()&&j<k){if(xx<b[j].GetRear())j++;else{cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&j<k){cout<<xx<<"号车厢移至"<<j+1<<"号缓冲轨"<<endl;b[j].EnQueue(xx);}if(j==k-1){cout<<"\n缓冲轨不够，重排车厢失败\n";return;}}}cout<<"车厢依次出轨的编号为：";while(b[k+1].Empty())cout<<b[k+1].DeQueue()<<" ";cout<<endl;}void main(){Train a;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。

迷宫问题实验报告迷宫问题实验报告引言：迷宫问题一直以来都是人们感兴趣的话题之一。

从古至今，人们一直试图解决迷宫问题，探索其中的奥秘。

本次实验旨在通过设计和构建迷宫，以及使用不同的解决方法来探索迷宫问题的解决策略，并对实验结果进行分析和总结。

实验设计：为了模拟真实的迷宫情境，我们设计了一个迷宫模型。

迷宫模型由一系列连通的房间和通道组成，每个房间都有多个出口，其中只有一个通向出口，其他出口通向死胡同。

我们使用纸板和胶水构建了迷宫模型，并在模型的起点和终点处标记了符号以便于记录和分析。

实验过程：在实验开始之前，我们首先确定了迷宫的起点和终点，并确保迷宫模型的结构复杂性和难度适当。

然后，我们邀请了一些志愿者参与实验。

志愿者们被要求从迷宫的起点处开始，通过选择不同的通道来寻找通向终点的路径。

他们可以使用不同的策略，如随机选择、右手法则、左手法则等来解决迷宫问题。

实验结果：通过观察和记录志愿者们的行为和选择，我们得出了以下实验结果：1. 随机选择策略：部分志愿者采用随机选择策略，即在每个房间中随机选择一个出口。

然而，这种策略并没有明显的优势，因为志愿者们往往陷入死胡同，无法找到通向终点的路径。

2. 右手法则：另一部分志愿者采用右手法则，即在每个房间中选择右边的出口。

这种策略相对较好，因为志愿者们能够逐渐接近终点，但是在复杂的迷宫结构中，他们可能会陷入循环，无法找到最短路径。

3. 左手法则：还有一些志愿者选择了左手法则，即在每个房间中选择左边的出口。

与右手法则相比，左手法则的效果稍差，因为志愿者们往往会绕远路，增加了寻找路径的时间和距离。

讨论与分析：通过对实验结果的分析，我们可以得出以下结论：1. 迷宫问题具有一定的复杂性和难度，随机选择策略并不是一个有效的解决方法。

在复杂的迷宫结构中，随机选择往往导致陷入死胡同，无法找到通向终点的路径。

2. 右手法则是一种相对有效的解决方法，尤其在简单的迷宫结构中。

通过选择右边的出口，志愿者们能够逐渐接近终点。

实习2栈的应用本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。

实验课时6课时程序1：迷宫问题［问题描述］以一个m×n的长方阵表示迷宫，‘0’和‘1’分别表示迷宫中的通路和障碍。

设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

［基本要求］首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

如：对下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），…［测试数据］迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。

[实现提示]计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道，可以二维数组存储迷宫数据。

[程序实现]#include<stdio.h>#include<stdlib.h>//1.迷宫位置坐标类型typedefstruct{intx;//行inty;//列}PosType;#defineMAXENGTH25//迷宫最大行列数位25typedefintMazeType[MAXENGTH][MAXENGTH];//迷宫数列typedefstruct//定义栈{intord;//通道块在路径上的序号PosTypeseat;//通道块在迷宫中的位置intdi;//走向下一块的方向（0~3表示东、南、西、北）}SElemType;//2.全局变量MazeTypem;//迷宫数组intcurstep=1;//当前位置，初值为1#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量//3.栈的顺序存储表示typedefstructSqStack{SElemType*base;//尾指针SElemType*top;//头指针intstacksize;//栈大小}SqStack;//顺序表//4.构造空栈intInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(S.base))exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}//5.判断栈是否为空（用来判断迷宫是否不可达到出口）intStackEmpty(SqStackS){if(S.top==S.base)//栈底与栈顶相等为空栈return1;elsereturn0;}//6.插入元素intPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize)//栈顶-栈底>=栈长，说明空间已满{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof (SElemType));if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*(S.top)++=e;return1;}//7.栈不为空时，删除栈顶元素，用e返回（用于当栈顶元素各方向均不通时，将其从路径中删除）intPop(SqStack&S,SElemType&e){if(S.top==S.base)return0;e=*--S.top;//先将S.top的值赋给e，再将S.top向下移一位return1;}//8.判断迷宫m中b点是否可通过（是1，否0），其中墙为0，可通过路径为1，不可通过路径为-1int Pass(PosTypeb){if(m[b.x][b.y]==1)return1;elsereturn0;}//9.是迷宫m中a的序号变为足迹（即该位置目前可通过）voidFootPrint(PosTypea){m[a.x][a.y]=curstep;}//10.根据当前位置方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};c.x+=direc[di].x;c.y+=direc[di].y;returnc;}//11.道路不能通过时（即为死路），将其标记为-1voidMarkPrint(PosTypeb){m[b.x][b.y]=-1;}//12.求迷宫出口intMazePath(PosTypestart,PosTypeend){SqStackS;PosTypecurpos;//当前位置SElemTypee;InitStack(S);curpos=start;do{if(Pass(curpos)){FootPrint(curpos);e.ord=curstep;e.di=0;Push(S,e);curstep++;if(curpos.x==end.x&&curpos.y==end.y)return1;curpos=NextPos(curpos,e.di);}else{if(!StackEmpty(S)){Pop(S,e);curstep--;while(e.di==3&&!StackEmpty(S)){MarkPrint(e.seat);Pop(S,e);curstep--;}if(e.di<3){e.di++;Push(S,e);curstep++;curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));return0;}//13.输出迷宫结构voidPrint(intx,inty){inti,j;for(i=0;i<x;i++){for(j=0;j<y;j++)printf("%3d",m[i][j]);printf("\n");}}//14.主函数intmain(){PosTypebegin,end;inti,j,x,y,x1,y1;printf("请输入迷宫行列数（包括外墙）:（空格隔开）\n");scanf("%d%d",&x,&y);for(i=0;i<x;i++)//定义外墙{m[0][i]=0;m[x-1][i]=0;}for(j=0;j<y-1;j++){m[j][0]=0;m[j][y-1]=0;}for(i=1;i<x-1;i++)for(j=1;j<y-1;j++)m[i][j]=1;//墙内初始值均为1//输入迷宫中墙的个数printf("输入墙的个数：");scanf("%d",&j);//安排墙的位置printf("请输入墙的位置（坐标），用空格隔开:\n");for(i=1;i<=j;i++){scanf("%d%d",&x1,&y1);m[x1][y1]=0;}printf("迷宫结构如下\n");Print(x,y);printf("请输入起点坐标：\n");scanf("%d%d",&begin.x,&begin.y);printf("请输入终点坐标：\n");scanf("%d%d",&end.x,&end.y);if(MazePath(begin,end)){printf("此迷宫的一条路径如下:\n");Print(x,y);}elseprintf("此迷宫无法到达出口\n");return0;}[实验结果]。

迷宫实验报告范文**迷宫实验报告****一、实验目的**1.理解迷宫问题的背景和相关概念；2.熟悉迷宫实验的规则和步骤，培养解决问题的能力；3.探究迷宫问题的求解方法及其效果。

**二、实验原理**1.迷宫问题：在一个固定的区域内，寻找从起点到终点的路径，期间避免碰到障碍物；2.深度优先算法（DFS）：从起点出发，每次选择一个没有访问过的相邻节点继续深入，直到找到终点或者无路可走；3.广度优先算法（BFS）：从起点出发，按照距离逐层，直到找到终点；4.A*算法：结合了启发函数和广度优先。

**三、实验步骤**1.首先，我们创建一个M*N的矩阵，用来表示迷宫。

其中，起点用"S"表示，终点用"E"表示，空格用"."表示，障碍物用"#"表示；2.然后，我们使用深度优先算法和广度优先算法分别求解迷宫问题；2.1深度优先算法（DFS）：从起点出发，每次选择一个没有访问过的相邻节点继续深入，直到找到终点或者无路可走；2.2广度优先算法（BFS）：从起点出发，按照距离逐层，直到找到终点；3.最后，我们使用A*算法求解迷宫问题。

A*算法结合了广度优先和启发函数，其中，启发函数用来估计每个节点到终点的距离。

**四、实验结果及分析**我们使用以上三种方法求解迷宫问题，并将结果进行比较：1.深度优先算法（DFS）：该算法能够找到至少一条路径，但是并不能保证找到最短路径。

它倾向于选择一个方向一直走下去，直到无路可走，然后回溯到上一个节点继续探索。

这种算法在迷宫问题中很容易陷入局部最优解，但是效率较高。

2.广度优先算法（BFS）：该算法可以保证找到最短路径，但是需要更长的时间和更大的空间。

它按照距离逐层，直到找到终点。

由于要保存每一层的节点，所以空间复杂度较高。

3.A*算法：该算法结合了广度优先和启发函数，能够找到最短路径，并且效率高。

启发函数用来估计每个节点到终点的距离，通过这个估计值，可以优先选择离终点更近的节点进行，从而提高效率。