Как сделать двусвязный список из структуры

Question

Не могу понять механизм реализации двусвязного списка,имеется структура простенькая

    struct Auto
{
    string name;
    string id;
    string colour;

    struct Auto *pPrev,*pNext;
};

и сами функции для работы со структурой

 #include <iostream>
#include<fstream>
#include "AvtoList.h"
using namespace std;

void SetAvtoList(Auto* avto,int size)
{
    int j = 1;

    for (int i = 0; i < size; i++)
    {
        cout << "\nМашина " << j++ << ":" << endl;
        cout << "\nМарка машины: "; cin >> avto[i].name;
        cout << "Номер машины: "; cin >> avto[i].id;
        cout << "Цвет машины: "; cin >> avto[i].colour; cout << endl << endl << "--------------" << endl << endl;
    }

    return;
}

void GetAvtoList(Auto* avto,int size)
{
    int j = 1;
    cout << "\nМашины в БД: "<<endl;
    for (int i = 0; i < size; i++)
    {
        cout << "\nМашина " << j++ << ":" << endl;
        cout << "\nМарка машины: "; cout << avto[i].name;
        cout << "\nНомер машины: "; cout << avto[i].id;
        cout << "\nЦвет машины: "; cout << avto[i].colour; 
        cout << endl << endl << "--------------" << endl << endl;
    }
    return;
}

void GetChoosenAvto(Auto* avto ,int size)
{
    string name;
    int flag = 0,j = 1;
    string colour;
    cout << "Введите желаемые марку и цвет.\n";
    cout << "Марка: "; cin >> name; 
    cout << "Цвет: "; cin >> colour; cout << endl;
    for (int i = 0; i < size; i++)
    {
        if (avto[i].name == name && avto[i].colour == colour)
        {
            cout << "\nМашина № " << j << " по вашему запросу:\n";
            cout << "\nМарка машины: "; cout << avto[i].name;
            cout << "\nНомер машины: "; cout << avto[i].id;
            cout << "\nЦвет машины: "; cout << avto[i].colour;
            cout << endl << endl << "--------------" << endl << endl;
            flag = 1;
        }
        j++;
    }
    if (flag == 0)
        cout << "\nМашин по вашему запросу не найдено.\n";
    return;
}

int main(int argc, char* argv[])
{
    system("chcp 1251>>NULL");

    int size = 0;
    cout << "Введите кол-во машин: "; cin >> size;
    Auto* automobile = new Auto[size];

    SetAvtoList(automobile,size);
    GetAvtoList(automobile, size);
    GetChoosenAvto(automobile, size);

    delete[] automobile;
    return 0;
}

Есть задание сделать из этого двусвязный список,хотел бы разобраться что вообще хотят. Как я понял,то нужна только структура,указатели на следующий и предыдущий элемент сделал,а вот дальше как правильно,в методичке у меня указывается,что нужно создавать отдельную структуру Node(ячейки),в инете почти везде через классы делают,как по всем правилам сделать грамотно двусвязный список,если не готовый код с комментариями,то хотя бы на словах,как поэтапно делать его,как принято и т.д.

Answer 1

Ловите код

#include <iostream>
#include <string>
using namespace std;

// элемент списка машин
struct Auto
{
    string name;
    string id;
    string colour;

    struct Auto *pPrev,*pNext;
};

// Список машин
struct AutoList {
  struct Auto *head, // указатель на первую
    *tail; // указатель на последюю
  // если head == tail == 0 список пустой
  // если head == tail в списке одна машина
};

// вернем указатель на машину, данные размещаются в куче
// указатели на следующий и предыдущий элементы списка обнулим
// при конце ввода вернем 0
Auto *
getAuto ()
{
  Auto *p = new Auto;

  if (cin >> p->name &&
      cin >> p->id &&
      cin >> p->colour) 
    p->pPrev = p->pNext = 0;
  else {
    delete p;
    p  = 0;
  }

  return p;
}

// построим список машин
// последовательно вводим машины из stdin
// каждая новая машина вставляется в конец списка
AutoList
getListAuto (void)
{
  AutoList lst;
  Auto *p = getAuto();     // получаем первую машину
  lst.head = lst.tail = p; // вставляем ее в список
                           // теперь список состоит из одого элемента
                           // у которго пока нет ни следующего, ни предыдущего
                           // (инвариант: if (p) p->pNext == p->pPrev == 0)

  if (p)  // прочли одну, т.е. список не пустой
    while (p = getAuto()) {
      // вставляем новую в конец списка,
      // поэтому head не трогаем
      p->pPrev = lst.tail;
      lst.tail->pNext = p;
      lst.tail = p;
    }

  return lst;
}

// перебираем элементы списка и печатаем их
void
printListAuto (AutoList lst)
{
  for (Auto *p = lst.head; p; p = p->pNext)
    cout << p->name << ' '
         << p->id << ' '
         << p->colour
         << '\n';
}

// очистим память, занимаемую элементами списка
AutoList
freeListAuto (AutoList lst)
{
  for (Auto *p = lst.head; p;) {
    Auto *cur = p;
    p = p->pNext; // нужно прочесть из памяти указатель на следующий
    delete cur;   // до того, как освободим ее
  }

  lst.head = lst.tail = 0;

  return lst;
}

int
main (int ac, char *av[])
{
  AutoList lst = getListAuto();

  printListAuto(lst);

  freeListAuto(lst);
}

Это проще, чем объяснять на словах

БЛОГ НА HUSL

Как сделать двусвязный список из структуры

Ответы (1 шт):