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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 265, средняя оценка - 4.79
Vasiliusis
40 / 40 / 1
Регистрация: 14.10.2008
Сообщений: 131
#1

Односвязный, двусвязный список, стек, очередь - C++

11.12.2008, 16:14. Просмотров 33315. Ответов 34
Метки нет (Все метки)

В общем, всем кто нуждается. Баггов вы не найдете.

Односвязный список
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
#include <iostream>
#include <windows.h>
using namespace std;
 
class Node
{
public:
    int number;
    Node* next;
};
 
void russia(const char*);
 
void main()
{
    Node* head = NULL;
    Node* lastPtr = NULL;
    short action = -1;
    while (1)
    {
        russia("1. Добавить Элемент\n");
        russia("2. Просмотр Списка\n");
        russia("3. Поиск Элемента\n");
        russia("4. Удалить Элемент\n");
        russia("5. Удалить Элемент По Выбору\n");
        russia("0. Выход\n\n");
        russia("Ваш Выбор: ");
        cin>>action;
        if (action == 0)
        {
            system("CLS");
            break;
        }
 
        if (action == 1)
        {
            system("CLS");
            Node* ptr = new Node;
            int numb = -1;
            russia("Введите Число: ");
            cin>>numb;
            ptr->number = numb;
            ptr->next = NULL;
            if (head == 0)
            {
                head = ptr;
                lastPtr = ptr;
                system("CLS");
                continue;
            }
            lastPtr->next = ptr;
            lastPtr = ptr;
            system("CLS");
            continue;
        }
 
        if (action == 2)
        {
            Node* ptr = NULL;
            system("CLS");
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("* * * * * СПИСОК * * * * *\n\n");
            ptr = head;
            while (1)
            {
                cout<<ptr->number<<" ";
                if (ptr->next == 0)
                    break;
                ptr = ptr->next;
            }
            cout<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 3)
        {
            Node* ptr = NULL;
            int key = -1;
            system("CLS");
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("Введите Элемент Для Поиска: ");
            cin>>key;
            ptr = head;
            while (1)
            {
                if (key == ptr->number)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n");
                    break;
                }
                if (ptr->next == NULL)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
                    break;
                }
                ptr = ptr->next;
            }
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 4)
        {
            system("CLS");
            Node* ptrDelete = NULL;         
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            if (head->next == NULL)
            {
                head = NULL;
                delete head;
                continue;
            }
            ptrDelete = head;
            head = ptrDelete->next;
            delete ptrDelete;
            continue;
        }
 
        if (action == 5)
        {
            system("CLS");
            Node* ptrPrev = NULL;
            Node* ptrDelete = NULL;
            int key = -1;
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("Введите Элемент Для Удаления: ");
            cin>>key;
            ptrDelete = head;
            if (ptrDelete->number == key)
            {
                head = ptrDelete->next;
                delete ptrDelete;
                system("CLS");
                continue;
            }
            while (1)
            {
                if (key == ptrDelete->number)
                {
                    ptrPrev->next = ptrDelete->next;
                    delete ptrDelete;
                    break;
                }
                if (ptrDelete->next == 0)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
                    system("PAUSE");
                    break;
                }
                ptrPrev = ptrDelete;
                ptrDelete = ptrDelete->next;
            }
            system("CLS");
            continue;
        }
 
        if (action > 5)
        {
            system("CLS");
            russia("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
            system("PAUSE");
            system("CLS");
            continue;
        }
    }   
}
 
void russia(const char* rus)
{
    char word[100];
    CharToOem(rus, word);
    cout<<word;
}
Двусвязный список
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
#include <iostream>
#include <windows.h>
using namespace std;
 
class Node
{
public:
    int number;
    Node* next;
    Node* last;
};
 
void russia(const char*);
 
