Добавление элемента в список

 Добавление элемента в список выполняется путем корректировки указателей. Для того чтобы добавить элемент в упорядоченный список, нужно сначала найти элемент, после которого требуется вставить новый. Затем следует скорректировать указатели. Указатель нового элемента нужно установить на тот элемент, на который указывает элемент, после которого добавляется новый. Указатель элемента, после которого добавляется новый элемент, установить на этот новый элемент (рис. 8.9).

Следующая программа (ее текст приведен в листинге 8.5, а диалоговое окно — на рис. 8.10)формирует список, упорядоченный по полю Фамилия. Данные вводятся в поля редактирования (Edit1и Edit2) и нажатием кнопки Добавить (Button1) добавляются в список таким образом, что список всегда упорядочен по полю Фамилия.

Листинг 8.5. Добавление элементов в упорядоченный список 

 Показать / Скрыть текст

001.unit dlist2__;

002.interface

003.uses

004.Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,Dialogs, StdCtrls;

005.type

006.TForml = class (TFonn)

007.Labell: TLabel;

008.Label2: TLabel;

009.Buttonl: TButton;

010.Button2: TButton;

011.Label3: TLabel;

012.Editl: TEdit;

013.Edit2: TEdit;

014.procedure ButtonlClickfSender: TObject);

015.procedure Button2Click(Sender: TObject);

016.procedure FormActivate(Sender: TObject);

017.private

018.{ Private declarations }

019.public

020.{Public declarations}

021.end;

022.var

023.Forml: TForrn1;

024.implementation

025.{$R -}

026.type

027.TPStudent=^TStudent; //указатель на тип TStudent

028.TStudent = record

029. 

030.f_name:string[20] ; // фамилия

031.l_name:string[20] ; // имя

032.next: TPStudent; // следующий элемент списка

033.end;

034.var

035.head: TPStudent; // начало (голова) списка

036.// добавить элемент в список

037.procedure TForml.ButtonlClickfSender: TObject);

038.Var

039.node: TPStudent; // новый узел списка

040.curr: TPStudent; // текущий узел списка

041.pre: TPStudent; // предыдущий, относительно curr, узел

042.begin

043.new (node); // создание нового элемента списка

044.node^. f_name:=Edit1. Text; // фамилия

045.node^. l_name:=Edit2. Text; // имя

046.// добавление узла в список

047.// сначала найдем в списке подходяшее место для узла

048.curr : =head;

049.pre : =NIL;

050.{

051.Внимание! Если приведенное ниже условие заменить

052.на (^node. f_name>curr^. f_name)and (curr<>NIL) ,

053.то при добавлении первого узла возникает ошибка времени

054.выполнения, т. к. curr = NIL и, следовательно,

055.переменной curr.^name нет!

056.В используемом варианте условия ошибка не возникает, т. к.

057.сначала проверяется условие (curr <> NIL), значение которого

058.FALSE, и второе условие в этом случае не проверяется.

059.}

060.while (curr о NIL) and (node. f_jiame > curr^ . f_name) do

061.begin

062.// введенное значение больше текущего

063.pre:= curr;

064.curr:=curr^.next; // к следующему узлу

065.end;

066.if pre = NIL then

067.begin

068.// новый узел В начало списка

069.node^. next: =head;

070.head: =nocie;

071.end

072.else

073.begin

074.// новый узел после pre, перед curr

075.node^. next: =pre^. next ;

076.pre^.next:=node;

077.end;

078.Edit1.text:='';

079.Edit2.text:='';

080.Edit1.SetFocus;

081.end;

082.// отобразить список

083.procedure TForm1.Button2Click(Sender: TObject);

084.var

085.curr: TPStudent; // текущий элемент списка

086.n:integer; // длина ( кол-во элементов) списка

087.st : string; // строковое представление списка

088.begin

089.n:=0;

090.curr:=head;

091.while curr <> NIL do

