Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.69/35: Рейтинг темы: голосов - 35, средняя оценка - 4.69
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
1

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

20.09.2011, 14:18. Просмотров 6457. Ответов 24
Метки нет (Все метки)

Собственно нужно реализовать такую сортировку, но что-то не могу я придумать как её реализовать именно в односвязном списке, у нас ведь доступ не прямой как у массива здесь ... есть варианты?
Собственно код моего односвязного списка (большим количеством места отделены функции которые вряд-ли понадобятся для сортировки, я их просто оставил для целостности, 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();
}
Мне также подойдёт пример и с Вашим односвязным списком (если Вы например делали свой односвязный список с сортировкой вставками и у Вас остался код).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2011, 14:18
Ответы с готовыми решениями:

Сортировка пузырьком в циклическом односвязном списке
Добрый день, нужна помощь в сортировке пузырьком в циклическом односвязном...

Ошибка в односвязном списке
Помогите решить эти 2 проблемы C4101: NextNode: неиспользованная локальная...

Ошибка в односвязном списке
#include&lt;iostream&gt; #include&lt;clocale&gt; using namespace std; #define DEBUG ...

Использование деструктора в односвязном списке с++
Здравствуйте. Нужна срочная помощь!!! Есть реализация односвязного списка в...

Удаление по ключу в односвязном списке
Написал алгоритм удаления по ключу в линейном, односвязном списке, но он не...

24
Almaz1988
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 12
06.12.2013, 16:04 21
Цитата Сообщение от Gepar Посмотреть сообщение
Есть же книга Седжвика "Алгоритмы на с++", притом книг этой серии больше чем в серии алгоритмов на java. Нет конечно же, затраты на создание массива, копирование в него значений и копирование значений назад (по памяти и времени) будут всегда в разы дороже.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А сортировка слияниями для списков должна быть абсолютно незатратна по памяси, в отличие от массивов
Почему же тогда в книге эти алгоритмы сортировки для связных списков даже не приводятся? Все алгоритмы разбираются только на массивах.

Вот и в книге "Фундаментальные алгоритмы С++" того же Седжвика открываю главу 6, посвященную сортировке. Сортировке связных списков посвящен предпоследний пункт из 4-ех страниц и читаю:
Все программные реализации сортировок, рассмот-
рассмотренные к этому моменту, предполагают, что сортируемые данные представлены в
виде массивов.
Т.е. я еще больше убеждаюсь, что связный список не приспособлен к сортировке.
0
Kuzia domovenok
2320 / 2069 / 480
Регистрация: 25.03.2012
Сообщений: 7,372
Записей в блоге: 1
06.12.2013, 16:17 22
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. я еще больше убеждаюсь, что связный список не приспособлен к сортировке.
а сортировки матриц, сортировки деревьев, сортировки ... там тоже нету, значит "не нужны".
Логика... мда
0
Almaz1988
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 12
06.12.2013, 16:51 23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
а сортировки матриц, сортировки деревьев, сортировки ... там тоже нету, значит "не нужны".
Логика... мда
Насколько я понимаю дело все-таки в быстродействии. У Седжвика далее в книге:
Три классические структуры данных, способные поддерживать эффективные алгоритмы поиска - бинарные деревья поиска, красно-черные деревья и хеш-таблицы.
Т.е. каждая структура данных заточена под конкретный тип операций.
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
06.12.2013, 21:18  [ТС] 24
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. каждая структура данных заточена под конкретный тип операций.
Предлагаю тебе таки дочитать книгу до конца, а потом делать выводы
0
gray_fox
What a waste!
1553 / 1258 / 166
Регистрация: 21.04.2012
Сообщений: 2,636
Завершенные тесты: 3
06.12.2013, 21:44 25
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. каждая структура данных заточена под конкретный тип операций.
И? В связном списке вставка в произвольное место (+ возможно splice) за константу.
0
06.12.2013, 21:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2013, 21:44

Удаление узлов в односвязном списке
Помогите пожалуйста, не могу понять что не так. Нужно удалить узлы содержащие...

Поиск цикла в односвязном списке
есть односвязный список struct List { int value; struct List *next;...

Поиск и удаление в односвязном списке
Помогите с удаление элемента по ключу(номеру этажа). При удалении 2-го элемента...


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

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

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