С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Эллина888
1 / 1 / 0
Регистрация: 06.11.2016
Сообщений: 53
1

Поиск подпоследовательности в списке

10.05.2017, 15:17. Просмотров 296. Ответов 3
Метки нет (Все метки)

Подскажите, пожалуйста, как реализовать поиск подпоследовательности в односвязном списке (создан список, создаем еще один список и проверяем - содержится ли он в исходном)?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2017, 15:17
Ответы с готовыми решениями:

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

Поиск самой длинной неубывающей подпоследовательности
Формулировка задачи: Реализовать на языке C или C++ алгоритм поиска для...

Поиск максимальной по длине монотонно неубывающей подпоследовательности вещественных чисел
Напишите на языке C / C++ программу поиска максимальной по длине монотонно...

Поиск наибольшей общей подпоследовательности методом методом полного перебора
Здравствуйте! Помогите пожалуйста с этим адом :wall: Нужно решить задачу о...

Поиск в списке
#include <iostream> #include <fstream> #include <cstring> #include...

3
MrGluck
Модератор
Эксперт CЭксперт С++
8105 / 4957 / 1436
Регистрация: 29.11.2010
Сообщений: 13,451
10.05.2017, 15:25 2
Либо std::search (непрерывная последовательность), либо std::includes (с разрывами).
C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <iostream>
#include <forward_list>
 
int main()
{
    const std::forward_list<int> fl = {1, 2, 3, 4, 5}, sub = {2, 3, 5};
    std::cout << std::boolalpha << std::includes(fl.cbegin(), fl.cend(), sub.cbegin(), sub.cend());
}
Добавлено через 30 секунд
C++
1
2
3
4
5
6
7
8
9
#include <algorithm>
#include <iostream>
#include <forward_list>
 
int main()
{
    const std::forward_list<int> fl = {1, 2, 3, 4, 5}, sub = {2, 3, 5};
    std::cout << std::boolalpha << (std::search(fl.cbegin(), fl.cend(), sub.cbegin(), sub.cend()) != fl.cend());
}
1
Эллина888
1 / 1 / 0
Регистрация: 06.11.2016
Сообщений: 53
10.05.2017, 15:54  [ТС] 3
А если в таком варианте программы? у меня выскакивает исключение.
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
#include <iostream>
#include <stdlib.h>
using namespace std;
 
struct  Node
{
    int x;
    Node *Next;
    
};
 
class List
{
    Node *Head, *Tail, *Head2, *Tail2, *Head3; //Первый элемент и тот что последний
    int size; //Число элементов в списке
public:
    List() :Head(NULL), Tail(NULL), size(0) {}; //Инициализация элементов в ноль с помощью конструктора
    ~List(); //Деструктор для освобождения памяти
    void Add(int x); //Функция добавления элементов в списов
    void Add2(int x); //Функция добавления элементов в списов
    void Show(int size); //Функция отображения элементов списка
    void Show2(int size); //Функция отображения элементов списка
    void Show3(int size); //Функция отображения элементов списка
    int Count(); //Функция возвращающая число элементов в списке
    void Sort();
    void obedinenie();
    void poisk_el(int x,int size);
};
 
List::~List()
{
    while (size != 0) //Пока размерность списка не станет нулевой 
    {
        Node *temp = Head->Next;
        delete Head; //Освобождаем память от активного элемента
        Head = temp; //Смена адреса начала на адрес следующего элемента
        size--; //Один элемент освобожден. корректируем число элементов
    }
    while (size != 0) //Пока размерность списка не станет нулевой 
    {
        Node *temp = Head2->Next;
        delete Head2; //Освобождаем память от активного элемента
        Head2 = temp; //Смена адреса начала на адрес следующего элемента
        size--; //Один элемент освобожден. корректируем число элементов
    }
    while (size != 0) //Пока размерность списка не станет нулевой 
    {
        Node *temp = Head3->Next;
        delete Head3; //Освобождаем память от активного элемента
        Head3 = temp; //Смена адреса начала на адрес следующего элемента
        size--; //Один элемент освобожден. корректируем число элементов
    }
}
 
 
int List::Count()
{
    return size; //Возвращаем число элементов списка
}
 
void List::Add(int x)
{
    size++; //При каждом добавлении элемента увеличиваем число элементов в списке
    Node  *temp = new Node; //Выделение памяти для нового элемента списка
    temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка 
    temp->x = x; //Записываем в выделенную ячейку памяти значение x 
 
    if (Head != NULL) //В том случае если список не пустой
    {
        Tail->Next = temp; //Запись данных в следующее за последним элементом поле
        Tail = temp; //Последний активный элемент=только что созданный.
    }
    else Head = Tail = temp;//Если список пуст то создается первый элемент.
}
void List::Add2(int x)
{
    size++; //При каждом добавлении элемента увеличиваем число элементов в списке
    Node  *temp = new Node; //Выделение памяти для нового элемента списка
    temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка 
    temp->x = x; //Записываем в выделенную ячейку памяти значение x 
 
    if (Head2 != NULL) //В том случае если список не пустой
    {
        Tail2->Next = temp; //Запись данных в следующее за последним элементом поле
        Tail2 = temp; //Последний активный элемент=только что созданный.
    }
    else Head2 = Tail2 = temp;//Если список пуст то создается первый элемент.
}
 
void List::Show(int temp)
{
    Node *tempHead = Head; //Указываем на голову
 
    temp = size; //Временная переменная равная числу элементов в списке
    while (temp != 0) //Пока не выполнен признак прохода по всему списку
    {
        cout << tempHead->x << '\n' ; //Очередной элемент списка на экран 
        tempHead = tempHead->Next; //Указываем, что нужен следующий элемент
        temp--; //Один элемент считан, значит осталось на один меньше 
    }
}
void List::Show2(int temp)
{
    Node *tempHead = Head2; //Указываем на голову
 
    temp = size; //Временная переменная равная числу элементов в списке
    while (temp != 0) //Пока не выполнен признак прохода по всему списку
    {
        cout << tempHead->x << '\n'; //Очередной элемент списка на экран 
        tempHead = tempHead->Next; //Указываем, что нужен следующий элемент
        temp--; //Один элемент считан, значит осталось на один меньше 
    }
}
void List::Show3(int temp)
{
    Node *tempHead = Head3; //Указываем на голову
 
    temp = size; //Временная переменная равная числу элементов в списке
    while (temp != 0) //Пока не выполнен признак прохода по всему списку
    {
        cout << tempHead->x << '\n'; //Очередной элемент списка на экран 
        tempHead = tempHead->Next; //Указываем, что нужен следующий элемент
        temp--; //Один элемент считан, значит осталось на один меньше 
    }
}
 
//сортировка слиянием
Node* _merge_sort(Node* h, Node** e) {
    Node* p, *n, *t, *la, *lb;
    if ((h == NULL) || (h->Next == NULL))
        return h;
 
    la = lb = h;
    p = n = t = NULL; 
        for (Node* i = h; (i != NULL) && (i->Next != NULL); i = i->Next->Next) {
            lb = la;
            la = la->Next;
        }
    lb->Next = NULL;
 
    h = _merge_sort(h, e);
    la = _merge_sort(la, e);
 
    while ((h != NULL) || (la != NULL)) {
        if (la == NULL) {
            n = h;
            h = h->Next;
        }
        else if (h == NULL) {
            n = la;
            la = la->Next;
        }
        else if (h->x < la->x) {
            n = h;
            h = h->Next;
        }
        else {
            n = la;
            la = la->Next;
        }
 
        if (p == NULL)
            p = n;
        else
            t->Next = n;
        t = n;
    }
    *e = t;
    return p;
}
void List::Sort()
{
    if ((Tail == NULL) || (Tail->Next == NULL))
        return;
 
    Tail->Next = NULL;
    Head = _merge_sort(Head, &Tail);
    Tail->Next = Head;
 
    std::cout << "\n";
}
 
void List::obedinenie()//пусть будет по аналогии
{
    Node *q1 = Head; Node *q2 = Head2; Node *pnew;
    pnew = new Node;
    Head3 = pnew;
    pnew->x = q1->x;
    q1 = q1->Next;
    while ((q1 != NULL) && (q2 != NULL))
    {
        pnew->Next = new Node;
        pnew = pnew->Next;
        pnew->x = q2->x;
        pnew->Next = new Node;
        pnew = pnew->Next;
        pnew->x = q1->x;
        q1 = q1->Next;
        q2 = q2->Next;
    }
    while (q1 != NULL)
    {
        pnew->Next = new Node;
        pnew = pnew->Next;
        pnew->x = q1->x;
        q1 = q1->Next;
    }
    while (q2 != NULL)
    {
        pnew->Next = new Node;
        pnew = pnew->Next;
        pnew->x = q2->x;
        q2 = q2->Next;
    }
    pnew->Next = NULL;
}
 
 
void List::poisk_el(int x,int M)
{
    List lst;
    int el,z,N,k,i;
    Node *temp, *temp2;
    cout << "Enter the size of the list:";
    cin >> N;
    for (z = 0; z < N; z++)
    {
        cout << "Enter  elements of the list:";
        cin >> k;
        lst.Add2(k);
    }
 
 
 
    temp = Head;
    temp2 = Head2;
    while (temp && temp2)//пока есть значения
    {
        for (i = 0; i < M; i++) {
 
 
            for (z = 0; z < N; z++)
            {
                if (temp->x == k)
                {
                    cout << "This element exists in the list " << "\n";
                    break; // чтобы выйти из цикла при нахождении первого элемента
                }
                else
                {
                    temp = temp->Next;
                    temp2 = temp2->Next;
                }
 
            }
        }
            cout << "This element does not exist in the list " << "\n";
            break;
        }
 
 
    
}
 
 
void main()
{
    system("CLS");
    List lst;
    int z, N, k,M;
    cout << "Enter the size of the list:";
    cin >> N;
    for (z = 0; z < N; z++)
    {
        cout << "Enter  elements of the list:";
        cin >> k;
        lst.Add(k);
    }
 
    lst.Sort();
    
    lst.Show(lst.Count()); //Показываем список на экране.
    lst.poisk_el(k,N);
    cout << "Enter the size of the list:";
    cin >> M;
    for (z = 0; z < M; z++)
    {
        cout << "Enter  elements of the list:";
        cin >> k;
        lst.Add2(k);
    }
    lst.Show2(lst.Count());
    Node *Head3 = NULL;
    lst.obedinenie();
    lst.Show3(lst.Count());
    
 
 
        cout << endl;
        system("PAUSE");
    }
0
MrGluck
Модератор
Эксперт CЭксперт С++
8105 / 4957 / 1436
Регистрация: 29.11.2010
Сообщений: 13,451
10.05.2017, 16:00 4
Цитата Сообщение от Эллина888 Посмотреть сообщение
у меня выскакивает исключение.
К сожалению, 300 строк кода как-то не охота самостоятельно отлаживать. Попробуйте пройтись отладчиком, посмотреть какие у вас данные вызывают ексепшн. Скорее всего, вы нулевой указатель разыменовываете. Но это из разряда "мне духи говорят" .
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2017, 16:00

Поиск элемента в списке
Здравствуйте, нужно написать функцию, которая будет вы водить на экран позицию...

Поиск в лин. списке
Помогите сделать сам поиск..я уже замучился.. вот что у меня сейчас { ...

Осуществить поиск в списке
Здравствуйте,вот такая вот проблема у нас новый препод она первый год...


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

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

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