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

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

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

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

В листинг #3 была создана переменная, которая приравнивается к числу элементов внутри списка. Сами эти элементы считаются при каждом новом добавлении элемента в список (см. листинг #2). Переменную, обозначающую число элементов в списке, лучше не трогать, поэтому обработка ведётся с помощью дополнительной переменной. Ведь может понадобится новая обработка этого списка и размер какой был, таким и должен оставаться (или изменяться только при добавлении/удалении, но не отображении списка на экране).
Обращаю внимание, что в функцию отображения передаётся аргумент, обозначающий количество элементов, помещённых в список. Список ведь кольцевой, и если знать сколько в нём элементов, то будет проще его обработать.

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



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

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

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

  1. 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;

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

  2. Viator:

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

  3. Vus:

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

  4. Виктория:

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

  5. Игорь:

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

  6. Аноним:

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

  7. аноним:

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

  8. Тарас:

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

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

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

https://www.litres.ru/robin-nikson/sozdaem-dinamicheskie-veb-sayty-s-pomoschu-php-mysql-javascript-i-css-2/?lfrom=15589587
Яндекс.Метрика