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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Как поставить условие http://www.cyberforum.ru/cpp-beginners/thread354039.html
Есть переменные: x1, x2, y1, y2. И нужно сделать следующее: Прибавить к x1 единицу (++x1) в том случае если выполняется одно из условий: 1) x1 не равен x2 и y1 не равен y2 2) x1 равен x2 или y1 равен y2 Я как то запутался.
C++ Найти произведение элементов вектора Всем форумчанинам привет, прошу помощи решения задачи Задача: Найти произведение элементов вектора (массивы не использовать, значения перемножать по мере ввода). http://www.cyberforum.ru/cpp-beginners/thread354031.html
Простая база данных с помощью массива C++
здравствуйте. Помогите пожалуйста, можете написать пример простейшей базы данных созданной с помощью массива. База состоит из 3-5 строк,в каждой из которых фио и год рождения.операции с базой данных :поиск (по году рождения),удаление записи и добавление в любое место записи. Всем кто сможет помочь,огромное спасибо заранее! ну язык С++ конечно:)
C++ Определить дату предыдущего дня
Все доброго времени суток. Нужна помощь в решении задачи. Заранее огромное спасибо. Вот собственно и задача: "Дата некоторого дня определяется двумя натуральными числами: порядковым номером месяца и числом. Определить дату предыдущего дня."
C++ идеальное хеширование http://www.cyberforum.ru/cpp-beginners/thread353967.html
В лабораторной работе задание "реализовать идеальное хеширование". в методичке очень мало материала по хешированию и по данному вопросу в частности. Посоветуйте какую-нибудь литературу или статью по этой теме, где все объясняется с нуля.
C++ MS VS in CODE BLOCKS Делал проекты в VISUAL C++ EXPRESS. Сеичас пересел на LINUX, пользуюсь CODE BLOCKS . Есть какие-нибудь варианты как открыть проекты написанные в VS C++ - в CODE BLOCKS? ПС: не нужно писать типа ты че парень VS ето под вин и т.д. (если проблема открытия в этом) Спасибо. подробнее

Показать сообщение отдельно
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
20.09.2011, 15:59     Сортировка вставками в односвязном списке
Gepar, единственное, что я вижу - это ресурсоёмкий оператор индексации, который будет выполнять поиск нужного элемента, начиная с головы.

Хотя, если можете - сделайте список двусвязным.

Добавлено через 6 минут
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
// ........
 
element &operator[]( size_t i )
    {
        element *e = head;
 
        while( i && e != tail )
        {
           i--;
           e = e->next;
        }
 
        return *e;
    }
 
//...........
 
int main()
{
   //........
   for( int i = 0; i < 5; i++ )
       cout << test[i].data << ' ';
   //........
}
Добавлено через 23 минуты
Gepar, если с двусвязным списком, то вот мои эксперементы. Также советую сделать у себя итераторы:

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
#include <string>
#include <cstring>
 
using namespace std;
 
class List
{
public:
    struct element
    {
        char blank;
        string data;
        element * next;
        element * prev;
 
        element( string str, char bl = 0 ) : data(str), blank(bl){};
    };
 
    element * head;
    element * tail; /* полуоткрытый диапазон */
 
public:
 
    class iterator
    {
    public:
        iterator( element * e = 0 ) : ptr(e){};
        iterator( const iterator &it ) : ptr(it.ptr){};
 
        iterator &operator++(int)
        {
            if( !ptr->blank )
               ptr = ptr->next;
 
            return *this;
        }
 
        iterator &operator--(int)
        {
            if( ptr->prev )
               ptr = ptr->prev;
 
            return *this;
        }
 
        iterator operator+( size_t i )
        {
            iterator it( *this );
 
            for( ; i; i-- )
               it++;
 
            return it;
        }
 
        iterator operator-( size_t i )
        {
            iterator it( *this );
 
            for( ; i; i-- )
               it--;
 
            return it;
        }
 
        string &operator*()
        {
            return ptr->data;
        }
 
        bool operator==( const iterator &it )
        {
            return ptr == it.ptr;
        }
 
        bool operator!=( const iterator &it )
        {
            return ptr != it.ptr;
        }
 
    private:
        element * ptr;
    };
 
    List( string str = "" )
    {
        head = new element(str);
        tail = new element( "", 1 );
 
        head->next = tail;
        head->prev = 0;
 
        tail->next = 0;
        tail->prev = head;
    }
 
    ~List()
    {
        element * it = head;
 
        while( it )
        {
            element * prev = it;
            it = it->next;
            delete prev;
        }
    }
 
    iterator begin(){ return iterator( head ); }
    iterator end(){ return iterator( tail ); }
 
    element * push_back( const string &str )
    {
        tail->data = str;
        tail->blank = 0;
        tail->next = new element("", 1);
        tail->next->prev = tail;
        tail = tail->next;
        tail->next = 0;
    }
 
    element * push_front( const string &str )
    {
        element * new_head = new element(str);
        new_head->next = head;
        head->prev = new_head;
        head = new_head;
    }
 
    element &operator[]( size_t i )
    {
        element *e = head;
 
        while( i && e != tail )
        {
           i--;
           e = e->next;
        }
 
        return *e;
    }
 
    void sort()
    {
        for( iterator it1 = begin(); it1 != end(); it1++ )
        {
            for( iterator it2 = it1; it2 != begin(); it2-- )
            {
                if( strcmp( (*it2).c_str(), (*(it2 - 1)).c_str() ) > 0 )
                   break;
 
                string tmp = *it2;
                *it2 = *(it2 - 1);
                *(it2 - 1) = tmp;
            }
        }
    }
};
 
 
int main()
{
    List test("simple");
 
    test.push_back("text");
    test.push_back("is");
    test.push_back("so");
    test.push_back("simple");
 
    for( List::iterator it = test.begin(); it != test.end(); it++ )
       cout << *it << ' ';
 
    cout << endl;
 
    test.sort();
 
    for( int i = 0; i < 5; i++ )
       cout << test[i].data << ' ';
}
Добавлено через 32 минуты
Вот так же с stl-совместимым двунаправленным итератором
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
class List
{
public:
    struct element
    {
        char blank;
        string data;
        element * next;
        element * prev;
 
        element( string str, char bl = 0 ) : data(str), blank(bl){};
    };
 
    element * head;
    element * tail; /* полуоткрытый диапазон */
 
public:
 
    class iterator
    {
    private:
        element * ptr;
 
    public:
        typedef string value_type;
        typedef string& reference;
        typedef string* pointer;
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef std::ptrdiff_t difference_type;
        typedef std::ptrdiff_t distance_type;
 
        iterator( element * e = 0 ) : ptr(e){};
        iterator( const iterator &it ) : ptr(it.ptr){};
 
        iterator &operator++()
        {
            if( !ptr->blank )
               ptr = ptr->next;
 
            return *this;
        }
 
        iterator &operator--()
        {
            if( ptr->prev )
               ptr = ptr->prev;
 
            return *this;
        }
 
        iterator &operator+=( size_t i )
        {
            for( ; i; i-- )
               ++(*this);
 
            return *this;
        }
 
        iterator &operator-=( size_t i )
        {
            for( ; i; i-- )
               --(*this);
 
            return *this;
        }
 
        iterator operator+( size_t i )
        {
            iterator it( *this );
            it += i;
            return it;
        }
 
        iterator operator-( size_t i )
        {
            iterator it( *this );
            it -= i;
            return it;
        }
 
        string &operator*()
        {
            return ptr->data;
        }
 
        bool operator==( const iterator &it )
        {
            return ptr == it.ptr;
        }
 
        bool operator!=( const iterator &it )
        {
            return ptr != it.ptr;
        }
    };
 
    List( string str = "" )
    {
        head = new element(str);
        tail = new element( "", 1 );
 
        head->next = tail;
        head->prev = 0;
 
        tail->next = 0;
        tail->prev = head;
    }
 
    ~List()
    {
        element * it = head;
 
        while( it )
        {
            element * prev = it;
            it = it->next;
            delete prev;
        }
    }
 
    iterator begin(){ return iterator( head ); }
    iterator end(){ return iterator( tail ); }
 
    element * push_back( const string &str )
    {
        tail->data = str;
        tail->blank = 0;
        tail->next = new element("", 1);
        tail->next->prev = tail;
        tail = tail->next;
        tail->next = 0;
    }
 
    element * push_front( const string &str )
    {
        element * new_head = new element(str);
        new_head->next = head;
        head->prev = new_head;
        head = new_head;
    }
 
 
    element &operator[]( size_t i )
    {
        element *e = head;
 
        while( i && e != tail )
        {
           i--;
           e = e->next;
        }
 
        return *e;
    }
 
    void sort( bool f( string &, string& ) )
    {
        for( iterator it1 = begin(); it1 != end(); ++it1 )
        {
            for( iterator it2 = it1; it2 != begin(); --it2 )
            {
                //if( strcmp( (*it2).c_str(), (*(it2 - 1)).c_str() ) > 0 )
                if( f( *it2, *(it2 - 1) ) )
                   break;
 
                string tmp = *it2;
                *it2 = *(it2 - 1);
                *(it2 - 1) = tmp;
            }
        }
    }
};
 
 
// предикат для cmp
bool cmp( string &str1, string &str2 )
{
    return strcmp( str1.c_str(), str2.c_str() ) < 0;
}
 
int main()
{
    List test("simple");
 
    test.push_back("text");
    test.push_back("is");
    test.push_back("so");
    test.push_back("simple");
 
    for_each( test.begin(), test.end(), [](string &s){ cout << s << ' ';} );
 
    cout << '\n';
 
    //test.sort( []( string &str1, string &str2 ){ return strcmp( str1.c_str(), str2.c_str() ) < 0; } );
    test.sort( cmp );
 
    for_each( test.begin(), test.end(), [](string &s){ cout << s << ' ';} );
}
std::sort не поддерживается, так как у нас двунаправленный итератор, а там нужен итератор произвольного доступа.


В любом случае, даже в однонаправленном списке можно реализовать сортировку вставками при помощи operator[].
 
Текущее время: 16:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru