Использование указателей для организации связанных списков

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

 

Одно из полей каждого объекта связанного списка имеет тип указатель и указывает на очередной объект в списке. Указатель на первый объект содержится в переменной First, а последний объект имеет указатель на Nil.

Пример программы создания и использования связанного списка

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

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

Program point;

Uses Crt;

Type

NameStr = String [20];

Link = ^Auto;

Auto = record

Name: NameStr; {Марка автомобиля}

Speed: real; {Скорость}

Next: Link; {Поле для связи со следующим объектом в списке}

end;

Var

Р,First: Link; {Указатели на запись: текущую, первую}

NamFind: NameStr; {Марка автомобиля для поиска}

V: 0..4; {Селектор меню}

EndMenu: boolean; {Окончание вывода меню}

{Поиск объекта с именем FN, по результатам поиска возвращает указатель на найденный объект или Nil, если объект не найден}

Function FindName(FN:NameStr): Link;

Var

Curr: Link;

begin

Curr:=First; {Установить указатель на первом объекте в списке }

{Повторять пока не дойдем до конца списка}

while Curr <> Nil do

if Curr^.Name=FN then {Если нашли заданный объект}

begin

FindName:=Curr; {Возвращаем значение указателя на него}

Exit; {Завершаем функцию}

end

else

Curr:=Curr^.Next; {Перейти к следующей записи}

FindName:=Nil; {В списке нет искомого объекта}

end; {Конец FindName}

{Добавление записи первой в связанный список}

procedure AddFirst(A:Link);

begin

A^. Next:=First; {Новый объект первый в списке}

First:=А; {Голова списка ссылается на новый объект}

end; {Конец AddFirst}

{Удаление первого объекта из списка}

procedure DelFirst(var A:Link);

begin

A:=First;

First:=First^. Next; {Теперь First указывает на тот объект, на который ранее ссылался объект А}

end; {Конец DelFirst}

{Удаление из списка объекта, стоящего после объекта Old}

procedure DelAfter(Old:Link; var A:Link);

begin

A:=Old^.Next; {Переменной А присваивается значение указателя на удаляемый объект}

Old^.Next:=Old^.Next^.Next; {Теперь Old указывает на тот объект, на который ранее ссылался следующий за ним объект, а объект А исключен из связанного списка}

end; {Конец DelAfter}

{Ввести данные об объекте}

procedure InpAvto;

begin

P:=New(Link); {Создать очередной объект типа Auto}

Write('Введите марку автомобиля:');

Readln(P^.Name);

Write('Максимальная скорость:');

Readln(Р^.Speed);

AddFirst(Р); {Вызов процедуры добавления записи, на которую ссылается указатель Р (Р- фактический параметр, А - формальный параметр-значение) }

end; {Конец InpAvto}

{Вывести на экран все объекты из связанного списка}

procedure MyList;

var

Curr: Link; {Локальная переменная - указатель на очередной объект}

begin

Curr:=First; {Установить указатель на первом объекте в списке}

{Повторять, пока не дойдем до конца списка}

while Curr <> Nil do

begin

Writeln('Марка: ', Curr^. Name,' скорость: ', Curr^. Speed);

Curr:=Curr^.Next; {Перейти к очередному объекту связанного списка}

end;

Write('Вывод списка окончен. Нажмите Enter');

Readln;

end; {Конец MyList}

Begin {Основная программа}

New(P); {Создать новую динамическую переменную и установить на нее переменную-указатель}

EndMenu:=False;

repeat {Очищать экран и выводить меню до тех пор, пока EndMenu<>True}

CIrScr;

Writeln('Укажите вид работы:');

Writein('1. Запись первым в список');

Writeln('2. Удаление первого объекта из списка');

Writein('3. Просмотр всего списка');

Writein('4. Удаление объекта, следующего в списке за указанным');

Writein('0. Окончание работы');

Readin(V);

Case V of {Вызов разных процедур в зависимости от выбора пункта меню}

1: InpAvto; {Ввод данных об объекте}

2: DelFirst(P); {Удаление первого в списке}

3: MyList; {Вывод списка всех элементов связанного списка}

4: begin {Удаление объекта, следующего за указанным}

Write('Введите марку автомобиля, за которым следует удаляемый из списка:');

Readln(NamFind);

DelAfter(FindHame(NamFind),P); {Вызов процедуры

DelAfter с параметрами: функцией FindName(NamFind) и указателем Р}

end

else

EndMenu:=True; {Завершить вывод меню}

end;

until EndMenu; {Если EndMenu=True, то завершить вывод меню на экран}

Dispose(Р); {Уничтожить динамическую переменную Р и освободить память в куче}

end.

Порядок выполнения работы

1. Изучить теоретические сведения по теме ” Разработка программы создания связанного списка”.

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

3. Показать работающую программу преподавателю.

4. Ответить на контрольные вопросы.

Контрольные вопросы

1. Связанные списки.

2. Применение указателей для организации связанных списков.

 

Лабораторная работа № 34