- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
Визначимо АТД стека через оголошення загальнодоступних функцій. При цьому передбачається, що представлення стека і будь-який інший код, що залежить від реалізації, є приватними, щоб можна було змінювати реалізації, не змінюючи код клієнтських програм. Крім того, у цьому інтерфейсі застосовується шаблон, що дозволяє програмам-клієнтам використовувати стеки, що містять об'єкти будь-яких класів, а в реалізаціях використовувати ключове слово Item як позначення типу об'єктів стека. Аргумент конструктора STACK задає максимальна кількість елементів, який можна помістити в стек.
template <class Item>
class STACK {
private: // програмний код, що залежить від реалізації
public:
STACK(int);
int empty() const;
void push(Item item);
Item pop();
}
Реалізація черги fifo на базі масиву
До вмісту черги відносяться всі елементи масиву, розташовані між індексами head і tail; при цьому враховується перехід з кінця на початок масиву. Якщо індекси head і tail рівні, черга вважається порожній, однак якщо вони стали рівними в результаті виконання операції put, черга вважається повною. Як звичайно, перевірка на такі помилкові ситуації не виконується, але розмір масиву робиться на 1 більше максимальної кількості елементів черги, очікуване програмою-клієнтом. При необхідності програму можна розширити, включивши в неї подібного роду перевірки.
template <class Item>
class QUEUE
{
private:
Item *q; int N, head, tail;
public:
QUEUE(int maxN)
{q = new ltem[maxN+l];
N = maxN+1; head = N; tail = 0;}
int empty () const
{return head % N = tail;}
void put(Item item)
{q[tail++] = item; tail = tail % N;}
Item get()
{head = head % N; return q[head++];}
}
Реалізація черги fifo на базі зв'язного списку
Розходження між чергою FIFO і стеком магазинного типу полягає в тому, що нові елементи вставляються в кінець списку, а не в його початок. Отже, у цьому класі зберігається покажчик tail на останній вузол списку, і, таким чином, функція put може додавати в список новий вузол, зв'язуючи його з вузлом, на який посилається покажчик tail, а потім обновляючи покажчик tail так, щоб він указував уже на новий вузол. Оскільки нові вузли завжди вставляються в кінець списку, конструктор вузлів може встановлювати в null поле покажчика кожного нового вузла й одержувати тільки один аргумент.
template <class Item>
class QUEUE {
private:
struct node
{ Item item; node* next;
node (Item x)
{
item = x; next = 0;
}
};
typedef node *link;
link head, tail;
public:
QUEUE(int)
{ head = 0; }
int empty () const
{ return head ==0; }
void put (Item x)
{ link t = tail;
tail = new node(x);
if (head == 0)
head = tail;
else t->next = tail;
}
Item get()
{Item v = head->item;
link t = head->next;
delete head; head = t; return v;
}
};
Перетворення з інфіксної форми в постфіксну
Ця програма є ще одним прикладом програми-клієнта для стека магазинного типу. У даному випадку стік містить символи. Для перетворення (А+В) у постфиксну форму АВ+ ліва дужка ігнорується, у вихідний потік записується А, у стеці запам'ятовується знак +, у вихідний потік записується В і потім при зустрічі правої дужки зі стека витягається знак + і він же записується у вихідний потік.
#include <iostream.h>
#include <string.h>
#include "STACK.cxx"
int main(int argc, char *argv[])
{char *a = argv[l] ; int N = strlen(a);
STACK<char> ops(N);
for (int i = 0; i < N; i++)
{
if (a[i] == ')')
cout << ops.pop () << " " ;
if ((a[i] == ' + ') || <a[i] = '*'))
ops.push(a[i]);
if <(a[i] >= '0') && (a[i] <= '9'))
cout << a[i] << " ";
}
cout << endl;
}
