Ссылки и указатели. Линейные и циклические
списки
Цель: изучение фундаментальной абстрактной
структуры - связных списков.
На сегодняшнем занятии мы рассмотрим
фундаментальную абстрактную структуру
связанный список.
Связанный список - это набор последовательно
организованных данных.
Связные списки определены как примитивы в
некоторых языках программирования (в частности в
Лиспе, Delphi), но не в Паскале. Однако Паскаль
предоставляет некоторые базовые примитивные
операции позволяющие легко использовать
связанные списки.
Главное преимущество связанных списков перед
массивами состоит в том, что они могут уменьшать
или увеличивать свои размеры во время выполнения
программы. В частности, мы не должны заранее
знать его максимальный размер.
Второе преимущество состоит в том, что они
обеспечивают гибкость при переорганизации их
элементов. Такая гибкость получается за счет
потери в скорости доступа к произвольному
элементу списка. Это станет более очевидным ниже,
после того, как мы ознакомимся с некоторыми
основными свойствами связанных списков и
базовыми операциями определенными над ними.
Список можно представить в виде звеньев цепи.
В массиве последовательная
организация обеспечивается непосредственно (согласно
индексу).
Для связанного списка используется
специальный способ организации данных, согласно
которому его элемент содержится в "узле"
содержащем данные, а также "ссылку" на
следующий "узел".
Узел и ссылку можно описать так:
Type
Link = ^Node;
Node = record
Data: integer;
Next: Link;
End;
Для описания списка мы будем использовать
дополнительно два вспомогательных узла head и z.
Узел head будет указывать на первый элемент списка,
а z - последний элемент списка. Head иногда называют
"голова" списка, а z - "хвост".
Тогда список можно будет представить в
следующем виде.
Такое представление данных позволяет
производить некоторые операции гораздо более
эффективными методами, чем над массивами.
Например, если мы хотим передвинуть элемент 1 из
конца в начало, то для произведения такой
операции в массиве нам потребовалось бы
передвинуть все его элементы чтобы освободить
место. В связанном же списке мы только меняем
ссылки. Оба варианта рисунка эквивалентны; они
только по разному нарисованы. Мы просто
переустанавливаем ссылку узла, содержащего 1, на
узел содержащий 2, а ссылку пустого узла head на
узел содержащий 1. Даже если бы список был очень
большой, то нам все равно потребовалось бы только
три перестановки ссылок для подобного обмена.
Что более важно, теперь мы можем
говорить о "вставке" элемента в связанный
список (что увеличивает его длину на один элемент)
- операции которая столь неестественна и
неудобна на массивах. На рисунке показано как
вставить в список новый узел. Нужно вначале
добавить этот узел, затем создать ссылку на узел
q, а затем изменить ссылку узла p на новый узел. Для
этого требуется изменить лишь две ссылки в
независимости от длины списка.
Аналогично, мы можем вести речь об "удалении"
элемента из списка (что уменьшает его размер на
один элемент). Нужно просто переставить ссылку на
узел, который следует за узлом q и после этого
узел содержащий q должен быть уничтожен.
С другой стороны, есть и операции для
которых связанный список не очень хорошо
подходит. Наиболее очевидная из них - это "найти
k-й элемент" (найти элемент по его индексу): в
массиве это делалось простым обращением типа a[k],
но в связанном списке мы должны пройти по k
ссылкам.
Другой неестественной операцией над
связанными списками является операция "найти
элемент перед заданным". Если все, что у на есть
- это ссылка на элемент q в нашем примере, то
единственный способ найти элемент p, который
указывает на q - это пройти по всем ссылкам
начиная с узла head. На самом деле - эта операция
необходима для удаления заданного элемента из
списка: как же иначе мы можем переустановить
ссылку предыдущего узла ? Во многих задачах, мы
можем обойти эту проблему посредством изменения
формулировки этой фундаментальной операции на
"удалить узел следующий после данного".
Аналогичная проблема может быть обойдена и для
вставки посредством изменения определения
операции на "вставить элемент после заданного
узла".
Паскаль предоставляет нам некоторые
примитивные операции которые позволяют нам
непосредственно создавать связанные списки.
Следующий фрагмент кода - это пример реализации
основных функций, которые мы только что
обсуждали.
Type
Link = ^Node;
Node = record
Data: integer;
Next: Link;
End;
Var
Head, z: link;
procedure list_initialize;
begin
new( head );
new( z );
head^.next := z;
z^.next := nil;
end;
procedure insert_after( v : integer; t : link );
var
x : link;
begin
new(x);
x^.data := v;
x^.next := t^.next;
t^.next := x;
end;
procedure delete_next( t : link );
var
del: link;
begin
del := t^.next;
t^.next := t^.next^.next;
dispose(del);
end;
Давайте рассмотрим их по подробнее.
Link = ^Node; - здесь создается новый тип Link,
который является типизированным указателем на
тип Node. Тип Node представлен ниже.
Указатель - это переменная целого типа, которая
интерпретируется как адрес байта памяти,
содержащий некоторый элемент данных.
Давайте поподробней разберем это определение.
Память компьютера можно представить в
следующем виде. Она разбита на блоки каждый такой
блок называется сегментом. В Dos номер каждого
сегмента может содержать максимум 16 бит(число
$FFFF, когда все биты равны
1)(символ $ - это знак шестнадцатеричной
системы исчисления) , т.е. любой сегмент может
иметь номер [0; $FFFF]. Предположим, что мы
рассматриваем участок памяти с сегментами $592B,
$592C, $592D. Чтобы найти конкретную ячейку памяти
внутри каждого сегмента есть так называемое
смещение, которое тоже может иметь номер [0; $FFFF]. К
примеру пусть смещение внутри сегмента $592C будет
$B401, тогда указатель на эту ячейку памяти будет
иметь значение $592CB401.
procedure list_initialize;
new( head ); - процедура new создает новую
динамическую переменную типа node и устанавливает
значение переменной head таким образом, чтобы оно
указывало на эту новую динамическую переменную,
т.е. программа ищет в памяти свободный участок
длиной 6($6) байт(запись node имеет два типа integer(2
байта) и pointer(4 байта)). Как только она его находит
она резервирует этот участок, т.е. объявляет этот
участок памяти занятым и другие переменные уже
не могут размещать там информацию. Затем
программа присваивает переменной head адрес этого
свободного участка. Пусть программа нашла
свободный участок памяти начиная с адреса $592CB401 и
присвоила этот номер переменной head.
new( z ) - пусть программа нашла участок
памяти со следующим адресом $592D000A и присвоила его
z.
Как же происходит обращение к содержимому
адреса памяти? С помощью оператора ^. К примеру,
head^.key:=10; Что здесь происходит? Мы заносим в
содержимое ячейки $592CB401, а конкретней в первые 2
байта (т.к. тип integer занимает 2 байта) в область
называемую key - число 10.
head^.next := z; - здесь мы заносим в ячейку
$592CB401, начиная с 3 байта(т.к. первые два заняты key) в
область называемую Next число $592D000A.
z^.next := nil - ячейку памяти адресуемую z, а
конкретней область next заполняем нулями.
procedure insert_after( v : integer; t : link );
procedure delete_next( t : link );{аналогично и см.
рис.}
Почему использование пустых узлов столь
полезно?
Во-первых, если бы мы условились держать
указатель на начало списка вместо того, чтобы
держать узел head, то процедуре вставки
потребовалась бы специальная проверка для
вставки в начало списка.
Во-вторых, соглашение о пустом узле z
предохраняет процедуру удаления от излишней
проверки на удаление из пустого списка.
А эти проверки существенно сказываются на
времени работы программы.
Выражение типа head^.next^.key дает нам
первый элемент списка, а head^. Next^.next^.key -
второй.
Давайте создадим программу обрабатывающею
информацию об автомобилях.
program car;
uses
crt;
type
namestr = string[20];
Link = ^Node;
Node = record
name: namestr;
speed: integer;
next: link;
end;
var
head, z: link;
namfind: namestr;
v: 0..4;
endmenu: boolean;
procedure list_initialize;
begin
new(head);
new(z);
head^.next:=z;
z^.next:=nil;
end;
procedure list_destroy;
begin
dispose(head);
dispose(z);
end;
procedure insert_after(name1: namestr; speed1: integer; t: link);
var
x : link;
begin
new(x);
x^.name := name1;
x^.speed:= speed1;
x^.next := t^.next;
t^.next := x;
end;
procedure delete_next(t: link);
var
del: link;
begin
del := t^.next;
t^.next := t^.next^.next;
dispose(del);
end;
procedure InpAuto;
var
nam: namestr;
sp: integer;
begin
write('Введите марку автомобиля: ');
readln(nam);
write('Максимальная скорость: ');
readln(sp);
insert_after(nam, sp, head);
end;
procedure Mylist;
var
Curr: Link;
begin
Curr:=head^.next;
While Curr^.next <> nil do
begin
writeln('Марка: ', Curr^.name, ' Скорость: ', Curr^.Speed);
curr:=curr^.next;
end;
write('Вывод списка окончен нажмите Enter.');
readln;
end;
function findname(fn: namestr): link;
var
Curr: Link;
begin
Curr:=head;
While Curr<>Nil do
if Curr^.name=fn then
begin
findname:=curr;
exit;
end
else
curr:=curr^.next;
findName:=Nil;
end;
begin
list_initialize;
endmenu:=false;
repeat
clrscr;
writeln('Укажите вид работы:');
writeln('1. Запись первым в список');
writeln('2. Удаление первого объекта из списка');
writeln('3. Просмотр всего списка');
writeln('4. Удаление объекта, следующего в списке за
указанным');
writeln('0. Окончание работы');
readln(v);
case v of
1: inpauto;
2: delete_next(head);
3: mylist;
4: begin
writeln('Введите марку автомобиля, за которым
следует удаляемый из списка');
readln(NamFind);
delete_next(FindName(namfind));
end;
else
endmenu:=true;
end;
until endmenu;
list_destroy;
end.
end;
Следующий вид списков - это циклические списки.
Циклический список - это список последний
элемент, которого указывает на первый. Этот
список позволяет программе снова и снова
просматривать список по кругу до тех пор, пока в
этом есть необходимость.
В качестве примера, мы рассмотрим так
называемую "проблему Джозефа". Она состоит в
следующем: представьте себе, что N человек решили
совершить массовое самоубийство, выстраивая
себя в круг и убивая каждого М-го человека и
постепенно сужая круг. Надо найти человека,
который умрет последним (хотя возможно под конец
он изменит свое мнение по этому вопросу), или, по-другому,
найти порядок смерти этих людей. Например, если N=9
и М=5, то люди будут убиты в следующем порядке: 5 1 7 4
3 6 9 2 8. Данная программа читает значения N и M, и
затем распечатывает этот порядок.
Эта программа использует циклический
связанный список для прямого симулирования
порядка совершения самоубийств. Сперва
создается список с ключами от 1 до N: переменная head
указывает на начало списка в процессе его
создания, а затем программа делает чтобы
последний элемент в списке указывал на head. Затем
программа проходит по этому циклическому списку,
пропуская M-1 элементом и уничтожая следующий
после них узел до тех пор, пока в списке не
останется один единственный элемент (который
указывает на себя самого).
Program Josef;
Type link=^node;
node=record
data:word;
next:link;
end;
Var N,M:word;
head:link;
Procedure Init;
Var q,l:link;
i:word;
Begin
Write('Enter N: ');
Readln(N);
New(head);
l:=head;
Head^.data:=1;
Head^.next:=head;
For i:=2 to n do
begin
New(q);
q^.data:=i;
l^.next:=q;
q^.next:=head;
l:=q;
end;
End;
Procedure Del;
Var i,k:word;
q,p:link;
Begin
Write('Enter M: ');
Readln(M);
k:=0;
i:=1;
q:=head;
While k<n-1 do
begin
While i<m-1 do
begin
inc(i);
q:=q^.next;
end;
i:=0;
inc(k);
p:=q^.next;
q^.next:=q^.next^.next;
writeln(p^.data:4);
dispose(p);
end;
Writeln('The Last: ',q^.data);
End;
Begin
Init;
Del;
readln
End.
Итак, на сегодняшнем занятии мы рассмотрели
ссылки и указатели, линейные и циклические
списки. |
