Cоздать Двунаправленный Список

Тема в разделе "Общие вопросы по С и С++", создана пользователем shilovec5377, 30 май 2013.

  1. shilovec5377

    shilovec5377 Member

    Регистрация:
    13 апр 2012
    Сообщения:
    12
    Симпатии:
    0
    Всем привет! помогите пж сохдать двунаправленный список с числами в диапазоне -50 +50.
    У меня есть простой пример однонаправленной очереди, но не знаю как сделать двунаправленную.
    Помогите пж.

    Код (C++):
    #include <iostream>
    #include <queue>
    #include <cstdlib>

    int main() {

    std::queue<int> q;
    const int N = 10;

    for( int i=0; i<N; ++i )
    {
    q.push( rand() % 100 - 50 );
    }

    while( !q.empty() )
    {
    std::cout << q.front() << " ";
    q.pop();
    }

    return 0;
    }
     
  2. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Код (Text):
    #include <iostream>
    #include <list>
    #include <cstdlib>

    int main() {

    std::list<int> q;
    const int N = 10;

    for( int i=0; i<N; ++i )
    {
    q.push_back( rand() % 100 - 50 );
    }

    while( !q.empty() )
    {
    std::cout << q.front() << " ";
    q.pop_front();
    }

    return 0;
    }
    не проверял
     
  3. shilovec5377

    shilovec5377 Member

    Регистрация:
    13 апр 2012
    Сообщения:
    12
    Симпатии:
    0
    а что изменилось? просто добавили q.pop_front.
     
  4. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    МБ ты сам сможешь найти отличия?
     
  5. shilovec5377

    shilovec5377 Member

    Регистрация:
    13 апр 2012
    Сообщения:
    12
    Симпатии:
    0
    я т их нашел, после этих изменений это стал Двунаправленный Список???
     
  6. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    я не уверен, но мне кажется, что std::list - двусвязный список.
    Нато посмотреть в справочниках.

    ----

    посмотрел: http://www.cplusplus.com/reference/list/list/

    второй абзац:
     
  7. shilovec5377

    shilovec5377 Member

    Регистрация:
    13 апр 2012
    Сообщения:
    12
    Симпатии:
    0
    вот сделал как можно запонить рандомно, помогите с условием: ( поменять местами элементы с максимальныи и минимальным значениями, при этом элементы не должны перемещаться в памяти )
    Код (C++):
    #include <stdlib.h>
    #include <iostream>
    using namespace std;

    struct Node   //Структура являющаяся звеном списка
    {
    int x;   //Значение x будет передаваться в список
    Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка
    };

    class List  //Создаем тип данных Список
    {
    Node *Head,*Tail; //Указатели на адреса начала списка и его конца
    public:
    List():Head(NULL),Tail(NULL){}; //Инициализируем адреса как пустые
    ~List(); //Деструктор
    void Show(); //Функция отображения списка на экране
    void Add(int x); //Функция добавления элементов в список
    };

    List::~List() //Деструктор
    {  
    while (Head) //Пока по адресу на начало списка что-то есть
    {
    Tail=Head->Next; //Резервная копия адреса следующего звена списка
    delete Head; //Очистка памяти от первого звена
    Head=Tail; //Смена адреса начала на адрес следующего элемента
    }
    }

    void List::Add(int x)
    {
    Node *temp=new Node; //Выделение памяти под новый элемент структуры
    temp->Next=NULL; //Указываем, что изначально по следующему адресу пусто
    temp->x=x;//Записываем значение в структуру

    if (Head!=NULL) //Если список не пуст
    {
    temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
    Tail->Next=temp; //Указываем адрес следующего за хвостом элемента
    Tail=temp; //Меняем адрес хвоста
    }
    else //Если список пустой
    {
    temp->Prev=NULL; //Предыдущий элемент указывает в пустоту
    Head=Tail=temp; //Голова=Хвост=тот элемент, что сейчас добавили
    }
    }

    void List::Show()
    {
    //ВЫВОДИМ СПИСОК С КОНЦА
    Node *temp=Tail;
    //Временный указатель на адрес последнего элемента
    while (temp!=NULL) //Пока не встретится пустое значение
    {
    cout<<temp->x<<" "; //Выводить значение на экран
    temp=temp->Prev; //Указываем, что нужен адрес предыдущего элемента
    }
    cout<<"\n";

    //ВЫВОДИМ СПИСОК С НАЧАЛА
    temp=Head; //Временно указываем на адрес первого элемента
    while (temp!=NULL) //Пока не встретим пустое значение
    {
    cout<<temp->x<<" "; //Выводим каждое считанное значение на экран
    temp=temp->Next; //Смена адреса на адрес следующего элемента
    }
    cout<<"\n";
    }

    int main ()
    {

    List lst; //Объявляем переменную, тип которой есть список
    for (int i = 0, n = rand()%11 + 10; i < n; ++i) {
    lst.Add(rand()%101-50);
    }


    lst.Show(); //Отображаем список на экране

    }
     
  8. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    это я не понял, МБ ты не дословно цитируешь или плохо перевел?
    я думаю имеется ввиду что надо std::move использовать
     
  9. shilovec5377

    shilovec5377 Member

    Регистрация:
    13 апр 2012
    Сообщения:
    12
    Симпатии:
    0
    вот код, но что-то выводит только исходный список (заполненный рандомно), а (поменяный min с max) не хочет, может я не так вывожу?

    функция для замены min с max: void List::Swap() //меняем min с max


    Код (C++):
    #include <stdlib.h>
    #include <iostream>
    using namespace std;

    struct Node   //Структура являющаяся звеном списка
    {
    int x;   //Значение x будет передаваться в список
    Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка
    };

    class List  //Создаем тип данных Список
    {
    Node *Head,*Tail; //Указатели на адреса начала списка и его конца
    public:
    List():Head(NULL),Tail(NULL){}; //Инициализируем адреса как пустые
    ~List(); //Деструктор
    void Show(); //Функция отображения списка на экране
    void Add(int x); //Функция добавления элементов в список
    void Swap();//sortirovka
    };

    List::~List() //Деструктор
    {  
    while (Head) //Пока по адресу на начало списка что-то есть
    {
    Tail=Head->Next; //Резервная копия адреса следующего звена списка
    delete Head; //Очистка памяти от первого звена
    Head=Tail; //Смена адреса начала на адрес следующего элемента
    }
    }

    void List::Add(int x)
    {
    Node *temp=new Node; //Выделение памяти под новый элемент структуры
    temp->Next=NULL; //Указываем, что изначально по следующему адресу пусто
    temp->x=x;//Записываем значение в структуру

    if (Head!=NULL) //Если список не пуст
    {
    temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
    Tail->Next=temp; //Указываем адрес следующего за хвостом элемента
    Tail=temp; //Меняем адрес хвоста
    }
    else //Если список пустой
    {
    temp->Prev=NULL; //Предыдущий элемент указывает в пустоту
    Head=Tail=temp; //Голова=Хвост=тот элемент, что сейчас добавили
    }
    }

    void List::Show()
    {
    //ВЫВОДИМ СПИСОК С КОНЦА
    Node *temp=Tail;
    //Временный указатель на адрес последнего элемента
    while (temp!=NULL) //Пока не встретится пустое значение
    {
    cout<<temp->x<<" "; //Выводить значение на экран
    temp=temp->Prev; //Указываем, что нужен адрес предыдущего элемента
    }
    cout<<"\n";
    }



    void List::Swap() //меняем min с max
    {
    Node *min = Head, *max = Head, *cur = Head;     //head element

    //Поиск минимального и максимального узла
    while(cur != Tail)
    {
    cur = cur->Next;
    if(cur->x < min->x)
    {
    min = cur;
    }
    if(cur->x > max->x)
    {
    max = cur;
    }
    }

    Node *beforeMin = min->Prev;
    Node *afterMin = min->Next;

    Node *beforeMax = min->Prev;
    Node *afterMax = max->Next;

    //выбор адресов элементов
    beforeMin->Next = max;
    afterMin->Prev = max;

    beforeMax->Next = min;
    afterMax->Prev = min;

    min->Prev = beforeMax;
    min->Next = afterMax;

    max->Prev = beforeMin;
    max->Next = afterMin;

    //Проверка головы и хвоста
    if(min == Head) Head = max;
    if(min == Tail) Tail = max;

    if(max == Head) Head = min;
    if(max == Tail) Tail = min;
    }



    int main ()
    {

    List lst; //Объявляем переменную, тип которой есть список
    for (int i = 0, n = rand()%11 + 10; i < n; ++i)
    {
    lst.Add(rand()%101-50);
    }


    lst.Show(); //Отображаем список на экране

    lst.Swap(); //Отображаем поменяный список на экране
    return 0;
    }
     

Поделиться этой страницей