Сортировка двунаправленного списка

@TheKnyazz · Регистрация: 27.04.2009

Author24 — интернет-сервис помощи студентам

Посоветуйте пожалуйста адекватный метод сортировки двунаправленного списка.
Я сопсно вычитал на вики, что лучше всего сортировать путем разбиения списка на 2.
Т.е
"на входе имеются указатели на первые элементы объединяемых списков. Началом результирующего списка из них выбирается элемент с наименьшим ключом. Затем в качестве следующих элементов результирующего списка выбирается последующие элементы из первого или второго исходного списка, с меньшим значением ключа. Когда достигнут последний элемент одного из исходных списков, указатель последнего элемента результирующего списка устанавливается на остаток другого входного списка." И они советуют сортировать двунаправленный как однонаправленный, а потом восстанавливать все ссылки на задний элемент.
Имелся там так же пример на дельфи, который я перекроил под себя.
Сопсно вот

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
void halfToOne_Sort(myList* &FIRST,myList* &LAST,int key)
{  int i;
   myList *temp=FIRST;
 
   while (temp)
     {
         i++;
     }
   int g=i%2;
   int k=i/2-g;
   temp=FIRST;
   for (int j = 0; j < k; j++)
     {
       temp=temp->forward;
     }
   //myList *pList1,pList2;
   myList *pCurItem;
   myList *p1;
   myList *p2;
   p1=FIRST;
   p2=temp->forward;
   temp->forward->back=NULL;
   temp->forward=NULL;
   switch(key)
        {   //проверка по ключу
            case 1://по фамилии
            {
            if (strcmp(p1->data.Fio,p2->data.Fio)<0)
            {
              pCurItem = p1;
              p1 = p1->forward;
            }
            else
             {
              pCurItem = p2;
              p2 = p2->forward;
             }
            }
            break;
            case 2://по таб. номеру
            {if (p1->data.tabNum < p2->data.tabNum)
            {
              pCurItem = p1;
              p1 = p1->forward;
            }
            else
             {
              pCurItem = p2;
              p2 = p2->forward;
             }
             }
            break;
            case 3://по году рождения
            {if (p1->data.age < p2->data.age)
            {
              pCurItem = p1;
              p1 = p1->forward;
            }
            else
             {
              pCurItem = p2;
              p2 = p2->forward;
             }
             }
            break;
            case 4://по участку
            {if (p1->data.num_sector < p2->data.num_sector)
            {
              pCurItem = p1;
              p1 = p1->forward;
            }
                    else
             {
              pCurItem = p2;
              p2 = p2->forward;
             }
             }
            break;
        }
 
    while ((p1 != NULL) || (p2 != NULL))
    {
       switch(key)
        {   //проверка по ключу
            case 1://по фамилии
            {
            if (strcmp(p1->data.Fio,p2->data.Fio)<0)
 
               {
                pCurItem->forward = p1;
                pCurItem = p1;
                p1 = p1->forward;
               }
              else {
                pCurItem->forward = p2;
                pCurItem = p2;
                p2 = p2->forward;
               }
             }
 
            break;
            case 2://по таб. номеру
            {if (p1->data.tabNum < p2->data.tabNum)
 
               {
                pCurItem->forward = p1;
                pCurItem = p1;
                p1 = p1->forward;
               }
              else {
                pCurItem->forward = p2;
                pCurItem = p2;
                p2 = p2->forward;
               }
             }
 
            break;
            case 3://по году рождения
            {if (p1->data.age < p2->data.age)
 
               {
                pCurItem->forward = p1;
                pCurItem = p1;
                p1 = p1->forward;
               }
              else {
                pCurItem->forward = p2;
                pCurItem = p2;
                p2 = p2->forward;
               }
             }
 
            break;
            case 4://по участку
            {if (p1->data.num_sector < p2->data.num_sector)
 
               {
                pCurItem->forward = p1;
                pCurItem = p1;
                p1 = p1->forward;
               }
              else {
                pCurItem->forward = p2;
                pCurItem = p2;
                p2 = p2->forward;
               }
             }
 
            break;
        }
 
      }
 
    if (p1!=NULL){
      pCurItem->forward = p1;}
    else
      pCurItem->forward = p2;
   myList *p;
    p = FIRST;
  if (p != NULL)
  {  // Проверка, что список не является пустым
    p->back = NULL;
    while (p->forward != NULL)
    {
      p->forward->back= p;
      p= p->forward;
    }
  }
  LAST=p;
}

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

@Sekt · 13.11.2009, 21:10

F11 пробовали ?
Меня на взгляд смущяет

C++
1
2
3
4
5
temp=FIRST;
   for (int j = 0; j < k; j++)
         {
           temp=temp->forward;
         }

@TheKnyazz · 13.11.2009, 21:12 **[ТС]**

Это я таким способом делю свой список пополам)Прошу прощения что комментов нету. т.е нашел некоторое целое число g, которое равно половине количества всех элементов, и потом до него довожу свой указатель в списке, потом по этому указателю разбиваю список пополам.

@Sekt · 13.11.2009, 21:17

a F11 что говорит?
и почему в switcha х нет

C++
1
default?

@TheKnyazz · 13.11.2009, 21:42 **[ТС]**

F11 у меня говорит object inspector))) Я б с удовольствием повотчил, но никак не могу дупля дать, как заставить builder(RAD studio 2007) заглядывать в гости к процедурам и функциям. Т.е я могу trace'ить Только функцию main. Щас подправлю switch, но вроде бы default не совсем обязателен.

Добавлено через 19 минут
А может мне вообще сделать массив структур, сортировать его допустим быстрой сортировкой Хоара, а потом восстановить в двунаправленный список?

@TheKnyazz · 14.11.2009, 23:37 **[ТС]**

Собственно так и сделал, но может кто-нибудь пожалуйста порекомендовать более удобный способ сортировки двунаправленного списка?? и вообще замечательно было бы с примерчиком)Или хоть скажите, хороший сборник алгоритмов??

@TheKnyazz · 15.11.2009, 13:25 **[ТС]**

В общей сложности сделал еще и сортировку выбором.
Вот так сортируется двунаправленный список методом выбора.

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
int sort(myList* &top,myList* &endl,int key)
{//сортировка Выбором
myList* sort;    // элемент для того, чтобы запоминать отсортированные элементы
myList* big;    // переменная для хранения или самого большого элемента, или наоборот
myList* temp;   // временная переменная, ней мы пробегаем по циклам
temp = big = top;       // начальные значения
sort = NULL;
 while (big!=NULL)    // пока у нас есть не отсортированные элементы
 {
    big=temp;     // запоминаем наименший элемент как первый из неотсорт списка
    if(big!=NULL) //проверка последнего прохода
    {
    while (temp!=NULL)
    {
            switch(key)
        {   //проверка по ключу            //поиск минимального элемента
            case 1://по фамилии
            if (strcmp(temp->data.Fio,big->data.Fio)<0) big=temp;break;
            case 2://по таб. номеру
            if (temp->data.tabNum < big->data.tabNum) big=temp;break;
            case 3://по году рождения
            if (temp->data.age < big->data.age) big=temp;break;
            case 4://по участку
            if (temp->data.num_sector < big->data.num_sector) big=temp;break;
        }
      temp=temp->forward;//следующий элемент
    }
    if (big->back!=NULL)
       big->back->forward=big->forward;   // отчленение минимального из списка
    if (big->forward!=NULL)
       big->forward->back=big->back;
    if (sort!=NULL)
    {
        big->forward=sort->forward;    // так вставляем если уже есть
        sort->forward=big;           // сортированный список
        big->back=sort;
        if(big->forward!=NULL)     // для последнего элемента,
        {                          // чтобы не присваивать  пустоте значения
        big->forward->back=big;
        }
        sort=big;              //запомиманем конец отсортированного списка
    }
    else                       // если первый элемент отсортированного
      {
        if (big!=top) big->forward=top;
        big->back=NULL;
        big->forward->back=big;
        top=sort=big;       // запоминаем указатели на конец и
      }                     // начала нового сортированного списка
  temp=big->forward; // передвигаем указатель на начало не сорт списка
      }
 }
temp=top;
while(temp!=NULL)
   {
     endl=temp;
     temp=temp->forward;
   } //находим последний элемент
return 1;
}

Может быть кому-нибудь пригодится.

Новые блоги и статьи Все статьи Все блоги /
Winforstrap или красявый дизайн своими руками на HTML+JS+Winforms anomal6 04.03.2025 Сидел тут вечером ковырял проект на MAUI, и как же глупо создаются пакеты MSIX и система обновлений пакета публикации, но не об этом. Бывает нужен современный дизайн программы а писать на MAUI,. . .	Формат данных для симуляции физики, посредством распространённых не обученных моделей. Hrethgir 04.03.2025 Что-то как-то снова потерялось, зато катангенсы закатангесились в одном сообщении. На днях писал, что планирую для работы апгрейдить (на этот раз удачно) девайс для работы (конкретно - здоровья для,. . .	Концепция variadic CoderHuligan 04.03.2025 Мне не очень нравится (а кому это нравится?) что у нас есть отдельно компилятор, отдельно линковщик, причем со своим собственным командным языком. При этом усложнении надо знать помимо языка. . .	Java Record или Kotlin Data Class: что лучше для неизменяемых данных Wired 04.03.2025 Java Record и Kotlin Data Class — два мощных инструмента для обуздания неизменяемых структур данных, каждый со своим уникальным подходом к решению этой задачи. История их появления весьма. . .	Создание производительных API с Java и gRPC Wired 04.03.2025 В мире микросервисной разработки вопрос производительности часто становится краеугольным камнем. И хотя REST API давно завоевал сердца разработчиков своей простотой и интуитивностью, при высоких. . .
Что нового в JDK 24 Wired 04.03.2025 JDK 24 — это настоящий прорыв в эволюции Java, который кардинально меняет правила игры. В этом релизе разработчики Oracle наконец-то довели до ума множество критически важных улучшений в. . .	Разработка блокчейн с использованием Java: смарт-контракты и dApp Wired 04.03.2025 Погружаясь в мир блокчейн-разработки на Java, разработчик получает доступ к внушительному арсеналу инструментов. В отличие от Solidity, который "заперт" в экосистеме Ethereum, Java предоставляет. . .	WebAssembly в Kubernetes stackOverflow 03.03.2025 В современной экосистеме облачных технологий WebAssembly (Wasm) становится все более значимым компонентом, предлагая уникальный подход к выполнению кода в распределенных системах. Эта технология. . .	GitHub Actions или Jenkins: Выбираем CI/CD платформу stackOverflow 03.03.2025 Непрерывная интеграция и развертывание (CI/ CD) изменили подход к разработке программного обеспечения, превратив его в бесшовный процесс от написания кода до развертывания в продакшн. GitHub Actions и. . .	Автоматизация тестирования Pull Request в Kubernetes: Интеграция с GitHub Actions и GKE stackOverflow 03.03.2025 Масштабные проекты с использованием Kubernetes требуют надежной системы тестирования изменений перед их внедрением в продакшн-среду. Традиционный подход с ручной проверкой Pull Request не справляется. . .

@TheKnyazz 11 / 11 / 1 Регистрация: 27.04.2009 Сообщений: 30
	13.11.2009, 21:12 [ТС]	3
	Это я таким способом делю свой список пополам)Прошу прощения что комментов нету. т.е нашел некоторое целое число g, которое равно половине количества всех элементов, и потом до него довожу свой указатель в списке, потом по этому указателю разбиваю список пополам. 0

@TheKnyazz 11 / 11 / 1 Регистрация: 27.04.2009 Сообщений: 30
	13.11.2009, 21:42 [ТС]	5
	F11 у меня говорит object inspector))) Я б с удовольствием повотчил, но никак не могу дупля дать, как заставить builder(RAD studio 2007) заглядывать в гости к процедурам и функциям. Т.е я могу trace'ить Только функцию main. Щас подправлю switch, но вроде бы default не совсем обязателен. Добавлено через 19 минут А может мне вообще сделать массив структур, сортировать его допустим быстрой сортировкой Хоара, а потом восстановить в двунаправленный список? 0

@TheKnyazz 11 / 11 / 1 Регистрация: 27.04.2009 Сообщений: 30
	14.11.2009, 23:37 [ТС]	6
	Собственно так и сделал, но может кто-нибудь пожалуйста порекомендовать более удобный способ сортировки двунаправленного списка?? и вообще замечательно было бы с примерчиком)Или хоть скажите, хороший сборник алгоритмов?? 0

Сортировка двунаправленного списка

Решение