Динамические структуры данных

Синтаксис языка С++ допускает определение структуры с элементами, которые являются указателями на тип самой структуры. Это позволяет создавать динамические типы с произвольным числом таких структур, связанных вместе.

Н а п р и м е р : struct type_list {

type data;

type_list * next;} *list_1;

list_1= new type_list;

1 2 3

list_→ datа data data

next next next = 0

Здесь list_1 – указатель на начало списка; data – данные типа type; next – адрес следующего элемента типа type_list или 0.

Через указатель на начало списков осуществляется доступ к данным, хранящимся в элементах.

Задания

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

Варианты СТД:

1. Динамический вектор;

2. Динамическая матрица;

3. Динамический куб;

4. Динамический стек;

5. Динамическая очередь;

6. Линейный связанный список;

7. Динамический массив комплексных чисел;

8. Мультивектор, содержащий три вектора;

9. Персонал;

10. Библиотека.

Проверьте работоспособность СТД на тестовом наборе данных.

Контрольные вопросы

1. Что такое структуры и объединения? Сформулируйте правила инициализации.

2. Опишите механизм передачи структур функциям.

3. По какому принципу создаются динамические структуры данных?

4. Объясните, что представляет собой массив структур?

5. В каких случаях возникает необходимость использовать вложенные структуры и объединения?

Р а з д е л IV

РАЗРАБОТКА АБСТРАКТНЫХ ТИПОВ ДАННЫХ

Цель работы: изучить способы определения классов, правила доступа к элементам; приобрести практические навыки работы с объектами класса; изучить принципы и механизмы создания абстрактных типов данных.

Основные теоретические положения

Определение классов

Класс – это гетерогенный агрегатный тип, имеющий элементы, данные и элементы функций, обеспечивающий сокрытие данных и наследование.

Структура класса имеет вид:

class имя_типа {public: // элементы доступны и наследуются

----- ------ -------

protected: //элементы защищены и наследуются

----- ------ -------

private: //элементы закрыты, не наследуются

----- ------ -------

};

Спецификаторы доступа public, protected и private определяют степень открытости элементов, которые следуют за ними.

По умолчанию элементы структуры являются открытыми, элементы класса – закрытыми.

Компонентные функции

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

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

Дружественные функции

Дружественная функция должна быть объявлена внутри объявления класса, по отношению к которому она является дружественной, с использованием спецификатора friend. Такая функция имеет доступ к закрытым элементам класса наряду с компонентными функциями. Дружественными могут быть как внешние, так и компонентные функции, в этом случае для указания имени функции в дружественном классе используется оператор разрешения области видимости ::.

Н а п р и м е р :

class A {-----

friend int B:: f( ); // f() - компонентная функция класса В, дружественная классу А

};

class C {----

friend class B; // все компонентные функции класса В являются дружественными классу С

};

class D {----

friend D f(D); // f() - внешняя функция, дружественная классу D

};

Указатель this

Ключевое слово this неявно объявляет указатель на себя. Может иметь место только в нестатических компонентных функциях. Заменяет объявление закрытого элемента:

class_type * const this.