C++用队列实现火车车厢重排问题
高手帮忙看下下面这段代码的错误，麻烦修改下，另外能不能帮我实现一下图形界面，要求实现单步演示，修改好麻烦发邮箱876223701@qq.com,分不是问题！
补充：#include<iostream>
using namespace std;
template<class T>
class Node{
friend: LinkedQueue<T>;
private:
T data;
Node<T>*link;
};
template<class T>
class LinkedQueue{
public:
LinkedQueue(){front=rear=0;}
~LinkedQueue()
{
Node<T>*nest;
while(front){
next=front->link;
delete front;
front=next;
}
}
bool IsEmpty() const
{return ((front)?false:true);}
bool IsFull()const;
T First()const;
T Last()const;
LinkedQueue<T>& Add(const& x)
{
Node<T>*p=new Node<T>;
p->data=x;
p->link=0;
if(front)rear->link=p;
else front =p;
rear=p;
return*this;
}
LinkedQueue<T>& Delete(T& x);
private:
Node<T>*front;
Node<T>*rear;
};
// template<class T>
// LinkedQueue<T>::~LinkedQueue()
template<class T>
bool LinkedQueue<T>::IsFull()const
{
Node<T>*p;
try{p=new Node<T>;
delete p;
return false;}
catch(NoMem){return true;}
}
template<class T>
T LinkedQueue<T>::First()const
{
if (IsEmpty())throw OutOfBounds();
return front->data;
}
template<class T>
T LinkedQueue<T>::Last()const
{
if (IsEmpty())throw OutOfBounds();
return rear->data;
}
// template<class T>
// LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
template<class T>
LinkedQueue<T>&LinkedQueue<T>::Delete(T& x)
{{
if(IsEmpty())throw OutOfBounds();
x=front->data;
Node<T>*p=front;
front=front->link;
delete p;
return *this;
}
bool Railroad(int p[],int n,int k-1)
{
LinkedQueue<int>*H;
H=new LinkedQueue<int> [k+1];
int NowOut=1;
int minH=n+1;
int minQ;
//车厢重排
for(int i=1;i<=n;i++)
if (p[i]==NowOut){
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[1],minH,minQ,H,k))
return false;}
return true;
}
void Output(int&minH,int&minQ,LinkedQueue<int>H[],int k,int n)
{//把车厢从缓冲轨送至出轨处，同时修改minS和minH
int c;//车厢索引
//从堆栈minS中删除编号最小的车厢minH
H[minQ].Delete(c);
cout<<"move car"<<minH<<"from holding track"<<minQ<<"to output"<<endl;
//
minH=n+2;
for (int i=1;i<=k;i++)
if(!H[i].IsEmpty()&&
(c=H[i].First())<minH){
minH=c;
minQ=i;}
}
bool Hold(int c,int&minH,int&minQ,LinkedQueue<int>H[],int k)
{
int BestTrack=0,
BestLast=0,
x;
for(int i=1;i<=k;i++)
if(!H[i].IsEmpty()){
x=H[i].Last();
if(c>x&&x>BestLast)
BestLast=x;
BestTrack=i;}
}
else
if(!BestTrack)return false;
H[BestTrack].Add(c);
cout<<"Move car"<<c<<"from input"<<"to holding track"<<BestTrack<<endl;
if (c<minH){minH=c;minQ=BestTrack;}
return true;
}
答案：#include<iostream.h>
const N=100;
template <class T>
struct Node
{
T data;
Node<T> *next; //此处<T>也可以省略
};
template <class T>
class LinkQueue
{
public:
LinkQueue( ); //构造函数，初始化一个空的链队列
~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间
void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队
T GetQueue( ); //取链队列的队头元素
bool Empty( ); //判断链队列是否为空
Node<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点
};
template <class T>
LinkQueue<T>::LinkQueue( )
{
Node <T> *s;
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
/*
* 前置条件：队列存在
* 输 入：无
* 功 能：销毁队列
* 输 出：无
* 后置条件：释放队列所占用的存储空间
*/
template <class T>
LinkQueue<T>::~LinkQueue( )
{
while(front)
{
Node <T> *p;
p=front->next;
delete front;
front=p;
}
}
/*
* 前置条件：队列已存在
* 输 入：元素值s
* 功 能：在队尾插入一个元素
* 输 出：无
* 后置条件：如果插入成功，队尾增加了一个元素
*/
template <class T>
void LinkQueue<T>::EnQueue(T x)
{
Node<T> *s;
s=new Node<T>;
s->data=x; //申请一个数据域为x的结点s
s->next=NULL;
rear->next=s; //将结点s插入到队尾
rear=s;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：删除队头元素
* 输 出：如果删除成功，返回被删元素值，否则，抛出删除异常
* 后置条件：如果删除成功，队头减少了一个元素
*/
template <class T>
T LinkQueue<T>::DeQueue()
{
Node <T> *p; int x;
if (rear==front) throw "下溢";
p=front->next;
x=p->data; //暂存队头元素
front->next=p->next; //将队头元素所在结点摘链
if (p->next==NULL) rear=front; //判断出队前队列长度是否为1
delete p;
return x;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：读取队头元素
* 输 出：若队列不空，返回队头元素
* 后置条件：队列不变
*/
template <class T>
T LinkQueue<T>::GetQueue()
{
if (front!=rear)
return front->next->data;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：判断队列是否为空
* 输 出：如果队列为空，返回1，否则，返回0
* 后置条件：队列不变
*/
template <class T>
bool LinkQueue<T>::Empty( )
{
if(front==rear)
return 1;
else
return 0;
}
void Output(int& minH, int& minQ, LinkQueue<int> H[], int k, int n)
{ //从缓冲铁轨移动到出轨，并修改minH 和m i n Q .
int c; // 车厢编号
// 从队列minQ 中删除编号最小的车厢minH
H[minQ].DeQueue( ) ;
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].Empty() &&(c = H[i].front->next->data) < minH)
{
minH = c;
minQ = i;
}
}
bool Hold(int c, int& minH, int &minQ, LinkQueue<int> H[], int k)
{ //把车厢c 移动到缓冲铁轨中
// 如果没有可用的缓冲铁轨，则返回f a l s e，否则返回t r u e
// 为车厢c 寻找最优的缓冲铁轨
// 初始化
int BestTrack = 0, // 目前最优的铁轨
BestLast = 0, // BestTrack 中最后一节车厢
x; // 车厢编号
// 扫描缓冲铁轨
for (int i = 1; i <= k; i++)
if (!H[i].Empty())
{// 铁轨i 不为空
x = H[i].rear->data;
if (c > x && x > BestLast)
{ // 铁轨i 尾部的车厢编号较大
BestLast = x;
BestTrack = i;
}
}
else // 铁轨i 为空
if (!BestTrack) BestTrack = i;
if (!BestTrack) return false; // 没有可用的铁轨
// 把c 移动到最优铁轨
H [BestTrack ] . EnQueue ( c ) ;
cout << "Move car " << c << " from input " << "to holding track " << BestTrack << endl;
// 如果有必要，则修改m i n H和m i n Q
if (c < minH)
{
minH = c; minQ = BestTrack ;
}
return true;
}
bool Railroad(int p[], int n, int k)
{// k 个缓冲铁轨，车厢初始排序为p [ 1 : n ]
// 如果重排成功，返回t r u e，否则返回false
// 如果内存不足，则引发异常NoMem 。
//创建与缓冲铁轨对应的堆栈
LinkQueue<int> *H;
H = new LinkQueue<int> [k + 1];
int NowOut = 1; //下一次要输出的车厢
int minH = n+1; //缓冲铁轨中编号最小的车厢
int minS; //minH号车厢对应的缓冲铁轨
//车厢重排
for (int i = 0; i < n; i++)
if (p[i] == NowOut)
{// 直接输出t
cout << "Move car " << p[i] << " from input to output" << endl;
NowOut++ ;
//从缓冲铁轨中输出
while (minH == NowOut)
{
Output(minH, minS, H, k, n);
NowOut++ ;
}
}
else {// 将p[i] 送入某个缓冲铁轨
if (!Hold(p[i], minH, minS, H, k))
return false;
}
return true;
}
void main()
{
//int p[9]={3,6,9,2,4,7,1,8,5},i=9,j=3;
int p[N],i,j;
cout<<"火车总数i和缓冲轨数j"<<endl;
cin>>i>>j;
cout<<"输入火车进轨的顺序"<<endl;
for(int k=0;k<i;k++)
cin>>p[k];
Railroad(p,i,j);
}
#include<iostream>
const N=100;
template <class T>
struct Node
{
T data;
Node *next;
};
<
上一个：怎样用C++实现文件另存为功能
下一个：帮忙修改一个c++程序，调试总是出错。
