Навігація
Головна
 
Головна arrow Інформатика arrow Інформатика
< Попередня   ЗМІСТ   Наступна >

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

Динамічна структура даних розміщується в динамічної пам'яті, її розмір змінюється під час виконання програми: пам'ять виділяється окремими блоками по мірі необхідності. Блоки зв'язуються один з одним за допомогою покажчиків.

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

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

Елемент динамічної структури описується в вигляді запису, наприклад:

type

pnode = ^ node; node = record

d: word; {Інформаційна} s: string; {Частина}

p: pnode; {Покажчик на наступний елемент} end;

ПРИМІТКА

Зверніть увагу, що тип покажчика pnode на запис node визначено раніше, ніж сама запис. Це не суперечить принципу "використання тільки після опису", оскільки для опису змінної типу pnode інформації цілком достатньо.

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

ЛІНІЙНІ СПИСКИ

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

Розглянемо програму, яка формує однозв'язний список з п'яти елементів, що містять число і його текстове представлення, а потім виконує вставку і видалення заданого елемента. Як ключ використовується число: program linked_list; const n = 5; type pnode = ^ node;

node = record {елемент списку} d: word; s: string; p: pnode; end;

var beg: pnode; {Покажчик на початок списку} i, key: word; s: string; option: word;

const text: array [1 .. n] of string =

( 'One', 'two', 'three', 'four', 'five');

{Додавання елемента в кінець списку}

procedure add (var beg: pnode; d: word; const s: string); var p: pnode; {Покажчик на створюваний елемент} t: pnode; {Покажчик для перегляду списку} begin

new (р); {створення елемента}

p ^ .d: = d; p ^ .s: = s; {Заповнення елемента}

р ^ .р: = nil;

if beg = nil then beg: = p {список був порожній} else begin {списку не порожній} t: = beg;

while t ^ .p <> nil do {прохід за списком до кінця} t: = t ^ .p;

t ^ .p: = p; {Прив'язка нового елемента до останнього} end end;

{Пошук елемента по ключу>

function find (beg: pnode; key: word; var p, pp: pnode): boolean; begin

p: = beg;

while p <> nil do begin {1}

if p ^ .d = key then begin {2}

find: = true; exit end;

PP: = p; {3}

P: = р ^ .р; {4}

end;

find: = false; end;

{Вставка елемента>

procedure insert (beg: pnode; key, d: word; const s: string); var p: pnode; {Покажчик на створюваний елемент} pkey: pnode; {Покажчик на шуканий елемент} pp: pnode; {Покажчик на попередній елемент} begin

if not find (beg, key, pkey, pp) then begin

writeln ( 'вставка не виконано'); exit; end; new (p); {1}

p ^ .d: = d; p ^ .s: = s; {2}

p ^ .p: = pkey ^ .p; {3}

pkey ^ .p: = p; {4}

end;

{Видалення елемента}

procedure del (var beg: pnode; key: word); var p: pnode; {Покажчик на видаляється елемент} pp: pnode; {Покажчик на попередній елемент} begin

if not find (beg, key, p, pp) then begin

writeln ( 'видалення не виконано'); exit; end; if p = beg then beg: = beg ^ .p {видалення першого елемента}

else рр ^ .р: = р ^ .р; dispose (р); end;

{Висновок списку}

procedure print (beg: pnode);

var p: pnode; {Покажчик для перегляду списку} begin

Р: = beg;

while p <> nil do begin {цикл за списком} writeln (p ^ .d: 3, p ^ .s); {Висновок елемента} p: = р ^ .р {перехід до наступного елементу списку} end; end;

{Головна програма}

begin

for i: = 1 to 5 do add (beg, i, text [i]); while true do begin

writeln (1 - вставка, 2 - видалення, 3 - висновок, 4 - вихід ');

readln (option); case option of

1: begin {вставка}

writeln ( 'Ключ для вставки?'); readln (key);

writeln ( 'вставляється елемент?'); readln (i); readln (s); insert (beg, key, i, s); end;

2: begin {видалення}

writeln ( 'Ключ для видалення?'); readln (key); del (beg, key); end;

3: begin {висновок}

writeln ( 'Виведення списку:'); print (beg); end;

4: exit; {Вихід} end

writeln;

end

end.

Функція пошуку елемента find повертає true, якщо шуканий елемент знайдений, і false у противному випадку. Оскільки одного факту відшукання елемента недостатньо, функція також повертає через список параметрів два покажчика: на знайдений елемент р і на попередній йому pp. Останній потрібно при видаленні елемента зі списку.

Якщо елемента із заданим ключем в списку немає, цикл перегляду списку завершиться природним чином, оскільки останній елемент списку містить nil в поле р покажчика на наступний елемент.

Вставка елемента виконується після елемента із заданим ключем (процедура insert). Під новий елемент виділяється місце в динамічній пам'яті (оператор {1}), і інформаційні поля елемента заповнюються переданими в процедуру значеннями (оператор {2}). Новий елемент р вставляється між елементами ркеу і наступним за ним (його адреса зберігається в ркеу ^ .р). Для цього в операторах {3} і {4} встановлюються дві зв'язку (рис. 25.3).

Вставка елемента в список

Мал. 25.3. Вставка елемента в список

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

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

procedure print_tree (дерево);

begin

print_tree (левое_поддерево) відвідування кореня print_tree (правое_поддерево)

end;

Наведена функція дозволяє отримати послідовність ключів, відсортовану по зростанню:

1, 6, 8, 10, 20, 21, 25, 30

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

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук