Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
#1

Реверс двусвязного списка - C++

13.08.2014, 22:58. Просмотров 767. Ответов 9
Метки нет (Все метки)

Столкнулся с задачей написать функцию реверса двусвязного списка. Часа 3 сушил себе мозг с копиями указателей, получилось что надо хранить копию данных и копию адреса 1 узла да еще и копировать все в ручную поэлементно. Выглядит очень громоздко...
Так вот сам вопрос то, зачем вообще может понадобиться такая функция если список можно обойти в обоих направлениях ( задача из книги "Язык программирования" Страуструп)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vourhey
Почетный модератор
6473 / 2248 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
13.08.2014, 23:03     Реверс двусвязного списка #2
Цитата Сообщение от MousePro Посмотреть сообщение
Часа 3 сушил себе мозг с копиями указателей
Почему нельзя просто поменять местами данные, не трогая указателей?
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
13.08.2014, 23:07  [ТС]     Реверс двусвязного списка #3
Сначала я подумал - просто поменять местами данные - легко(до этого сортировку пузырьком писал), потом вообще подумал зачем что то трогать если можно обойти в с конца. Потом я подумал реально ли сделать поменяв указатели,с 1-го раза не получилось, потом с 2 не получилось,ну а потом я просто не мог забить, ну а когда написал ужаснулся
Vourhey
Почетный модератор
6473 / 2248 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
13.08.2014, 23:22     Реверс двусвязного списка #4
Цитата Сообщение от MousePro Посмотреть сообщение
Так вот сам вопрос то, зачем вообще может понадобиться такая функция если список можно обойти в обоих направлениях
Да ни за чем, просто для тренировки.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
14.08.2014, 14:06     Реверс двусвязного списка #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от MousePro Посмотреть сообщение
получилось что надо хранить копию данных и копию адреса 1 узла да еще и копировать все в ручную поэлементно. Выглядит очень громоздко...
Да вроде не очень:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/////////////////////////////////////////////////////////////////////////////////////////
//написать функцию реверса двусвязного списка
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T_key >
struct  T_node
{
    //-----------------------------------------------------------------------------------
    T_key       key_;
    T_node  *   prev_;
    T_node  *   next_;
    //-----------------------------------------------------------------------------------
    T_node
        (
            T_key       key     =   T_key(),
            T_node  *   prev    =   nullptr,
            T_node  *   next    =   nullptr
        )
        :
        key_    ( key   ),
        prev_   ( prev  ),
        next_   ( next  )
    {}
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T_key >
class   T_list
{
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    typedef T_node  < T_key >       T_node_type;
    typedef T_node_type         *   T_link;
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    T_link  head_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_list()
        :
        head_()
    {}
    //-----------------------------------------------------------------------------------
    void    push_front( T_key   const   &   key )
    {
        head_   =   new     T_node_type
                                (
                                    key,
                                    nullptr,
                                    head_
                                );
 
        if( head_->next_ != nullptr )
        {
            head_->next_->prev_     =   head_;
        }
    }
    //-----------------------------------------------------------------------------------
    void    print()
    {
        T_link  temp_node_ptr   =   head_;
 
        while   (
                    temp_node_ptr   !=  nullptr
                )
        {
            std::cout   <<  temp_node_ptr->key_
                        <<  '\t';
 
            temp_node_ptr   =   temp_node_ptr->next_;
        }
        std::cout   <<  std::endl;
    }
    //-----------------------------------------------------------------------------------
    void    reverse()
    {
        if( head_ == nullptr )
        {
            return;
        }
 
        for(;;)
        {
            std::swap
                (
                    head_->prev_,
                    head_->next_
                );
 
            T_link  prev    =   head_->prev_;
 
            if( prev == nullptr )
            {
                break;
            }
 
            head_   =   prev;
        }//for
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_list<int>     int_list;
    const   int     LIST_SIZE   =   10;
 
    for( int  i = 0; i < LIST_SIZE; ++i )
    {
        int_list.push_front(i);
    }//for
 
    int_list.print      ();
    int_list.reverse    ();
    int_list.print      ();
 
    system("pause");
}
Fallenworld
76 / 76 / 9
Регистрация: 14.04.2014
Сообщений: 408
14.08.2014, 14:33     Реверс двусвязного списка #6
Цитата Сообщение от Mr.X Посмотреть сообщение
C++
1
2
3
4
5
6
7
T_link *prev * *= * head_->prev_;
if( prev == nullptr )
* * * * * * {
* * * * * * * * break;
* * * * * * }
head_ * = * prev;
* * * * }//for
а почему нельзя просто
C++
1
2
if(head_->prev) return;
else head_ = head_->prev;
я имею ввиду без доп обьекта
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
14.08.2014, 14:56     Реверс двусвязного списка #7
Цитата Сообщение от Fallenworld Посмотреть сообщение
а почему нельзя просто
Код C++
1
2
if(head_->prev) return;
else head_ = head_->prev;
я имею ввиду без доп обьекта
Ну, именно чтобы избежать повторения выражения "head->prev", ибо на повторение кода у меня аллергия.
Kuzia domovenok
1888 / 1743 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
14.08.2014, 15:52     Реверс двусвязного списка #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Vourhey, а зачем в СПИСКЕ менять данные? Как же оптимизация? Или ты проги пишешь по принципу "быстрее бы реализовать первое же простейшее решение".

MousePro, для реверса двусвязного списка достаточно у каждого элемента поменять местами PREV и NEXT
MousePro
49 / 30 / 1
Регистрация: 25.04.2013
Сообщений: 366
14.08.2014, 17:15  [ТС]     Реверс двусвязного списка #9
Чел ты всегда так форматируешь код, как то не удобно читать

Добавлено через 31 минуту
А почему у тебя 1 указатель на структуру, а у меня 2 ?))
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
struct Node
    {
        string name;
        Node * Next;
        Node *Prev;
    };
    int count = 0;
    Node * Head = NULL;
    Node *Tail = NULL;


push
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
oid push(string a)
    {
        Node *temp = new Node;
        temp->Next = NULL;
        temp->name = a;
        if (Head != NULL)
        {
            temp->Prev = Tail;
            Tail->Next = temp;
            Tail = temp;
        }
        else
        {
            temp->Prev = NULL;
            Head = temp;
            Tail = temp;
        }
        count++;
    }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2014, 01:21     Реверс двусвязного списка
Еще ссылки по теме:

C++ Сериализация и десериализация двусвязного списка
C++ Удаление из двусвязного циклического списка
C++ Создание двусвязного списка
Реверс списка C++
C++ Функция удаления из двусвязного списка

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gray_fox
What a waste!
1253 / 1136 / 54
Регистрация: 21.04.2012
Сообщений: 2,359
Завершенные тесты: 3
15.08.2014, 01:21     Реверс двусвязного списка #10
как вариант
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <utility>
 
 
template<typename T>
class list {
 
   struct list_node;
   struct list_node_base;
 
 
public:
   void reverse() {
      std::swap(head.prev, head.next);
      for (list_node_base * p = head.prev; p != &head; p = p->prev) {
         std::swap(p->prev, p->next);
      }
   }
 
   bool empty() const {
      return &head == head.next;
   }
   
   void push_back(T const& value) {
      head.insert_before(new list_node(value));
   } 
   
   template<typename F>
   void apply(F f) const {
      for (list_node_base * p = head.next; p != &head; p = p->next) {
         f(p->get_data());
      }
   }
 
   ~list() {
      while (!empty()) {
         head.next->erase();
      }
   }
 
 
private:
   struct list_node_base {
 
      list_node_base() : prev(this), next(this) {}
 
      void insert_before(list_node_base * const what) {
         prev->next = what;
         what->prev = prev;
         
         this->prev = what;
         what->next = this;
      }
 
      void erase() {
         prev->next = next;
         next->prev = prev;
         
         delete static_cast<list_node *>(this);
      }
 
      T & get_data() {
         return static_cast<list_node *>(this)->data;
      }
      T const& get_data() const {
         return static_cast<list_node const*>(this)->data;
      }
 
      list_node_base * prev;
      list_node_base * next;
   };
 
   struct list_node : list_node_base {
    
      list_node(T const& data) : data(data) {}
 
      T data;
   };
 
   list_node_base head;
};
 
 
int main() {
   list<int> instance;
   
   for (int i = 0; i != 5; ++i) {
      instance.push_back(i);
   }
   
   auto const printer = [](int const value) {
      std::cout << value << ' ';
   };
   
   instance.apply(printer);
   std::cout << std::endl;
   
   instance.reverse();
   
   instance.apply(printer);
   std::cout << std::endl;
}
http://ideone.com/GBZvde
Yandex
Объявления
15.08.2014, 01:21     Реверс двусвязного списка
Ответ Создать тему
Опции темы

Текущее время: 12:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru