.: Учебник по Delphi 7 для начинающих :.

Глава 8. Типы данных, определяемые программистом Перечисляемый тип Интервальный тип Запись Объявление записи Инструкция with Ввод и вывод записей в файл Вывод записи в файл Чтение записи из файла Динамические структуры данных Указатели Динамические переменные Списки Упорядоченный список Добавление элемента в список Удаление элемента из списка

Глава 8

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

До этого момента в программах использовались стандартные типы данных: integer, Real, Char, string и Boolean. Вместе с тем, язык Delphi позволяет программисту определить свой собственный тип данных, а затем данные этого типа использовать в программе.

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

• перечисляемому;
  
• интервальному;
  
• составному типу данных (записи).
  

Перечисляемый тип

Определить перечисляемый тип — это значит перечислить все значения, которые может принимать переменная, относящаяся к данному типу.

В общем виде объявление перечисляемого типа выглядит так:

Тип =(Значение1, Значение2, ... Значение i)

где:

• тип — имя перечисляемого типа данных;
  
• Значение i — символьная константа, определяющая одно из значений, которое может принимать переменная типа Тип.
  

Примеры:

TDayOfWeek = (MON,TUE,WED,THU,FRI,SAT,SUN);

TColor = (Red,Yellow,Green);

Примечание

Согласно принятому в Delphi соглашению, имена типов должны начинаться с буквы Т (от слова Туре — тип).

После объявления типа можно объявить переменную, относящуюся к этому типу, например:

type

TDayOfWeek = (MON,TUE,WED,THU, FRI,SAT,SUN) ;

var

ThisDay, LastDay: TDayOfWeek;

Помимо указания значений, которые может принимать переменная, описание типа задает, как значения соотносятся друг с другом. Считается, что самый левый элемент списка значений является минимальным, а самый правый — максимальным. Для элементов типа DayOfWeek справедливо:

MON < TUE < WED < THU < FRI < SAT < SUN

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

if (Day = SAT) OR (Day = SUN) then

begin

{ действия, если день — суббота или воскресенье }

end;

Приведенную инструкцию можно записать и так:

if Day > FRI then begin

{ действия, если день — суббота или воскресенье }

end;

Очевидно, что программа, написанная с использованием объявленного программистом типа, более наглядна, легче читается и, следовательно, уменьшается вероятность появления ошибки.

Во время компиляции Delphi проверяет соответствие типа переменной типу выражения, которое присваивается переменной. Если тип выражения не может быть приведен к типу переменной, то выводится сообщение об ошибке.

Например, в фрагменте программы

type

TDayOfWeek = (MON, TUE, WED, THU, FRI, SAT, SUN) ;

ThisDay: TDayOfWeek; begin

ThisDay:=1;

if ThisDay = 6 then begin

{ блок инструкций } end;

инструкция ThisDay:= i; ошибочна, т. к. переменная ThisDay принадлежит к определенному программистом перечисляемому типу TDayOfWeek, а константа, значение которой ей присваивается, принадлежит к целому типу (integer). В условии инструкции if тоже ошибка.

Можно утверждать, что объявление перечисляемого типа — это сокращенная форма записи объявления именованных констант. Например, приведенное выше объявление типа TDayOfWeek равносильно следующему объявлению:

const

MON=0; TUE=1; WED=2; THU=3; FRI=4; SAT=5; SUN=6;

Интервальный тип

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

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

Тип = НижняяГраница..ВерхняяГраница;

где:

• тип — имя объявляемого интервального типа данных;
  
• НижняяГраница — наименьшее значение, которое может принимать переменная объявляемого типа;
  
• верхняяГраница — наибольшее значение, которое может принимать переменная объявляемого типа.
  

Примеры:

TIndex = 0 .. 100; TRusChar = 'А' .. 'я';

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

const

HBOUND=100;

type

TIndex=l..HBOUND;

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

type

TIndex =1 .. 100;

var

tab1 : array[TIndex] of integer; i:TIndex;

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

type

TMonth = (Jan, Feb, Mar, Apr, May, Jun,

Jul, Aug, Sep, Oct, Nov, Dec);

TSammer = Jun.. Aug;

Запись

В практике программирования довольно часто приходится иметь дело с данными, которые естественным образом состоят из других данных. Например, сведения об учащемся содержат фамилию, имя, отчество, число, месяц и год рождения, домашний адрес и другие данные. Для представления подобной информации в языке Delphi используется структура, которая носит название запись (record).

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

