Двусвязный список в С++ для начинающих

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

В деструкторе прописан код, освобождающий те ячейки памяти, которые были задействованы программой.
В листинге #1 стоит обратить внимание на функцию добавления элементов в список: на логику и порядок выполнения действий.
В функции отображения, независимо от того, с какой стороны просматривать список, признаком окончания списка является пустое поле и просматривать можно как с начала, так и с конца.
Кто-то может спросить: "А как определяется то, что список двусвязный?". Просто в структуре, обозначающей звено списка (тут это Node), имеется два адресных поля: *Next и *Prev, обозначающие адреса на правый и левый элемент (следующий и предыдущий). Так как адресных полей два, где одно связывает элемент с адресом правого соседа, а другое с адресом левого, то и список называется двусвязным.
Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

33 комментария: Двусвязный список в С++ для начинающих

  • Никита говорит:

    39. temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
    Вместо tail должно быть Head, или я не прав?




    1



    2
  • Елена говорит:

    действительно мало кто подробно описывет эти темы.. Спасибо !!!




    4



    3
  • Андрей говорит:

    Оч классно расписано, нравится ваш сайт, не первый раз на него попадаю и нахожу нужный ответ… но к сожалению у меня по ходу проблема со списками… Мне нужно написать прогу где двунаправленный список с информационным полем char и нужно добавить к списку элементы с номерами 1,3,5 итд.. Как это реализовать?? Может есть прога похожая где нить?? ссори если не туда пишу…




    2



    2
    • admin говорит:

      Я не совсем задание понимаю. Две разные ситуации по вашим словам возможны:
      1) нужно в список добавить определенное количество нечетных чисел, идущих подряд.
      2) нужно взять из массива элементы на нечетных индексах и переписать эти значения из массива в список.
      проги нет.
      вроде реализовать совсем просто, можно попробовать. только уточните, что нужно.




      0



      5
      • Андрей говорит:

        Спасибо большое за внимание и спасибо вашему сайту, снова благодаря вам решил задачку)) вот мое решение:
        http://pastebin.com/1iPbNQ1m
        Но есть вопрос, как в конце программы удалить список? т.е. очистить память?? И еще один вопрос (пользуясь случаем):
        Нужно сделать бинарное дерево, где тип информационного поля int и найти максимальный элемент в списке… Может есть что то похожее у вас??
        с приогромнейшим уважением и благодарностью!!




        0



        2
        • admin говорит:

          Если смотреть на приведенный здесь пример, то
          Удаление списка из памяти описано в деструкторе. Деструктор вызывается автоматически после выполнения работы программы, поэтому список здесь автоматически удаляется из памяти. Если читали про конструктор/деструктор, должны это знать.

          Про бинарные деревья у меня только 2 темы.
          http://ci-plus-plus-snachala.ru/?p=89
          http://ci-plus-plus-snachala.ru/?p=90

          Разбираться не очень хочется с чужими задачами, вы уж простите. Но если логику поймете, то, думаю, сами своими силами сможете решить вашу задачу. Я скажу то, в чем не уверен совсем, и, возможно, я ошибусь, но
          Поиск элемента выполняется при помощи обхода дерева, вы проверяете новый элемент с последним запомненным и если новый элемент больше, записываете его на место последнего запомненного. После выполнения обхода по дереву вам остается вывести запомненный элемент на экран. У меня описаны три вида обходов, любой из них подойдет.




          0



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

    ❗ ❗ 😯 😮




    0



    2
  • Александр говорит:

    Не очевидные название переменной в деструкторе.

    Вместо:

    Tail=Head->Next;
    delete Head;
    Head=Tail;

    Лучше:

    Node *temp;
    ...
    temp=Head->Next;
    delete Head;
    Head=temp;
    ...




    0



    2
    • admin говорит:

      Может и лучше, но принципиальной разницы нет.
      Лучше так или не лучше должно зависеть от того как человек представляет весь процесс в воображении. Для одних моя запись (именно по этому примеру) очевидна, для других нет.
      Хотя я согласен, что лучше объявить доп переменную.




      0



      2
  • Илья говорит:

    Копирую вашу программу и мне выдаёт 0 error(s), 1 warning(s): warning C4508: ‘main’ : function should return a value; ‘void’ return type assumed. В чем проблема?




    0



    2
    • Илья говорит:

      И при нажатии на ошибку выделяет 82 строку




      0



      2
    • admin говорит:

      warning — не ошибка, а только и только предупреждение.
      void main() не по стандарту, пропустят не все компиляторы.,
      правильно




      0



      2
  • Александр говорит:

    temp=temp->Next; //Смена адреса на адрес следующего элемента
    можете объяснить , что здесь происходит , ведь если это и так итератор нельзя ли просто temp=Next ? или с итераторами нельзя проделывать данную операцию?




    0



    2
  • Александр говорит:

    Цены, тебе нет) Очень помог, выручил, слов нет




    0



    2
  • Андрей говорит:

    Добрый день! В программировании я новичек, но мне поставили задачу от которой будет зависеть мое будущее:

    Используя ООП подход реализовать двухсвязный список. Каждый элемент списка может содержать один объект. Объект может быть трех типов: «целое число», «вещественное число», «строка». В разных узлах одного списка может быть любой объект одного из допустимых типов. Каждый объект должен иметь возможность вывести свое содержимое на консоль. У списка должен быть метод, выводящий все элементы.
    Класс списка реализовать с «нуля» (не используя темплейты, std::list или аналоги) При реализации класса «строка» можно использовать std::string.

    Как мне это лучше реализовать? напишите мне на E-mail: fastmoney7@mail.ru
    Спасибо!




    0



    2
  • Olya говорит:

    Спасибо большое 🙂




    0



    2
  • Empty говорит:

    А функция удаления? Пожалуйста, можете написать эту функцию хотя бы в коментах.




    0



    2
  • Светлана говорит:

    Помогите пожалуйста реализовать функцию взаимообмена узлов в двусвязном линейном списке 😉

    Автор сайта отвечает:
    Не могу помочь.




    0



    1
  • Крыл говорит:

    Спасибо за статьи. Очень помогло написать лабу.




    0



    3
  • Марина говорит:

    А не подскажите как заполнять двусвязный список вводимыми данными?




    0



    2
  • Александр говорит:

    А можно реализовать без класса или как использовать данный пример в windows forms, необходимо вывести элементы в ListBox




    0



    1
    • admin говорит:

      Поменять «class» на «struct».
      Без класса (структуры) — никак. Это собственный тип данных, имеющий определённые способности, которым научен.

      С Windows Form дела не имел. Это не С++ как таковой. Хотя в QT можно создавать.




      1



      2
  • Vrezh говорит:




    0



    1
  • апрлап говорит:

    привет
    я в шоке
    (не могу работать)
    🙂




    3



    1
  • salaga говорит:

    kek




    2



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

    хуйня




    3



    0

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

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

− 7 = 2

Поиск

 
     

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

https://www.litres.ru/larri-ulman/osnovy-programmirovaniya-na-rnr-22872234/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Встречает в аду один черт другого и говорит: "Слушай, это ты того компьютерщика сюда притащил?" - "Да, а что?" - "Ты в другой раз толком объясняй, что такое ад - а то он, пока понял, что это не Doom, двести чертей перестрелял..."

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

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