数据结构实验报告
实验名称：实验二——车厢重排
学生姓名：
班级：
班内序号：
学号：
日期：
1．实验要求
（1）、实验目的：
①进一步掌握指针、模板类、异常处理的使用
②掌握栈的操作的实现方法
③掌握队列的操作的实现方法
④学习使用栈解决实际问题的能力
⑤学习使用队列解决实际问题的能力
（2）、实验内容：
一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。
给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。
转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。
开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。
缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。
2. 程序分析
2.1 存储结构
链队列:
2.2 关键算法分析
（1）、入队操作：（时间复杂度为O（1））
①.建立新结点：rear->next=new Node<T>
②.移动队尾指针：rear=rear->next
③.赋值：rear->data=x
④.将新结点的next指针域赋为空：rear->next=NULL
入队结构示意图如下：
（2）、出队操作：（时间复杂度为O（1））
算法伪代码如下：
①.保存队头元素指针：Node<T>*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<int> *rail;
rail=new LinkQueue<int>[k+2]
2.将n节乱序的车厢放进入轨：cin>>arr[j];
rail[k].EnQueue(arr[j])
3. 将入轨中的车厢放进缓冲轨中，设置一个变量判断车厢是否成功放进缓冲轨：
while((i<n)&&success!=0)
3.1如果队列不为空而且该队列的队尾元素小于入轨中的头元素，则头元素
入轨，并且跳出for循环：rail[j].EnQueue(num);
success=1;
i++;
break;
3.2否则，如果队列为空，则入队：if(!rail[j].Empty())
rail[j].EnQueue(num);
success=1;
i++;
break;
3.3如果两种情况都不满足的话，则跳出while循环：success=0
4.如果车厢没有全部放进缓冲轨，则输出“缓冲轨不足，无法进行后续排序！”。
5.否则的话，可以进行排序：
5.1若此时要输出的车厢号小于等于总的车厢数，则进行出轨操作
5.1.1依次获取缓冲轨的头元素，如果与此时要输出的车厢号相同，则将其出队，并且放进出轨中，并且跳出for循环：if(rail[j].GetFront()==order)
{ ReNum=rail[j].DeQueue();
rail[k+1].EnQueue(ReNum);
order++;
break; }
6. 输出排序后的车厢顺序：cout<<rail[k+1].DeQueue()
（6）、主函数：直接调用重排函数：ReArrangement();
2.3 其他
将入轨中的元素放入缓冲轨中，如果有入轨中的元素无法放进缓冲轨，则说明缓冲轨不够，无法进行排序。
若车厢全部放入了缓冲轨，则能按顺序将车厢放入出轨中，排序完成。
3. 程序运行结果
1.测试主函数流程图：
2.测试条件：输入的车厢数n,缓冲轨数k均应该是整数，且车厢标号为从1到n。
3.测试结论：如果未输入n节车厢，则抛出错误。
如果缓冲轨数不够，则输出无法排序；如果入轨中的车厢均进入缓冲轨，则输出各车厢进入的缓冲轨的顺序与进入的缓冲轨，最后输出排序后的车厢顺序。
4.总结
1.调试时出现的问题及解决方法：
但我在调试程序的时候发相，如果输入的车厢数小于n值时，直接按Ctrl+Z结束输入，则由于开始给每个车厢都赋值为0，造成后面的车厢编号相同，无法进行正常的排序。
因此，我在车厢入轨后加入了一个异常处理，判断是否给每一个车厢都进行了赋值。
若已赋值，则进行下面的过程。
若未赋值则直接输出程序无法进行。
2.心得体会：
通过这个实验，我熟悉了队列的使用方法。
进一步加深了对于出入队的理解。
同时我也意识到，在一个程序基本功能实现之后，其实还有许多我们未曾想到的BUG。
当我们按我们所设计的方式操作时，这些BUG好像并没有什么影响。
但一旦我们错误操作，这些BUG就会使我们的程序崩掉。
所以写程序时要特别注意异常处理。
3.下一步的改进：
我了解到，车厢重排问题其实也可以用递归方法写，这样的代码会更为简单。
这次我设计的程序还应该多增加一些创新点，如如何重排任意序号的车厢，而非由1~n的车厢。
这些都是下一步改进的方向。