Розділ 8. Динамічні структури даних

korpy@ukr.net
Лекція № 10
Розділ 8. Динамічні структури даних
Зміст
8. Динамічні структури даних

8.1. Вказівники
8.2. Динамічні змінні
8.3. Списки
8.4. Впорядкований список
8.5. Впорядкований динамічний список 2
8.6. Видалення елементу із списку
 
Питання
Література
Додаток 1

10
До цього моменту ми працювали тільки з даними, що мають

статичну, незмінну під час виконання програми, структуру. Під час роботи програми могли змінюватися тільки значення змінних, тоді як кількість змінних завжди залишалася постійною (звідси і назва — статичні структури). Це не завжди зручно.
Наприклад, в програмі, призначеній для введення і обробки даних про студентів в групі, для зберігання даних використовуються масиви. При визначенні розміру масиву програмістові доводиться орієнтуватися на деяку середню або граничну кількість студентів в групі. При цьому, якщо реально студентів в групі менше передбачуваної кількості, то неефективно використовується пам'ять комп'ютера, а якщо це число більше, то програму використовувати вже не можна (треба внести зміни до початкового тексту і виконати компіляцію).
Завдання, що обробляють дані, які за своєю природою є динамічними, зручно вирішувати за допомогою динамічних структур.

Розділ 8. Динамічні структури даних

10
Будова: набір вузлів, обьєднаних за допомогою посилань.
Як влаштований вузол:
Динамічні структури

даних

Типи структур:

10
Коли необхідні списки?
Задача (алфавітно-частотного словника). У файлі записаний текст.

Необхідно записати в інший файл в стовпчик всі слова, що зустрічаються в тексті, в алфавітному порядку, і кількість повторень для кожного слова.
Проблеми:
кількість слів наперед невідома (статичний масив);
кількість слів визначається тільки в кінці роботи (динамічний масив).
Рішення – список.
Алгоритм:
створити список;
якщо слова у файлі закінчились, то стоп.
прочитати слово і шукати його у списку;
якщо слово знайдено – збільшити лічильник повторень, інакше додати слово в список;
перейти до кроку 2.

10
8.1. Вказівники
Зазвичай змінна зберігає деякі дані. Проте окрім звичайних, існують

змінні, які посилаються на інші змінні. Такі змінні називаються вказівниками. Вказівник — це змінна, значенням якої є адреса іншої змінної або структури даних. Графічно вказівник може бути зображений так, як на мал. 8.1.

Рис. 8.1. Змінна-вказівник

Вказівник, як і будь-яка інша змінна програми, повинні бути оголошений в розділі оголошення змінних. У загальному вигляді оголошення вказівник виглядає таким чином:

^ Тип;
де:
ім'я — ім'я змінної-вказівника;
Тип — тип змінної, на яку

указує змінна- вказівника;
значок ^ показує, що змінна яку оголосили - є вказівник.
Наведемо приклади оголошення вказівника:






У приведеному прикладі змінна pI — це вказівник на змінну типу integer, а pR — вказівник на змінну типу real.
Тип змінної, на яку посилається вказівник, називають типом вказівника. Наприклад, якщо в програмі оголошений вказівник
р: ^integer, то кажуть:
^р — вказівник цілого типу" або "р — це вказівник на ціле".

var pC: ^char; // адреса символа
pI: ^integer; // адреса цілої змінної
pR: ^real; // адреса дійсної змінної

вказівник

^

записати адресу:
var m: integer; // ціла змінна
pI:

^integer; // вказівник
A: array[1..2] of integer; // масив
...
pI:= @ m; // адреса змінної m
pI:= @ A[1]; // адреса елемента масиву A[1]
pI:= nil; // нульова адреса

адреса комірки

@

nil

комірки
@
nil
procedure ……();
var m, n: integer;
pI: ^integer;
begin
m :=

4;
pI := @m;
writeln('Адрес m = ', pI); // вивід адреси
writeln('m = ‘, pI^); // вивід значення
n := 4*(7 - pI^); // n = 4*(7 - 4) = 12
pI^ := 4*(n - m); // m = 4*(12 – 4) = 32
end;

«витягнути» значення за адресою

^

Звернення до даних через вказівник

10
На початку роботи програми змінна- вказівник "ні на що не

вказує". В цьому випадку кажуть, що значення вказівника дорівнює NIL. Зарезервоване слово NIL відповідає значенню покажчика, який ні на що не вказує.
Ідентифікатор NIL можна використовувати в інструкціях привласнення і в умовах. Наприклад, якщо змінні p1 і р2 оголошені як покажчики, то інструкція
p1 := NIL;
встановлює значення змінної, а інструкція
if р2 = NIL then ShowMessage(' Вказівник р2 не ініціалізований!');
перевіряє, чи ініціалізований вказівник р2.
Вказівнику можна привласнити значення — адресу змінної відповідного типу (у тексті програми адреса змінної — це ім'я змінної, перед яким коштує оператор @). Нижче приведена інструкція, після виконання якої змінна р міститиме адресу змінної п.
р := @n;
Крім адреси змінної, вказівнику можна привласнити значення іншого вказівника за умови, що вони є вказівники на змінну одного типу. Наприклад, якщо змінні p1 і р2 є вказівниками типу integer, то в результаті виконання інструкції
p2 := p1;
змінні p1 і р2 вказують на одну і ту ж змінну.

10
Вказівник – це змінна, в якій можна зберігати адресу іншої

змінної;
при оголошенні вказівника необхідно вказувати тип змінних, на які він буде вказувати, а перед типом поставити знак ^ ;
знак @ перед ім’ям змінної означає її адресу;
запис p^ означає значення комірки, на яку вказує вказівник p;
nil – це нульовий вказівник, він нікуди не вказує
при зміні значення вказівника на n він насправді зсувається до n- ого наступного числа даного типу (для вказівників на цілі числа – на n*sizeof(integer) байт).

Що необхідно знати про вказівники

Динамічні змінні
Динамічною змінною називається змінна, пам'ять для якої виділяється під

час роботи програми.
Виділення пам'яті для динамічної змінної здійснюється викликом процедури new. У процедури new один параметр — покажчик на змінну того типу, пам'ять для якої треба виділити. Наприклад, якщо р є покажчиком на тип real, то в результаті виконання процедури new(p); буде виділена пам'ять для змінній типу real (створена змінна типу real), і змінна-покажчик р міститиме адресу пам'яті, виділеної для цієї змінної.
У динамічної змінної немає імені, тому звернутися до неї можна тільки за допомогою покажчика.
Процедура, що використовує динамічні змінні, перед завершенням своєї роботи повинна звільнити займану цими змінними пам'ять або, як говорять програмісти, знищити динамічні змінні". Для звільнення пам'яті, займаної динамічної змінної, використовується процедура Dispose, яка має один параметр, — покажчик на динамічну змінну.
Наприклад, якщо р — вказівник на динамічну змінну, пам'ять для якої виділена інструкцією new(p), то інструкція dispose(р) звільняє займану динамічною змінною пам'ять.
Наступна процедура (її текст приведений в лістингу 8.3) демонструє створення, використання і знищення динамічних змінних.

10
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;

Лістинг 8.3. Створення, використання і знищення динамічних змінних

На початку роботи процедура створює три динамічні змінні. Дві змінні, на які указують p1 і р2, набувають значення в результаті виконання інструкції привласнення. Значення третьої змінної обчислюється як сума перших два.

Списки
Вказівники і динамічні змінні дозволяють створювати складні динамічні структури даних,

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

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

Кожен елемент списку (вузол) є записом, що складається з двох частин. Перша частина — інформаційна. Друга частина відповідає за зв'язок з наступним і, можливо, з попереднім елементом списку. Список, в якому забезпечується зв'язок тільки з наступним елементом, називається однозв'язним.
Для того, щоб програма могла використовувати список, треба визначити тип компонентів списку і змінну-покажчик на перший елемент списку. Нижче приведений приклад оголошення компоненту списку студентів:

дані можна в початок, в кінець або в потрібне місце

списку. У всіх цих випадках необхідно коректувати покажчики. На рис. 8.7 зображений процес додавання елементів в початок списку.

додавання другого елементу в список head указує на цей елемент
Рис.

8.7. Додавання елементів в список

Наступна програма (її текст приведений в лістингу 8.4) формує список студентів, додаючи прізвища в початок списку. Дані вводяться в поля редагування діалогового вікна програми (рис. 8.8) і додаються в список натисканням кнопки Додати (Button1).

Лістинг 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)

Рис. 8.8. Вікно програми Динамічний список 1

// покажчик на тип TStudent
TStudent = record
f_name:string[20]; // прізвище

l_name: string[20]; // ім'я
next: TPStudent; // наступний елемент списку
end;
var
head: TPStudent; // початок (голова) списку
// додати елемент в початок списку
procedure TForm1.BtnAddClick(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.BtnShowClick(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+#10 + st)
else ShowMessage('У списку немає елементів.');
end;
end.

елементу в список виконує процедура TForm1.BtnAddClick, яка створює динамічну змінну-запис,

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

Впорядкований список
Як правило, списки впорядковані. Порядок проходження елементів в списку

визначається вмістом одного з полів. Наприклад, список з інформацією про людей зазвичай впорядкований по полю, що містить прізвище.

елементу в список

Додавання елементу в список виконується шляхом коректування покажчиків.

Для того, щоб додати елемент у впорядкований список, потрібно спочатку знайти елемент, після якого потрібно вставити новий. Потім слід скоректувати покажчики. Покажчик нового елементу потрібно встановити на той елемент, на який указує елемент, після якого додається новий. Покажчик елементу, після якого додається новий елемент, встановити на цей новий елемент (рис. 8.9).

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

8.10. Діалогове вікно програми
 Наступна програма (її текст приведений в

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

8.5. Впорядкований динамічний список 2

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, і друга умова в цьому випадку не перевіряється. }

(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;

Tform1.Button1Click створює динамічну змінну-запис, привласнює її полям значення, відповідні вмісту

полів введення діалогового вікна, знаходить відповідне місце для вузла і додає цей вузол в список, коректуючи при цьому значення покажчика вузла next, після якого повинен бути поміщений новий вузол.

Виведення списку виконує процедура TForm1.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. Вікно програми

Implementation
{$R *.DFM}
type TPStudent=^TStudent; //вказівник на тип TStudent
TStudent = record f_name:string[20]; // прізвище l_name:string[20]; // ім'я next: TPStudent; // наступний елемент списку end;
var head: TPStudent; // початок (голова) списку

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 і друга умова в цьому випадку не перевіряється.}

(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;
Memo1.Lines.Add(st);
end;
if n <> 0
then ShowMessage('Список:'+#13+st)
else ShowMessage('В списке нет элементов.');
end;

елемент з списка
procedure TForm1.Button3Click(Sender: TObject);
var
curr: TPStudent; // попередній, перевіряемий

вузол
pre: TPStudent; // попередній вузол
found: boolean; // TRUE - вузол, який необхідно видалити, є в списку
begin
if head = NIL then
begin
MessageDlg('Список пустий!', mtError, [mbOk], 0); Exit;
end;
curr := head; // поточний вузол – перший вузол
pre := NIL; // попереднього вузла немає
found := FALSE;
// знайти вузол, який треба видалити
while (curr <> NIL) and (not found) do
begin
if (curr^.f_name = Edit1.Text) and (curr^.l_name = Edit2.Text) then
found := TRUE // потрібний вузел знайдений
else // до наступного вузла
begin
pre := curr;
curr := curr^.next;
end;
end;

if found then
begin
// потрібний вузол знайдений

if MessageDlg('Вузол буде видалений з списку!', mtWarning, [mbOk, mbCancel], 0) <> mrYes then Exit;
// удаляем узел
if pre = NIL then
head := curr^.next // видаляем перший вузол списка
else
pre^.next := curr.next;
Dispose(curr);
MessageDlg('Вузол' + #13 + 'Ім"я:' + Edit1.Text + #13 + 'Прізвище:' +
Edit2.Text + #13 + 'Видалений з списку.', mtInformation, [mbOk], 0);
end
else // вузла, який потрібно видалити, в списку немає
MessageDlg('Вузол' + #13 + 'Ім"я:' + Edit1.Text + #13 + 'Прізвище:' +
Edit2.Text + #13 + 'в списку не знайдений.', mtError, [mbOk], 0);
Edit1.Text := ''; Edit1.Text := ''; Edit1.SetFocus;
end;

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



Процедура проглядає список від початку, порівнюючи вміст

полів поточного вузла з вмістом полів введення діалогового вікна. Якщо їх вміст співпадає, то процедура просить користувача підтвердити видалення вузла. Якщо користувач натисненням кнопки ОК підтверджує, що вузол повинен бути видалений, то процедура видаляє його. Якщо вузла, який хоче видалити користувач, в списку немає, програма виводить повідомлення про помилку.

двонаправлений список.
“Застосування засобів ООП в лінгвістичних задачах” Корпильов Д.В. 2012
Лекція

№10

Питання:

проектирование с примерами приложений на С++. 2002 г. - 250

с.
Миронченко А.С. Императивное и обьектно-ориентированое программирование на Turbo Pascal и Delphi.
Т.А. Павловская Паскаль. Программирование на языке высокого уровня.: Учебник для вузов. – СПб.: Питер, 2007. -393 с. Ил.
Архангельский А.Я. Программирование в Delphi для Windows. Версии 2006, 2007, Turbo Delphi, 2007 г. - 1248 с.
Гофман В. Э., Хомоненко А. Д. Delphi. Быстрый старт. — СПб.: БХВ-Петербург, 2003. — 288 с: ил.
Шупрута В.В. Delphi 2005. Учимся программировать.

“Застосування засобів ООП в лінгвістичних задачах” Корпильов Д.В. 2012

Лекція №10