Реализация циклического однонаправленного списка при помощи двух массивов

Циклический однонаправленный список: адрес первого элемента списка хранится в специальной переменной v, называемой внешним указателем списка или указателем на первый элемент. Указатель последнего элемента списка указывает на его начало, именно поэтому список является циклическим или кольцевым.

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

Обход списка (вывод на экран значений элементов списка):

Код C++

Удаление пятого по порядку элемента списка:

Сводится к общей задаче удаления из списка элемента, следующего за элементом с адресом m. В данном случае m = 3. Поэтому:

Код C++

Добавление в список после третьего элемента трёх новых элементов

Вставка элемента x в список после элемента с адресом k в общем виде:

Код C++

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

Код C++

И, наконец полный текст программы, реализующей циклический однонаправленный список при помощи двух массивов и операции со списком:

Код C++

Поделиться с друзьями