Конспект по теме: Динамические структуры. Линейные списки.
Учитель информатики Батракова Л.В.
Динамические структуры
Определение: Данные динамической структуры – это данные, внутреннее строение которых формируется по какому-либо закону, но количество элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы, согласно закону формирования.
К данным динамической структуры относят файлы, несвязанные и связанные динамические данные.
Заметим, что файлы в данной классификации отнесены к динамическим структурам данных. Это сделано исходя из вышеприведенного определения. Хотя удаление и вставка элементов в середину файла не допускается, зато длина файла в процессе работы программы может изменяться – увеличиваться или уменьшаться до нуля. А это уже динамическое свойство файла как структуры данных.
Линейные списки (однонаправленные цепочки)
Определение: Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Каждый элемент связанного списка, во-первых, хранит какую-либо информацию, во-вторых, указывает на следующий за ним элемент. Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.
Лишь на самый первый элемент списка (голову) имеется отдельный указатель. Последний элемент списка никуда не указывает.
Описание списка
Type ukazat= ^ S;
S= record
Inf: integer;
Next: ukazat;
End;
В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.
Формирование списка
Чтобы список существовал, надо определить указатель на его начало.
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
End;
Создадим первый элемент списка:
New (u); {выделяем место в памяти}
u^.Next:= nil; {указатель пуст}
u^.Inf:=3;
Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.
А) Добавление элемента в голову списка. Для этого необходимо выполнить последовательность действий:
добавить указатель для нового элемента;
получить память для нового элемента;
поместить туда информацию;
присоединить элемент к голове списка.
New(x);
Readln(x^.Inf);
x^.Next:=u;
u:=x;
Б) Добавление элемента в конец списка. Для этого введем еще один указатель, который будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост).
x:= hv;
New( x^. next); {выделяем память для следующего элемента}
x:= x^.next;
x^.next:= nil;
x^. inf:= 5;
hv:=x;
Просмотр списка
While u<> nil do
Begin
Writeln (u^.inf);
u:= u^.next;
end;
Удаление элемента из списка
А) Удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель.
x:= u;
u:= u^.next;
dispose(x);
Б) Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.
x:= u;
while ( x<> nil) and ( x^. inf<> digit) do
begin
dx:= x;
x:= x^.next;
end;
dx:= x^.next:
dispose(x);
В) Удаление из конца списка. Для этого нужно найти предпоследний элемент.
x:= u; dx:= u;
while x^.next<> nil do
begin
dx:= x; x:= x^.next;
end;
dx^.next:= nil;
dispose(x);
Прохождение списка
Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму элементов списка.
summa:= 0;
x:= u;
while x<> nil do
begin
summa:= summa+ x^.inf;
x:= x^.next;
end;
Пример: Создать динамический список, вывести его содержимое на экран, добавить новые компоненты и удалить первый элемент, стоящий за значением, равным 3.
uses crt;
type ref=^elem;
elem=record
date:integer;
next:ref
end;
var p,q:ref;
i:integer;
procedure newlist(var p:ref); {создание списка}
var q:ref;
i:integer;
begin p:=nil;
writeln('input i or -1');
readln(i);
while i<>-1 do
begin new(q);
q^.date:=i;
q^.next:=p;
p:=q;
readln(i);
end;
end;
procedure print(p:ref); {вывод содержимого списка на экран}
var q:ref;
begin q:=p;
while q<>nil do
begin write(q^.date,' ');
q:=q^.next
end;
writeln
end;
procedure insert2(p:ref); {вставка новых компонент в конец списка}
var q,l,k:ref;
i:integer;
begin q:=p;
while q<>nil do
begin l:=q;
q:=q^.next
end;
writeln('input i or -1');
readln(i);
while i<>-1 do
begin new(k);
k^.date:=i;
k^.next:=q;
l^.next:=k;
q:=l^.next;
readln(i);
end;
end;
procedure delete2(p:ref); {удаление компоненты из списка}
var q:ref;
begin if p^.next<>nil then
begin q:=p^.next;
p^.next:=p^.next^.next;
dispose(q)
end;
end;
begin clrscr;
newlist(p);
print(p);
insert2(p);
print(p);
q:=p;
while (q^.date<>3) and(q^.next<>nil) do q:=q^.next;
delete2(q);
print(p);
end.
Выводы
Однонаправленный список - простая динамическая структура данных, каждый элемент которой содержит в себе ссылку (адрес) на следующий элемент.
Для хранения однонаправленного списка достаточно хранить в статической памяти только одну переменную – указатель на первый элемент списка.
Основные действия по обработке однонаправленного списка – последовательный просмотр всех элементов списка, добавление иудаление элементов списка в указанном месте.
Однонаправленный список эффективно использовать при частой вставке / добавлении элементов, при неизвестном заранее их количестве.
Задача 1:
Создать линейный однонаправленный динамический список, вывести его содержимое на экран, добавить новые компоненты и удалить все элементы, равные 3. Если таких элементов нет, то вывести об этом сообщение, если есть, то вывести получившийся список.
Задача 2:
Создать линейный однонаправленный динамический список. Значения элементов задать случайным образом (через Random). Вывести его содержимое на экран, найти максимальный элемент и поместить его в конец списка. Если максимальных элементов несколько, то оставить только один, а остальные удалить. Получившийся список вывести на экран.
Двунаправленные списки
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.
Type u= ^S;
S= record
Inf: integer;
Next: u;
Pred: u;
End;
Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:
  Заглавное звено
Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
В программировании двунаправленные списки часто обобщают следующим образом: в качестве значения поля Next последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Pred заглавного звена – ссылку на последнее звено:
 
