- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Сортування методом вставки в список
В прикладі генерується N випадкових цілих чисел у діапазоні від 0 до 999, будується зв'язний список, в якому на кожен вузол приходиться по одному числу (перший цикл for), потім переставляються вузли, щоб при обході списку числа випливали один по одному (другий цикл for). Для виконання сортування використовується два списки — список уведення (несортований) і список висновку (сортований). У кожній ітерації циклу з уведення віддаляється вузол і вставляється у визначену позицію списку висновку. Код спрощений завдяки використанню ведучих вузлів у кожному списку, що містить посилання на перші вузли. В оголошеннях ведучих вузлів застосований конструктор, тому їх дані ініціалізуються при створенні.
node heada(0, 0); link a = &heada, t = а;
for (int i = 0; i < N; i++)
t = (t->next = new node(rand() % 1000, 0) );
node headb(0, 0); link u, x, b = &headb;
for (t = a->next; t != 0; t = u)
{
u = t->next;
for (x = b; x->next != 0; x = x->next)
if (x->next->item > t->item) break;
t->next = x->next; x->next = t;
}
Звертання порядку проходження елементів списку
Ця функція звертає порядок проходження посилань у списку, повертаючи покажчик останнього вузла, що потім указує на передостанній вузол і т.д. При цьому для посилання в першому вузлі вихідного списку встановлюється значення 0 (null-показник). Для виконання цієї задачі необхідно зберігати посилання на три послідовних вузли списку.
link reverse(link x)
{ link t, y = x, r = 0;
while (y != 0)
{ t = y->next; y->next = r; r = y; y = t; }
return r;
}
Структури даних. Рядки Сортування масиву рядків
Ця програма ілюструє важливу функцію обробки рядків: розташування набору рядків у порядку сортування. Рядки зчитуються в буфер, що досить великий, щоб умістити їх усі. Для кожного рядка в масиві зберігається вказівник. Потім змінюється розташування вказівників, щоб вказівник на самий молодший рядок містився в першу позицію масиву, вказівник на наступну за абеткою рядок — у другу позицію і т.д.
Бібліотечна функція qsort, що у дійсності виконує сортування, приймає чотири аргументи: вказівник на початок рядка, кількість об'єктів, розмір кожного об'єкта і функцію порівняння. Незалежність від типу об'єктів досягається за рахунок сліпого перерозподілу блоків даних, що представляють об'єкти (у даному випадку, вказівники на рядки), а також шляхом використання функції порівняння, що приймає як аргумент покажчик на void. Програма виконує зворотне перетворення цих блоків у тип вказівників на вказівники символів для функції strcmp. Щоб звернутися до першого символу рядка для операції порівняння, розіменовується три вказівники: один для одержання індексу (який є вказівником) елемента масиву, один для одержання вказівника рядка (за допомогою індексу) і ще один для одержання символу (за допомогою вказівника).
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
int compare (const void *i, const void *j)
{ return strcmp(*(char **)i, * (char **)j); }
int main ()
{
const int Nmax = 1000;
const int Mmax = 10000;
char* a[Nmax]; int N;
char buf[Mmax]; int M = 0;
for (N = 0; N < Nmax; N++)
{
a[N] = &buf [M];
if (!(cin >> a[N])) break;
M += strlen(a[N])+l;
}
qsort(a, N, sizeof(char*), compare);
for (int i = 0; i < N; i++)
cout << a[i] << endl;
