6. Операции над линейными списками
 

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

К первой группе операций относятся:

• создание списка;
• уничтожение списка;
• печать (вывод) списка;
• копирование списка;
• упорядочение списка;
• объединение списков;
• сохранение и восстановление списка.

• поиск элемента в списке;
• включение элемента в список;
• выборка и обработка элементов;
• удаление элемента из списка.

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

Обозначим указатели на эту тройку элементов через PRED, ТЕК и SLED (смотри рис.), пусть поле указателя в элементе имеет имя Ptr , а поле ключа — key.

Отношение порядка между элементами списка

Переход к последующему элементу осуществляется по указателю LED=TEK.Ptr в текущем элементе. Конец списка определяется нулевым указателем в текущем элементе (TEK.Ptr==NULL).

Возможны удачный и неудачный поиски. Удачный поиск завершается при нахождении искомого элемента, в этом случае возвращается адрес найденного элемента, по которому и осуществляется его обработка. Если элемент не найден при достижении конца списка (неудачный поиск), то возвращается некоторый признак «элемент не найден» (обычно нулевой указатель NULL). Для поиска элемента достаточно одного указателя ТЕК. Алгоритм поиска можно представить в следующем виде:
 1.  ТЕК = указатель на первый элемент.
 2.  Если ТЕК == NULL, то конец списка и элемент не найден.
Переход к п. 5.
 3.  Если ТЕК.кеу == ключу поиска, то элемент найден, переход к п.5.
 4.  ТЕК = TEK.Ptr; переход к п. 2.
 5.  Конец алгоритма, возврат результата.

Поиск в упорядоченном списке имеет свою особенность. Так при поиске в списке, упорядоченном по возрастанию ключей, если ключ поиска меньше ключа текущего элемента, то дальнейший поиск теряет смысл, например, в упорядоченном списке с ключами 5, 7, 9,... осуществляется поиск элемента с ключом 8. Поиск прекращается при достижении элемента с ключом 9 (8ɡ).

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

После создания дескриптора формирование списка сводится к последовательному включению элементов в список.

Уничтожение списка. Уничтожение списка сводится к освобождению памяти, занятой элементами и дескриптором списка. Алгоритм уничтожения сводится к следующему:
 1.  В указатель ТЕК заносим адрес начала списка из дескриптора, а в SLED — адрес следующего элемента: SLED=TEK.Ptr.
 2.  Если TEK==NULL, то переход на пункт 5, иначе по указателю ТЕК освободим память.
 3.  Продвинемся по списку на следующий элемент: TEK=SLED; SLED=TEK.Ptr (или SLED=SLED.Ptr, что равносильно).
 4.  Выполним пункты 2 и 3.
 5.  Освободим память из-под дескриптора (обнулим указатель на начало списка). Конец алгоритма.

Печать (вывод) списка. Печать списка сводится к последовательному просмотру элементов списка до его конца и печати полей каждого элемента в определенном формате. Аналогичным образом производятся и другие виды обработки элементов списка. Для продвижения по списку достаточно одного указателя ТЕК.
 1.  В ТЕК заносим адрес начала списка.
 2.  Если TEK==NULL, то переход на 5, иначе печать элемента по указателю ТЕК.
 3.  Продвижение по списку ТЕК = TEK.Ptr.
 4.  Выполнение пунктов 2 и 3.
Конец алгоритма.

Копирование списка. В результате копирования создаются два списка с одинаковыми элементами в различных областях памяти. Алгоритм копирования списка А в список В можно представить в следующем виде.
 1.  Построить дескриптор нового списка В.
 2.  Установить указатель текущего элемента ТЕК_А на очередной элемент списка А, начиная с начала списка.
 3.  Получить память для элемента В и занести ее адрес в указатель ТЕК_В.
 4.  Копировать содержимое текущего элемента списка А в текущий элемент списка В: *ТЕК_В = *ТЕК_А.
 5.  Выполнять пункты 2 — 4, пока не будет достигнут конец списка А.

Иногда копирование списка производится для получения; упорядоченного списка из исходного неупорядоченного.

