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

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

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

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

  1. Никита:

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

    7
    12
  2. Елена:

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

    9
    11
  3. Андрей:

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

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

      2
      14
      • Андрей:

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

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

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

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

          16
  4. Аноним:

    ❗ ❗ 😯 😮

    14
  5. Александр:

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

    Вместо:

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

    Лучше:

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

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

  6. Илья:

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

    • Илья:

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

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

      4
      8
  7. Александр:

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

  8. Александр:

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

    4
    3
  9. Андрей:

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

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

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

  10. Olya:

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

  11. Empty:

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

  12. Крыл:

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

  13. Марина:

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

  14. Александр:

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

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

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

      1
      3
  15. Vrezh:

  16. апрлап:

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

    4
    2
  17. Аноним:

    хуйня

    8
    1
  18. s:

    c++ code:
    #include
    using namespace std;

    struct Node
    {
    int data;
    Node *Next, *Prev;
    };

    class List
    {
    Node *Head, *Tail;
    public:
    List() :Head(NULL), Tail(NULL) {};

    void Add(int data)
    {
    Node *temp = new Node;
    temp->Next = NULL;
    temp->data = data;

    if (Head != NULL)
    {
    temp->Prev = Tail;
    Tail->Next = temp;
    Tail = temp;
    }
    else
    {
    temp->Prev = NULL;
    Head = Tail = temp;
    }
    }

    void Print()
    {
    Node *temp = Tail;
    while (temp != NULL)
    {
    cout <data <Prev;
    }
    cout << "\n";
    temp = Head;
    while (temp != NULL)
    {
    cout <data <Next;
    }
    cout << endl << endl;
    }
    };
    int main()
    {
    List lst;
    lst.Add(1);
    lst.Add(2);
    lst.Add(3);

    lst.Print();
    system("pause");
    return 0;
    }

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

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

Поиск

 
     

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

https://www.litres.ru/skott-mayers/effektivnoe-ispolzovanie-c-55-vernyh-sposobov-uluchshit-strukturu-i-kod-vashih-programm/?lfrom=15589587
Яндекс.Метрика