Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/43: Рейтинг темы: голосов - 43, средняя оценка - 4.72
Toshi2011
32 / 32 / 1
Регистрация: 13.01.2011
Сообщений: 193
1

Сортировка односвязного списка

28.06.2011, 03:37. Просмотров 8916. Ответов 4
Метки нет (Все метки)

Всем доброго времени суток!
Пишу курсавик по программированию, всё написал, осталась только одна функция уже голову всю сломал, никак не придумаю как же её реализовать , может вы чем сможите мне помочь, буду очень благодарен!
Нужно всего лишь отсортировать односвязный список:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct account
   {
     int visual;
     int number;
     char name[9];
     char surname[12];
     char nickname[9];
     char hometown[11];
     char residence[12];
     int birthday;
     int month;
     int year;
     char phone[12];
     struct account *nextPtr;
   }
Правда необходимо выполнить две сортировки:
1) По фамилии и имени(можно просто по фамилии) в алфавитном порядке.
2) По дате рождения.
Записей около 45...
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.06.2011, 03:37
Ответы с готовыми решениями:

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

Сортировка односвязного списка (пузырьком)
нужно отсортировать информацию о поездах по номеру поезда. Сортировку нужно сделать изменением...

Сортировка односвязного динамического списка
Добрый вечер! Есть список и функции работы с ним(переходы к элементам, их удаление, поиск...

Сортировка динамического односвязного списка
Здравствуйте. Буду признателен за помощь в написании функции сортировки односвязного списка. ...

Удаление узла из односвязного списка. + Сортировка
Уважаемые, форумчане! Помогите разобраться с работой функции void DeleteNodeByIndex(NODE *head,int...

4
xAtom
922 / 747 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
28.06.2011, 07:32 2
Вот написал, смотри сортировка по - алфавиту и по-дате от меньшего к большему, по-возрастанию.:cofee:
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
171
172
173
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <ctype.h>
 
#ifndef NULL
#define NULL  0
#endif
 
typedef const char*  cchar;
 
 
 struct account  {
   //   int visual;
   //   int number;
     char name[9];
     char surname[12];
  //   char nickname[9];
  //   char hometown[11];
  //   char residence[12];
     int  birthday;
     int  month;
     int  year;
     struct account *nextPtr;
 };
 
 // эту функцию - добавления в список данных  можешь удалить у тебя наверное свои есть
 void  add(struct account** plist, cchar iname, cchar surname, int day, int mon, int year) {
      if(! plist) {
          (*plist) = (struct account*) malloc(sizeof(struct account));
 
          strcpy((*plist)->name, iname);
          strcpy((*plist)->surname, surname);
          (*plist)->birthday = day;
          (*plist)->month    = mon;
          (*plist)->year     = year;
 
          (*plist)->nextPtr  = NULL;
      } else {
          struct account*  ptr = (struct account*) malloc(sizeof(struct account));
 
          strcpy(ptr->name, iname);
          strcpy(ptr->surname, surname);
          ptr->birthday = day;
          ptr->month    = mon;
          ptr->year     = year;
 
          ptr->nextPtr = *plist;
          *plist = ptr;
      }
 
 }
 
 
 
 long  timestamp(struct account* obj) {
        return (obj->month * 30) + (obj->year * 12 * 30) + obj->birthday;
 }
 
 
 typedef enum enum_sort{
    sort_family = 0, sort_date = 1
 };
 
 // сортировка по-фамилиям и по-дате
 void  sort_list(struct account*  plist, enum enum_sort type) {
        struct account*  first;
        struct account*  last;
        int    id, tmp;
        char   surname[12];
        char   name[9];
        while(1) {
               id = 0;
               first = plist;
               last  = plist->nextPtr;
               for( ; last != NULL ; last = last->nextPtr, first = first->nextPtr) {
 
                   if( (tolower(first->surname[0]) > tolower(last->surname[0]) && type == sort_family) ||
                        (timestamp(first) > timestamp(last) && type == sort_date) ) {
 
                          strcpy(surname, first->surname);
                          strcpy(first->surname, last->surname);
                          strcpy(last->surname, surname);
 
                          strcpy(name, first->name);
                          strcpy(first->name, last->name);
                          strcpy(last->name, name);
 
                          tmp               = first->birthday;
                          first->birthday = last->birthday;
                          last->birthday = tmp;
 
                          tmp          = first->month;
                          first->month = last->month;
                          last->month  = tmp;
 
                          tmp          = first->year;
                          first->year = last->year;
                          last->year  = tmp;
 
                          // по-такой аналогии отсортируй оставшиеся поля в структуре
 
                          id |= 1;
                   }
               }
               if(! id)
                   break;
 
        };
 }
 
 
 
 
int main(void)
{
     struct account* iter = NULL;
     struct account* list = NULL;
 
     // добавляем в список людей
     add(&list, "Sara", "Cobra", 1, 1, 2000);
     add(&list, "Bob", "Viking", 12, 2, 1999);
     add(&list, "Make", "Zero", 22, 1, 1991);
     add(&list, "Alex", "Zorro", 1, 2, 1990);
     add(&list, "Tom", "Alien", 1, 8, 1998);
     add(&list, "Jerry", "Based", 2, 7, 1989);
     add(&list, "Vasy", "Ultra", 3, 3, 1992);
     add(&list, "Warrior", "SWAT", 12, 4, 1993);
     add(&list, "Ninja", "Apache", 28, 11, 1994);
     add(&list, "Oscar", "York", 1, 1, 1982);
 
 
 
     // сортируем список по-фамилиям
     sort_list(list, sort_family);
 
 
     // выводим отсортированный список
     iter = list;
     while(iter != NULL) {
          printf("person: %s   %s\t date: %d.%d.%d\n", iter->name, iter->surname,
          iter->birthday, iter->month, iter->year);
         iter = iter->nextPtr;
     }
 
 
     // теперь сортируем по-дате
     sort_list(list, sort_date);
 
     puts("\n");
 
     // смотрим как отсортировалась по-дате
     iter = list;
     while(iter != NULL) {
          printf("person: %s   %s\t date: %d.%d.%d\n", iter->name, iter->surname,
          iter->birthday, iter->month, iter->year);
         iter = iter->nextPtr;
     }
 
 
 
     // чистим список
     while(list != NULL) {
          iter = list;
          list = list->nextPtr;
          free(iter);
          iter = NULL;
     }
     list = NULL;
 
   getchar();
   return 0;
}
2
Toshi2011
32 / 32 / 1
Регистрация: 13.01.2011
Сообщений: 193
28.06.2011, 14:37  [ТС] 3
Цитата Сообщение от xAtom Посмотреть сообщение
Вот написал, смотри сортировка по - алфавиту и по-дате от меньшего к большему, по-возрастанию.:cofee:
Спасибо оргомное!
Вы пошли немного другим путём. Я пытался работать с указателями, т.е. не копировать данные а поменять их местами. В результате, менять то она меняла, но при переходе к следующему элементу, они вставали обратно на свои места...
Ради спортивного интереса, если есть время, можите черкнуть как это будет выглядить, используя перестановку.
Ещё раз огромное спасибо!
0
xAtom
922 / 747 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
29.06.2011, 05:53 4
вот дополнение к твоему коду.
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
void swap(struct account** plist, int pos_a, int pos_b) {
 
        int  tmp;
        struct account* first = *plist;
        struct account* last  = *plist;
 
        while( pos_a-- )
            first = first->nextPtr;
 
        if(first == NULL)
            return;
 
        while( pos_b-- )
            last  = last->nextPtr;
 
        if(last == NULL)
            return;
 
        tmp           = first->visual;
        first->visual = last->visual;
        last->visual  = tmp;
 
        // здесь перестановку делай также как в сортировке
        // для каждого элемента структуры
        // дело в том что указатель это адрес а память физически выделяется для того чтобы
        // сменить данные под этот указатель нужно данные переместить в тот указатель с копировать
        // без манипуляции стека не обойтись
 
 }
 
 int  length(const struct account* plist) {
      int len = 0;
      for(; plist != NULL ;len++, plist = plist->nextPtr);
      return len;
 }
 
 
void  main(void) {
 
     size = length(list);  // получить размер списка
     // обменять последнее значение с серединным
     swap(&list, size - 1, size >> 1);
 
}
Добавлено через 17 минут
Небольшой пример на указатели.

char* A;
char* B;
char* T;

A = (char*) malloc(4);
B = (char*) malloc(4);
strcpy(A, "AAA");
strcpy(B, "BBB");


T = B; сохранить адрес указателя - B
B = A; адрес указателя B - затёрся адресом указателя - A

puts(T);
puts(B);

в указателе B - адрес остался, но по этому указателю в куче не будет данных после освобождения их, ниже освобождаем.

free(A);
A = NULL;

// free(B); при вызове удалить действия не даст так как адрес указывает
// на указатель - A данные были удалены

free(T); // вот теперь удалить данные по - указателю - B
T = NULL;

Все эти действия показывают как не делать утечки памяти.

Указатели не хранять сами данные, а только адрес для 32-разрядных он 4-байтный двойное слово(dword) Причина утечек памяти происходит из-за затирания(переименовывания) указателя и конечно из-за лени удалить память free/delete.
для безопасного использования создали const
const *int - говорит что адрес может меняться данные нет
int *const - вот так данные могут менятся а адрес нет, итерацией здесь уже не воспользуешься

GC - сборщик мусора в .NET, JAVA2 сохраняет адреса на кучу все указатели потом по-ним удаляет занимаемые данные в куче.

Ладно пойду спать.
2
Toshi2011
32 / 32 / 1
Регистрация: 13.01.2011
Сообщений: 193
29.06.2011, 22:21  [ТС] 5
Ясно, спосибо огромное! Всё понятно, со всем разобрался.
Хоть и запоздалое, но всё же: "спокойной ночи.".
0
29.06.2011, 22:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2011, 22:21

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

Реализация односвязного списка
Здравствуйте! Программа падает, судя по тестам, после команды list_clear, которая очищает все...

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


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

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

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