Одномерные однонаправленные списки

Одномерный однонаправленный список представляет собой совокупность отдельных элементов, каждый из которых содержит две части – информационную (Inf) и адресную (Adr). Информационная часть предназначена для хранения “полезных” данных и может иметь практически любой тип. Адресная часть каждого элемента содержит адрес следующего элемента списка. Схематическое изображение такого списка представлено на следующем рисунке.

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

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

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

Типовыми операциями при работе со списками являются:

· создание списка;

· освобождение памяти от списка (удаление списка);

· доступ к заданному элементу списка для манипуляций с его информационной частью;

· добавление нового элемента к списку;

· удаление элемента из списка;

· перестановка элемента списка на новую позицию внутри списка.

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

Прежде всего, определим необходимые типы данных для работы со списком.

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

Struct t_Item

{

Double Inf;

t_Item * Adr;

};

Для того чтобы хранить в списке другие данные (не double), достаточно заменить тип doubleполя Inf на другой необходимый тип данных.

Тип адресного поля этой структуры определен как указатель на тип данных элемента списка (t_Item * Adr).

Создание списка

Представленная ниже функция CreateListобеспечивает создание динамического однонаправленного списка на Lengthэлементов и возвращает адрес первого элемента созданного списка.

t_Item *CreateList ( unsigned Length )

{

t_Item *Curr = 0,// Адрес очередного элемента списка

*Next = 0;// Адрес следующего за очередным элемента списка

// Начинаем создавать список с последнего элемента

for ( unsigned i = 1; i <= Length; ++ i )

{

// Создаем очередной элемент списка

Curr = new t_Item;

// В адресную часть записываем адрес следующего

// за очередным элемента списка

Curr->Adr = Next;

// Запоминаем адрес очередного элемента в качестве

// следующего элемента для следующего шага цикла

Next = Curr;

}

// Возвращаем адрес последнего созданного элемента,

// как адрес первого элемента списка

Return Curr;

}

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

Использовать эту функцию для создания списка можно, например, так:

t_Item *List = CreateList ( 5 );

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

Заполнить информационные части элементов этого списка конкретными данными, например, с клавиатуры можно так:

// Чтобы не потерять адрес начала списка (он нам понадобится для дальнейшей

// работы со списком) вводим дополнительную переменную-указатель Curr – адрес

// очередного элемента списка и делаем его равным адресу первого элемента списка

t_Item * Curr = List;

// Выполняем цикл пока адрес очередного элемента списка не равен 0

While ( Curr )

{

// Вводим данные в информационную часть очередного элемента с клавиатуры

cin >> Curr->Inf;

// Делаем очередным следующий элемент списка. Для этого переменной

// Curr присваиваем адрес следующего элемента списка. Последний элемент

// списка содержит в адресной части 0, поэтому кода мы обработаем последний

// элемент списка, переменная Curr станет равна 0, и цикл закончится

Curr = Curr->Adr;

}

Вывод значений информационных частей элементов списка на экран делается аналогично:

Curr = List;

While ( Curr )

{

// Выводим информационную часть очередного элемента на экран

cout << Curr->Inf << “ “;

Curr = Curr->Adr;

}

cout << endl;

Удаление списка

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

void DeleteList ( t_Item * &Beg )

{

t_Item *Next;// Указатель на следующий элемент списка

// Начинаем с начала списка

While ( Beg )

{

// Запоминаем адрес следующего элемента списка. Если этого не сделать,

// то после удаления элемента по адресу Beg негде будет взять адрес

// следующего элемента списка

Next = Beg->Adr;

// Удаляем первый элемент списка

Delete Beg;

// Делаем адрес первого элемента списка равным адресу

// следующего после удаленного (мы его запомнили чуть выше)

Beg = Next;

}

}

После окончания работы эта функция возвращает через свой параметр-ссылку Beg адрес 0 – список отсутствует (он перестал существовать).

Использование этой функции: