С++ для начинающих. Однонаправленный список 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 адреса, значение и размер очереди. Этот скелет имеет смысл запихать в класс или структуру. Т. к. поначалу структуры попроще воспринимаются, я запихаю скелет в структуру. Тому, кто плохо знаком со структурами и классами, имеет смысл прочитать С++ для начинающих. Классы. Первое знакомство.

Да, выше я не сказал про следующий элемент, но чтобы создать очередь FIFO, нужно как-то связывать текущий элемент с вновь пришедшим. Это как в поликлиннике, когда прибежал какой-то гад, сказал, что за вами и убежал. Но связь создана. Вот чтобы создать такую связь внутри программы, используют адреса памяти, проще говоря, указатели. Тип этих указателей соответствует названию класса/структуры. В скелете я обозначил переменную *Next. Эта переменная будет хранить адрес памяти последнего поступившего в очередь элемента. Не впереди идущего, а последнего поступившего.
Теперь, когда создан скелет очереди, можно добавить функцию добавления элементов. Чтобы добавить элемент в очередь FIFO, имеет смысл запомнить простой алгоритм:

  • 1) Создать новый элемент, тип которого соответствует типу класса/структуры
  • 2) Записать в этот элемент полученное значение
  • 3) Запомнить адрес начала очереди
  • 4) Проверить очередь на наличие в ней элементов. Не новый элемент проверить, а то, что голова не пустая

    -Если Очередь пустая — то обозначить, что начало очереди одновременно и конец очереди. Для всех указателей (начало, голова, хвост) хранимый адрес на такой случай должен быть один и тот же.
    -Если очередь не пустая — то записать в хвост очереди созданный элемент и сдвинуть хвост, указав что адресом хвоста теперь будет адрес вновь созданного элемента.

Показываю описанный алгоритм на примере:



static int count — переменная-счетчик, которая благодаря ключевому слову static не будет умирать и будет сохранять свое последнее значение после завершения работы Add. Вот при каждом новом вызове Add эта переменная будет увеличиваться на 1 и после этого запоминаться в переменную size структуры MyFIFO.
Так, добавление показал и объяснил. Теперь вопрос в том, как работать с этой очередью. Элементарное, что можно с ней сделать — это вывести всю очередь на экран. Чтобы вывести её на экран, нужно узнать адрес начала очереди. После того как адрес очереди известен, можно вывести на экран значение текущего элемента очереди и сдвинуть адрес на адрес следующего запомненного элемента. (Внутри очереди это последний туда поступивший после только что выбранного). Т. к. нами создавалась связь адресов, то попасть в нужный адрес не будет проблемой, для этого при помощи цикла нужно постепенно обращаться к элементу Next только что выбранного элемента, выводить значение val на экран и вновь двигаться по нашей очереди к следующему элементу. Цикл выполнять имеет смысл до тех пор, пока не будет достигнут конец очереди. На самом деле очередь FIFO может быть кольцевой и не кольцевой. В зависимости от закольцованности признаки определения конца очереди могут различаться. Наша очередь не кольцевая. Для некольцевой очереди обычно признак то, что изъятый элемент не последний элемент очереди (т. е. указатель Next ведёт на ненулевой адрес). Ну а в кольцевом — наиболее удобным признаком конца может послужить количество элементов, записавшихся в очередь. В самом конце я покажу кольцевой, он почти не отличается от некольцевого FIFO, а сейчас некольцевой FIFO:


Вот и всё. Теперь осталось написать функцию удаления очереди из памяти. Вместе с удалением я буду выводить информацию по удаляемому элементу:

Вот так вот. Не так уж и сложно. А теперь к тому, что есть, сделаем маленький апгрэйд. Из обычной очереди сделаем кольцевую. Для этого хвост должен указывать на начало, а вовнутрь функции приниматься аргумент, который сообщает количество итераций (количество повторений цикла). Весь код абсолютно такой же, за исключением маленьких поправок:

Т. к. до этого самым первым поступившим в очередь был NULL, который был использован в цикле для проверки окончания работы цикла (например, в функции Show()), то теперь же произведённым изменением вместо NULL используется адрес начала очереди, т. е. хранимое Head. Поскольку теперь у нас всегда Next указывает на существующий элемент, то проверка указывания на адрес с несуществующим элементом: проверка на NULL не годится. Это значит, что там где использовался обход по признаку указывания вникуда, там нужно поменять критерии выполнения цикла. Изменяем функцию Show():


Как видите, вовнутрь функции обхода теперь передаётся аргумент, т. е. вызов функции Show() слегка меняется. Теперь требуется указывать количество итераций, т. к. без этого цикл не выполняется, а чтобы их указывать, можно вовнутрь функции передавать параметр, обозначающий это количество.
Полный код кольцевого списка FIFO:


Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

