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

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

Войти
Регистрация
Восстановить пароль
 
Валентин^_^
10 / 10 / 2
Регистрация: 15.10.2009
Сообщений: 119
#1

Сортировка линейного однонаправленного списка - C++

10.12.2011, 19:31. Просмотров 584. Ответов 0
Метки нет (Все метки)

Всем привет)
Нужно отсортировать линейный однонаправленный список. Как это можно сделать?
Причем нужно менять местами не данные, а указатели..

Вот код программы, список структур. Помогите плиз с сортировкой

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
#include "stdafx.h"
#include <clocale>
#include <iostream>
 
using namespace std;
 
struct Train
{
    char *Destination;
    int TrainNumber;
    char *Time;
    Train *next;
};
 
void init_train(Train &train);
void deinit_train(Train &train);
bool add_train(Train *&head, Train src);
void sort_train(Train *head, int n);
Train *search_train(Train *head, int TrainNumber);
 
int main()
{
    setlocale(LC_ALL, "russian");
 
    const int n = 3;
 
    Train *head = NULL;
 
    Train buf;
 
    for(int i = 0; i < n; i++)
    {
        init_train(buf);
 
        cout << "Пункт назначения: ";
        cin >> buf.Destination;
        cout << "Номер поезда: ";
        cin >> buf.TrainNumber;
        cout << "Время отправления: ";
        cin >> buf.Time;
 
        if(!add_train(head, buf))
            return 0;
    }
 
    sort_train(head, n);
 
    Train *srch = head;
    for(int i = 0; i < n; i++)
    {
        cout << srch->Destination << " #" << srch->TrainNumber << ": " << srch->Time << endl;
        srch = srch->next;
    }
 
    /*int train_number;
    cout << "Введите номер поезда для поиска: ";
    cin >> train_number;
    Train *srch = search_train(head, train_number);
    if(srch != NULL) cout << srch->Destination << " #" << srch->TrainNumber << ": " << srch->Time << endl << endl;
    delete [] srch;*/
 
    delete [] head;
    deinit_train(buf);
 
    system("pause");
    return 0;
}
 
void init_train(Train &train)
{
    train.Destination = new char[150];
    train.TrainNumber = -1;
    train.Time = new char[20];
    train.next = NULL;
}
 
void deinit_train(Train &train)
{
    delete [] train.Destination;
    train.Destination = NULL;
    delete [] train.Time;
    train.Time = NULL;
}
 
bool add_train(Train *&head, Train src)
{
    if(head == NULL)
    {
        head = new Train;
        head->Destination = src.Destination;
        head->TrainNumber = src.TrainNumber;
        head->Time = src.Time;
        head->next = NULL;
        return true;
    }
    else
    {
        Train *p = head;
        while(p->next != NULL)
            p = p->next;
        p->next = new Train;
        *(p->next) = src;
        p->next->next = NULL;
        return true;
    }
    return false;
}
 
void sort_train(Train *head, int n)
{
    Train *buf;
    
    bool change;
    do
    {
        Train *p = head;
        change = false;
        for(p = head; p->next != NULL && p->next->next != NULL; p = p->next)
        {
            if(p->TrainNumber > p->next->TrainNumber)
            {
                /*if(head != NULL)
                {
                    buf = p->next;
                    p->next = buf->next;
                    buf->next = head;
                    head = buf;
                }
                else
                {
                    
                }*/
                change = true;
            }
        }
    }
    while(change);
}
 
Train *search_train(Train *head, int TrainNumber)
{
    if(head == NULL) return NULL;
    Train *p = head;
    while(p != NULL && p->TrainNumber != TrainNumber)
        p = p->next;
    return p;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2011, 19:31     Сортировка линейного однонаправленного списка
Посмотрите здесь:

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

Как из линейного однонаправленного списка сделать кольцевой однонаправленный? - C++
как из линейного однонаправленного списка сделать кольцевой однонаправленный. программа имеет функции добавить/удалить звено, вывод на...

Сортировка однонаправленного списка - C++
Доброго времени суток, уважаемые форумчане! Возникла проблема с сортировкой однонаправленного списка методом &quot;пузырька&quot;. Что делать-не...

структуры данных. сортировка однонаправленного списка - C++
значит так, есть вот эта программа: #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; struct spisok { int info; ...

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

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

Сортировка линейного списка по полю year - C++
Господа подскажите как осуществить сортировку списка по полю year? При этом неважно по убыванию или возрастанию, метод сортировки тоже...

Сортировка линейного списка слиянием сверху вниз - C++
«Функция merge должна сливать список, на который указывает a, со списком, на который указывает b, с помощью вспомогательного указателя с....

Реализация однонаправленного списка - C++
не знаю в чём проблема нужно было: Разработать класс для работы с динамической структурой «Однонаправленный список», содержащей...

Создание однонаправленного списка - C++
Запишите все необходимые объявления (типов и переменных) для создания в программе на языке C++ однонаправленного списка людей...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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