Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
NinGAZ
14 / 14 / 4
Регистрация: 27.07.2011
Сообщений: 162
1

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

24.03.2013, 23:04. Просмотров 1020. Ответов 5
Метки нет (Все метки)

Всем доброго времени суток. Уже на протяжении нескольких дней бьюсь с сортировкой линейных списков. Вариант сортировки не важен, важно чтобы было сделано через смену узла указателя. Если кто может помочь,сказать куда копать,где прочитать,буду рад помощи.

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;
 
}*/ - эта сортировка рабочая,но не тот метод работы. смена содержимого не катит :(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2013, 23:04
Ответы с готовыми решениями:

пересечение и разность односвязных списков
Помогите, пожалуйста. нужно написать подпрограммы для пересечения и получения...

Объединение (конкатенация) двух односвязных списков
Задача: Построить стек (односвязный список). Показать реализацию стека на...

Сравнить элементы линейных списков
написать процедуру, которая по 2-м линейным спискам L1 и L2 формирует новый...

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

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

5
ya_noob
_
315 / 149 / 27
Регистрация: 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)
1
anmartex
...
1711 / 1204 / 909
Регистрация: 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
1
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
25.03.2013, 14:43 4
Цитата Сообщение от anmartex Посмотреть сообщение
C++
1
list.first = list.first->next;
а что будет если сортируется пустой список?
0
anmartex
...
1711 / 1204 / 909
Регистрация: 12.02.2013
Сообщений: 1,978
25.03.2013, 16:28 5
Цитата Сообщение от ya_noob Посмотреть сообщение
а что будет если сортируется пустой список?
Согласен, занесло. А что мешает в начало вставить?:
C++
1
2
3
4
   if (list.first == NULL)
   {
      return list;
   }
0
NinGAZ
14 / 14 / 4
Регистрация: 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;
    }
 
}
0
27.03.2013, 01:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2013, 01:34

Сравнение элементов двух однонаправленных линейных списков
А как сравнить элементы двух списков? Чтобы при совпадении элементов счётчик...

«Хранение и обработка данных с использованием линейных списков».
Вот мне к курсовой работе дали задание.Я не могу его понять, что от меня...

Организовать представление множеств в виде линейных однонаправленных списков
Даны два множества А и В. Организовать представление множеств в виде линейных...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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