Как сделать список в паскале

Добавил пользователь Алексей Ф.
Обновлено: 04.10.2024

Давай переделаем структуру программы. Очень уж тяжело воспринимать смешение интерфейса (меню) и реализации структуры.
1. Создай новый файл.
2. В нем реализуй меню по образцу

3. Реализуй все процедуры, которые упоминаются в меню. Если какие-то вызывают временное затруднение, то сделай заглушки (только опиши заголовки процедур и их begin-end).
Так тебе будет легче работать и отлаживать.
Кроме того, для облегчения жизни, можно сделать ещё один трюк. Опиши типы своего списка следующим образом:

Для чего? Так можно на время отладки списка заменить TInfo на integer и отладить без ввода множества символов (в Stud). А после отладки на "кошках" перейти к сложным типам.
-------------
И ещё. Постарайся избежать глобальных переменных в процедурах. Это с первого взгляда они упрощают жизнь (не нужно объявлять переменные) - потом не сможешь понять, где изменилась нужная переменная и откуда ошибки.
--------------
Только так. Искать ошибку в коде из поста №1 слишком тяжело.

На этом шаге мы рассмотрим однонаправленные списки .

Под списком мы будем понимать конечный упорядоченный набор объектов произвольных размера и природы.

Связанные списки используются в двух основных случаях.
Во-первых, при создании в оперативной памяти набора данных, размер которого заранее неизвестен. Если заранее известно, какого размера память потребуется для решения задачи, то можно использовать массив. Однако, если действительный размер списка неизвестен, то применяют связанный список.
Во-вторых, связанные списки используются в базах данных. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего дискового файла. По этим причинам связанные списки широко используются в программах по управлению базами данных.

Связанные списки могут иметь одиночные или двойные связи.

Список с одной связью ( однонаправленный список ) содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью ( двунаправленный список ) каждый элемент имеет связь, как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависимости от решаемой задачи.

Однонаправленные списки

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

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

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

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

Рассмотрим схематичное изображение однонаправленного списка:

Рис.1. Схематичное изображение однонаправленного списка без заглавного звена

начальное формирование списка (запись первой компоненты);
добавление компоненты в конец списка;
определение первого элемента в линейном списке;
чтение компоненты с заданным ключом; с заданным свойством;
вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
исключение компоненты с заданным ключом из списка.
упорядочивание узлов линейного списка в определенном порядке.

Описание компоненты однонаправленного списка дадим следующим образом:

Для формирования однонаправленного списка и работы с ним необходимо описать четыре переменных типа указатель на запись. Договоримся, что pBegin определяет начало списка, а pCKey, pPredRec, pAux определим как вспомогательные (указатель на компоненту с заданным ключем, указатель на компоненту перед заданным ключем, временный указатель):

На следующем шаге мы рассмотрим формирование списка с сохранением порядка поступающих элементов .

Цель: изучение фундаментальной абстрактной структуры - связных списков.

На сегодняшнем занятии мы рассмотрим фундаментальную абстрактную структуру связанный список.

Связанный список - это набор последовательно организованных данных.
Связные списки определены как примитивы в некоторых языках программирования (в частности в Лиспе, 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.

Следующий вид списков - это циклические списки. Циклический список - это список последний элемент, которого указывает на первый. Этот список позволяет программе снова и снова просматривать список по кругу до тех пор, пока в этом есть необходимость.

В качестве примера, мы рассмотрим так называемую "проблему Джозефа". Она состоит в следующем: представьте себе, что N человек решили совершить массовое самоубийство, выстраивая себя в круг и убивая каждого М-го человека и постепенно сужая круг. Надо найти человека, который умрет последним (хотя возможно под конец он изменит свое мнение по этому вопросу), или, по-другому, найти порядок смерти этих людей. Например, если N=9 и М=5, то люди будут убиты в следующем порядке: 5 1 7 4 3 6 9 2 8. Данная программа читает значения N и M, и затем распечатывает этот порядок.

Эта программа использует циклический связанный список для прямого симулирования порядка совершения самоубийств. Сперва создается список с ключами от 1 до N: переменная head указывает на начало списка в процессе его создания, а затем программа делает чтобы последний элемент в списке указывал на head. Затем программа проходит по этому циклическому списку, пропуская M-1 элементом и уничтожая следующий после них узел до тех пор, пока в списке не останется один единственный элемент (который указывает на себя самого).

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

Итак, на сегодняшнем занятии мы рассмотрели ссылки и указатели, линейные и циклические списки

Что такое список -- знают все из повседневной жизни. Это лист бумаги, который содержит пункты, например, того, что нужно купить в магазине. Аналога связного списка [1] в жизни нет. С большой натяжкой связным списком в жизни можно назвать алгоритм схемы в виде блок-схем [2] . В блок-схемах каждый последующий блок, связан с предыдущим. но в блок-схемам могут быть побочные связи, а в связных списках их нет.

Связный список, как и блок-схема, в каждом элементе списка содержит полезную информацию, и также содержит служебную информацию. Эта информация, может быть представлена указателем на следующий элемент, точно такой же по структуре. Такой список называется односвязным. Может быть в элементе указатель на предыдущую структуру. Такой список называется двусвязным. Могут быть ещё какие-то указатели на совсем другие структуры, по необходимости.

При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже [3] .

Задача создания двусвязного списка разбивается на несколько простых подзадач.

Для начала создадим тип данных, соответствующей нашей задаче -- элемент двусвязного списка . Примерный код представлен ниже:

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

Элемент двусвязного списка не является указателем на запись, т. к. с применённым подходом нельзя было бы использовать указателя на тип "указатель на запись" (т.е. на самого себя).

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

Пример такого списка:

Как видно из примера, управляющая структура совсем короткая. Даже короче, чем элемент двусвязного списка. Сам тип TDblList определён через указатель на структуру, поэтому переменную такого типа, можно создать динамически, что позволит сократить объём программы в виде исполняемого файла.

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

В этом методе используется ссылки на пользовательский тип "TDblList". Происходит принудительное обнуление длины списка, и присвоение указателям значения "NIL" ("НИЧЕГО"). Это специальная переменная, для указания того, что здесь "пустота" [4] .

Вставку нового элемента в список рационально (но не обязательно) реализовать в форме метода объекта. Представленный вариант ниже вставляет новый элемент только в конец списка. Для включения элемента в произвольное место, необходимо в объект TDblList свойство "cur"("current", "текущий"). Оно как раз и будет указателем на то место, куда вставлять. Предлагается такой вариант списка выполнить самостоятельно.

Работа с указателями в Компонентном Паскале упрощена до предела [5] . Если в предыдущих вариантах Паскаля (или даже во вполне современном FreePascal) использовалась специальная семантика для работы с указателями, то сейчас она изъята из языка, как излишняя. Ведь тип переменной известен точно [6] . Во входных параметрах метода указана переменная "v". Она вместе с созданием нового элемента присваивает значение новому элементу. В конце метода выводится контрольная строка, что элемент действительно вставлен.

Удаление элемента из списка опасно тем, что может разорвать цепочку, и если её не срастить -- указатель будет висеть в никуда.

Удалять элементы проще, чем вставлять, так как не приходится думать об удалённом элементе. Но в любом случае, надо контролировать ссылки.

Метод будет реализован с помощью цикла FOR. Необходим только для первоначального заполнения списка.

В приведённом методе происходит заполнение списка 15 элементами.

Удаление будет производиться с конца списка, так как это заложено в алгоритме работы списка. После удаления, будет выведен список оставшихся элементов.

Внутри метода первый цикл можно заменить на REPEAT. UNTIL. А вот со вторым использовать не получится, так как последний элемент имеющий признак "el.last" не будет выведен на экран.

Это процедура является завершающей, и включает в себя всю последовательность вызовов методов.

Последовательные вызовы приводят к созданию списка, его заполнению, затем удалению пяти элементов.

Текст модуля достаточно разобран выше, текст приводится без комментариев. Рекомендуется самостоятельно разобраться в деталях реализации.

Если программа набрана правильно, то должен быть получен следующий вывод:

Приведённый пример является простейшим. В нём не хватает нескольких методов для доступа к произвольному элементу (на самом деле, здесь бы хватило и фиксированного массива указателей). Кроме того, нельзя удалять элементы из середины списка. Но данный учебный пример позволяет понять как это сделать, и пример можно взять за основу для своих решений. Ещё раз хотелось бы остановиться на эффективности использования памяти в приведённом примере -- очень не эффективно. Структуры данных надо проектировать тщательно, особенно когда дело касается большого массива данных.

Читайте также: