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

Сортировка линейных(односвязных) списков - C++

Восстановить пароль Регистрация
 
NinGAZ
13 / 13 / 1
Регистрация: 27.07.2011
Сообщений: 162
24.03.2013, 23:04     Сортировка линейных(односвязных) списков #1
Всем доброго времени суток. Уже на протяжении нескольких дней бьюсь с сортировкой линейных списков. Вариант сортировки не важен, важно чтобы было сделано через смену узла указателя. Если кто может помочь,сказать куда копать,где прочитать,буду рад помощи.

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
struct list
{
    char* data;
    list* next;//указатель на следующий элемент
};
 
struct points
{
   list* first;
   list* last;
};
 
 
/*void sort(points *pnt) // эта сортировка не работает.. думаю из-за указателя prev
{
 
    list* prev=pnt->first;
    for(list* a=pnt->first;a!=NULL;a=a->next)
        for(list* b=pnt->first;b!=a;b=b->next)
        {
            list* tmp = b->next;
            if(wordCmp_list(b,tmp)==1)
            {
                b->next = tmp->next;
                prev->next = tmp;
                tmp->next = b;
                
            }
            if(tmp->next==a)
                prev = pnt->first;
            else
                prev = tmp;
        }
    pnt->last->next=NULL;
 
}*/
 
/*
 void sort(points *pnt)
{
    char* data;
 
    for(list* a=pnt->first;a!=NULL;a=a->next)
        for(list* b=pnt->first;b!=NULL;b=b->next)
        {
           if(wordCmp_list(a,b)==-1)
           {
              data = b->data;
              b->data = a->data;
              a->data = data;
           }
        }
    pnt->last->next=NULL;
 
}*/ - эта сортировка рабочая,но не тот метод работы. смена содержимого не катит :(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2013, 23:04     Сортировка линейных(односвязных) списков
Посмотрите здесь:

C++ Сортировка списков (Умножение полиномов)
«Хранение и обработка данных с использованием линейных списков». C++
Объединение (конкатенация) двух односвязных списков C++
Хранение и обработка данных с использованием линейных списков C++
Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 08:51     Сортировка линейных(односвязных) списков #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
struct node //list
{
    char* data;
    node* next;//указатель на следующий элемент
};
typedef node *Link;
 
struct points
{
    Link first;
    Link last;
};
 
void sort( Link &head )
// это реализация сортировки вставками insertion sort
{
    node tempHead;
 
    tempHead.next = 0;
    for ( Link t = head, u, p; t; t = u )
    {
        u = t->next;
        for ( p = &tempHead; p->next && p->next->data < t->data; p = p->next );
        t->next = p->next;
        p->next = t;
    }
    head = tempHead.next;
// здесь добавь код для иэменения указателя last, т.к. скорее всего он будет указывать не на последний узел в списке
}
И совет напоследок: правильно по смыслу называй структуры (твоя структура list на самом деле описывает только узел, cледовательно логичнее было бы назвать ее node)
anmartex
...
 Аватар для anmartex
1700 / 1193 / 494
Регистрация: 12.02.2013
Сообщений: 1,978
25.03.2013, 11:12     Сортировка линейных(односвязных) списков #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
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
struct TNode
{
    string data;
    TNode* next;
};
 
struct TList
{
   TNode* first;
   TNode* last;
};
 
//----------------------------------------------//
TList& Push(TList& list, const string& text)
{
   TNode* node = new TNode;
   node->data = text;
   node->next = NULL;
 
   if (list.last == NULL)
   {
      list.first = list.last = node;
   }
   else
   {
      list.last->next = node;
      list.last = node;
   }
 
   return list;
}
//----------------------------------------------//
string GetRandomWord(size_t length)
{
   static const string CAlphabet = "abcdefghijklmnopqrstuwvxyz";
   //static const string CAlphabet = "0123456789";
 
   string word;
 
   while (length--)
   {
      word += CAlphabet[rand() % CAlphabet.size()];
   }
 
   return word;
}
//----------------------------------------------//
ostream& operator << (ostream& os, const TList& list)
{
   TNode* node = list.first;
 
   os << "[";
   for (; node && (node != list.last->next); node = node->next)
   {
      os << node->data;
 
      if (node != list.last)
      {
         os << ", ";
      }
   }
   os << "]";
 
   return os;
}
//----------------------------------------------//
TList& Sort(TList& list)
{
   TList result = {list.first, list.first};
   list.first = list.first->next;
 
   while (list.first)
   {
      TNode* node = list.first;
      list.first = list.first->next;
 
      if (node->data < result.first->data)
      {
         node->next = result.first;
         result.first = node;
      }
      else
      {
         TNode* cursor = result.first;
         for (; cursor != result.last &&
                (cursor->next->data < node->data)
              ; cursor = cursor->next) { ; }
 
         node->next = cursor->next;
         cursor->next = node;
 
         if (cursor == result.last)
         {
            result.last = node;
         }
      }
   }
   result.last->next = NULL;
 
   list = result;
 
   return list;
}
//----------------------------------------------//
 
int main()
{
   srand(time(NULL));
 
   TList list = {NULL, NULL};
 
   for (size_t i = 0; i < 8; ++i)
   {
      Push(list, GetRandomWord(6));
   }
 
   cout << "source: " << list << endl;
   cout << "sorted: " << Sort(list) << endl;
 
   system("pause");
 
   return 0;
}
Сортировка линейных(односвязных) списков

Бинарник + исходник: program.7z
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 14:43     Сортировка линейных(односвязных) списков #4
Цитата Сообщение от anmartex Посмотреть сообщение
C++
1
list.first = list.first->next;
а что будет если сортируется пустой список?
anmartex
...
 Аватар для anmartex
1700 / 1193 / 494
Регистрация: 12.02.2013
Сообщений: 1,978
25.03.2013, 16:28     Сортировка линейных(односвязных) списков #5
Цитата Сообщение от ya_noob Посмотреть сообщение
а что будет если сортируется пустой список?
Согласен, занесло. А что мешает в начало вставить?:
C++
1
2
3
4
   if (list.first == NULL)
   {
      return list;
   }
NinGAZ
13 / 13 / 1
Регистрация: 27.07.2011
Сообщений: 162
27.03.2013, 01:34  [ТС]     Сортировка линейных(односвязных) списков #6
Всем спасибо. На что-то мне открыли глаза, чего-то я не понял, но все же сортировку сделал.

вот код, может кому понадобится:
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
void sort(points *pnt)
{
    if(elemCnt(pnt)==0)return;
 
    if(elemCnt(pnt)<3)
    {
        if(wordCmp_list(pnt->first,pnt->last)==1)
        {
            list* tmp = pnt->first;
            pnt->first = pnt->last;
            pnt->last = tmp;
        }
    }
    else
    {
        list* prev = pnt->first;
        list* cur = prev->next;
        list* next = cur->next;
        
        int i=0,cnt=0;
        while(i<elemCnt(pnt))
        {
          
           while(next!=NULL)
           {
               if(prev == pnt->first)
               {
                 //  cout << "first!" << endl;
                  // cnt++;
                if(wordCmp_list(pnt->first,cur)==1)
                 {
                    prev->next = next;
                    cur->next = prev;
                    pnt->first = cur;
                    list* tmp = prev;
                    prev = cur;
                    cur = tmp;
                   
                }
                 if(wordCmp_list(cur,next)==1)
                    {
                     if(pnt->first->next == cur)cnt++;
                        prev->next = cur->next;
                        cur->next = next->next;
                        next->next = cur;
                    }
              }
               else if(wordCmp_list(cur,next)==1 && next->next!=NULL)
            {
                   //if(pnt->first->next == cur)cnt++;
                prev->next = next;
                cur->next = next->next;
                next->next = cur;
            }
               else if(wordCmp_list(cur,next)==1 && next->next==NULL)
               {
                   prev->next = cur->next;
                   cur->next = NULL;
                   next->next = cur;
                   pnt->last = cur;
               }
            prev = cur;
            cur = next;
            next = next->next;
           // if(next==NULL)cout << "NULL - " << cur->data << endl;
           }
        prev = pnt->first;
        cur = prev->next;
        next = cur->next;        
        i++;
        }
        pnt->last->next = NULL;
    //    cout << cnt << endl;
    }
 
}
Yandex
Объявления
27.03.2013, 01:34     Сортировка линейных(односвязных) списков
Ответ Создать тему
Опции темы

Текущее время: 12:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru