Реализация операций над связными линейными списками

5.2.2. Реализация операций над связными линейными списками

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

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

В программных примерах подразумеваются определенными следующие типы данных:

• любая структура информационной части списка:
  type data = ...;
• элемент односвязного списка (sll - single linked list): type sllptr = ^slltype; { указатель в односвязном списке } slltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент } end;
• элемент двухсвязного списка (dll - double linked list): type dllptr = ^dlltype; { указатель в двухсвязном списке } dlltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент (вперед) } prev : sllptr; { указатель на предыдущий элемент (назад) } end;

Словесные описания алгоритмов даны в виде комментариев к программным примерам.

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