Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
1 / 2 / 0
Регистрация: 13.03.2022
Сообщений: 99

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

31.10.2022, 18:17. Показов 950. Ответов 5

Студворк — интернет-сервис помощи студентам
Здравствуйте, формучане. Хотел бы задать вопрос по поводу сортировки односвязного списка. У меня есть структура, в которой хранятся данные. Сейчас важен number - он отвечает за номер маршрута. Я реализовал добавление узла, куда передаётся и номер маршрута, и место старта и место финиша. Но тут возник вопрос: как можно реализовать функцию сортировки получившегося списка по номеру(к примеру назовём её sort()), если функция ничего не принимает. Также вопрос по поводу функции удаления: реализовал функцию del, но почему-то вылетает и не особо понимаю, как это можно исправить?
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
struct marsh
{
    string start;
    string finish;
    int number;
    marsh* next;
};
class List
{
private:
    marsh* head;
public:
    List()
    {
        head = NULL;
    }
    void addNode(string s, string f,int n)
    {
        marsh* nd = new marsh;
        nd->start= s;
        nd->finish = f;
        nd->number = n;
        nd->next = NULL;
        if (head == NULL) 
            head = nd;
        else
        {
            marsh* current = head;
            while (current->next != NULL)
                current = current->next;
            current->next = nd;
        }
    }
    /*void del(int n) //если удаления я понимаю, что есть ошибка и она вылетает, то как реализовать сортировку вообще не понятно
    {
        marsh* current = head;
        if (current->number == n) {
            current = current->next;
            free(current);
            return;
        }
        while (current != NULL)
        {
            if (n ==current->next->number)
            {
                current->next = current->next->next;
               
            }
            current = current->next;
        }
    }*/
};
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
31.10.2022, 18:17
Ответы с готовыми решениями:

Сортировка односвязного линейного списка по алфавиту
Всем здравствуйте! Имеется линейный список. Помогите, пожалуйста, написать сортировку студентов этого списка по фамилии. То есть, в...

Спроектировать шаблон класса spisok для реализации односвязного линейного списка. Не работает сортировка
Здравствуйте! Очень нужна помощь в реализации программы. Задание: Спроектировать шаблон класса spisok для реализации односвязного...

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

5
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
31.10.2022, 18:32
Цитата Сообщение от ivankn Посмотреть сообщение
как можно реализовать функцию сортировки получившегося списка по номеру(к примеру назовём её sort()), если функция ничего не принимает.
Не назовем.
Назовем ее sort_by_number()
Все, дело в шляпе.
Сортируем подходящим алгоритмом с последовательным доступом к элементам.

Пример примитивным пузырьком :
Список, классы
0
1 / 2 / 0
Регистрация: 13.03.2022
Сообщений: 99
31.10.2022, 19:25  [ТС]
Пузырёк я понимаю. Другая сложность в том, что список у меня не реализован, а реализацию необходимо делать самому и вопрос состоит в указателях и их правильного использования при сортировки и удалении
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
31.10.2022, 19:35
ivankn, А вы не удаляйте, а обменивайте указатели при сортировке ?
Вы никогда по указателях не сортировали ?

Добавлено через 1 минуту
Все тоже самое что у меня по ссылке, только вместо итераторов, указатель на указатель на узел.
Чуток подправить...

Добавлено через 4 минуты
Если еще не рабочий доделайте, напишите код заполнения (не вручную с клавиатуры).
И я напишу метод сортировки.
Или получите набросок.
0
1 / 2 / 0
Регистрация: 13.03.2022
Сообщений: 99
31.10.2022, 19:44  [ТС]
Да, сортировал я только массивы, а по указателям не сортировал ни разу. Было бы классно, если бы вы написали, как это можно сделать
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
31.10.2022, 20:22
Я тоже списки самописные еще не сортировал.

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
#include <iostream>
#include <list>
 
using namespace std;
struct Marsh{
    string start;
    string finish;
    int number;
};
struct Node
{
    Marsh data;
    Node* next;
};
class List
{
private:
    Node* head;
 
public:
    List()
    {
        head = NULL;
    }
    void addNode(string s, string f,int n)
    {
        Node* nd = new Node;
        nd->data.start= s;
        nd->data.finish = f;
        nd->data.number = n;
        nd->next = NULL;
        if (head == NULL) 
            head = nd;
        else
        {
            Node* current = head;
            while (current->next != NULL)
                current = current->next;
            current->next = nd;
        }
    }
    void print(){
        Node *h = head;
        while(h){
           cout << h->data.start << " - " << h->data.finish << " " << h->data.number << endl;
           h = h->next;
        }
    }
    
    void sort_by_number(){
        using It = Node**;
        It b = &head;
        Node* e = nullptr;
        It c = b;
        bool sort = false;
        while(!sort && *c!=e){
            sort = true;
            while( *(c = &((*c)->next)) != e){
                if ((*c)->data.number < (*b)->data.number){
                    swap((*c)->data, (*b)->data);
                    sort = false;
                }
            }
            b = &((*b)->next);
            c = b;
        }
    }
};
 
int main()
{
    List l;
    l.addNode("1", "2", 5);
    l.addNode("2", "3", 2);
    l.addNode("355", "1", 10);
    l.print();
    cout << endl;
 
    l.sort_by_number();
    cout << "After sort by number : " << endl;
    l.print();
    cout << endl;
}
Добавлено через 7 минут
Ну его, переписал на обычные указатели.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    void sort_by_number(){
        Node *b = head;
        Node *e = nullptr;
        Node *c = b;
        bool sort = false;
        while(!sort && c!=e){
            sort = true;
            while( (c = (c->next)) != e){
                if ( c->data.number < b->data.number){
                    swap( c->data, b->data);
                    sort = false;
                }
            }
            b = b->next;
            c = b;
        }
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
31.10.2022, 20:22
Помогаю со студенческими работами здесь

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

Проход по элементам односвязного линейного списка
Допустим у меня существует класс линейного односвязного списка. Надо пройти по его элементам и присвоить каждому соответствующее...

Найти наименьший элемент односвязного линейного списка
Найти наименьший элемент односвязного линейного списка. Сценарий: обходя список найти минимальное значение поля Data. Прошу помогите, ума...

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

Задать двумерный массив с помощью линейного односвязного списка
Помогите решить задачу: &quot;Задать двумерный массив с помощью линейного односвязного списка&quot;. Может кто знает, буду очень благодарен!


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&amp;d=1772460536 Одним из. . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru