迷宫问题 火车车厢重排问题 实验报告
实验报告
实验名称：数据结构实验二
实验名称：栈和队列
时间：
班级：000 学号：000
姓名：神刀公子
一、问题描述
（1）迷宫问题
①问题描述
这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。
简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。
入口
出口
图1 迷宫示意图
迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。
②基本要求
●设计迷宫的存储结构。
●设计通路的存储结构。
●设计求解通路的算法。
●设计迷宫显示和通路的显示方式。
●输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。
●输出：迷宫、入口、出口及通路路径。
③思考
●若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北），
如何修改程序？
●如何求得所有通路？
●如何求得最短通路？
（2）火车车厢重排问题
①问题描述
一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为
了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和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;
else
return 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;
}
else
return 0;
（1）迷宫线路的判断和寻找方法
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, 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(!StackEmpty(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.y && maze[a][b]==0)
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=4;
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 4为走出迷宫\n通路为:(行坐标,列坐标,方向)\n");
while(S1)
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("——>(%d,%d,%d)",e.x,e.y,e.d);
}
return;
}
if(maze[a][b]==0)
{
maze[a][b]=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;
else{
cout<
p=p->next;}
}
（2）火车进入缓冲轨的判断
void PermuteTrans(int* arr,LinkQueue* a,int n,int k){
int i=0;
bool flag=true; ///设置标志，初始为真
while(i flag=false; ///改变标志 for(int j=0;j { 实验报告 实验课名称：数据结构实验二 实验名称：火车重排问题 班级：20130612 学号：13姓名：李寅龙时间：2014-5-18 一、问题描述 ①问题描述 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。 车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。 ②基本要求 ●设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨； ●设计并实现车厢重排算法； ●分析算法的时间性能。 二、数据结构设计 创建队列结构和相关操作函数 typedef struct { int *base; int front; int rear; }SqQueue; int InitQueue(SqQueue &Q){ Q.base=(int *)malloc(MAXSIZE*sizeof(int)); if(!Q.base) exit(-2); Q.front=Q.rear=0; return 1;} int DestroyQueue(SqQueue &Q){//销毁队列 free(Q.base); return 1;} int QueueEmpty(SqQueue Q){//判断队空 return (Q.front-Q.rear)%100==0 ? 1: 0;} int Getfront(SqQueue Q ,int &front){//读取队头元素 if(QueueEmpty(Q)) exit(0); front=Q.base[Q.front]; 计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-4-21 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（）试 验目的及要求（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。 成 绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告程序代码规范、功能正确 报告详实完整、体现收获 70分 备注： 评阅教师： 日期：年月日 出 轨 入 轨 581 H 1 H 3 H 2 963 742 出 轨 入 轨 58 H 1 H 3 H 2 96 7 4321 出 轨 入 轨 5 H 1 H 3 H 2 96 87 54321 出 轨 入 轨 H 1 H 3 H 2 987654321 (a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至 出轨 (c) 将8入缓冲轨，5移至出轨 (d) 将6789移至出轨 试 验 内 容 一、实验目的和要求 1、实验目的： （1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。 2、实验内容: 火车车厢重排问题。 转轨站示意图如下： 火车车厢重排算法伪代码如下： 出 轨 入 轨 581742963 987654321 H 1 H 3 H 2 1. 分别对k个队列初始化； 2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号； 3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢； 3.1.2 nowOut++； 3.2 否则，考察每一个缓冲轨队列 for (j=1; j<=k; j++) 3.2.1 取队列j 的队头元素c； 3.2.2 如果c=nowOut，则 3.2.2.1 将队列j 的队头元素出队并输出； 3.2.2.2 nowOut++； 3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j; 3.3.2 如果j 存在，则把入轨中的第一个车厢移至缓冲轨j； 3.3.2 如果j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个 空缓冲轨；否则车厢无法重排，算法结束； 3、实验要求： 使用顺序存储队列的方式完成该实验。 二、设计分析 根据实验要求，采用队列来完成本次实验。 实验中定义了三个队列，一个用来存储输入的车厢号，另两个用来存储缓存出队顺序及序号。 三、源程序代码 #include 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。 实验报告 实验名称：数据结构实验二 实验名称：栈和队列 时间： 班级：000 学号：000 姓名：神刀公子 一、问题描述 （1）迷宫问题 ①问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 ②基本要求 ●设计迷宫的存储结构。 ●设计通路的存储结构。 ●设计求解通路的算法。 ●设计迷宫显示和通路的显示方式。 ●输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。 ●输出：迷宫、入口、出口及通路路径。 ③思考 ●若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北）， 如何修改程序？ ●如何求得所有通路？ ●如何求得最短通路？ （2）火车车厢重排问题 ①问题描述 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为 了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。 车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和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; 实验报告 了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。 车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和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; else return 0; } int Push(PLStack &S, Element e) { PLStack p; p=(PLStack)malloc(sizeof(LStack)); p->elem=e; p->next=S; S=p; return 1; } 《算法与数据结构》实验指导书 实验课程类别：课程内实验 实验课程性质：必修 适用专业、年级：2012级计算机大类 开课院、系：计算机科学与工程学院 学时：18 编写依据：《算法与数据结构》实验教学大纲 修订时间：2014年2月 《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。 上机的工作环境要求：Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。 学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。 每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容： 1、学生基本情况：专业班级、学号、姓名 2、实验题目、实验内容 3、设计分析 4、源程序代码 5、测试用例（尽量覆盖所有分支） 6、实验总结 一．实验内容与学时分配 序次实验 题目 实验 类型 基本技能训练 学 时 一线性结构综合应用基础性（1）掌握线性结构的常用操作； （2）能够应用线性结构解决比较简单的问题。 10 二非线性结构综合应 用 设计性 （1）掌握树形、图形结构的插入、删除、查找等算法； （2）能够应用二叉树解决比较简单的问题。 4 三查找技术综合应用设计性（1）熟练掌握查找的常用算法； （2）设计和应用查找算法解决简单的实际问题。 2 四排序技术综合应用基础性（1）熟练掌握常用的排序方法，并掌握用高级语言实 现排序算法的方法； （2）深刻理解排序的定义和各种排序方法的特点，并 能加以灵活应用； （3）了解各种方法的排序过程及其依据的原则，并掌 握各种排序方法的时间复杂度的分析方法。 2 二．实验说明 实验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.2 2、问题分析 为了重排车厢，需从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求 火车车厢重排问题源程序代码 #include { QueuePtr p; if (Q.front == Q.rear) return 0; else { p=Q.front->next; Q.front->next=p->next; if(p->next==NULL) Q.front=Q.rear; int m=p->data; free(p); return m; } } int Getfront(LinkQueue &Q)//取队头元素 { if(Q.front==Q.rear) return 0; else return Q.front->next->data; } int Getrear(LinkQueue &Q)//取队尾元素 { if(Q.front==Q.rear) return 0; else return Q.rear->data; } int IsEmpty(LinkQueue &Q)//判断队列为空 { if (Q.front == Q.rear) return 0; return 1; } void Resort(LinkQueue &Q,LinkQueue *H,int k)//火车车厢重排{ 目录 一、功能描述 (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、系统设计框图: 火车车厢重排问题c++解决方法（队列实现） //Queue.h #ifndef QUEUE_H #define QUEUE_H #include public: LinkQueue(); ~LinkQueue(); void MakeEmpty(); void Enqueue(T x); T Dequeue(); bool IsEmpty()const; bool IsFull()const; T GetFirstItem(); T GetlastItem(); private: Node 数据结构实验报告 实验名称：实验二——车厢重排 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 （1）、实验目的： ①进一步掌握指针、模板类、异常处理的使用 ②掌握栈的操作的实现方法 ③掌握队列的操作的实现方法 ④学习使用栈解决实际问题的能力 ⑤学习使用队列解决实际问题的能力 （2）、实验内容： 一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。 2. 程序分析 2.1 存储结构 链队列: 2.2 关键算法分析 （1）、入队操作：（时间复杂度为O（1）） ①.建立新结点：rear->next=new Node ③.赋值：rear->data=x ④.将新结点的next指针域赋为空：rear->next=NULL 入队结构示意图如下： （2）、出队操作：（时间复杂度为O（1）） 算法伪代码如下： ①.保存队头元素指针：Node 实验一线性表 1 实验目的 通过选择下面四个题目之一进行实现，掌握如下内容： ?熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 ?学习指针、模板类、异常处理的使用 ?掌握线性表的操作的实现方法 ?学习使用线性表解决实际问题的能力 2 实验内容 2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、带头结点的单链表 2、不带头结点的单链表 3、循环链表 4、双链表 5、静态链表 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2.2题目2 利用线性表实现一个通讯录管理，通信录的数据格式如下： struct DataType { int ID; //编号 char name[10]; //姓名 char ch; //性别 char phone[13]; //电话 char addr[31]; //地址 }; 要求： ?实现通讯录的建立、增加、删除、修改、查询等功能 ?能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。 ?能够保存每次更新的数据（选作） ?能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作） ?编写测试main()函数测试线性表的正确性 2.3题目3 利用线性表实现一个一元多项式Polynomial f(x) = a + a1x + a2x2 + a3x3+ … + a n x n 提示： Polynomial的结点结构如下： struct term { float coef; //系数 int expn; //指数 }; 可以使用链表实现，也可以使用顺序表实现。 要求： ?能够实现一元多项式的输入和输出 ?能够进行一元多项式相加 ?能够进行一元多项式相减 ?能够计算一元多项式在x处的值 ?能够计算一元多项式的导数（选作） ?能够进行一元多项式相乘（选作） 本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 二、《数据结构课程设计》的要求 设计中要求综合运用所学知识，解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 三、《数据结构课程设计》的内容 分析：问题描述； 概要设计：数据结构的设计，算法的设计，抽象数据类型的设计； 详细设计：抽象数据类型对应的C++类定义，设计每个成员函数和主函数（流程图） 实现与测试： 编写课程设计报告： 四、《数据结构课程设计》时间和人员安排 15-16周组织进行汇报演示验收；4个人一组，每个人主要承担的任务 1. 停车场管理 [问题描述] 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 [基本要求] 按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，如汽车的输入数据格式为：（…A?，1，5），（…A?，2，10），（…D?，1，15），（…A?，3，20），（…A?，4，25），（…A?，5，30），（…D?，2，35），（…D?，4，40），（…E?，0，0），其中，…A?表示到达；…D?表示离去，…E?表示输入结束。 对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。 错位重排： 错位重排是指一种比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。 简介： 表述为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法？ 对这类问题有个固定的递推公式，记n封信的错位重排数为Dn，则D1=0，D2=1， Dn=（n-1）（Dn-2+Dn-1）此处n-2、n-1为下标。 n>2 我们只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。我们只需要记住结论，进行计算就可以。 【例】五个盒子都贴了标签，全部贴错的可能性有多少种？ 即全贴错标签，N个项数全部排错的可能数，可以总结出数列：0，1，2，9，44，265，……… 可以得到这样一个递推公式：（N-1）*（A+B）=C （A是第一项，B是第二项，C是第三项，N是项数） s(n)=(n-1) [ s（n-1）+s（n-2）] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 .................... 公式由来把编号1→n的小球放到编号1→n的盒子里，全错位排列（1号球不在1号盒，2号球不在2号盒，依次类推），共有几种情况？ ------------------------------------------------------ 设n个球全放错的情况有s(n)种，那么可以有如下思路： 不妨设1号球选择2号盒，接下来会有两种情况： 第一种情况：2号球选择1号盒，剩下（n-2）个球去错排，有s（n-2）种情况 第二种情况：2号球不选择1号盒，则题目可转化为把编号为2→n的小球分别放入编号为1、3、4……→n的盒子错位重排（即2号球不在1号盒、3号球不在3号盒…n号球不在n号盒），相当于n-1个球错位重排，有s(n-1)种 因为1号球可以放到[2,n]中任意一个盒子里，共（n-1）种选择，于是s(n)=(n-1) *[s(n-1)+s(n-2)] s(1)=0 s(2)=1 s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 .................... 【例题】四位厨师聚餐时各做了一道拿手菜。现在要求每人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法？ 学期论文2 专业：计算机科学与技术_______ 班级： U计算机111__________ 学号： 1111503111_________ _ 姓名：于秀芳_________ _ 指导教师：孟敏 ________ __ 完成日期： 2012年11月29日_____ _ 浅析队列、栈的应用 于秀芳 (盐城工学院优集学院江苏盐城 224051) 摘要：栈和队列是两种常用的数据结构，广泛应用在操作系统、编译程序等各种软件系统中。从数据结构角度看，栈和队列是操作受限的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；从抽象数据类型角度看，栈和队列又是两种重要的抽象数据类型。 关键词：栈和队列；数据结构；编译程序 Analysis Of The Queue, Stack Of Applications YuXiuFang (UGS College, Yancheng Institute of Technology, Yancheng, Jiangsu 224051) Abstract:Stacks and queues are two common data structure widely used operating systems, compilers and other software systems .From the perspective of data structure, stack and queue operation is constrained linear list, stack and queue data elements having a single precursor and successor linear relationship;From the perspective of abstract data types, stacks and queues are two kinds of important abstract data type. Key words: Stack and queue ;Data structure; Compiler program 0引言： 目前我们所学的数据结构包括上学期学过的C++都运用到了栈，队列。 1 栈的逻辑结构 1.1栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。 栈中元素除了具有线性关系外，还具有后进先出的特性。 1.2栈的顺序存储结构及实现 1.2.1栈的顺序存储结构 栈的顺序存储结构称为顺序栈。 顺序栈本质上是顺序表的简化，唯一需要确定的是用数组的那一端表示栈底。通常把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在元组中的位置。设存储栈元素的数组长度为StackSize，则栈空时栈顶指针 top=-1；栈满时栈顶指top=StackSize-1。入栈时，栈顶指针top加1；出栈时，栈顶指针top 减1。 1.2.2顺序栈的实现 （1）栈的初始化 初始化一个空栈只需将栈顶指针top置为1。 （2）入栈操作 Template 一、试验课题 队列的应用 实验目的： （1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。 二、试验内容 (1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。 (2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能 三、试验分析 实验说明： 转轨站示意图如下： 2 22 2(a) 将369、247依次入缓冲轨 (b) 将1移至出轨，234移至 出轨 (c) 将8入缓冲轨，5移至出轨 (d) 将6789移至出轨 火车车厢重排过程如下： 火车车厢重排算法伪代码如下： 四、源程序代码 #include 东华理工大学长江学院数据结构课程设计报告 学号： 09321110 姓名：刘曹杰 指导老师：刘自强 2011年1月3日 队列的应用举例——火车车厢重排一、实验分析 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 ~ n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站（目的地）的编号相同，使各车厢从前至后按编号1到n的次序排列，这样，在每个车站只需卸掉最后一节车厢即可。所以，给定任意次序的车厢，必须重新排列他们。可以通过转轨站完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，n节车厢从入轨进入转轨站，转轨结束时各车厢按照编号1至n的次序离开转轨站进入出轨。假定缓冲轨按先进先出的方式运作，因此可将它们视为队列，并且禁止将车厢从缓冲轨移至入轨，也禁止从出轨移至缓冲轨。图中给出了一个转轨站，其中有3个缓冲轨H1，H2和H3。 为了重排车厢，若有k个缓冲轨，缓冲轨H k为可直接将车厢从入轨移动到出轨的通道，则可用来暂存车厢的缓冲轨的数目为k-1。假定重排9节车厢，其初始次序为5, 8, 1, 7, 4, 2, 9, 6, 3，同时令k=3，如图3-23所示。3号车厢不能直接移动到出轨，因为1号车厢和2号车厢必须排在3号车厢之前，因此，把3号车厢移动至H1。6号车厢可放在H1中3号车厢之后，因为6号车厢将在3号车厢之后输出。9号车厢可以继续放在H1中6号车厢之后，而接下来的2号车厢不能放在9号车厢之后，因为2号车厢必须在9号车厢之前输出。因此，应把2号车厢放在H2的队头。4号车厢可以放在H2中2号车厢之后，7号车厢可以继续放在4号车厢之后。如图3-24(a)所示。至此，1号车厢可通过H3直接移至出轨，然后从H2移动2号车厢至出轨，从H1移动3号车厢至出轨，从H2移动4号 实验报告 1．实验要求 利用队列结构实现车厢重排问题。车厢重排问题如下： 一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，的车厢编号。 提示： 一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。 2. 程序分析 2.1 存储结构 本程序采用单链表结构，具体为链队列结构，使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下： 2.2 关键算法分析 一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下： void TrainPermute(): 1. 初始化条件:计数器i=0,与非门aa=1 2. 判断是否能入轨while(用i火车重排问题
火车车厢重排问题,队列,c语言
火车调度问题PROJECT
迷宫问题 火车车厢重排问题 实验报告
迷宫问题 火车车厢重排问题 实验报告材料
2012级算法与数据结构实验指导书18
实验2用堆栈解决火车车厢重排问题的编程
火车车厢重排问题
数据结构之火车厢重排
火车车厢重排 问题解决 c++(队列方法)
北京邮电大学数据结构第二次实验车厢重排实验报告
数据结构实验题目
数据结构课程设计题
错位重排公式推导
浅析队列、栈的应用
队列的应用火车车厢重排问题
火车车厢重排实验报告
车厢重排问题实验报告
相关文档
- 火车车厢重排 问题解决 c++(队列方法)
- 迷宫问题 火车车厢重排问题 实验报告
- C++火车车厢重排问题
- 基于Asp .net、XML与Flash架构的火车车厢重排问题虚拟实验开发
- 火车车厢重排问题
- 数据结构实验题目
- c++队列实现数据结构火车车厢重排
- 北邮数据结构实验题目
- 火车车厢重排问题,队列,c语言
- 数据结构之火车厢重排
- 数据结构课程设计题
- 队列的应用火车车厢重排问题
- 火车重排问题
- 迷宫问题 火车车厢重排问题 实验报告材料
- 堆与栈
- 2012级算法与数据结构实验指导书18
- 队列的应用火车车厢重排问题
- 火车车厢重排问题,队列,c语言
- 火车车厢重排问题,队列,c语言
- 北京邮电大学数据结构实验报告与源代码实验二火车车厢重排问题