题目详情
假设火车调度站（如图1.1所示）入口处有n节硬席或软席车厢（分别用H、S表示）等待调度，请写一个算法，实现对这n节车厢的调度，使所有的软席车厢都被调整到硬席车厢之前。（可以调用图1.2的基本操作）
图1.1-用铁路调度站表示栈
图1.2-栈的基本操作
void Train_arrange ( char * train )
{ p=train ; q=train ;
InitStack(s);
while ( *p )
{ if (*p==‘H’)
else //把'S'调到前部
p++;
}
while(!StackEmpty(s))
{
}
}
实现
思想
将所有H车厢先放入容器中等待，迭代到S车厢时，将其车厢放到开头。
算法实现思路
创建两个指针P、q，初始化执行当前第一个车厢。循环迭代P指针，当迭代到S车厢时，将其车厢放到开头，即当前q指针所在位置，随后q指针向后移，否则迭代到H车厢时，将H车厢先放入栈中中等待。最后p指针指向null地址时结束循环，此时q执行最后一个S车厢的后面的车厢。那么我们就可以从栈中取出所有H车厢放入q指针所指位置，随后q向后移动。最终即可做到使所有的软席车厢都被调整到硬席车厢之前。
题目难点
笔者认为此算法并不算太难，主要难在题目要求一空一行代码，再加上笔者对C++不熟，一时半会想不出。
代码
// 栈-火车站调度.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<stack>
using namespace std;
void Pop(stack<char> &s, char& e)
{
e = s.top();
/*std::cout << s.top() << std::endl;*/
s.pop();
}
void Push(stack<char> &s, char e)
{
s.push(e);
}
void Train_arrange(char* train)
{
char* p = train; char* q = train;
stack<char> s;
while (*p)
{
if (*p == 'H') { Push(s, *p); }
else { *q++ = *p; } //把'S'调到前部
p++;
}
std::cout << train << std::endl;
std::cout << train << std::endl;
while (!s.empty())
{
Pop(s, *q);
++q;
}
}
int main()
{
char train[]= "HHSSHSHS";
Train_arrange(train);
std::cout << train << std::endl;
return 0;
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
// 入门使用技巧:
// 1. 使用解决方案资源管理器窗口添加/管理文件
// 2. 使用团队资源管理器窗口连接到源代码管理
// 3. 使用输出窗口查看生成输出和其他消息
// 4. 使用错误列表窗口查看错误
// 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
// 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
