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

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

Войти
Регистрация
Восстановить пароль
 
NinGAZ
14 / 14 / 1
Регистрация: 27.07.2011
Сообщений: 162
#1

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

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

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

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

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

Сравнение элементов двух однонаправленных линейных списков - C++
А как сравнить элементы двух списков? Чтобы при совпадении элементов счётчик прибавлял единичку? Если список вот так задан: #include...

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

Хранение и обработка данных с использованием линейных списков - C++
Люди, помогите пожалуйста!!! Дали задание к курсовой работе. Сделать надо любое из двух (какое легче) но сделать не могу ни 1, ни 2 ...

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

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

Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков - C++
Здравствуйте! Собственно, вопрос находится в заголовке: у меня описано два списка, надо этим алгоритмом найти количество вхождений первого...

Сортировка списков - C++
Как можно из двух списков, допустим с фамилиями, вывести на экран так, чтобы первые были фамилии, начинающиеся на букву А?

Сортировка посредством слияния списков - C++
Помогите пожалуйста написать алгоритм сортировки посредством слияния списков

Сортировка списков (Умножение полиномов) - C++
Задача: Имеются 2 полинома (А и В). Они задаются, как массив коэффициентов при иксах. Нужно создать третий полином (С = А * В) и...

Сравнение множеств (реализованых на односвязных списках) - C++
Требуется найти алгоритм, который без труда сможет сравнивать множества, содержащие большое количество элементов(~100000 элементов...:) )....


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

Или воспользуйтесь поиском по форуму:
NinGAZ
14 / 14 / 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     Сортировка линейных(односвязных) списков
Ответ Создать тему
Опции темы

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