实验报告04

《算法与数据结构》实验报告(四)

专业班级 学生学号 学生姓名 实验项目 实验类别 2016级3E软件工程 1605121007 董婉清 队列的应用 基础性（√） 设计性（） 综合性（） 其它（ ） （1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。 实验地点 指导教师 实验时间 8号机房 姚峰 2018-05-18 实验目的及要求 成 绩 评 定 表 类 别 上机表现 评 分 标 准 积极出勤、遵守纪律 按要求完成设计任务 程序代码规范、功能正确 报告详实完整、体现收获 分值 30分 得分 70分 合 计 程序与报告 说明： 评阅教师： 姚峰 日 期： 20 年 月 日 计算机科学与工程学院

实 验 内 容 实验内容：火车车厢重排问题。 实验说明： 转轨站示意图如下： 581742963 入 轨 火车车厢重排过程如下： 963 H1 581 H3 出 轨 入 轨 742 H2 (a) 将369、247依次入缓冲轨 96 H1 5 54321 H3 出 轨 入 轨 87 H2 (c) 将8入缓冲轨，5移至出轨 火车车厢重排算法伪代码如下： 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.3如果j不存在,但有多余一个空缓冲轨,则把入轨中的第一个车厢移至一个空缓冲结束 《算法与数据结构》实验报告

H1 H3 H2 987654321 出 轨 96 H1 58 入 轨 H3 7 H2 4321 出 轨 (b) 将1移至出轨，234移至出轨 H1 入 轨 H3 H2 (d) 将6789移至出轨 987654321 出 轨 2

计算机科学与工程学院

#include #include using namespace std; struct Node { int data; Node *next; }; //LinkQueue.h class LinkQueue { private: Node *first,*rear; public: LinkQueue(); ~LinkQueue(); void EnQueue(int); int DeQueue(); int GetQueue_head(); int GetQueue_rear(); int Vide_Queue(); void Print_Queue(); }; //LinkQueue.cpp LinkQueue::LinkQueue()//无T惨¨°构1造¨¬函¡¥数ºy { Node *s=new Node; s->next=NULL; first=rear=s; } LinkQueue::~LinkQueue()//析?构1函¡¥数ºy释º¨ª放¤?空?间? { while(first) { Node *p; p=first->next; delete first; first=p; } } void LinkQueue::EnQueue(int x)//队¨®尾2入¨?队¨® { Node *s=new Node; 《算法与数据结构》实验报告

3

计算机科学与工程学院

s->data=x; s->next=NULL; rear->next=s; rear=s; } int LinkQueue::DeQueue()//队¨®头ª¡¤出?队¨® { int x; x=first->next->data; Node *p=first->next; first->next=p->next; if(p->next==NULL) rear=first; delete p; return x; } int LinkQueue::GetQueue_head()//取¨?得Ì?队¨®列¢D第̨²一°?个?元a素?的Ì?数ºy据Y { if(first!=rear) return (first->next->data); } int LinkQueue::GetQueue_rear()//取¨?得Ì?队¨®列¢D最Á?后¨®一°?个?元a素?的Ì?数ºy据Y { if(first!=rear) return (rear->data); } int LinkQueue::Vide_Queue()//判D断?队¨®列¢D是º?否¤?为a空?，ê?若¨?为a空?返¤¦Ì回?0，ê?若¨?不?为a空?返¤¦Ì回?1 { if(first==rear) return 0; else return 1; } void LinkQueue::Print_Queue()//输º?出?队¨®列¢D中D所¨´有®D元a素? { Node *p=first->next; while(p) { 《算法与数据结构》实验报告

4

计算机科学与工程学院

cout<data<<\" \"; p=p->next; } } const int k=3;//假¨´设¦¨¨有®D三¨y个?缓o冲?轨¨¬ int TrainMain() { LinkQueue Q[k];//k个?缓o冲?轨¨¬ LinkQueue A;//入¨?轨¨¬ LinkQueue C;//出?轨¨¬ cout<<\"请?输º?入¨?1~9:\"<>x; A.EnQueue(x);//入¨?队¨® } cout<<\"入¨?轨¨¬中D的Ì?车¦Ì厢¨¢序¨°列¢D如¨?下?:\"<5

计算机科学与工程学院

for(int i=0;i6

计算机科学与工程学院

Q[num].Print_Queue(); cout<7

计算机科学与工程学院

实 验 内 容 《算法与数据结构》实验报告

8

计算机科学与工程学院

实 验 总 结 本次试验较难，大量借鉴了网上的资源，感觉到算法很重要。

《算法与数据结构》实验报告 9