6.2 Розіменування вказівника
Операція отримання значення, на яке посилається вказівник, називається розіменування вказівника.
У мові програмування С:
double A = 5; /*декларація дійсної змінної подвійної точності */
double *a; /*декларація вказівника на дійсну змінну */
a = &A; /* присвоєння вказівнику адреси змінної A. a тепер вказує на A */
*a = 10; /*Присвоєння значення тому, на що вказує а. *a — операція розіменування вказівника */
a є вказівником на число типу double. *a — розіменування вказівника. У результаті змінна A отримує значення 10.
7 Лінійні списки
Лінійний список в інформатиці та програмуванні визначається як екземпляр абстрактного типу даних, що формалізує концепцію впорядкованої множини елементів. Наприклад, абстрактний тип даних для безтипових, змінних списків можна визначити із допомогою конструктора та чотирьох операцій[1]:
конструктор для створення порожнього списку;
операція визначення порожності списку;
операція для додавання елемента в початок списку (cons в Лісп);
операція отримання першого елемента списку (або «голови») списку (car в Лісп);
операція для визначення списку, що складається із всіх елементів списку окрім першого (або його «хвоста») (cdr в Лісп).
Важливими окремими випадками лінійних списків, в яких операції додавання та вилучення певних значень можуть бути виконані лише для першого чи останнього елементу, є:
стек
лінійний список, в якому операції додавання та вилучення виконуються лише на одному кінці списку (верхівці стеку). Принцип побудови стеку називають LIFO (англ. last in, first out).
черга (однобічна черга)
лінійний список, в якому усі операції додавання виконується на одному кінці (в голові черги), а операції вилучення — на іншому кінці списку (в хвості черги). Принцип побудови черги називають FIFO (англ. first in, first out).
дек або двобічна черга
лінійний список, в якому всі операції вставки та видалення виконуються на обох кінцях списку.
Не менш важливим окремим випадком лінійного списку є зв'язаний список, в якому кожний елемент окрім поля даних зберігає також вказівник на наступний.
Така
структура дозволяє зняти обмеження на
зберігання лінійного списку в безперервній
області пам'яті.
Важливим узагальненням лінійного списку є багатовимірний масив.
8. Нелінійні списки
8.1 Двійкове дерево В програмуванні двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.
8.2 Різновиди двійкових дерев
Двійкове дерево — таке кореневе дерево, в якому кожна вершина має не більше двох дітей. Повне (закінчене) двійкове дерево — таке двійкове дерево, в якому кожна вершина має нуль або двох дітей.
Ідеальне двійкове дерево — це таке повне двійкове дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).
Двійкове дерево на кожному n-му рівні має від 1 до 2n вершин.
Представлення n-арних дерев як двійкові
Існує
єдине та взаємооднозначне відображення
довільного впорядкованого
дерева в двійкове.
Рисунок 5 – двійкове дерево.
Для
цього слід послідовно зв'язати усіх
дітей кожної сім'ї з першою дитиною та
видалити усі вертикальні з'єднання за
виключенням з'єднання батька з першою
дитиною в сім'ї. Тобто
кожна вершина
N
впорядкованого
n-арного дерева відповідає вершині
M
деякого
двійкового дерева. Ліва дитина вершини
M
відповідає
першій дитині вершини
N,
а права дитина
M
відповідає
першому з наступних братів
N
(тобто
першому з наступних дітей батька вершини
N).
Така відповідність має назву
природної відповідності між n-арним та двійковим деревом.
9
TIME.H
time.h — заголовний файл стандартної бібліотеки мови програмування СІ, що містить типи і функції для роботи з датою й часом.
Деякі функції можуть працювати з місцевим часом, який може відрізнятися від календарного, наприклад у зв'язку з часовими поясами. Визначено арифметичні типи clock_t і time_t для представлення часу, а структура struct tm містить компоненти календарного часу.
Таблиця 1 – Функції для роботи з датою і часом
Ім'я |
Опис |
int tm_sec; |
Секунди від початку хвилини (0,59) |
int tm_min; |
Хвилини від початку години (0,59) |
int tm_hour; |
Години від півночі (0,23) |
int tm_mday; |
Число місяця (1,31) |
int tm_mon; |
Місяці після січня (0,11) |
int tm_year; |
Роки з 1900 (в Windows), з 1970 (в Unix) |
int tm_wday; |
Дні з неділі (0,6) |
Inttm_yday; |
Дні з першого січня (0,365) |
int tm_isdst; |
Ознака літнього часу |
Поле tm_isdst має позитивне значення, якщо активний режим літнього часу, нуль в іншому випадку і негативне значення, якщо інформація про сезон часу невідома.