092.begin

093.n:=n+1;

094.st:=st-*-curr^.f_name+' '+curr^.l_name+#13;

095.curr : =curr^ . next ;

096.end;

097.if n<>0 then ShowMessage( 'Список: '+#13+st)

098.else ShowMessage ( 'В списке нет элементов.');

099.end;

100.// начало работы программы

101.procedure TForml.Formactivate(Sender: TObject);

102.begin

103.head:=NlL; // список пустой

104.end;

105.end.

 

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

Вывод списка выполняет процедура TForml.Button2Click, которая запускается нажатием кнопки Показать. После запуска программы и ввода нескольких фамилий, например, в такой последовательности: Иванов, Яковлев, Алексеев, петров, список выглядит так, как показано на рис. 8.11. 

Удаление элемента из списка. 

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

 

Поскольку узел является динамической переменной, то после исключения узла из списка занимаемая им память должна быть освобождена. Освобождение динамической памяти, или, как иногда говорят, "уничтожение переменной", выполняется вызовом процедуры dispose. У процедуры dispose один параметр — указатель на динамическую переменную. Память, занимаемая этой динамической переменной, должна быть освобождена.

Например, в программе

 Показать / Скрыть текст

var

р:^integer;

begin

new (p) ;

// инструкции программы 1

dispose(p);

end

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

 

Следующая программа позволяет добавлять и удалять узлы упорядоченного списка. Диалоговое окно программы приведено на рис. 8.13. Процедуры добавления узла в список и вывода списка, а также объявление типа узла списка ничем не отличаются от соответствующих процедур рассмотренной ранее программы Упорядоченный динамический список 2, поэтому они здесь не приводятся.

 

Удаление узла из списка выполняет процедура TForm1.ButtonSClick, которая запускается нажатием кнопки Удалить (Buttons). Текст процедуры приведен в листинге 8.6. 

Листинг 8.6. Удаление узла из списка

 Показать / Скрыть текст

01.// щелчок на кнопке Удалить

02.procedure TForml.Button3Click[Sender: TObject);

03.var

04.curr: TPStudertt; // текущий, проверяемый узел

05.pre: TPStudent; // предыдущий узел

06.foimd:boolean; // TRUE — узел, который надо удалить, есть в списке

07.begin

08.if head - NIL then

09.begin

10.MessageDlg('Список пустой!', mtError,[mbOk],0);

11.Exit;

12.end;

13.curr := head; // текущий узел — первый узел

14.pre := MIL; // предыдущего узла кет

15.found := FALSE;

16.// найти узел, который надо удалить

17.while (curr о NIL) and {not found] do

18.begin

19.if (curr^.f_name = Edit1.Text) and (curr^.l_name = Edit2.Text)

20.then found:=TRUE // нужный узел найден

21.else // к следующему узлу

22.begin

23.pre:=curr;

24.curr:=curс^.next;

25.end;

26.end;

27.if found then

28.begin

29.// нужный узел найден

30.if MessageDlg('Узел будет удален иэ списка!',

31.mtWaming, [mbOk,nibCancel] ,0| о mrYes

32.than Exit;

33.// удаляем узел

34.if pre = NIL

35.then head:=curr'.next // удаляем первый узел списка

36.else pre^.next:*curr.next;

37.Dispose(curr);

38.Message('Узел' + №13 +'Имя:'+Edit1.Text + #13 +'Фамилия;' +Edit2.Text + #13 +'удален из списка.',

39.rat Information, [rnbOk] ,0);

40.end

41.else // узла, который надо удалить, в списке нет

42.MessageDLg('Уэел' + #13 -t

43.'Имя:' + Editl.Text + #13 +

44.'Фамилия:' + Edit2.Text +#13 +

45.'в списке не найден.',

46.mtError,[mbOk],0);

47.Editl.Text:='';

48.Editl.Text:=";

49.Editl.SetFocus;

50.end;

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