й однозв'язний список
Лінійний список - це динамічна структура даних, кожен елемент якої за допомогою покажчика зв'язується з наступним елементом.
Графічно лінійний список можна представити таким чином:
В
Більш докладно цей вид розглянемо в 3 частини.
.4 двохзв'язной лінійні списки
Як ми вже говорили, лінійні списки можуть бути однозв'язний і двохзв'язной.
Кожен елемент односвязного списку крім власне даних містить поле з адресою наступного елементу. Роботу з такими списками ми тільки що розглянули.
У двохзв'язной списку кожен елемент має поля з даними і два покажчика: один покажчик зберігає адресу попереднього елемента списку, другий - адреса наступного елемента. Цілком природно для роботи з двохзв'язной списком використовувати два покажчика, що зберігають адреси початку і кінця такого списку. На малюнку нижче дається графічне представлення двохзв'язной списку.
.5 Кільцевій список
Кільцевій список - це список, у якого останній елемент пов'язаний з першим. Кільцевій список можна зробити як однозв'язний, так і двохзв'язной. Розглянемо коротко однозв'язний кільцевої список.
Схема кільцевого списку представлена ​​на малюнку нижче (використовуємо ті ж дані, що і для раніше розглянутого односвязного списку, тобто список з чисел 3, 5, 1, 9):
В
2.6 Черга
Черга - це лінійна динамічна структура даних, для якої виконується правило: додавання нових даних можливе лише в кінець цієї структури, а видалення (витяг ) - тільки з початку. В англомовній літературі цей принцип називається FIFO (First Input - First Output, тобто перший прийшов - перший пішов).
Прикладом з реального життя може бути черга з покупців до каси в магазині.
Як не важко зрозуміти, черга - це лінійний список, для якого визначені всього дві основні операції: додавання в кінець і витяг з початку. Значить, зручно мати два покажчика: на початок і кінець цієї динамічної структури. Але списки бувають однозв'язний і двохзв'язной. Який використовувати? Підійде тільки двохзв'язной список. У цьому можна буде переконатися при розгляді основних алгоритмів для роботи з чергою. p align="justify"> На малюнку нижче показано графічне представлення черги. Як і в попередніх темах, чергу будемо будувати з цілих чисел, наприклад: 3, 5, 1. br/>В
