Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Добавление нового элемента в очередь
|
|
Определена структура, которая будет использоваться в последующих примерах:
#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 показано происходящее после каждого шага изменения.
Рис. 8 – Добавление элемента в середину очереди