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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа построения графа Герца http://www.cyberforum.ru/cpp-beginners/thread63613.html
добрый вечер! вот есть такая задачка Ориентированный граф сильно связен, если для любой пары вершин u,v существует путь из u в v. Компонентой сильной связности назовем произвольный максимальный сильно связный подграф. Конденсацией ориентированного графа(или графом Герца, или фактор-графом) называется орграф,который получается стягиванием в одну вершину каждой компоненты сильной связности...
C++ Обработка строк на C, за коментарии +)) Задача. Написать программу, которая в исходном тексте определяет количество каждой из букв и все символы, которые не являются буквами заменить символом '@'. На экран вывести список букв с количеством их в тексте и измененный текст(обработка исходного текста, который состоит из 8-10 строк длиной 60-80 символов каждая и расположен во входном файле на диске. В программе необходимо предусмотреть... http://www.cyberforum.ru/cpp-beginners/thread63602.html
C++ Обработка одномерных масивов, обьясните новичку.
1) Найти максимальный элемент массива A. 2) Найти среднее арифметическое элементов массива В. A (25), B (30) Метод сортировки массива А : перестановкой. Заранее спасибо.
C++ Обработка одномерных масивов.
1) Найти максимальный элемент массива A. 2) Найти среднее арифметическое элементов массива В. A (25), B (30) Метод сортировки массива А : перестановкой. Заранее спасибо.
C++ Вопросы http://www.cyberforum.ru/cpp-beginners/thread63590.html
Ребята, никто не писал никогда код на С++, связанный с имитационным моделированием? Просто, дали, там набор математич. формул и теория, а реального воплощения на С++ не находил.
C++ Посчитать сумму чисел. Нужно закончить программу. Доброго времени суток. Задача - посчитать сумму по такой формуле: (1+0.1)(2+0.2)...(N+N/10) #include <stdio.h> #include <math.h> #include <iomanip> #include <iostream> using namespace std; подробнее

Показать сообщение отдельно
TheKnyazz
10 / 10 / 1
Регистрация: 27.04.2009
Сообщений: 30
13.11.2009, 21:00     Сортировка двунаправленного списка
Посоветуйте пожалуйста адекватный метод сортировки двунаправленного списка.
Я сопсно вычитал на вики, что лучше всего сортировать путем разбиения списка на 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;
}
Но где-то закрался злобный ошипка вызывающий зацикливание.
Помогите пожалуйста вычислить ошибку, и был бы очень рад совету по поводу других хороших способов отсортировать двунаправленный список.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru