Более универсальным является двунаправленный (двухсвязный) список, в каждый элемент которого кроме указателя на следующий элемент включен и указатель на предыдущий. Для обработки такого списка обычно аналогично очереди используются два указателя – на первый и последний элементы.
Графически такой список выглядит следующим образом:
Введем структуру, в которой (для простоты, как и раньше) информационной частью info будут целые числа, а адресная часть состоит из двух указателей на предыдущий (Prev) и следующий (Next) элементы:
struct Spis {
int info;
Spis *Prev, *Next;
};
Для работы со списком декларируем Spis * begin, * end; – указатели на начало и конец списка соответственно.
Формирование двунаправленного списка проводится в два этапа – формирование первого элемента и добавление нового. Причем добавление может выполняться как в начало, так и в конец списка.
Формирование первого элемента
1. Захват памяти под текущий элемент:
Spis *t = (Spis*) malloc (sizeof(Spis));
На данном этапе имеем элемент:
2. Формируем первый элемент списка:
а) формируем информационную часть, например, вводя с клавиатуры:
scanf(“%d”, &t -> info); или cin >> t -> info;
б) формируем адресные части (первоначально это NULL):
t -> Prev = t -> Next = NULL;
в) указатели начала и конца списка устанавливаем на этот элемент:
begin = end = t;
После выполнения указанных действий получили первый элемент списка:
Добавление элементов в конец списка
1. Начало цикла.
2. Захват памяти под текущий элемент:
t = (Spis*) malloc(sizeof(Spis));
3. Формирование информационной части:
scanf(“%d”, &t -> info);
4. Формирование адресных частей текущего элемента:
а) указателю на следующий элемент (Next) присваиваем значение NULL, т.к. добавление выполняем в конец, следующего за t нет:
t -> Next = NULL;
б) указателю на предыдущий элемент (Prev), используя указатель конца (end), присваиваем адрес бывшего последнего элемента:
t -> Prev = end;
5. Последним элементом был end, а должен стать t, для этого указатель на следующий элемент последнего в списке (end) устанавливаем на созданный (текущий):
end -> Next = t;
6. Переставляем указатель конца списка на созданный элемент:
end = t;
7. Продолжаем цикл до тех пор, пока не обработаем признак его завершения.
Алгоритм просмотра списка
| С начала | С конца |
| 1. Устанавливаем текущий указатель на: | |
| начало списка t = begin; | конец списка t = end; |
| 2. Начало цикла, работающего до тех пор, пока t!= NULL. | |
| 3. Информационную часть текущего элемента t -> info – на печать. | |
| 4. Устанавливаем текущий указатель на: | |
| следующий элемент, адрес которого находится в поле Next текущего элемента t = t -> Next; | предыдущий элемент, адрес которого находится в поле Prev текущего элемента t = t -> Prev; |
| 5. Конец цикла. |
