поля: для зберігання даних і для покажчика. Полів даних і покажчиків може бути кілька. Поля даних можуть бути будь-якого типу: основного, складеного або типу покажчик. Опис найпростішого елемента (компоненти, вузла) виглядає наступним чином:
Node
{d;// Тип даних Data повинен бути визначений раніше * next;// Покажчик на наступний елемент списку
Node * prev;// Покажчик на наступний елемент (якщо використовується двусвязний список)
};
Список, кожен елемент якого містить покажчик тільки на наступний за ним елемент, називається односпрямованим або однозв'язний. Якщо додати в кожен елемент друге посилання - на попередній елемент, вийде двонаправлений список (двусвязний), якщо останній елемент зв'язати покажчиком з першим, вийде кільцевої список. [2] На малюнку 1 наведена структура односвязного списку. На ньому поле INF - інформаційне поле (дані), NEXT - покажчик на наступний елемент списку. Кожен список повинен мати особливий елемент, званий покажчиком початку списку або головою списку, який зазвичай за форматом різниться від інших елементів. У полі покажчика останнього елемента списку знаходиться спеціальний ознака nil, який свідчить про кінець списку.
Рисунок 1 - Структура односвязного списку
Однак, обробка односвязного списку не завжди зручна, оскільки відсутня можливість просування в протилежну сторону. Таку можливість забезпечує двусвязний список, кожен елемент якого містить два покажчика: на наступний і попередній елементи списку. Структура лінійного двохзв'язної списку наведена на малюнку 2, де поле NEXT - покажчик на наступний елемент, поле PREV - покажчик на попередній елемент. У крайніх елементах відповідні покажчики повинні містити nil, як і показано на малюнку 2:
Малюнок 2 - Структура двусвязного списку
Для зручності обробки списку додають ще один особливий елемент - покажчик кінця списку. Наявність двох покажчиків в кожному елементі ускладнює список і призводить до додаткових витрат пам'яті, але в той же час забезпечує більш ефективне виконання деяких операцій над списком. [3]
Різновидом розглянутих видів лінійних списків є кільцевої список, який може бути організований на основі як односвязного, так і двохзв'язної списків. При цьому в однозв'язний списку покажчик останнього елемента повинен вказувати на перший елемент; в двохзв'язної списку в першому і останньому елементах відповідні покажчики перевизначаються, як показано на малюнку 3:
Рисунок 3 - Структура кільцевого списку
При роботі зі списками використовуються наступні основні операції:
- початкове формування списку (створення першого елемента);
- додавання елемента в кінець списку;
- читання елемента із заданим ключем;
- вставка елемента в задане місце списку (до або після елемента із заданим ключем);
- видалення елемента із заданим ключем;
- упорядкування списку по ключу.
. РОЗРОБКА І ВИБІР АЛГОРИТМІВ
У своїй роботі за основу я вирішив взяти лінійний двусвязний список, так як...
