в'язків і програмними прикладами.
На всіх малюнках суцільними лініями показані зв'язку, що були до виконання і що збереглися після виконання операції. Пунктиром показані зв'язки, встановлені при виконанні операції. Значком x відзначені зв'язку, розірвані при виконанні операції. У всіх операціях надзвичайно важлива послідовність корекції покажчиків, яка забезпечує коректне зміна списку, що не зачіпає інші елементи. При неправильному порядку корекції легко втратити частину списку. Тому на малюнках поряд з встановлюваними зв'язками в дужках показані кроки, на яких ці зв'язки встановлюються.
Вставка елемента в список
Вставка елемента в середину 1-зв'язного списку
Вставка елемента в середину 2-зв'язного списку
Наведені приклади забезпечують вставку в середину списку, але не можуть бути застосовані для вставки в початок списку. При останній повинен модифікуватися покажчик на початок списку, як показано на малюнку.
Вставка елемента в початок 1-зв'язного списку
Видалення елемента зі списку
Видалення елемента з 1-зв'язного списку
Процедуру видалення елемента з двохзв'язной списку виявиться навіть простіше, ніж для одинзв'язного, оскільки в ній не потрібен пошук попереднього елемента, він вибирається за вказівником тому.
Перестановка елементів списку
Мінливість динамічних структур даних передбачає не тільки зміни розміру структури, а й зміни зв'язків між елементами. Для зв'язкових структур зміна зв'язків не вимагає пересилки даних у пам'яті, а тільки зміни покажчиків в елементах зв'язковий структури. Як приклад наведена перестановка двох сусідніх елементів списку.
Нелінійні розгалужені списки
Основні поняття
нелінійних розгалуженим списком є ??список, елементами якого можуть бути теж списки. Раніше ми расс?? отрелі двохзв'язной лінійні списки. Якщо один з покажчиків кожного елементу списку задає порядок зворотний до порядку, що встановлюється іншим покажчиком, то такий двусвязний список буде лінійним. Якщо ж один з покажчиків задає порядок довільного виду, який не є зворотним по відношенню до порядку, що встановлюється іншим покажчиком, то такий список буде нелінійним.
У обробці нелінійний список визначається як будь-яка послідовність атомів і списків (подсписков), де в якості атома береться будь-який об'єкт, який при обробці відрізняється від списку тим, що він структурно неподільний.
Спосіб подання, часто використовуваний для ілюстрації списків, - графічні схеми, аналогічний способу уявлення, вживаному при зображенні лінійних списків. Кожен елемент списку позначається прямокутником; стрілки або покажчики показують, чи є прямокутники елементами одного і того ж списку або елементами подсписка.
Схематичне представлення розгалуженого списку
Розгалужені списки описуються трьома характеристиками: порядком, завглибшки і завдовжки.
Порядок. При поданні списків графічними схемами порядок визначається горизонтальними стрілками. Горизонтальні стрілки тлумачаться так: елемент з якого виходить стрілка, передує елементу, на який вона вказує.
Глибина. Це максимальний рівень, приписуваний елементам усередині списку або всередині будь-якого подсписка в списку. Рівень елемента наказується вкладеністю подсписков всередині списку. Глибина списку є максимальним значенням рівня серед рівнів всіх атомів списку.
Довжина. Це число елементів рівня 1 в списку. Наприклад, довжина списку на малюнку дорівнює 3.
Подання списковую структур в пам'яті
Відповідно до схематичним зображенням розгалужених списків типова структура елемента такого списку в пам'яті повинна бути такою, як показано на малюнку.
Структура елемента розгалуженого списку
У цьому випадку покажчик down вказує на дані або на подсписок. Оскільки списки можуть складатися з даних різних типів, доцільно адресувати покажчиком down не безпосереднє дані, а їх дескриптор, в якому може бути описаний тип даних, їх довжина і т.п. Сам опис того, чи є адресується покажчиком даних об'єкт атомом або вузлом також може знаходитися в цьому дескрипторі. Зручно зробити розмір дескриптора даних таким же, як і елемента списку. У цьому ...
