笔试题
一列货运列车共有9节车厢，每节车厢将停放在不同的车站。假定 9个车站的编号分别为1 ~9，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号 1到9的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和 3个缓冲铁轨（位于入轨和出轨之间）,编写程序实现整个车箱重排方案
_________________ _________________
5 8 1 7 4 2 9 6 3 9 8 7 6 5 4 3 2 1
----------------- -----------------
|-| |-| |-|
|-| |-| |-|
a b c
[解决办法]
//用栈，链表，队列都可以做，队列方法如下，两个文件
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <deque>
#include <list>
#include <exception>
template <typename T>
class Queue
{
protected:
//std::deque <T> c;
std::list <T> c;
public:
class ReadEmptyQueue:public std::exception
{
public:
virtual const char* what() const throw()
{
return "read empty queue ";
}
};
typename std::deque <T> ::size_type size() const
{
return c.size();
}
bool empty() const
{
return c.empty();
}
void push(const T & elem)
{
c.push_back(elem);
}
T pop()
{
if(c.empty())
throw ReadEmptyQueue();
T elem(c.front());
c.pop_front();
return elem;
}
T & front()
{
if(c.empty())
throw ReadEmptyQueue();
return c.front();
}
};
#endif
/*=========================================================
********************队列车厢重排＊*************************
=========================================================*/
#include <iostream>
#include "queue.h "
using namespace std;
//--------------------------
bool Railroad(int p[],int n,int k)
{// k 个缓冲铁轨，车厢初始排序为p[1:n]
// 如果重排成功，返回true，否则返回false
// 如果内存不足，则引发异常NoMem 。
//创建与缓冲铁轨对应的堆栈
Queue <int> *H;
H=new Queue <int> [k+1];
int NowOut=1; //下一次要输出的车厢
int minH=n+1; //缓冲铁轨中编号最小的车厢
int minQ; //minH号车厢对应的缓冲铁轨
//车厢重排
for(int i=1;i <=n;i++)
if(p[i]== NowOut)
{// 直接输出t
cout < < "Move car " < <p[i] < < " from input to output " < <endl;
NowOut++;
//从缓冲铁轨中输出
while(minH==NowOut)
{
Output(minH, minQ, H, k, n);
NowOut++;
}
}
else
{
// 将p[i] 送入某个缓冲铁轨
if (!Hold(p[i], minH, minQ, H, k))
return false;
}
return true;
}
//---------------------
void Output(int& minH, int& minQ, LinkedQueue <int> H[], int k, int n)
{
//从缓冲铁轨移动到出轨，并修改minH 和minQ .
int c; // 车厢编号
// 从队列minQ 中删除编号最小的车厢minH
H[minQ].Delete(c);
cout < < "Move car " < <minH < < " from holding track " < <minQ < < " to output " < < endl;
// 通过检查所有队列的首部，寻找新的m i n H和m i n Q
minH = n + 2;
for (int i = 1; i <= k; i++)
if (!H[i].IsEmpty() &&
(c = H[i].First()) < minH) {
minH = c;
minQ = i;}
}
//----------------------------
void main()
{
try
{
Queue <int> q;
q.push(3);
q.push(8);
q.push(11);
cout < <q.pop() < <endl;
cout < <q.pop() < <endl;
}
catch(const exception& e)
{
cerr < < "EXCEPTION: " < <e.what() < <endl;
}
}
[解决办法]
一楼的算法不对，要是输入队列是“198765432”怎么办？我拿你的程序试了一下。会发生错误哦呵呵
