Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.3 Динамические структуры данных

____________________________________________________________________

begin

p^.next:= pCurrent^.next; { в новом элементе делаем ссылку на следующий элемент, который был до вставки} pCurrent^.next:= p; {в текущем элементе делаем

ссылку на новый}

end;

pCurrent:= p; // текущим становится новый элемент

end;

Функция поиска элемента в списке просто проходит все элементы списка по ссылкам от начала до тех пор, пока не будет найден искомый элемент.

function Search_MyList(Elem: integer;

var pHead: PMyList): boolean;

var

p: PMyList; begin

if pHead <> nil then p:= pHead

else begin

writeln(UTF8ToConsole('Список пуст'));

exit;

end;

Search_MyList:= false;

while true do

begin

if p^.data = Elem then

begin

366

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Search_MyList:= true; break;

end else

if p^.next = nil then break; p:= p^.next;

end;

end;

Функция возвращает true, если требуемый элемент найден.

Процедура удаления элемента из списка:

procedure Delete_MyList(Elem: integer;

var pHead, pCurrent: PMyList);

var

p: PMyList;

pPrev: PMyList; // предыдущий элемент списка find: boolean;

begin

if pHead <> nil then p:= pHead

else begin

writeln(UTF8ToConsole('Список пуст'));

exit;

end;

find:= false;

while true do

begin

if p^.data = Elem then

367

4.3 Динамические структуры данных

____________________________________________________________________

begin // если удаляется не первый элемент

pPrev^.next:= p^.next; { в предыдущем элементе заменяем ссылку на следующий элемент после удаляемого }

Dispose(p);

pCurrent:= pPrev; // текущим делаем предыдущий элемент

end;

writeln(UTF8ToConsole('Элемент успешно удален'));

end

else writeln(UTF8ToConsole('Элемент не найден'));

end;

Процедура, прежде чем удалить элемент, должна его найти. Эта часть сов-

368

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

падает с функцией поиска. Поскольку код функции поиска небольшой, мы вставили в процедуру непосредственно сам код. В принципе, в процедуре мож-

но вызвать функцию поиска. Для этого необходимо видоизменить функцию та-

ким образом, чтобы она возвращала ссылку на найденный элемент. Если эле-

мента нет, она должна возвращать nil. Предоставляем изменить функцию поис-

ка самому читателю.

Напишем главную программу работы со списком (не забудьте включить в программу процедуры и функции, которые мы только что разобрали):

program operation_list; {$mode objfpc}{$H+} uses

CRT, FileUtil; type

PMyList = ^TMyList; TMyList = record data: integer; next: PMyList; end;

var

pHead, pCurrent: PMyList; Elem, choose: integer;

{Сюда добавьте процедуры и функции, реализующие стандартные операции с линейными списками }

begin

pHead:= nil;

pCurrent:= nil;

repeat

writeln(UTF8ToConsole('Выберите нужное действие:'));

369

4.3 Динамические структуры данных

____________________________________________________________________

writeln(UTF8ToConsole('1-ввод элемента списка')); writeln(UTF8ToConsole('2-поиск элемента списка')); writeln(UTF8ToConsole('3-удаление элемента списка')); writeln(UTF8ToConsole('4-просмотр всего списка')); writeln(UTF8ToConsole('5-выход из программы')); readln(choose);

case choose of

1: begin {ввод элемента списка} writeln(UTF8ToConsole('Введите элемент списка')); readln(Elem);

Insert_MyList(Elem, pHead, pCurrent); end;

2: begin {поиск элемента списка}

writeln(UTF8ToConsole('введите искомый элемент'));

readln(Elem);

if Search_MyList(Elem, pHead)then

writeln(UTF8ToConsole('Элемент найден'))

else

writeln(UTF8ToConsole('Элемент не найден')); end;

3: begin {удаление элемента списка} writeln(UTF8ToConsole('введите элемент')); readln(Elem);

Delete_MyList(Elem, pHead, pCurrent); end;

4: begin {Вывод списка на экран}

writeln(UTF8ToConsole('Элементы списка:'));

writeln;

370