Технологии программирования - Смирнов А.А

Технологии программирования, основанные на динамическом распределении памяти

Связные списки основаны на использовании типизиро- ванных указателей. Типизированные указатели связных списков используют тип RECORD. Записи связного списка содержат ука- затель на последующий соседний элемент. Последняя запись в качестве указателя содержит специальное значение “NIL”.

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

Для хранения указателя на первый элемент списка фор- мируется отдельная переменная. Как правило, она называется “FIRST”. Потеря указателя на первый элемент списка делает обращение ко всем элементам списка невозможным.

Схема организации информации в виде связного списка.

First = <Указатель на первый элемент>

При разработке в среде DELPHI программного комплек- са для обработки экономической информации с использова- нием связных списков может быть спроектирована экранная форма следующего вида:

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

Unit LISTS_U;

Interface

Uses

Windows, Messages, SysUtils, Classes, Graphics,

Controls, Forms, Dialogs,

Menus, Grids, StdCtrls;

Type

31

Технологии программирования

TListsForm = Class(TForm) MainMenuLISTS: TMainMenu; ItemCreate: TMenuItem; ItemView: TMenuItem; ItemAppend: TMenuItem; ItemSeek: TMenuItem; ItemDelete: TMenuItem; ItemInsert: TMenuItem; ItemExit: TMenuItem; LbInput: TLabel;

LbNumI: TLabel;

LbFamilyI: TLabel;

EdNumI: TEdit;

EdFamilyI: TEdit;

LbSeek: TLabel;

LbNumS: TLabel;

LbFamilyS: TLabel;

EdNumS: TEdit;

EdFamilyS: TEdit; LbList: TLabel; GridList: TStringGrid; LbMes: TLabel;

Procedure CreateClick(Sender: TObject); Procedure Activate(Sender: TObject); Procedure ItemExitClick(Sender: TObject); Procedure Seek(Sender: TObject); Procedure View(Sender: TObject); Procedure Append(Sender: TObject); procedure Delete(Sender: TObject); procedure Insert(Sender: TObject);

End;

T_Pointer=^T_Rec;{Указатель на элемент списка} T_Rec=Record

Number:Integer;{ Табельный номер} Family:String[30];{Фамилия} Next:T_Pointer;{Ссылка на следующий элемент} End;

Var

ListsForm: TListsForm;

First:T_Pointer; {Ссылка на первый элемент} Implementation

{$R *.DFM}

Procedure TListsForm.Activate(Sender: TObject); {Присвоение первоначальных значений}

32

Технологии программирования, основанные на динамическом распределении памяти

Begin

Caption:='Обработка связных списков'; LbInput.Caption:='Ввод информации о работнике'; LbInput.AutoSize:=True; LbNumI.Caption:='Табельный номер'; LbNumI.Autosize:=True;

EdNumI.Text:=''; LbFamilyI.Caption:='Фамилия И.О.'; LbFamilyI.Autosize:=True; EdFamilyI.Text:='';

LbSeek.Caption:='Поиск работника(Удаление работника)'; LbSeek.AutoSize:=True;

LbNumS.Caption:='Табельный номер'; LbNumS.Autosize:=True; EdNumS.Text:=''; LbFamilyS.Caption:='Фамилия И.О.'; LbFamilyS.Autosize:=True; LbFamilys.Visible:=False; EdFamilys.Visible:=False; LbList.Caption:='Список работников'; LbList.AutoSize:=True; LbList.Visible:=False; GridList.ColCount:=3; GridList.Cells[0,0]:='Номер п/п'; GridList.Cells[1,0]:='Табельный номер'; GridList.Cells[2,0]:='Фамилия И.О.'; GridList.Visible:=False; LbMes.AutoSize:=True; LbMes.Visible:=False; EdNumi.SetFocus;

End;

Procedure TListsForm.ItemExitClick(Sender: TObject); {Закрытие выполняемого проекта}

