До сих пор мы с Вами рассматривали структуры данных, отображая их на массив. За это время мы успели изучить стек, очередь, очередь с приоритетами и таблицу. Однако эти структуры данных можно реализовывать и без массива, а например с использованием так называемых связных списков.
Списку можно дать несколько определений. Здесь представлены некоторые из них.
Связный список — конечная последовательность однотипных элементов, которые называются узлами списка.
Связный список — последовательность, элементами которой являются записи (структуры), связанные друг с другом с помощью указателей, которые хранятся в этих же элементах.
Связный список — структура данных, определяемая следующим образом:
- Пустой список является списком
- Структура вида [Голова | Хвост] является списком, если голова — первый элемент списка, а хвост — список, состоящий из оставшихся элементов исходного списка
Обращаю Ваше внимание, что последнее определение называется рекурсивным определением списка.
Существует несколько видов списка: односвязный линейный список (ОЛС), последовательный линейный список (ПЛС), двусвязный линейный список (ДЛС) и другие. Однако в данной статье будет рассматриваться именно ОЛС.
Каждый прямоугольник на этом рисунке — элемент списка. Как и было сказано выше, в каждом элементе есть поле с данными и поле с указателем на следующий элемент. Следует отметить, диагональная черта у последнего прямоугольника — признак конца списка.
Вообще говоря, чаще всего списки используются с фиктивным элементом, который является первым в последовательности. Использование фиктивного элемента позволяет упростить реализацию некоторых операций. Добавлю, что не стоит пугаться таких элементов, это всего-навсего элемент списка, поле данных которого не используется.
Над линейный списком определены следующие операции:
- Инициализация
- Включение элемента
- Исключение элемента
- Переход в начало списка
- Переход в конец списка
- Переход к следующему элементу
- Уничтожение списка
При реализации ОЛС в статической памяти располагают дескриптор, состоящий из двух полей:
- Указатель на фиктивный элемент
- Указатель на текущий элемент
Хочу обратить ваше внимание на тот факт, что в любой момент времени нам известен лишь дескриптор и, соответственно, информация в нем, поэтому все операции над списком выполняются непосредственно через него.
P.S. При использовании фиктивного элемента, все операции нужно выполнять после того элемента, на который указывает ptr.
Инициализация списка
Инициализация происходит в три шага:
- Выделение памяти для фиктивного элемента
- В дескрипторе указателю start присвоить блок с только что выделенной памятью
- Указателю ptr присвоить start.
Поясню, что здесь, и зачем. При инициализации происходит создание списка, но не заполнение его элементами. Создание списка подразумевает создание фиктивного элемента. Так как его поле данных не используется, то список остается по-прежнему пуст. Когда память выделена, остается лишь правильно присвоить ссылки указателям.Код инициализации таков:
Включение элемента
Так как ptr указывает на фиктивный элемент, то новый элемент нужно вставить после него, но перед элементом со значением 5. Прежде чем вставить, нужно выделить память под новый элемент и занести информацию в него. Допустим, мы вставляем элемент с данными — 100.Теперь нужно вставить новый элемент между двумя элементами списка, то есть изменить ссылки, находящиеся в полях ptr.#image.jpgТеперь рассмотрим код операции включения.
Исключение элемента
Пусть нам дан тот же список, что и в примере с включением элемента.
#image.jpgТак как ptr указывает на фиктивный — исключаем первый. Здесь перемычка ссылок немного сложнее, чем в предыдущем примере. Нужно создать временный элемент так, чтобы он был равен исключаемому, т.е. имел один и тот же с ним адрес. Это нужно для того, чтобы не потерять тот элемент, на который исключаемый ссылается.#image.jpgТеперь — перемычка указателей и удаление временного элемента. #image.jpg
Вот и вся операция исключения. Ниже представлен код.
Остальные операции я не буду так подробно расписывать, так как они просты в реализации.
Файл List_One.h
Файл List_One.c
Осталось только добавить, что перечисленные мной операции — далеко не все, которые можно реализовать для списка. Вы сами можете создавать новые. На этом все, если что было не понятно, пишите в комментариях.
