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