С++. Простой пример списка FIFO

Один из наиболее простых примеров реализации списка с организацией FIFO был найден мной в англоязычной википедии: FIFO (computing and electronics). К сожалению, показанная мной реализация С++ для начинающих. Однонаправленный список FIFO, определённо один из усложнённых вариантов. Об этом мне не стало известно, пока хорошие люди не подсказали. В любом случае, иногда несколько примеров решений лучше, чем один или вообще ничего, поэтому я решил, что пусть и повторюсь, но дам читателям очень выразительный и понятный код списка FIFO.
Без знаний об этих вещах понять даваемую мной здесь информацию может быть труднее. Ну что ж, приступим. Я на этот раз не буду растягивать описание, а просто сразу напишу код и опишу, что и зачем в нём делается. Поскольку предполагается, что вы уже ознакомлены с показанными темами, то сам процесс описания действий с полного нуля только зря засорит информационное поле, необходимое для уяснения.

Поскольку код достаточно выразителен, его легко запомнить, а по комментариям многое, если не всё, должно проясниться. Но, может, кто-то будет, кому нужно ещё доразжевать один момент. Когда список пустой, понятно, что нужно просто выделить память для вставляемого в список элемента (у нас это сейчас структура, внутри которой хранится число) и вставить туда требуемый элемент путём направления на него указателей. Т. е. мы выделили память, записали в выделенную память какие-то значения и направили на этот участок нужный указатель. В нашем случае нужный указатель определяет головной (передний) элемент списка, поэтому это указатель front. После этого нам указатель front нужен только для обработки, но не для модификации списка, поэтому в операциях вставки о нём можно забыть. Каждый новый вставляемый элемент — это последний элемент списка, следовательно указатель back, обозначающий как раз последний элемент списка, следует направлять на него, но нужно обязательно учесть вставку первого элемента в список: это ситуация, когда и указатель на последний элемент, и указатель на первый элемент направлены на один и тот же участок памяти, на одно и то же значение. Нужно делать корректировку для такой ситуации, в остальном всё довольно просто: сначала мы определяем, что следующий для последнего вставленного элемента будет сейчас вставляемый, направляем на вставляемый back->next и только потом обозначаем, что вставленный элемент оказался последним, направляем на него back. Тут фокус в том, что когда мы смещаем back, на другой элемент списка, он начинает показывать на элемент, внутри которого указатель next указывает на нулевой адрес (благодаря конструктору, описанному внутри структуры). Мы корректируем направление на адрес вставляемого в список элемента, направляем его, и потом снова смещаем back, чтобы опять же скорректировать направление лежащего уже там указателя и т. д.

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

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

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

Поиск

 
     

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

https://www.litres.ru/denis-kolisnichenko/programmirovanie-dlya-android-samouchitel/?lfrom=15589587
Яндекс.Метрика