Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.61/18: Рейтинг темы: голосов - 18, средняя оценка - 4.61
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 10
1

Сортировка кольцевого двусвязного списка (пузырьковая)

25.06.2015, 06:14. Показов 3290. Ответов 7
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Доброго дня! Помогите пожалуйста разобраться с сортировкой кольцевого двухсвязного списка. У меня при попытке отсортировать выводит ошибку
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

#include <iostream>
using namespace std;
struct node
{
  int elem;
  node *sled;
  node *pred;
};
 
class Spisok
{
  private:
    node *nsp;
  public:
    Spisok() {nsp=NULL;}
    void BuiltRing (int i);
    void Sort();
};
void Spisok::BuiltRing (int k)
// Построение двунаправленного кольцевого списка nsp
 
// nsp - указатель на заглавное звено списка.
{
  node *r;
  int el;
  //Построим заглавное звено кольцевого списка.
  nsp = new(node);
  r = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL;
  
  el=rand()%100;
  
  for (int i=0; i<k;i++)
  {
    (*r).sled = new (node);
    (*((*r).sled)).pred = r; r = (*r).sled;
    (*r).sled = NULL; (*r).elem = el;
    el=rand()%100;
    
  }
  //образуем кольцевой список
  if  ((*nsp).sled!=NULL)
    { (*((*nsp).sled)).pred = r; (*r).sled = (*nsp).sled; }
  else
    cout<<"Кольцевой список пуст!\n";
}
 
//Вывод кольца по часовой стрелке
void Spisok::VyvodLeftRight ()
// Вывод содержимого двунаправленного кольцевого списка
// с удаленным заглавным звеном "по часовой стрелке".
// nsp - указатель на заглавное звено списка.
{
  node *r;
 
  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*nsp).sled)).elem<<" ";
    r = (*((*nsp).sled)).sled;
    while  (r!=(*nsp).sled)
      { cout<<(*r).elem<<" "; r = (*r).sled; }
    cout<<endl;
  }
  else cout<<"пуст!";
}
 
//Сортировка
void Spisok::Sort()
 {
    
    node *list;
    list = new(node);
        node * n;
    n = new(node);
    node * n2; 
    n2 = new(node);
 
      for( n = list; n; n = (*n).sled )
        for( n2 = list; n2; n2 = (*n2).sled )
            if( (*n).elem > (*n2).elem ){ /*если число из n меньше числа из n2 то переставляем их; выдаёт ошибку на этой строке*/
                int i = (*n).elem;
                (*n).elem = (*n2).elem;
                (*n2).elem = i;
            }
 if  ((*list).sled!=NULL)
    { (*((*list).sled)).pred = n; (*n).sled = (*list).sled; }
     std::cout<<"\n";
    
 }
 
 
void main ()
{
  setlocale(LC_ALL,"Russian");
    Spisok A;
char otv;
  do 
{ 
cout << "1. Добавление случайных значений" << endl 
<< "2. Вставка после элемента"<<endl
<< "3. Вставка перед элементом"<< endl 
<< "4. Удаление элемента" << endl
<< "5. Сортировка"<<endl
<< "0. Выход" << endl 
<< " = "; 
cin >> otv;
switch(otv) 
{ 
case '1': 
  cout<< "Введите количество элементов"<<endl;
  int n;
  cin>>n;
  A.BuiltRing (n);
  cout<<"Содержимое кольца 'по часовой стрелке': \n";
  A.VyvodLeftRight ();
 // cout<<"Содержимое кольца'против часовой стрелки': \n";
 // A.VyvodRightLeft ();
  break;
case '5':
    A.Sort();
    A.VyvodLeftRight();
    break;
case '0':
    break;
    default:
cout << endl << "Ошибка" << endl; 
break;}
}
while(otv!='0');
cin.get();
system("pause");
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 25.06.2015, 06:14
Ответы с готовыми решениями:

Сортировка слиянием кольцевого списка
Есть класс двусвязного кольцевого списка и итератор к нему-шаблоны. не могу довести до ума...

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка
Здравствуйте! Возникла проблема с программой. Тема: &quot;Сортировка двусвязного списка путем исключения...

Пузырьковая сортировка односвязного списка
Здравствуйте! Увидел на форуме данный алгоритм сортировки односвязного списка. Можете, пожалуйста,...

Сортировка выбором двусвязного списка
Помогите пожалуйста написать функцию которая сортирует двусвязный список методом выбора Вот...

7
55 / 56 / 34
Регистрация: 29.12.2012
Сообщений: 478
25.06.2015, 09:03 2
у тебя две функции в классе, а на код уже не приятно смотреть зачем эти коментарии?
C++
1
2
3

// Построение двунаправленного кольцевого списка nsp
 
// nsp - указатель на заглавное звено списка.
вообше не очем,и противно смотреть...
если так хочеш прокоментировать что делают функции
C++
1
2
3
4
5
6
7
8
9
10

class Spisok
{
  private:
    node *nsp;               //указатель на заглавное звено списка
  public:
    Spisok() {nsp=NULL;}     //конструктор
    void BuiltRing (int i);       //строит список
    void VyvodLeftRight ();   //выводит список
    void Sort();                  //сортирует список
};
а если еше немного подумать и вспомнить для чего существуют коментарии,тоесть возможность обьяснить участок кода который не понятный сразу,то делать надо так
C++
1
2
3
4
5
6
7
8
9
10

class Spisok
{
  private:
    node *nsp;               //указатель на заглавное звено списка
  public:
    Spisok() {nsp=NULL;}     
    void BuiltRing (int i);  
    void VyvodLeftRight (); 
    void Sort();             
};
так как именна методов информативные,а вот указатель сразу можна не понять что делает...
ты же писал в коментариях изложения в котором просто поток инфы...

про ошибки
C++
1

void Spisok::VyvodLeftRight ()  //забыл определить ты его в классе
и еше пару мелких
C++
1
2
3
4
5
6
7
8

 case '0':
  //  break;лишний брик,слово "Ошибка" никогда невыведится
    default:
cout << endl << "Ошибка" << endl; 
break;}
}while(otv!='0');
 //cin.get(); и system и это одно и тоже в твоей(тоесть не длает закрытсяконсоли)
 system("pause");
Этого хватит чтобы запустить твою програму заполнить сможеш(кстате ты не задал зерно для рандомных чисел из-за этого при каждом запуске одинаковые числа будут),
а вот сортировка не работает гдето ошибка там...
КСТАТЕ Про правильные отступы и работу пробелом я вообше молчю, подправь код чтобы на него смотреть можна было и тебе скорее всего помогут...
0
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 10
25.06.2015, 09:33  [ТС] 3
Я привёл только кусок кода, может, при копировании чего напортачил. А так всё там работает кроме сортировки.
Могу весь текст привести
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248

#include <iostream>
using namespace std;
struct node
{
  int elem;
  node *sled;
  node *pred;
};
 
class Spisok
{
  private:
    node *nsp;
  public:
    Spisok() {nsp=NULL;}
    void BuiltRing (int i);
    void VyvodLeftRight ();
    void VyvodRightLeft ();
    void InsAfter (node*,int);
    void InsBefore (node*,int);
    void Delete (node*);
    void DelAfter (node*);
    node *SearchRing (int);
    void Sort();
    void Ochistka();
    
 
    
};
void Spisok::BuiltRing (int k)
{
  node *r;
  int el;
  nsp = new(node);
  r = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL;
  el=rand()%100;
  for (int i=0; i<k;i++)
  {
    (*r).sled = new (node);
    (*((*r).sled)).pred = r; r = (*r).sled;
    (*r).sled = NULL; (*r).elem = el;
    el=rand()%100;
  }
  //образуем кольцевой список
  if  ((*nsp).sled!=NULL)
    { (*((*nsp).sled)).pred = r; (*r).sled = (*nsp).sled; }
  else
    cout<<"Кольцевой список пуст!\n";
}
 
