С++ для начинающих. Однонаправленный список FIFO
- FIFO — это способ организации сцепки элементов в порядке обычной, привычной нам, очереди.
Когда говорят о FIFO, прежде всего подразумевают динамическую сцепку элементов, т. е. говорят о динамической структуре данных. Также FIFO могут называть очередью FIFO или списком FIFO. Всё это одна и та же организация работы программы с памятью, реализация которой сводится к тому, что,первый вошедший в очередь объект первым и обслуживается.
Ранее на странице этого сайта описывалась организация работы с памятью по принципу LIFO:
В отличие от организации работы с памятью по принципу LIFO, где первым обслуживается последний пришедший элемент, при организации памяти по принципу FIFO первым всегда обслуживается объект, занявший очередь первым. Поскольку структуры данных очень часто называют очередями или списками, то чтобы ничего не перепутать, имейте в виду, что FIFO — это однонаправленный список, направление обхода которого происходит от первого размещённого элемента к последнему размещённому.
Пришел 1 (первый)
Пришел 2 (второй)
Пришел 3 (третий)
Пришел 4 (четвертый)
====================
При выводе, например, на экран в порядке следования будет: 1 2 3 4
Сама организация структуры FIFO предполагает, что обращением к элементу списка выбирается элемент пришедший первым. Первым пришла единица, следовательно первым будет 1, вторым 2, третьим 3..
Если создать несколько по порядку идущих чисел и поочереди записать их в список, а потом вывести список на экран, то при выводе на экран будет сохранён порядок, в LIFO же порядок переворачивается.
Я как-то долго не мог понять, чем отличается очередь от списка FIFO — ответ: ничем; это и есть список FIFO. А очередью называется потому как соблюдаются правила "Справедливых" очередей. Т. е. кто первее — того первее обслужат. Надеюсь, доступно, понятно и не сложно запомнить. Теперь перейдём к практической части.
Так как FIFO мало отличается от LIFO, то коды, организующие эти принципы, всегда будут очень сильно схожи. Итак, чтобы построить очередь FIFO, для начала имеет смысл запомнить, что для FIFO обязательные элементы адрес начала очереди и адрес конца очереди. Запихивать в очередь я буду обычные числа, т. к. так удобнее смотреть. И добавлю размер, т. е. количество размещённых в очередь элементов. Этот размер совсем не обязателен, но пусть будет.
Итак, со скелетом очереди определились: 2 адреса, значение и размер очереди. Этот скелет имеет смысл запихать в класс или структуру. Т. к. поначалу структуры попроще воспринимаются, я запихаю скелет в структуру. Тому, кто плохо знаком со структурами и классами, имеет смысл прочитать С++ для начинающих. Классы. Первое знакомство.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Листинг #a1 Скелет очереди для вставки в очередь целых чисел struct MyFIFO{ int val; //Значение как элемент очереди: оно будет вставляться в очередь int size; //Размер очереди MyFIFO *Head, *Tail, *Next; //Указатели на начало очереди, на конец очереди и на следующий элемент очереди. }; int main(){ return 0; } |
Да, выше я не сказал про следующий элемент, но чтобы создать очередь FIFO, нужно как-то связывать текущий элемент с вновь пришедшим. Это как в поликлиннике, когда прибежал какой-то гад, сказал, что за вами и убежал. Но связь создана. Вот чтобы создать такую связь внутри программы, используют адреса памяти, проще говоря, указатели. Тип этих указателей соответствует названию класса/структуры. В скелете я обозначил переменную *Next. Эта переменная будет хранить адрес памяти последнего поступившего в очередь элемента. Не впереди идущего, а последнего поступившего.
Теперь, когда создан скелет очереди, можно добавить функцию добавления элементов. Чтобы добавить элемент в очередь FIFO, имеет смысл запомнить простой алгоритм:
- 1) Создать новый элемент, тип которого соответствует типу класса/структуры
- 2) Записать в этот элемент полученное значение
- 3) Запомнить адрес начала очереди
-
4) Проверить очередь на наличие в ней элементов. Не новый элемент проверить, а то, что голова не пустая-Если Очередь пустая — то обозначить, что начало очереди одновременно и конец очереди. Для всех указателей (начало, голова, хвост) хранимый адрес на такой случай должен быть один и тот же.-Если очередь не пустая — то записать в хвост очереди созданный элемент и сдвинуть хвост, указав что адресом хвоста теперь будет адрес вновь созданного элемента.
Показываю описанный алгоритм на примере:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//Листинг #1 Пример организации FIFO struct MyFIFO{ int val; int size; MyFIFO *Head,*Tail,*Next; void Add(const int x); //Добавил функцию добавления для очереди }; void MyFIFO::Add(int x){ MyFIFO *temp = new MyFIFO; //Создаем вообще новый элемент temp Next = NULL; //Задаём указателю настоящей очереди, указывающему на следующий элемент, направление на нулевой адрес. (Это не указатель temp->Next, это указатель очереди, обрабатываемой снаружи функции) temp->val = x; //Записываем принятый элемент в temp, точнее в нужную переменную вовнутрь temp if (Head != NULL){ //Проверка на пустоту. Если не пусто Tail->Next = temp; //Записываем, что следующий элемент в хвосте имеет адрес temp Tail = temp; //Перемещаем хвост на свой следующий элемент. Получается, что хвост теперь начинается в последнем созданном temp } else Head = Tail = temp; //Если же очередь пустая, то тогда, адреса начала, конца очереди и первого созданного элемента должны быть одинаковыми } int main(){ return 0; } |
Так, добавление показал и объяснил. Теперь вопрос в том, как работать с этой очередью. Элементарное, что можно с ней сделать — это вывести всю очередь на экран. Чтобы вывести её на экран, нужно узнать адрес начала очереди. После того, как адрес очереди будет известен, можно вывести на экран значение текущего элемента очереди и сдвинуть адрес на адрес следующего запомненного элемента. (Внутри очереди это будет последний туда поступивший после только что выбранного). Т. к. нами создавалась связь адресов, то попасть в нужный адрес не будет проблемой, для этого при помощи цикла нужно постепенно обращаться к элементу Next только что выбранного элемента, выводить значение val на экран и вновь двигаться по нашей очереди цепочке узлов к следующему элементу. Цикл выполнять имеет смысл до тех пор, пока не будет достигнут конец очереди. На самом деле очередь FIFO может быть кольцевой и не кольцевой. В зависимости от закольцованности признаки определения конца очереди могут различаться. Наша очередь не кольцевая. Для некольцевой очереди обычно признак то, что изъятый элемент не последний элемент очереди (т. е. указатель Next ведёт на ненулевой адрес). Ну а в кольцевом — наиболее удобным признаком конца может послужить количество элементов, записавшихся в очередь. В самом конце я покажу кольцевой, он почти не отличается от некольцевого FIFO, а сейчас некольцевой FIFO:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> //для cout using std::cout; //Листинг #2 FIFO Не кольцевая очередь struct MyFIFO{ int val; int size; MyFIFO *Head, *Tail, *Next; void Add(const int x); void Show(); }; void MyFIFO::Add(int x){ static int count=0; ///////////////////////////////////////////// MyFIFO *temp = new MyFIFO; //Выделяем память новому узлу, каждый новый добавляемый элемент требует выделение себе участка в памяти! Каждое такое выделение даёт нам узел списка. Next = NULL; //Сразу обозначаем, что следующий элемент обрабтываемого сейчас списка не сформирован, делаем это путём указания на нулевой адрес temp->val = x; //Копируем значение x вовнутрь созданного нами сейчас узла списка if (Head != NULL){ Tail->Next = temp; Tail = temp; } else Head = Tail = temp; //////////////////////////////////////////// } void MyFIFO::Show(){ MyFIFO *temp = Head; //Получаем адрес начала очереди while (temp != Tail->Next){ //Пока адрес указателя не совпадет со следующим элементом за хвостом очереди cout << temp->val << "\n"; //Будем выбирать элементы, использя указатель temp temp = temp->Next; //Как только выбрали элемент, переходим по новому адресу к следующему элементу } } int main(){ return 0; } |
Вот и всё. Теперь осталось написать функцию удаления очереди из памяти. Вместе с удалением я буду выводить информацию по удаляемому элементу:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
//Листинг #3 Пример организации FIFO Некольцевая очередь Полный пример #include <iostream> //для cout using std::cout; struct MyFIFO{ int val; int size; MyFIFO *Head, *Tail, *Next; void Add(const int x); void Show(); void Del(); }; void MyFIFO::Add(int x){ static int count=0; ///////////////////////////////////////////// MyFIFO *temp = new MyFIFO; //Выделяем память новому узлу, каждый новый добавляемый элемент требует выделение себе участка в памяти! Каждое такое выделение даёт нам узел списка. Next = NULL; //Сразу обозначаем, что следующий элемент обрабтываемого сейчас списка не сформирован, делаем это путём указания на нулевой адрес temp->val = x; //Копируем значение x вовнутрь созданного нами сейчас узла списка if (Head != NULL){ Tail->Next = temp; Tail = temp; } else Head = Tail = temp; //////////////////////////////////////////// } void MyFIFO::Show(){ MyFIFO *temp = Head; //Получаем адрес начала очереди while (temp != Tail->Next){ //Пока адрес указателя не совпадет со следующим элементом за хвостом очереди cout << temp->val << "\n"; //Будем выбирать элементы, использя указатель temp temp = temp->Next; //Как только выбрали элемент, переходим по новому адресу к следующему элементу } } void MyFIFO::Del(){ MyFIFO *temp = Head; //Создаём указатель, направляем его на начало очереди while (temp != Tail){ temp = Head; //Нашли текущее начало очереди и запомнили адрес в сторонюю переменую Head = Head->Next; //Сместили фактическое начало на адрес следующего поступившего элемента cout << "Udalena swiaz s: " << temp->val << "\n"; //Для наглядности delete temp; //Очистили связь } } int main(){ return 0; } |
Я не писал, что нужно в main, чтобы не отвлекать этим. Теперь мы пришли к моменту, когда всё готово, использовать созданную нами очередь довольно легко:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
int main(){ MyFIFO Q1; //Объявили переменную типа нашей очереди FIFO (имя структуры) Q1.Head = NULL; //Обозначили что голова пустая, ибо очередь пуста (можно в конструкторе) Q1.Add(100); //Добавляем элементы Q1.Add(200); Q1.Add(300); Q1.Show(); //Показываем нашу очередь Q1.Del(); //Очищаем память cin.get(); return 0; } |
Вот так вот. Не так уж и сложно. Если мы задействуем конструктор, то код можно сделать чуть лучше. В настоящий момент нам после объявления очереди необходимо указывать, что Q1.Head = NULL;, это довольно неудобно. Поправим:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
//Листинг #3.1 Пример организации FIFO Некольцевая очередь Полный пример #include <iostream> //для cout using std::cout; //Листинг #2 FIFO Не кольцевая очередь struct MyFIFO{ int val; int size; MyFIFO *Head, *Tail, *Next; void Add(const int x); void Show(); void Del(); MyFIFO():Head(NULL), Tail(NULL), Next(NULL){}; //При создании очереди Head, Tail и Next инициализируются нулевым адресом. Это конструктор класса }; void MyFIFO::Add(int x){ static int count=0; ///////////////////////////////////////////// MyFIFO *temp = new MyFIFO; //Выделяем память новому узлу, каждый новый добавляемый элемент требует выделение себе участка в памяти! Каждое такое выделение даёт нам узел списка. Next = NULL; //Сразу обозначаем, что следующий элемент обрабтываемого сейчас списка не сформирован, делаем это путём указания на нулевой адрес temp->val = x; //Копируем значение x вовнутрь созданного нами сейчас узла списка if (Head != NULL){ Tail->Next = temp; Tail = temp; } else Head = Tail = temp; //////////////////////////////////////////// } void MyFIFO::Show(){ MyFIFO *temp = Head; //Получаем адрес начала очереди while (temp != Tail->Next){ //Пока адрес указателя не совпадет со следующим элементом за хвостом очереди cout << temp->val << "\n"; //Будем выбирать элементы, использя указатель temp temp = temp->Next; //Как только выбрали элемент, переходим по новому адресу к следующему элементу } } void MyFIFO::Del(){ MyFIFO *temp = Head; while (temp != Tail){ temp = Head; //Нашли текущее начало очереди и запомнили адрес в сторонюю переменую Head = Head->Next; //Сместили фактическое начало на адрес следующего поступившего элемента cout << "Udalen uzel s: " << temp->val << "\n"; //Для наглядности delete temp; //Зачистили узел } } int main(){ MyFIFO Q1; //Объявили переменную типа нашей очереди FIFO (имя структуры) Q1.Add(100); //Добавляем элементы Q1.Add(200); Q1.Add(300); Q1.Show(); //Показываем нашу очередь Q1.Del(); //Очищаем память return 0; } |
Всё бы ничего, но у нас на самом деле имеется весомый потенциал возникновения ошибки при работе программы: она случится, если очередь будет пустая. При наличии пустой очереди у нас будет происходить аналог вот такого:
Чтобы этого избежать, достаточно в функции вывода предусмотреть этот момент и ничего не выводить на экран, если очередь не заполнялась элементами или зачистилась до состояний "пустая":
|
1 |
cout << NULL; |
Чтобы этого избежать, достаточно в функции вывода предусмотреть этот момент и ничего не выводить на экран, если очередь не заполнялась элементами или зачистилась до состояний "пустая":
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void MyFIFO::Show(){ if (!Head) { //Если Head != NULL (головной узел не направлен на нулевой адрес), то cout << "Empty list"; //сообщаем о том, что список пуст return; //и выходим из функции ничего не делая } //Иначе функция выполняет, что должна: MyFIFO *temp = Head; //Получаем адрес начала очереди while (temp != Tail->Next){ //Пока адрес указателя не совпадет со следующим элементом за хвостом очереди cout << temp->val << "\n"; //Будем выбирать элементы, использя указатель temp temp = temp->Next; //Как только выбрали элемент, переходим по новому адресу к следующему элементу } } |
Не хочу повторять один и тот же код ради небольшой поправки. Ничего сложного, надеюсь, не сделал. Функция вывода не изменилась почти никак, туда только добавилась одна проверка. Тут важно, что сначала надо проверить очередь на пустоту, и только потом выполнять действия с очередью. Это может касаться не только функции отображения, но и других функций, манипулирующих данными очереди.
А теперь к тому, что есть, сделаем маленький апгрэйд. Из обычной очереди сделаем кольцевую. Для этого хвост должен указывать на начало, а вовнутрь функции приниматься аргумент, который сообщает количество итераций (количество повторений цикла). Весь код абсолютно такой же, за исключением некоторых незначительных поправок:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Листинг #b1 Организуем кольцевую очередь FIFO, пишем функцию добавления элемента void MyFIFO::Add(int x){ static int count=0; ///////////////////////////////////////////// MyFIFO *temp = new MyFIFO; Next = temp->Head; temp->val = x; if (Head != NULL){ Tail->Next = temp; Tail = temp; } else Head = Tail = temp; //////////////////////////////////////////// count++; size = count; Tail->Next = Head; //Поправка №1. Из-за нее текущая функция вывода на экран перестанет работать. } |
static int count — переменная-счетчик, которая благодаря ключевому слову static не будет умирать и будет сохранять свое последнее значение после завершения работы Add. Вот при каждом новом вызове Add эта переменная будет увеличиваться на 1 и после этого запоминаться в переменную size структуры MyFIFO.
Т. к. до этого самым первым поступившим в очередь был NULL, который был использован в цикле для проверки окончания работы цикла (например, в функции Show()), то теперь же произведённым изменением вместо NULL используется адрес начала очереди, т. е. хранимое Head. Поскольку теперь у нас всегда Next указывает на существующий элемент, то проверка указывания на адрес с несуществующим элементом: проверка на NULL не годится. Это значит, что там где использовался обход по признаку указывания вникуда, там нужно поменять критерии выполнения цикла. Изменяем функцию Show():
|
1 2 3 4 5 6 7 8 9 |
//Листинг #b2 Из-за закольцованности обход выполняется немного иначе чем было показано для некольцевого списка void MyFIFO::Show(const int count){ MyFIFO *temp = Head; //Получаем адрес начала очереди for (int i=0; i<count;i++){ //Обходим по известному числу элементов cout << temp->val << " "; temp = temp->Next; } cout << "\n"; } |
Как видите, вовнутрь функции обхода теперь передаётся аргумент, т. е. вызов функции Show() слегка меняется. Теперь требуется указывать количество итераций, т. к. без этого цикл не выполняется, а чтобы их указывать, можно вовнутрь функции передавать параметр, обозначающий это количество.
Полный код кольцевого списка FIFO:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
//Листинг #4 Кольцевой список FIFO #include <iostream> using namespace std; struct MyFIFO{ int val; int size; MyFIFO *Head, *Tail, *Next; void Add(const int x); void Show(const int count); //Изменилась функция Show/ Теперь она принимает параметр void Del(); }; void MyFIFO::Add(int x){ static int count=0; ///////////////////////////////////////////// MyFIFO *temp = new MyFIFO; Next = temp->Head; temp->val= x; if (Head != NULL){ Tail->Next = temp; Tail = temp; } else Head = Tail = temp; //////////////////////////////////////////// count++; size = count; Tail->Next = Head; } void MyFIFO::Show(const int count){ //Появился аргумент (получаемый параметр) if (!Head) { //Если Head != NULL (головной узел не направлен на нулевой адрес), то cout << "Empty list"; //сообщаем о том, что список пуст return; //и выходим из функции ничего не делая } MyFIFO *temp = Head; for (int i=0; i<count; i++){ //Количество итераций будет равно этому аргументу cout << temp->val << " "; temp = temp->Next; } cout << "\n"; } void MyFIFO::Del(){ if (!Head) return; //Если очередь пустая, то удалять нечего //Если не пустая, то организуем удаление int count = 0; MyFIFO *temp = Head; while (temp != Tail){ temp = Head; //Нашли текущее начало очереди и запомнили адрес в сторонюю переменую Head = Head->Next; //Сместили фактическое начало на адрес следующего поступившего элемента cout << "Udalena swiaz s: " << temp->val << "\n"; //Для наглядности delete temp; //Очистили связь } size = 0; //Обозначили, что в очереди ноль элементов } int main(){ MyFIFO Q1; Q1.Head = NULL; Q1.Add(100); Q1.Add(200); Q1.Add(300); Q1.Show(5); //Сама функция вызывается с указанным количеством. сейчас 5, но можно другие значения Q1.Del(); cin.get(); return 0; } |
10 комментариев на «“С++ для начинающих. Однонаправленный список FIFO”»
Добавить комментарий
Случайная книга в электронном формате
Долго, очень долго искала информацию в интернете о программировании списков!!! И… вот, наконец-то нашла!!! Спасибо за скрупулезность и доброту! Вы мне очень помогли! Желаю удачи, здоровья, благополучия…
Спасибо автору за статьи, очень нужное дело для начинающих. Обязательно продолжайте писать.
Дополню в Show утечка памяти и ненужное копирование, можно написать так:
void List::Show() //метод отображения списка на экране
{
element *temp=Head; //прыгаем этим указателем к голове списка
while (temp!=NULL) //пока что-то встречается
{
cout<x<Next; //и переходим к следующему элементу
}
}
редактор подвел 🙁
void List::Show() //метод отображения списка на экране
{
element *temp=Head; //прыгаем этим указателем к голове списка
while (temp!=NULL) //пока что-то встречается
{
cout<x<Next; //и переходим к следующему элементу
}
}
Да уж в тэги не взял код. В общем в Show()
element *temp=Head; //прыгаем этим указателем к голове списка
вместо
element *temp=new element; //выделяем память указателю
temp=Head; //прыгаем этим указателем к голове списка
temp->x=Head->x; //присваиваем в x нашего указателя x головы
Благодарю. Исправил.
Спасибо огромное за такую легкоусвояемую информацию)))
а зачем делать постоянное изменение указателя в 13 строке второго примера, Next=temp->Head; там же движение по хвосту все равно только, если не кольцевать то temp->Next=null; я бы еще понял, но вот здесь то зачем
Низачем, да и кроме этого с кодом не всё в порядке: удаление некорректное. Так получилось, что не особо понимал, что к чему, когда писал статью. Буду на предстоящей неделе вспоминать, что к чему, и пробовать исправить свои упущения. Спасибо, что обратили внимание.
Внесены некоторые исправления.
А у вас функция удаления одного элемента есть?То есть сдвигать нго в конец