Понятие односвязного линейного списка и его реализация на языке C

d0bfd0bed0bdd18fd182d0b8d0b5 d0bed0b4d0bdd0bed181d0b2d18fd0b7d0bdd0bed0b3d0be d0bbd0b8d0bdd0b5d0b9d0bdd0bed0b3d0be d181d0bfd0b8d181 статьи

Понятие односвязного линейного списка и его реализация на языке C (C, Список)

До сих пор мы с Вами рассматривали структуры данных, отображая их на массив. За это время мы успели изучить стек, очередь, очередь с приоритетами и таблицу. Однако эти структуры данных можно реализовывать и без массива, а например с использованием так называемых связных списков.

Списку можно дать несколько определений. Здесь представлены некоторые из них.

Связный список — конечная последовательность однотипных элементов, которые называются узлами списка.

Связный список — последовательность, элементами которой являются записи (структуры), связанные друг с другом с помощью указателей, которые хранятся в этих же элементах.

Связный список — структура данных, определяемая следующим образом:

  1. Пустой список является списком
  2. Структура вида [Голова | Хвост] является списком, если голова — первый элемент списка, а хвост — список, состоящий из оставшихся элементов исходного списка

Обращаю Ваше внимание, что последнее определение называется рекурсивным определением списка.

Существует несколько видов списка: односвязный линейный список (ОЛС), последовательный линейный список (ПЛС), двусвязный линейный список (ДЛС) и другие. Однако в данной статье будет рассматриваться именно ОЛС.

Каждый прямоугольник на этом рисунке — элемент списка. Как и было сказано выше, в каждом элементе есть поле с данными и поле с указателем на следующий элемент. Следует отметить, диагональная черта у последнего прямоугольника — признак конца списка.

Вообще говоря, чаще всего списки используются с фиктивным элементом, который является первым в последовательности. Использование фиктивного элемента позволяет упростить реализацию некоторых операций. Добавлю, что не стоит пугаться таких элементов, это всего-навсего элемент списка, поле данных которого не используется.

Над линейный списком определены следующие операции:

  1. Инициализация
  2. Включение элемента
  3. Исключение элемента
  4. Переход в начало списка
  5. Переход в конец списка
  6. Переход к следующему элементу
  7. Уничтожение списка

При реализации ОЛС в статической памяти располагают дескриптор, состоящий из двух полей:

  1. Указатель на фиктивный элемент
  2. Указатель на текущий элемент

Хочу обратить ваше внимание на тот факт, что в любой момент времени нам известен лишь дескриптор и, соответственно, информация в нем, поэтому все операции над списком выполняются непосредственно через него.

P.S. При использовании фиктивного элемента, все операции нужно выполнять после того элемента, на который указывает ptr.

Инициализация списка

Инициализация происходит в три шага:

  1. Выделение памяти для фиктивного элемента
  2. В дескрипторе указателю start присвоить блок с только что выделенной памятью
  3. Указателю ptr присвоить start.

Понятие односвязного линейного списка и его реализация на языке C (C, Список)

Поясню, что здесь, и зачем. При инициализации происходит создание списка, но не заполнение его элементами. Создание списка подразумевает создание фиктивного элемента. Так как его поле данных не используется, то список остается по-прежнему пуст. Когда память выделена, остается лишь правильно присвоить ссылки указателям.Код инициализации таков:

Включение элемента

Понятие односвязного линейного списка и его реализация на языке C (C, Список)

Так как ptr указывает на фиктивный элемент, то новый элемент нужно вставить после него, но перед элементом со значением 5. Прежде чем вставить, нужно выделить память под новый элемент и занести информацию в него. Допустим, мы вставляем элемент с данными — 100.Теперь нужно вставить новый элемент между двумя элементами списка, то есть изменить ссылки, находящиеся в полях ptr.#image.jpgТеперь рассмотрим код операции включения.

Исключение элемента

Пусть нам дан тот же список, что и в примере с включением элемента.

#image.jpgТак как ptr указывает на фиктивный — исключаем первый. Здесь перемычка ссылок немного сложнее, чем в предыдущем примере. Нужно создать временный элемент так, чтобы он был равен исключаемому, т.е. имел один и тот же с ним адрес. Это нужно для того, чтобы не потерять тот элемент, на который исключаемый ссылается.#image.jpgТеперь — перемычка указателей и удаление временного элемента. #image.jpg

Вот и вся операция исключения. Ниже представлен код.

Остальные операции я не буду так подробно расписывать, так как они просты в реализации.

Файл List_One.h

Файл List_One.c

Осталось только добавить, что перечисленные мной операции — далеко не все, которые можно реализовать для списка. Вы сами можете создавать новые. На этом все, если что было не понятно, пишите в комментариях.

Оцените статью
Секреты программирования
Добавить комментарий