Додавання елементу в список
P1: ^integer;
р2: ^real;
У приведеному прикладі змінна p1 — це вказівник на змінну типу integer, а p2 — вказівник на змінну типу real.
Тип змінної, на яку посилається вказівник, називають типом вказівника. Наприклад, якщо в програмі оголошений вказівник
р: ^integer, то кажуть:
^р — вказівник цілого типу" або "р — це вказівник на ціле".
На початку роботи програми змінна- вказівник "ні на що не указує". В цьому випадку говорять, що значення покажчика рівне NIL. Зарезервоване слово NIL відповідає значенню покажчика, який ні на що не указує.
Ідентифікатор NIL можна використовувати в інструкціях привласнення і в умовах. Наприклад, якщо змінні p1 і р2 оголошені як покажчики, то інструкція
p1 := NIL;
встановлює значення змінної, а інструкція
if р2 = NIL then ShowMessage(' Вказівник р2 не ініціалізований!');
перевіряє, чи ініціалізував вказівник р2.
Вказівнику можна привласнити значення — адресу змінної відповідного типу (у тексті програми адреса змінної — це ім'я змінної, перед яким коштує оператор @). Нижче приведена інструкція, після виконання якої змінна р міститиме адресу змінної п.
р := @n;
Крім адреси змінної, вказівнику можна привласнити значення іншого вказівника за умови, що вони є вказівники на змінну одного типу. Наприклад, якщо змінні p1 і р2 є вказівниками типу integer, то в результаті виконання інструкції
p2 := p1;
змінні p1 і р2 указують на одну і ту ж змінну.
Вказівник можна використовувати для доступу до змінної, адресу якої містить вказівник. Наприклад, якщо р указує на змінну 1, то в результаті виконання інструкції
р^ : = 5;
значення змінної i буде рівне п'яти. У приведеному прикладі значок ^ показує, що значення п'ять привласнюється змінною, на яку указує змінна-вказівник.
8.2. Динамічні змінні
Динамічною змінною називається змінна, пам'ять для якої виділяється під час роботи програми.
Виділення пам'яті для динамічної змінної здійснюється викликом процедури 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; |
На початку роботи процедура створює три динамічні змінні. Дві змінні, на які указують p1 і р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) і додаються в список натисненням кнопки Додати(Button1).
Рис. 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 Button1Click(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 TForm1.Button1Click(Sender: TObject);
Var
curr: TPStudent; // новий елемент списку
Begin
new(curr); // виділити пам'ять для елементу списку
curr^.f_name := Edit1.Text;
curr^.1_nаmе := Edit2.Text; // додавання в початок списку
curr^.next := head;
head := curr; // очистити поля введення
Edit1.text:='';
Edit2.text: = " ;
End;
// вивести список
procedure TForm1.Button2Click(Sender: TObject);
Var
curr: TPStudent; // поточний елемент списку
n:integer; // довжина (к-ть елементів) списку
st:string; // стрічкове представлення списку
Begin
n := 0;
st := '';
curr := head; // вказівник на перший елемент списку
while curr <> NIL dobegin
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.Діалогове вікно програми
8.5. Впорядкований динамічний список 2
Наступна програма (її текст приведений в лістингу 8.5, а діалогове вікно — на мал. 8.10) формує список, впорядкований по полю Прізвище.Дані вводяться в поля редагування (Edit1 і Edit2) і натисненням кнопки Додати(Button1) додаються в список таким чином, що список завжди впорядкований по полю Прізвище.
Лістинг 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 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=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+1;
st:=st+curr^.f_name+' '+currA.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.
Процедура Tform1.Button1Click створює динамічну змінну-запис, привласнює її полям значення, відповідні вмісту полів введення діалогового вікна, знаходить відповідне місце для вузла і додає цей вузол в список, коректуючи при цьому значення покажчика вузла next, після якого повинен бути поміщений новий вузол.
Рис. 8.11.Приклад впорядкованого списку, сформованого програмою
Виведення списку виконує процедура TForm1.Button2Сlick, яка запускається натисненням кнопки Показати.Після запуску програми і введення декількох прізвищ, наприклад, в такій послідовності: Іванов, Іванов, Петров, Сидоров список виглядає так, як показано на мал. 8.11.
8.6. Видалення елементу із списку
Для того, щоб видалити вузол, необхідно скоректувати значення покажчика вузла, який знаходиться перед вузлом, що видаляється (рис. 8.12).
Рис. 8.12.Видалення елементу із списку
Оскільки вузол є динамічній змінній, то після виключення вузла із списку займана ним пам'ять повинна бути звільнена. Звільнення динамічної пам'яті, або, як іноді говорять, "знищення змінної", виконується викликом процедури dispose. У процедури dispose один параметр — вказівник на динамічну змінну. Пам'ять, займана цією динамічною змінною, повинна бути звільнена. Наприклад, в програмі
Var
р: ^integer;
Begin
new(p);
{ інструкції програми }
dispose(p);
End
створюється динамічна змінна р, а потім вона знищується. Пам'ять, що звільнилася, зможуть використовувати інші змінні. Якщо цього не зробити, то, можливо, через нестачу вільної пам'яті в якийсь момент часу програма не зможе створити чергову динамічну змінну.
Наступна програма дозволяє додавати і видаляти вузли впорядкованого списку. Діалогове вікно програми приведене на рис. 8.13.
Процедури додавання вузла в список і виведення списку, а також оголошення типу вузла списку нічим не відрізняються від відповідних процедур розглянутої раніше програми Впорядкований динамічний список2, тому вони тут не приводяться.
Видалення вузла із списку виконує процедура TForm1.Button3Click, яка запускається натисненням кнопки Видалити(Buttons). Текст процедури приведений в лістингу 8.6.
Рис. 8.13.Вікно програми
Динамічний список 3
Лістинг 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.
Процедура проглядає список від початку, порівнюючи вміст полів поточного вузла з вмістом полів введення діалогового вікна. Якщо їх вміст співпадає, то процедура просить користувача підтвердити видалення вузла. Якщо користувач натисненням кнопки ОК підтверджує, що вузол повинен бути видалений, то процедура видаляє його. Якщо вузла, який хоче видалити користувач, в списку немає, програма виводить повідомлення про помилку.
Питання:
1. Що таке вказівник.
2. Що таке список даних.
3. Що таке однонаправлений список.
4. Що таке двонаправлений список.
Література: