русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Покажчик


Дата додавання: 2014-11-27; переглядів: 858.


на вершину

 

 

Рис. 13.8. Граф – динамічна структура загального вигляду.

 

Граф утворюють декілька записів, покажчики яких виставлені довільним чином. У програмуванні використовуються і інші типи динамічних інформаційних структур (двозв’язні списки, кільця, і т.д.).

Ще раз відмітимо, що використання посилань частіше всього – чисто технічний прийом. Пам’ять для розміщення змінної може виділятись автоматично при виклику процедури і звільнятись при виході з неї. Однак явне використання посилань дозволяє використовувати при програмуванні більш різноманітні структури. Тому у сучасних мовах програмування (зокрема, в Паскалі) введені засоби, що маніпулюють як даними, так і посиланнями на них.

13.2. Посилальний тип даних. Посилання

Значеннями посилального типу даних є посилання (покажчики) на інші дані. Посилальні типи описуються у розділі типів наступним чином:

Type <ім’я посилального типу > = ^ <ім’я базового типу >

Ім’я змінної може бути зв’язано з описанням її типу безпосередньо в розділі змінних, або з іменем типу, вже описаного в розділі типів. Стиль мови віддає перевагу явному використанню імен типів.

Приклади описань:

1. Type

Vector = Array[1..100] of Integer;

Place = ^ Vector;

Var

a, b: Place;

або

Var

a, b: ^ Array[1..100] of Integer;

 

2. Type

Item = Record

Name: String[20];

Age: Integer

end;

Point = ^ Item;

Var

x, y: Point;

 

Якщо p – покажчик на змінну типу Т, то p^ – позначення самої цієї змінної. Ця система позначень може бути продемонстрована так:

 

змінна типу ^T змінна типу T

 

Рис. 13.9. Покажчики на змінні та змінні.

 

Ще раз укажемо на те, що при описанні посилальної змінної p пам’ять резервується тільки для неї. Значенням p по суті є початкова адреса розміщення p^ у пам’яті.

Для резервування пам’яті під дане типу Т^у мові використовується процедура New.

New (< змінна посилального типу >)

Виконання процедури New(p) полягає у заповненні комірки пам’яті, відведеної під змінну p початковою адресою ділянки пам’яті, в якій буде розміщено значення p^. Розмір цієї ділянки визначається типом змінної p.

Для звільнення пам’яті, відведеної раніш під T^, використовується процедура Dispose.

Dispose(<змінна посилального типу>)

 

Приклад 13.3.

 

Program ExamNewDis;

Type

Vector = Array[1..100] of Integer;

Place = ^Vector;

Item = Record

Name: String[20];

Age: Integer

end;

Point = ^Item;

Var

a, b: Place;

x, y: Point;

i: Integer;

Begin

New(x);

New(y);

Read(x^.Name);

Read(x^.Age);

y^ := x^;

Dispose(x);

New(a);

For I:= 1 to 100 do a^[i] := Sqr(i)+1;

b := a;

Dispose(a);

End.

 

Тут при зверненні до процедури New(x) буде відведено 22 байта під x^, при виконанні New(y) - 22 байта під y^, а при виконанні New(a) - 200 байт під a^. (Ми вважаємо, що під ціле число відводиться 2 байта). Оператор y^ := x^ пересилає дані з запису x^ у запис y^. Пам’ять, яку займає x^, звільняється оператором Dispose(x). Для переводу покажчика з одного даного на інше використовується оператор присвоювання. Нехай, наприклад, p і q - змінні одного посилального типу і має місце ситуація

 
 


P

Q

Тоді після виконання оператора p := q схема зміниться:

 
 


P

Q

Рис. 13.10. Виконання оператора присвоювання з покажчиками.

Зверніть увагу на те, що дані, на які до присвоювання посилалась p, стають недоступними! У прикладі, що розглядається, посилання b встановлено оператором b := a на масив a^. Тому оператор Dispose(a), звільняючи пам’ять, позбавить захисту не тільки масив a^, але й масив b^! Тому наступний оператор New може розмістити дані на місці масиву b.

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

13.3. Програмування динамічних структур даних

Найпростіші характерні прийоми обробки динамічних структур даних розглянемо на наступному прикладі:

 

Приклад 13.4.

а) Побудувати динамічну структуру даних, що зображена на рисунку 13.11:

 

First

 

Рис. 13.11.

 

(Дано хі - цілі числа.)

б) Прочитати дані в наступній послідовності x1 x4 x3 x1, x1 x2 x3.

Розв’язок.

Тип елемента структури визначимо наступним чином:

Type

Point = ^ Item;

Item = record

Data: Integer;

Right, Left: Point

End;

 

Для побудови структури використовуємо дві змінні типу Point - p і First.

 

Program Structure;

Type

Point = ^ Item;

Item = Record

Data: Integer;

Right, Left: Point

End;

Var

First: Point;

 

Procedure Build( Var First: Point);

Var p: Point;

Begin

New(p);

First := p;

Read(p^.Data); {побудований перший елемент структури}

New(p^.Left);

Read(p^.Left^.Data); {побудований другий елемент структури}

New(p^.Right);

Read(p^.Right^.Data); {побудований четвертий елемент структури}

p := p^.Left;

New(p^.Left);

p := p^.Left; Read(p^.Data);

p^.Right := Nil;

p^.left := First; {побудований третій елемент структури}

p := First^.Right; {p установлений на 4-ий елемент }

p^.Left := First^.Left;

p^.Right := First^.Left^.Left; {покажчики виставлені. Побудова закінчена}

End;

 

Procedure ReadGraph(First: Point);

Var p: Point;

Begin

{початок блока читання}

Writeln('x1,x4,x3,x1:');

p := First;

Write(p^.Data,'');

p := p^.Right;

Write(p^.Data,'');

p := p^.Right;

Write(p^.Data,'');

p := p^.Left;

Write(p^.Data,'');

p := First;

Writeln; Writeln('x1,x2,x3:');

Write(p^.Data,'');

p := p^.Left;

Write(p^.Data,'');

p := p^.Left;

Write(p^.Data,'');

Writeln('Кінець роботи')

End;

 

Begin

Build(First);

ReadGraph(First);

end.

 

Посилання p використовувалось для обходів структури, а First – як покажчик на початковий елемент структури.

13.4. Стеки, списки, черги

У цьому розділі розглядаються процедури, що реалізують стандартні засоби роботи зі списками: пошук елемента, вилучення елемента, вставка елемента. Аналогічними засобами користуються і при обробці інших інформаційних структур. Елемент списку описується наступним чином:

 

Type

Point = ^ Item;

Item = Record

Data: Integer;

Next: Point

End;

 

Відмітимо характерну деталь: описання елемента динамічної структури рекурсивне! Таким чином, описання динамічних структур неможливе без явного описання типів елементів цих структур.


 

 
 



<== попередня лекція | наступна лекція ==>
Конструктора | Місце вставки елемент, що вилучається


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн