Блог

Я попытался создать хэш-карту, хранящую его входные данные в виде узлов связанного списка, используя разделенную цепочку. Первая функция отображения выдает желаемый результат, но следующая сбрасывает весь массив в пустой nullptr . Я использовал один и тот же объект класса, поэтому не должен ли он каждый раз давать один и тот же результат? Было ли это из-за деструктора каким-то образом? Я подумал, что это может быть потому, что я вставил новый элемент, поэтому я удалил его, и то же самое все еще сохраняется. Я подозреваю только функцию display(), но, пожалуйста, укажите, если проблема возникает откуда-то еще.

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

 #include <iostream>
#include <string>
#include "C:Usersadminsourcereposhash-library-mastersha3.cpp"
using namespace std;

const int TABLE_SIZE = 11;

struct HashNode
{
    string key;
    string value;
    HashNode* next;
};

class HashMap {
private:
    HashNode **table;

public:
    //each element of table will be a root pointer to their respective chain
    HashMap() {
        table = new HashNode*[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i  )
        {
            table[i] = nullptr;
        }   
    }

    //hashing algorithm using SHA3 (courtesy of Stephan Brumme)
    string hashFunc(string input)
    {
        string key;
        SHA3 sha3;

        key = sha3(input);

        return key;
    }

    //insert new node
    void insert(string key, string value)
    {
        //using hashing function to calculate hash index from string variable key
        int hash = 0;
        for (int a = 0; a < key.length();   a)
            hash  = key[a];
        hash = hash % TABLE_SIZE;

        //create new node to store data
        HashNode* newNode = new HashNode;
        newNode->value = value;
        newNode->key = key;
        newNode->next = nullptr;

        //check and insert new node to front of line
        if (table[hash] == nullptr)
            table[hash] = newNode;
        else
        {
            newNode->next = table[hash]->next;
            table[hash]->next = newNode;
        }
    }

    void display()
    {
        for (int i = 0; i < TABLE_SIZE;   i)
        {
            if (table[i] == nullptr)
                cout << i << " NULL" << endl;
            else
            {
                while (table[i] != nullptr)
                {
                    cout << i << " " << table[i]->value << "; ";
                    table[i] = table[i]->next;
                    if (table[i] == nullptr)
                        cout << "(end of chain)" << endl;
                }
            }
        }   
    }

    ~HashMap() {
        for (int i = 0; i < TABLE_SIZE; i  )
            if (table[i] != NULL)
                delete table[i];
        delete[] table;
    }
};
 

Драйвер

 #include <iostream>
#include <string>
#include "hashMap.h"
using namespace std;

int main()
{
    HashMap obj;
    
    //test insert
    obj.insert("5", "3100 Main St, Houston TX ");
    obj.insert("5", "2200 Hayes Rd, Austin TX");
    obj.insert("226", "1775 West Airport St, San Antonio TX");
    obj.insert("273", "3322 Walnut Bend, Houston TX");
    obj.insert("491", "5778 Alabama, Waco TX");
    obj.insert("94", "3333 New St, Paris TX");

    obj.display(); //resolved

    cout << endl << endl;

    //testing new hashing algorithm
    string input, key;
    cout << "Please enter any new address you want to store: ";
    cin >> input;

    key = obj.hashFunc(input); //create hash key
    obj.insert(key, input);
    obj.display(); //resets the array somehow

    return 0;
}
 

Вывод

 0 1775 West Airport St, San Antonio TX; (end of chain)
1 NULL
2 3322 Walnut Bend, Houston TX; (end of chain)
3 NULL
4 5778 Alabama, Waco TX; (end of chain)
5 NULL
6 NULL
7 NULL
8 NULL
9 3100 Main St, Houston TX ; 9 2200 Hayes Rd, Austin TX; (end of chain)
10 3333 New St, Paris TX; (end of chain)

//where display() resets
Please enter any new address you want to store: ewrewrw
0 NULL
1 ewrewrw; (end of chain)
2 NULL
3 NULL
4 NULL
5 NULL
6 NULL
7 NULL
8 NULL
9 NULL
10 NULL
 

Создайте все функции-члены, которые не должны изменять сам объект const . Это гарантирует, что функция может использоваться, когда объект используется в const контексте, а также позволит компилятору помочь вам, если вы допустите ошибку. Это приведет к ошибкам компиляции, если вы попытаетесь изменить объект в функции, и поэтому будет жаловаться на строку table[i] = table[i]->next; , в которой вы вносите изменения в объект в вашем текущем коде.

Итак, начните с создания функции const и исправьте ошибки. С исправлениями на месте это может выглядеть примерно так:

 void display() const  // const added
{
    for (int i = 0; i < TABLE_SIZE;   i)
    {
        if (table[i] == nullptr)
            cout << i << " NULL" << endl;
        else
        {
            // using a temporary pointer, ptr, to go through the list
            for(HashNode* ptr = table[i]; ptr != nullptr; ptr = ptr->next)
            {
                cout << i << " " << ptr->value << "; ";
            }
            cout << "(end of chain)" << endl;
        }
    }   
}
 

Ваша display функция устанавливает все элементы table в nullptr циклически, пока они не станут nullptr .

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

     void display()
    {
        for (int i = 0; i < TABLE_SIZE;   i)
        {
            if (table[i] == nullptr)
                cout << i << " NULL" << endl;
            else
            {
                HashNode *p = table[i]; // another pointer variable for iterating
                while (p != nullptr)
                {
                    cout << i << " " << p->value << "; ";
                    p = p->next;
                    if (p == nullptr)
                        cout << "(end of chain)" << endl;
                }
            }
        }   
    }