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

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

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

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

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

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

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

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)。