Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Лекція
Предмет:
Об’єктно-орієнтоване програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
НУ „Львівська політехніка”
Лекція №10
з курсу: «Застосування засобів об’єктно-орієнтованого програмування в лінгвістичних задачах»
Львів - 2010
Розділ 8. Динамічні структури даних
До цього моменту ми працювали тільки з даними, що мають статичну,
незмінну під час виконання програми, структуру. Під час роботи програми
могли змінюватися тільки значення змінних, тоді як кількість змінних
завжди залишалася постійною (звідси і назва — статичні структури). Це не
завжди зручно.
Наприклад, в програмі, призначеній для введення і обробки даних про
учнів класу, для зберігання даних використовуються масиви. При
визначенні розміру масиву програмістові доводиться орієнтуватися на
деяку середню або граничну кількість учнів в класі. При цьому, якщо
реально учнів в класі менше передбачуваної кількості, то неефективно
використовується пам'ять комп'ютера, а якщо це число більше, то програму
використовувати вже не можна (треба внести зміни до початкового тексту і
виконати компіляцію).
Завдання, оброблювальні дані, які за своєю природою є динамічними,
зручно вирішувати за допомогою динамічних структур.
8.1. Вказівники
Зазвичай змінна зберігає деякі дані. Проте крім звичайних, існують
змінні, які посилаються на інші змінні. Такі змінні називаються
вказівниками. Вказівник — це змінна, значенням якої є адреса іншої
змінної або структури даних. Графічно вказівник може бути зображений
так, як на мал. 8.5.
ВказівникЗвичайна
змінна
Мал. 8.1. Змінна-вказівник
Вказівник, як і будь-яка інша змінна програми, повинні бути
оголошений в розділі оголошення змінних. У загальному вигляді
оголошення вказівник виглядає таким чином:
Ім'я: ^ Тип;
де:
.
ім'я — ім'я змінної-вказівника;
.
Тип — тип змінної, на яку указує змінна- вказівника;
значок ^ показує, що змінна яку оголосили - є вказівник.
Приведемо приклади оголошення вказівника:
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.3. Списки
Вказівники і динамічні змінні дозволяють створювати складні динамічні
структури даних, такі як списки і дерева.
Список можна зобразити графічно (мал. 8.6).
Вказівникна початок спискуДаніДаніДаніДаніNILОстанній елемент
в списку
Мал. 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 указує на цей
елемент
ДаніДаніДаніHeadNILHeadHeadNIL
Мал. 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 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.4. Впорядкований список
Як правило, списки впорядковані. Порядок проходження елементів в
списку визначається вмістом одного з полів. Наприклад, список з
інформацією про людей зазвичай впорядкований по полю, що містить
прізвища.
Додавання елементу в список
Додавання елементу в список виконується шляхом коректування
покажчиків. Для того, щоб додати елемент у впорядкований список,
потрібно спочатку знайти елемент, після якого потрібно вставити новий.
Потім слід скоректувати покажчики. Покажчик нового елементу потрібно
встановити на той елемент, на який указує елемент, після якого додається
новий. Покажчик елементу, після якого додається новий елемент,
встановити на цей новий елемент (мал. 8.9).
ІвановHeadHeadHeadNILNILІвановСидоровСидоровПетров
Мал. 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).
ІвановHeadHeadHeadNILNILІвановСидоровСидоровПетров
Мал. 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.
Процедура проглядає список від початку, порівнюючи вміст полів
поточного вузла з вмістом полів введення діалогового вікна. Якщо їх вміст
співпадає, то процедура просить користувача підтвердити видалення
вузла. Якщо користувач натисненням кнопки ОК підтверджує, що вузол
повинен бути видалений, то процедура видаляє його. Якщо вузла, який
хоче видалити користувач, в списку немає, програма виводить
повідомлення про помилку.
17.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора