Цель занятия:
Целью занятия является практическое изучение организации множественного наследования в системе программирования С++ на примере сортировки данных с помощью 2-х стеков.

Постановка задачи:
Разработать программу сортировки потока данных с использованием 2-х стеков. Программа должна использоваться как фильтр, который читает поток символов из стандартного ввода (stdin), сортирует принятые символы в порядке возрастания их кодов ASCII и направляет результат в поток стандартного вывода (stdout).

Принцип стековой сортировки.

Для сортировки входного потока символов используются два стека: Lstack и Hstack. Первоначально Lstack инициализируется символом с кодом 0, Hstack инициализируется символом с максимальным кодом 255. В процессе сортировки часть символов сохраняется в стеке Lstack, другая часть - в стеке Hstack. Стек Lstack предназначен для хранения данных в порядке возрастания их величин. В стеке Hstack символы хранятся в порядке убывания их кодов. При этом, код символа в вершине стека Lstack не должен превосходить по величине код символа в вершине стека Hstack:

Lstack_top <= Hstack_top

По договоренности новые символы входного потока должен принимать стек Lstack. Для сохранения отношения порядка внутри стеков и между вершинами стеков при поступлении нового символа в стек Lstack, нужно чтобы код принятого символа S был в диапазоне между кодами вершин стеков:

Lstack_top <= S <= Hstack_top

Выполнение этого неравенства можно обеспечить соответствующей перекачкой данных между стеками при поступлении очередного символа из входного потока:

Lstack --> Hstack 

Lstack<--Hstack

Когда входной поток будет исчерпан, нужно передать все данные из стека Lstack в стек Hstack:

Lstack --> Hstack.

где они автоматически будут расположены в порядке убывания их величин. Последовательное выталкивание данных из стека Hstack образует выходной поток, где символы располагаются в порядке возрастания их кодов ASCII:

Hstack --> stdout.

Пример 1

Рассмотренный алгоритм иллюстрирует состояние стеков Lstack и Hstack при обработке входной последовательности латинских букв:

m (109) , d (100) , x (120) , f (102) , b (98) , p (112), где в скобках указаны десятичные коды символов.
1. Начальное состояние:
Lstack: 0
Hstack: 255

2. Состояние после ввода m (109):
Lstack: 0, 109
Hstack:: 255
3. Состояние после ввода d (100):
Lstack: 0, 100
Hstack:: 255, 109

4. Состояние после ввода x (120):
Lstack: 0, 100, 109, 120
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

8. Состояние после завершения ввода:
Lstack:0
Hstack::255, 120, 112, 109, 102, 100, 98


Печать стека Hstack образует выходную последовательность

b (98), d (100), f (102), m (109), p (112), x (120),

где символы упорядочены по возрастанию их кодов ASCII (т. е. по алфавиту).

Структуры данных.

Для информационной поддержки алгоритма стековой сортировки необходимо построить 4 стековых класса: базовый класс Stack, производные от класса Stack классы Lstack и Hstack, класс двойной стек Dstack, производный от Lstack и Hstack. Иерархия наследования для этих классов имеет вид ациклического графа, изображенного на следующем рисунке.

Рис. 1.  

Базовый класс 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.

Контрольные задания.

1.Составить программу стековой сортировки потока символов в порядке убывания их кодов.

2.Составить программу стековой сортировки на базе контейнерного класса, который включает 2 компонентных класса Lstack и Hstack.

3.Составить программу сортировки потока данных на основе дека.

Дек - абстрактная структура данных, в которой разращен стековый доступ с обоих концов последовательности данных.

Литература.

1. Дж. Уокерли

Литература и программирование микро-ЭВМ., кн.1, М., Мир, 1983

2. Собоцинский В. В.

Практический курс Турбо С++, М., Свет, 1993