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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
20.09.2011, 14:18     Сортировка вставками в односвязном списке #1
Собственно нужно реализовать такую сортировку, но что-то не могу я придумать как её реализовать именно в односвязном списке, у нас ведь доступ не прямой как у массива здесь ... есть варианты?
Собственно код моего односвязного списка (большим количеством места отделены функции которые вряд-ли понадобятся для сортировки, я их просто оставил для целостности, main в коде тоже оставлен с той же целью):
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
#include <iostream>
using std::cout;
using std::endl;
#include <string>
using std::string;
 
class List
{
    struct element
    {
        element(string s, element *next=NULL)
        {
            data=s;
            Next=next;
        }
        string data;
        element *Next;
    };
 
    element *Head;
    element *Tail;
 
public:
    List(string str)
    {
        Head=new element(str,0);// второй аргумент - адрес для сл.элемента
        Tail=Head;
    }
 
    void addToTail(string str)
    {
        element *temp=new element(str,0);
        if (Tail)
        {
         Tail->Next=temp;
         Tail = temp;
        }
        else
         Head=Tail=temp;
    }
 
    void addToHead(string str)
    {
        element *temp=new element (str,0);
        if(Head)
        {
            temp->Next=Head;
            Head = temp;
        }
        else
         Head=Tail=temp;
    }
 
    void print()
    {
        element *temp=Head;
        while(temp)
        {
            cout<<temp->data<<' ';
            temp=temp->Next;
        }
        cout<<endl;
    }
 
    void sort()
    {
        bool flag=true;
    }
 
 
 
 
 
 
 
 
 
 
    void reverse()
    {
        if(!Head)
         return;
 
        element *temp=Head;
        element *newHead;
        element *newTail;
        element *prev;
        element *add;
        if (temp)
        {
            add=new element(temp->data,0);
            newTail=add;
            prev=add;
        }
        temp=temp->Next;
        while(temp)
        {
            add=new element(temp->data,prev);
            newHead=add;
            prev=add;
            temp=temp->Next;
        }
        free();
        Head=newHead;
        Tail=newTail;
    }
 
    void free()
    {
        this->~List();
    }
 
 
    ~List()
    {
        element *temp;
        while(Head)
        {
            temp=Head;
            Head=Head->Next;
            delete temp;
        }
        Head=Tail=temp=NULL;
    }
};
 
int main()
{
    List test("simple");
    test.addToTail("text");
    test.addToTail("is");
    test.addToTail("so");
    test.addToTail("simple");
    test.print();
//    cout<<"After reverse():\n";
//    test.reverse();
//    test.print();
//    test.addToTail("text");
//    test.print();
}
Мне также подойдёт пример и с Вашим односвязным списком (если Вы например делали свой односвязный список с сортировкой вставками и у Вас остался код).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Almaz1988
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 12
06.12.2013, 16:04     Сортировка вставками в односвязном списке #21
Цитата Сообщение от Gepar Посмотреть сообщение
Есть же книга Седжвика "Алгоритмы на с++", притом книг этой серии больше чем в серии алгоритмов на java. Нет конечно же, затраты на создание массива, копирование в него значений и копирование значений назад (по памяти и времени) будут всегда в разы дороже.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А сортировка слияниями для списков должна быть абсолютно незатратна по памяси, в отличие от массивов
Почему же тогда в книге эти алгоритмы сортировки для связных списков даже не приводятся? Все алгоритмы разбираются только на массивах.

Вот и в книге "Фундаментальные алгоритмы С++" того же Седжвика открываю главу 6, посвященную сортировке. Сортировке связных списков посвящен предпоследний пункт из 4-ех страниц и читаю:
Все программные реализации сортировок, рассмот-
рассмотренные к этому моменту, предполагают, что сортируемые данные представлены в
виде массивов.
Т.е. я еще больше убеждаюсь, что связный список не приспособлен к сортировке.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.12.2013, 16:17     Сортировка вставками в односвязном списке #22
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. я еще больше убеждаюсь, что связный список не приспособлен к сортировке.
а сортировки матриц, сортировки деревьев, сортировки ... там тоже нету, значит "не нужны".
Логика... мда
Almaz1988
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 12
06.12.2013, 16:51     Сортировка вставками в односвязном списке #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а сортировки матриц, сортировки деревьев, сортировки ... там тоже нету, значит "не нужны".
Логика... мда
Насколько я понимаю дело все-таки в быстродействии. У Седжвика далее в книге:
Три классические структуры данных, способные поддерживать эффективные алгоритмы поиска - бинарные деревья поиска, красно-черные деревья и хеш-таблицы.
Т.е. каждая структура данных заточена под конкретный тип операций.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,508
06.12.2013, 21:18  [ТС]     Сортировка вставками в односвязном списке #24
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. каждая структура данных заточена под конкретный тип операций.
Предлагаю тебе таки дочитать книгу до конца, а потом делать выводы
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2013, 21:44     Сортировка вставками в односвязном списке
Еще ссылки по теме:

Нужно продублировать первое чётное число в односвязном списке C++
C++ Добавление узла перед заданным в односвязном списке
Ошибка в односвязном списке C++

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

Или воспользуйтесь поиском по форуму:
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
06.12.2013, 21:44     Сортировка вставками в односвязном списке #25
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. каждая структура данных заточена под конкретный тип операций.
И? В связном списке вставка в произвольное место (+ возможно splice) за константу.
Yandex
Объявления
06.12.2013, 21:44     Сортировка вставками в односвязном списке
Ответ Создать тему
Опции темы

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