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

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

Войти
Регистрация
Восстановить пароль
 
Zakhsukh
0 / 0 / 0
Регистрация: 17.04.2013
Сообщений: 8
#1

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

16.10.2013, 21:26. Просмотров 503. Ответов 0
Метки нет (Все метки)

В плюсах полный нуб.
Что-то смог написать с помощью разных интернет ресурсов..
Это даже работает так как нужно.
НО еще нужно написать итератор, с ним возникли большие проблемы.
итератор для доступа к значениям в списке с основными операциями:
– установка на первое значение в списке,
– переход к следующему значению в списке,
– проверка состояния итератора,
– доступ по чтению и записи к текущему значению.

Вот код без итератора:
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
 
 
//связанные структуры
 
template <class T>
 
class list
{
    
    struct elem
    {
        int first;
        int free;
        T data;
        elem *next;
        elem (){};
        elem(T d){data = d;}
    };
    elem*head;
    int size;
    public:
        list()
        {
            head = new elem; 
            head->next = head; 
            size = 0;
        }
//print all elements
    void display(){
        int n = 0;
        elem *pre=head;
         while (n<=size) //До тех пор пока не встретит пустое значение
         {
          cout<<pre->data<<" "; //Выведет элемент x из списка
          pre=pre->next; //Указываем, что далее нам нужен следующий элемент
          n++;
         }
    }
//insert by id function
    bool insert_by_id(T d, int n)
    {
        if (n>size || n<(size-size)) {
            return false;
        }
        else{
            elem* p_new = new elem;
            
            elem *pre=head;
            elem* p=head;
            elem *current=head;
            for (int i=0; i<n; i++, pre=p, p=p->next)
            {
                current = current->next;                            
            }
            p_new -> next = pre -> next;    
            pre->next = p_new;
            p_new->data = d;
            size++;
            return true;
        }
    }
//insert function
    bool insert(T d)
    {
        elem* p_new = new elem;
        int j=size;
        j++;
        elem *pre=head;
        elem* p=head;
            for (int i=0; i<j; i++, pre=p, p=p->next)
            {
                p_new -> next = pre -> next;                
            }
        pre->next = p_new;
        p_new->data = d;
        size=j;
        return true;
    }
 
    bool del_by_id(int n){
        if (n>size || n<0){return false;}
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        for (int i = 0; i < n; i++){
            current = current->next;
        }
        if (current!=NULL){//проверка на корректность
            if (current==head){//удаляем первый элемент
                head = head->next;
                delete(current);
                current = head;
            }
            else {//удаляем непервый элемент
                ptr = head;
                while (ptr->next != current)
                    ptr = ptr->next; 
                ptr->next = current->next;
                delete(current);
                current=ptr;
            }
            size--;
            return true;
        }
    }
//delete by value
    bool del_by_val(char value){
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        
        for (int i = 0; i < size; i++){
            current = current->next;
            if (current->data == value){
                i = size + 1;
            }
        }
        if (current->data == value){
            if (current!=NULL){//проверка на корректность
                if (current==head){//удаляем первый элемент
                    head = head->next;
                    delete(current);
                    current = head;
                }
                else {//удаляем непервый элемент
                    ptr = head;
                    while (ptr->next != current)
                        ptr = ptr->next; 
                    ptr->next = current->next;
                    delete(current);
                    current=ptr;
                }
                size--;
                return true;
            }
        }
        else{return false;}
    }
//find element by value
    int find_by_val(char value){
        string f;
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        for (int i = 1; i < size; i++){
            current = current->next;
            if (current!=NULL){//проверка на корректность
                if (current->data==value){
                    return i;
                }
            }
        }
        return -1;
    }
//rewrite the element with index
    bool cahnge_by_index(char value, int n){
        if (n>size || n<0){return false;}
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        for (int i = 0; i < n; i++)
            current = current->next;
            if (current!=NULL){//проверка на корректность
                current->data=value;
                return true;                                
            }
    }
//read the element with index
    string find_by_id(int n){
        string element = "nothing.";
        if (n>size || n<0){return element;}
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        for (int i = 0; i < n; i++)
            current = current->next;
            if (current!=NULL){//проверка на корректность
                    element = current->data;
                    return element;
            }
    }
//if element with input value exist
    bool check_by_val(char value){
        
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        for (int i = 1; i < size; i++){
            current = current->next;
            if (current!=NULL){//проверка на корректность
                if (current->data==value){
                    return true;
                    i = size+1;
                }
            }
        }
        return false;
    }
//show size
    int show_size(){
        return size;
    }
//if list is empty
    int emptiness(){
        int rez;
        if (size<=0){
            rez = 0;
        }
        else{
            rez = 1;
        }
        return rez;
    }
//clear list
    bool clear_list(){
        elem *pre=head;
        elem *ptr;//вспомогательный указатель
        elem *current=head;
        
        for (int i = 0; i < size; i++){
            current = current->next;
            
            if (current!=NULL){//проверка на корректность
                if (current==head){//удаляем первый элемент
                    head = head->next;
                    delete(current);
                    current = head;
                }
                else {//удаляем непервый элемент
                    ptr = head;
                    while (ptr->next != current)
                        ptr = ptr->next; 
                    ptr->next = current->next;
                    delete(current);
                    current=ptr;
                }
                size--;
            }
        }
        size=0;
        return true;
    }
};
 
int main()
{
    bool m = false;
    list<char>* my_list=new list<char>;
    
    cout << "\nPlease, enter command:\n1-insert element by id\n2-insert element\n3-delete element by id\n4-show elements\n5-delete element by value\n6-find element by value\n7-change element with entered index\n8-show element with entered index\n9-find if element with entered value exist\n10-show size\n11-check if list is empty\n12-clear list\n";
    while(true){    
        int pickedCommandNumber=0;
        cin >> pickedCommandNumber;
    switch(pickedCommandNumber){
    case 1:{
        cout<<"Enter index of new element:";
        int index;
        cin>>index;
        cout<<"Enter content:";
        char content;
        cin>>content;
        m = my_list->insert_by_id(content, index);
        if (m){cout<<"insert by id done.";}
        else {cout<<"insert by id failed";}
        }
    break;
    case 2:{
        cout<<"Enter content:";
        char content;
        cin>>content;
        m = my_list->insert(content);
        if (m){cout<<"insert done.";}
        else {cout<<"insert failed";}
        }
 
    break;
    case 3:{
        cout<<"Enter index:";
        int index;
        cin>>index;
        m = my_list->del_by_id(index);
        if (m){cout<<"delete by id done.";}
        else {cout<<"delete by id failed";}
        }
    break;
    case 4:{
        my_list->display();
        }
    break;
    case 5:{
        cout<<"Enter value:";
        char value;
        cin>>value;
        m = my_list->del_by_val(value);
        if (m){cout<<"delete by value done.";}
        else {cout<<"delete by value failed";}
        }
    break;
    case 6:{
        int found;
        cout<<"Enter value:";
        char value;
        cin>>value;
        found = my_list->find_by_val(value);
        if (found==-1){cout<<"element have not been found";}
        else {cout<<"element position "<<found;}
        }
    break;
    case 7:{
        cout<<"Enter index:";
        int index;
        cin>>index;
        cout<<"Enter value:";
        char value;
        cin>>value;     
        m = my_list->cahnge_by_index(value, index);
        if (m){cout<<"change by id done.";}
        else {cout<<"change by id failed";}
        }
    break;
    case 8:{
        string found;
        cout<<"Enter index:";
        int index;
        cin>>index;     
        found = my_list->find_by_id(index);
        cout<<"found "<<found;
        }
    break;
    case 9:{
        cout<<"Enter value:";
        char value;
        cin>>value;     
        m = my_list->check_by_val(value);
        if (m){cout<<"Element exist.";}
        else {cout<<"Element haven't been found.";}     
        }
    break;
    case 10:{
        int list_size;
        list_size = my_list->show_size();
        cout<<"list size "<<list_size;
        }
    break;
    case 11:{
        int m = my_list->emptiness();
        if (m==0){
            cout<<"list is empty";
        }
        else{
            cout<<"list is not empty";
        }       
        }
    break;
    default:;
 
    }
 
    }
    
    return 0;
    
}
Если кто поможет с организацией подкласса итератор в классе list, буду очень благодарен..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2013, 21:26     Кольцевой односвязный список на базе адресных указателей с использованием фиктивного элемента
Посмотрите здесь:

C++ Кольцевой односвязный список
C++ Кольцевой односвязный список
C++ Кольцевой односвязный список
C++ Односвязный список с добавлением нового элемента в конец.
Односвязный кольцевой список, реализовать C++
Односвязный список: оптимальное удаление элемента C++
C++ Сформировать односвязный кольцевой линейный список по файлу целых чисел
C++ Односвязный список: удаление элемента
C++ Функция добавления элемента в кольцевой список
Вставка элемента в линейный односвязный список после заданного C++
C++ Функция добавления элемента в односвязный список в указанную позицию
C++ Вставка элемента в пустой односвязный список

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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