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

Линейный поиск в массиве и списке - C++

Восстановить пароль Регистрация
 
whhandrey
0 / 0 / 0
Регистрация: 11.09.2013
Сообщений: 14
26.09.2013, 17:49     Линейный поиск в массиве и списке #1
Добрый день, дорогие форумчане!
Имеется программа, которая должна выполнять линейный поиск по ключу в массиве и списке, но функция поиска LinearSearch должна быть шаблонной.
Функцию саму написал, с массивом работает на ура, но в самом списке я не знаю как перегрузить операторы, что бы она работала со списком. Перегрузить нужно оператор ==, ибо компилятор ругается на него и оператор индексации (иначе как обращаться к элементу списка)

Наработки:

Сама функция поиска
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class Type>
int LinearSearch(Type *object, int key, int N)
{
    int i;
    bool a=false;
    for(i=0; i<N; i++)
    {
        if(object[i] == key)
        {
            a=true;
            break;
        }
    }
    if(a==true)
        return i;
    else
        return -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
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
class List
{
private:
    Node *head;
    Node *current;
    Node *tail;
    int N;
public:
    List()
    {
        head = new Node;
        current = new Node;
        tail = new Node;
        head->left=0;
        tail->right=0;
        head=tail;
        current=0;
    }
    ~List(){}
    void SetOnHead() {current = head;}
    void SetOnTail() {current = tail;}
    void SetNext() {current = current->right;}
    void SetPrev() {current = current->left;}
    int GetValue() { return current->value;}
    void InputList(int N)
    {
        this->N = N;
        int i=0;
        Node *q = new Node;
        q->value=i*2;
        q->left=0;
        q->right=0;
        head = q;
        current=head;
        for(i=1; i<N; i++)
        {
            Node *n = new Node;
            n->value = i*2;
            n->right = 0;
            n->left=current;
            current->right = n;
            tail=n;
            current=n;
        }
    }
    void ShowList()
    {
        current = head;
        while(current->right!=0)
        {
            std::cout<<current->value<<" ";
            current=current->right;
        }
        std::cout<<std::endl;
    }
        // вот тут фигня какая-то..
    int operator [](int index)
    {
        current = head;
        for(int i=0; i<index; i++)
        {
            current=current->right;
        }
        return current->value;
    }
    friend std::ostream& operator<<(std::ostream& os, List const& ls)
    {
        return os<<ls.current->value;
    }
    friend bool operator ==(const List &left, const int &right)
    {
        if(left.current->value==right)
            return true;
        else return false;
    }
};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Cynacyn
 Аватар для Cynacyn
33 / 33 / 0
Регистрация: 02.05.2013
Сообщений: 109
26.09.2013, 18:31     Линейный поиск в массиве и списке #2
попробуйте описать функцию поиска так, чтобы она была похоже на алгоритмы STL, тогда Ваша функция будет максимально гибкой
C++
1
2
typedef<class T>
T* LinearSearch(T* begin, T* end, T key); // если не находит ничего, то возвразащает end; end - это не последний элемент последовательности, а следующий за ним
в Вашем классе лист нужно будет реализовать два метода .begin(), который бы возвращал указатель на головной узел, и .end() который бы возвращал указатель на узел следующий за последним (это обусловлено понятием полуоткрытой [begin:end) последовательности в STL), что то типа:
C++
1
2
3
4
Node* end() {
Node* p = tail; 
p++;
return p; }
пример вызова для вашего класса list
C++
1
2
3
4
List l1;
// заполняем список
some_type key; 
Node* result =  LinearSearch(l1.begin(),l1.end(),key)
на всякий случай скажу что должны быть определены операторы сравнения для Node
пример вызова для std::vector<int> v;
C++
1
int* result = LinearSearch(v.begin(),v.end(),key)
для массива double d_arr[20];
C++
1
double* result = LinearSearch(d_arr,d_arr+20,key)
whhandrey
0 / 0 / 0
Регистрация: 11.09.2013
Сообщений: 14
26.09.2013, 22:03  [ТС]     Линейный поиск в массиве и списке #3
Спасибо за идею, я фактически ее воплотил, но остался вопрос - как перегрузить ++.
Как я понял, его перегружать нужно в классе Node. Пошарился в нете, перегружал 4-мя разными вариантами, нифига не помогло(проверял через дебаггер).
Остальные операторы работают нормально..

Добавлено через 1 час 0 минут
Возвращать нужно позицию элемента.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LinearSearch(T* begin, T* end, T key)
{
    //bool a=false;
    T* it;
    int i=0;
    for(it=begin; it!=end; it++)  // вот тут. как перегрузить этот оператор?
    {
        if(*it == key)
        {
            return i;
        }
        i++;
    }
    return -1;
}
Cynacyn
 Аватар для Cynacyn
33 / 33 / 0
Регистрация: 02.05.2013
Сообщений: 109
27.09.2013, 11:01     Линейный поиск в массиве и списке #4
Цитата Сообщение от whhandrey Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int LinearSearch(T* begin, T* end, T key)
{
    //bool a=false;
    T* it;
    int i=0;
    for(it=begin; it!=end; it++)  // вот тут. как перегрузить этот оператор?
    {
        if(*it == key)
        {
            return i;
        }
        i++;
    }
    return -1;
}
Для указателей уже определен этот оператор. Олсо гляньте пункт 4. Операции с указателями

Ваш код работает и компилируется у меня:
C++
1
2
3
4
5
6
7
    vector<int> v;
    cin>>v; // перегружен
    int key = 20;
    int pos = LinearSearch(&v[0], &v[0]+v.size(),key);
 
    if(pos!=-1) cout << "Index of " << key << " == " << pos << endl;
        else cout << key << " not found" << endl;
При описании примера для работы со стандартным вектором, я ошибся.
Если vector<some_class> v; то v.begin() ( как и v.end()) не является указателем на some_class, а имеет тип vector<some_class>::iterator.
Для того чтобы Ваша функция работала со контейнерами STL (vector, list, ect), нужно определить её по другому:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template<class Iter>
int LinearSearch(Iter begin, Iter end, Iter key)
{
    int i=0;
    for(Iter it=begin; it!=end; it++) 
    {
        if(*it == *key) {
            return i;
        }
        i++;
    }
    return -1;
}
Для итераторов STL контейнеров как минимум перегружены операции инкремента и разыменования.
Теперь функцию можно использовать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
    vector<int> v;
    v.push_back(555); 
    cin>>v;
    vector<int>::iterator key = v.begin();
    int pos = LinearSearch(v.begin()+1, v.end(), key); // ищем второе вхождение 555
    if(pos!=-1) cout << "Index of second entry of " << *key << " == " << pos << endl;
    else cout << "There is no second entry of " << *key << endl;
 
    double ar[5] = { 100.1, 200.2, 300.3, 400.4, 500.5 };
    double* key2 = new double(300.3);
    pos=LinearSearch(ar, ar+5, key2);
    cout << "Index of " << *key2 << " == " << pos << endl;
Добавлено через 1 час 18 минут
или так
C++
1
2
template<class Iterator, class value_type>
int search(Iterator first, Iterator last, const value_type& val)
Yandex
Объявления
27.09.2013, 11:01     Линейный поиск в массиве и списке
Ответ Создать тему
Опции темы

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