void Spisok::VyvodLeftRight ()
{
  node *r;
  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*nsp).sled)).elem<<" ";
    r = (*((*nsp).sled)).sled;
    while  (r!=(*nsp).sled)
      { cout<<(*r).elem<<" "; r = (*r).sled; }
    cout<<endl;
  }
  else cout<<"пуст!";
}
 
void Spisok::VyvodRightLeft ()
{
  node *r;
 
  cout<<"Кольцевой список: ";
  if  ((*nsp).sled!=NULL)
  {
    cout<<(*((*((*nsp).sled)).pred)).elem<<" ";
    r = (*((*((*nsp).sled)).pred)).pred;
    while  (r!=(*((*nsp).sled)).pred)
      { cout<<(*r).elem<<" "; r = (*r).pred; }
    cout<<endl;
  }
  else cout<<"пуст!";
}
 
node *Spisok::SearchRing (int el)
{
  node   *q;
  node   *p;
  node *Res;
 
  Res = NULL; p = nsp;
  if  ((*((*p).sled)).elem==el) Res = (*p).sled;
  else
  {
    q = (*((*p).sled)).sled;
    while  (q!=(*p).sled && Res==NULL)
      if  ((*q).elem==el) Res = q;
      else  q = (*q).sled;
  }
  return Res;
}
 
void Spisok::InsAfter (node *Res,int el)
{
  node *q;
 
  q = new(node);
  (*q).elem = el; (*q).sled = (*Res).sled;
  (*q).pred = (*(*Res).sled).pred;
  (*(*Res).sled).pred = q; (*Res).sled = q;
}
 
void Spisok::InsBefore (node *Res,int el)
{
  node *q;
 
  q = new(node);
  (*q).elem = el;
  (*q).sled = (*(*Res).pred).sled; (*q).pred = (*Res).pred;
  (*(*Res).pred).sled = q; (*Res).pred = q;
  if  (Res==(*nsp).sled) (*nsp).sled = q;
}
 
void Spisok::Delete (node *Res)
{
  if  ((*Res).sled==Res)
    { (*nsp).sled = NULL; delete Res; }
  else
  {
    (*(*Res).sled).pred = (*Res).pred;
    (*(*Res).pred).sled = (*Res).sled;
    if  ((*nsp).sled==Res)
     
      (*nsp).sled = (*Res).sled;
    delete Res;
  }
}
 
 
 
    
 
 void Spisok::Sort()
 {
    node *list;
    list = new(node);
    node * n;
    n = new(node);
    node * n2; 
    n2 = new(node);
 
      for( n = nsp; (*n).sled!=NULL; n = (*n).sled )
        for( n2 = nsp; (*n2).sled!=NULL; n2 = (*n2).sled )
            if( (*n).elem > (*n2).elem ){ // если число из n меньше числа из n2 то переставляем их
                int i = (*n).elem;
                (*n).elem = (*n2).elem;
                (*n2).elem = i;
            }
 if  ((*nsp).sled!=NULL)
    { (*((*nsp).sled)).pred = n; (*n).sled = (*nsp).sled; }
     std::cout<<"\n";
    
 }
 
 
void Spisok::Ochistka()
{
  node *q,*q1;
 
  q = (*((*nsp).sled)).sled;
  q1 = (*q).sled;
  while (q1!=(*((*nsp).sled)).sled)
    { delete q; q=q1; q1=(*q1).sled; }
  delete q;
  delete nsp;
}
 
void main ()
{
  setlocale(LC_ALL,"Russian");
    Spisok A;
  node *Res;
  int el,el1;
  char otv;
  do 
{ 
cout << "1. Добавление случайных значений" << endl 
<< "2. Вставка после элемента"<<endl
<< "3. Вставка перед элементом"<< endl 
<< "4. Удаление элемента" << endl
<< "5. Сортировка"<<endl
<< "0. Выход" << endl 
<< " = "; 
cin >> otv;
switch(otv) 
{ 
case '1': 
  cout<< "Введите количество элементов"<<endl;
  int n;
  cin>>n;
  A.BuiltRing (n);
  cout<<"Содержимое кольца 'по часовой стрелке': \n";
  A.VyvodLeftRight ();
  cout<<"Содержимое кольца'против часовой стрелки': \n";
  A.VyvodRightLeft ();
  break;
case '2':
cout<<"Введите элемент звена, после которого ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    {A.InsAfter (Res,el1); A.VyvodLeftRight ();}
  else  cout<<"Звена с таким элементом в списке нет!\n";
  break;
case '3':
    cout<<"Введите элемент звена, перед которым ";
  cout<<"осуществляется вставка: ";
  cin>>el;
  cout<<"Введите элемент вставляемого звена: ";
  cin>>el1;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    { A.InsBefore (Res,el1); A.VyvodLeftRight (); }
  else  cout<<"Звена с таким элементом в списке нет!\n";
    break;
case '4':
    cout<<"Введите элемент звена, который ";
  cout<<"надо удалить: ";
  cin>>el;
  Res = A.SearchRing (el);
  if  (Res!=NULL)
    { A.Delete (Res); A.VyvodLeftRight (); }
  else  cout<<"Звена с таким элементом в списке нет!\n";
    break;
case '5':
    A.Sort();
    A.VyvodLeftRight();
    break;
case '0':
    break;
    default:
cout << endl << "Ошибка" << endl; 
break;}
}
while(otv!='0');
cin.get();
A.Ochistka();
 system("PAUSE");
0
55 / 56 / 34
Регистрация: 29.12.2012
Сообщений: 478
25.06.2015, 10:56 4
а у тебя какой список?
кольцевой

Добавлено через 6 минут
твой цыкла начинает с 1 элемента который сравнивает со 2 элементом и так далее НО у тебя последний элемент указывает на первый, а ты приказал цыклу пока ты ненайдеш какойто мифический NULL ходи и сравнивай вечность)))
0
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
25.06.2015, 10:57 5
Цитата Сообщение от Starkwr90 Посмотреть сообщение
Помогите пожалуйста разобраться с сортировкой кольцевого двухсвязного списка.
Вам с указателями или просто сортировка массива? Если сортировка массива, то сюда. С указателями, пока там ничего нет. Я пишу этот справочник по принципу, от простого к сложному. Надеюсь, почерпнёте инфы. Если не затруднит, оставьте комментарий. Принимаю любые, даже матерные .
0
55 / 56 / 34
Регистрация: 29.12.2012
Сообщений: 478
25.06.2015, 11:00 6
кстате подумайте про использувания косвеных указателей место (*р).sled попробывать писать p->sled так вроде яснее

Добавлено через 47 секунд
Starkwr90,
C++
1
2
3

 case '0':
  //  break;лишний брик,слово "Ошибка" никогда невыведится
    default:
0
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 10
25.06.2015, 11:01  [ТС] 7
А как сделать так, чтобы не зацикливало?
0
55 / 56 / 34
Регистрация: 29.12.2012
Сообщений: 478
25.06.2015, 11:36 8
надо в класе завести переменную len и функцию которая возрашает ее length()

Добавлено через 6 минут
ну там где ты просеш ввести кол-во элементов ее проинициализируй
C++
1

for( n = nsp,int i=0;i<length();i++,n = (*n).sled)
вот как то так я бы писал, конешно при удалении и вставки одного обьекта надо незабыть декременты и инкременты этой переменной...
0
25.06.2015, 11:36
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 25.06.2015, 11:36
Помогаю со студенческими работами здесь

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

Быстрая сортировка двусвязного списка
что не так?? void newsort(Offender_Node*first,Offender_Node*last) { ...

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

Шейкерная сортировка двусвязного списка
Здравствуйте! У меня возникла проблема с сортировкой двусвязного списка. Получилось...


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

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