11 комментариев: С++ для начинающих. Однонаправленный список FIFO

  • СВЕТА говорит:

    Долго, очень долго искала информацию в интернете о программировании списков!!! И… вот, наконец-то нашла!!! Спасибо за скрупулезность и доброту! Вы мне очень помогли! Желаю удачи, здоровья, благополучия…




    0



    0
  • Slavik говорит:

    Спасибо автору за статьи, очень нужное дело для начинающих. Обязательно продолжайте писать.
    Дополню в Show утечка памяти и ненужное копирование, можно написать так:
    void List::Show() //метод отображения списка на экране
    {
    element *temp=Head; //прыгаем этим указателем к голове списка

    while (temp!=NULL) //пока что-то встречается
    {
    cout<x<Next; //и переходим к следующему элементу
    }
    }




    0



    0
  • Slavik говорит:

    редактор подвел 🙁
    void List::Show() //метод отображения списка на экране
    {
    element *temp=Head; //прыгаем этим указателем к голове списка

    while (temp!=NULL) //пока что-то встречается
    {
    cout<x<Next; //и переходим к следующему элементу
    }
    }




    0



    0
  • Slavik говорит:

    Да уж в тэги не взял код. В общем в Show()

    element *temp=Head; //прыгаем этим указателем к голове списка
    вместо

    element *temp=new element; //выделяем память указателю
    temp=Head; //прыгаем этим указателем к голове списка
    temp->x=Head->x; //присваиваем в x нашего указателя x головы




    0



    0
  • admin говорит:

    Благодарю. Исправил.




    0



    0
  • Дмитрий говорит:

    Не могли бы помочь вывести список в обратном порядке? Всю голову уже сломал, но не выходит.

    Автор сайта отвечает:
    Именно список FIFO надо в обратном?
    может вам просто LIFO нужен?




    0



    0
  • Дмитрий говорит:

    admin, LIFO

    Автор сайта отвечает:
    так есть же пример с описанием. Предыдущая статья. Ссылка есть даже на этой странице (вверху переход слева на предудущую статью)
    http://ci-plus-plus-snachala.ru/?p=57




    0



    0
  • Дмитрий говорит:

    там как я понял, идет вывод: если вводим (1, 2 , 3 , 4) то выводит 1->2->3->4->NULL. Это я уяснил.
    А вот как 4->3->2->1, не понимаю что то…

    Автор сайта отвечает:
    Ясно. Сейсач проверять и перепроверять нет возможности, но возможно я там и правда ошибся.
    А вот так 4-3-2-1 — это стек. Насколько я понял по отписанным там комментариям, стек описан мной достаточно удачно, вот ссылка
    http://ci-plus-plus-snachala.ru/?p=91

    Дмитрий говорит: Спасибо за внимание. Нравится ваш сайт

    Автор сайта отвечает:
    Тут по обеим ссылкам , которые я вам дал, описывается решение вашего вопроса.
    В первом случае описывается более сложно, но более подробно, во втором случае описывается достаточно просто.

    я посмотрел код из LIFO и он работает как вам и надо. Что-то вы невнимательно посмотрели и поэтому неправильно поняли.




    0



    0
  • Vus говорит:

    Добрый вечер) Не подскажите, у меня проблемы с данным списком. Поиск одинаковых элементов в списке, делаю по вашему примеру.Получается муть какая то.

    Автор сайта отвечает:
    Скорее всего подскажу.
    Только я не знаю где вы чудите, чтобы я мог вам подсказать. К сожалению, я не экстрасенс и не верю что таковые существуют.
    Функция поиска выполняется достаточно легко, только сам поиск элементов может существовать в разных вариациях. Она очень похожа на функция Show
    В общем, желательно увидеть ваши «жалкие» потуги
    Нужно более полно описать ожидаемый результат. Может вам количество надо, а может просто что есть одинаковые, а может нужно расписать позиции для каждого или может создать массив, который хранит позиции. Тут как бы много вариантов конечного результата возможно.
    ======================
    Да. Я могу помочь. Но нужен ваш пример и ваша задача. Конечный результат может требоваться разный.




    0



    0
  • Руфина говорит:

    Спасибо огромное за такую легкоусвояемую информацию)))




    0



    0
  • Marina говорит:

    в 12-й стройке 2-го кода нету ли ошибки, не понимаю смысл данной строчки.

     

    Автор сайта отвечает:
    Вот в этой?
    Next=temp->Head;




    0



    0

Добавить комментарий

Ваш e-mail не будет опубликован.

− 1 = 2

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/uriy-magda/programmirovanie-i-otladka-c-c-prilozheniy-dlya-mikrokontrollerov-arm/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Классическая ошибка, которую совершают проектировщики абсолютно надежных систем, – недооценка изобретательности клинических идиотов.

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок