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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.61
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
#1

Поиск элемента в списке. - C++

08.10.2011, 00:48. Просмотров 6128. Ответов 14
Метки нет (Все метки)

Есть список, который содержит объекты класа type. Мне нужно найти в этом списке объект, который будет отвечать некоторым условиям. Пробую реализовать это с помощью рекурсии
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
{
    if ((*itr))
    {
        if <условие>
            return itr;
 
        if (itr != List.end())
        {
            ++itr;
            GetUnit(List, itr);
        }
    }
    return NULL;
}
Задача примерно такая - есть 10 объектов. Мне нужно достать 5 объектов, которые будут отвечать условиям. Причем после возвращения объект перестанет отвечать условию. Но не работает. Проблема в том, что ++itr не срабатывает. И получается вечная рекурсия. Как это исправить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2011, 00:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск элемента в списке. (C++):

Поиск элемента в списке - C++
Добрый день! У меня есть набор некоторых значений, например такой: (&quot;0&quot;, &quot;1&quot;,&quot;6&quot;,&quot;7&quot;,&quot;8&quot;,&quot;9&quot;,&quot;10&quot;,&quot;11&quot;....) Мне же нежно среди...

Поиск элемента в списке - C++
Добавьте в класс списков метод int Search(T x) для поиска зна- чения x в списке. Метод должен возвращать номер узла со значением x или...

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

Поиск элемента в двусвязном списке - C++
Элемент двусвязного списка точка(x,y). Нужно написать функцию для нахождения максимально удаленной точки от центра координат. ...

Реализовать поиск максимального элемента в двусвязном списке - C++
Помогите пожалуйста доделать код. Вместо блока удаление нужен осуществить поиск максимального элемента :help: #include &quot;stdafx.h&quot; ...

Вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента - C++
Добавить в класс &quot;Односвязный список&quot; следующие функции: вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск...

14
Jupiter
Каратель
Эксперт С++
6561 / 3982 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
08.10.2011, 00:57 #2
Цитата Сообщение от ZaxarPal Посмотреть сообщение
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
Цитата Сообщение от ZaxarPal Посмотреть сообщение
return NULL;
'это явно не вяжется
0
rescr1pt
33 / 34 / 1
Регистрация: 03.10.2011
Сообщений: 61
08.10.2011, 00:59 #3

Не по теме:

ZaxarPal, какие люди, в Голливуде.



Добавлено через 1 минуту
Цитата Сообщение от Jupiter Посмотреть сообщение
'это явно не вяжется
А то, смысл "Get"у возвращать NULL?
0
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 08:40  [ТС] #4
rescr1pt, привет
Jupiter, а если все объекты списка не подходят под условие? Тогда ловить краш?
Есть другой способ решить проблему с поиском в списке. Каждый раз проходить с начала списка форчиком и возвращать первый же найденный элемент. Но мне все же интересно, почему не срабатывает вариант с передачей в параметры функции списка и итератора. Ведь если, например, в списке будет миллиард элементов и найти нужно 5 миллионов проход с начала списка будет не самым удачным решением...

P.S. Почему всегда найдется человек, который вместо того, что бы помочь с решением конкретно заданного вопроса, начинает рассказывать что у примера нету смысла, оно не вяжется и вообще глупо? Вопрос ведь был задан как решить проблему с поиском, а не есть ли смысл в отрывке кода. Решили по умничать?
0
Jupiter
Каратель
Эксперт С++
6561 / 3982 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
08.10.2011, 12:28 #5
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Jupiter, а если все объекты списка не подходят под условие? Тогда ловить краш?
возвращать end()

