Добавление элемента в очередь
Рассмотрим алгоритм добавления только для второго элемента.
1. Ввод информации для текущего (второго) элемента – значение i .
2. Захватываем память под текущий элемент:
t = (Spis*) malloc (sizeof(Spis)); или t = new Spis;
3. Формируем информационную часть (обозначим i2):
t -> info = i;
4. В адресную часть созданного элемента (текущего) заносим NULL, т.к. этот элемент становится последним:
t -> Next = NULL;
5. Элемент добавляется в конец очереди, поэтому в адресную часть бывшего последнего элемента end заносим адрес созданного:
end -> Next = t;
бывший последний элемент становится предпоследним.
6. Переставляем указатель последнего элемента на добавленный:
end = t;
В результате получим
Для добавления в очередь любого количества элементов организуется цикл, включающий пункты 1– 6 рассмотренного алгоритма. Завершение цикла реализуется в зависимости от поставленной задачи.
Обобщим рассмотренные этапы, тогда функция формирования очереди из данных объявленного типа с добавлением новых элементов в конец может иметь следующий вид:
void Create(Spis **begin, Spis **end) {
Spis *t = (Spis*) malloc(sizeof(Spis));
printf(“\n Input Info ”);
scanf(“%d”, &t -> info);
t -> Next = NULL;
if(*begin == NULL) // Формирование первого элемента
*begin = *end = t;
else {
(*end) -> Next = t; // Добавление в конец
*end = t;
}
}
Участок программы с обращением к функции Create для добавление необходимого количества элементов в очередь может иметь следующий вид:
¼
Spis *begin = NULL, *end;
int repeat = 1;
while(repeat) { // repeat=1 – продолжение ввода данных
Create(&begin, &end);
printf(“ Stop - 0 ”); // repeat=0 – конец ввода данных
scanf(“%d”, &repeat);
}
¼
Алгоритм удаления первого элемента из очереди
Предположим, что очередь создана, т.е. begin не равен NULL (рекомендуется организовать проверку на равенство NULL с соответствующей обработкой данной ситуации).
1. Устанавливаем текущий указатель на начало очереди: t = begin;
2. Обрабатываем информационную часть первого элемента очереди, например, выводим на экран.
3. Указатель на начало очереди переставляем на следующий (2-й) элемент
begin = begin->Next;
4. Освобождаем память, захваченную под 1-й элемент: free(t);
5. Выводим сообщение, например, «Элемент удален!».
Алгоритмы просмотра очереди и освобождения памяти выполняются аналогично стеку (см. п. 15.2).
Двунаправленный линейный список
Более универсальным является двунаправленный (двухсвязный) список, в каждый элемент которого кроме указателя на следующий элемент включен и указатель на предыдущий. Для обработки такого списка обычно аналогично очереди используются два указателя – на первый и последний элементы.
Графически такой список выглядит следующим образом:
Введем структуру, в которой (для простоты, как и раньше) информационной частью info будут целые числа, а адресная часть состоит из двух указателей на предыдущий (Prev) и следующий (Next) элементы:
struct Spis {
int info;
Spis *Prev, *Next;
} ;
Для работы со списком декларируем Spis *begin, *end; – указатели на начало и конец списка соответственно.
Формирование двунаправленного списка проводится в два этапа – формирование первого элемента и добавление нового. Причем добавление может выполняться как в начало, так и в конец списка.