Итак, запись — это структура данных, состоящая из отдельных именованных компонентов разного типа, называемых полями.

Объявление записи

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

Имя = record

Поле_1 : Тип_1; Поле_2 : Тип_2; Поле_К : Тип_К; end;

где:

• Имя — имя типа "запись";
  
• record — зарезервированное слово языка Delphi, означающее, что далее следует объявление компонентов (полей) записи;
  
• поле_i и тил_i — имя и тип i-го компонента (поля) записи, где i=1, ..., k;
  
• end — зарезервированное слово языка Delphi, означающее, что список полей закончен.
  

Примеры объявлений:

type

TPerson = record

f_name: string[20];

l_name: string[20];

day: integer;

month: integer;

year: integer;

address: string[50]; end;

TDate = record

day: integer; month: integer; year: integer;

end;

После объявления типа записи можно объявить переменную-запись (или просто запись), например:

var

student : TPerson; birthday : TDate;

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

ShowMessage('Имя: ', student.f_name + #13 + 'Адрес: ', student.address);

выводит на экран содержимое полей f_name (имя) и address (адрес) переменной-записи student.

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

student: record

f_name:string[20];

l_name:string[20];

day:integer;

month:integer;

year:integer;

address:string[50];

end;

Инструкция with

Инструкция with позволяет использовать в тексте программы имена полей без указания имени переменной-записи. В общем виде инструкция with выглядит следующим образом:

with Имя do

begin

( инструкции программы } end;

где:

• имя — имя переменной-записи;
  
• with — зарезервированное слово языка Delphi, означающее, что далее, до слова end, при обращении к полям записи имя, имя записи можно не указывать.
  

Например, если в программе объявлена запись

student:record // информация о студенте

f_name: string[30]; // фамилия

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

address: string[50}; // адрес

end;

и данные о студенте находятся в полях Edit1, Edit2 и Edit3 диалогового окна, то вместо инструкций

student.f_name := Editl.text;

student.l_name := Edit2.text;

student.address := Edit3.text;

можно записать:

with student do begin

f_name := Edit1.text; l_name := Edit2.text; address := Edit3.text;

end;

Ввод и вывод записей в файл

Записи можно хранить в файле. Для того чтобы программа могла сохранить значение переменной-записи в файле или ввести его из файла, необходимо объявить файл, указав в качестве типа его компонентов тип "запись". Например, инструкции

type

ТРеrson = record

f_riame: string [20] ;

l_name: string[20];

address: string[50]; end; var

f: file of TPerson;

объявляют файл, компонентами которого являются записи типа TPerson.

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

Вывод записи в файл

Рассмотрим программу, которая записывает в файл введенные пользователем данные о результатах соревнований, формируя, таким образом, простую базу данных. Исходные данные вводятся в поля диалогового окна (рис. 8.1) и сохраняются в файле, компонентами которого являются записи типа TMedal.

Рис. 8.1. Окно программы Добавление записи в файл

Для ввода фамилии спортсмена применяется поле редактирования (компонент Edit). Для ввода названия вида спорта и страны используются компоненты ComboBox (комбинированный список).

Компонент ComboBox, значок которого находится на вкладке Standard (рис. 8.2), дает возможность ввести данные либо непосредственно в поле ввода-редактирования, либо путем выбора из списка, который появляется в результате щелчка на кнопке раскрывающегося списка.

Рис. 8.2. Значок компонента ComboBox В табл. 8.1 перечислены свойства компонента ComboBox.

Таблица 8.1. Свойства компонента ComboBox

Список, который появляется в результате щелчка на кнопке раскрытия списка, может быть сформирован как в процессе разработки формы приложения, так и во время работы программы. Чтобы сформировать список во время разработки формы, нужно в окне Object Inspector выбрать свойство Items, щелкнуть на кнопке активизации редактора списка строк (кнопка с тремя точками) и ввести элементы списка (рис. 8.3).

Рис. 8.3. Ввод списка для компонента ComboBox2 во время создания формы приложения

Полный текст программы приведен в листинге 8.1.

Листинг 8.1. Добавление записей в файл

unit аррrес_;

interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class(TForm) Label1: TLabel;

Label2: TLabel; Label3: TLabel;

Edit1: TEdit; // спортсмен

ComboBoxl: TComboBox; // страна

ComboBox2: TComboBox; // вид спорта

RadioGroup1: TRadioGroup; // медаль

Buttonl: TButton; // кнопка Добавить

Labels: TLabel;

Label4: TLabel;

procedure FormActivate(Sender: TObject);

procedure FormClose(Sender: TObject;

var Action: TCloseAction)

procedure ButtonlClick(Sender: TObject);

private

{ Private declarations } public

{ Public declarations } end;

// тип медали

TKind = (GOLD, SILVER, BRONZE);

// запись файла

TMedal=record

country: string[20]; // страна

sport: string[20]; // вид спорта

person: string[40]; // спортсмен

kind: TKind; // медаль

end;

var

Form1: TForm1;

f: file of TMedal; // файл записей — база данных

implementation

{$R *.DFM}

// активизация формы

procedure TForm1.FormActivate(Sender: TObject);

var

resp : word; // ответ пользователя

begin

AssignFile(f, 'a:\medals.db');

{$I-}

Reset (f); // открыть файл

Seek(f, FileSize(f)); // указатель записи в конец файла

{$I!+}

if lOResult = 0

then buttonl.enabled:=TRUE // теперь кнопка Добавить доступна

else begin

resp:=MessageDlg('Файл базы данных не найден.'

+ 'Создать новую БД?', mtlnformation,[mbYes,mbNo],0);

if resp = mrYes then begin {$I-}

rewrite(f); {$!+}

if lOResult = 0

then buttonl.enabled:=TRUE

else ShowMessage('Ошибка создания файла БД.');

end;

end;

end;

// щелчок на кнопке Добавить

procedure TForml.Button1Click(Sender: TObject);

var

medal: TMedal;

begin

with medal do begin

country := ComboBox1.Text;

sport := ComboBox2.Text;

person := Edit1.Text;

case RadioGroup1.Itemlndex of

0: kind := GOLD;

1: kind := SILVER;

2: kind := BRONZE;

end;

end;

write(f,medal); // записать содержимое полей записи в файл

end;

// завершение работы программы

procedure TForm1.FormClose(Sender: TObject;

var

Action: TCloseAction);

begin

CloseFile(f); // закрыть файл

end;

end.

В представленной программе процедура TForm1.FormActivate открывает файл базы данных для добавления. Здесь следует обратить внимание на то, как это реализовано. Процедуру AppendFile, которая открывает файл для добавления в конец, использовать нельзя, т. к. файл не является текстовым. Поэтому файл сначала открывается процедурой Rewrite в режиме перезаписи, а затем процедура Seek устанавливает указатель чтения/записи в конец файла. Параметром процедуры seek является функция Fiiesize, значение которой равно размеру файла (в байтах).

Процедура TForm1.Button1Click, которая запускается нажатием кнопки Добавить (Buttoni), выполняет непосредственное добавление записи в файл. Поля country и sport добавляемой записи заполняются из свойства Text комбинированных списков Страна (comboBoxi) и Вид спорта (ComboBox2).

Поле person формируемой записи заполняется из поля ввода Спортсмен (компонент Editi), а содержимое поля medal определяется выбранной кнопкой компонента RadioGroupl.

Процедура TForm1. FormClose закрывает файл базы данных поскольку тип TMedal используется двумя процедурами (TForm1.FormActivate и TForm1.Button1Сlick), то его описание помещено в раздел type модуля формы. Объявление файловой переменной f по этой же причине помещено в раздел объявления переменных модуля формы.

В приведенном варианте программы предполагается, что списки стран и названий видов спорта формируются при помощи редактора списка строк во время разработки формы. Вместе с тем, список можно сформировать во время разработки программы. Для этого надо к свойству items применить метод Add. Например, список стран может быть сформирован при помощи следующих инструкций (их нужно поместить в процедуру Tform1.FormActivate):

Form1.ComboBox1.Item.Add('Россия');

Form1.ComboBox1.Item.Add('Австрия');

Form1.ComboBox1.Item.Add('Германия');

Form1.ComboBox1.Item.Add('Франция');

Чтение записи из файла

Рассмотрим программу, демонстрирующую процесс чтения и обработки записей файла. Программа Чтение записей из файла, диалоговое окно которой представлено на рис. 8.4, а текст — в листинге 8.2, открывает файл, сформированный программой Добавление записи в файл, и, в зависимости от того, какой из переключателей все или выбрать — установлен, выводит список медалей, выигранных соответственно представителями всех стран или страны, название которой введено в поле Страна. Для вывода результата чтения из файла используется компонент Memol.

В табл. 8.2 приведены значения свойств компонентов формы.

Так как компонент Memol предназначен только для просмотра информации, то свойству Readonly (только чтение, просмотр) присвоено значение True. Свойство scroiiBars (полосы прокрутки) компонента Memo позволяет задавать отображаемые полосы прокрутки. По умолчанию свойству scroiiBars присвоено значение ssNone, т. е. полосы прокрутки не отображаются. В рассматриваемом примере выводится вертикальная полоса, поэтому свойству ScroiiBars присвоено значение ssVertical.

Таблица 8.2. Значения свойств компонентов

Для ввода названия страны используется компонент ComboBox1, что позволяет задавать имя не только прямым вводом названия, но и выбором из списка. Список стран нужно сформировать во время создания формы путем присвоения значения свойству items.

Чтобы сразу после запуска программы список выбора страны был недоступен (т. к. выбран переключатель все группы Показать), свойству Enabled компонентов ComboBox1 и Label1 во время создания формы нужно присвоить значение False.

Список ввода-выбора названия страны (comboBoxl) становится доступным в результате выбора во время работы программы переключателя выбрать. Процедура обработки события Onclick на переключателе RadioButton2 делает доступным поле ComboBox1.

Рис. 8.4. Окно программы Чтение записей из файла

Листинг 8.2. Чтение записей из файла

unit rdrec_;

interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls;

type

TForm1 = class(TForm)

RadioButton1: TRadioButton; // переключатель Все

RadioButton2: TRadioButton; // переключатель Выбрать

// текст Страна

Button1: TButton;

GroupBox1: TGroupBox;

Label1: TLabe1;

procedure Button1Click(Sender: TObject);

procedure RadioButton2Click(Sender: TObject);

procedure RadioButton1Click(Sender: TObject);

ComboBox1: TComboBox; // комбинированный список

// для ввода названия страны

Memol: TMemo; // поле вывода записей, удовлетворяющих

// условию запроса

private

{ Private declarations } public

{ Public declarations } end;

var

Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject) ;

