С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.69
Gepar
1178 / 534 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

20.09.2011, 14:18. Просмотров 5791. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка вставками в односвязном списке (C++):

Ошибка в односвязном списке - C++
#include&lt;iostream&gt; #include&lt;clocale&gt; using namespace std; #define DEBUG class Monom{ protected: int...

Ошибка в односвязном списке - C++
Помогите решить эти 2 проблемы C4101: NextNode: неиспользованная локальная переменная (в 118 строке) C4703: используется потенциально...

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

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

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

Удаление узлов в односвязном списке - C++
Помогите пожалуйста, не могу понять что не так. Нужно удалить узлы содержащие простые числа.Программа не удаляет! #include&lt;iostream&gt; ...

24
talis
792 / 544 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
02.10.2011, 13:50 #16
Извините, неправильно изобразил вторую схему. Вот так надо было:

Сортировка вставками в односвязном списке
0
Gepar
1178 / 534 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
02.10.2011, 16:22  [ТС] #17
Цитата Сообщение от talis Посмотреть сообщение
То есть, в любом случае нужно знать адрес предыдущего элемента.
Мммм, ну да, я подзабыл что при моём обмене ссылок нужно ещё и пред. элемент сделать чтобы указывал на новые изменённые данные ... тем не менее преподаватель точно говорил что мол чтобы мы ему меняли только указатели, а не информационные части... есть вариант как реализовать максимально эффективную сортировку в односвязном списке с заменой только указателей? У меня из задания так уже всё реализовано, кроме сортировки ...
Можно в принципе хранить адрес ещё и предыдущего предыдущему элементу но такой алгоритм учитывающий всё у меня что-то тоже не получается ...

Добавлено через 2 часа 26 минут
Вроде написал какую-то сортировку, не знаю только как её назвать, я пока её называю "работающая сортировка"
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
void Students:: sort(bool cmp(string&,string&))
{
    ListItem* new_begin=NULL;
    ListItem* new_end=NULL;
    ListItem* sprev=NULL;
 
    for(ListItem *scur=this->Head;scur!=NULL;scur=this->Head)
    {
        ListItem *smin=NULL;
        ListItem *sminprev=scur;
        string min_name=scur->fullname;
        for(ListItem *gp=scur->Next;gp!=NULL;gp=gp->Next)
        {
            if(cmp(gp->fullname,min_name))
            {
                min_name=gp->fullname;
                smin=gp;
                sprev=sminprev;
            }
            sminprev=gp;
        }
        if(smin==NULL)
        {
            smin=scur;
        }
        else if(smin==scur->Next)
        {
            scur->Next=scur->Next->Next;
        }
        else
        {
            sprev->Next=smin->Next;
        }
        if(new_begin!=NULL)
        {
            new_end->Next=smin;
            new_end=smin;
        }
        else
        {
            new_begin=smin;
            new_end=smin;
        }
        if(smin==this->Head)
         this->Head=smin->Next;
    }
    this->Head=new_begin;
    this->Tail=new_end;
 
}
0
Almaz1988
0 / 0 / 0
Регистрация: 24.11.2012
Сообщений: 12
05.12.2013, 16:04 #18
Здравствуйте, у меня несколько вопросов методического плана)
Читаю книгу Седжвика "Алгоритмы в Java" и решаю все задачи на С++.
Дошел до главы "Сортировка", реализовал сортировку Шелла, выбором, связную и быструю сортировку статических массивов. Результаты совпали с книжными: самым быстрым способом оказалась Быстрая сортировка. Также реализовал все эти способы сортировки для односвязных списков. Как и ожидалось сортировка односвязного списка происходит гораздо медленнее, чем сортировка статического массива: "Быстрая" сортировка 1 млн целых чисел в виде обычного массива заняла 143 мС, а в виде односвязного списка - почти 10 секунд.

Тут и появился вопрос: выполняется ли на практике сортировка односвязных списков?
Как мне кажется - гораздо производительнее будет односвязный список скопировать в обычный массив, произвести в нем сортировку и скопировать обратно в список. Прав ли я? Спасибо)
0
Gepar
1178 / 534 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
06.12.2013, 15:02  [ТС] #19
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Читаю книгу Седжвика "Алгоритмы в Java" и решаю все задачи на С++.
Есть же книга Седжвика "Алгоритмы на с++", притом книг этой серии больше чем в серии алгоритмов на java.

Цитата Сообщение от Almaz1988 Посмотреть сообщение
Как мне кажется - гораздо производительнее будет односвязный список скопировать в обычный массив, произвести в нем сортировку и скопировать обратно в список. Прав ли я? Спасибо)
Нет конечно же, затраты на создание массива, копирование в него значений и копирование значений назад (по памяти и времени) будут всегда в разы дороже.
0
Kuzia domovenok
2062 / 1907 / 176
Регистрация: 25.03.2012
Сообщений: 6,572
Записей в блоге: 1
06.12.2013, 15:22 #20
Для списков даже обычная сортировка вставками должна быть гораздо быстрее

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

Вот и в книге "Фундаментальные алгоритмы С++" того же Седжвика открываю главу 6, посвященную сортировке. Сортировке связных списков посвящен предпоследний пункт из 4-ех страниц и читаю:
Все программные реализации сортировок, рассмот-
рассмотренные к этому моменту, предполагают, что сортируемые данные представлены в
виде массивов.
Т.е. я еще больше убеждаюсь, что связный список не приспособлен к сортировке.
0
Kuzia domovenok
2062 / 1907 / 176
Регистрация: 25.03.2012
Сообщений: 6,572
Записей в блоге: 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
1178 / 534 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
06.12.2013, 21:18  [ТС] #24
Цитата Сообщение от Almaz1988 Посмотреть сообщение
Т.е. каждая структура данных заточена под конкретный тип операций.
Предлагаю тебе таки дочитать книгу до конца, а потом делать выводы
0
gray_fox
What a waste!
1522 / 1227 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 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
Привет! Вот еще темы с ответами:

Ошибка с удалением элемента в односвязном списке - C++
Здравствуйте! Вроде написал функцию удаления элемента в указанной позиции, но почему то не срабатывает. Где ошибка?Или если есть вариант...

Удаление повторяющихся элементов в односвязном списке - C++
Добрый день! Задание такое: построить линейный список из нескольких динамических переменных, содержащих вводимые целые числа....

Как сделать сортировку по узлам в односвязном списке? - C++
Есть задача: отсортировать узлы по возрастанию в односвязном списке. Есть код, но при его выполнении вылетает ошибка: Вызвано исключение...

Найти в односвязном списке отрицательные элементы и удалить их - C++
Нужно в списке, типа очередь находить отрицательные элементы и удалять их. Написал код, но почему то не работает функция удаления...


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

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

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