Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 12.05.2020
Сообщений: 6
1

Отсортировать двусвязный линейный список по возрастанию,или убыванию методом пузырька

20.05.2020, 20:58. Показов 168. Ответов 7
Метки нет (Все метки)

функция перестановки ссылок рабочая(вроде бы),узлы добавляются,список заполняется, а вот сама сортировка не работает. Помогите найти ошибку и исправить
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;
class node
{
public:
    node *next;
    node *pred;
    int data;
    node *Root=nullptr;
    node *perest(node *_Root,node* nod1,node *nod2)// перестановка ссылок
    {
        node *lnext,*pnext,*lpred,*ppred;
 
        lpred=nod1->pred;
        ppred=nod2->pred;
        lnext=nod1->next;
        pnext=nod2->next;
        if (nod2==lnext)
        {
            nod2->next=nod1;
            nod2->pred=lpred;
            nod1->next=pnext;
            nod1->pred=nod2;
            if (pnext!=nullptr)
            {
               pnext->pred=nod1;
               nod1->next=pnext;
            }
            if (nod1!=_Root)
            {
               lpred->next=nod2;
               nod2->pred=lpred;
            }
 
        }
            else
 
                if (nod1==pnext)
                {
                    nod1->next=nod2;
                    nod1->pred=ppred;
                    nod2->next=lnext;
                    nod2->pred=nod1;
                    if(lnext!=nullptr)
                    {
                        lnext->pred=nod2;
                        nod2->next=lnext;
                    }
                    if(nod2!=_Root)
                    {
                        ppred->next=nod1;
                        nod1->pred=ppred;
                    }
                }
 
        else
        {
            if(nod1!=_Root){
                lpred->next=nod2;
                nod2->next=lnext;}
        if(nod2!=_Root){
            ppred->next=nod1;
 
            nod2->pred=lpred;}
         nod1->next=pnext; 
        if (pnext!=nullptr){
            pnext->pred=nod1;
           }
         nod1->pred=ppred;
        if (lnext!=nullptr){
            lnext->pred=nod2;}
        }
        if (nod1==_Root)
            return (nod2);
        if (nod2==_Root)
            return(nod1);
        return (_Root);
 
    }
    void add(node *next,node *pred,node* val)// добавление узла
    {
        if (next!=nullptr)
        {
        next->pred =val;
         val->next=next;
        }
        else
        {
            val->next= nullptr;
        }
        if (pred!=nullptr)
        {
        pred->next=val;
          val->pred=pred;
        }
        else
        {
             val->pred=nullptr;
        }
    }
};
 
 
#include <QCoreApplication>
#include<iostream>
#include "node.h"
#include <stdlib.h>
using namespace std;
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    node* Root =nullptr;
    node* next =nullptr;
    node* pred = nullptr;
    int k=0;
  srand( time(0) );
    for (int i=0;i<10;i++)
    {
      node* ptr =new node();
      if(i==0)
      {
       Root = ptr;
      }
     k ++;
    ptr->data = rand();
    ptr->add(next, pred, ptr);
    cout<<i<<")"<<ptr->data<<endl;
    pred=ptr;
    }//заполнение списка
 
//тут я пытаюсь реализовать сортировку, меняются местами p и p->next,при чем не важно кто из них больше,l вообще не меняется
    node *l=Root;
    node *p=Root->next;
    while (l->next!=nullptr)
    {
        while(p->next!=nullptr)
        {
           if(p->data>l->data)
           {
 
            Root=p->perest(Root,l,p);
 
           }
           p=p->next;
        }
       l=l->next;
    }
        cout<<"------------"<<endl;
        p=Root;
        while(p->next!=nullptr)
        {
 
            cout<<p->data<<endl;
            p=p->next;
        }
 
    return a.exec();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.05.2020, 20:58
Ответы с готовыми решениями:

Отсортировать по возрастанию методом пузырька с ограничением первую половинку массива,а вторую по убыванию методом отбора
Отсортировать по возрастанию методом пузырька с ограничением первую половинку массива,а вторую по...

Массив, состоящий из N элементов, отсортировать методом пузырька сначала по возрастанию, а затем по убыванию
Массив, состоящий из N элементов, отсортировать методом пузырька сначала по возрастанию, а затем по...

Сортировка методом пузырька по возрастанию или убыванию
Здравствуйте, Задали задачку, не могу додуматься уже неделю. Вообщем, программа сортирует массив...

Отсортировать массив по убыванию методом "пузырька", а по возрастанию — простым выбором
Всем привет! Задание таково: Я сделал оба массива и застрял на сортировке &quot;пузырьком&quot;. Все...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
7
6595 / 4436 / 1797
Регистрация: 07.05.2019
Сообщений: 13,436
Записей в блоге: 1
20.05.2020, 21:14 2
Цитата Сообщение от babay Посмотреть сообщение
функция перестановки ссылок рабочая(вроде бы),узлы добавляются,список заполняется, а вот сама сортировка не работает. Помогите найти ошибку и исправить
Ошибка в том, что меняешь элементы местами, а потом делаешь p=p->next и l=l->next. Очевидно, что они будут указывать не на тот элемент, который нужен.
0
0 / 0 / 0
Регистрация: 12.05.2020
Сообщений: 6
20.05.2020, 21:42  [ТС] 3
как-то так ? или тут вообще все иначе написать надо?
node *l=Root;
node *p=Root->next;
while (l->next!=nullptr)
{
l=l->next;

while(p->next!=nullptr)
{
p=p->next;
if(p->data>l->data)
{

Root=p->perest(Root,l,p);

}

}

}
0
6595 / 4436 / 1797
Регистрация: 07.05.2019
Сообщений: 13,436
Записей в блоге: 1
20.05.2020, 21:46 4
Цитата Сообщение от babay Посмотреть сообщение
как-то так ? или тут вообще все иначе написать надо?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node *l = Root;
node *p = Root->next;
while (l->next != nullptr)
{
    node *next1 = l->next;
    while (p->next != nullptr)
    {
        node *next2 = p->next;
        
        if (p->data > l->data)
            Root = p->perest(Root, l, p);
 
        p = next2;
    }
    l = next1;
}
1
0 / 0 / 0
Регистрация: 12.05.2020
Сообщений: 6
20.05.2020, 22:23  [ТС] 5
если ваши поправки не сработали ,значит еще где-то ошибку искать?
0
6595 / 4436 / 1797
Регистрация: 07.05.2019
Сообщений: 13,436
Записей в блоге: 1
20.05.2020, 22:26 6
Цитата Сообщение от babay Посмотреть сообщение
если ваши поправки не сработали ,значит еще где-то ошибку искать?
Проверь, что обмен нормально работает, особенно на первом и последнем элементах.
0
0 / 0 / 0
Регистрация: 12.05.2020
Сообщений: 6
20.05.2020, 22:32  [ТС] 7
попробую,спасибо
0
6595 / 4436 / 1797
Регистрация: 07.05.2019
Сообщений: 13,436
Записей в блоге: 1
20.05.2020, 22:36 8
Кстати, тоже неправильно тебе показал.
Списки обычно не сортируют пузырьком, лучше вставками

Добавлено через 3 минуты
Цитата Сообщение от babay Посмотреть сообщение
попробую,спасибо
Там не в обмене проблема, а в том, что в цикле надо отслеживать текущий/следующий элементы с учётом того, что они могут измениться, т.е. не просто по указателю
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.05.2020, 22:36

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Нужно создать линейный двусвязный список, бинарный поиск и сортировку пузырька с флажком
unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics,...

Упорядочить матрицу по возрастанию(методом выбора) и убыванию(методом пузырька).
Дана квадратная матрица А(NxN). Упорядочить матрицу по возрастанию(методом выбора) и...

Отсортировать массив по возрастанию двумя способами – методом «пузырька» и методом «быстрой сортировки» .
Доброго времени суток)Помогите пожалуйста написать вроде поняла быструю сортировку, а как написать...

Отсортировать массив R(20) методом «пузырька» по убыванию
Отсортировать массив R(20) методом «пузырька» по убыванию. Составить программу для сортировки...

Отсортировать массив по убыванию методом “пузырька”
Требуется отсортировать массив по убыванию методом “пузырька”. Ребят срочно нужен код..

Отсортировать массив по убыванию методом пузырька
Вот то что у меня получилось #include&lt;iostream&gt; #include&lt;conio.h&gt; #include&lt;math.h&gt; using...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.