С++. Простой пример списка FIFO
Один из наиболее простых примеров реализации списка с организацией FIFO был найден мной в англоязычной википедии: FIFO (computing and electronics). К сожалению, показанная мной реализация С++ для начинающих. Однонаправленный список FIFO, определённо один из усложнённых вариантов. Об этом мне не стало известно, пока хорошие люди не подсказали. В любом случае, иногда несколько примеров решений лучше, чем один или вообще ничего, поэтому я решил, что пусть и повторюсь, но дам читателям очень выразительный и понятный код списка FIFO.
Для знакомства с этой темой желательно, чтобы читатель уже был знаком с:
Знал темы:
- Указатели в C++ для начинающих. Поверхностное знакомство
- Структуры в С++ для начинающих
- С++ для начинающих. Классы. Первое знакомство
- Классы. Продолжаем знакомиться. Методы классов
- С++ для начинающих. Конструктор Класса
- С++ для начинающих Конструктор класса с параметрами. Передача в конструктор класса значений
- private, public, protected внутри класса
- Знакомимся с деструктором на примере создания объекта-массива
Без знаний об этих вещах понять даваемую мной здесь информацию может быть труднее. Ну что ж, приступим. Я на этот раз не буду растягивать описание, а просто сразу напишу код и опишу, что и зачем в нём делается. Поскольку предполагается, что вы уже ознакомлены с показанными темами, то сам процесс описания действий с полного нуля только зря засорит информационное поле, необходимое для уяснения.
|
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 |
//Листинг #1 g++ Список FIFO Простой пример кода #include <iostream> /*СТРУКТУРА — ЭТО ЭЛЕМЕНТ СПИСКА, В НАШЕМ СЛУЧАЕ ПРОСТО ЧИСЛО int, НО МОЖЕТ БЫТЬ БОЛЕЕ СЛОЖНОЙ*/ struct Node { int value; //обычное число, мы будем вставлять числа Node *next; //указатель на другой элемент списка Node(int _value) : value(_value), next(NULL) {} //конструктор, используется для инициализации указателей направлением на нулевой адрес }; /*КЛАСС, КОТОРЫЙ И БЫЛ НАШЕЙ ОСНОВНОЙ ЗАДАЧЕЙ, С ПОМЕЩЬЮ НЕГО МЫ РЕАЛИЗУЕМ ОБРАБОТКУ СПИСКА В ФОРМЕ FIFO*/ class FIFO { private: Node *front; //указатель на самый первый элемент списка Node *back; //указатель на последний добавленный элемент списка public: FIFO() : front(NULL), back(NULL) {} //конструктор используется для инициализации указателей направлением на нулевые адреса ~FIFO() { //деструктор, используется для автоматической зачистки памяти в момент прекращения работы класса while (front != NULL) //с помощью цикла вызываем функцию-член класса, освобождающую занятую элементом списка память pop(); //вызов функции-члена класса } void push(int _value) { //функция добавления в список элемента Node *newNode = new Node(_value); //выделение памяти для нового элемента if (front == NULL){ //если элемент первый front = newNode; //направляем указатель front на него } else { back->next = newNode; //в противном случае направляем указатель back->next на созданный узел } back = newNode; //и обозначаем, что созданный узел — это последний, хвостовой, элемент списка } void pop() { // if (front == NULL) throw std::underflow_error("Nothing to dequeue"); if (front == NULL) { //Это упрощённая запись того, что вы видите в закомментированной выше строчке, то обработка путём //выброса исключения, но мы скорее всего плохо понимаем, что это, поэтому так //здесь можно вставить информационное сообщение о том, что список пустой// return; } //Если список не пустой, то делаем организацию fifo Node *temp = front; //Объявляем себе указатель и направляем его на начало списка front = front->next; //Смещаем указатель на начало списка на следующий элемент delete temp; //Высвобождаем память от элемента, который стал уже бывшим первым } /*ФУНКЦИЯ-ЧЛЕН, ВЫВОД ДАННЫХ СПИСКА НА ЭКРАН*/ void print(){ Node *temp = front; //Объявляем себе указатель и направляем его на начало списка while (temp != NULL){ //С помощью цикла обходим весь список std::cout << temp->value << ' '; //Выводим информацию на экран temp = temp->next; //Направляем указатель на следующий элемент } } }; int main(){ FIFO f1; f1.push(100); f1.push(200); f1.print(); } |
Поскольку код достаточно выразителен, его легко запомнить, а по комментариям многое, если не всё, должно проясниться. Но, может, кто-то будет, кому нужно ещё доразжевать один момент. Когда список пустой, понятно, что нужно просто выделить память для вставляемого в список элемента (у нас это сейчас структура, внутри которой хранится число) и вставить туда требуемый элемент путём направления на него указателей. Т. е. мы выделили память, записали в выделенную память какие-то значения и направили на этот участок нужный указатель. В нашем случае нужный указатель определяет головной (передний) элемент списка, поэтому это указатель front. После этого нам указатель front нужен только для обработки, но не для модификации списка, поэтому в операциях вставки о нём можно забыть. Каждый новый вставляемый элемент — это последний элемент списка, следовательно указатель back, обозначающий как раз последний элемент списка, следует направлять на него, но нужно обязательно учесть вставку первого элемента в список: это ситуация, когда и указатель на последний элемент, и указатель на первый элемент направлены на один и тот же участок памяти, на одно и то же значение. Нужно делать корректировку для такой ситуации, в остальном всё довольно просто: сначала мы определяем, что следующий для последнего вставленного элемента будет сейчас вставляемый, направляем на вставляемый back->next и только потом обозначаем, что вставленный элемент оказался последним, направляем на него back. Тут фокус в том, что когда мы смещаем back, на другой элемент списка, он начинает показывать на элемент, внутри которого указатель next указывает на нулевой адрес (благодаря конструктору, описанному внутри структуры). Мы корректируем направление на адрес вставляемого в список элемента, направляем его, и потом снова смещаем back, чтобы опять же скорректировать направление лежащего уже там указателя и т. д.
|
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 81 |
//Листинг #2 g++ Список FIFO Простой пример кода #include <iostream> /*ЭЛЕМЕНТ СПИСКА, ИНОГДА НАЗЫВАЮТ "НОД", "НОДА", "УЗЕЛ"*/ struct Node{ int x; Node *next; }; /*СТРУКТУРА, ОРГАНИЗАЦИЯ FIFO*/ struct Fifo{ Node *head, *tail; Fifo():head(NULL), tail(NULL){} void push(const Node &node); void print() const; ~Fifo(); }; void Fifo::push(const Node &node){ Node *temp = new Node; //*temp = node; //Так можно написать, чтобы не писать две следующие строки //Но это история с конструктором копирования //если вы не знакомы с копирующим конструктором, то копируем структуру в temp //покусочно //Объекты одной структуры можно присваивать друг в друга напрямую, //но с объектами одного класса так нельзя, поэтому показан покусочный способ temp -> x = node.x; temp -> next = node.next; if (head == NULL){ head = temp; } else { tail -> next = temp; } tail = temp; } void Fifo::print() const{ if (!head){ std:: cout << "EMPTY\n"; return; } Node *temp = head; while (temp){ std::cout << temp -> x << ' '; temp = temp -> next; } } /*ДЕСТРУКТОР ДЛЯ ЗАЧИСТКИ ПАМЯТИ*/ Fifo::~Fifo(){ while (head){ Node *temp = head; head = head -> next; delete temp; } } int main(){ Fifo f1; Node n1; //Создали структуру n1 = {10}; //Здесь вставляется цельная структура, не просто число f1.push(n1); n1 = {20}; f1.push(n1); f1.print(); } |
2 комментария на «“С++. Простой пример списка FIFO”»
Добавить комментарий
Случайная книга в электронном формате
Вам обязательно нужно нанять корректора, потому что вы совершенно неграмотны: 19 строк слитых в один абзац — читать просто невозможно!
Так же вам нужно дорабатывать дизайн вашего веб-сайта: оформление просто чудовищное и режет глаз (например, со светлого бело-голубого фона очень тяжело переключаться на угольно черный экран с кодом). Неужели нельзя сделать их в схожих тонах? (Код, конечно, можно переключить на белый, но тогда пропадает форматирование текста.)
Вот веб-сайт с идеальным оформлением, но, к сожалению, представленный на нем материал далек от совершенства: https://codelessons.ru/cplusplus/ochered-queue-v-c-realizaciya-i-chto-eto-voobshhe-takoe.html
И последний вопрос: в чем отличие этих двух кодов программы (листингов)? И там и там он «простой», но в чем их простота?
Простота того кода в том, что механизм полностью скрыт. Берёшь готовое и используешь. Это намного проще, чем здесь.
Код здесь осложнён тем, что раскрывается механизм, скрываемый на том сайте. Из-за этого — текста намного больше. Но даже так, код здесь упрощён тем, что не показывается обязательное: не описываются необходимые конструкторы, например. В коде здесь реализуется три (меньше трёх в принципе никак не выйдет при рассмотрении) метода вместо большего их числа. Вариант, показываемый здесь — студент-академический, он не предназначен без доработки для использования, а код там — вполне годен для использования в боевых программах. Цель статьи, показать в общих чертах, как оно вообще работает.