Основи програмування



1. Вказівники

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

Нижче схематично зображено, як саме виглядає пам'ять комп'ютера.

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

Ми маємо змінні різних типів - int, float тощо. З їх допомогою ми зберігаємо у пам'яті різні дані - цілі, дробові числа. Покажчик - це також певного роду тип даних, але покажчики зберігають адреси в пам'яті.

Варто зазначити, що у 32-розрядній системі, усі адреси в пам'яті мають розмір 4 байти, тому й покажчики теж мають розмір 3 байти.

Покажчики створюються майже так само як і інші змінні. Загальний синтаксис оголошення покажчика:

<тип>* <ім'я змінної>

За адресою, на яку вказує покажчик, можна зберігати лише дані того ж типу, що має покажчик.

Приклади:

int* x;

char* y;

Розіменування - це отримання доступу до значення, що зберігається у комірці пам'яті, адреса якої зберігається в покажчику. Простіше кажучи, розіменування дозволяє отримати значення, на яке посилається покажчик. Синтаксис:

*<ім'я покажчика>

Взяття адреси - це операція, за допомогою якої можна дізнатися, за якою адресою зберігається змінна у пам'яті. Синтаксис:

&<ім'я покажчика>

2. Зв’язані списки

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

Зв'язний список має можливість динамічної вставки, тобто ми можемо розмістити елемент будь-де в списку, нічого не переміщаючи, бо переміщування займає багато часу. У випадку зі зв'язним списком досить лише викликати malloc та оновити кілька вказівників.

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

Динамізм та гнучкість — ось переваги списків, але пам'ятайте:

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

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

Пам'ятайте: вставка, пошук та видалення елементів у зв'язаному списку відбувається за час Ο або за лінійний час, адже елемент може бути в кінці списку, або на початку — тоді це час Ω(1).

Але ж нам би хотілося, щоб пошук та додавання елементів виконувались за сталий час Ο(1).