Неправильный результат в реализации HashTable - PullRequest
Новая
       10

Неправильный результат в реализации HashTable

0 голосов
/ 28 декабря 2011

Я запрограммировал приведенный ниже код для реализации алгоритма HashTable by Chains, но когда я использую его в функции main, результат будет неправильным: 

#define _SIZE 1000

class HashEntry
{
    public: int Tel;
            string Name;

    public: HashEntry(){}
    public: HashEntry(int Tel, string Name)
    {
        this->Tel = Tel;
        this->Name = Name;
    }
};

class Link {
    public:
    HashEntry data;
        Link *next;

    public:
        Link() : next(NULL){ }

};

void Insert (Link *head, HashEntry data)
{
    Link *t= new Link;
    t->data=data;

    if(head==NULL)
    {
        head = new Link;
        head->next = NULL;
        head->data = data;
        return;
    }

    Link *head2= head;
    while(head2->next!=NULL)
    {     
        if( head2->data.Name == data.Name)
            return;
        head2=head2->next;
    }

    head2->next=t;
}

class  HashTable {
    public:
    Link **a;
    public:
    HashTable()
        {
            a = new Link *[_SIZE];
            for (int i=0; i<_SIZE; i++)
                a[i]=NULL;
        }

    public:
        int HashFonction (string key)
        {
            int res=0;
            for ( int i = 0; i < key.length(); i ++ )
            {
                char ch = key.at(i);
                if( i%2==0)
                    res+=(int)ch;
                else 
                    res-=(int)ch;
            }

            return (int)fabsf((float)res) % _SIZE;
        }

        void HashInsert (string key, int val){
            int index= HashFonction(key);
            HashEntry s(val, key);
            Insert(a[index],s);
        }    

        int HashSearch(string key)
        {
            int inx=HashFonction(key);
            Link *head=a[inx];

            if(head==NULL){
                return -1;
            }

            while(head!=NULL){
                if(head->data.Name==key)
                    return head->data.Tel;

                head=head->next;
            }

            return -1;
        }
};

После реализации этого класса я запрограммировал следующие коды, но результат поиска равен -1: - / 

HashTable ht;
ht.HashInsert("Hossein", 849348);
ht.HashInsert("Ali", 94343);
ht.HashInsert("Fatemeh", 940343);

cout << ht.HashSearch("Ali") << endl; // output = -1 :-/

Может кто-нибудь объяснить, что не так?

Спасибо за внимание

Ответы [ 2 ]

2 голосов
/ 28 декабря 2011

Ваша проблема 

void Insert (Link * head, HashEntry data)

Измените его на 

void Insert (Link *& head, HashEntry data)

В основном указатели передаются по значению

То, что вы пытаетесь сделать, равно 

void Bar( Link* input )
{   
   input = new Link();
}

Link* foo = 0;
Bar( foo );

После возвращения Bar foo будет по-прежнему 0 .Когда вы передаете указатель по значению, вы можете изменить содержимое того, на что он указывает, а не сам указатель.Чтобы все вышеперечисленное работало должным образом, вы можете

ALTERNATIVE 1

Передать по указателю по ссылке 

void Bar( Link*& input )
{   
   input = new Link();
}

Link* foo = 0;
Bar( foo );

ALTERNATIVE 2

Передать указатель на указатель 

void Bar( Link** input )
{   
   *input = new Link();
}

Link* foo = 0;
Bar( &foo );
1 голос
/ 28 декабря 2011

Вы передаете головку указателя в функцию Insert по значению, поэтому массив "a" в хэш-таблице класса не изменяется. Переход по ссылке решает проблему: 

void Insert (Link *&head, HashEntry data)
...