Begin

Close;

End;

End.

33

Технологии программирования

3.3. Создание связного списка

Создание связного списка предусматривает следующие действия:

Во-первых, ввод первого элемента в объекты, распола- гаемые на экранной форме;

Во-вторых, выделение специальной переменной для хранения указателя на первый элемент списка;

В-третьих, выделение динамической памяти для первого элемента;

В-четвертых, перенесение информации из объектов в динамическую память, выделенную для первого элемента списка;

В-пятых, занесение ссылки равной “Nil” на место указа- теля на следующий элемент.

Procedure TListsForm.CreateClick(Sender: TObject); {Процедура создания первого элемента списка} Begin

NEW(First);

First^.Number:=StrToInt(EdNumI.Text);

First^.Family:=EdFamilyI.Text;

First^.Next:=Nil;

End;

3.4. Просмотр связного списка

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

Для организации просмотра связного списка целесооб- разно использовать компонент TstringGrid.

Procedure TListsForm.View(Sender: TObject); {Просмотр списка}

34

Технологии программирования, основанные на динамическом распределении памяти

Var P:T_Pointer; L:Integer; Begin P:=First; L:=0;

{Формирование выходной таблицы} While P<>Nil Do

Begin L:=L+1;

GridList.Cells[0,L]:=IntToStr(L);

GridList.Cells[1,L]:=IntToStr(P^.Number);

GridList.Cells[2,L]:=P^.Family;

P:=P^.Next;

End;

{Просмотр таблицы} GridList.RowCount:=L+1; GridList.Visible:=True; LbList.Visible:=True; End;

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

Добавление элемента в конец связного списка преду- сматривает следующие действия:

Во-первых, ввод добавляемого элемента в объекты, рас- полагаемые на экранной форме;

Во-вторых, нахождение последнего элемента списка; В-третьих, выделение динамической памяти для добав-

ляемого элемента; В-четвертых, формирование в последнем элементе спи-

ска ссылки на добавляемый элемент; В-пятых, перенесение информации из объектов в дина-

мическую память, выделенную для нового элемента списка; В-шестых, занесение в добавляемый элемент ссылки

равной “Nil” на место указателя на следующий элемент.

Procedure TListsForm.Append(Sender: TObject); {Добавление нового элемента в конец списка} Var

35

Технологии программирования

P:T_Pointer; Begin P:=First;

{Нахождение последнего элемента} While P^.Next<>Nil Do P:=P^.Next;

{Создание нового элемнта} New(P^.Next);

P:=P^.Next;

P^.Number:=StrToInt(EdNumI.Text);

P^.Family:=EdFamilyI.Text;

P^.Next:=Nil;

End;

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

WN:=P^.Number;

New(P^.Next);

P:= P^.Next; P^.Number:=Wn+1;

3.6. Поиск требуемого элемента в списке

Поиск элемента в списке предусматривает следующие действия:

Во-первых, ввод ключевого значения признака искомого элемента;

Во-вторых, последовательныйпросмотр элементов списка; В-третьих, сравнение ключевого поля элемента списка с

искомым значением; В-четвертых, проверку на окончание списка.

Procedure TListsForm.Seek(Sender: TObject);

{Поиск элемента в списке}

Var

P:T_Pointer;

Begin

36

Технологии программирования, основанные на динамическом распределении памяти

P:=First;

{Поиск требуемого элемента}

While (P<>Nil) And (P^.Number<>StrToInt(EdNumS.Text))Do P:=P^.Next;

If P=Nil Then Begin

LbMes.Caption:='Табельный номер задан неверно'; LbMes.Visible:=True;

EdFamilys.Visible:=False;

LbFamilys.Visible:=False; End

Else

Begin EdFamilyS.Text:=P^.Family; EdFamilys.Visible:=True; LbFamilys.Visible:=True; LbMes.Visible:=False;

End;

End;

3.7. Удаление требуемого элемента из списка

