Присваивание указателей друг другу 7 страница

};

// Функции работы со списком

struct TList *create_list(); // Создание

void delete_list(struct TList** list); // Удаление

// Функции работы с элементами списка

// Добавление

struct TItem *add_item(struct TList *list, int num);

// Исключение

int remove_item(struct TList *list);

struct TStack // Структура стека.

{

struct TList *top; // Указатель на вершину стека

};

// Функции работы со стеком

struct TStack *create_stackt(); // Создание

void delete_stack(struct TStack **stack); // Удаление

// Функции работы с элементами стека

void push(struct TStack *stack, int a); // Добавление

int pop(struct TStack *stack); // Исключение

Первый большой недостаток такой реализации стека – засорение пространства имен. Несмотря на то, что в остальной программе используется лишь стек, для того чтобы определить его, нам понадобилось создать большое количество вспомогательных функций. Это, в свою очередь, означает, что в остальной части программы будут доступны функции, в которых нам нет необходимости, а полезные имена будут заняты. Например, переменная top имеет вполне универсальное название, и вполне возможно, что программист захочет использовать ее где-то еще. Это усложнит понимание программы из-за придания переменной еще одного смысла и может привести к ошибке неправильного ее использования. Засорение пространства имен чревато также тем, что программисту все труднее становится ориентироваться в исходном коде и придумывать новые идентификаторы, а это может перерасти в серьезную проблему при разработке больших программ.

Вторым недостатком может стать то, что в любой точке программы можно получить доступ непосредственно к списку, на базе которого реализован стек, или даже к отдельным его элементам. Это, вероятнее всего, приведет к тому, что всякий раз, когда возникает необходимость сделать что-то нетривиальное, вместо создания новой функции интерфейса «стек – программа», программист будет напрямую управлять списком и его элементами. В результате, программа будет содержать большое количество различных функций, обращающихся непосредственно к реализации стека, и, если возникнет необходимость изменить ее, придется изменить всю программу.

Третий недостаток состоит в необходимости вызывать функции инициализации (конструкторы) каждый раз при начале работы со стеком, и не забывать вызывать функции уничтожения (деструкторы) в конце. Причем вызов конструкторов или деструкторов несколько раз подряд чреват непредсказуемым поведением программы.

13.2. Решение задачи средствами Си

Единственным средством, позволяющим хоть как-то решить первые две проблемы, является использование модульного программирования. Разобьем программу на две части: интерфейс и реализацию. Первая будет содержать те функции и структуры, которые необходимы для нормальной работы с объектом, вторая – все остальное. Вот как может выглядеть интерфейсная часть стека:

Пример 13.3. Интерфейсная часть стека.

struct TStack;

struct TStack *create_stackt();

void delete_stack(struct TStack **stack);

void push(struct TStack *stack, int a);

int pop(struct TStack *stack);

Эти четыре функции и структура позволяют полностью управлять стеком. Надо заметить, что программисту удобно не знать внутренних деталей реализации: если стек написан одним программистом, а используется другим, для работы достаточно документировать его интерфейс.

Чтобы окончательно скрыть реализацию, разобьём проект на файлы: выделим для реализации стека файл stack.c и перенесем туда определения всех функций из примера 13.2. Основной файл проекта, (содержащий функцию main()) назовем main.c. Теперь осталось лишь создать заголовочный файл, содержащий объявления функций из примера 13.3, и включить его в stack.c и main.c.

Сейчас можно говорить о том, что первый недостаток (в некоторой степени) устранен. Стек разбит на две части: интерфейс содержит все то, что объявлено в stack.h, реализация, все то, что определено в stack.c.

Второй недостаток, заключающийся в необходимости явно вызывать специальные функции инициализации и деинициализации стека решить средствами языка Си практически невозможно.

13.3. C++. Классы

Языки, поддерживающие концепцию объектно-ориентированного программирования (ООП) вводят средства, позволяющие решать вышеназванные проблемы. Одним из таких языков является C++. Основное средство, реализованное в C++ для поддержки парадигмы ООП – класс.

