10

10. РЕКУРСИВНІ СТРУКТУРИ ДАНИХ

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

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

Динамічні структури даних також часто називають рекурсивними. Ми вже зустрічались з рекурсивними алгоритмами та програмами. Аналогічно рекурсивним програмам, рекурсивні структури даних у своєму описі посилаються самі на себе. Взагалі поняття динамічних структур даних є більш широким, ніж поняття рекурсивних структур даних, але в цьому розділі ми будемо розглядати саме рекурсивні структури даних, їх визначення, реалізацію та використання. На відміну від попередніх розділів, ми не будемо використовувати алгоритмічну мову, а всі поняття будемо розглядати з точки зору їх реалізації у мовах програмування Паскаль та Сі.

10.1. Статична та динамічна пам’ять

Пам’ять комп’ютера, яку системи програмування виділяють для роботи програм, можна поділити на 4 частини:

1. Програмний код.

2. Дані.

3. Програмний стек.

4. Купа.

Пам’ять під програмний код призначена для збереження програм у внутрішньому представленні системи програмування або у машинних кодах.

Пам’ять під дані призначена для збереження статичних даних програм (глобальних змінних та констант).

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

Купа призначена для динамічного розподілу пам’яті під структури даних.

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

Визначають дві базові операції над динамічною пам’яттю (купою): „виділити блок пам’яті” та „звільнити блок пам’яті”. Блоком називають неперервну ділянку пам’яті визначеного розміру. У деякий момент роботи програми купу можна представити у вигляді двох списків (Рис. 10.1): список зайнятих блоків (L1) та список вільних блоків (L2).

Після отримання команди на виділення блоку пам’яті (Рис. 10.1 а) ) програма, що керує купою, шукає у списку вільних блоків блок пам’яті потрібного розміру (або більше) та заносить його у список зайнятих блоків, повертаючи посилання на цей блок (Рис. 10.1 б) ). Якщо блок потрібного розміру не знайдено, виникає помилка.

Після отримання команди на звільнення блоку пам’яті (Рис. 10.2 а) ) програма, що керує купою, звільняє цей блок, можливо об’єднавши його з сусідніми вільними блоками, якщо такі є (Рис. 10.2 б) ).

Рис. 10.1 - Виділення блоку пам’яті

Рис. 10.2 - Звільнення блоку пам’яті m

10.2. Вказівники

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

Можна вважати, що вказівник вказує на початок деякого блоку пам’яті або на деяку змінну, яку ми так і будемо називати: „змінна, на яку вказує вказівник” (Рис. 10.3).

Рис. 10.3 – Графічне зображення вказівників

Розглянемо реалізацію вказівників у мовах Паскаль та Сі.

У мові Паскаль опис типу вказівника та змінної цього типу виглядає так:

type t = ^t;

var p: t;

де t - тип вказівника, t – тип змінної, на яку вказує вказівник. Наприклад:

type pint = ^integer;

pchar = ^char;

Для вказівників у Паскалі визначено такі операції, відношення та інструкції:

1. операції

- розіменування вказівника

_^ : t -> t

наприклад, p^ за вказівником p дає змінну, на яку вказує вказівник.

- отримання адреси змінної

@_ : t -> t

наприклад, @x дає адресу змінної x (вказівник на x).

2. відношення

для вказівників визначені відношення = та <>.

3. інструкції

- виділення пам’яті

new(_)

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

- звільнення пам’яті

dispose(_)

dispose(p) звільняє блок пам’яті, на який вказував вказівник p (Рис. 10.4 б) ). Після цього значення змінної, на яку вказує вказівник p, стає недосяжним.

Рис. 10.4 – Виділення, звільнення пам’яті та константа nil

- присвоєння, наприклад, після присвоєння p1:=p2 (Рис. 10.5 а), б) ) вказівник p1 буде вказувати на той самий блок пам’яті, що й p2. Присвоєння для вказівників треба відрізняти від присвоєння для змінних, на які вони вказують, яке записують з використанням розіменування. Наприклад, присвоєння p1^:=p2^ копіює значення змінної, на яку вказує p2, у змінну, на яку вказує p1 (Рис. 10.5 а), в) ).

