Как пройти через deque и найти элемент? - PullRequest
Новая
       19

Как пройти через deque и найти элемент?

0 голосов
/ 25 марта 2020

У меня есть два запроса, которые определены следующим образом: 

struct elem
{
    int key; elem* next;
}
*left = NULL, *right=NULL, *left2 = NULL, *right2 = NULL;

и функция pu sh и pop 

void push_front(int n, elem*&l, elem*&r)
{
    elem *p=left;
    left = new elem;
    left -> key=n;
    left -> next=p;
    if(right==NULL)
    {
        right = left;
    }
}

int pop_front(int &n, elem*&l, elem*&r)
{ 
    elem *p; 
if (left)  
{    
    n=left->key; 
    p=left;    
    left=left->next;
    if (left==NULL)
        right=NULL;    
    delete p;     
    return 1;
}   
else
    return 0;
}

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

void search(int x)
{
    elem *y=left;
    while(y->key!=x)
    {
    if(y==right)
    {
        cout<<x<<" wasn't found, adding to front."<<endl;
        push_front(x);
        return;
    }
    y=y->next;
    }
    cout<<x<<" was found"<<endl;
    return;

}

Любая помощь приветствуется. А также нет, я не могу использовать библиотеку deque или std :: find или что-то в этом роде.

Ответы [ 2 ]

0 голосов
/ 25 марта 2020

Как пройти deque ...

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

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

current = beginning_of_the_range;
last    = end_of_the_range;
for (; current != last; ++current) {
    // current points to current element here
}

struct elem
{
    int key; elem* next;
}

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

  • Сохранить указатель на текущий узел в итераторе. Давайте назовем это node.
  • . Направление итератора может быть реализовано как return node->key;
  • . Чтобы перейти к следующему элементу, выполните node = node->next;.
  • . проверьте, равен ли итератор, return node == other.node;.
  • Итератор, представляющий конец, может быть представлен как nullptr, или с использованием сторожевого узла.

... и найдите элемент?

После того, как вы реализовали обход, вы можете использовать линейный поиск.

0 голосов
/ 25 марта 2020

Для начала обе функции push_front и pop_front имеют опечатки. Внутри функций вместо идентификаторов left и right вы должны использовать идентификаторы параметров l и r. 

void push_front(int n, elem*&l, elem*&r)
                       ^^^^^^^^^^^^^^^^
{
    elem *p=left;
            ^^^^^
    //...

И вам не следует определять глобальные переменные left, right, left2, и правильно2. Функции не должны зависеть от глобальных переменных.

Функция, подобная поиску, должна делать только одно: сообщать, присутствует ли элемент в списке или нет.

Таким образом, функция должна быть определяется как 

bool search( const elem * &l, int x )
{
    const elem *current = l;

    while ( current != nullptr && current->key != x ) current = current->next;

    return current != nullptr;
}

На основе возвращаемого значения функции вы можете добавить значение в список или сделать что-то еще.

Если использовать вспомогательный список (который неэффективен) поскольку вы можете просматривать список только с помощью функций pop_front и push_front, функция может выглядеть следующим образом: 

bool search( elem * &l, elem * &r, int x )
{
    elem *l2 = nullptr, *r2 = nullptr;

    bool success = false;

    if ( l != nullptr )
    {
        do 
        {
            int key;

            pop_front( key, l, r );
            push_front( key, l2, r2 );

            success = key == x;
        } while ( !success && l != nullptr );
    }

    while ( l2 != nullptr )
    {
        pop_front( key, l2, r2 );
        push_front( key, l, r );
    }

    return success;
}

Вот демонстрационная программа. 

#include <iostream>

struct elem
{
    int key; 
    elem *next;
};

void push_front( int n, elem * &l, elem * &r )
{
    l = new elem { n, l };

    if ( r == nullptr ) r = l;
}

bool pop_front( int &n, elem * &l, elem * &r )
{ 
    bool success = l != nullptr;

    if ( success )
    {
        n = l->key;

        elem *tmp = l;

        l = l->next;

        if ( l == nullptr ) r = nullptr;

        delete tmp;
    }

    return success;
}   


bool search( elem * &l, elem * &r, int x )
{
    elem *l2 = nullptr, *r2 = nullptr;

    bool success = false;

    if ( l != nullptr )
    {
        do 
        {
            int key;

            pop_front( key, l, r );
            push_front( key, l2, r2 );

            success = key == x;
        } while ( !success && l != nullptr );
    }

    while ( l2 != nullptr )
    {
        pop_front( key, l2, r2 );
        push_front( key, l, r );
    }

    return success;
}

int main() 
{
    elem *left = nullptr, *right = nullptr;

    const int N = 10;

    for ( int i = N; i != 0; --i )
    {
        push_front( i, left, right );
    }

    if ( !search( left, right, 0 ) )
    {
        push_front( 0, left, right );
    }

    while ( left != nullptr )
    {
        int key;

        pop_front( key, left, right );

        std::cout << key << ' ';
    }

    std::cout << '\n';

    return 0;
}

Ее вывод 

0 1 2 3 4 5 6 7 8 9 10

То есть, если 0 не найден в сформированном списке, он выдвигается вперед в списке. Вывод программы показывает результат.

...