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

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

31.10.2022, 18:17. Показов 909. Ответов 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
Заблокирован
31.10.2022, 18:32
Цитата Сообщение от ivankn Посмотреть сообщение
как можно реализовать функцию сортировки получившегося списка по номеру(к примеру назовём её sort()), если функция ничего не принимает.
Не назовем.
Назовем ее sort_by_number()
Все, дело в шляпе.
Сортируем подходящим алгоритмом с последовательным доступом к элементам.

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

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

Добавлено через 4 минуты
Если еще не рабочий доделайте, напишите код заполнения (не вручную с клавиатуры).
И я напишу метод сортировки.
Или получите набросок.
0
1 / 2 / 0
Регистрация: 13.03.2022
Сообщений: 99
31.10.2022, 19:44  [ТС]
Да, сортировал я только массивы, а по указателям не сортировал ни разу. Было бы классно, если бы вы написали, как это можно сделать
0
Заблокирован
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
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru