数据结构之火车厢重排

目录

一、功能描述 (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

{

scanf("%d",&A[i]);

}

printf("未转轨前的火车厢排列如下，请核对：\n");

for(i=0;i

printf("A[%d]=%d\n",i,A[i]);

3)算法分析：

此功能模块简单明了没有深度算法，在此不做分析。

2 功能二：入轨

1）概要设计：

通过比较栈顶元素的大小的方法使得每个缓冲铁轨中车厢的排序是依次递减排列。本自定义的函数实现过程中调用了将初始化一个堆栈函数及单个元素进栈函数，实现需要的时候重新初始化一个堆栈并找到合适的堆栈存放车厢号后就将车厢进栈的操作。

2）算法描述：

流程图:

:

代码:

void init(STLink top[],int m) /*初始化堆栈*/

{

top[m]=NULL;

}

火车重排问题

实验报告 实验课名称：数据结构实验二 实验名称：火车重排问题 班级：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];

火车车厢重排问题,队列,c语言

计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级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 #include #define Max 20 typedef struct { int data[Max]; int front,rear; }squeue; void initqueue(squeue *&q) { q=(squeue *)malloc(sizeof(squeue)); q->front=q->rear=0; }

火车调度问题PROJECT

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

《算法与数据结构》实验指导书 实验课程类别：课程内实验 实验课程性质：必修 适用专业、年级：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用堆栈解决火车车厢重排问题的编程

实验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、问题分析 为了重排车厢，需从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求

数据结构实验四题目一排序实验报告

数据结构实验报告 实验名称：实验四——排序 学生：XX 班级： 班序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构

存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆

火车车厢重排问题

火车车厢重排问题源程序代码 #include #include typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; // 头指针，若队列不空，指向队列头元素 QueuePtr rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 } LinkQueue; int InitQueue (LinkQueue &Q)// 构造一个空队列Q { Q.front = Q.rear = (QueuePtr) malloc (sizeof (QNode)); if (!Q.front) return 0; // 存储分配失败 Q.front->next=NULL; return 1; } int EnQueue (LinkQueue &Q, int e) // 插入元素e为Q的新的队尾元素{ QueuePtr p; p=(QueuePtr) malloc (sizeof (QNode)); if(!p) return 0; //队列满 p->data=e; p->next =NULL; Q.rear->next =p; Q.rear =p; return 1; } int DeQueue (LinkQueue &Q) // 若队列不空，则删除Q的队头元素，用e 返回其值，并返回1; 否则返回0

{ 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++(队列方法)

火车车厢重排问题c++解决方法（队列实现） //Queue.h #ifndef QUEUE_H #define QUEUE_H #include using namespace std; template class Queue { public: virtual void MakeEmpty()=0; virtual void Enqueue(T x)=0; virtual T Dequeue()=0; virtual bool IsEmpty()const=0; virtual bool IsFull()const=0; virtual T GetFirstItem()=0; }; class EmptyQueue { }; class FullQueue { }; #endif //LinkQueue.h //链表队列 #ifndef LINKQUEUE_H #define LINKQUEUE_H #include #include"Queue.h" using namespace std; template struct Node { T date; Node *next; }; template class LinkQueue:public Queue { template friend ostream & operator<<(ostream &s,const LinkQueue &lq);

public: LinkQueue(); ~LinkQueue(); void MakeEmpty(); void Enqueue(T x); T Dequeue(); bool IsEmpty()const; bool IsFull()const; T GetFirstItem(); T GetlastItem(); private: Node *front; Node *rear; }; template LinkQueue::LinkQueue() { front=new Node; front->next=NULL; rear=front; } template LinkQueue::~LinkQueue() { MakeEmpty(); delete front; } template void LinkQueue::Enqueue(T x) { Node *newnode; newnode=new Node; newnode->date=x; newnode->next=NULL; rear->next=newnode; rear=newnode; } template T LinkQueue::Dequeue() { if(IsEmpty()) throw EmptyQueue(); Node *p; p=front->next;

数据结构课程设计 火车订票系统

软件课程设计--C语言设计火车票订票系统之源代码(模拟数据库功 能)(需求分析+可行性分析) 设计题目:火车订票系统 小组成员: 指导教师: 完成时间: 一.需求设计: 1.每条线路所涉及的信息有：起点、终点、站名、车次、、票价、时间、座位号。 2.作为示意系统，全部数据可以只放在内存中。 3.系统能实现的功能和操作如下： ①.查询路线：根据旅客提出的终点站名输入下列信息：车次、车站名。 ②.承办订票业务：根据客户提出的要求查询该车次票额的情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新查询客户要求，若需要可登记排队候补。 ③.承办退票业务：根据客户提供的情况（车次、时间、座位号）为客户办理退票手续，然后查询该车次是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。 ④登记旅客情况：包括旅客姓名，性别，年龄，家庭住址，联系方式等。 ⑤统计功能：将每次车的订票，退票结果统计出来。 ⑥管理功能:列车管理员可以通过调用函数来查看车票极其用户情况. ⑦.查询功能:用户可以查询自己需要的车辆信息. 二．总体设计 1．程序流程图：

按2键 按3键 按4键 进入in函数 进入book函数 进入inquire函数 进入cancel函数 按5键 进入you函数 2．总体设计说明： ①.数据结构设计: 程序=数据结构+算法,一个好的程序必定有一个好的数据结构.本设计主要考虑车票信息和用户信息的数据结构. 车票信息采用半十字链表.横向链表中的每一个结点包含以下内容:车次,起始站,发车时间,指向下一个结点的指针,指向中途站的指针.纵向链表中每一个结点包含以下内容:从始发站开始的依次到站,票价,到达时间,是否已被购买标识,才用mark标识,当mark为1时车票已售出,当mark为0时车票还未售出.以及指向下一个结点的指针.纵向链表采用循环链表,尾指针指向首指针. 未购票用户信息使用队列来保存,因为考虑到用户会预订票,所以把用户以来订票的时间早晚排在队中.先来先买,后来后买.队列中的每个元素包含以下内容:用户姓名,身份证号码,想要购票的车次,起始站,要到的站,时间. 已经购票用户信息使用一个单链表来保存,链表中的没个结点包含以下内容:用户姓名,身份证号码,已购车票的车次,出发时间,到达时间. 车票信息链表示意图: 车次 起始站 发车时间 downn next

北京邮电大学数据结构第二次实验车厢重排实验报告

数据结构实验报告 实验名称：实验二——车厢重排 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 （1）、实验目的： ①进一步掌握指针、模板类、异常处理的使用 ②掌握栈的操作的实现方法 ③掌握队列的操作的实现方法 ④学习使用栈解决实际问题的能力 ⑤学习使用队列解决实际问题的能力 （2）、实验内容： 一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。 2. 程序分析 2.1 存储结构 链队列: 2.2 关键算法分析 （1）、入队操作：（时间复杂度为O（1）） ①.建立新结点：rear->next=new Node ②.移动队尾指针：rear=rear->next

③.赋值：rear->data=x ④.将新结点的next指针域赋为空：rear->next=NULL 入队结构示意图如下： （2）、出队操作：（时间复杂度为O（1）） 算法伪代码如下： ①.保存队头元素指针：Node*p=front->next； ②.如果为空队则抛出异常：if(!p)throw"下溢"; ③.原队头元素出列：front->next=p->next; ④.保存队头数据：T x=p->data; ⑤.释放原队头：delete p; ⑥.若队列变为空队，修改队尾指针：if(!(front->next))rear=front; ⑦.返回出队数据：return x; 出队结构示意图如下： （3）、查找队头元素：（时间复杂度为O（1）） 算法分析：1.如果是空队列，则抛出异常：if (!(front->next))throw"上溢"; 2. 否则返回队头元素：return front->next->data; （4）、查找队尾元素：（时间复杂度为O（1）） 算法分析：1.如果是空队列，返回0：if(rear==front) return 0; 2.否则返回队尾元素return rear->data; （5）、车厢重排函数：（时间复杂度为O（n）） 算法分析：1. 建立k+2个新队列：LinkQueue *rail; rail=new LinkQueue[k+2] 2.将n节乱序的车厢放进入轨：cin>>arr[j]; rail[k].EnQueue(arr[j]) 3. 将入轨中的车厢放进缓冲轨中，设置一个变量判断车厢是否成功放进缓冲轨： while((i

数据结构1-4章习题答案

第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题

数据结构实验题目

实验一线性表 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?表示输入结束。 对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。

浅析队列、栈的应用

学期论文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 Void SeqStack::Push(DataType x) {

队列的应用火车车厢重排问题

一、试验课题 队列的应用 实验目的： （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 using namespace std; const MS=100; template struct QNode { T data; QNode *next; }; template class LiQueue { public: LiQueue( ); //构造函数，初始化一个空的链队列 ~LiQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetFront( ); //取链队列的队头元素 T GetRear(); bool Empty( ); //判断链队列是否为空 QNode *front, *rear; //队头和队尾指针，分别指向头结点和终端结点}; template LiQueue::LiQueue( ) { QNode *s;s=new QNode;s->next=NULL;front=rear=s; } template LiQueue::~LiQueue( ) { QNode *p; while(front) { p=front;front=front->next;delete p; } } template