下载文档原格式
⽕车车厢重排问题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.火车车厢排序六、实验收获与思考通过本次实验，进一步增强了对栈和队列的理解，明白的栈的先进后出和队列先进先出的方式，对压栈和出入栈与队列有了深刻认识。
数据结构实验报告实验名称:实验二一一栈和队学生姓名:申宇飞班级：班内序03号：学号：日期2013年11月18日：1- 实验要求1.1实验目的：通过选择卞面五个题目之一进行实现，掌握如卞内容：>进一步掌握指针、模板类、异常处理的使用>掌握栈的操作的实现方法>掌握队列的操作的实现方法>学习使用栈解决实际问题的能力>学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。
要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试mainO函数测试线性表的正确性。
2.程序分析2.1存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。
第］页北京邮电大学信息与通信工程学院data next栈顶栈底关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1)Node<T> * s = new Node<T>;2)p->data = x;3)p->next = top;4)top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1)if(EmptyO)throw" F溢“；2)T x = top->data;3)Node<T> * p = top;4)top = top->next;5)elete p;三、链栈的取栈顶元素算法步骤：自然语言描述：1、判断栈是否为空第3页2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(EmptyO)tlu'ow H卜溢"；2)Node<T>*p=top;3)cout«p->data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p 伪代码描述：1)Node<T>*p = top;2)while(p !=NULL)3)cout« p->data ;4)p = p->next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1)while(top)2)strnct Node <T> * p = top;3)top = top->next;4)deletep; 时间复杂的：0(1)。
实验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是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。
火车车厢重排问题栈c语言以下是一个用C语言实现火车车厢重排问题的代码：```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {int val;struct Node* next;} Node;typedef struct {Node* top;} Stack;Stack* createStack() {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->top = NULL;return stack;}int isEmpty(Stack* stack) {return (stack->top == NULL);}void push(Stack* stack, int val) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = val;newNode->next = stack->top;stack->top = newNode;}int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}int val = stack->top->val;Node* temp = stack->top;stack->top = stack->top->next;free(temp);return val;}int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty.\n");return -1;}return stack->top->val;}int canReorder(int numCars, int cars[]) { Stack* stationStack = createStack(); Stack* branchStack = createStack(); int nextCar = 1;for (int i = 0; i < numCars; i++) {// 如果当前车厢和需要出站的车厢一致，直接出站if (cars[i] == nextCar) {nextCar++;continue;}// 将从站台出来的车厢压入分支轨道while (!isEmpty(stationStack) && peek(stationStack) == nextCar) {push(branchStack, pop(stationStack));nextCar++;}// 当前车厢进站push(stationStack, cars[i]);}// 如果分支轨道中的车厢可以按顺序出站，则返回1，否则返回0while (!isEmpty(branchStack)) {if (pop(branchStack) != nextCar) {return 0;}nextCar++;}return 1;}int main() {int numCars;int cars[MAX_SIZE];printf("Enter the number of train cars: ");scanf("%d", &numCars);printf("Enter the train car numbers: ");for (int i = 0; i < numCars; i++) {scanf("%d", &cars[i]);}int result = canReorder(numCars, cars);if (result) {printf("Yes, it is possible to reorder the train cars.\n"); } else {printf("No, it is not possible to reorder the train cars.\n"); }return 0;}```输入示例：```Enter the number of train cars: 5Enter the train car numbers: 3 1 2 4 5```输出示例：```Yes, it is possible to reorder the train cars. ```。
计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级 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.如果输入的序列不是连续自然数。
数据结构车厢调度第一篇：数据结构车厢调度#include #include#define STACK_INIT_SIZE 20 #define STACK_SIZEtypedef struct { int *base;int *top;int stacksize;} SqStack;bool InitStack(SqStack &S){ // 初始化栈S.base =(int *)malloc(STACK_INIT_SIZE*sizeof(SqStack));if(!S.base) exit(0);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return true;} // InitStackbool GetT op(SqStack S, int &e){ // if(S.top == S.base)return false;e = *(S.topS.base >= S.stacksize){S.base =(int *)realloc(S.base,(S.stacksize + STACK_SIZE)*sizeof(SqStack));if(!S.base)exit(0);S.top = S.base + S.stacksize;S.stacksize += STACK_SIZE;} *S.top++ = e;return true;} // Pushbool Pop(SqStack &S, int &e){ if(S.top == S.base)return false;e = *--S.top;return true;}/////////////////////////////////////////////////////////////////// ////////////////bool Judement(int *Array, int n){ int Count = 0;for(int i = 1;i <= 2*n;i++)if(Array[i] == 1)Count++;if(Count == n && Array[2*n] == 0)一个是出栈return true;elsereturn false;}void operation(SqStack S, int n){ // n代表获得数量，分别标记为1,2,3....n int *Array;int nCount = 0, e;Array =(int *)malloc((2 * n + 1)* sizeof(int));if(!Array)exit(0);// 将其初始化为1234..n的形式for(int i = 1;i <= 2*n;i++)if(i%2 == 1)Array[i] = 1;elseArray[i] = 0;while(1){if(Judement(Array, n)){nCount = 0;for(int i = 1;i <= 2*n;i++){if(Array[i] == 1)Push(S, ++nCount);// 必须保证最后//从1开始// 代表入栈// 代表出栈else{Pop(S, e);printf(“%d ”, e);}}printf(“n”);}Array[2*n] += 1;// 最后一个自增1，等于2时本为为0前一位加1for(int i = 2*n;i >= 1;i--){if(Array[i] == 2){Array[i-1] += 1;Array[i] = 0;}}nCount = 0;for(int i = 1;i <= n;i++){if(Array[i] == 1)nCount++;}if(nCount == n && Array[2*n] == 1)break;// 退出循环的条件为前n个为1同时最后一位也为1 } }void main(){ // 这个是在左边有1,2,3...n节车厢的情况，得出在右边所有的情况SqStack S;InitStack(S);int n;scanf_s(“%d”, &n);if(n <= 1){printf(“输入数字小于1”);return;} operation(S, n);第二篇：数据结构任务调度实验报告实验报告实验名称：表达式求值任务调度实验类型：综合性实验班级：学号：姓名：实验日期：2014.5.28表达式求值 1.问题描述表达式是数据运算的基本形式。
北邮数据结构实验报告-排序北邮数据结构实验报告-排序一、实验目的本实验旨在掌握常见的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，并通过实际编程实现对数字序列的排序。
二、实验内容1.冒泡排序冒泡排序是一种简单的排序算法，其基本思想是依次比较相邻的两个元素，并按照从小到大或从大到小的顺序交换。
具体步骤如下：- 从待排序序列的第一个元素开始，依次比较相邻的两个元素；- 如果前面的元素大于后面的元素，则交换这两个元素的位置；- 重复上述步骤，直到整个序列有序。
2.插入排序插入排序是一种简单且直观的排序算法，其基本思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的合适位置。
具体步骤如下：- 从待排序序列中选择一个元素作为已排序部分的第一个元素；- 依次将未排序部分的元素插入到已排序部分的合适位置，使得已排序部分保持有序；- 重复上述步骤，直到整个序列有序。
3.选择排序选择排序是一种简单且直观的排序算法，其基本思想是每次选择未排序部分中的最小（或最大）元素，并将其放在已排序部分的末尾。
具体步骤如下：- 在未排序部分中选择最小（或最大）的元素；- 将选择的最小（或最大）元素与未排序部分的第一个元素交换位置；- 重复上述步骤，直到整个序列有序。
4.快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两部分，其中一部分的元素都比另一部分的元素小。
具体步骤如下：- 选择一个枢轴元素（一般选择第一个元素）；- 将待排序序列中小于枢轴元素的元素放在枢轴元素的左侧，大于枢轴元素的元素放在枢轴元素的右侧；- 对枢轴元素左右两侧的子序列分别进行递归快速排序；- 重复上述步骤，直到整个序列有序。
5.归并排序归并排序是一种高效的排序算法，其基本思想是将待排序序列划分成足够小的子序列，然后对这些子序列进行两两合并，最终形成有序的序列。
具体步骤如下：- 将待排序序列递归地划分成足够小的子序列；- 对每个子序列进行归并排序；- 合并相邻的子序列，直到整个序列有序。
北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。
本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。
二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。
具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。
三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。
通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。
2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。
通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。
3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。
通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。
4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。
通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。
四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。
在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。
2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。
在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。
3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。
在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。
目录一、功能描述 (2)1、输入火车厢信息 (2)2、入轨 (2)3、出轨 (2)4、退出 (2)二、总体概要设计 (2)1、系统设计框图: (2)2、系统设计流程图 (3)三、详细设计 (3)1 功能一：输入火车厢信息 (3)1）概要设计： (3)2）算法描述： (3)3)算法分析 (4)2 功能二：入轨 (4)1）概要设计： (4)2）算法描述： (4)3)算法分析： (7)3 功能三：出轨 (8)1）概要设计 (8)2）算法描述： (8)3）算法分析: (11)4 功能四：退出 (11)四、效果及存在问题 (11)1、效果显示: (11)1）输入火车厢信息 (12)2）入轨 (12)3）出轨： (12)4）显示重排完成车厢排列 (13)2、存在问题 (13)五、心得及体会 (14)六、参考文献 (14)七、评分表（见尾页）.............................. 错误！未定义书签。
附录：源代码. (14)一、功能描述1、输入火车厢信息设置欢迎界面，引导用户输入火车厢总长及原始火车厢排列，给系统提供必要数据信息。
2、入轨给出每节火车厢对应转入的缓冲铁轨提示，并显示所需缓冲铁轨数。
3、出轨给出每节火车厢出轨提示。
4、退出如果不需要操作就退出系统。
二、总体概要设计建立一个堆栈数组及栈顶指针数组，将所有的车厢都压入到堆栈（缓冲铁轨）中，入轨方法是使得每个堆栈里的元素从栈底到栈顶都是依次递减的，每次单节车厢出栈时，只要找到最小的栈顶元素令其依次出栈便可得到排好序的火车厢排列。
1、系统设计框图:2、系统设计流程图三、详细设计1 功能一：输入火车厢信息1）概要设计：通过printf语句设置欢迎界面及显示让用户输入火车厢总长及火车原始排列信息，并在屏幕上显示火车原始排列。
2）算法描述：流程图：在总流程图已经画出中，此处不再累述功能代码：int i,M,A[100],N=0;printf("\n\n");printf("************************************************************\n\n"); printf("===============您好,欢迎光临火车转轨系统！===============\n\n");printf("请输入您要进行转轨的火车车厢总长：");scanf("%d",&M);printf("\n请输入未转轨前车厢的排列顺序，请不要重复输入相同且不要遗漏输入车厢号\n\n");for(i=0;i<M;i++){scanf("%d",&A[i]);}printf("未转轨前的火车厢排列如下，请核对：\n");for(i=0;i<M;i++)printf("A[%d]=%d\n",i,A[i]);3)算法分析：此功能模块简单明了没有深度算法，在此不做分析。
