одинзв’язні списки

У однозв'язного списку кожен елемент інформації містить посилання на наступний елемент списку. Кожен елемент даних зазвичай є структурою, яка складається з інформаційних полів і покажчика зв'язку. Концептуально однозв'язний список виглядає так, як показано на рис. 22.2.

Мал. 22.2 однозв'язного список

Існує два основних способи побудови однозв'язного списку. Перший спосіб - поміщати нові елементи в кінець списку [1]. Другий - вставляти елементи в певні позиції списку, наприклад, в порядку зростання. Від способу побудови списку залежить алгоритм функції додавання елемента. Давайте почнемо з простішого способу створення списку шляхом поміщення елементів в кінець.

Наведена нижче функція slstore () створює однозв'язний список шляхом поміщення кожного чергового елемента в кінець списку. Як параметри їй передаються покажчик на структуру типу address. містить новий запис, і покажчик на останній елемент списку. Якщо список порожній, покажчик на останній елемент має дорівнювати нулю.

Незважаючи на те, що створений за допомогою функції slstore () список можна відсортувати окремою операцією вже після його створення, легше відразу створювати впорядкований список, вставляючи кожен новий елемент в потрібне місце в послідовності. Крім того, якщо список вже відсортований, має сенс підтримувати його впорядкованість, вставляючи нові елементи у відповідні позиції. Для вставки елемента таким способом потрібно послідовно переглядати список до тих пір, поки не буде знайдено місце нового елемента, потім вставити в знайдену позицію новий запис і перевстановити посилання.

При вставці елементу в однозв'язний список може виникнути одна з трьох ситуацій: елемент стає першим, елемент вставляється між двома іншими, елемент стає останнім. На рис. 22.3 показана схема зміни посилань в кожному випадку.

Мал. 22.3. Вставка елемента new в однозв'язний список (в якому info - поле даних)

Наступна функція, sls_store (). вставляє структури типу address в список розсилки, впорядковуючи його по зростанню значень в поле name. Функція приймає покажчики на покажчики на перший і останній елементи списку, а також покажчик на вставляється елемент. Оскільки перший або останній елементи списку можуть змінитися, функція sls_store () при необхідності автоматично оновлює покажчики на початок і кінець списку. При першому виклику даної функції покажчики first і last повинні бути рівні нулю.

Послідовний перебір елементів пов'язаного списку здійснюється дуже просто: почати з початку і слідувати вказівниками. Зазвичай фрагмент коду перебору настільки малий, що його вставляють в іншу процедуру - наприклад, функцію пошуку, видалення або відображення вмісту. Так, наведена нижче функція виводить на екран всі імена зі списку розсилки:

При виконанні функції display () параметр start повинен бути покажчиком на першу структуру в списку. Після цього функція переходить до наступного елементу, на який вказує покажчик в поле next. Процес припиняється, коли next дорівнює нулю.

Для отримання елемента зі списку потрібно просто пройти по ланцюжку посилань. Нижче наведено приклад функції пошуку по вмісту поля name.

Оскільки функція search () повертає покажчик на елемент списку, що містить шукане ім'я, повертається тип описаний як покажчик на структуру address. При відсутності в списку відповідних елементів повертається нуль (NULL).

Видалення елемента з однозв'язного списку виконується просто. Так само, як і при вставці, можливі три випадки: видалення першого елемента, видалення елемента в середині, видалення останнього елемента. На рис. 22.4 показані всі три операції.

Мал. 22.4. Видалення елемента з однозв'язного списку

Нижче приведена функція, що видаляє заданий елемент зі списку структур address.

Функції sldelete () необхідно передавати покажчики на видаляється елемент, що передує удаляемому, а також на перший і останній елементи. При видаленні першого елемента покажчик на попередній елемент має дорівнювати нулю (NULL). Ця функція автоматично оновлює покажчики start і last. якщо один з них посилається на видаляється елемент.

У однозв''язних списків є один великий недолік: однозв'язний список неможливо прочитати в зворотному напрямку. З цієї причини зазвичай застосовуються двусвязного списки.

[1] Не забувайте, що у однозв'язного списку, як і у мотузки, два кінця: початок і кінець.