Копирование части списка.

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

Рис. 10. Перестановка соседних элементов 2-связного списка

Представление списка на базе вектора не вызывает затруднения.

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

ЛЕКЦИЯ 5. СТЕК, ОЧЕРЕДЬ

Цели и задачи лекции:

Ознакомить с принципами статической и динамической организации стека, очереди.

Основные рассматриваемые вопросы: стек, очередь.

Стек

Стек - это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. Здесь используется принцип «последним пришел - первым вышел» (LIFO: Last Input - First Output).

Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка

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

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

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

Поскольку стек, по своей сути, является структурой с изменяемым количеством элементов, то для динамической реализации стека целесообразно использовать линейный однонаправленный список.

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка

Основные операции, производимые со стеком:

- записать (положить в стек);

- прочитать (снять со стека);

- очистить стек;

- проверка пустоты стека.

Очередь

Очередь - это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип «первым пришел - первым вышел» (FIFO: First Input - First Output).

Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка .

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

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

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

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

С точки зрения экономии вычислительных ресурсов более предпочтителен второй способ. Однако здесь усложняется проверка на пустоту очереди и контроль переполнения очереди - индекс конца очереди не должен «набегать» на индекс начала.

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

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

Основные операции, производимые с очередью:

- добавить элемент;

- извлечь элемент;

- очистить очередь;

- проверка пустоты очереди.