Далее, когда речь будет идти о концепции (описании, спецификации) стека, будем использовать термин класс, а для реального стека, занимающего место в динамической памяти, хранящего реальные элементы – термин объект класса. Опишем класс «стек чисел»:

Пример 13.4. Класс iStack

// Класс iStack (стек чисел_типа_int)

class iStack

{

public:

iStack(); // Конструктор

~iStack(); // Деструктор

void push(int a);

int pop();

private:

struct TList *top; // Указатель на вершину стека

};

В первых строках содержится заголовок класса, здесь указано, что определяемая структура – класс, а идентификатор, который станет именем нового типа, – iStack. Ключевое слово public говорит компилятору о том, что последующие объявления будут относиться к интерфейсной части класса. Далее идут объявления следующих функций: конструктор и деструктор, push() и pop(). Именно эти четыре функции были вынесены в интерфейсную часть стека (пример 13.3).

Ключевое слово private начинает область, члены объявленные в которой относятся к реализации класса и не должны быть доступны извне. К таким членам отнесена переменная-указатель на список: имей пользователь непосредственный доступ к ней, он получил бы возможность обращаться к любым членам списка (т.е. сортировать его, извлекать элементы из середины и т.д.), а это недопустимо для стека.

Здесь и далее, для простоты, подразумевается, что в точке объявления класса доступны определенные ранее «элемент списка» и «список». Преобразовав таким образом стек из примера 13.2, поместим код в один файл (например, stack.cpp) в таком порядке:

1. Подключение заголовочных файлов библиотек

2. Определение типов данных «элемент списка» и «список»

3. Определение функций работающих с элементами списка

4. Определение функций работающих со списком

5. Класс iStack

На следующем шаге необходимо определить функции, объявленные внутри класса. Этот код следует добавить в конец файла stack.cpp:

iStack::iStack() { top = create_list(); }

void iStack::~iStack() { delete_list(&top); }

void iStack::push(int a) { add_item(top, a); }

int iStack::pop() { return remove_item(top); }

В части кода, использующей объекты, изменились имена функций инициализации и деинициализации. Их пришлось переименовать так, чтобы компилятор мог определить, какая именно из функций объявленных в классе конструктор, а какая деструктор (для автоматического их вызова). В C++ конструктор и деструктор должны называться так же, как и класс, а деструктор, кроме того, должен иметь тильду “~” перед идентификатором (как в примере 13.3).

Кроме того, перед каждым именем функции обязательно ставить имя класса и оператор разрешения области видимости “::”. Таким образом, функция, ранее объявленная, как int pop(), теперь будет объявлена так: int iStack::pop(), и т.д.

Работать со стеком теперь тоже надо по-другому. Для того чтобы создать стек не надо явно вызывать некоторую функцию – достаточно лишь объявить переменную типа iStack (т.е. создать объект класса iStack). В момент, когда в своем выполнении дойдет до оператора объявления конструктор будет вызван автоматически. Для того, чтобы выполнить над стеком некоторое действие, нужно для объекта “стек” вызвать соответствующий метод (так иногда называют функцию-член класса). Уничтожение объекта также автоматизировано. Оно, как и уничтожение любой встроенной переменной, произойдет при выходе из объемлющего блока. Проиллюстрируем все сказанное примером:

void main()

{

int i;

iStack stack;

for(i = 0; i <= 10; i++) stack.push(i*10);

for(i = 0; i <= 10; i++) printf("%d\n", stack.pop());

getch();

}

В четвёртой строке объявлена переменная типа iStack. В отличие от Си, в C++ это объявление является оператором, вызывающим конструктор класса iStack для объекта stack.

Следует упомянуть, что, поскольку эта переменная имеет автоматический тип хранения, она будет размещена в системном стеке. Размер памяти, необходимой для ее размещения, определяется суммарным размером членов-данных класса iStack. Может создаться ошибочное впечатление, что в области памяти, отведенной под объект, помещается все, что объявлено внутри класса. Однако это не верно: функции, объявленные в классе хранятся вне какого-либо блока данных.

