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

1. Зачем нужны структуры?

2. Как определить новую структуру и объявить переменные-структуры?

3. Как инициализировать структуру?

4. Как объявить массив структур?

5. Что такое поле структуры и как к ним обращаться?

6. Что такое вложенные структуры?

7. Как вывести содержимое массива структур в виде таблицы?

8. Можно ли передавать структуры в качестве аргументов функций и возвращать структуры в качестве значений функций?

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

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

Тема 4.5. Реализация динамических структур данных на основе массива

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

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

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

4.5.1Пометка элементов

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

Реализуем динамический массив для целых чисел. Объявим целочисленный массив для хранения элементов и логический массив для отметки существования элементов. Кроме того, зададим константу, означающую вместимость массива. Создадим функцию инициализации, заполняющую логический массив значениями false, что означает отсутствие элементов.

const int size=10;

int numbers[size];

bool exists[size];

void init() {

for (int i=0; i<size; i++) {

exists[i]=false;

}

}

Для вывода всех элементов следует пробежаться по всему массиву и вывести элементы, помеченные существующими:

void print() {

for (int i=0; i<size; i++) {

if (exists[i]) {

cout << numbers[i] << " ";

}

}

cout << endl;

}

Для реализации добавления элемента следует найти пустую позицию, записать туда новое значение и пометить его существующим. Если пустая позиция не найдена, то следует сообщить, что массив заполнен.

int getEmptyPosition() {

for (int i=0; i<size; i++) {

if (!exists[i]) {

return i;

}

}

return -1;

}

void add(int x) {

int pos = getEmptyPosition();

if (pos != -1) {

numbers[pos]=x;

exists[pos]=true;

} else {

cout << "No place\n";

}

}

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

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

int find(int x) {

for (int i=0; i<size; i++) {

if (exists[i] && numbers[i]==x) {

return i;

}

}

return -1;

}

Наконец, удаление заключается в том, что удаляемый элемент ищется и, если он найден, то помечается как несуществующий.

void remove(int x) {

int pos = find(x);

if (pos != -1) {

exists[pos]=false;

} else {

cout << "No such element\n";

}

}

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

init();

for (;;) {

cout << "1 - Print\n2 - Add\n3 - Remove\n";

cout << "0 - Exit\nYour choice - ";

int choice; cin >> choice;

int toRemove;

switch(choice) {

case 1 : print(); break;

case 2 : add (rand()); print(); break;

case 3 : cout << "Element to be removed=";

cin >> toRemove;

remove(toRemove);

print(); break;

case 0 : exit(EXIT_SUCCESS);

default : cout << "Error\n";

}

system("pause"); system("cls");

}