Меотдические указания
для практических занятий
по курсу:
Разработка ПО САПР
на тему:
Сортировка потока данных
с использованием 2-х стеков.
1. Постановка задачи.
Lstack_top <= Hstack_top
По договоренности новые символы входного потока должны принимать стек Lstack. Для сохранения отношения порядка внутри стеков и между вершинами стеков при поступлении нового символа в стек Lstack, нужно чтобы код принятого символа S был в диапазоне между кодами вершин стеков:
Lstack_top <= S <= Hstack_top
Выполнение этого неравенства можно обеспечить соответствующей перекачкой данных между стеками при поступлении очередного символа из входного потока:
Lstack --> Hstack
<--
Когда входной поток будет исчерпан, нужно передать все данные из стека Lstack в стек Hstack:
Lstack --> Hstack.
где они автоматически будут расположены в порядке убывания их величин. Последовательное выталкивание данных из стека Hstack образует выходной поток, где символы располагаются в порядке возрастания их кодов ASCII:
Hstack --> stdout.
m (109) , d (100) , x
(120) , f (102) , b (98) , p (112), где в скобках указаны десятичные коды
символов.
|
Hstack: 255 |
Hstack:: 255 |
|
Hstack:: 255, 109 |
Hstack:: 255 |
|
5. Состояние после ввода f (102):
Lstack: 0, 100, 102 Hstack:: 255, 120, 109 |
6. Состояние после ввода b (98):
Lstack: : 0.98 Hstack:: 255, 120, 109, 102, 100 |
|
7. Состояние после ввода p (112):
Lstack:0, 98, 100, 102, 109, 112 Hstack: 255, 120 |
Hstack::255, 120, 112, 109, 102, 100, 98 |
Печать стека Hstack образует выходную последовательность
b (98), d (100), f (102), m (109), p (112), x (120),
где символы упорядочены по возрастанию их кодов ASCII (т. е. по алфавиту).
Class Stack
class Lstack : Stack class Hstack : Stack
class Dstack : Lstack, Hstack
Базовый класс Stack должен включать классические стековые компоненты. Он должен иметь следующие защищенные (protected) компоненты- данные:
буфер стека stbuf - массив символов, объемом BUFSIZ;
целочисленный указатель стека sp;
и общедоступные (public) методы:
функция char pop( ) - извлекает символ из вершины стека;
функция void push (char) - размещает символ в вершине стека;
функция char top ( ) - возвращает код символа в вершине стека.
Класс Stack должен иметь конструктор, который инициализирует вершину пустого стека заданным символом:
Stack:: Stack (char s) {....}
Классы Lstack и Hstack - идентичные производные копии базового класса Stack. Они могут быть декларированы следующим образом:
class Lstack : public Stack {....};
и class Hstack : public Stack {....};
Их конструкторы должны вызывать конструктор базового класса Stack, с параметром, инициализирующим вершину пустого стека символом с минимальным (low):
Lstack :: Lstack (char low) : Stack (low) { }
и максимальным (high):
Hstack :: Hstack (char high) : Stack (high) { }
кодом соответственно.
Класс Dstack образуется путем множественного наследования компонентов 2-х идентичных классов Lstack и Hstack. Его декларация имеет следующий вид:
class Dstack : public Lstack, public Hstack { };
В результате множественного наследования класс Dstack будет включать 2 копии базового класса Stack (Lstack и Hstack), компоненты которых имеют одинаковые имена. Чтобы разрешить неоднозначность вызова, необходимо в спецификации обращения к одноименным компонентам указывать имя соответствующего базового класса, например:
Lstack :: pop( ); // вытолкнуть символ из класса Lstack или
Hstack :: pop( ); // вытолкнуть символ из стека Hstack
Кроме унаследованных компонент классов Lstack и Hstack, класс Dstack должен иметь собственный общедоступный (public) метод:
void Dstack, ::swap (char S) {....}
Эта функция должна обеспечивать обмен данными между стеками Lstack и Hstack, который необходим для размещения очередного символа.
Конструктор класса Dstack должен иметь 2 параметра типа char, зачениями которых инициализируются вершины стеков Lstack и Hstack. Чтобы обеспечить такую инициализацию, конструктор класса Dstack обращается к конструкторам классов Lstack и Hstack:
Dstack :: Dstack (char low, char high) : Lstack (low) , Hstack (high) { }
Конструкторы классов Lstack и Hstack в свою очередь вызывают конструктор их базового класса Stack.
Составить программу стековой сортировки на базе контейнерного класса, который включает 2 компонентных класса Lstack и Hstack.
Составить программу сортировки потока данных на основе дека.
Литература и программирование микро-ЭВМ., кн.1, М., Мир, 1983
2. Собоцинский В. В.
Практический курс Турбо С++, М., Свет, 1993