Структури даних. Типові статичні та динамічні структури даних. Доступ до даних.

 

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

Статичні структури даних характеризуються тим, що кількість даних і відношення не змінюються в часі.

Динамічні структури даних означають, що кількість даних або відношення (або і перше і друге) модифікується у часі.

Класичною задачею в галузі структур даних є задача інформаційного пошуку в структурах даних.

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

Типовою стандартною статичною структурою даних є масив. Його властивості:

Усі елементи масиву мають один і той же тип.

Усі елементи розташовуються один за одним.

Індекс першого елементу — 0.

Ім’я масиву є вказівником-константою, що дорівнює адресі початку масиву (перший байт першого елемента).

Компілятор відводить для масиву пам’ять N*sizeof(тип_елементів).

Розмір масиву може визначатися як на етапі компіляції (int a[10];), так і на етапі виконання (int *a = new int[input];). На етапі виконання додати до масиву більше елементів, ніж виділено на нього пам’яті, просто так не можна.

Динамічні структури даних — стек, двійкове дерево, контейнери, наприклад, однозв’язні та двозв’язні списки, динамічними масивами, тощо. У мові С++ контейнери представлені в стандартній бібліотеці шаблонів (STL), яка є складовою мови С++.

Розглянемо деякі контейнери детальніше:

vector — С-подібний динамічний масив. Елементи зберігаються в пам’яті послідовно, додавання в кінець масиву здійснюється за допомогою процедури push_back. Доступ до елементів здійснюється за рахунок перевантаженої операції [] так само, як до елементів звичайного масиву:

vector<int> vec; …; for (int i=0; i<vec.size(); ++i) { cout << vec[i];}

list — двозв’язний список, елементи якого зберігаються в довільних ділянках пам’яті.

map — упорядкований асоціативний масив пар елементів, що складаються із ключів та відповідних значень. Ключі повинні бути унікальними. Відрізняється швидким часом пошуку за ключем.

Найпростіший динамічний список можна виготовити самому:

struct ListElement {

int value; // значення, що зберігає елемент списку

ListElement *next_element; // вказівник на наступ ний елемент списку

};

struct List {

ListElement *list_elements;

List(): list_elements(NULL) {}

void addElement(int element) { /* реалізація процедури додавання елемента */}

int getElement(int element_number) {/* реалізація процедури отримання елемента за його номером*/}

};

Аналіз методів подання графів у вигляді динамічних та статичних структур даних. Матриця суміжності

Матриця суміжності це двовимірний масив розміром N*N, де N кількість вершин у графі:

Статичний:

int Graph[N][N];

Динамічний:

int** Graph; //масив массивів (тобто двовимірний масив)

Graph=new int*[N]; //виділяємо пам’ять для масиву вказівників (на масиви)

for (int i=0; i<N; i++)

Graph[i]=new int[N]; // виділяємо пам’ять для кожного рядка

При цьому Graph[i][j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для зваженого графа Graph[i][j] дорівнює вазі ребра (дуги) з вершини i у вершину j (якщо ребра не існує то якійсь домовленій константі – це або дуже велике число, або від’ємне, якщо немає від’ємних ваг).

Просторова складність цього способу O(N²).

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

Матриця інцидентності

Ребро і її вершина називаються інцидентними.

Матриця інцидентності це двовимірний масив розміром N*M:

 

Статичний:

int Graph[N][M];

Динамічний:

int** Graph; //масив массивів (тобто двовимірний масив)

Graph=new int*[N]; //виділяємо пам’ять для масиву вказівників (на масиви)

for (int i=0; i<N; i++)

Graph[i]=new int[M]; // виділяємо пам’ять для кожного рядка

M кількість ребер.

При цьому Graph[i][j] дорівнює 0, якщо вершини i та ребро j не є інцидентними, -1, якщо вершина i є кінцем орієнтованого ребра j, +1, якщо вершина i є початком орієнтованого ребра j. Інколи зручно користуватись означенням, у якому Graph[i][j] рівний вазі ребра (дуги) j, що є інцидентним вершині i.

Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.

Списки суміжності

Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:

Статична структура:

struct NodeType

{

int count; //кількість вершин суміжних з даною

struct

{

int Node; //номер вершини

int Weight; //номер ребер

} List[N]; //масив суміжних вершин та ваг ребер, що їх з’єднують

} Graph[N];

Динамічна(у вигляді масиву однозв’язних списків):

struct NodeType

{

NodeType* next;

struct

{

int Node;

int Weight;

} item;

} *Graph=new NodeType[N];

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.

Список ребер

Статичний:

struct

{

int Node1; //звідки ребро

int Node2; //куди

int Weight; //вага

} Branches[M];

Динамічний (у вигляді списку):

struct NodeType

{

NodeType* next;

struct

{

int Node1;

int Node2;

int Weight;

} item;

} FirstBranch;

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

Статичні підходи застосовують тоді, коли кількість ребер відома наперед (відома на етапі компіляції).

Динамічний підхід застосовують тоді, коли кількість ребер невідома наперед(визначається в процесі виконання).

Парадигма об’єктно-орієнтованого програмування та основні його принципи, їх зміст.

 

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

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

ООП грунтується на трьох основних принципах:

Інкапсуляція, поліморфізм, успадкування.

об’єкти можна розглядати як деяку сукупність даних і способів роботи з ними. Дані можна розглядати як поля запису – характеристики поб’єкта. Користувач та об’єкти програми повинні мати можливість читати дані об’єкта, певним чином їх обробляти та записувати в об’єкт нові занчення. Тут найважливіше значення має принцип інкапсуляції і приховування даних, який означає, що зовнішнім об’єктам і користувачу прямий доступ до даних, як правило, заборонено.

Для реалізації приховування даних в об’єкті зазвичай визначають процедури та функції, які забезпечують необхідні операції з даними: читання обробку, запис. Ці функції і процедури називають методами. Сукупність даних і методів їх читання та запису називається властивостями об’єкта. Середовищем взаємодії об’єктів є повідомлення, які генеруються у результаі виникнення різних подій.

Для організації динамічного розподілу пам’яті до всіх об’єктів закладено методи їх створення – конструктори та методи їх знищення – деструктори.

Типи об’єктів, зокрема, компонентів бібліотек системи розробки, застосувань формуються у вигляді класів (класи – це типи, обумовлені користувачем, де описуються властивості об’єкта, його методи і події, на які він може реагувати. Якби при створенні нового класу все доводилось починати з нуля, то ефективність цього заняття була би мінімальна. Для цього існує важливий принцип ООП – успадкування.

Новий клас може успадкувати властивості, методи, події батьківського класу, на основі якого він створюється.

Третій важливий принцип ООП – поліморфізм – означає можливість визначення методу з одним і тим самим ім’ям, який можна застосувати одночасно до всіх примірників об’єктів ієрархії успадкування. В цьому випадку кожен примірник об’єкта може «замоляти» особливості реалізації цього методу «над собою»