Удаление элемента из списка предусматривает следую- щие действия:

Во-первых, ввод ключевого значения признака удаляе- мого элемента;

Во-вторых, поиск элемента с заданным ключевым при- знаком;

В-третьих, определение элемента, предшествующего удаляемому элементу;

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

При удалении элемента из списка следует отдельно рас- сматривать ситуацию удаления первого элемента. Удаление первого элемента предполагает замену ссылки FIRST, опреде- ляющей начало списка.

37

Технологии программирования

Для освобождения занимаемой динимаческой памяти используется процедура Dispose.

Procedure TListsForm.Delete(Sender: TObject); {Удаление элемента c заданным табельным номером} Var

P,Q:T_Pointer; Begin P:=First;Q:=First;

If P^.Number=StrToInt(EdNumS.Text) Then Begin

{Удаляется первый элемент} First:=P^.Next;

Dispose(P);

LbMes.Visible:=False; End

Else

Begin

{Поиск удаляемого элемента}

While (P<>Nil) And (P^.Number<>StrToInt(EdNumS.Text))Do Begin

Q:=P;

P:=P^.Next;

End;

If P=Nil Then Begin

{Выдача сообщения об ошибке} LbMes.Caption:='Табельный номер задан неверно'; LbMes.Visible:=True;

End

Else

Begin

{Удаление найденного элемента} Q^.Next:=P^.Next;

Dispose(P);

LbMes.Visible:=False;

End;

End;

End;

38

Технологии программирования, основанные на динамическом распределении памяти

3.8.Вставка элементов в список, упорядоченный по ключевому признаку

Вставка элементов в список предусматривает следующие действия:

Во-первых, ввод вставляемого элемента; Во-вторых, выделение динамической памяти для нового

элемента; В-третьих, занесение информации во вновь выделенную

память; В-четвертых, определение элемента списка, предшест-

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

чение нового элемента в список.

При засылке указателя отдельно рассматриваются три ситуации:

Во-первых, вставка на место первого элемента; Во-вторых, вставка в середину списка; В-третьих, вставка на место последнего элемента.

При вставке перед первым элементом предусматривает- ся выполнение следующих действий:

Во-первых, замена ссылки FIRST, определяющей начало списка;

Во-вторых, во вставляемый элемент заносится указатель на элемент, который раньше был первым.

При вставке в середину списка требуется выполнение следующих действий:

Во-первых, в предшествующий элемент списка заносится указатель на вставляемый элемент;

Во-вторых, во вставляемый элемент заносится указатель на элемент, следующий за вставляемым элементом.

При вставке на место последнего элемента предполага- ется выполнение следующих действий:

Во-первых, в последний элемент списка заносится указа- тель на вставляемый элемент;

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

39

Технологии программирования

Procedure TListsForm.Insert(Sender: TObject); {Вставка элемента в упорядоченный список, в соответствии с заданным табельным номером} Var

R,P,Q:T_Pointer; Begin

{Формирование нового элемента} New(R); R^.Number:=StrToInt(EdNumI.Text); R^.Family:=EdFamilyI.Text; P:=First;

LbMes.Visible:=False;

If R^.Number < P^.Number Then {Новый элемент вставляется перед первым элементом списка} Begin

First:=R;

R^.Next:=P; End

Else

Begin

While (P^.Next<>Nil) And (R^.Number>P^.Number)Do {Пропуск записей с меньшими значениями табельных номеров. Просмотр завершается на последнем элементе списка.}

Begin

Q:=P;

P:=P^.Next;

End;

If R^.Number<P^.Number Then

{Новый элемент вставляется между Q и P } Begin

Q^.Next:=R;

R^.Next:=P;

End;

If R^.Number>P^.Number Then {Новый элемент вставляется после последнего элемента списка} Begin

P^.Next:=R;

R^.Next:=Nil;

End;

If R^.Number=P^.Number Then

40