С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.89/75: Рейтинг темы: голосов - 75, средняя оценка - 4.89
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
1

Поменять местами два элемента двусвязного списка и удалить из него указанный элемент

29.11.2014, 22:05. Показов 15092. Ответов 16
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Дан двусвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка путём перецепления ссылок на узлы списка, номера которых введёт пользователь с клавиатуры. Удалить элемент списка, номер которого введёт пользователь с клавиатуры. Напечатать получившийся список.

Добавлено через 22 часа 38 минут
Цитата Сообщение от Nosey
Давай изучим swap?
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

#include <iostream>
 
using namespace std;
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
struct MineListNode
{
    MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next;
    MineListNode* prev;
    Data data;
};
 
struct MineList
{
    MineListNode* _head;
    MineListNode* _last;
    MineList() : _head(nullptr), _last(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        if (_head)
        {
            _head->prev = head;
        }
        if (!_last)
        {
            _last = _head;
        }
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            cout << head->data.value << " ";
            head = head->next;
        }
        cout << endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
            return;
 
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 == 0)
            index1Node = _head;
 
        MineListNode* head = _head;
        while (head != nullptr && !index1Node)
        {
            index++;
            if (index == index1)
            {
                index1Node = head->next;
                index--;
                break;
            }
            head = head->next;
        }
        if (index1Node == nullptr)
            return;
        while (head != nullptr)
        {
            index++;
            if (index == index2)
            {
                index2Node = head->next;
                break;
            }
            head = head->next;
        }
 
        if (index2Node == nullptr)
            return;
 
        std::swap(index1Node->prev, index2Node->prev);
        std::swap(index1Node->next, index2Node->next);
        if (index1Node == _head)
        {
            index1Node->prev->next = index1Node;
            if (index2Node == _last)
            {
                index2Node->next->prev = index2Node;
            }
            else
            {
                std::swap(index1Node->next->prev, index2Node->next->prev);
            }
            _head = index2Node;
        }
        else if (index2Node == _last)
        {
            std::swap(index1Node->prev->next, index2Node->prev->next);
            index2Node->next->prev = index2Node;
            _last = index1Node;
        }
        else
        {
            std::swap(index1Node->prev->next, index2Node->prev->next);
            std::swap(index1Node->next->prev, index2Node->next->prev);
        }
    }
};
 
 
void main()
{
    MineList mineList;
    int c;
    cout << "vvedite razmer spiska:" << endl;
    cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    cout << " --------------- " << endl;
    mineList.printList();
    int first, last;
    cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << endl;
    cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    cout << " --------------- " << endl;
    mineList.printList();
 
    cout << endl;
 
    system("pause");
}
Добавлено через 3 минуты
Цитата Сообщение от Dennis Ritchie Посмотреть сообщение
Давай изучим swap?
Давай.
Спасибо за код. Я сломал swap с первого раза. Попробуйте ввести размер списка 5 и поменять местами первый и второй элемент списка. Надо реализовать проверку на выход за границы списка, а то будет плохо...
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 29.11.2014, 22:05
Ответы с готовыми решениями:

Поменять местами два элемента двусвязного списка
Доброго времени суток. Помогите пожалуйста с задачей. Необходимо реализовать функцию, которая...

Поменять местами два элемента односвязного списка
Дан односвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка,...

Удалить элемент из середины двусвязного списка
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека

Удалить элемент в конце двусвязного списка
как удалить элемент в конце двусвязного списка Добавлено через 10 минут while (this-&gt;tail !=...

16
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
29.11.2014, 22:37 2
Лучший ответ Сообщение было отмечено Dennis Ritchie как решение

Решение

Dennis Ritchie,
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

....
 
        if (index2Node == nullptr)
            return;
 
        if (index1Node == _head)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            index1Node->prev->next = index1Node;
            if (index2Node == _last)
            {
                index2Node->next->prev = index2Node;
            }
            else
            {
                std::swap(index1Node->next->prev, index2Node->next->prev);
            }
            _head = index2Node;
            _last = index1Node;
        }
        else if (index2Node == _last)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            std::swap(index1Node->prev->next, index2Node->prev->next);
            index2Node->next->prev = index2Node;
            _head = index2Node;
        }
        else
        {
            std::swap(index1Node->prev->next, index2Node->prev->next);
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next->prev, index2Node->next->prev);
            std::swap(index1Node->next, index2Node->next);
        }
1
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
29.11.2014, 22:53  [ТС] 3
Nosey, а попробуйте пройти любимый тест моего препода. Размер списка равен 2, а поменять нужно нулевой и первый элемент списка.
0
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
06.12.2014, 08:40  [ТС] 4
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

#include <iostream>
 
using namespace std;
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
struct MineListNode
{
    MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next;
    MineListNode* prev;
    Data data;
};
 
struct MineList
{
    MineListNode* _head;
    MineListNode* _last;
    MineList() : _head(nullptr), _last(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        if (_head)
        {
            _head->prev = head;
        }
        if (!_last)
        {
            _last = _head;
        }
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            cout << head->data.value << " ";
            head = head->next;
        }
        cout << endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
            return;
 
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 == 0)
            index1Node = _head;
 
        MineListNode* head = _head;
        while (head != nullptr && !index1Node)
        {
            index++;
            if (index == index1)
            {
                index1Node = head->next;
                index--;
                break;
            }
            head = head->next;
        }
        if (index1Node == nullptr)
            return;
        while (head != nullptr)
        {
            index++;
            if (index == index2)
            {
                index2Node = head->next;
                break;
            }
            head = head->next;
        }
 
        if (index2Node == nullptr)
            return;
 
        if (index2Node == nullptr)
            return;
 
        if (index1Node == _head)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            index1Node->prev->next = index1Node;
            if (index2Node == _last)
            {
                index2Node->next->prev = index2Node;
            }
            else
            {
                std::swap(index1Node->next->prev, index2Node->next->prev);
            }
            _head = index2Node;
            _last = index1Node;
        }
        else if (index2Node == _last)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            std::swap(index1Node->prev->next, index2Node->prev->next);
            index2Node->next->prev = index2Node;
            _head = index2Node;
        }
        else
        {
            std::swap(index1Node->prev->next, index2Node->prev->next);
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next->prev, index2Node->next->prev);
            std::swap(index1Node->next, index2Node->next);
        }
    }
};
 
 
void main()
{
    MineList mineList;
    int c;
    cout << "vvedite razmer spiska:" << endl;
    cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    cout << " --------------- " << endl;
    mineList.printList();
    int first, last;
    cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << endl;
    cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    cout << " --------------- " << endl;
    mineList.printList();
 
    cout << endl;
}
Nosey, помогите, пожалуйста, реализовать проверку на введённый размер списка и на индексы элементов, которые меняются. Например, программа неправильно работает, когда переменная c = 2, first = 0 и last = 1.
И можно ещё напечатать все элементы списка в обратном порядке?
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
07.12.2014, 02:06 5
Лучший ответ Сообщение было отмечено Dennis Ritchie как решение

Решение

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

#include <iostream>
 
using namespace std;
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
struct MineListNode
{
    MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next;
    MineListNode* prev;
    Data data;
};
 
struct MineList
{
    MineListNode* _head;
    MineListNode* _last;
    MineList() : _head(nullptr), _last(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(const Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        if (_head)
        {
            _head->prev = head;
        }
        if (!_last)
        {
            _last = _head;
        }
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            cout << head->data.value << " ";
            head = head->next;
        }
        cout << endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
            return;
 
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        index1Node = get_by_idx(index1 ,_head);
        if (index1Node == nullptr)
            return;
        index2Node = get_by_idx(index2 - index1, index1Node);
 
        if (index2Node == nullptr)
            return;
 
 
        MineListNode
            *n1p, *n1n;//, *n2n, *n2p ;
        n1n = index1Node->next;
        n1p = index1Node->prev;
        //n2n = index2Node->next;
        //n2p = index2Node->prev;
 
        cut_node(index1Node);
        //printList();
        paste_node(index1Node, index2Node);
        //printList();
        if(n1n != index2Node) {
            cut_node(index2Node);
            //printList();
            paste_node(index2Node, n1p);
            //printList();
 
        }
 
    }
private:
    /// вырезает указанное звено из списка
    void cut_node(MineListNode* n) {
        if(n->prev) {
            n->prev->next = n->next;
        }
        if(n->next) {
            n->next->prev = n->prev;
        }
        if(n == _head) _head = _head->next;
        if(n == _last) _last = _last->prev;
        n->next = nullptr;
        n->prev = nullptr;
    }
    /// вставляет звено n после x. при x == nullptr вставляет в начало
    void paste_node(MineListNode* n, MineListNode* x) {
        if (x == nullptr) {
            n->next = _head;
            if (_head) {
                if(_head->next) _head->next->prev = n;
            }
            _head = n;
        }
        else {
            n->next = x->next;
            n->prev = x;//->prev;
            if (x->prev) x->prev->next = n;
            //if (x->next) x->next->prev = n;
            x->next = n;
        }
        if (x == _last) _last = n;
    }
    /// поиск звена по смещению от first
    static MineListNode* get_by_idx(int idx,
                            MineListNode* first) {
        int index = 0;
        while (first) {
            if (index == idx) break;
            first = first->next;
            index++;
        }
        return first;
    }
};
 
 
int main()
{
    MineList mineList;
    int c;
    cout << "vvedite razmer spiska:" << endl;
    cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    cout << " --------------- " << endl;
    mineList.printList();
    int first, last;
    cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << endl;
    cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    cout << " --------------- " << endl;
    mineList.printList();
 
    cout << endl;
    return 0;
}
1
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
13.12.2014, 14:29  [ТС] 6
Объясните, пожалуйста, что значит эта часть кода:
Цитата Сообщение от Cra3y Посмотреть сообщение
C++
1
2
3
4
5
6
7

struct MineListNode
{
    MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next;
    MineListNode* prev;
    Data data;
};
И что значит именно эта строка:
C++
1

MineListNode() : next(nullptr), prev(nullptr) {}
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
13.12.2014, 15:24 7
Dennis Ritchie,
C++
1
2
3
4
5
6
7

struct MineListNode // структура "звено списка"
{
    MineListNode() : next(nullptr), prev(nullptr) {} // Это конструктор по умолчанию, с установкой полей next и prev в nullptr
    MineListNode* next; // следующее "звено"
    MineListNode* prev; // предыдущее "звено"
    Data data; // собственно данные
};
1
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
20.12.2014, 04:35  [ТС] 8
Cra3y, а можно заменить конструктор на что-нибудь более простое?
И ещё программа удаляет один элемент из списка, когда переменная c = 5, first = 2 и last = 3 или при c = 15, first = 1 и last = 2.
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
20.12.2014, 05:16 9
Цитата Сообщение от Dennis Ritchie Посмотреть сообщение
а можно заменить конструктор на что-нибудь более простое?
В смысле? ИМХО, проще не куда. можно только автоматическое обнуление указателей убрать и заполнять их ручками.
Цитата Сообщение от Dennis Ritchie Посмотреть сообщение
И ещё программа удаляет один элемент из списка,
баг в функции paste_node, вроде пофиксил, проверьте
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

#include <iostream>
 
using namespace std;
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
struct MineListNode
{
    MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next;
    MineListNode* prev;
    Data data;
};
 
struct MineList
{
    MineListNode* _head;
    MineListNode* _last;
    MineList() : _head(nullptr), _last(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(const Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        if (_head)
        {
            _head->prev = head;
        }
        if (!_last)
        {
            _last = _head;
        }
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            cout << head->data.value << " ";
            head = head->next;
        }
        cout << endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
            return;
 
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        index1Node = get_by_idx(index1 ,_head);
        if (index1Node == nullptr)
            return;
        index2Node = get_by_idx(index2 - index1, index1Node);
 
        if (index2Node == nullptr)
            return;
 
 
        MineListNode
            *n1p, *n1n;//, *n2n, *n2p ;
        n1n = index1Node->next;
        n1p = index1Node->prev;
        //n2n = index2Node->next;
        //n2p = index2Node->prev;
 
        cut_node(index1Node);
        //printList();
        paste_node(index1Node, index2Node);
        //printList();
        if(n1n != index2Node) {
            cut_node(index2Node);
            //printList();
            paste_node(index2Node, n1p);
            //printList();
 
        }
 
    }
private:
    /// вырезает указанное звено из списка
    void cut_node(MineListNode* n) {
        if(n->prev) {
            n->prev->next = n->next;
        }
        if(n->next) {
            n->next->prev = n->prev;
        }
        if(n == _head) _head = _head->next;
        if(n == _last) _last = _last->prev;
        n->next = nullptr;
        n->prev = nullptr;
    }
    /// вставляет звено n после x. при x == nullptr вставляет в начало
    void paste_node(MineListNode* n, MineListNode* x) {
        if (x == nullptr) {
            n->next = _head;
            if (_head) {
                if(_head->next) _head->next->prev = n;
            }
            _head = n;
        }
        else {
            n->next = x->next;
            n->prev = x;//->prev;
            //if (x->prev) x->prev->next = n;
            if (x->next) x->next->prev = n;
            x->next = n;
        }
        if (x == _last) _last = n;
    }
    /// поиск звена по смещению от first
    static MineListNode* get_by_idx(int idx,
                            MineListNode* first) {
        int index = 0;
        while (first) {
            if (index == idx) break;
            first = first->next;
            index++;
        }
        return first;
    }
};
 
 
int main()
{
    MineList mineList;
    int c;
    cout << "vvedite razmer spiska:" << endl;
    cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    cout << " --------------- " << endl;
    mineList.printList();
    int first, last;
    cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << endl;
    cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    cout << " --------------- " << endl;
    mineList.printList();
 
    cout << endl;
    return 0;
}
1
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
20.12.2014, 05:34  [ТС] 10
Цитата Сообщение от Cra3y Посмотреть сообщение
баг в функции paste_node, вроде пофиксил, проверьте
Да, теперь кажется всё.
Цитата Сообщение от Cra3y Посмотреть сообщение
В смысле? ИМХО, проще не куда. можно только автоматическое обнуление указателей убрать и заполнять их ручками.
Тогда препод начнёт завтра спрашивать: а что означает MineListNode(), а что означает двоеточие, а что означает next, а что означают фигурные скобочки {} и т. д. В общем, я не очень желаю отвечать на такие вопросы, ибо такими вопросами, как обычно, программу у меня не примут, пока не переделаю на что-нибудь более простое, т. е. без конструктора. Как-то так.

Добавлено через 4 минуты
А что, если так сделать?
C++
1
2
3
4
5
6
7

struct MineListNode
{
    //MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next = nullptr;
    MineListNode* prev = nullptr;
    Data data;
};
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
20.12.2014, 05:45 11
Dennis Ritchie, а там то же самое что и в строке 24
C++
1
2
3
4

MineList() :// ":" означает, что тут идет инициализация данных, могут быть вызовы родительских конструкторов
    _head(nullptr), // тоже самое что this->_head = nullptr;
    _last(nullptr) // тоже самое что this->_last = nullptr;
   {} // данные мы уже инициализировали, тело конструктора не содержит дополнительных операций
Добавлено через 3 минуты
в 9й строке, тот же самый прием
C++
1

Data(int value) : value(value) {}
Добавлено через 46 секунд
только инициализируется параметром конструктора
0
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
20.12.2014, 05:49  [ТС] 12
Цитата Сообщение от Cra3y Посмотреть сообщение
Dennis Ritchie, а там то же самое что и в строке 24
Где?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct MineListNode
{
    //MineListNode() : next(nullptr), prev(nullptr) {}
    MineListNode* next = nullptr;
    MineListNode* prev = nullptr;
    Data data;
};
 
struct MineList
{
    MineListNode* _head = nullptr;
    MineListNode* _last = nullptr;
    //MineList() : _head(nullptr), _last(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
Я хочу понять: такая замена, которую произвёл я, корректно будет работать?

Добавлено через 3 минуты
Цитата Сообщение от Cra3y Посмотреть сообщение
в 9й строке, тот же самый прием
А тут как заменять, я не знаю...
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
20.12.2014, 06:09 13
Цитата Сообщение от Dennis Ritchie Посмотреть сообщение
Я хочу понять: такая замена, которую произвёл я, корректно будет работать?
оно не везде соберется http://ideone.com/P4s3E5
Но в С++11 по идее должно работать так же http://en.cppreference.com/w/c... ta_members

Добавлено через 2 минуты
Цитата Сообщение от Dennis Ritchie Посмотреть сообщение
А тут как заменять, я не знаю...
C++
1
2
3
4
5
6

struct Data
{
    int value;
    Data() {}
    Data(int value) { this->value = value; }
};
1
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
20.12.2014, 15:39  [ТС] 14
Cra3y, можете после смены местами элементов списка напечатать список в обратном порядке.

Добавлено через 16 минут
Я написал такую функцию:
C++
1
2
3
4
5
6
7
8
9
10

void printList1()
    {
        MineListNode* head = _last;
        while (head != nullptr)
        {
            cout << head->data.value << " ";
            head = head->prev;
        }
        cout << endl;
    }
Но эта функция при c = 10, first = 0 и last = 9 выдаёт неправильный ответ.

Добавлено через 2 часа 28 минут
Cra3y, пожалуйста, можете помочь именно сейчас. Очень нужно.
0
шКодер самоучка
2282 / 1958 / 945
Регистрация: 09.10.2013
Сообщений: 4,385
Записей в блоге: 3
20.12.2014, 15:43 15
пофиксил вроде
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

#include <iostream>
 
using namespace std;
#if __cplusplus < 201103L
#define nullptr NULL
#endif
struct data_t
{
    int value;
    data_t() {}
    data_t(int value) : value(value) {}
    data_t(const data_t& d) : value(d.value) {}
};
 
struct node_t:public data_t
{
    node_t():
        next(nullptr), prev(nullptr) {}
    node_t(const data_t& d, node_t* n = nullptr, node_t* p = nullptr):
         data_t(d.value),next(n), prev(p) {}
    node_t* next;
    node_t* prev;
    //data_t data;
};
 
struct list_t
{
    node_t* m_head;
    node_t* m_last;
    list_t() : m_head(nullptr), m_last(nullptr) {}
    node_t* head()
    {
        return m_head;
    }
 
    inline void push_front(const data_t& data)
    {
        return paste_node(new node_t(data), nullptr);
    }
    inline void push_back(const data_t& data)
    {
        return paste_node(new node_t(data), m_last);
    }
    inline void reverse_print() const
    {
        return reverse_print_from(m_last);
    }
    inline void forward_print() const
    {
        return forward_print_from(m_head);
    }
 
    void swap_nodes(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
            return;
 
        node_t* index1Node = nullptr;
        node_t* index2Node = nullptr;
 
        index1Node = get_by_idx(index1 ,m_head);
        if (index1Node == nullptr)
            return;
        index2Node = get_by_idx(index2 - index1, index1Node);
 
        if (index2Node == nullptr)
            return;
 
 
        node_t
            *n1p, *n1n;//, *n2n, *n2p ;
        n1n = index1Node->next;
        n1p = index1Node->prev;
        //n2n = index2Node->next;
        //n2p = index2Node->prev;
 
        cut_node(index1Node);
        //forward_print();
        //reverse_print();
        paste_node(index1Node, index2Node);
        //forward_print();
        //reverse_print();
        if(n1n != index2Node) {
            cut_node(index2Node);
            //forward_print();
            //reverse_print();
            paste_node(index2Node, n1p);
            //forward_print();
            //reverse_print();
 
        }
 
    }
private:
    void reverse_print_from(const node_t* tmp) const
    {
        while (tmp != nullptr)
        {
            cout << tmp->value << " ";
            tmp = tmp->prev;
        }
        cout << endl;
    }
    void forward_print_from(const node_t* tmp) const
    {
        while (tmp != nullptr)
        {
            cout << tmp->value << " ";
            tmp = tmp->next;
        }
        cout << endl;
    }
    /// вырезает указанное звено из списка
    void cut_node(node_t* n) {
        if(n == m_head) m_head = m_head->next;
        else if(n->prev) {
            n->prev->next = n->next;
        }
        if(n == m_last) m_last = m_last->prev;
        else if(n->next) {
            n->next->prev = n->prev;
        }
        n->next = nullptr;
        n->prev = nullptr;
    }
    /// вставляет звено n после x. при x == nullptr вставляет в начало
    void paste_node(node_t* n, node_t* x) {
        if (x == nullptr) {
            n->next = m_head;
            if(!m_head) {
                m_head = m_last = n;
            }
            else {
                m_head->prev = n;
                m_head = n;
            }
        }
        else {
            n->next = x->next;
            n->prev = x;//->prev;
            //if (x->prev) x->prev->next = n;
            if (x->next) x->next->prev = n;
            x->next = n;
            if (x == m_last) m_last = n;
        }
    }
    /// поиск звена по смещению от first
    static node_t* get_by_idx(int idx,
                            node_t* first) {
        int index = 0;
        while (first) {
            if (index == idx) break;
            first = first->next;
            index++;
        }
        return first;
    }
};
 
 
int main()
{
    list_t lst;
    int c;
    cout << "vvedite razmer spiska:" << endl;
    cin >> c;
    while (c --> 0)
    {
        lst.push_front(data_t(c));
    }
 
    cout << " --------------- " << endl;
    lst.forward_print();
    lst.reverse_print();
    int first, last;
    cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << endl;
    cin >> first >> last;
    lst.swap_nodes(first, last);
    cout << " --------------- " << endl;
    lst.forward_print();
    lst.reverse_print();
 
    cout << endl;
    return 0;
}
1
0 / 0 / 0
Регистрация: 01.03.2022
Сообщений: 2
01.03.2022, 16:08 16
Цитата Сообщение от Nosey Посмотреть сообщение
Dennis Ritchie,
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

....
 
        if (index2Node == nullptr)
            return;
 
        if (index1Node == _head)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            index1Node->prev->next = index1Node;
            if (index2Node == _last)
            {
                index2Node->next->prev = index2Node;
            }
            else
            {
                std::swap(index1Node->next->prev, index2Node->next->prev);
            }
            _head = index2Node;
            _last = index1Node;
        }
        else if (index2Node == _last)
        {
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next, index2Node->next);
            std::swap(index1Node->prev->next, index2Node->prev->next);
            index2Node->next->prev = index2Node;
            _head = index2Node;
        }
        else
        {
            std::swap(index1Node->prev->next, index2Node->prev->next);
            std::swap(index1Node->prev, index2Node->prev);
            std::swap(index1Node->next->prev, index2Node->next->prev);
            std::swap(index1Node->next, index2Node->next);
        }
думаю, уже очень давно никто не заходил на эту тему, но... я ее нашел, и в общем использовал ваш код для лабы,
но спустя некоторое время, я решил, что хочу оптимизировать свап,
я писал сам, все рабочее, все отлаженное, надеюсь кому-то это понадобится, еще возможно стоит админам добавить это как-то в тему со свапами
единственное, что возможно стоит добавить, это проверку на одинаковость, и на пустой указатель, а так вообще, всё рабочее:
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

template<class T>
inline void List<T>::swapElems(Node<T>*& a, Node<T>*& b)
{
    /* перестановка в правильном порядке
    1 - голова всегда сначала
    2 - хвост всегда в конце
    3 - если b раньше а
    */
    if (a == tail || b == head || b->next == a)swapPointers(a, b);
    /* обмен, который происходит для всех случаев */
    swapPointers(a->next, b->next);
    swapPointers(a->prev, b->prev);
    /* присвоение, если элементы не рядом */
    if (!a->next == b) {
        a->prev->next = a;
        b->next->prev = b;
    }
    /* если рядом или два всего */
    else if (a->next == b) swapPointers(a->prev, b->next);
    /* если не два */
    if (!(a->next == b && a == head && b == tail)) {
        if (!b == tail)a->next->prev = a;
        if (!a == head)b->prev->next = b;
    }
    /* присвоение головы и хвоста в случае необходимости */
    head = a == head ? b : head;
    tail = b == tail ? a : tail;
 
}
template<class T>
inline void List<T>::swapPointers(Node<T>*& a, Node<T>*& b)
{
    Node<T>* buffer = a;
    a = b;
    b = buffer;
}
0
0 / 0 / 0
Регистрация: 01.03.2022
Сообщений: 2
10.05.2022, 23:25 17
позже решил отказаться от дополнительной функции swapPointers(...) и решил написать максимально сжатый код, без лишнего:
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

template<class T>
inline void List<T>::SwapPointers(Elem<T>* a, Elem<T>* b)
{
    if (a == nullptr || b == nullptr || head == nullptr || tail == nullptr || a == b) return;
    Elem <T>* buffer = nullptr;
    if (a == tail || b == head || b->Next() == a) {
    /*  swapPointers(a, b)  */
        buffer = b;
        b= a;
        a= buffer;
    }
 
    /*  swapPointers(a->prev, b->prev)  */
 
    buffer = b->prev;
    b->prev = a->prev;
    a->prev = buffer;
    
    /*  swapPointers(a->next, b->next)  */
 
    buffer = b->next;
    b->next = a->next;
    a->next = buffer;
 
 
    if (a->Prev() != a) {
        a->Prev()->Next(a);
        b->Next()->Prev(b);
    }
    else if (a->Prev() == a) {
        
        /*  swapPointers(a->prev, b->next)  */ 
 
        buffer = b->Next();
        b->Next(a->Prev());
        a->Prev(buffer);   /* buffer from swapPointers(a->next, b->next) */
    
    }
    if (!(a->Prev() == a && a == head && b == tail)) {
        if (b != tail)a->Next()->Prev(a);
        if (a != head)b->Prev()->Next(b);
    }
    head = a == head ? b : head;
    tail = b == tail ? a : tail;
}
Ниже привел разные случаи, если в чем-то ошибся, исправьте, буду рад.
Миниатюры
Поменять местами два элемента двусвязного списка и удалить из него указанный элемент   Поменять местами два элемента двусвязного списка и удалить из него указанный элемент   Поменять местами два элемента двусвязного списка и удалить из него указанный элемент  

Поменять местами два элемента двусвязного списка и удалить из него указанный элемент   Поменять местами два элемента двусвязного списка и удалить из него указанный элемент  
0
10.05.2022, 23:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 10.05.2022, 23:25
Помогаю со студенческими работами здесь

Как из двусвязного списка удалить заданный элемент
как из двусвязного списка удалить заданный элемент? у нас есть список фамилий:...

Если все элементы «двусвязного списка» отрицательны, то удалить элемент «стека»
помогите,пожалуйста... -Если все элементы «двусвязного списка» отрицательны, то удалить элемент...

Поменять местами два элемента массива, равноудалённых от элемента с заданным номером
Помогите с задачей : В отсортированном по убыванию одномерном массиве из N вещественных чисел...

Поменять местами первый элемент первого списка с последним элементом второго списка
Здравствуйте, вот такое задание : Поменять местами первый элемент первого списка с последним...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru