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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.74
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
#1

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

13.11.2009, 21:00. Просмотров 4132. Ответов 6
Метки нет (Все метки)

Посоветуйте пожалуйста адекватный метод сортировки двунаправленного списка.
Я сопсно вычитал на вики, что лучше всего сортировать путем разбиения списка на 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;
}
Но где-то закрался злобный ошипка вызывающий зацикливание.
Помогите пожалуйста вычислить ошибку, и был бы очень рад совету по поводу других хороших способов отсортировать двунаправленный список.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2009, 21:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка двунаправленного списка (C++):

Сортировка двунаправленного списка - C++
Помогите отсортировать составленный список по определенному полю, я пробовал методом пузырька, но не получается, просьба подсказать: ...

Сортировка двунаправленного линейного списка по алгоритму Хоара - C++
ПОМОГИТЕ СРОЧНО!!!! нужно отсортировать двунаправленный линейный список по алгоритму Хоара менять местами можно только указатели!! код...

Получить указатель на элемент двунаправленного списка, добавить значение в начало списка и очистить его - C++
Нужно создать двунаправленный список //вроде так, но не уверен struct Double_List {//структура данных int Data;...

Удаление из двунаправленного списка - C++
Программа компилируется, добавляет элементы в список, но когда доходит до удаления вылетает. #include &lt;iostream&gt; #include &lt;cstring&gt; ...

Реализация Двунаправленного списка - C++
Ребят, что он хочет от меня, ошибка компиляции, понять не могу в чем проблема, у меня еще просто компилятор не пишет причину ошибки а...

Шаблон двунаправленного списка - C++
Добрый день! Пишу программу &quot;библиотека&quot;, которая включает в себя типы данных Книга и Читатель соответственно: const int...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
13.11.2009, 21:10 #2
F11 пробовали ?
Меня на взгляд смущяет
C++
1
2
3
4
5
temp=FIRST;
   for (int j = 0; j < k; j++)
         {
           temp=temp->forward;
         }
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
13.11.2009, 21:12  [ТС] #3
Это я таким способом делю свой список пополам)Прошу прощения что комментов нету. т.е нашел некоторое целое число g, которое равно половине количества всех элементов, и потом до него довожу свой указатель в списке, потом по этому указателю разбиваю список пополам.
Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
13.11.2009, 21:17 #4
a F11 что говорит?
и почему в switcha х нет
C++
1
default?
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
13.11.2009, 21:42  [ТС] #5
F11 у меня говорит object inspector))) Я б с удовольствием повотчил, но никак не могу дупля дать, как заставить builder(RAD studio 2007) заглядывать в гости к процедурам и функциям. Т.е я могу trace'ить Только функцию main. Щас подправлю switch, но вроде бы default не совсем обязателен.

Добавлено через 19 минут
А может мне вообще сделать массив структур, сортировать его допустим быстрой сортировкой Хоара, а потом восстановить в двунаправленный список?
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
14.11.2009, 23:37  [ТС] #6
Собственно так и сделал, но может кто-нибудь пожалуйста порекомендовать более удобный способ сортировки двунаправленного списка?? и вообще замечательно было бы с примерчиком)Или хоть скажите, хороший сборник алгоритмов??
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
15.11.2009, 13:25  [ТС] #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
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;
}
Может быть кому-нибудь пригодится.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2009, 13:25
Привет! Вот еще темы с ответами:

Swap для двунаправленного списка - C++
Поменять просто значения узлов, не интересно. Я запутываюсь с ссылками. элементы могут быть заглавными или последними. struct node ...

Реализовать стек на массиве с использованием двунаправленного списка - C++
здраствуйте, может кто-то пожалуйста привести реализацию примера стека, реализованого на массиве с использиванием...

Нахождение и изменение элемента двунаправленного кольцевого списка - C++
помогите дополнить код,что бы можно было найти элемент введенный с клавиатуры и заменить его другим элементом( тоже введенным с...

Вложенные структуры. Ошибка с создании вложенного двунаправленного списка - C++
Доброго времени суток. Хочу представить граф в виде списка смежности, но у меня компилятор выдает кучу ошибок, помогите разобраться...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.11.2009, 13:25
Ответ Создать тему
Опции темы

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