С++ для начинающих Кольцевой Однонаправленный список FIFO

По некоторым причинам для начинающих вопрос по кольцевым спискам возникает достаточно часто и заставляет тратить время на осознание этого чуда программерской природы. Кольцевые списки также называют циклические списки. Смысл в том, что у таких списков нет начала и нет конца. Очень похоже на однонаправленный линейный список с небольшим отличием. Там указаны голова и хвост., причем хвост ссылается в никуда. В циклических списках последний ссылается на начало списка и таким образом образуется замкнутый круг.

Так как в в циклическом списке ничто не ссылается на пустоту, то признаком для обработки может быть счетчик элементов списка. В предыдущих статьях я опускал создание счетчика, но тут он будет очень полезен.
Код С++ Циклический (Кольцевой) однонаправленный

Начало положено. В отличии от предыдущих примеров в глаза может броситься название структуры. Но во-первых так часто называют звенья списков (Node), а во вторых в многочисленных примерах можно встретить именно такое название первой структуры. Просто Element (из прошлых моих примеров стало Node). Называть-то можно как душе угодно, главное чтоб вам удобно было и другие могли прочитать то что вы напишете.
Второе отличие появилась переменная size внутри класса List. Лично мне так оказалось вполне удобно в написании кода дальше. Предполагается подсчет элементов внутри списка.
Код С++ Циклический (Кольцевой) однонаправленный

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

Следующий этап написания программы — это отображение списка на экране.

Код С++ Циклический (Кольцевой) однонаправленный

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

Изменилось то, что внутри функии main и вот тут у кого-то может возникнуть вопрос по отображению списка на экране. Кто все понял, тот молодчик, но кому нужно помочь объясняю. Вспоминаем, что внутри списка при каждом новом добавлении элемента счетчик числа элементов увеличивается. Но сам по себе счетчик объявлен внутри класса и в защищенном поле private. Доступ к этому счетчику разрешен только изнутри класса, а вне класса доступ закрыт. Чтобы этот счетчик не был бесполезен нужно создать новую функцию класса, которая и будет возвращать этот счетчик

Код С++ Циклический (Кольцевой) однонаправленный FIFO

Вроде бы всё. Но нет. Ни в коем случае не всё. При динамическом программировании если была выделена память, то выделенную память надо освобождать, чтобы не допустить утечки памяти. Освобождение памяти как и в прошлых примерах удобно описать в деструкторе. Деструктор очень похож на функцию отображения списка.

Код С++ Циклический (Кольцевой) однонаправленный FIFO

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

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

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

  • Slavik говорит:

    1. Утечка памяти
    void List::Show(int temp)
    {

    Node *tempHead= Head;//Саму голову трогать не надо
    //вместо
    ///Node *tempHead=new Node;
    //// tempHead=Head; //Саму голову трогать не надо

    2. Не понял смысла в функции Show(int), передаваемый параметр затирается количеством в списке. Так лучше не делать. Объяснять не буду, но минусы стиль, путаница для другого программиста, быстродействие.

    temp=size; //Временная переменная равная числу элементов в списке
    Лучше сделать так
    void List::Show(void)
    {
    int temp=size;

    • admin говорит:

      1 пункт исправил.
      2 пункт я поясню.
      тут не имеет значения то, что переменная затирается. Так как в момент вызова функции вовнутрь функции передается параметр, а сама функция принимает этот параметр как обычную переменную (не как указатель или ссылку), то внутри функции создается локальная копия переменной, что является аналогом того, что вы в пункте 2 написали. В любом случае переменная вне функции, которую мы отдаем вовнутрь функции работой функции не измениться.

  • Viator говорит:

    а как добавить в кольцевой односвязный список фиктивный элемент, выполняющий роль барьера, между началом и концом списка?

  • Vus говорит:

    Здравствуйте, хотела спросить, а удаление и поиск нужного элемента как производиться, у меня с этим проблемы.

  • Виктория говорит:

    Помогите пожалуйста
    Во всех вариантах необходимо организовать список, состоящий из 10 элементов вводимых с клавиатуры, через функцию вставки первого элемента в список. Организовать функцию просмотра всего списка элементов. Организовать функцию очистки списка. Остальные функции реализовать в соответствии с вариантом.
    17. Организовать однонаправленный линейный список с функцией вывода на экран элементов больших первого элемента.

  • Игорь говорит:

    2 пункт я поясню.
    тут не имеет значения то, что переменная затирается. Так как в момент вызова функции вовнутрь функции передается параметр, а сама функция принимает этот параметр как обычную переменную (не как указатель или ссылку), то внутри функции создается локальная копия переменной, что является аналогом того, что вы в пункте 2 написали. В любом случае переменная вне функции, которую мы отдаем вовнутрь функции работой функции не изменитьс
    Это Ваш ответ от 29.08.2013 в 5:28 пп
    Но все равно можно ведь и сократить код, убрав метод Count (), просто создать локальную переменную в Show и все….

  • Аноним говорит:

    А как удалить любой элемент из списка?

  • аноним говорит:

    А как удалить любой элемент из списка?

  • Тарас говорит:

    И каким боком здесь АДА? Не хорошо так.

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

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

Поиск

 
     

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

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

В обед, шеф заходит в бухгалтерию. На столах лежат "мыши" на спине. Спрашивает: - В чём дело? - Чтобы компьютеры не тормозили, сисадмин рекомендовал класть "мышек" на спину, для отдыха в нерабочее время.

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

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