ций:
Complex u, v, w, z, t;
...
t = C_add( u, v );
w = C_mult( z, t );
Конечно, более естественной является запись:
Complex u, v, w, z;
...
w = z * ( u + v );
Тип "Complex" является типом, введенным пользователем, и, естественно, в
языке Си++ арифметические операторы для этого типа не определены. Поэтому для
естественной записи выражений с числами в виде структур "Complex" надо перегру-
зить операторы сложения и умножения:
Complex operator +( const Complex& x, const Complex& y )
{
Complex t;
t.re = x.re + y.re;
t.im = x.im + y.im;
return t;
}
Complex operator *( const Complex& x, const Complex& y )
{
Complex t;
t.re = x.re*y.re - x.im*y.im;
t.im = x.re*y.im + x.im*y.re;
return t;
}
Правила размещения перегруженных операторов в исходном тексте программ
аналогичны правилам размещения функций: прототипы отдельно, определения от-
дельно (возможно, прототипы операторов расположены в заголовочном файле, а оп-
ределения –в файле реализации).
Аналогично арифметическим операторам, в Си++ допускается перегружать
операторы потокового ввода/вывода ">>" и "<<". Например, вывести комплексное
число на экран можно так:
void main()
{
Complex u, v;
u.re = 2.1; u.im = 3.6;
v.re = 6.5; v.im = 7.8;
cout << "Числа равны (" << u.re << " + " << u.im << "i) и ";
cout << " (" << v.re << " + " << v.im << "i).\n";
}
107
В результате выполнения этой программы на экране будет напечатана строка:
Числа равны (2.1 + 3.6i) и (6.5 + 7.8i).
Для упрощения записи операции печати комплексного числа на экране можно
перегрузить оператор вывода в поток:
ostream& operator <<( ostream& s, const Complex& x )
{
s << "(" << x.re << " + " << x.im << "i)";
return s;
}
void main()
{
Complex u, v;
u.re = 2.1; u.im = 3.6;
v.re = 6.5; v.im = 7.8;
cout << "Числа равны " << u << " и " << v << ".\n";
}
В определении оператора фигурирует тип "ostream". Это класс "поток выво-
да", объектом которого является стандартный поток вывода на экран "cout". Для по-
токового ввода/вывода в файл необходимо перегружать операторы применительно к
классам "ofstream" и "ifstream" (см. 4-ю лекцию).
6. Применение структур для реализации стека
Абстрактный тип данных "стек" кратко рассматривался в 8-й лекции (компиля-
тор использует стек для организации вызовов функций). Стек встречается не только в
компиляторах, но и во многих численных алгоритмах. В данном параграфе рассмат-
риваются два варианта реализации стека на Си++ с помощью структур.
Среди значений английского слова "stack" есть значения "пачка" и "стопа". Аб-
страктный тип данных, соответствующий принципу "последним прибыл –первым
обслужен" получил свое название из-за своего сходства со стопкой тарелок (рис. 1).
Рис. 1..Поведение стека при записи и чтении элементов.
Основные свойства стека:
1) Элементы добавляются или удаляются только сверху стека.
2) Для добавления элемента применяется функция "push()".
3) Для удаления элемента применяется функция "pop()".
108
6.1 Реализация стека на основе статического массива
В качестве задачи поставим разработку стека для хранения вещественных чи-
сел. Свойства стека очень просты, поэтому для работы со стеком, например, из 20-ти
вещественных чисел достаточно несложно написать программу, похожую на про-
грамму 6.1.
#include <iostream.h>
struct Stack {
double v[20];
int top;
};
void push( Stack& s, double val )
{
s.v[s.top] = val;
s.top++;
}
double pop( Stack& s )
{
return s.v[--(s.top)];
}
void init( Stack& s )
{
s.top = 0;
}
bool full( Stack& s )
{
return s.top >= 20;
}
void main()
{
Stack s;
init( s ); // Инициализация стека
push( s, 2.31); // Помещение в стек первого элемента
push( s, 1.19 ); // Помещение в стек второго элемента
cout << pop( s ) << '\n'; // Извлечение верхнего элемента
// и вывод его на экран
push( s, 6.7 ); // Помещение в стек элемента
push( s, pop(s)+pop(s) ); // Замена двух верхних элементов
// стека их суммой
}
Программа 6.1.
В программе 6.1 стек реализован на базе статического массива, один из элемен-
тов которого играет роль верхушки стека. Индекс этого элемента хранится в компо-
ненте top. (рис. 2).
109
Рис. 2..Стек на основе массива с фиксацией верхушки стека. Серым цветом
обозначены помещенные в стек элементы.
6.2 Недостатки структуры данных Stack
Приведенному в п. 6.1 простейшему варианту реализации стека (в виде струк-
туры "Stack") присущи ряд недостатков, которые можно разбить на две группы:
1) Малая гибкость применения
•У стека ограниченный размер (20 элементов).
•В стеке могут храниться только значения типа double.
•Имена функций наподобие "full()" и "init()" очень распростра-
нены и может возникнуть конфликт этих имен с именами функций из
других библиотек.
2) Безопасность использования стека
•Внутренние переменные стека не защищены от изменений извне. По-
этому стек легко повредить путем изменения значений компонент
структуры. Это может привести к сложно обнаружимым ошибкам.
•Назначение компонент стека тесно связано с особенностями реализа-
ции обслуживающих функций ("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.
6.3 Реализация стека с использованием динамической памяти
Для реализации стека можно предложить структуру, позволяющую создать
стек произвольного размера и работать с элементами стека через указатели. Далее
_______приведен один из вариантов этой структуры:
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 );