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

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

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

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

10.12.2011, 19:31. Просмотров 587. Ответов 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++
Добрый вечер!Написала программу создания линейного списка и вывод его на экран с клавиатуры и из файла.Вроде бы всё верно и программа даже...

Как из линейного однонаправленного списка сделать кольцевой однонаправленный? - 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 а не перенаправлять указатели, но программа не работает правильно не могли бы вы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2011, 19:31
Привет! Вот еще темы с ответами:

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

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

Сортировка двунаправленного линейного списка по алгоритму Хоара - C++
ПОМОГИТЕ СРОЧНО!!!! нужно отсортировать двунаправленный линейный список по алгоритму Хоара менять местами можно только указатели!! код...

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


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

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

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