type

// тип медали

TKind = (GOLD,SILVER,BRONZE);

// запись файла

TMedal = record

country:string[20]; sport:string[20];

person:string[40]; kind:TKind;

end;

var

f: file of TMedal; // файл записей

rec: TMedal; // запись, прочитанная из файла

n: integer; // кол-во записей, удовлетворяющих запросу

st: string[80];

begin

AssignFile(f,'a:\medals.db');

{$I-}

Reset (f); // открыть файл для чтения

{$I-}

if IOResult <> 0 then begin

ShowMessage('Ошибка открытия файла БД.');

Exit;

end;

// обработка БД

if RadioButton2.Checked then

Memo1.Lines.Add('*** ' + ComboBox1.Text + ' ***'); n := 0;

Memol.Clear; // очистить список поля Memo

while not EOF(f) do begin

read(f, rec); // прочитать запись

if RadioButton1.Checked or

(rec.country = ComboBoxl.Text) then begin

n := n + 1;

st := rec.person+ ', ' + rec.sport;

if RadioButtonl.Checked then

st := st + ', '+ rec.country; case rec.kind of

GOLD: st := st+ ', золото';

SILVER:st := st+ ', серебро';

BRONZE:st := st+ ', бронза';

end;

Memo1.Lines.Add(st); end;

end;

CloseFile(f); if n = 0 then

ShowMessage('В БД нет запрашиваемой информации.');

end;

// переключатель Выбрать

procedure TForm1.RadioButton2Click(Sender: TObject);

begin

Label1.Enabled := True;

ComboBox1.Enabled := True; // теперь поле Страна доступно

ComboBox1.SetFocus; // курсор в поле Страна

end;

// переключатель Все

procedure TForm1.RadioButton1Click(Sender: TObject);

begin

Label1.Enabled := False;

ComboBox1.Enabled := False; // теперь поле Страна не доступно

end;

end.

Процедура TForm1.Button1Click открывает файл и последовательно считывает находящиеся в нем записи. Содержимое записи добавляется в поле Memol, если прочитанная запись удовлетворяет условию запроса, т. е. содержимое поля country совпадает с названием страны, введенным пользователем в поле редактирования компонента ComboBox1, или если выбран переключатель RadioButton1.

Информация в поле Memo добавляется инструкцией Memo1.Lines.Add(st), которая является инструкцией применения метода Add (Добавить) к компоненту Memo1.

Примечание

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

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

До этого момента мы работали только с данными, имеющими статическую, неизменяемую во время исполнения программы, структуру. Во время работы программы могли изменяться только значения переменных, в то время как количество переменных всегда оставалось постоянным (отсюда и название — статические структуры). Это не всегда удобно.

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

Задачи, обрабатывающие данные, которые по своей природе являются динамическими, удобно решать с помощью динамических структур.

Указатели

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

Рис. 8.5. Переменная-указатель

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

Имя: ^Тил;

где:

• имя — имя переменной-указателя;
  
• Тип — тип переменной, на которую указывает переменная-указатель;
  

значок ^ показывает, что объявляемая переменная является указателем.

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

p1: ^integer; р2: ^real;

В приведенном примере переменная p1 — это указатель на переменную типа integer, a p2 — указатель на переменную типа real.

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

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

Идентификатор NIL можно использовать в инструкциях присваивания и в условиях. Например, если переменные pi и р2 объявлены как указатели, то инструкция

p1 := NIL;

устанавливает значение переменной, а инструкция if р2 = NIL then ShowMessage('Указатель р2 не инициализирован!');

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

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

р := @n;

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

p2 := p1;

переменные pi и р2 указывают на одну и ту же переменную.

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

р^ : = 5;

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

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

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

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

У динамической переменной нет имени, поэтому обратиться к ней можно только при помощи указателя.

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

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

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

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

procedure TForm1.Button1Click(Sender: TObject); var

p1,p2,p3: Integer; // указатели на переменные типа integer

begin

// создадим динамические переменные типа integer

// (выделим память для динамических переменных)

New(p1);

New(p2);

New(p3);

р1^ := 5;

р2^ := 3;

р3^ := р1^ + р2^;

ShowMessage('Сумма чисел равна ' + IntToStr(р3^));

// уничтожим динамические переменные

// (освободим память, занимаемую динамическими переменными)

Dispose(p1);

Dispose(р2);

Dispose(р3);

end;

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

Списки

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

Список можно изобразить графически (рис. 8.6).

Рис. 8.6. Графическое изображение списка

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

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

type

TPStudent = ^TStudent; // указатель на переменную типа TStudent

// описание типа элемента списка

TStudent = record

surname: string[20]; // фамилия

name: string[20];' // имя

group: integer; // номер группы

address: string[60]; // домашний адрес

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

end;

var

head: TPStudent; // указатель на первый элемент списка

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

После добавления второго элемента в список head указывает на этот элемент

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

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

Рис. 8.8. Окно программы Динамический список 1

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

unit dlist1_; interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Edit1: TEdit; // фамилия

Edit2: TEdit; // имя

Button1: TButton; // кнопка Добавить

Button2: TButton; // кнопка Показать

procedure ButtonlClick(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations } public

{ Public declarations } end;

var

Form1: TForm1;

implementation

{$R *.DFM)

type

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

TStudent = record

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

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

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

end;

var

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

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

procedure TForml.Button1Click(Sender: TObject);

var

curr: TPStudent; // новый элемент списка

begin

new(curr); // выделить память для элемента списка

curr^.f_name := Edit1.Text;

curr^.1_пате := Edit2.Text;

// добавление в начало списка

curr^.next := head; head := curr;

// очистить поля ввода

Edit1.text:=''; Edit2.text: = " ;

end;

// вывести список

procedure TForml.Button2Click(Sender: TObject);

var

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

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

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

begin n := 0; st := '';

curr := head; // указатель на первый элемент списка

while curr <> NIL do begin

n := n + 1;

st := st + curr^.f_name + ' ' + curr^.1_name

+#13; curr := curr^.next;

// указатель на следующий элемент end;

if n <> 0

then ShowMessage('Список:' + #13 + st)

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

end;

end.

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

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

Упорядоченный список

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

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

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

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

Рис. 8.10. Диалоговое окно программы Упорядоченный динамический список 2

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

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

unit dlist2_;

interface

uses

Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Button1: TButton;

Button2: TButton;

Label3: TLabel;

Edit1: TEdit;

Edit2: TEdit;

procedure ButtonlClick(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure FormActivate(Sender: TObject);

private

{ Private declarations } public

{ Public declarations } end;

var

Form1: TForm1;

implementation

($R *.DFM}

type

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

TStudent = record

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

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

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

end;

var

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

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

procedure TForm1.Button1Click(Sender: TObject);

var

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

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

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

begin

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

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

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

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

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

curr:=head;

pre:=NIL;

{ Внимание!

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

на (node. f_name>curr". f__name) and (currONIL) ,

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

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

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

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

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

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

}

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

begin

// введенное значение больше текущего pre:= curr;

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

end;

if pre = NIL then

begin

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

node^. next: =head; head:=node;

end

else

begin

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

curr node^.next:=рre^.next;

рrе^.next:=node;

end;

Edit1.text:='';

Edit2.text:='';

Edit1.SetFocus;

end;

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

procedure TForm1.Button2Click(Sender: TObject);

var

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

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

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

begin

n:=0;

st: = '';

curr:=head;

while curr <> NIL

do

begin n:=n+l;

st:=st+curr^.f_name+' '+curr^A.l_name+#13;

curr:=curr^.next;

end; if n <> 0

then ShowMessage('Список: '+ЦЗ+st)

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

end;

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

procedure TForm1.FormActivate(Sender: TObject);

begin

head:=NIL; // список пустой

end;

end.

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

Рис. 8.11. Пример упорядоченного списка, сформированного программой

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

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

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

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

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

var

р: ^integer;

begin

new(p);

{ инструкции программы } dispose(p);

end

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

Следующая программа позволяет добавлять и удалять узлы упорядоченного списка. Диалоговое окно программы приведено на рис. 8.13.

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

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

Рис. 8.13. Окно программы Динамический список

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

unit dlist2_;

interface

uses
Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms, Dialogs,
StdCtrls;

type
TForm1 = class(TForm)
Label1: TLabel;
Label2: TLabel;
Button1: TButton;
Button2: TButton;
Label3: TLabel;
Edit1: TEdit;
Edit2: TEdit;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormActivate(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation
{$R *.DFM}

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

TStudent = record
f_name:string[20]; // фамилия
l_name:string[20]; // имя
next: TPStudent; // следующий элемент списка
end;

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

procedure TForm1.Button1Click(Sender: TObject);
var
node: TPStudent; // новый узел списка
curr: TPStudent; // текущий узел списка
pre: TPStudent; // предыдущий, относительно curr, узел
begin
new(node); // создание нового элемента списка
node^.f_name:=Edit1.Text; // фамилия
node^.l_name:=Edit2.Text; // имя
// добавление узла в список
// сначала найдем подходящее место в списке для узла
curr:=head;
pre:=NIL;
{ Внимание!
если приведенное ниже условие заменить
на (node.f_name>curr^.f_name)and(curr<>NIL)
то при добавлении первого узла возникает ошибка времени
выполнения, так как curr = NIL и, следовательно,
переменной curr.^name нет!
В используемом варианте условия ошибка не возникает, так как
сначала проверяется условие (curr <> NIL), значение которого
FALSE и второе условие в этом случае не проверяется.
}
while (curr <> NIL)and(node.f_name > curr^.f_name) do
begin
// введенное значение больше текущего
pre:= curr;
curr:=curr^.next; // к следующему узлу
end;
if pre = NIL
then
begin
// новый узел в начало списка
node^.next:=head;
head:=node;
end
else
begin
// новый узел после pre, перед curr
node^.next:=pre^.next;
pre^.next:=node;
end;

Edit1.text:='';
Edit2.text:='';
Edit1.SetFocus;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
curr: TPStudent; // текущий элемент списка
n:integer; // длина (кол-во элементов) списка
st:string; // строковое представление списка
begin
n:=0;
st:='';
curr:=head;
while curr <> NIL do
begin
n:=n+1;
st:=st+curr^.f_name+' '+curr^.l_name+#13;
curr:=curr^.next;
end;
if n <> 0
then ShowMessage('Список:'+#13+st)
else ShowMessage('В списке нет элементов.');
end;

procedure TForm1.FormActivate(Sender: TObject);
begin
head:=NIL;
end;

end.

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