2015-05-27
1532
Отчёт по лабораторной работе
Задание на ЛР.
Описать класс, реализующий стек.
Написать программу, использующую этот класс для моделирования Т-образного сортировочного узла на железной дороге. Программа должна разделять на два направления состав, состоящий из вагонов двух типов (на каждое направление формируется состав из вагонов одного типа). Предусмотреть возможность формирования состава из файла.
Описание основных структур данных и алгоритмов, используемых в работе
Стэк – линейный список, данные в котором обрабатываются согласно дисциплине LIFO.
Определяется класс Stack, позволяющий выполнять следующие операции:
- создать пустой стэк;
- добавить элемент в вершину стэка (заталкивание (push) элемента);
- удалить элемент из вершины стэка (выталкивание (pop) элемента);
- проверка, пуст ли стэк (isEmpty);
- проверка, полон ли стэк (isFull);
Для хранения элементов стека используется массив (последовательный способ хранения).
При тестировании в качестве типа, определяющего категорию вагона, используются char-значения R, G.
|
|
|
В функции main определяются два стэка R и G, моделирующих R и G составы соответственно.
Данные вводятся с клавиатуры (RG-последовательность символов) и входная строка разбиваеься на две строки (R и G, моделирующих R и G составы соответственно).
Описание интерфейса пользователя программы
После запуска программы, на экран отображается подсказка с просьбой ввести RG-последовательность символов.
Enter RG-sequence:
После ввода RG-строки, программа выполняет расчет и выводит на экран следующую информацию:
1. R-строку, моделирующую R состав.
1. G-строку, моделирующую G состав.
Контрольный пример и результаты тестирования
Enter RG-sequence: RGRRGGGRRRGGRGGG
R – stack
RRRRRRR
G - stack
GGGGGGGGG
Листинг программы
#include <iostream>
#include <cctype>
using namespace std;
typedef char Item;
class Stack
{
private:
enum {MAX = 20}; // Вместимость стэка
Item items[MAX]; // Массив, для хранения элементов стэка
int top; // Текущее количество элементов стэка
// (индекс первого свободного элемента в массиве)
public:
Stack(): top(0) {}
bool isEmpty() const { return top == 0; } // Возвращает true, если стэк пуст,
// false - в противном случае
bool isFull() const { return top == MAX; } // Возвращает true, если стэк
// полон, false - в противном
// случае
bool push(const Item & item); // Добавляет элемент в стек.
// Возвращает false, если стэк полон,
// true - в противном случае
bool pop(Item & item); // Выталкивает элемент с вершины стэка.
// Возвращает false, если стэк пуст,
// true - в противном случае
};
int _tmain()
{
Stack R, G;
char ch;
cout << "Enter RG-sequence: ";
while ((ch = cin.get())!= '\n')
{
if (ch == 'R') R.push(ch);
else G.push(ch);
}
cout << endl << "R - stack" << endl;
while (!R.isEmpty())
{
|
|
|
R.pop(ch);
cout << ch;
}
cout << endl;
cout << endl << "G - stack" << endl;
while (!G.isEmpty())
{
G.pop(ch);
cout << ch;
}
cout << endl;
return 0;
}
bool Stack::push(const Item & item)
{
if (!isFull())
{
items[top++] = item;
return true;
}
return false;
}
bool Stack::pop(Item & item)
{
if (!isEmpty())
{
item = items[--top];
return true;
}
return false;
}
