0

所以我目前正在做一个项目，旨在帮助我更多地了解哈希表

但是，我在实现 HashTable 的数据成员时遇到了重大困难，该成员应该是模板链接列表的数组，其类型为 KeyValuePair。

该程序的要求之一是我实现了链式寻址，并且允许用户初始化 Data 数组的长度，所以我几乎被迫使用链表数组。

由于我在插入 Data 成员时遇到问题，我假设我的 Data 成员声明可能有问题（在以下代码段的底部）：

template <typename DATA_TYPE>
class HashTable
{
    typedef pair<const int, DATA_TYPE> KeyValuePair;

private:
    int Size;
    int Keys;
    list<KeyValuePair>* Data;

据我了解，这应该允许我指向链接列表数组的元素。

但是，当涉及到初始化我的数组（并插入到我的数组中，稍后我将向您展示）时，我不太清楚出了什么问题。

这是我的构造函数和析构函数：

public:
HashTable(const int& size = INITIAL_SIZE)
{
    assert( size > 0 );
    Keys = 0;
    Size = size;
    Data = new list<KeyValuePair>[Size];
    /*for(int i = 0; i<Capacity; i++)
        Data[i] = new list<DATA_TYPE>;*/
}

~HashTable()
{
    delete[] Data;
}

这是我的插入函数，它会导致在 std::list 中出现断点，这（我认为）是因为我试图使用 list.merge() 访问 NULL“.Next”指针。但我不确定：

void Insert(const DATA_TYPE& value)
{
    int hashIndex;
    hashIndex = HashCode(value);

    KeyValuePair* newPair = new KeyValuePair(hashIndex, value);
    list<KeyValuePair>* newHash = new  list<KeyValuePair>;

    newHash->push_back(*newPair);
    while(hashIndex>Size)
    {
        hashIndex-=Size;
    }
    //Data[hashIndex]->push_back(value);
    Data[hashIndex].merge(*newHash);
}

过去几天我一直在做这件事，真的需要一些新鲜的眼睛来审视我正在做的事情，并确认或帮助我的想法......

4

2 回答 2

0

弄清楚了！

因此，最困难的问题之一是无法在调试窗口中查看数组指针的数据元素，因为它始终只指向数组的开头或某个点。

但是，无论如何，（除了修复我的原始代码中的内存泄漏之外）主要问题是（正如我所想的那样）我试图将一个初始化的链表与一个未初始化的链表合并。

为了解决这个问题，在下面的代码片段中，我使用了 std::list.push_back() 函数。它初始化列表并且不会覆盖该哈希索引中可能已经存在的任何值。

为了检查我实际上是在散列值，我创建了一个搜索函数（给定一个数据值）查找索引并输出保存在该索引处的字符串。

void Insert(const DATA_TYPE& value)
{
    int hashIndex;
    hashIndex = HashCode(value);

    KeyValuePair newPair = KeyValuePair(hashIndex, value);

    while(hashIndex>Size)
    {
        hashIndex-=Size;
    }

    Data[hashIndex].push_back(newPair);
}

（遗憾的是，我不得不等待才能发布答案）

于 2013-04-22T16:00:38.350 回答
0

为什么要在构造函数中删除数据

HashTable(const int& size = INITIAL_SIZE)
{
    Keys = 0;
    Size = size;
    if(size!=INITIAL_SIZE)
    {
        delete[] Data;  <------------
        Data = new list<KeyValuePair>[Size];
    }
}

没有什么可删除的，只是做 

 HashTable( int size = INITIAL_SIZE)
{
    assert ( size > 0 );
    Keys = 0;
    Size = size;
    Data = new list<KeyValuePair>[Size];
}

还

while(hashIndex>Size)
{
    hashIndex-=Size;
}
//Data[hashIndex]->push_back(value);
Data[hashIndex].merge(*newHash);

如果hashIndex == Size，您将访问一个超出范围的元素。

于 2013-04-19T19:37:33.280 回答