Далее, в циклах, для объекта stack вызываются функции члены push() и pop(). Как видно из примера, доступ к ним, как и к элементам структуры, осуществляется посредством оператора “.” (точка):

stack.push(i*10);

stack.pop();

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

push(stack, i*10);

pop(stack);

В сущности обе версии программы вызывают одну и ту же функцию. Разница заключается лишь в том, как, синтаксически, это происходит. В обоих случаях функции должны получить адрес конкретного стека, над которым нужно выполнить операцию, но в случае с ООП-реализацией этот адрес передается неявно, а при использовании обычных функций – явно.

После того, как стек сыграл свою роль в программе, (например, после выхода из функции, где был объявлен), он должен быть удален из памяти. В Си для этого приходилось явно вызывать специальную функцию:

delete_stack(&stack);

Для объекта stack такую функцию вовсе вызывать не нужно: его деструктор будет автоматически вызван перед выходом из объемлющей области, в нашем примере, функции main().

13.4. C++ и объектно-ориентированное программирование

Кроме решения приведенных выше (в разделе 13.1) проблем, ООП стимулирует повторное использование существующего кода, способствует коллективной работе нескольких программистов над проектом, повышает безопасность и отказоустойчивость программ, простоту их тестирования и сопровождения. Другим немаловажным фактом является то, что применение ООП позволяет описать задачу в более понятных и близких человеку понятиях.

Объектно-ориентированное программирование (ООП) – это подход к написанию программ, суть которого заключается в сведении реализации проекта к реализации набора объектов и построению взаимосвязей между ними. Методология ООП отталкивается от понятия объекта, как некоторого набора данных и функций, управляющих этими данными. Обычно тип объекта – это реализованная на языке программирования концепция.

Так, можно говорить о концепции вещественного числа (с операциями +, -, *, /, …), концепции человека (с операциями «вывести на экран свою фамилию», «начислить себе зарплату», «идти выносить мусор»), стека (со сложной структурой данных и простым интерфейсом «push» и «pop»).

В языке C++ типом объекта называется его класс. Класс – это определяемый пользователем тип. Класс включает данные, необходимые для хранения информации об объекте, и функции управления этими данными. Объект – это переменная класса (т.е. типа данных объявленного пользователем). Синтаксис определения класса, в упрощенном виде, можно описать так:

определение_класса::=

“class | struct” идентификатор “{” { блок_объявлений } “};”

блок_объявлений::=

дисциплина_доступа { объявление_члена_класса }

дисциплина_доступа::=

“private:” | “public:”

объявление_члена_класса::=

объявление_функции | объявление_переменной

В описании класса могут содержаться объявления функций, данных, типов, других классов (все они называются членами класса). Все пространство объявлений разделяется на области по дисциплине доступа. Дисциплину доступа к тому или иному члену класса определяет ключевое слово (private или public), стоящее перед блоком объявлений, в который он входит.

Очевидно, дисциплина доступа к члену класса определяется ближайшим (сверху) квалификатором доступа. В случае, когда такого квалификатора нет, член получает права доступа по умолчанию: если описание класса началось ключевым словом class – private, если struct – public.

Важно помнить, что понятия объявления и определения (declaration and definition) различаются. Так, например, объявить функцию – значит задать ее прототип:

int summ(int, int);

определить функцию, значит привести ее тело:

int summ(int a, int b) { return a+b; };

Аналогично, разделяют понятия объявления и определения класса: определение класса содержит перечисление всех его членов, тогда как объявление лишь указывает компилятору, что данное имя – имя класса.

class some_class; // Объявление класса

class some_class // Определение класса

{

//...

};

Формально, класс или функция считаются определенными после того, как встретилась закрывающая фигурная скобка определения.

Относительно данного класса весь код программы можно условно разделить на две части: код, который «принадлежит» классу, и весь остальной код. К первой группе относятся, в частности, определения функций-членов. К закрытым членам класса (т.е. к функциям и переменным, объявленным с дисциплиной доступа private) можно обратиться только из тех частей программы, которые принадлежат классу. Рассмотрим определение функции извлечения элемента из стека:

int iStack::pop()

{

return remove_item(top);

}

