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

Указатели 

Обычно переменная хранит некоторые данные. Однако помимо обычных, существуют переменные, которые ссылаются на другие переменные. Такие переменные называются указателями. Указатель — это переменная, значением которой является адрес другой переменной или структуры данных. Графически указатель может быть изображен так. как на рис. 8.5.

 

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

 

Имя: ^Тип;

 

где:

  • имя — имя переменной-указателя;
  • тип — тип переменной, на которую указывает переменная-указатель;
  • значок ^- показывает, что объявляемая переменная является указателем.

Приведем примеры объявления указателей:

 


p1: ^integer;
р2: ^real;

 

В приведенном примере переменная pi — это указатель на переменную типа integer, а р2 — указатель на переменную типа real. Тип переменной, на которую ссылается указатель, называют типом указателя. Например, если в программе объявлен указатель р: ^integer, то говорят: ^р — указатель целого типа^ или ^р — это указатель на целое^. В начале работы программы переменная-указатель ^ни на что не указывает^.

В этом случае говорят, что значение указателя равно NIL.

Зарезервированное слово NIL соответствует значению указателя, который ни на что не указывает.

Идентификатор NIL можно использовать в инструкциях присваивания и в условиях.

Например, если переменные p1 и р2 объявлены как указатели, то инструкция

 

p1:= NIL;

 

устанавливает значение переменной, а инструкция

 


if р2 = NIL
then ShowMessage('Указатель р2 не инициализирован!'];

 

проверяет, инициализирован ли указатель р2.

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

 

p:=@n;

 

 

Помимо адреса переменной, указателю можно присвоить значение другого указателя при условии, что они являются указателями на переменную одного типа. Например, если переменные pi и р2 являются указателями типа integer, то в результате выполнения инструкции

 

Р2 := p1;

 

 

переменные pi и р2 указывают на одну и туже переменную. Указатель можно использовать для доступа к переменной, адрес которой содержит указатель.

Например, если р указывает на переменную - то в результате выполнения инструкции

 

р^ : = 5;

 

 

значение переменной i будет равно пяти. В приведенном примере значок ^ показывает, что значение пять присваивается переменной, на которую указывает переменная-указатель.


Динамические переменные 

Динамической переменной называется переменная, память для которой выде-
ляется во время работы программы.
Выделение памяти для динамической переменной осуществляется вызовом
процедуры new. У процедуры new один параметр — указатель на переменную
того типа, память для которой надо выделить. Например, если р является
указателем на тип real, то в результате выполнения процедуры new(p],- бу-
дет выделена память для переменной типа real (создана переменная типа
real), и переменная-указатель р будет содержать адрес памяти, выделенной
для этой переменной.
У динамической переменной нет имени, поэтому обратиться к ней можно
только при помощи указателя.
Процедура, использующая динамические переменные, перед завершением
своей работы должна освободить занимаемую этими переменными память

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

Выделение памяти для динамической переменной осуществляется вызовом процедуры new. У процедуры new один параметр — указатель на переменную того типа, память для которой надо выделить. Например, если р является указателем на тип real, то в результате выполнения процедуры new(p)- будет выделена память для переменной типа real (создана переменная типаreal), и переменная-указатель р будет содержать адрес памяти, выделенной для этой переменной.

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

Например, если р — указатель на динамическую переменную, память для которой выделена инструкцией new ( p ) , то инструкция dispose (p) освобождает занимаемую динамической переменной память.

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

Листинг 8.3. Создание, использование и уничтожение динамических переменных

 


01.procedure TForm1.Button1Click(Sender: TObject);
02.var
03.pl,p2,p3: ^integer// указатели на переменные типе integer
04.begin
05.// создадим динамические переменные типа integer
06.// (выделим память для динамических переменных)
07.New(pl);
08.Hew(p2];
09.Hew(p3);
10.pi^ := 5;
11.p2n := 3;
12.рЗ^ := pi^ + p2^;
13.ShowMessage['Сумма чисел равна ' + IntToStrIp3^));
14.// уничтожим динамические переменные
15.// (освободим память, занимаемую динамическими переменными;
16.Dispose(pi);
17.Dispose(p2);
18.Dispose(рЗ);
19.end;

 

В начале работы процедура создает три динамические переменные. Две переменные, на которые указывают p1 и р2, получают значение в результате выполнения инструкции присваивания. Значение третьей переменной вычисляется как сумма первых двух.


 Списки

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

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

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

Ниже приведен пример объявления компонента списка студентов:

 


01.type
02.TPStudent ^TStudent; // указатель не переменную типа TStudent
03.// описание тила элемента списка
04.TStudent = record
05.surname: string[20]; // фамилия
06.name: string[20]; // имя
07.group: integer;  // номер группы
08.address: string[60]; // домашний адрес
09.next: TPStudent; // указатель на следующий элемент списка
10.end;
11.var
12.head: TPStudent; // указатель на первый элемент списка

 

Добавлять данные можно в начало, в конец или в нужное место списка. Во всех этих случаях необходимо корректировать указатели. На рис. 8.7 изображен процесс добавления элементов в начало списка.

Следующая программа (ее текст приведен в листинге 8.4) формирует список студентов, добавляя фамилии в начало списка. Данные вводятся в поля редактирования диалогового окна программы (рис. 8.8) и добавляются в список нажатием кнопки Добавить (Button1).

Листинг 8.4. Добавление элемента в начало динамического списка

 


 
01.unit dlistl ;
02.interface
03. 
04.Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
05.Dialogs, StdCtrls;
06.type
07.TForml = class(TForm!
08.Labell: TLabel;
09.Label2: TLabel;
10.Label3: TLabel;
11.Editl: TEdit; // фамилия
12.Edit2: TEdit; // имя
13.Buttonl: TButton; // кнопка Добавить
14.Button.2: TButton; // кнопка Показать
15.procedure ButtonlClickfSender; TObject);
16.procedure Button2Click(Sender: TObject];
17.private
18.{ Private declarations}
19.public
20.{ Public declarations }
21.end;
22.vat
23.Forml: TForml;
24.implementation
25.{SR *.DFM}
26.type
27.TPStudent="TStudent; // указатель на тип TStudent
28.TStudent = record
29.f_name:string[20]; // фамилия
30.l_name: string[20]; // имя
31.next: TPStudent; // следующий элемент списка
32.end;
33.var
34.head: TPStudent; // начало (голова) списка
35. 
36.// добавить элемент в начало списка
37.procedure TFoml.ButtonlClicU Sender: TObject);
38.var
39.curr: TPStudent; // новый элемент списка
40.begin
41.new(curr); // наделить память для элемента списка
42.curr^. f_name := Edit1.Text;
43.curt^.l_name := Edit2.Text;
44.// добавление в начало списка
45.curr^.next := head;
46.head := curr;
47.// очистить поля ввода
48.Edit1.text:='';
49.Edit2.text:='';
50.end;
51.// вывести список
52.procedure ТForml.Button2Click(Sender: TObject);
53.var
54.curr: TPStudent; // текущий элемент списка
55.n:integer// длина (кол-во элементов) списка
56.st:string// строковое представление списка
57.begin
58. 
59.n := 0;
60.st := ";
61.curr := head; // указатель на первый элемент списка
62.while curr о NIL do
63.begin
64.n := n + 1;
65.st := st + curr^. f_name + ' ' + curr^ l_name +S13;
66.curr := curr^.next; // указатель на следующий элемент
67.end;
68.if n=0 then ShowMessage('Список:' 113 + st)
69.else ShowMessage('В списке нет элементов.');
70.end;
71.end.

 

 

Добавление элемента в список выполняет процедура TFormi.Buttoniciick, которая создает динамическую переменную-запись, присваивает ее полям значения, соответствующие содержимому полей ввода диалогового окна, и корректирует значение указателя head.

Вывод списка выполняет процедура TForml.Button2Click, которая запускается нажатием кнопки Показать. Для доступа к элементам списка используется указатель curr. Сначала он содержит адрес первого элемента списка. После того как первый элемент списка будет обработан, указателю curr присваивается значение поли next той записи, на которую указывает curr.

В результате этого переменная curr содержит адрес второго элемента списка. Таким образом, указатель перемещается по списку. Процесс повторяется до тех пор, пока значение поля next текущего элемента списка (элемента, адрес которого содержит переменная curr) не окажется равно NIL.


dle

Помоги проекту! Расскажи друзьям об этом сайте:


Изменил: admin по причине: Исправлена ошибка