2020-01-14
132
• Назначение компонент стека тесно связано с особенностями реализа-
ции обслуживающих функций ("init()", "push()", "pop()" и др.).
• В обслуживающих функциях не предусмотрена обработка типичных
Ошибок: переполнение стека, попытка извлечения элемента из пусто-
Го стека, повторная инициализация стека, нет способа проверки со-
Стояния стека (поврежден/не поврежден).
• Присвоение структур (напр., "A=B") приводит к возникновению вися-
Чих указателей, т.к. присвоение компонент-массивов означает при-
Своение указателей, а не копирование отдельных элементов.
Перечисленные недостатки показаны во фрагменте программы 6.2.
void Stack_Print(Stack& A)
{
if (A.top = 0) // Ошибка: присваивание вместо сравнения
cout << "Стек пуст.\n";
Else
cout << "Стек не пуст.\n";
}
Void main()
{
Stack A;
double x;
Push(A, 3.141); // Стек A не был проинициализирован
110
init(A);
x = pop(A); // Ошибка: A в данный момент пуст,
// поэтому стек окажется в поврежденном
// состоянии, а значение x не определено
A.v[3] = 2.13; // Так помещать элементы в стек нельзя
|
|
|
A.top = -42; // Теперь стек окажется в логически
// некорректном состоянии
Stack C, D;
push(C, 0.9);
push(C, 6.1);
init(D);
D = C; // Такое присвоение допускается по
// правилам языка, но не обеспечивает
// копирования элементов стека
Init(C); // Эта инициализация очищает содержимое
// и C, и D, поскольку они обращаются
// к одному массиву
}
Фрагмент программы 6.2.
Реализация стека с использованием динамической памяти
Для реализации стека можно предложить структуру, позволяющую создать
Стек произвольного размера и работать с элементами стека через указатели. Далее
_______приведен один из вариантов этой структуры:
struct DStack {
double* bottom;
double* top;
Int size; // Это максимальный размер стека,
}; // а не количество элементов в нем
Массив для хранения элементов стека должен создаваться динамически на эта-
Пе инициализации. Два внутренних указателя стека ссылаются на начало массива
("bottom") и на элемент-верхушку стека ("top"). Устройство стека на базе динамиче-
Ского массива показана на рис. 3.
Рис. 3..Стек с хранением элементов в динамической памяти.
Для работы со стеком целесообразно сделать несколько обслуживающих функ-
ций:
1) Инициализация стека.
bool DStack_init(DStack& s, int N);
111
Эта функция динамически создает целочисленный массив размером N эле-
ментов и сохраняет его указатель в компонентах структуры "DStack". Если
операция инициализации прошла успешно, то функция возвращает "true",
а если памяти недостаточно – то "false".
2) Добавление элемента в стек.
bool DStack_push(DStack& s, double val);
Помещает элемент на верх стека. Возвращает "true", если это удалось сде-
|
|
|
лать, или "false", если стек целиком заполнен.
3) Извлечение верхнего элемента.
double DStack_pop(DStack& s);
Возвращает верхний элемент из стека или вохвращает 0.0 (или некоторое
Другое специально оговоренное значение), если стек пуст.
4) Проверка на пустоту.
bool DStack_empty(Dstack& s);
Возврашает "true", если стек пуст, или "false" в противном случае.
5) Удаление стека.
void DStack_free();
Освобождает динамическую память, занятую при создании стека.
По сравнению со стеком из п.6.1, в описанном варианте реализации достигает-
ся ряд улучшений:
Есть возможность создания стеков разного размера.
В обслуживающих функциях предусмотрена обработка элементарных оши-
Бок переполнения и обращения к пустому стеку.
3) Имена обслуживающих функций, начинающиеся с "DStack_", менее веро-
Ятно обнаружить в других библиотеках.
К сожалению, опасность несанкционированного изменения внутренних пере-
Менных стека сохраняется и в этой реализации.
Сводка результатов
Составной тип данных позволяет объединить под одним именем несколько пе-
ременных уже существующих типов. В Си++ для описания составного типа применя-
ется служебное слово "struct". Структуры могут быть вложенными. Для обращения
к компонентам структуры используются операции точка "." или "->" (если обраще-
Ние выполняется через указатель на структуру).
Внутрь функций структуры чаще передаются по ссылке. Если параметры-
Структуры внутри функции заведомо не изменяются, то такие параметры обычно опи-
Сываются как константные параметры.
Можно создавать и использовать массивы структур, или использовать массивы
В качестве компонент структур. Для более краткой и естественной записи выражений
Со структурами допускается перегрузка операторов.
В лекции рассмотрено два варианта реализации стека на базе статического мас-
Сива и с использованием динамической памяти. Явным недостатком обоих вариантов
Стека является открытость внутренних переменных структуры для логически некор-
Ректных изменений извне.
112
Упражнения
Упражнение 1
Напишите функцию для печати на экране содержимого стека, представленного
в виде структуры "Stack" из п. 6.1. Перегрузку операторов не используйте. Проверь-
Те работу функции с помощью подходящей тестовой программы.
Упражнение 2
Разработайте статический стек для хранения целых чисел и для хранения сим-
Вольных строк длиной до 100 символов. Для каждого из стеков сделайте отдельные
заголовочные файлы ("stack_int.h" и "stack_string.h") и файлы реализации
("stack_int.cpp" и "stack_string.cpp"). Проверьте работу стеков с помощью
Соответствующей тестовой программы.
Упражнение 3
Согласно описанию из п. 6.3 реализуйте стек с использованием динамической
памяти (примените операторы "new" и "delete").
Упражнение 4
Напишите функции для записи содержимого массива структур "Person"
(см. п.2) в файл, для чтения структур "Person" из файла и для печати этих структур
На экране. Для ввода/вывода из файла и для вывода на экран примените перегружен-
ные операторы ">>" и "<<".
113
ПРИЛОЖЕНИЕ. Краткое руководство по среде разработки
Developer Studio Visual C++
Microsoft Developer Studio – это интегрированная среда разработки программ,
