Линейные односвязные списки используют чаще других списковых структур, так как они сравнительно просты, но одновременно в отличие от одномерных массивов позволяют:
• работать с произвольным количеством элементов, добавляя и удаляя их по мере необходимости;
• осуществлять вставку и удаление записей, не перемещая остальных элементов последовательности.
Недостатком этой структуры является то, что при поиске элемента по номеру приходится просматривать все ранее расположенные элементы, в то время как в одномерном массиве возможен прямой доступ к элементу по индексу. К тому же реализация линейного односвязного списка требует дополнительной памяти для хранения адресной части элементов.
Рассмотрим более подробно, как выполняются основные операции с линейными односвязными списками.
Исходные установки. В начале программы необходимо описать элемент и его тип:
Type tpel=Aelement; {тип «указатель на элемент»} element=record
num: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):
new(q); {запрашиваем память под элемент} qAnum:=4; {заносим число в информационное поле} qAp:=first; {в поле «адрес следующего» переписываем адрес
первого элемента} first:=q; ... {в указатель списка заносим адрес нового элемента}
Добавление элемента перед заданным (не первым). Для выполнения операции необходимо знать адреса элементов, между которыми вставляется элемент, так как адресные части этих элементов при выполнении операции
| |
| |
будут корректироваться (рис. 7.12). Пусть f- адрес предыдущего элемента, а п - адрес следующего элемента, тогда:
new(q); {запрашиваем память под элемент} дл.пит:=3; {заносим число в информационное поле} qA.p:=n; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента} j*.p:=q; ... {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}
Минимально для вставки элемента в линейный односвязный список необходимо знать только адрес предыдущего элемента, так как тогда адрес следующего элемента известен -
new(q); {запрашиваем память под элемент} qA.num:=3; {заносим число в информационное поле} qA.p:=f*.p; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента} f*.p:=q; ... {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}
| |
Добавление элемента в конец списка. В этом случае должен быть известен адрес элемента, после которого добавляется новый элемент (рис. 7.13):
new(q); {запрашиваем память под элемент} qA.num:=7; {заносим число в информационное поле} qA.p:=nil; {в поле «адрес следующего» элемента записываем nil} fAp:=q;... {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}
| |
Анализ показывает, что этот случай можно свести к предыдущему, так как адресная часть последнего элемента содержит nil:
new(q); {запрашиваем память под элемент} q\num:=7; {заносим число в информационное поле} qA.p:=fA.p; {в поле «адрес следующего» нового элемента записываем nil}
fA.p:=q; ... {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}
Комбинируя эти фрагменты, можно организовать построение списка с любой дисциплиной добавления элементов.
Пример 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 необходимо разместить в адресном поле только последнего элемента:
ReadLn(a);
new(first); {запрашиваем память под элемент}
first Апит:=а; {заносим число в информационное поле} f:—first; {f - текущий элемент, после которого добавляется
следующий}
while not EOF do begin ReadLn(a);
new(q); {запрашиваем память под элемент} qA.num:-a; {заносим число в информационное поле} fA.p:=q; {в поле «адрес следующего» предыдущего элемента
заносим адрес нового элемента} f:-f\p; {теперь новый элемент стал последним} end;
qA.p:=nil; {в поле «адрес следующего» последнего элемента записываем nil}
Этот фрагмент можно упростить, если заметить, что новый элемент к списку можно добавлять сразу при запросе памяти:
ReadLn(a);
new(first); {запрашиваем память под элемент}
first Апит:=а; {заносим число в информационное поле} f:-Jirst; {f - текущий элемент, после которого добавляется
следующий}
while not EOF do begin
ReadLn(a);
new(f\p); {запрашиваем память под элемент} f:=fA>p; {теперь новый элемент стал последним} fA.num:=a; {заносим число в информационное поле} end;
f\p:-nil; {в поле «адрес следующего» последнего элемента записываем nil}
Пример 7.4. Разработать программу, которая строит список, сортированный по возрастанию элементов, из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации CTRL-Z (конец файла на устройстве ввода).
Список сортирован, соответственно, добавляя элемент, необходимо сохранить закон сортировки: элемент должен вставляться перед первым элементом, который больше, чем добавляемый. В зависимости от конкретных данных он может вставляться в начало, середину и конец списка.
new(first); {запрашиваем память под первый элемент}
ReadLn(first Апит); {заносим число в информационное поле} firstAp:=nil; while not EOF do begin
new(q); {создаем элемент}
ReadLn(q\num); {заносим значение} if qAnum<firstAnum then {если элемент меньше первого
элемента списка, то}
begin {вставляем перед первым}
qA.p:=first; first: =q;
end
else {иначе вставляем в середину или конец}
begin
n:=first; {указатель на текущий элемент} f:=first; {указатель на предыдущий элемент} flag:=false; {"элемент не вставлен"} {цикл поиска места вставки} while (nA.ponil) and (not flag) do begin
n:=nA.p; {переходим к следующему элементу} if qAnum<nAnum then {место найдено} begin {вставляем в середину} qAp:=fAp;
flag:=true; {"элемент вставлен"} end
else f:=n; {сохраняем адрес текущего элемента} end;
if not flag then {если элемент не вставлен, то} begin {вставляем после последнего}
qA.p:-nil; fAp:=q; end;
end;
end;
Просмотр и обработка элементов списка. Просмотр и обработка элементов списка выполняется последовательно с использованием дополнительного указателя:
f—first; while fonil do begin
<обработка элемента по адресу f> end; ...
В качестве примера рассмотрим вывод на экран элементов списка:
f:=first;
while fonil do begin
WriteLn(fA.num,' ');
f:=fA-P; end; ...
Поиск элемента в списке. Поиск элементов в списке также выполняется последовательно, но при этом, как это и положено в поисковом цикле, обычно организуют выход из цикла, если нужный элемент найден, и осуществляют проверку после цикла, был ли найден элемент:
f:=first;
flag:-false;
while (fonil) and (not flag) do begin
if fA пит =k then flag: =not flag else f:=f A.p;
end;
if flag then <элемент найден>
else <элемент не найден>; ...
Удаление элемента из списка. При выполнении операции удаления также возможно четыре случая:
• удаление единственного элемента;
• удаление первого (не единственного) элемента списка;
• удаление элемента, следующего за данным;
• удаление последнего элемента.
Удаление единственного элемента. После удаления единственного элемента список становится пустым, следовательно при выполнении этой операции необходимо не только освободить память, выделенную для размещения элемента, но и занести nil в указатель списка first (рис. 7.14):
| |
| |
f:=firstAp; {сохраняем адрес следующего элемента} Dispose(first); {освобождаем память}
first: =/• ... {заносим в указатель списка адрес следующего
элемента}
Удаление единственного элемента и первого элемента в программе можно объединить:
q —first; first: =firstA.p; Dispose(q);...
Удаление элемента, следующего за данным (не последнего). Удаление элемента, следующего за данным, требует запоминания адреса удаляемого элемента, изменения адресной части данного элемента и освобождения памяти (рис. 7.16).
n:=fAp; {сохраняем адрес удаляемого элемента} fA.p:=nA.p; {заносим в адресное поле предыдущего элемента адрес следующего элемента} Dispose(n); ... {освобождаем память}
| |
Удаление последнего элемента. Удаление последнего элемента отличается только тем, что в поле «адрес следующего» заданного элемента записывается константа nil:
n:=fA.p;
fAp:=nil;
Dispose(п); ...
Удаление последнего элемента можно свести к удалению элемента, следующего за данным, так как адресная часть удаляемого элемента равна nil.
Комбинируя приемы удаления, мы также можем организовать любую дисциплину удаления.
Пример 7.5. Разработать программу, которая удаляет из списка все элементы меньше заданного значения к.
Удаляемые значения могут располагаться в списке на любом месте, следовательно, возможны все четыре варианта удаления элемента, которые сводятся к двум случаям:
• удаление единственного элемента и удаление записей из начала списка-удаление из начала списка;
• удаление средних и последнего элементов - удаление не из начала списка. Для разделения этих двух случаев введем специальный признак «удаление из начала», который в начале установим равным true, а затем, как только в списке будет оставлен хотя бы один элемент - изменим на false.
п:-first;
nft:=true; {признак «удаление из начала списка»} repeat
if пА.пит<к then begin
if nft then {если «удаление из начала списка»} begin {удаление из начала списка} q:=first; first:=firstA.p; Dispose(q);
n:=first; {переходим к следующему элементу} end
else {иначе}
begin {удаление из середины и конца} q:=n;
n:=n^.р; {переходим к следующему элементу} Dispose(q); f\p:=n;
end
end
else {оставляем элемент в списке} begin
f:=n; {устанавливаем адрес предыдущего элемента}
п:-п\р; {переходим к следующему элементу} nft:=not nft {«удаление не из начала списка»} end;
until n-nil;... {до завершения списка}
0 коммент.:
Отправить комментарий