Назва роботи: Зв'язковий список. Сортування списків
Предметна область: Інформатика, кібернетика та програмування
Опис: Зв'язковий список. Сортування списків. Як відомо, масив завжди займає безперервний блок пам'яті, що дозволяє швидко отримувати доступ до довільного елементу масиву за індексом, проте істотно ускладнює вставку і видалення елементів, оскільки.
Розмір файлу: 51 KB
Роботу скачали: 47 чол.
Зв'язний список. Сортування списків.
Як відомо, масив завжди займає безперервний блок пам'яті, що дозволяє швидко отримувати доступ до довільного елементу масиву за індексом, проте істотно ускладнює вставку і видалення елементів, оскільки ці операції змушують здійснювати зсув всіх наступних елементів. Крім того, вставка елемента в заповнений динамічний масив призводить до необхідності виділення пам'яті і переміщення всього вмісту масиву.
Найпростіший однозв'язний список являє собою лінійну послідовність елементів, для кожного з яких, крім останнього, відомий наступний елемент:
Елементи такого списку можна описати в наступному вигляді:
struct L ist N ode
ListN ode * next; // Покажчик на следущий елемент списку
Доступ до такого списку забезпечується через покажчик на його перший елемент:
ListN ode * head; // Покажчик на перший елемент списку
Типовий набір операцій на списком включає в себе додавання, видалення і пошук елементів, обчислення довжини списку, послідовний обхід елементів (ітерацію). Додавання візуального ефекту в список дуже ефективна: для цього потрібно всього лише перепризначити зв'язку тільки двох сусідніх елементів, на місце між якими здійснюється вставка:
Такий список дозволяє здійснювати видалення елементів так само ефективно, як і вставку. Проте, здійснення довільного доступу до елементів за індексом в списках набагато менш ефективно, ніж в масивах.
У наступному прикладі показано заповнення однозв'язного списку і реалізація функцій виведення списку на екран і очищення пам'яті:
// Структура, що описує однозв'язний список
// Функція виводить список на екран
void printList (const ListNode * head)
Вимірювання інформації: змістовний і алфавітний підходи. Одиниці виміру інформації. Визначити поняття кількість інформації досить складно. один з основоположників кібірнетіеі американський математик Клож Шенон розвинув імовірнісний підхід до вимірювання кількості інформації а роботи по створенню ЕОМ привели до об'ємного підходу.