Добавление нового элемента в очередь

1 2 3 4 5 6 7

Определена структура, которая будет использоваться в последующих примерах:

#define QUEUE struct List

QUEUE

{

char info;

QUEUE *next;

};

Функция добавления элемента в очередь:

void insert(QUEUE **pbeg, char item) { QUEUE *current = *pbeg; QUEUE *previous = 0; QUEUE *new_node; while (current) { previous = current; current = current -> next; } new_node = new QUEUE; new_node->info = item; if (previous) { new_node->next = 0; previous->next = new_node; } else { *pbeg = new_node; (*pbeg)->next = 0; } }

//*pbeg – указатель на первый элемент очереди //current – указатель на текущий элемент очереди; указывает на первый элемент //указатель на предыдущий элемент очереди //указатель на новый элемент очереди //пока текущий элемент не равен NULL //указатель previous указывает на тот же элемент, что и указатель current //перемещение указателя current на следующий по отношению к текущиму элемент //создаем новый элемент очереди //записываем в поле info нового элемента значение переменной item //если очередь не пустая (добавляется элемент в конец очереди) //указатель на следующий элемент после нового равен нулю (т.е. элемент не существует) //следующим по отношению к последнему элементу очереди становится новый элемент //если очередь пустая (добавляется первый элемент очереди) //первым элементом очереди будет новый элемент //указатель на следующий элемент поcле первого элемента равен 0 (т.е. элемент не существует)

Пример 1. Необходимо сформировать очередь, состоящую из трех элементов (‘a’,’b’,’c’), представленную в программе переменной q. Для этого используется функция insert.

QUEUE *q;

insert(&q,’a’);

insert(&q,’b’);

insert(&q,’c’);

На рис. 5 показаны изменения, происходящие при добавлении первого элемента очереди, на рис. 6 – при добавлении второго элемента очереди, на рис. 7 – добавление третьего элемента очереди.

Рис. 5 – Добавление первого элемента очереди

Рис. 6 – Добавление второго элемента очереди

Рис. 7 – Добавление третьего элемента очереди

Пример 2. Пусть в очередь, состоящую из трех элементов (‘a’,’b’,’c’), представленную в программе переменной q, необходимо добавить элемент ‘d’ после элемента ‘b’. В этом случае необходимо добавить элемент в середину очереди.

Функция добавления элемента в середину очереди:

void insert_mid(QUEUE **pbeg, char item) { QUEUE *current; QUEUE *new_node; current = *pbeg; while(current->info!=’b’) { current = current->next; } new_node = new QUEUE; new_node->info = item; new_node->next = current->next; current->next = new_node; }

//*pbeg – указатель на первый элемент очереди //текущий элемент очереди //новый элемент очереди //просмотр очереди начинаем с первого элемента //пока поле info текущего элемента не содержит символ ‘b’ //указатель current перемещается на следующий элемент очереди //создаем новый элемент очереди //в поле info нового элемента заносится значение ‘d’ //следующим элементом по отношению к новому становится следующий по отношению к текущему элемент //следующим по отношению к текущему элементу становится новый элемент

На рис. 8 показано происходящее после каждого шага изменения.