Наиболее простым динамическим типом данных является односвязный список. Элементами списка могут быть данные произвольного типа, однако каждый элемент помимо содержательной информации должен уметь хранить информацию о следующем элементе. Например, список можно представить с помощью следующего структурного типа:


Ассоциативная связь


Структура LIST является рекурсивной, т.к. содержит ссылку на саму себя.


Ассоциативная связь


Не уменьшая общности, будем считать, каждый элемент списка содержит целое (a) и символьное (с) значение. Для связи со следующим элементом служит поле next. Его значение равно адресу области памяти, в которой располагается следующий элемент списка.


В программе список может представляться указателем на первый элемент. Доступ ко всем последующим элементам осуществляется от предыдущего элемента.


Ассоциативная связь


Признаком окончания списка является нулевое значение поля next. Вместо этого условия можно хранить указатель на последний элемент списка.


Представление информации в виде списка имеет свои достоинства и недостатки.


Достоинства:

  • До начала работы программы не нужно описывать конфигурацию списка (динамичность).
  • Легко изменять размер списка.
  • Легко вставлять элементы в середину списка и удалять их оттуда.


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


Для того, чтобы использовать списки для решения содержательных задач, необходимо реализовать простейшие функции для работы со списком: вставка элемента в список, удаление элемента, просмотр списка. Реализовывать эти функции можно разными способами, в зависимости от потребностей решаемых задач. Например, элементы можно вставлять в начало или конец списка.


Ассоциативная связь


Создадим проект list. Опишем структуру списка и объявим функции для работы с ним в заголовочном файле list.h.


Ассоциативная связь


Обратите внимание на «**» в списке формальных параметров для функций insert и del. Напомним, что в программе список представляется указателем на первый элемент. Т.е. параметр head должен иметь тип LIST *. Для этой переменной, как и для любого указателя, в памяти будет отведено 4 байта и в нее запишется адрес первого элемента. Но в процессе вставки или удаления элементов первый элемент может измениться. Значит может измениться и значения переменной head. Поэтому в соответствующую функцию должно передаваться не значение head, а ее адрес. Следовательно, параметром функции должен быть указатель на указатель на список.


Рассмотрим реализацию функций работы со списком, которые будут размещены в файле с исходным кодом list.c.


Рассмотрим вариант вставки, который отслеживает упорядоченность списка по целочисленному полю.


Ассоциативная связь


Функцию удаления элемента можно также реализовать разными способами. Рассмотрим вариант, когда del ищет в списке элемент со значением целочисленного поля, равным параметру it, и удаляет его.


Ассоциативная связь


Функция вывода элементов списка на экран не меняет значение указателя на список head, поэтому перед head в списке параметров только одна звездочка. При реализации этой функции очень изящно и естественно используется рекурсия.


Ассоциативная связь


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