Упорядочение списка. Упорядочение списка (сортировка списка) — это перестановка элементов списка в восходящем или нисходящем порядке в зависимости от конкретных значений одного или нескольких полей внутри элементов списка. Обработка упорядоченных списков облегчается.

Обычно упорядочение списка осуществляется при его создании или копировании. Упорядочение существующего списка «на месте» можно выполнить по методу прямого включения, суть которого заключается в следующем. Начиная со второго элемента, выбираем очередной элемент и включаем его в нужное место с начала списка. Для этого достаточно скорректировать указатели элементов.

Пусть в неупорядоченном списке элементы расположены в следующей последовательности ключей: 5, 8, 9, 6, 7, ...Обозначим указатели на элементы как Р1, Р2, РЗ, Р4, Р5 (рис. ).

Алгоритм включения элемента в нужное место можно описать так. Последовательным просмотром с начала списка и сравнением ключей текущего и следующего элементов по признаку TEK.key > SLED.key устанавливаем, что элемент с ключом 6 должен быть переставлен в списке ближе к его началу. Далее последовательным просмотром с начала списка и сравнением по признаку ТЕК.кеу > 6 находим место вставки — это между элементами с ключами 5 и 8. Процесс перестановки элемента с ключом 6 сводится к обмену указателями между элементами:
 Р1.Ptr = РЗ.Ptr; (P4);
 РЗ.Ptr = Р4.Ptr; (P5);
 Р4.Ptr = PI.Ptr; (Р2);

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

Объединение списков. Алгоритмы объединения списков в основном определяются характером решаемой задачи и зависят от многих факторов.
1. Объединяемые списки могут рассматриваться как множества, тогда возможны схемы логического объединения А∩В, А?В, А-В, и производится соответствующий отбор элементов, включаемых в новый список.
2. Исходные списки могут быть упорядочены или нет.
3. Результирующий список создается на новом месте и исходные списки сохраняются либо он создается на месте исходных без дополнительного выделения памяти.

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

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

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

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

Возможны два вида хранения данных в файле: в текстовом формате с использованием средств форматного ввода-вывода и в двоичном формате — неформатный ввод-вывод. Хранение элементов списка в текстовом формате предпочтительней, так как позволяет редактировать данные непосредственно в файле. Более того, появляется возможность построения списка по данным из обычного файла с однотипными записями.

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

• разрешается наличие элементов с дублирующими ключами. Новый элемент включается в список. Если список упорядоченный, то новый элемент включается за элементами с такими же ключами;
• элементы с дублирующими ключами не допускаются, но новый элемент вклю-чается вместо старого (обновление на месте);
• элемент с дублирующим ключом отвергается.

Кроме того, действия по включению элемента зависят от места включения элемента в список.

Включение элемента в начало списка. Если список пустой, то:
 1.  Получение памяти под элемент, адрес элемента помещается в указатель списка.
 2.  Заполнение полей элемента данными (инициализация элемента).
 3.  Обнуление указателя в элементе.

Если список не пустой, то:
  1.  Получение памяти под элемент. В поле указателя нового элемента помещает-ся содержимое указателя списка из дескриптора а адрес элемента помещается в поле указателя списка в дескрипторе.
  2.  Инициализация нового элемента.

Включение элемента за определенным (текущим) элементом. После того как текущий элемент, за которым включается новый, найден:
 1.  Получаем память под элемент, его адрес помещаем в указатель NEW. В поле указателя его помещаем содержимое поля указателя из текущего элемента (за которым включаем): NEW.Ptr= TEK.Ptr.
 2.  В поле указателя текущего элемента помещаем адрес нового элемента:
TEK.Ptr = NEW
 3.  Инициализируем новый элемент данными.

По этому же алгоритму осуществляется и включение элемента в конец списка.

Включение элемента перед определенным (текущим) элементом. При поиске места включения запоминаются два адреса: текущего элемента ТЕК, перед которым включается новый элемент, и предыдущего элемента PRED. После того как нужный элемент найден, новый элемент включается за предыдущим, как было рассмотрено выше.

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

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

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

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

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

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