Для того чтобы определить функцию-член класса необходимо в ее заголовке, непосредственно перед именем (через два двоеточия “::”) указать название класса. В нашем примере, функции remove_item, в качестве параметра, передается закрытый член класса iStack – переменная top. Такое обращение к переменной правомерно, т.к. происходит в определении функции-члена того же класса. Точно так же, при необходимости, из функции, принадлежащей области видимости класса, можно обращаться к его открытым членам и к членам-функциям.

С другой стороны, из любой, не принадлежащей области видимости класса функции, обращение к закрытым членам невозможно. Следует помнить, что определение метода класса может встретиться на значительном расстоянии от определения самого класса, и все функции, оказавшиеся между ними, могут не иметь к классу никакого отношения.

Для класса могут быть объявлены две функции специального вида. Первая из них называется конструктор (constructor). Он не имеет типа возвращаемого значения и его имя должно совпадать с именем класса. Гарантируется, что если у класса есть конструктор, то он будет вызван для каждого объекта класса перед первым его (объекта) использованием.

Второй функцией специального назначения является деструктор (destructor). Его имя также должно совпадать с именем класса и в объявлении не надо указывать тип возвращаемого значения, но начинаться оно должно с тильды “~”. Гарантируется, что если у класса есть деструктор, то он будет вызван перед выходом из блока объемлющего объявление объекта данного класса:

class Group

{

public:

Group(int); // Constructor

~Group(); // Destructor

//...

private:

int *marks;

//... Другие члены.

};

Group::Group(int number)

{

// Выделение памяти для массива оценок

// студентов группы из number целых чисел

marks = (int *) malloc(number);

//... Инициализация других переменных.

}

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

В примере конструктору должен передаваться параметр – величина массива. Ниже приведен пример функции создающей объект класса Group, и передающий, в качестве параметра, его конструктору число 15:

void function(void)

{

Group g251002(15);

//... Использование объекта g251002

}

Из того, как вызывается конструктор, следует, что он (конструктор) не может иметь возвращаемого параметра. Это правило распространяется и на деструктор:

Group::~Group()

{

// Удаление массива из динамической памяти

free(marks);

}

Обычно, деструктор освобождает ресурсы, выделенные для объекта конструктором.

Как и к членам структуры Си, доступ к членам класса производится посредством операторов “.” (точка) и “->” (стрелка). Таким образом, можно получить доступ не только к данным объекта, но и к его функциям:

g251002.~Group();

g251002.Group(25);

Таким образом, для объекта g251002 был вызван деструктор, который вернул в кучу память, выделенную для массива из 15 элементов, а затем конструктор, который создал новый массив из 25 элементов.

Если имеется указатель на объект, то те же действия можно выполнить таким образом:

Group *pg = &g251002;

pg->~Group();

pg->Group(25);

ООП зиждется на трех основных понятиях: инкапсуляция, наследование и полиморфизм. Инкапсуляцией называется способность классов скрывать детали реализации (функции и переменные), или, другими словами, совмещать данные и функции их обработки. Эта способность классов была рассмотрена выше. Наследование – это механизм, позволяющий получить новый тип данных (класс) из уже имеющегося. При этом описание класса может быть изменено и дополнено. Наследование стимулирует повторное использование кода. Под понятием полиморфизм (в контексте ООП) понимают возможность одинаково обращаться к родственным объектам. Так, примером полиморфизма является перегрузка функций. Эта тема рассмотрена в разделе 13.6.

13.5. Наследование

При решении многих задач оказывается, что разные классы имеют множество близких свойств и используют большое количество схожего кода. Примерами таких классов могут служить стек и очередь. Если реализовать эти классы раздельно, то в части реализации списков, на которых они основаны, различий может не быть вовсе. Реализовав список, и наследуя от него стек и очередь можно добиться наиболее простого и изящного решения.

Преобразуем список из примера 13.2 в класс iList. Для этого проделаем все то же, что и в разделе 13.1 со стеком: выделим интерфейс и реализацию, заменим имена конструкторов и деструкторов, уберем из числа формальных параметров ссылки на конкретный объект. В результате список примет такой вид:

class iList

{

public:

iList(); // Конструктор

~iList(); // Деструктор

struct TItem* add_item(int num);

int front_item_value();

void removet_item();

private:

struct TItem* front;

int size;

};

iList::iList() // Конструктор

{

size = 0;

front = 0;

}

iList::~iList() // Деструктор

{

while (size) remove_item();

}

// Остальные функции-члены

В данном примере для простоты подразумевается, что в точке объявления класса доступен, определенный ранее «элемент списка». Теперь структура программы такова:

1. Подключение заголовочных файлов библиотек

2. Определение типа «элемент списка»

3. Определение функций работающих с элементами списка

4. Класс iList

5. Класс iStack

В связи с изменениями, произошедшими в реализации списка, придется модифицировать стек. Это можно сделать так:

// Класс iStack (стек чисел_типа_int)

class iStack

{

public:

void push(int a);

int pop();

private:

struct iList list; // Список

};

void iStack::push(int a)

{

list.add_item(a);

}

int iStack::pop()

{

int res = list.front_item_value();

list.remove_item();

return res;

}

Следует отметить, что в данном случае нет необходимости в создании конструктора и деструктора класса iStack, т.к. единственная переменная член (list) имеет конструктор и деструктор по умолчанию (т.е. конструктор и деструктор не требующие передачи им параметров), которые будут вызваны автоматически.

Уже на таком простом примере видно, что создание цепочки базирующихся друг на друге классов имеет большие преимущества по сравнению с созданием набора процедур, реализующих более простые сущности. Однако ООП предлагает еще более широкие возможности.

Недостатком приведенной реализации стека может стать то, что, формально, он никак не связан со списком, хотя представляет с ним практически одно целое. Одним из способов указать компилятору, что данные классы имеют родственную структуру (а конкретней, стек – является развитием идеи списка), и, таким образом, избавиться от программирования тех функций стека, которые уже есть в списке, является применение механизма наследования.

class iStack: public iList

{

public:

void push(int a);

int pop();

};

В данном случае класс iList становится предком для iStack и все его члены (кроме конструктора и деструктора) автоматически становятся членами класса-потомка. Определению, очевидно, подлежат функции-члены push() и pop():

void iStack::push(int a)

{

add_front_item(a);

}

int iStack::pop()

{

int res = get_front_item();

del_front_item();

return res;

}

Как и в предыдущем, в данном примере явно не вызываются конструкторы iList и iStack. Это объясняется тем, что первый имеет конструктор по умолчанию, а второму конструктор вообще не нужен (нет данных подлежащих инициализации или действий, которые нужно произвести перед началом работы с экземпляром класса).

Упрощенно наследованием классов называется порождение одного класса от другого. При этом порождающий класс является предком, отцом, базовым классом для порождаемого класса. И наоборот, порождаемый класс – наследник, сын, производный класс относительно порождающего класса. Возможны разные способы наследования. Простейший из них описывается так:

определение_класса_наследника::=

“class” имя_потомка “: public” имя_предка

“{” { блок_объявлений } “};”

В результате потомок содержит все члены базового класса но имеет доступ лишь к открытым.

13.6. Перегрузка

Перегрузка – это средство языка C++, позволяющее несколько раз использовать один и тот же идентификатор для схожих логически, но разных формально сущностей. Так, перегрузить функцию означает – создать несколько функций с одинаковым именами, но разными формальными параметрами:

void print(int a); // Вывести на печать число

void print(char c); // Вывести на печать символ

void print(char* s); // Вывести на печать строку

Каноническим является пример функции print. Это очень удобное имя для функции, выводящей что-то на печать. Но если в программе используется несколько функций, одна из которых выводит число, другая – символ и т.д., то в Си придется создать функции с разными именами (printa(int), printc(char), prints(char*), …). Это, в свою очередь, вносит некоторые неудобства при работе с функциями (иногда необходимо иметь достаточно богатую фантазию, чтобы придумывать новые имена, сложно вспомнить, какое имя имеет нужная модификация и т.д.).

