Попередня Змiст Наступна

ГЛАВА 2. СТРУКТУРИ ДАНИХ

2.1. Структури даних

  Означення 2.1 Опис складних об'єктів засобами більш простих типів даних, які безпосередньо представляються у машині, називається структурами даних.
  Означення 2.2 Списком (довжини n) називається впорядкована послідовність елементів a1, a2, ..., an. Список розміру 0 називається порожнім.
  Означення 2.3 Список можна реалізувати або за допомогою масиву або за допомогою зв'язування його елементів вказівниками (зв'язаний список). У зв'язаному списку елементи лінійно впорядковані, їх порядок визначається вказівниками, що входять у склад елементів списку.
  Означення 2.4 Елемент двостороннього зв'язаного списку містить три поля: ключ та два вказівники - наступний та попередній. В односторонньому зв'язаному списку відсутнє поле "попередній". У впорядкованому списку елементи розташовані в порядку зростання ключів на відміну від невпорядкованого списку.
  Означення 2.5 Стеки та черги - це динамічні множини (або спеціальні типи списків), в яких елемент що додається, визначається структурою множини. Стек працює за принципом "останній прийшов - перший пішов (LIFO)", а черга - за принципом "перший прийшов - перший пішов (FIFO)".
Приклади структур даних.
Нехай S - деяка множина, представлена структурою даних, і нехай u - довільний елемент деякої множини, підмножиною якої є S. Наведемо основні операції, які зустрічаються при роботі із множинами:
  1. ПРИНАЛЕЖНІСТЬ (u,S). Вірно, що ? (Відповідь типу ДА/НІ).
  2. ВСТАВИТИ (u,S). Включить u у S.
  3. ВИЛУЧИТИ (u,S). Вилучити u із S.

  4.   Припустимо, що { S1 , S2 ,…, Sk } - набір множин (які попарно не перетинаються). На цьому наборі корисні такі операції:
  5. ЗНАЙТИ (u). Знайти таке j, що .
  6. ОБ'ЄДНАТИ (Si, Sj; Sk). Сформувати об'єднання Si і Sj і назвати його Sk.

  7.   Якщо універсальна множина повністю упорядкована, то дуже важливі такі операції:
  8. MIN(S). Знайти найменший елемент S.
  9. РОЗЧЕПИТИ (u,S). Розділити S на {S1 ,S2 } такі, що .
  10. ЗЧЕПИТИ (S1 ,S2 ). Припустимо, що для будь-яких і маємо ; необхідно сформувати множину .
  Структури даних можна класифікувати на базі операцій, які на них допустимі ( без врахування їх ефективності). Так, для упорядкованих множин має місце таблиця:
Структури даних Допустимі операції
Словник НАЛЕЖНІСТЬ, ВСТАВИТИ, ВИЛУЧИТИ
Пріоритетна черга MIN, ВСТАВИТИ, ВИЛУЧИТИ
Зчеплена черга ВСТАВИТИ, ВИЛУЧИТИ, РОЗЧЕПИТИ, ЗЧЕПИТИ

  Природа геометричних задач дозволила створити спеціальні, особливі структури даних, дві із яких виявились загально значимими, і їм приділяється особлива увага. Ці структури- дерево відрізків та реберний список з подвійними зв'язками (РППЗ).

Попередня Змiст Наступна