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

Сортировка связного списка - C++

Восстановить пароль Регистрация
 
septe-mber
0 / 0 / 0
Регистрация: 02.01.2013
Сообщений: 123
06.02.2013, 00:54     Сортировка связного списка #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
#include <iostream>
 
using namespace std;
 
struct Node
{
    int data;
    Node* next;
};
 
void push(Node*& head, Node*& tail, int value)
{
    Node* newptr = new Node;
    newptr->next = newptr;
    newptr->data = value;
 
    if(head == NULL)
        head = tail = newptr;
    else
    {
        tail->next = newptr;
        tail = newptr;
    }
}
 
void insert(Node*& head, int index, int value)
{
    Node* cur = head;
 
    Node* newptr = new Node;
    newptr->data = value;
 
    if(index == 1)
    {
        newptr->next = head;
        head = newptr;
    }
    else
    {
        for(int i = 1; i < index - 1; i++)
            cur = cur->next;
 
        newptr->next = cur->next;
        cur->next = newptr;
    }
}
 
void show(Node* head, int count)
{
    Node* cur = head;
    if(count != 0)
    {
        cout<<cur->data<<'\t';
        show(cur->next, count - 1);
    }
}
 
void remove(Node*& head, int index)
{
    Node* cur = head;
 
    if(index == 1)
    {
        head = cur->next;
        delete cur;
        cur = NULL;
    }
    else
    {
        for(int i = 1; i < index; i++)
            cur = cur->next;
 
        Node* prev = head;
        while(prev->next != cur)
            prev = prev->next;
        prev->next = cur->next;
 
        delete cur;
        cur = NULL;
    }
}
 
void fun_sort(Node* head, int n)
{
    Node* cur = head;
    while(n != 0)
    {
        if(cur->data > cur->next->data)
            swap(cur->data, cur->next->data);
        cur = cur->next;
        n--;
    }
}
 
int main()
{
    Node* head, *tail;
    head = NULL; tail = NULL;
 
    for(int i = 5; i >= 1; i--)
        push(head, tail, i);
 
    show(head, 5); cout<<endl<<endl;
 
    fun_sort(head, 5);
    show(head, 5);
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2013, 00:54     Сортировка связного списка
Посмотрите здесь:

C++ Реализация связного списка
Ошибка в Классе связного списка C++
обращение к члену связного списка C++
Создание и сортировка связного списка C++
сортировка пузырьком связного списка C++
C++ сортировка связного списка
C++ Реализация связного списка
Удаление элементов из связного списка C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dekio
Фрилансер
Эксперт C++
 Аватар для Dekio
5816 / 1214 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
06.02.2013, 01:20     Сортировка связного списка #2
Сортировка через значения и с помощью указателей
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
#include <iostream>
#include <random>
 
struct Node
{
    int value;
    Node *next;
};
 
void insertItem(Node *posItem, int value)
{
    Node *item = new Node;
    item->value = value;
    item->next = posItem->next;
    posItem->next = item;
}
 
void deleteNode(Node *startItem)
{
    Node *item = startItem->next;
    while (item != startItem) {
        startItem->next = item->next;
        delete item;
        item = startItem->next;
    }
    delete startItem;
}
 
void sortByValues(Node *startItem)
{
    for (Node *i = startItem->next; i->next != startItem; i = i->next)
        for (Node *j = startItem->next; j->next != startItem; j = j->next)
            if (j->value > j->next->value) {
                int buf = j->value;
                j->value = j->next->value;
                j->next->value = buf;
            }
}
 
void sortByLinks(Node *startItem)
{
    for (Node *i = startItem->next; i != startItem; i = i->next)
        for (Node *j = startItem; j->next->next != startItem; j = j->next)
            if (j->next->value > j->next->next->value) {
                Node *buf = j->next;
                j->next = j->next->next;
                i = j->next;
                buf->next = j->next->next;
                j->next->next = buf;
            }
}
 
void printNode(Node *startItem)
{
    for (Node *i = startItem->next; i != startItem; i = i->next)
        std::cout << i->value << std::endl;
}
 
int main()
{
    Node *startItem = new Node,
         *currItem = startItem;
    startItem->next = startItem;
    std::random_device rand;
    std::mt19937 gen(rand());
    std::uniform_int_distribution <> distr(-10, 30);
    for (int i = 0; i < 10; i++) {
        insertItem(currItem, distr(gen));
        currItem = currItem->next;
    }
    std::cout << "Before:" << std::endl;
    printNode(startItem);
    sortByLinks(startItem);
    std::cout << "After:" << std::endl;
    printNode(startItem);
    deleteNode(startItem);
    return 0;
}
Yandex
Объявления
06.02.2013, 01:20     Сортировка связного списка
Ответ Создать тему
Опции темы

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