Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

#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 – Добавление элемента в середину очереди

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.