ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


ВИДІЛЕННЯ ПАМ’ЯТІ ПІД ДИНАМІЧНУ ЗМІННУ

ДИНАМІЧНІ СТРУКТУРИ ДАНИХ.

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

В таких задачах зручно використовувати структури (подібні до масивів) в яких кількість елементів може змінюватися. Такими структурами є зв’язані список. Зв’язаний список нагадує масив, в якому кількість елементів змінюється під час роботи програми.

Зв’язаний список можна побудувати використовуючи динамічні змінні. Динамічні змінні можна створювати під час роботи програми («на ходу») за допомогою так званих змінних-вказівників.

 

ЗМІННІ-ВКАЗІВНИКИ.

Змінну-вказівник можна уявити як звичайну статичну змінну, але таку, в якій зберігається не деяке конкретне значення (наприклад типу integer, real, …), а адрес іншої змінної.

Змінна-вказівник (р) нагадує конверт, який містить лише адресу квартири Петрова, а не її вміст. Можна сказати, що змінна-вказівник р вказує на іншу змінну, яка знаходиться за адресою вул.. 1-го Травня, 58.

Вміст змінної-вказівника р:

Вул. 1 Травня, 58

Вміст змінної за адресою «Вул. 1 Травня, 58» (ця змінна не має імені):

Квартира Петрова

 

Змінна, що містить значення Квартира Петроване є звичайною статичною змінною – вона динамічна.

- так будемо позначати змінну-вказівник.
Зауваження!!!

 

Запам’ятайте!!!

  1. Статична змінна має назву.
  2. Динамічна змінна назви не має.
  3. До статичної змінної можна звернутися по її назві.
  4. До динамічної змінної – по її адресі (тобто по вказівнику, де ця адреса знаходиться)
  5. Змінна-вказівник може вказувати лише на динамічну змінну. І не може вказувати на статичну.

ОПИС ЗМІННИХ-ВКАЗІВНИКІВ

<Ім’я змінної-вказівника>:^тип динамічної змінної

Наприклад, a:^integer; b:^real;

Щоб змінити значення динамічній змінній, на яку вказує деяка змінна-вказівник z, необхідно виконати команду:

z^:=<значення> (z – це змінна вказівник, а z^ - динамічна змінна, на яку вказує вказівник z).

Щоб змінити значення змінної-вказівника z (направити її на іншу динамічну змінну) необхідно:

z:=<деякий вказівник на іншу динамічну змінну>

 

Формування стеку.

- так будемо позначати змінну-вказівник.
Формувати список можна добавляючи елементи як на початок списку (стек), як в кінець (черга), так і в довільне місце списку.

Зауваження!!!

       
 
   
Список до внесення елемента «Ільчук» в стек
 
 
 
   
Список після внесення елемента «Ільчук» в стек
 

 


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


Приклад 1. Наступна програма демонструє добавляння елемента на початок списку.

type

elem=^zapis;

zapis=record

name:string;

next:elem;

end;

var

a1,a:elem;

begin

new(a1);

a1^.name:='Иванов';

a1^.next:=nil;

writeln(a1^.name);

{Добавимо елемент 'Петров' на початок}

writeln('Формування стеку:');

new(a);

a^.name:='Петров';

a^.next:=a1;

write(a^.name,' ');

a:=a^.next;

writeln(a^.name);

end.

Результат роботи програми:

Иванов

Формування стеку:

Петров Иванов

 

BEGIN

s1:=nil; s:=nil;

repeat

new(s);

readln(name);

if name<>’’ then begin

s^.name:=name;

s^.next:=nil;

if s1=nil then s1:=s;

else sn^.next:=s;

sn:=s;

end;

until name=’’;

while s1<>nil do begin

writeln('--',s1^.name);

s1:=s1^.next;

end;

END.


 

ЗАДАЧІ

ЗАВДАННЯ

  1. Об’єднання двох списків (спочатку елементи першого списку, а потім елементи другого списку)
  2. Об’єднання двох списків (елементи першого та другого списку чередуються)

ДЕРЕВА. БІНАРНЕ ДЕРЕВО.

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

Кореневий вузол (корінь дерева) – це самий верхній вузол (вузол a – кореневий) . Якщо з деякого вузла (наприклад, вузла а) вказівники вказують на інші вузли (в нашому випадку на вузли b та c), то такий вузол називають предком. Вузли ж на які вказують вказівники від предка називаються потомками.

 

Лівий потомок вузла а – вузол b

Правий потомок – вузол c.

Вузли b та c мають спільного предка – вузол а

Якщо вузол не має потомків, то такий вузол називають листком дерева

 

На мал. 1 вершини d, g та f – є листками.

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

 

ВИЗНАЧЕННЯ КІЛЬКОСТІ РІВНІВ БІНАРНОГО ДЕРЕВА (ВИСОТИ ДЕРЕВА).

На малюнку 5 зображено шести-рівневе бінарне дерево. Лівий потомок (6) – 4-х рівневе дерево. Правий потомок (16) 5-ти рівневе дерево. Бачимо, що для того, щоб визначити висоту дерева необхідно до висоти «вищого» потомка додати 1. Виходячи з таких міркування функція визначення висоти дерева (Function height_tree(x:BinarTree):integer) має рекурсивний характер.

Нехай i – висота лівого потомка, а j – висота правого потомка. Тоді:

 

Function height_tree(x:BinarTree):integer;

var

i,j:integer;

begin

if x=nil then height_tree:=0

else

begin

i:=height_tree(x^.left);

j:=height_tree(x^.right);

if i>j then height_tree:=i+1

else height_tree:=j+1;

end;

end;

 

При введенні дерева, зображеного на мал.5, результат роботи функції height_tree наступний:

Висота дерева: 6

 

ЗАВДАННЯ.

1. Напишіть функцію, яка знаходить крайній лівий та крайній правий листки бінарного дерева.

2. Напишіть процедуру видалення вузла з усіма його потомками.

3. Напишіть функцію, яка вертає значення «істина», якщо дерево пусте.


ДИНАМІЧНІ СТРУКТУРИ ДАНИХ.

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

В таких задачах зручно використовувати структури (подібні до масивів) в яких кількість елементів може змінюватися. Такими структурами є зв’язані список. Зв’язаний список нагадує масив, в якому кількість елементів змінюється під час роботи програми.

Зв’язаний список можна побудувати використовуючи динамічні змінні. Динамічні змінні можна створювати під час роботи програми («на ходу») за допомогою так званих змінних-вказівників.

 

ЗМІННІ-ВКАЗІВНИКИ.

Змінну-вказівник можна уявити як звичайну статичну змінну, але таку, в якій зберігається не деяке конкретне значення (наприклад типу integer, real, …), а адрес іншої змінної.

Змінна-вказівник (р) нагадує конверт, який містить лише адресу квартири Петрова, а не її вміст. Можна сказати, що змінна-вказівник р вказує на іншу змінну, яка знаходиться за адресою вул.. 1-го Травня, 58.

Вміст змінної-вказівника р:

Вул. 1 Травня, 58

Вміст змінної за адресою «Вул. 1 Травня, 58» (ця змінна не має імені):

Квартира Петрова

 

Змінна, що містить значення Квартира Петроване є звичайною статичною змінною – вона динамічна.

- так будемо позначати змінну-вказівник.
Зауваження!!!

 

Запам’ятайте!!!

  1. Статична змінна має назву.
  2. Динамічна змінна назви не має.
  3. До статичної змінної можна звернутися по її назві.
  4. До динамічної змінної – по її адресі (тобто по вказівнику, де ця адреса знаходиться)
  5. Змінна-вказівник може вказувати лише на динамічну змінну. І не може вказувати на статичну.

ОПИС ЗМІННИХ-ВКАЗІВНИКІВ

<Ім’я змінної-вказівника>:^тип динамічної змінної

Наприклад, a:^integer; b:^real;

Щоб змінити значення динамічній змінній, на яку вказує деяка змінна-вказівник z, необхідно виконати команду:

z^:=<значення> (z – це змінна вказівник, а z^ - динамічна змінна, на яку вказує вказівник z).

Щоб змінити значення змінної-вказівника z (направити її на іншу динамічну змінну) необхідно:

z:=<деякий вказівник на іншу динамічну змінну>

 

ВИДІЛЕННЯ ПАМ’ЯТІ ПІД ДИНАМІЧНУ ЗМІННУ

Оскільки динамічна змінна не має імені (а отже не описується в блоці var), то на початку роботи програми пам’ять під дану змінну не виділяється. А відповідна змінна-вказівник ні нащо не вказує. Коли змінна-вказівник ні нащо не вказує, то говорять, що вона вказує на nil.

Щоб виділити пам’ять, необхідно виконати процедуру new(x), де х – змінна-вказівник.

Після виконання даної процедури (new(x)) вказівник x буде вказувати на комірку пам’яті відповідного типу.

 

Наприклад,

Var x:^integer;

Begin

……..

New(x);

 

…….

End.

ЗМІНЕННЯ ЗНАЧЕНЬ ДИНАМІЧНИХ ЗМІННИХ
ТА НАПРЯМКІВ ЗМІННИХ-ВКАЗІВНИКІВ

Змінити значення динамічної змінної (нехай на неї вказує вказівник а) можна, використовуючи вказівку:

a^:=<значення>

Щоб змінити напрям вказівникаа необхідно:
a:=<інша змінна-вказівник>

 

Нехай на якомусь етапі роботи програми вказівник a вказує на деяку динамічну змінну, що містить число 5, аb на іншу змінну, що містить число 10 (мал.1)

Після виконання вказівки a^:=10 (або a^:=b^) напрям вказівника aне змінюється, змінюється значення динамічної змінної (в нашому випадку зміниться значення змінної за адресою 1: замість 5 там буде міститися 10) (мал 2)

 

Якщо ж замість a^:=b^ записати a:=b, то напрям вказівника aзмінюється. Змінна-вказівник a буде вказувати на ту ж змінну, що і вказівник b.(мал 3). Тепер значення динамічної змінної, що знаходиться за адресою 2 можна змінити двома способами: використовуючи вказівник a та вказівник b.

Після виконання вказівок:
a:=b;
a^:=100;
b^:=15;
writeln(a^);
на екрані буде число 15 (а не 100)

 

Приклад 1. Демонструє зміну напрямків вказівників на дві незалежні динамічні змінні.

var a,b,c:^byte;

begin

new(a);

new(b);

read(a^,b^);

c:=a;


a:=b;

b:=c;

writeln(a^,' ',b^);

end.

Результат роботи програми:

1 2

2 1

В даній програмі використовується лише дві динамічні змінні (дві комірки пам’яті)

 

Приклад 2. Демонструє перестановку двох динамічних змінних з використанням третьої.

var

a,b,c:^byte;

begin

new(a);

new(b);

new(с);

read(a^,b^);


c^:=a^;

a^:=b^;

b^:=c^;

writeln(a^,' ',b^);

end.

Результат роботи програми:

1 2

2 1

В даній програмі використовується три динамічні змінні (три комірки пам’яті). Вона працює повністю аналогічно як у випадку із звичайними статичними змінними.

Приклад 1 ефективніший за приклад 2, бо

По-перше, використовується дві комірки пам’яті;

По-друге, вміст комірок пам’яті не змінюється.

Проаналізуйте наступну програму:

uses crt;

var

i,p:^integer;

begin

clrscr;

new(p);

new(i);

p^:=5; i^:=1;

writeln('p -> ',p^,' i -> ',i^);

readkey;

i:=p;

writeln('p -> ',p^,' i -> ',i^);

readkey;

p^:=10;

writeln('p -> ',p^,' i -> ',i^);

readkey;

i^:=15;

writeln('p -> ',p^,' i -> ',i^);

readkey;

end.

Результат роботи програми:

p -> 5 i -> 1

p -> 5 i -> 5

p -> 10 i -> 10

p -> 15 i -> 15

Якщо вказівку i:=pзмінити на i^:=p^, то результат програми буде наступним:

p -> 5 i -> 1

p -> 5 i -> 5

p -> 10 i -> 5

p -> 10 i -> 15


ЗВ’ЯЗАНИЙ СПИСОК. СТЕК.

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

Найпростішою з них є зв’язаний список.

Схематично зв’язаний список можна зобразити так:

 

 


a1 – змінна-вказівник

Елемент списку a1^– це динамічна змінна (наприклад типу zapis=record), яка в найпростішому випадку складається з двох полів: інформаційного (наприклад, name:string) та змінної-вказівника на наступний елемент списку (next:^zapis). Тобто, динамічна змінна – елемент списку – крім деякого значення містить адресу (змінну-вказівник) наступного елемента списку.

Спробуємо описати тип динамічної змінної.

Якщо ми назвали тип динамічної змінної zapis, то, здавалося б, цей тип має виглядати так:

type

zapis=record

Pascal цього не дозволить (тоді, як С++ дозволяє)  
name:string;

next:^zapis;

end;

Щоб вийти з цієї ситуації оголосимо спочатку «тип-вказівник» elem на тип zapis:

type

elem=^zapis;

zapis=record

name:string;

next:elem;

end;

 

Список, кожен елемент якого містять вказівник лише на наступний елемент називається однозв’язним.

Список, що містить два вказівники (на попередній та на наступний елементи) – двозвязний.

Формування стеку.

- так будемо позначати змінну-вказівник.
Формувати список можна добавляючи елементи як на початок списку (стек), як в кінець (черга), так і в довільне місце списку.

Зауваження!!!

       
 
   
Список до внесення елемента «Ільчук» в стек
 
 
 
   
Список після внесення елемента «Ільчук» в стек
 

 


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


© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти