Складна Структура Даних

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

У C структури (struct) забезпечують гнучкий спосіб реалізації багатьох із цих структур даних.

Зв'язані списки

Зв'язаний список корисний, коли кількість елементів може змінюватися динамічно. Кожен вузол містить дані та вказівник на наступний вузол.

Приклад структури вузла:

struct Node {
    int data;           // data in node
    struct Node* next;  // pointer to next node
};

Кожен вузол містить поле data та вказівник next. Це дозволяє додавати або видаляти елементи в будь-якому місці списку без необхідності реорганізовувати всю структуру, на відміну від масивів.

Хеш-таблиця

Хеш-таблиці дозволяють швидко отримувати дані за ключем. Хеш-функція перетворює ключ на індекс масиву, де зберігається значення.

Приклад реалізації хеш-таблиці:

struct Node {
    char* key;          // key
    int value;          // value
    struct Node* next;  // pointer to next node
};

struct HashTable {
    struct Node** table; // array of node pointers
    int size;            // table size
};

unsigned int hashFunction(char* key, int size) {
    unsigned int hash = 0;
    while (*key) {
        hash += *key++;
    }
    return hash % size;
}

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

Дерева

Дерева корисні для ієрархічних даних, швидкого пошуку, вставки та видалення.

Бінарне дерево — це дерево, в якому кожен вузол має не більше двох нащадків: лівого та правого.

Приклад реалізації бінарного дерева:

struct node
{
	int data;
	struct node* left; 
	struct node* right; 
};

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

Стек

Використовується для моделювання мереж і взаємозв'язків.

Стек — це структура даних, у якій елементи додаються (push) і видаляються (pop) за принципом LIFO — (останній прийшов, перший пішов).

Приклад стека на основі масиву:

// Stack structure
typedef struct {
    int data[MAX_SIZE]; 
    int top;
} Stack;

MAX_SIZE – максимальна кількість елементів, яку може містити стек.

// Push an element onto the stack
void push(Stack *stack, int value) {
    stack->data[++stack->top] = value;  // Increment top and add the element
    printf("Element %d pushed onto the stack\n", value);
}

// Pop an element from the stack
int pop(Stack *stack) {
    int value = stack->data[stack->top--];  // Retrieve the element and decrement top
    printf("Element %d popped from the stack\n", value);
    return value;
}

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

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