2015-10-13
1853
Раніше розглядались структури, в яких зв ' язок між елементами заданий неявно. Однак в класі лінійних структур даних існують значно складніші зв ' язні структури, в яких функціональний зв ' язок між його елементами заданий явно. До таких структур належать спискові. Розглянемо найпростіші з таких структур, а саме, лінійні списки.
Список, що відображає відношення сусідства між елементами, називають лінійним. Будь-який інший список вважається нелінійним. Тип списків визначається типом зв ' язків між його елементами. За кількістю зв ' язків розрізняють списки одно- і багатозв ' язні, а за типом функції зв ' язку - лінійні і нелінійні.
Основний принцип спискової структури даних полягає в тому, що логічний порядок слідування елементів задається сукупністю посилань або вказівників. У послідовній пам ' яті дані розміщуються в послідовних одиницях пам ' яті і цим визначається порядок їх слідування.
Отже, поняттю "список" можна дати таке пояснення: організацію зберігання даних, при якій логічний порядок слідування даних визначається посиланнями aбo вказівниками, називають списковою організацією пам'яті, а дані, що зберігаються таким чином, - списком. Спискова організація пам ' яті має також назву зчеплення.
|
|
|
Елемент списку складається як мінімум з двох полів - безпосереднього значення елемента даних і вказівника на наступний елемент списку. У деяких випадках значення елементів даних можуть зберігатися окремо, тоді у полі "значення" елемента списку може знаходитися вказівник на місцезнаходження цього елемента даних. Вказівники елементів списку називають також адресами зв ' язку, або зв ' язками.
Однією з основних властивостей списків є те, що елементи розміщуються в пам ' яті довільним способом, а не в суміжних одиницях пам ' яті, як у векторів.
Кожний список має свій заголовок, у якому зберігається посилання на перший елемент списку. Заголовок списку називають також іменем списку. Всі інші елементи досягаються шляхом проходження списку за допомогою вказівників.
Існує два способи зображення списків: 1) графічний (рис.8.1,а); 2) дужковий (рис.8.1,б).
Рис.8.1. Приклади зображення списків: а) графічний; б) дужковий
При графічному способі список зображується у вигляді ланцюга, кожна ділянка якого складається з двох полів - довідки і тіла. Дужковий вираз для зображення списку зручний тоді, коли списки складаються з різних типів даних і зміна одного списку не впливає на другий. Наприклад, на рис.8.1,а зображено список, у якого в полі тіла елемента записано безпосередньо значення елемента даних, а на рис.8.1,б - вказівник на місцезнаходження елемента даних. Дужковий вираз у обох випадках залишається однаковим і не відображає різного вмістимого поля тіла елементів списку.
|
|
|
При обробці списків найчастіше виконуються такі дії:
1) доступ до к -го елемента списку з метою аналізу і заміни його полів;
2) включення нового елемента безпосередньо перед заданим;
3) виключення заданого елемента;
4) об’єднання декількох списків в один;
5) розбиття списку на два або більше списки;
6) копіювання списку;
7) визначення кількості елементів у списку;
8) знаходження елемента за заданими властивостями;
9) пересортування або впорядкування елементів списку у висхідному або низхідному порядку.
