Другая операция, неестественная для списков с единичными ссылками, - поиск элемента, предшествующего данному .

После удаления узла из связного списка посредством операции x->next = x->next->next, повторное обращение к нему окажется невозможным. Для небольших программ, вроде рассмотренных вначале примеров, это не имеет большого значения, но хорошей практикой программирования обычно считается применение оператора delete. Он служит противоположностью оператора new для любого узла, который более не придется использовать. В частности, последовательность операторов

t = x->next; x->next = t->next; delete t;

не только удаляет t из списка, но также информирует систему, что задействованная память может использоваться для других целей. Оператору delete особое внимание уделяется при наличии больших списков либо большого их количества, но до раздела 3.5 будем его игнорировать, чтобы сосредоточиться на оценке преимуществ связных структур.

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

Иосифа (Флавия), которая служит интересным контрастом решету Эратосфена.

Программа 3.9 Пример циклического списка (задача Иосифа)

Для представления людей, расставленных в круг, построим циклический связный список, где каждый элемент (человек) содержит ссылку на соседний элемент против хода часовой стрелки. Целое число i представляет i-того человека в круге. После создания циклического списка из одного узла вставляются узлы от 2 до N. В результате образуется окружность с узлами от 1 до N. При этом переменная х указывает на N. Затем пропускаем М-1 узлов, начиная с 1-го, и устанавливаем значение ссылки (М-1)-го узла таким образом, чтобы пропустить М-ый узел. Продолжаем эту операцию, пока не останется один узел.

#include <iostream.h> #include <stdlib.h> struct node { int item; node* next;

РИСУНОК 3.4 ВСТАВКА В СВЯЗНОМ СПИСКЕ

Для вставки узла t в позицию связного списка, следующую за узлом х (верхняя диаграмма), для t->next устанавливается значение х- >next (средняя диаграмма), затем для х- >next устанавливается значение t (нижняя диаграмма).

node(int X, node* t) { item = x; next = t; }

typedef node *lin]c; int main(int argc, char *argv[]) { int i, N = atoKargvtl]) , M = atoi (argv[2]) ;

link t = new node(l, 0); t->next = t;

link x = t;

for (i = 2; i <= N; i++)

x s (x->next = new node(i, t)) ; while (x != x->next)

for (i = 1; i < M; i++) x = x->next; x->next = x->next->next;

cout x->item endl;

Предположим, Л человек решило выбрать главаря. Ця этого они встали в круг и стали удалять каждого М-го человека в определенном направлении отсчета, смыкая ряды после каждого удаления. Задача состоит в определении, кто останется последним (потенциальный лидер с математическими способностями заранее определит выигрышную позицию в круге).

Номер выбираемого главаря является функцией от Ли М, называемой функцией Иосифа. В более общем случае требуется выяснить порядок удаления людей. В примере, показанном на рис. 3.5, если Л= 9 и М = 5, люди удаляются в порядке 5174369 2, а 8-ой номер становится избранным главарем. Программа 3.9 считывает значения и Af, а затем распечатывает эту последовательность.

Для прямой имитации процесса выбора в программе 3.9 используется циклический связный список. Сначала создается список элементов от I до N. Для этого создается циклический список с единственным узлом для участника 1, затем вставляются узлы для участников от 2 до с помощью операции, иллюстрируемой на рис. 3.4. Затем в списке отсчитывается М- 1 элемент и удаляется следующий при помощи операции, проиллюстрированной на рис. 3.3, Этот процесс продолжается до тех пор, пока не останется только один узел (который будет указывать на самого себя).

Решето Эратосфена и задача Иосифа хорошо иллюстрируют различие между использованием массивов и связных списков для представления последовательно расположенных наборов объектов. Использование связного списка вместо массива для построения решета Эратосфена скажется на производительности, поскольку эффективность алгоритма

РИСУНОК 3.5 ПРИМЕР ЗАДАЧИ ИОСИФА

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

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

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

Упражнения

> 3.23 Написать функцию, которая возвращает количество узлов циклического списка для данного указателя одного из узлов списка.

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

012345678

item next

РИСУНОК 3.6 ПРЕДСТАВЛЕНИЕ СВЯЗНОГО СПИСКА В ВИДЕ МАССИВА

Эта последовательность отражает связный список для задачи Иосифа (см. рис. 3.5), реализованный с помощью индексов массива вместо указателей. Индекс элемента, следующего в списке за элементом с индексом О, - nextfOJ, и т.д. Сначала (три верхних строки) элемент для участника / имеет индекс и формируется циклический список путем присвоения значений i+1 членам next[i] для i от О до 8, а элементу next[8] присваивается значение 0. Для имитации процесса выбора Иосифа изменяются ссылки (записи next массива), но элементы не перемещаются. Каждая пара строк показывает результат перемещения по списку с четырехкратной установкой значений х = nextfxj и последующим удалением пятого элемента (отображаемого в крайнем левом столбце) путем присвоения значения nextfnextfxJJ указателю nextfxj.

3.25 Написать фрагмент кода, который

по указателям х и t двух непересекающихся связных списков вставляет список, указываемый t, в список, указываемый х, в позицию, которая следует после узла