Цитата Сообщение от ZaxarPal Посмотреть сообщение
Почему всегда найдется человек, который вместо того, что бы помочь с решением конкретно заданного вопроса, начинает рассказывать что у примера нету смысла, оно не вяжется и вообще глупо? Вопрос ведь был задан как решить проблему с поиском, а не есть ли смысл в отрывке кода. Решили по умничать?
в вашем поиске не вижу условия поиска, чем помочь? я так понимаю вы пришили сюда за готовым кодом, так его не будет потому что
Цитата Сообщение от ZaxarPal Посмотреть сообщение
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
{
if ((*itr))
{
if <условие>
return itr;
вы сами не знаете что вам надо
0
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 13:02  [ТС] #6
Jupiter, если бы не читали через строки, то все поняли бы. Я пришел не за готовым кодом, для этого я и не писал задачу. В первом посте я написал:
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Мне нужно найти в этом списке объект, который будет отвечать некоторым условиям.
Вот в
Цитата Сообщение от Jupiter Посмотреть сообщение
if <условие>
как раз и проверяется, отвечает ли объект условию.
Цитата Сообщение от Jupiter Посмотреть сообщение
возвращать end()
Лолчто? Который вернет последний элемент, который в свою очередь не отвечает условиям = равно краш.
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Проблема в том, что ++itr не срабатывает. И получается вечная рекурсия.
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Но мне все же интересно, почему не срабатывает вариант с передачей в параметры функции списка и итератора.
Был задан вопрос. Причем тут вообще готовый код? Кэп намекает, что если бы был нужен готовый код, то было бы лишь условие задачи, как в соседних темах...

P.S. А вы вообще читать умеете? Ибо начинают закрадываться сомнения.
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
08.10.2011, 14:19 #7
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Задача примерно такая - есть 10 объектов. Мне нужно достать 5 объектов, которые будут отвечать условиям
все уже написали за тебя: http://en.cppreference.com/w/cpp/container/list/remove, http://en.cppreference.com/w/cpp/algorithm/remove_copy
тред не читал
Цитата Сообщение от ZaxarPal Посмотреть сообщение
P.S. А вы вообще читать умеете? Ибо начинают закрадываться сомнения.
давай поспокойнее, а?
0
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 14:34  [ТС] #8
Цитата Сообщение от Nameless One Посмотреть сообщение
все уже написали за тебя
Какое отношение имеет метод remove и remove_if к данному вопросу? Метод remove_copy remove_copy_if тоже не очень подходит. За один раз мне нужно достать один элемент. Первый попавшийся, который удовлетворяет условиям. Объектов в списке может быть 10, может быть и 20. Так же не известно количество объектов, которые удовлетворяют условиям. Проблему с поиском элемента я решил. Мне интересно только почему в параметр функции передается один и тот же итератор, судя по всему.
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
08.10.2011, 14:49 #9
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Лолчто? Который вернет последний элемент, который в свою очередь не отвечает условиям = равно краш
метод end(), несмотря на название, возвращает не последний элемент коллекции. И возвращать end() - вполне нормальное решение.

Цитата Сообщение от ZaxarPal Посмотреть сообщение
Какое отношение имеет метод remove и remove_if к данному вопросу?
прямое. С помощью метода remove_if ты можешь получить список, который содержит только те элементы, которые удовлетворяют условию.
0
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 15:11  [ТС] #10
Цитата Сообщение от Nameless One Посмотреть сообщение
метод end(), несмотря на название, возвращает не последний элемент коллекции. И возвращать end() - вполне нормальное решение.
А что тогда возвращает?
Цитата Сообщение от Nameless One Посмотреть сообщение
С помощью метода remove_if ты можешь получить список, который содержит только те элементы, которые удовлетворяют условию.
Метод ведь удалит элементы, которые не проходят по условию? Но этого делать нельзя.
Даже если и получить список этих элементов, разве это будет рациональное решение данного вопроса? А если элементов очень много. Причем первый элемент будет отвечать требованиям, а последний нет. В таком случае, если использовать методот remove_if, будут обработаны все элементы списка, вместо того, что бы проверить только первый. Или как тогда?
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
08.10.2011, 15:27 #11
Цитата Сообщение от ZaxarPal Посмотреть сообщение
А что тогда возвращает?
http://cplusplus.com/reference/stl/list/end/. Возвращает итератор, указывающий на несуществующий элемент, "расположенный" за последним элементом списка
Цитата Сообщение от ZaxarPal Посмотреть сообщение
разве это будет рациональное решение данного вопроса? А если элементов очень много
у тебя при каждом вызове твоей функции происходит копирование всего списка, так что получится гораздо эффективнее.
1
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 15:33  [ТС] #12
Nameless One, а если в цикле проверять каждый элемент на выполнение условия и возвращать верный? Удалять элементы списка нельзя.
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
08.10.2011, 15:42 #13
Цитата Сообщение от ZaxarPal Посмотреть сообщение
а если в цикле проверять каждый элемент на выполнение условия и возвращать верный? Удалять элементы списка нельзя.
тоже можно

Вот пример класса, который возвращает очередной элемент последовательности, удовлетворяющий предикату, при каждом вызове оператора ():
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
#include <iostream>
#include <functional>
#include <list>
 
template <class T, class Pred, class Cont = std::list<T> >
class filter
{
public:
 
    typedef typename Cont::iterator iterator;
    
    filter(iterator, iterator, Pred);
 
    iterator operator () ();
 
    iterator end();
        
private:
    iterator it;
    iterator last;
    Pred pred;
};
 
template <class T, class Pred, class Cont>
filter<T, Pred, Cont>::filter(iterator f, iterator l, Pred p)
    : it(f), last(l), pred(p)
{
}
 
template <class T, class Pred, class Cont>
typename filter<T, Pred, Cont>::iterator filter<T, Pred, Cont>::end()
{
    return last;
}
 
template <class T, class Pred, class Cont>
typename filter<T, Pred, Cont>::iterator filter<T, Pred, Cont>::operator () ()
{
    iterator result = it;
    
    if(it != last)
    {
    while((result = it) != last)
    {
        if(pred(*it))
        {
        ++it;
        break;
        }
        
        ++it;
    }
    }
 
    return result;
}
 
bool even(int i)
{
    return !(i & 1);
}
 
typedef bool (*PRED)(int);
 
int main()
{
    std::list<int> l = {1,2,3,4,5,6,7,8,9,10};
 
    filter<int, PRED> evens(l.begin(), l.end(), even);
 
    filter<int, PRED>::iterator it;
 
    while((it = evens()) != evens.end())
    std::cout << *it << std::endl;
    
    
    return 0;
}
Чтобы не указывать тип предиката при объявлении объекта-фильтра, можно сделать оператор шаблоном, принимающим предикат в качестве параметра
1
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
08.10.2011, 23:11 #14
Задание интересно, единственное, что я не мог понять- что должна возвращать рекурсивная функция,
объект или указатель на объект, решил возвернуть объект

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
#include <iostream>
#include <string>
#include <list>
using namespace std;
 
 
//Это вот будет описание типа
class type {
 public:
  type (int);
  ~type () {};
 
 int f () {return x;};
 
 private:
  int  x;
};
 
type::type (int nomer) {
 x= nomer;
};
 
 
//Это вот прототип функции
type GetUnit(list<type*> , list<type*>::iterator );
 
int main() {
 
 //Кропаем список из 10-ти указателей.
 type** p= new type* [10];
 
 
 //Теперь каждый указатель проинициализируем конкретным объектом типа type
 for (int i= 0; i< 10; i++) {
  p[i]= new type (i);
 }
 
 //собсно список
 list<type*> List (p, p + 10);
 
 list<type*>::iterator itr= List.begin();
 
 //Вызываем функцию, которая вернёт нам переменную типа type
 type rez= GetUnit (List, List.begin());
 
 
 printf ("%d\n", rez.f());
 
 getchar ();
 return 0;
}
 
 
type GetUnit(std::list<type*> List, list<type*>::iterator itr) {
 
    if (itr!=List.end()) {
     printf ("(**itr).f()%3= %d\n", (**itr).f()%3);
     //Так, а здесь проверяем условие. Я придумал условие такое:
     //член x обхекта при делении по модулю на 3 должен давать 2
     if (((**itr).f()%3)== 2)
      return **itr;
     else
      return GetUnit (List, ++itr);
    }
    return type (-1);
}
1
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 23:43  [ТС] #15
kravam, да, абсолютно верно поняли задачу Большое спасибо!
0
08.10.2011, 23:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 23:43
Привет! Вот еще темы с ответами:

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

Удаление элемента в списке - C++
Необходимо реализовать метод удаления элемента из списка не после определённого элемента (как сделано в коде), а по индексу этого элемента ...

Удаление элемента в списке - C++
Описать функцию, которая удаляет из списка все вхождения элемента Е, значение которого введено с клавиатуры. это само задание. ...

Ошибка в удалении элемента в списке - C++
Собственно не получается последняя функция &quot;delete_e&quot;, задача удалить в списке след. элемент по номеру, если он отличен от предыдущего. Не...


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

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

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