<<
>>

Линейные односвязные списки

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

• работать с произвольным количеством элементов, добавляя и удаляя их по мере необходимости;

• осуществлять вставку и удаление записей, не перемещая остальных элементов последовательности.

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

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

Исходные установки. В начале программы необходимо описать элемент и его тип:

Type tpel=Aelement; {тип «указатель на элемент»} element=record

пит:integer; {число}

p.tpel; {указатель на следующий элемент} end;

В статической памяти описываем переменную-указатель списка и несколько переменных-указателей, используемых при выполнении операций со списком:

Var first, {указатель списка - адрес первого элемента списка}

n,f,q:tpel; {вспомогательные указатели}

Исходное состояние «список пуст»:

first: =nil;

Добавление нового элемента к списку.

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

В общем случае при добавлении элемента к списку возможны следующие варианты:

• список пуст, добавляемый элемент станет единственным элементом списка;

• элемент необходимо вставить перед первым элементом списка;

• элемент необходимо вставить перед заданным (не первым) элементом списка;

• элемент необходимо дописать в конец списка.

Добавление элемента к пустому списку состоит из записи адреса элемента в указатель списка, причем в поле «адрес следующего» добавляемого элемента необходимо поместить nil:

new(first); {запрашиваем память под элемент}

first А.пит:=5; {заносим число в информационное поле} first A.p:=nil; {записываем nil в поле «адрес следующего»}

На рис. 7.10 показана последовательность операций при добавлении элемента к пустому списку.

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

{запрашиваем память под элемент}

{заносим число в информационное поле}

{в поле «адрес следующего» переписываем адрес

первого элемента}

{в указатель списка заносим адрес нового элемента}

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

будут корректироваться (рис. 7.12). Пусть f- адрес предыдущего элемента, а п - адрес следующего элемента, тогда:

{запрашиваем память под элемент}

{заносим число в информационное поле}

{в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}

{в поле «адрес следующего» предыдущего элемента за- носим адрес нового элемента}

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

{запрашиваем память под элемент}

{заносим число в информационное поле}

{в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}

{в поле «адрес следующего» предыдущего элемента за- носим адрес нового элемента}

Добавление элемента в конец списка.

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

(запрашиваем память под элемент}

(заносим число в информационное поле}

(в поле «адрес следующего» элемента записываем nil} (в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}

д

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

{запрашиваем память под элемент}

{заносим число в информационное поле}

{в поле «адрес следующего» нового элемента записываем nil}

{в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}

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

Пример 7.2. Разработать программу, которая строит список по типу стека из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации клавиш CTRL-Z (конец файла на устройстве ввода).

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

ReadLn(a);

new(first); {запрашиваем память под элемент}

first А.пит:=а; {заносим число в информационное поле} first A.p:=nil; {записываем nil в поле,«адрес следующего»} while not EOF do begin

ReadLn(a);

new(q); {запрашиваем память под элемент} qA.num:=a; {заносим число в информационное поле} qA.p:—first; {в поле «адрес следующего» переписываем адрес

первого элемента}

first :=q; {в указатель списка заносим адрес нового элемента} end; ...

Пример 7.3. Разработать программу, которая строит список по типу очереди из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации CTRL-Z (конец файла на устройстве ввода).

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

{запрашиваем память под элемент}

{заносим число в информационное поле}

{Г - текущий элемент, после которого добавляется следующий}

{запрашиваем память под элемент} {заносим число в информационное поле}

fA-p:=q; {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента} f:—f Л.р; {теперь новый элемент стал последним} end; ~

qA.p:=nil; {в поле «адрес следующего» последнего элемента записываем nil}

Этот фрагмент можно упростить, если заметить, что новый элемент к списку можно добавлять сразу при запросе памяти:

ReadLn(a);

new (first); {запрашиваем память под элемент}

first А.пит:=а; {заносим число в информационное поле}

f:=Jirst; {f - текущий элемент, после которого добавляется

следующий}

fA.p:=nil; ... {в поле «адрес следующего» последнего элемента записываем nil}

Пример 7.4. Разработать программу, которая строит список, сортированный по возрастанию элементов, из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации СТ11Ь-2 (конец файла на устройстве ввода).

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

new(first); {запрашиваем память под первый элемент}

ReadLn(first А.пит); {заносим число в информационное поле} firstA.p:=nil; while not EOF do begin

new(q); {создаем элемент}

ReadLn(qA.num); {заносим значение} if qA.num

<< | >>
Источник: Иванова Г.С. Основы программирования. 2002

Еще по теме Линейные односвязные списки:

  1. ИГНОРИРУЙТЕ ЛИНЕЙНЫЕ ПРЕДСКАЗАНИЯ И ИЗБЕГАЙТЕ ЛИНЕЙНЫХ ВЫВОДОВ! ВЕРЬТЕ СВОЕМУ СЕРДЦУ!
  2. Номер один в списке неправильных действий
  3. Линейно-функциональные структуры.
  4. Линейный и нелинейный умы
  5. Линейные структуры.
  6. Линейный ум-эго
  7. Модификации линейной организационной структуры.
  8. Линейное и нелинейное мышление
  9. Линейное и нелинейное мышление
  10. Линейный и нелинейный ум
  11. Линейный и нелинейный умы
  12. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  13. Зрители требуются во всех играх.
  14. Иерархия