Рис. 10.5 – Присвоєння для вказівників та присвоєння для змінних, на які вони вказують

Для вказівників у Паскалі також визначено константу nil. Nil - це вказівник, що не вказує на жодну клітинку пам’яті (Рис 10.4 в) ). Значення nil часто використовують у реалізації рекурсивних структур даних для позначення завершення структури.

Роботу із вказівниками та побудову рекурсивних структур даних розглянемо на прикладі стеку. Визначимо стек як:

1. Порожній стек.

2. Верхівка стеку; стек.

Читати це означення треба так: стек – це або порожній стек, або верхівка стеку, за яким слідує стек.

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

Рис. 10.6 – Стек

Операції, відношення та інструкції для стеків:

1. Почати роботу.

2. Чи порожній стек?

3. Вштовхнути елемент у стек.

4. Верхівка стеку.

5. Забрати верхівку стеку.

Дії 1, 3, 5 – інструкції; 2 – відношення; 4 – операція.

“Почати роботу” означає створити порожній стек.

“Вштовхнути елемент у стек” – додати до стеку один елемент, який стає верхівкою стеку.

“Верхівка стеку” – повернути верхній елемент. Стек при цьому не змінюється. Для порожнього стеку ця операція повинна давати відмову.

“Забрати верхівку стеку” – видалити верхній елемент. Верхнім стає попередній елемент стеку або стек стає порожнім. Для порожнього стеку ця інструкція повинна давати відмову.

Можлива реалізація стеку з використанням вказівників зображена на Рис. 10.7. Стек реалізовано, як вказівник на верхній елемент. Якщо стек порожній, то елементів немає, а вказівник на верхівку дорівнює nil. Елементи стеку – це записи з двох полів: поле даних та вказівник на попередній елемент. За допомогою вказівника елементи стеку з’єднані у ланцюг. У першому елементі вказівник на попередній елемент дорівнює nil.

Рис. 10.6 – Реалізація стеку

Розглянемо модуль реалізації стеку символів.

{ Стек символів }

unit ChStack;

interface

type stack = ^selem; { Стек }

selem = record { Елемент стеку }

d: char;

next: stack

end;

procedure Init(var s: stack); { Почати роботу }

function Empty (s: stack): boolean; { Чи порожній стек? }

procedure Push (var s: stack; c: char); { Вштовхнути елемент у стек }

function Top (s: stack): char; { Верхівка стеку }

procedure Pop (var s: stack); { Забрати верхівку стеку }

implementation

procedure Init(var s: stack);

begin

s := nil

end;

function Empty (s: stack): boolean;

begin

Empty:= s=nil

end;

procedure Push (var s: stack; c: char);

var p: stack;

begin

new(p); p^.d := c; p^.next := s;

s := p

end;

function Top (s: stack): char;

begin

if s = nil then begin

writeln(' Top: Стек порожній'); halt

end;

Top := s^.d

end;

procedure Pop (var s: stack);

var p: stack;

begin

if s = nil then begin

writeln(' Pop: Стек порожній'); halt

end;

p:=s; s:= s^.next; dispose(p)

end;

end.

У описах типів ми спочатку описуємо тип вказівника (stack),

type stack = ^selem;

а потім тип елемента стеку, на який вказує вказівник (selem).

selem = record

d: char;

next: stack

end;

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

Почати роботу зі стеком (процедура Init) – це просто присвоїти вказівнику на верхівку стеку значення nil.

Перевірити, чи стек порожній (функція Empty), означає порівняти вказівник на верхівку стеку з nil.

Зміни стеку під час дії „вштовхнути елемент” (процедура Push) зображені на Рис. 10.7. Після new(p) (Рис. 10.7 а) ) виділяється пам’ять під новий елемент стеку. Ланцюг p^.d:=c; p^.next:=s (Рис. 10.7 б) ) забезпечує запис символа c у поле даних та зв’язування нового елемента з поточною верхівкою стеку. Дійсно, p^ дає змінну, на яку вказує вказівник. Ця змінна є записом, отже p^.d та p^.next – це відповідні поля цього запису. s:=p змінює вказівник на верхівку стеку (Рис. 10.7. в) ). Пунктирна стрілка тут і далі позначає розірваний зв’язок.

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

Рис. 10.7 – Додавання елемента у стек

Зміни стеку під час дії „забрати верхівку стеку” (процедура Pop) зображені на Рис. 10.8. Після p:=s запам’ятовуємо вказівник на верхівку стека у змінній p (Рис. 10.8 а) ). s:=s^.next змінює вказівник на верхівку стеку (Рис. 10.8 б) ). dispose(p) звільнає пам’ять, яку займав колишній верхній елемент стеку (Рис. 10.8 в) ).

Рис. 10.8 – Видалення верхівки стеку

Покажемо використання модуля стеку символів для розв’язку такої задачі. Вводиться послідовність символів, яка завершується символом ‘#’. Треба показати цю послідовність у зворотньому порядку.

У програмі Inversion послідовність символів, що введена, записується у стек. Потім символи забираються зі стеку та виводяться на екран у зворотньому порядку.

{ Запис послідовності символів у зворотньому порядку }

program Inversion;

uses ChStack;

const EndCh = '#';

var s: stack; c : char;

begin

Init(s);

writeln('Введіть послідовність символів. Кінец введення - ',EndCh);

read(c);

while c <> EndCh do begin

Push(s,c); read(c)

end;

writeln('Послідовність у зворотньому порядку');

while not Empty(s) do begin

write(Top(s));

Pop(s)

end;

writeln;

end.

Модуль ChStack та програма Inversion демонструють стандартний підхід до використання вказівників. Воно обмежене модулем, а програма тільки викликає підпрограми, що реалізують дії над стеком. Обмеження використання вказівників обумовлене небезпекою, пов’язаною з безпосередньою роботою з пам’яттю. Дійсно, розглянемо ланнцюг:

new(p2); … p1:=p2; dispose(p2)

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

У мові Сі вказівники мають більш широке застосування, ніж у Паскалі. Зокрема, вказівники використовуються не тільки для організації динамічних структур даних, але й для передачі параметрів підпрограм. Масиви та рядки теж є, по суті, вказівниками на початок масиву або рядка. Опис вказівника на змінні деякого типу t:

t *p;

наприклад,

int *pit;

char *pch;

У Сі визначені такі операції, відношення та інструкції для вказівників:

1. операції

- розіменування вказівника

*_ , наприклад, *p за вказівником p дає змінну, на яку вказує вказівник.

- отримання адреси змінної

&_ , наприклад, &x дає адресу змінної x.

- арифметичні операції додавання та віднімання цілого числа i:

p+i повертає адресу, яка більша p на i елементів типу t,

p-i повертає адресу, яка менша p на i елементів типу t.

- знаходження різниці вказівників

p1-p2 повертає ціле число, яке є різницею значень p1 та p2.

2. відношення

для вказівників визначені стандартні відношення =, !=, >, <, >=, <=.

3. інструкції

- виділення пам’яті

malloc(_)

p = malloc(n) виділяє у динамічній пам’яті блок пам’яті, який має розмір, рівний або більший n байт. Вказівник p буде вказувати на початок цього блоку пам’яті. Функція malloc повертає вказівник на тип void.

- звільнення пам’яті

free(_)

free(p) звільняє блок пам’яті, на який вказував вказівник p. Функції malloc() та free() описано у бібліотеці stdlib.h.

- присвоєння, наприклад, після присвоєння p1=p2 вказівник p1 буде вказувати на той самий блок пам’яті, що й p2. Присвоєння для змінних, на які вказують вказівники, записують з використанням розіменування: *p1=*p2.

- збільшення та зменшення вказівника на одиницю

p++ або p--

збільшує або зменшує адресу на один елемент типу t.

Роль константи nil у мові Сі грає NULL.

Зауваження. Операції додавання та віднімання цілого числа, різниці вказівників, відношення >, <, >=, <=, інструкції збільшення та зменшення вказівника на одиницю мають сенс тільки тоді, коли два вказівники вказують на один масив (рядок) у пам’яті.

Розглянемо тепер реалізацію стеку символів у мові Сі. Модуль для реалізації стеку розміщено у 2 файлах: stack.h, stack.c. У файлі stack.h описано типи даних для елемента стеку (struct selem) та стеку (stack) а також заголовки функцій для реалізації дій над стеком. Оскільки у функціях init, push та pop стек є результатом або модифікованим параметром, ми використовуємо вказівник на стек *sp. У Сі, як і у Паскалі, ми спочатку описуємо тип вказівника stack, а потім структуру struct selem.

/* Стек символів stack.h */

typedef struct selem *stack; /* Стек */

struct selem { /* Елемент стеку */

char d;

stack next;

};

extern int stack_error; /* Код помилки */

extern void init(stack *sp); /* Почати роботу */

extern int empty(stack s); /* Чи порожній стек? */

extern void push(stack *sp, char ch); /* Вштовхнути елемент у стек */

extern char top(stack s); /* Верхівка стеку */

extern void pop(stack *sp); /* Забрати верхівку стеку */

У файлі stack.c описано реалізацію дій над стеком. Ця реалізація відрізняється від описаної вище для Паскаля обробкою виключних ситуацій. Замість генерації відмов безпосередньо у модулі, використовується змінна stack_error, яка зберігає код останньої помилки (0, якщо все норамльно). Виклик

p = (stack) malloc(sizeof(struct selem));

виділяє пам’ять під елемент стеку розміром sizeof(struct selem) та явно приводить вказівник до типу stack. Позначення “->” використовується у Сі як альтернативне для вибору поля запису, на який вказує вказівник. Тобто, замість (*p).d пишемо p -> d, щоб не ставити дужки.

/* Стек символів stack.c */

#include <stdlib.h>

#include "stack.h"

int stack_error = 0;

void init(stack *sp)

{

*sp = NULL;

stack_error = 0;

}

int empty(stack s)

{

return s == NULL;

}

void push(stack *sp, char ch)

{

stack p;

p = (stack) malloc(sizeof(struct selem));

p -> d = ch; p -> next = *sp; *sp = p;

}

char top(stack s)

{

if (s == NULL)

{

stack_error = 2;

return 0;

}

else return s -> d;

}

void pop(stack *sp)

{

stack p;

p = *sp;

if (p == NULL) stack_error = 3;

else

{

*sp = p -> next;

free(p);

}

Програма, яка записує введену послідовність символів у звортньому порядку, наведена нижче. У цій програмі функція process_error аналізує код помилки, видає повідомлення та аварійно завершує роботу програми. Сама програма викликає функцію process_error, якщо код помилки останньої дії не дорівнює 0.

/* Inversion */

#include <stdio.h>

#include <stdlib.h>

#include "stack.h"

#define ENDCH '#'

void process_error()

{

switch (stack_error)

{

case 2: printf("*** Неможливо взяти верхівку порожнього стеку ***\n");

break;

case 3: printf("*** Неможливо забрати елемент з порожнього стеку ***\n");

break;

}

exit(1);

}

main()

{

stack s;

char ch;

printf("Введіть послідовність символів до %c\n", ENDCH);

init(&s);

while (1)

{

scanf("%c",&ch);

if (ch == ENDCH) break;

push(&s,ch);

}

printf("Послідовність у зворотньому порядку\n");

while (!empty(s))

{

printf("%c",top(s));

if (stack_error != 0) process_error();

pop(&s);

if (stack_error != 0) process_error();

}

printf("\n");

}

[ЗМІСТ] [Далі] [Назад]