CS50. Семінар 6

На відміну від масивів, вставка та вилучення елементів у Зв'язний список потребують сталого часу (О(1)). Також значною перевагою зв'язних списків є можливість легкого розширення: щоб збільшити розмір списку, треба лише додати ще один елемент.

Недоліком зв'язних списків є необхідність проходити весь список, щоб знайти елемент (тобто час доступу до елемента списку - О(n)).

Елемент зв'язаного списку містить дані та посилання (покажчик) на наступний елемент списку, або NULL, - якщо цей елемент є останнім.

Нижче наведено код структури, що реалізує елемент зв'язаного списку (і власне список). Дані представлені числовим значенням.

typedef struct node
{
  int n;
  struct node* next;
} node;

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

У цьому прикладі для того, щоб знайти елемент "9", необхідно перш за все з голови списку перейти на елемент "2". Потім за посиланням перейти на елемент "3". Лише після цього можна за посиланням знайти елемент "9".

Нижче наведено код функції, яка шукає заданий елемент у списку і повертає true, якщо елемент є у списку, або false, якщо елемента немає у списку.

bool search (node* list, int n)
{
  node* ptr = list;
  while (ptr != NULL)
  {
    if(ptr -> n == n)
    {
      return true;
    }
    ptr = ptr -> next;
  }
  return false;
}

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

Розглянемо вставку в початок списку (оскільки це найбільш часто використовуваний варіант вставки).

1. Створимо новий елемент. Він поки що не посилається на інші елементи, і на нього ніякий інший елемент не посилається.

   

2. Переназначити покажчик нового елементу так, щоб він вказував на той же елемент, на який вказує head.

   

3. Переназначити покажчик head на новий елемент.

   

Важливо зробити кроки 2 і 3 саме в такому порядку. Якщо спершу встановити head на новий елемент, то ми втратимо частину списку.

Нижче наведено код функції для вставки нового елементу на початок списку.

void insert(int n)
{
  //створити новий елемент
  node* new = malloc(sizeof(node));
  
  //перевірка на NULL
  if(new == NULL)
  {
    exit(1);
  }
  
  //ініціалізувати новий елемент
  new->n = n;
  new->next = NULL;
  
  //вставити новий елемент у голову списку
  new->next = head;
  head = new;
}

Елемент двозв'язного списку містить дані та два поля: prev та next, - покажчики на попередній та наступний елементи списку відповідно.

Код структури елемента двозв'язного списку мовою С:

typedef struct node
{
  int n;
  struct node* next;
  struct node* prev;
} node;

Хеш-таблиця - це, масив, у якому місце розташування елемента залежить від значення, яке має сам елемент. Зв'язок між значенням елемента і його позицією у хеш-таблиці задає хеш-функція. Важлива властивість хеш-таблиці: пошук, вставка і видалення елементів з таблиці виконуються за час О(1).

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

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

Приклади: порядковий номер першої букви слова у алфавіті, остача від ділення на 13, тощо.

Нижче наведено код хеш-функції на основі першої літери в рядку:

int hash_function(char* key)
{
  int hash = toupper(key[0]) - 'A';
  return hash % SIZE;
}

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

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

typedef struct node 
{
  // Маркер кінця слова 
  bool is_word; 
  // Покажчики на інші елементи 
  struct node* children[27]; 
} node;

Маємо наступного виду префіксне дерево, у якому є слова bat та zoom:

Переходячи за послідовними посиланнями згори донизу доти, доки не зустрінемо маркер кінця слова, отримаємо слово bat:

Для того щоб вставити слово zoo у масив, необхідно пройти по списку і встановити маркер:

А щоб додати у дерево слово bath, треба в останньому елементі слова bat створити посилання, що вказує на букву h:

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

typedef struct node
{
  int n;
  struct node* left;
  struct node* right;
} node;

У бінарному дереві пошуку все, що справа від батьківського вузла - більше за нього, а все, що зліва - менше.

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

Нижче наведено код функції пошуку елемента у бінарному дереві пошуку.

bool search(node* root, int val)
{
  if(root == NULL)
    return false;
  if(root->n == val)
    return true;
  if(val < root->n)
    return search(root->left, val);
  if(val > root->n)
    return search(root->right, val);
}