С другой стороны, очевидно, что компилятор и сам может выбрать среди предложенных прототипов, какую именно функцию имеет в виду программист:

void f(int a, char c, char* s)

{

//...

print(a); // Будет вызвана void print(int a)

print(c); // Будет вызвана void print(char c)

print(s); // Будет вызвана void print(char* s)

//...

}

В случае, когда ни один из прототипов не подходит для вызова (например, при попытке вызова print с параметром типа double или int*) компилятор попытается выполнить неявное преобразование к нужному типу, или, если оно не возможно, констатирует ошибку.

Очевидно, перегрузка функций является развитием принципа полиморфизма в ООП. Перегрузку можно применять и к членам-функциям классов.

13.7. Ссылочный тип

Дополнительно к типу указателя в C++ введен ссылочный тип. Переменная ссылочного типа похожа на переменную указатель, но может быть проинициализирована ссылкой на некоторую переменную (ее адресом) лишь один раз (при объявлении) и, в дальнейшем, не нуждается в операциях раскрытия указателя:

int a = 5; // Переменная целого типа

int *pa = &a; // Указатель на переменную целого типа

int &sa = a; // Ссылка на переменную a (целого типа)

Из данного примера виден синтаксис объявления ссылок. В отличие от объявления указателя идентификатору ссылки предшествует не звёздочка, а амперсанд. Кроме того, как уже было сказано, ссылка должна быть инициализирована при объявлении (заметьте, что в инициализации ссылки, перед идентификатором «a», нет амперсанда).

Работать со ссылочной переменной можно точно так же, как с переменной на которую она ссылается:

void f(int a)

{

int *pa = &a;

int &sa = a;

sa = 3; // Эквивалентно a = 3; или *pa = 3;

//...

f(sa); // Эквивалентно f(a); или f(*pa);

}

Это средство было бы практически бесполезно, если бы не возможность передавать функции параметры ссылочного типа:

void s_add(int &sa, int b)

{

sa += b;

}

При передаче параметров, переменная b будет передана в функцию через стек по значению, а переменная sa станет ссылкой на первый фактический параметр функции add(). Таким образом, при изменении sa реально изменяется переменная, на которую sa ссылается. Можно говорить что add() является аналогом такой функции использующей указатель:

void p_add(int *pa, int b)

{

*pa += b;

}

Применение ссылки в качестве формального параметра функции изменит и синтаксис ее вызова:

void f(int a, int b)

{

// Вызов с передачей адреса переменной

p_add(&a, b);

// Вызов с «передачей ссылки» на переменную

s_add(a, b);

}

В приведенном примере обе функции изменят значение a, прибавляя к нему b. Не следует, также, забывать и о том, что во втором случае также произошла передача адреса, хотя и в неявной форме.

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

struct TItem *create_item(struct TItem **item,

struct TItem *nxt,

int num)

{

*item = (struct TItem *) malloc(sizeof(struct TItem));

(*item)->number = num;

(*item)->next = nxt;

return *item;

}

Здесь для того, чтобы дать возможность функции изменить при необходимости указатель на элемент списка, используется указатель на указатель. Хотя это вполне простой прием, он делает код непонятным и запутанным. Его можно упростить заменив один из указателей ссылкой:

struct TItem *create_item(struct TItem *&item,

struct TItem *nxt,

int num)

{

item = (struct TItem *) malloc(sizeof(struct TItem));

item->number = num;

item->next = nxt;

return item;

}

Таким образом, использование ссылок упрощает синтаксис функций, которые должны в качестве параметров получать (константные) указатели, а не сами переменные. Следует помнить о том, что нет способа изменить переменную ссылку так, чтобы она ссылалась на другую переменную, нежели указано в объявлении (или при передаче фактического параметра функции).

Литература

1. Бахтизин В.В., Глухова Л.А. и др. Методические указания по вычислительной практике и самостоятельной работе по курсам "Программирование" и "Конструирование программ и языки программирования" для студентов специальности "Вычислительные машины, комплексы, системы и сети", "Программное обеспечение ЭВМ и автоматизированных систем", Части 1, 2, 3, 4. - Мн.: МРТИ, 1989-1992.