Заглавное звено
Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
Над двунаправленными списками определены те же операции, что и над однонаправленными:
создание списка
вставка звена
удаление звена
поиск элемента в звене.
Как работают эти операции, можно увидеть на примерах приведенных ниже.
Пример 1: Создается динамический двунаправленный кольцевой список, выводится его содержимое на экран, добавляются новые компоненты и удаляется первый элемент, равный 3.
uses crt;
type ref=^elem;
elem=record
pred:ref;
next:ref;
date:integer;
end;
var p,ring:ref; d:integer;
procedure insertl(d:integer; p:ref); {Процедура создания двунаправленного списка}
var q:ref;
begin new(q);
q^.date:=d;
q^.next:=p^.next;
q^.pred:=p^.next^.pred;
p^.next^.pred:=q;
p^.next:=q
end;
procedure deletel( p:ref); {Процедура удаления звена из списка}
begin p^.next^.pred:=p^.pred;
p^.pred^.next:=p^.next;
dispose(p);
end;
begin new(p);
p^.next:=p;
p^.pred:=p;
ring:=p;
writeln('Ввод элементов списка');
writeln('Введите d or -1');
readln(d);
while d<>-1 do
begin insertl(d,ring^.pred);
readln(d);
end;
Writeln('Вывод созданного списка');
p:=ring^.next;
while p<> ring do
begin write(p^.date:3);
p:=p^.next;
end;
writeln;
ring:=p;
writeln('Добавление новых звеньев в список');
writeln('Введите d or -1');
readln(d);
while d<>-1 do
begin insertl(d,ring^.pred);
readln(d);
end;
Writeln('Вывод дополненного списка');
p:=ring^.next;
while p<> ring do
begin write(p^.date:3);
p:=p^.next;
end;
writeln;
p:=ring^.next;
while (p<> ring)and (p^.date<>3) do
p:=p^.next;
deletel(p);
Writeln('Вывод списка после удаления звена');
p:=ring^.next;
while p<> ring do
begin write(p^.date:3);
p:=p^.next;
end;
writeln;
end.
Пример 2: Функция, которая находит нужный элемент в двунаправленном списке.
Здесь ring – ссылка на заглавное звено списка; t – ссылка на звено с искомым элементом; d – искомый элемент.
function poisk(ring:ref; d:integer; var t:ref):boolean;
var p,q:ref;
b:boolean;
begin b:=false;
p:=ring;
t:=nil;
q:=p^.next;
while (p<>q) and not b do
begin if q^.date=d then begin b:=true; t:=q; end;
q:=q^.next;
end;
poisk:=b
end;
Пример 3: Процедура, которая печатает список в обратном порядке.
procedure printl2( p:ref);
var q:ref;
begin q:=p^.pred; {Указатель на последнее звено}
while q<>p do
begin writeln(q^.date);
q:=q^.pred;
end;
end;
Задание 1: Написать программу, которая создает двунаправленный список, добавляет в него элементы, удаляет все звенья с заданным значением. Все действия сопровождать выводом списка.
Задание 2: Написать программу, которая создает числовой двунаправленный список и находит в нем максимальное значение.
|
