Стек. Загальні поняття.

Стек (англ. stack - стопка) - структура даніх, в якій доступ до елементів організованій за принципом LIFO (англ. last in - first out, «останнім прийшов - Перша Вийшов»). Найчастіше принцип роботи стека порівнюють Зі стопки тарілок: щоб взяти одного зверху, потрібно зняті верхні.

Додавання елемента, звання кож проштовхуванням (push), можливости Тільки в вершину стека (Доданий елемент стає Першим зверху). Відалення елемента, звання кож віштовхуванням (pop), теж можливости Тільки з вершини стека, при цьому другий зверху елемент стає верхнім.

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

Приклад використання стеку

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

Исходный код:

#include <stdio.h>

int mas[10];

int count=0;

void push(int a)

{

mas[count]=a;

count++;

}

int pop()

{

if (count==0)

{

printf("Стек пуст");

return 1;

}

count--;

return mas[count];

}

main()

{

push(1);

push(2);

push(3);

while (count>0)

{

printf("Рузультат: %d\n", pop());

}

}

Питання для контролю:

7. Що таке стек?

8. Як занести значення в стек?

9. Як видалити значення зі стеку?

Література:

1. Д. Рассохин, “От С к С++” , Москва, “Едель” 2003 г., с. 467-471

Урок №66

(згідно робочої навчальної програми)

Тема: Дерева

Питання:

1. Основні визначення

1. Приклад використання дерев

Основні визначення

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

Дерево - це зв'язний граф без циклів.

Дерево - це зв'язний граф, в якому при N вершинах завжди рівно N-1 ребро.

Дерево - це граф, між якими двома вершинами якого існує рівно один шлях.

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

Кореневе дерево - це орієнтоване дерево, в якому можна виділити вершини трьох видів: корінь, листя (інша їх назва: термінальні вершини) і інші вершини (нетермінальні); причому повинні виконуватися дві обов'язкові умови:

з листя не виходить жодна дуга; з інших вершин може виходити скільки завгодно дуг;

в корінь не заходить жодна дуга; під всі інші вершини заходить рівно по одній дузі.

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

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

Бінарне дерево - це кореневе дерево, кожна вершина якого має не більше двох нащадків. У такому випадку іноді говорять про лівому нащадку і правом нащадку для поточної вершини.

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

І на закінчення ми наведемо визначення, що зв'язує довільні графи з деревами більш щільно.

Каркас графа - це дерево, отримане після викидання з графа деяких ребер.

Прикладом каркаса є (кореневе) дерево найкоротших шляхів від деякої виділеної вершини (вона буде коренем каркаса) до всіх інших вершин графа.