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

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

Восстановить пароль Регистрация
 
Валентин^_^
10 / 10 / 2
Регистрация: 15.10.2009
Сообщений: 119
10.12.2011, 19:31     Сортировка линейного однонаправленного списка #1
Всем привет)
Нужно отсортировать линейный однонаправленный список. Как это можно сделать?
Причем нужно менять местами не данные, а указатели..

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

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++
C++ Создание однонаправленного списка
C++ Сортировка однонаправленного списка
C++ Формировка однонаправленного Списка
C++ Создание линейного однонаправленного списка
C++ Сортировка динамического линейного списка
C++ Сортировка линейного списка по полю year
Реализация однонаправленного списка C++

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

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

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