GETMEM/FREEMEM

Цими засобами не рекомендовано користуватися одночасно (в одній програмі).

Структури, побудовані на базі показівників:

1. Масиви показівників

2. Лінійні та циклічні однозв'язані списки, стек, черга

3. Лінійні двозв'язані списки

4. Дерева

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

Лінійний та циклічний однозв'язаний список. Кожний окремий елемент такої структури містить крім одного або декількох інформаційних полів поле, в якому зберігається адреса наступного елементу. Останній елемент лінійного списку містить порожнє посилання (nil), тоді як останній елемент циклічного списку містить посилання на перший елемент. Такі структури утворюються та змінюються тільки під час роботи програми.

Стек типу FILO (first input last out) за допомогою лінійного однозв'язного списку може бути побудований наступним чином: список буде зростати з кінця, від елементу з порожнім посиланням на наступний. Кожний черговой елемент буде додаватись перед ним і ставати поточним (доступним для обробки - читання). При читанні останнього (поточного) елементу він знищується і показівник поточного елементу встановлюється на попередній.

Черга типу FIFO (first input first out) також може бути побудована за допомогою лінійного однозв'язного списку. Додавання елементу до черги буде виконуватись в кінець списку (після останнього елементу), а зчитування - з першого елементу з наступним його знищенням. Таким чином треба буде зберігіти два показівники - посилання на перший та останній елементи черги.

Двозв'язний список - такий, кожний елемент якого містить два посилання - на попередній та на наступний елементи. Перший елемент містить пусте посилання на попередній елемент, а останній - пусте посилання на наступний елемент. Такий список також можна зробити циклічним.

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

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

Приклад: Побудувати програму утворення бінарного дерева - реалізація програми «Вгадати тварину». Аналіз наявності вільної пам’яті не реалізовано.

program animals;

uses crt;

type tr=^tree; {опис показівника на тип tree, який описано нижче }

tree= record { тип “вузол дерева” – запис, який містить: інформаційне поле - }

mouse:string; { назва або властивість тварини, що відрізняє її від інших - і }

left,right:tr { посилання на ліве та праве піддерева }

end;

p=^string; { тип - показівник на рядок}

Var

ut,ut1,utr,utl:tr; { змінні – показівники на вузол дерева}

s:string;

ans,new_anim,new_prop:p; { змінні – показівники на рядок:}

fl:boolean; { прапорець для виходу із програми}

pp:pointer; { показівник для фіксування та відновлення стану динамічної пам’яті }

function yes (s:p):boolean;

{ функція аналізує відповідь на запитання s і повертає значення true, якщо вона позитивна }

Begin

write (s^);

readln (s^);

if (s^[1]='y') or (s^[1]='Y') then yes:=true else yes:=false;

end;

function add_node (s:p):tr;

{ функція створює новий вузол дерева як останній в данній гілці; повертає значення показівника на цей вузол; заповнює інформаційну частину нового вузла інформацією із рядка, на який вказує показівник s }

Var

a:tr;

Begin

new (a);

a^.mouse:=s^;

a^.left:=nil;

a^.right:=nil;add_node:=a

end;

Begin

clrscr; writeln (‘Задумайте, будь ласка, тварину, а я її спробую відгадати’);

mark (pp); { фіксуємо поточний стан динамічної пам’яті}

{ ініціалізація майбутнього дерева – створення початкових трьох вузлів і зв’язків між ними:}

new (ut); {виділення місця для збереження змінної типу tree – вершини майбутнього дерева, показівники на неї – змінні ut – поточний- і ut1-фіксований}

s:='миша'; utl:= add _ node (@s);ut^.left:=utl; {створюються і заповнюються }

s:='слон'; utr:= add _ node (@s);ut^.right:=utr; { лівий і правий вузли першого рівня}

ut^.mouse:='великий';

ut1:=ut;

Repeat

ut:=ut1;

repeat { проходження по існуючій структурі - відгадування }

ans^:='Про Вашу тварину можна сказати: «'+ut^.mouse+'»?(y/n)';

if yes (ans) then ut:=ut^.right else ut:=ut^.left;

until ut^.left=nil;

ans^:='Ви задумали тварину - '+ut^.mouse+'?(y/n)';

if not yes (ans) then

begin { доповнення дерева вузлами з новою інформацією}

writeln ('А яку тварину Ви задумали?'); readln (new_anim^);

ut^.left:= add _ node (@ut^.mouse);

ut^.right:= add _ node (new_anim);

writeln ('Яка властивість, на Ваш погляд, її відрізняє?'); readln (new_prop^);

ut^.mouse:=new_prop^;

end;

s:='Бажаєте повторити?';

fl:= yes (@s)

until not fl;

release (pp); { відновлення стану динамічної пам’яті }

writeln (‘Приємно було поспілкуватися’); readln

end.

Поиск по сайту: