15. Связанные списки: описание структуры, добавление и удаление элементов в односвязный линейный список.

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

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

Вставка узла

Одной из типичных операций при работе со списком является вставка нового узла в определенное место связанного списка.

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

1. Необходимо выделить память под новый узел.

2. Записать в новый узел значение.

3. Записать в указатель на следующий узел в этом узле адрес узла, который должен располагаться после нового узла.

4. Заменить в узле, который будет располагаться перед новым узлом, записанный адрес на адрес нового узла.

Если осуществить действия в другом порядке, то мы потеряем адрес узла, который должен располагаться после нового узла. А это означает, что мы не только не найдем этот узел, но и потеряем все узлы, расположенные за ним.

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

Удаление узла

Второй типичной операцией со списками является удаление узла, находящегося в середине списка.

В односвязном списке для удаления узла нужно выполнить следующие действия:

1. Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел в узле, предшествующем удаляемому.

2. Удалить узел, предназначенный для удаления.

16. Виды линейных списков: стек, очередь, дек.

Линейные списки – структуры данных, в которых элементы (переменные) следуют друг за другом, и каждому можно поставить в соответствие порядковый номер.

Стек – это линейный список, в котором все операции вставки и удаления( и как правило операции доступа к данным) выполняются только на одном конце списка.

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

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

17. Описание структуры на языке C++. Определение переменных структурного типа. Способы доступа к элементам структур.

18. Описание объединения на языке C++. Определение переменных типа «объединение». Способы доступа к элементам объединений.