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

@Toshi2011 · Регистрация: 13.01.2011

Author24 — интернет-сервис помощи студентам

Всем доброго времени суток!
Пишу курсавик по программированию, всё написал, осталась только одна функция уже голову всю сломал, никак не придумаю как же её реализовать

, может вы чем сможите мне помочь

, буду очень благодарен!

Нужно всего лишь отсортировать односвязный список:

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...

@xAtom · 28.06.2011, 07:32

Вот написал, смотри сортировка по - алфавиту и по-дате от меньшего к большему, по-возрастанию.: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;
}

@Toshi2011 · 28.06.2011, 14:37 **[ТС]**

Сообщение от xAtom

Вот написал, смотри сортировка по - алфавиту и по-дате от меньшего к большему, по-возрастанию.:cofee:

Спасибо оргомное!

Вы пошли немного другим путём. Я пытался работать с указателями, т.е. не копировать данные а поменять их местами. В результате, менять то она меняла, но при переходе к следующему элементу, они вставали обратно на свои места...

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

Ещё раз огромное спасибо!

@xAtom · 29.06.2011, 05:53

вот дополнение к твоему коду.

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 сохраняет адреса на кучу все указатели потом по-ним удаляет занимаемые данные в куче.

Ладно пойду спать.

@Toshi2011 · 29.06.2011, 22:21 **[ТС]**

Ясно, спосибо огромное! Всё понятно, со всем разобрался.

Хоть и запоздалое, но всё же: "спокойной ночи.".

Новые блоги и статьи Все статьи Все блоги /
Обнаружение объектов в реальном времени на Python с YOLO и OpenCV AI_Generated 29.04.2025 Компьютерное зрение — одна из самых динамично развивающихся областей искусственного интеллекта. В нашем мире, где визуальная информация стала доминирующим способом коммуникации, способность машин. . .	Эффективные парсеры и токенизаторы строк на C# UnmanagedCoder 29.04.2025 Обработка текстовых данных — частая задача в программировании, с которой сталкивается почти каждый разработчик. Парсеры и токенизаторы составляют основу множества современных приложений: от. . .	C++ в XXI веке - Эволюция языка и взгляд Бьярне Страуструпа bytestream 29.04.2025 C++ существует уже более 45 лет с момента его первоначальной концепции. Как и было задумано, он эволюционировал, отвечая на новые вызовы, но многие разработчики продолжают использовать C++ так, будто. . .	Слабые указатели в Go: управление памятью и предотвращение утечек ресурсов golander 29.04.2025 Управление памятью — один из краеугольных камней разработки высоконагруженных приложений. Го (Go) занимает уникальную нишу в этом вопросе, предоставляя разработчикам автоматическое управление памятью. . .	Разработка кастомных расширений для компилятора C++ NullReferenced 29.04.2025 Создание кастомных расширений для компиляторов C++ — инструмент оптимизации кода, внедрения новых языковых функций и автоматизации задач. Многие разработчики недооценивают гибкость современных. . .
Гайд по обработке исключений в C# stackOverflow 29.04.2025 Разработка надёжного программного обеспечения невозможна без грамотной обработки исключительных ситуаций. Любая программа, независимо от её размера и сложности, может столкнуться с непредвиденными. . .	Создаем RESTful API с Laravel Jason-Webb 28.04.2025 REST (Representational State Transfer) — это архитектурный стиль, который определяет набор принципов для создания веб-сервисов. Этот подход к построению API стал стандартом де-факто в современной. . .	Дженерики в C# - продвинутые техники stackOverflow 28.04.2025 История дженериков началась с простой идеи — создать механизм для разработки типобезопасного кода без потери производительности. До их появления программисты использовали неуклюжие преобразования. . .	Тестирование в Python: PyTest, Mock и лучшие практики TDD py-thonny 28.04.2025 Тестирование кода играет весомую роль в жизненном цикле разработки программного обеспечения. Для разработчиков Python существует богатый выбор инструментов, позволяющих создавать надёжные и. . .	Работа с PDF в Java с iText Javaican 28.04.2025 Среди всех форматов PDF (Portable Document Format) заслуженно занимает особое место. Этот формат, созданный компанией Adobe, превратился в универсальный стандарт для обмена документами, не зависящий. . .

@Toshi2011 33 / 33 / 1 Регистрация: 13.01.2011 Сообщений: 193
	29.06.2011, 22:21 [ТС]
	Ясно, спосибо огромное! Всё понятно, со всем разобрался. Хоть и запоздалое, но всё же: "спокойной ночи.". 0

Опции темы