void main()
{
    short action = -1;
    Node* head = NULL;
    Node* tail = NULL;
    Node* ptrLast = NULL;
 
    while (1)
    {       
        russia("1. Добавить Элемент\n");
        russia("2. Просмотр Списка Слева Направо\n");
        russia("3. Просмотр Списка Справа Налево\n");
        russia("4. Удалить Голову\n");
        russia("5. Удалить Хвост\n");
        russia("6. Поиск Элемента\n");
        russia("0. Выход\n\n");
        russia("Ваш Выбор: ");
        cin>>action;
 
        if (action == 0)
        {
            system("CLS");
            break;
        }
 
        if (action == 1)
        {
            system("CLS");
            int numb = -1;
            russia("Введите Число: ");
            cin>>numb;
            Node* ptr = new Node;
            ptr->number = numb;
            ptr->next = NULL;
            tail = ptr;
            if (head == NULL)
            {
                head = ptr;
                ptrLast = ptr;
                ptr->last = NULL;
                system("CLS");
                continue;
            }
            ptr->last = ptrLast;
            ptrLast->next = ptr;
            ptrLast = ptr;
            system("CLS");
            continue;
        }
 
        if (action == 2)
        {
            system("CLS");
            Node* ptr = NULL;
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("* * * * * СПИСОК: СЛЕВА НАПРАВО * * * * *\n\n");
            ptr = head;
            while (1)
            {
                cout<<ptr->number<<" ";
                if (ptr->next == 0)
                    break;
                ptr = ptr->next;
            }
            cout<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 3)
        {
            system("CLS");
            Node* ptr = NULL;           
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("* * * * * СПИСОК: СПРАВА НАЛЕВО * * * * *\n\n");
            ptr = tail;
            while (1)
            {
                cout<<ptr->number<<" ";
                if (ptr->last == 0)
                    break;
                ptr = ptr->last;
            }
            cout<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 4)
        {
            system("CLS");
            Node* ptrDelete = NULL;         
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            if (head->next == NULL)
            {
                head = NULL;
                tail = NULL;
                delete head;
                continue;
            }
            ptrDelete = head;
            head = ptrDelete->next;
            head->last = NULL;
            delete ptrDelete;
            continue;
        }
 
        if (action == 5)
        {
            system("CLS");
            Node* ptrDelete = NULL;
            if (tail == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            if (tail->last == NULL)
            {
                head = NULL;
                tail = NULL;
                delete tail;
                continue;
            }           
            ptrDelete = tail;
            tail = ptrDelete->last;
            tail->next = NULL;
            ptrLast = tail;
            delete ptrDelete;
            continue;
        }
 
        if (action == 6)
        {
            system("CLS");
            Node* ptr = NULL;
            int key = -1;
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("Введите Элемент Для Поиска: ");
            cin>>key;           
            ptr = head;
            while (1)
            {
                if (key == ptr->number)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n");
                    break;
                }
                if (ptr->next == NULL)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
                    break;
                }
                ptr = ptr->next;
            }
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action > 6)
        {
            system("CLS");
            russia("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
            system("PAUSE");
            system("CLS");
            continue;
        }
    }
}
 
void russia(const char* rus)
{
    char word[100];
    CharToOem(rus, word);
    cout<<word;
}
Стек
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
#include <iostream>
#include <windows.h>
using namespace std;
 
class Node
{
public:
    int number;
    Node* last;
};
 
void russia(const char*);
 
void main()
{
    Node* ptrLast = NULL;
    Node* top = NULL;
    short action = -1;
 
    while (1)
    {
        russia("1. Затолкнуть В Стек\n");
        russia("2. Вытолкнуть Из Стека\n");
        russia("3. Вершина Стека\n");
        russia("4. Содержимое Стека\n");
        russia("0. Выход\n\n");
        russia("Ваш Выбор: ");
        cin>>action;        
 
        if (action == 0)
        {
            system("CLS");
            break;
        }
 
        if (action == 1)
        {
            system("CLS");
            int numb = -1;          
            russia("Введите Число: ");
            cin>>numb;
            Node* ptr = new Node;
            ptr->number = numb;         
            if (top == NULL)
            {
                ptr->last = NULL;
                top = ptr;
                ptrLast = ptr;
                system("CLS");
                continue;
            }
            top = ptr;
            ptr->last = ptrLast;
            ptrLast = ptr;
            system("CLS");
            continue;
        }
 
        if (action == 2)
        {
            system("CLS");
            Node* ptrDelete = NULL;
            if (top == NULL)
            {
                russia("\t!!! СТЕК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }           
            ptrDelete = top;
            if (ptrDelete->last == NULL)
            {
                top = NULL;
                delete ptrDelete;
                system("CLS");
                continue;
            }
            top = ptrDelete->last;
            ptrLast = top;
            delete ptrDelete;
            continue;
        }
 
        if (action == 3)
        {
            system("CLS");
            if (top == NULL)
            {
                russia("\t!!! СТЕК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("Вершина Стека: ");
            cout<<top->number<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 4)
        {
            system("CLS");
            Node* ptr = NULL;
            if (top == NULL)
            {
                russia("\t!!! СТЕК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("* * * * * СОДЕРЖИМОЕ СТЕКА * * * * *\n\n");
            ptr = top;
            while (1)
            {
                cout<<ptr->number<<endl;
                if (ptr->last == NULL)
                {
                    system("PAUSE");
                    system("CLS");
                    break;
                }
                ptr = ptr->last;
            }
        }
 
        if (action > 4)
        {
            system("CLS");
            russia("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
            system("PAUSE");
            system("CLS");
            continue;
        }
 
    }
}
 
void russia(const char* rus)
{
    char word[100];
    CharToOem(rus, word);
    cout<<word;
}
Очередь
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
#include <iostream>
#include <windows.h>
using namespace std;
 
class Node
{
public:
    int number;
    Node* last;
    Node* next;
};
 
void russia(const char*);
 
void main()
{
    Node* head = NULL;
    Node* tail = NULL;
    Node* ptrLast = NULL;
    short action = -1;
 
    while(1)
    {
        russia("1. Добавить Элемент\n");
        russia("2. Просмотр Очереди\n");
        russia("3. Удалить Элемент\n");
        russia("4. Поиск Элемента\n");
        russia("0. Выход\n\n");
        russia("Ваш Выбор: ");
        cin>>action;
 
        if (action == 0)
        {
            system("CLS");
            break;
        }
 
        if (action == 1)
        {
            system("CLS");
            int numb = -1;
            russia("Введите Число: ");
            cin>>numb;
            Node* ptr = new Node;
            ptr->number = numb;
            ptr->next = NULL;
            tail = ptr;
            if (head == NULL)
            {
                head = ptr;
                ptrLast = ptr;
                ptr->last = NULL;
                system("CLS");
                continue;
            }
            ptr->last = ptrLast;
            ptrLast->next = ptr;
            ptrLast = ptr;
            system("CLS");
            continue;
        }
 
        if (action == 2)
        {
            system("CLS");
            Node* ptr = NULL;           
            if (head == NULL)
            {
                russia("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("* * * * * ОЧЕРЕДЬ * * * * *\n\n");
            ptr = tail;
            while (1)
            {
                cout<<ptr->number<<" ";
                if (ptr->last == 0)
                    break;
                ptr = ptr->last;
            }
            cout<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 3)
        {
            system("CLS");
            Node* ptrDelete = NULL;
            if (head == NULL)
            {
                russia("\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            if (head->next == NULL)
            {
                head = NULL;
                tail = NULL;
                delete tail;
                continue;
            }           
            ptrDelete = head;
            head = ptrDelete->next;
            head->last = NULL;
            delete ptrDelete;
            continue;
        }
 
        if (action == 4)
        {
            system("CLS");
            Node* ptr = NULL;
            int key = -1;
            if (head == NULL)
            {
                russia("\t!!! СПИСОК ПУСТ !!!\n\n");
                system("PAUSE");
                system("CLS");
                continue;
            }
            russia("Введите Элемент Для Поиска: ");
            cin>>key;           
            ptr = head;
            while (1)
            {
                if (key == ptr->number)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n");
                    break;
                }
                if (ptr->next == NULL)
                {
                    russia("\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n");
                    break;
                }
                ptr = ptr->next;
            }
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action > 4)
        {
            system("CLS");
            russia("\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n");
            system("PAUSE");
            system("CLS");
            continue;
        }
    }
}
 
void russia(const char* rus)
{
    char word[100];
    CharToOem(rus, word);
    cout<<word;
}
Пользуйтесь, наздоровье
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2008, 16:14     Односвязный, двусвязный список, стек, очередь
Посмотрите здесь:
C++ Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список»
C++ Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов
C++ Двусвязный в односвязный список
Преобразовать односвязный список в двусвязный C++
C++ Преобразовать односвязный список в двусвязный
Создать динамический односвязный или двусвязный список C++
C++ Возможно ли как-то переделать односвязный список в двусвязный?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ксюшк@
0 / 0 / 0
Регистрация: 02.06.2010
Сообщений: 17
07.06.2010, 22:42     Односвязный, двусвязный список, стек, очередь #21
а в чем разница этих двух строчек?
lastPtr->next = ptr;
lastPtr = ptr;
Обьясните,плиз)
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
08.06.2010, 02:09     Односвязный, двусвязный список, стек, очередь #22
lastPtr - указатель на последний элемент списка
следующий за ним элемент поначалу равен NULL
ptr - новый узел, который добавляется
нужно добавить его после последнего элемента

когда ptr добавлен после lastPtr, lastPtr указывает на предпоследний элемент
поэтому переставляем указатель lastPtr на последний элемент

в ptr->next записан NULL, поэтому после перестановки lastPtr на ptr lastPtr->next даст NULL
Ксюшк@
0 / 0 / 0
Регистрация: 02.06.2010
Сообщений: 17
08.06.2010, 10:19     Односвязный, двусвязный список, стек, очередь #23
Почему,когда я пытаюсь присвоить элементу какое-то значение,например
ptr->name="ivanov" он мне выводит ошибку "Cannot convert 'char *' to 'char'?
А если в самой структуре написать name[10], то выдает "Lvalue required".
Как сделать так,чтобы он присваивал имя длиннее одного символа?
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
08.06.2010, 10:31     Односвязный, двусвязный список, стек, очередь #24
C
1
2
3
4
5
6
7
8
9
10
11
12
13
struct node {
    char name[10];
    struct node *next;
};
 
...
 
    struct node n, *ptr;
 
    ptr = &n;
 
    strcpy(ptr->name, "ivanov");
    ptr->next = NULL;
для strcpy() нужно сделать #include <string.h>
если C++, #include <cstring>

Добавлено через 2 минуты
ещё бывает так
C
1
2
3
4
5
6
7
8
9
10
11
12
13
struct node {
    char *name;
    struct node *next;
};
 
...
 
    struct node n, *ptr;
 
    ptr = &n;
 
    ptr->name = "ivanov";
    ptr->next = NULL;
во втором случае строку нельзя видоизменить (она является строковой константой)
Ксюшк@
0 / 0 / 0
Регистрация: 02.06.2010
Сообщений: 17
08.06.2010, 10:36     Односвязный, двусвязный список, стек, очередь #25
А что означает
ptr = &n;?мы ведь потом это n нигде не используем.
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
09.06.2010, 01:33     Односвязный, двусвязный список, стек, очередь #26
n используется, доступ к нему осуществляется с помощью указателя ptr
указатель ничего из себя не представляет, это переменная, которая может хранить только адрес чего-нибудь
megabobik
0 / 0 / 0
Регистрация: 15.01.2010
Сообщений: 45
10.06.2010, 08:10     Односвязный, двусвязный список, стек, очередь #27
Можете помочь с такой задачей ?

Построить односвязный список, в котором каждый елемент поле связи спредыдущим или следующим елементом елементом списка. Определить количество узлов списка. Найти узел с заданым значением и напечатать его порядковый номер.
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
10.06.2010, 08:41     Односвязный, двусвязный список, стек, очередь #28
C
1
2
3
4
struct node {
    int num;
    struct node *next;
};
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    struct node *list; /* указатель на первый узел списка */
    struct node n1, n2, n3, n4; /* это разные узлы */
    
    list = &n1;
    list->next = &n2;
    list->next->next = &n3;
    list->next->next->next = &n4;
    
    /* список готов, в нём четыре узла */
 
    list->num = 1;
    list->next->num = 2;
    list->next->next->num = 3;
    list->next->next->next->num = 4;
 
    /* занесли значения в каждый узел */
 
    /* дальше список можно выводить, считать количество элементов */
 
    list->next->next->next->next = NULL; /* конец списка */
    
    /* пятого узла нет, он равен NULL */
megabobik
0 / 0 / 0
Регистрация: 15.01.2010
Сообщений: 45
10.06.2010, 19:43     Односвязный, двусвязный список, стек, очередь #29
Цитата Сообщение от accept Посмотреть сообщение
C
1
2
3
4
struct node {
    int num;
    struct node *next;
};
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    struct node *list; /* указатель на первый узел списка */
    struct node n1, n2, n3, n4; /* это разные узлы */
    
    list = &n1;
    list->next = &n2;
    list->next->next = &n3;
    list->next->next->next = &n4;
    
    /* список готов, в нём четыре узла */
 
    list->num = 1;
    list->next->num = 2;
    list->next->next->num = 3;
    list->next->next->next->num = 4;
 
    /* занесли значения в каждый узел */
 
    /* дальше список можно выводить, считать количество элементов */
 
    list->next->next->next->next = NULL; /* конец списка */
    
    /* пятого узла нет, он равен NULL */
Ето мне ?
hexvoltt
18 / 18 / 2
Регистрация: 17.08.2010
Сообщений: 54
17.08.2010, 15:24     Односвязный, двусвязный список, стек, очередь #30
Случайно наткнулся на эту тему, рыская в инете по поводу списков на C++
> Баггов вы не найдёте
C++
1
2
                                tail = NULL;
                                delete tail;
Это что за ересь??
Недостатки кода: следовало бы сделать полноценную инкапсуляцию в классы, а сами классы шаблонными.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
18.08.2010, 00:47     Односвязный, двусвязный список, стек, очередь #31
мда...
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
18.08.2010, 23:24     Односвязный, двусвязный список, стек, очередь #32
Цитата Сообщение от CheshireCat Посмотреть сообщение
На самом деле, что произойдет при неудачной попытке выделить память - довольно-таки неоднозначная ситуация. Более того, даже на одном и том же компиляторе это зависит от кода!! Я немного поэкспериментировал с доступными мне компиляторами, и вот какие результаты получились:
Тест 1
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
#include <iostream>
#include <exception>
#include <stdexcept>
 
using namespace std;
 
int main()
{
    try
    {
        while(true)
        {
            char* p = new char[0x40000000];
            if (p == NULL)
            {
                cout << "NULL pointer" << endl;
                break;
            }
        }
    }
    catch(bad_alloc& a)
    {
        cout << "bad_alloc exception" << endl;
    }
    return 0;
}
 
// GCC 3.4             bad_alloc exception
// GCC 4.4             bad_alloc exception
// MSVC++ 5 (97)       NULL pointer
// MSVC++ 6            NULL pointer
// MSVC++ 7.0          bad_alloc exception
// MSVC++ 7.1 (2003)   bad_alloc exception
// MSVC++ 2005         bad_alloc exception
// Borland C++ 5.5     bad_alloc exception
Тест 2
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
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    try
    {
        while(true)
        {
            char* p = new char[0x40000000];
            if (p == NULL)
            {
                printf("NULL pointer\n");
                break;
            }
        }
    }
    catch(...)
    {
        printf("bad_alloc exception\n");
    }
    return 0;
}
 
// GCC 3.4             bad_alloc exception
// GCC 4.4             bad_alloc exception
// MSVC++ 5 (97)       NULL pointer
// MSVC++ 6            NULL pointer
// MSVC++ 7.0          NULL pointer
// MSVC++ 7.1 (2003)   NULL pointer
// MSVC++ 2005         bad_alloc exception
// Borland C++ 5.5     bad_alloc exception
Вот это и привносит любопытную проблему - как написать переносимый код?....

Добавлено через 32 минуты 40 секунд
PS: юзать new(std::nothrow) не предлагать - бо имеется большой объем legacy code... и переписывать его - не вариант.
М-да. Самый злостный нарушитель - MSVC++. Но она вроде бы уже исправилась. На MSVC++ 2008 оба теста работают согласно стандарту.
moonlawn
Сообщений: n/a
10.11.2010, 16:40     Односвязный, двусвязный список, стек, очередь #33
Vasiliusis,
Здравствуй , РАЗДАЮ. Односвязный, двусвязный список, стек, очередь чертовски помогли.
Спасибо!
Хотелось бы ещё модефицировать список или стек в бинарное дерево. пытался , с укзателями путаница... впринципе проще создать новое, но уж очень хотелось попытаться .увы! если выложите Б-Дерево (обход , добавление элем, удаление эл из узлов) будо беконнечно бллагодарен!
White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
07.12.2010, 21:23     Односвязный, двусвязный список, стек, очередь #34
C++
1
 Node* ptrLast = NULL;
а что означает этот указатель в очереди , там где двусвязный список?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2013, 13:12     Односвязный, двусвязный список, стек, очередь
Еще ссылки по теме:
C++ Односвязный (двусвязный) список - поиск людей по минимальному и максимальному возрасту
C++ Реализовать иерархию классов, включающую в себя односвязный и двусвязный список
C++ Стек (односвязный список)
Очередь через односвязный список C++
Односвязный список (очередь). Удаление узла C++

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

Или воспользуйтесь поиском по форуму:
as1224
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 8
28.01.2013, 13:12     Односвязный, двусвязный список, стек, очередь #35
Очень нужна ваша помощь

переделал немного односвязный список
вот код

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
      #include <iostream>
#include <windows.h>
using namespace std;
 
class Node
{
public:
    int number;
    Node* next;
};
 
 
 
void main()
{   setlocale (LC_ALL,"");
    Node* head = NULL;
    Node* lastPtr = NULL;
    short action = -1;
    while (1)
    {
        cout<<"1. Добавить Элемент\n";
        cout<<"2. Просмотр Списка\n";
        cout<<"3. Поиск Элемента\n";
        cout<<"4. Удалить Элемент\n";
        cout<<"5. Удалить Элемент По Выбору\n";
        cout<<"0. Выход\n\n";
        cout<<"Ваш Выбор: ";
        cin>>action;
        if (action == 0)
        {
            system("CLS");
            break;
        }
 
        if (action == 1)
        {
            system("CLS");
            Node* ptr = new Node;
            int numb = -1;
            cout<<"Введите Число: ";
            cin>>numb;
            ptr->number = numb;
            ptr->next = NULL;
            if (head == 0)
            {
                head = ptr;
                lastPtr = ptr;
                system("CLS");
                continue;
            }
            lastPtr->next = ptr;
            lastPtr = ptr;
            system("CLS");
            continue;
        }
 
        if (action == 2)
        {
            Node* ptr = NULL;
            system("CLS");
            if (head == NULL)
            {
                cout<<"\t!!! СПИСОК ПУСТ !!!\n\n";
                system("PAUSE");
                system("CLS");
                continue;
            }
            cout<<"* * * * * СПИСОК * * * * *\n\n";
            ptr = head;
            while (1)
            {
                cout<<ptr->number<<" ";
                if (ptr->next == 0)
                    break;
                ptr = ptr->next;
            }
            cout<<"\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 3)
        {
            Node* ptr = NULL;
            int key = -1;
            system("CLS");
            if (head == NULL)
            {
                cout<<"\t!!! СПИСОК ПУСТ !!!\n\n";
                system("PAUSE");
                system("CLS");
                continue;
            }
            cout<<"Введите Элемент Для Поиска: ";
            cin>>key;
            ptr = head;
            while (1)
            {
                if (key == ptr->number)
                {
                    cout<<"\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n";
                    break;
                }
                if (ptr->next == NULL)
                {
                    cout<<"\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n";
                    break;
                }
                ptr = ptr->next;
            }
            system("PAUSE");
            system("CLS");
            continue;
        }
 
        if (action == 4)
        {
            system("CLS");
            Node* ptrDelete = NULL;         
            if (head == NULL)
            {
                cout<<"\t!!! СПИСОК ПУСТ !!!\n\n";
                system("PAUSE");
                system("CLS");
                continue;
            }
            if (head->next == NULL)
            {
                head = NULL;
                delete head;
                continue;
            }
            ptrDelete = head;
            head = ptrDelete->next;
            delete ptrDelete;
            continue;
        }
 
        if (action == 5)
        {
            system("CLS");
            Node* ptrPrev = NULL;
            Node* ptrDelete = NULL;
            int key = -1;
            if (head == NULL)
            {
                cout<<"\t!!! СПИСОК ПУСТ !!!\n\n";
                system("PAUSE");
                system("CLS");
                continue;
            }
            cout<<"Введите Элемент Для Удаления: ";
            cin>>key;
            ptrDelete = head;
            if (ptrDelete->number == key)
            {
                head = ptrDelete->next;
                delete ptrDelete;
                system("CLS");
                continue;
            }
            while (1)
            {
                if (key == ptrDelete->number)
                {
                    ptrPrev->next = ptrDelete->next;
                    delete ptrDelete;
                    break;
                }
                if (ptrDelete->next == 0)
                {
                    cout<<"\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n";
                    system("PAUSE");
                    break;
                }
                ptrPrev = ptrDelete;
                ptrDelete = ptrDelete->next;
            }
            system("CLS");
            continue;
        }
 
        if (action > 5)
        {
            system("CLS");
            cout<<"\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n";
            system("PAUSE");
            system("CLS");
            continue;
        }
    }   
}
но вот такая проблема не работает ввод после удаления т.е.
например я вожу список 1 2 3 4 5 потом удаляю например 5 и снова пытаюсь ввести т.е. добавить элемент но выбивает ошибка.

Заранее благодарен за пояснение.
Yandex
Объявления
28.01.2013, 13:12     Односвязный, двусвязный список, стек, очередь
Закрытая тема Создать тему
Опции темы

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