我正在尝试使用 C++ 中的哈希表来存储字符串,即字符串键和数据。我正在使用 2003 年出版的《游戏程序员的数据结构》一书中的代码。
虽然我可以实现一个 int 哈希表,但当我尝试对 string one 执行相同操作时,我却陷入了错误。
C++ 总是给我同样的错误。
//code
#include <string>
#include <iostream>
#include "HashTable.h"
using namespace std;
//hash table
//***********************************************************************
unsigned long int Hash(int i) {
return i;
}
unsigned long int StringHash(const char* p_string) {
unsigned long int hash = 0;
int i;
int length = strlen(p_string);
for(i = 0; i < length; i++) {
hash += ((i + 1) * p_string[i]);
}
return hash;
}
HashTable<string, string> table(10, StringHash); <<--problem here ERROR BELOW
HashEntry<string, string>* entry;
//***********************************************************************
Error 6 error C2664: 'HashTable<KeyType,DataType>::HashTable(int,unsigned long (__cdecl *)(KeyType))' : cannot convert parameter 2 from 'unsigned long (__cdecl *)(const char *)' to 'unsigned long (__cdecl *)(KeyType)' j:\my_docs\college 2010 -2011\data structures for games\ca3_datastructures_gerry mc donnell\ca3_datastructures_gerry mc donnell\loginuser.h 31 CA3_DataStructures_gerry mc donnell
如果有人能提供帮助,那就太好了。
stringhash
函数是书中给出的,所以我不确定我做错了什么。
哈希表.h
// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// HashTable.h
// This file holds the Linekd Hash Table implementation.
// ============================================================================
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "DLinkedList.h"
#include "Array.h"
// -------------------------------------------------------
// Name: HashEntry
// Description: This is the hash table entry class. It
// stores a key and data pair.
// -------------------------------------------------------
template< class KeyType, class DataType >
class HashEntry {
public:
KeyType m_key;
DataType m_data;
};
// -------------------------------------------------------
// Name: HashTable
// Description: This is the hashtable class.
// -------------------------------------------------------
template< class KeyType, class DataType >
class HashTable {
public:
// typedef the entry class to make is easier to work with.
typedef HashEntry<KeyType, DataType> Entry;
// ----------------------------------------------------------------
// Name: HashTable
// Description: construct the table with a size, and a hash
// function. The constructor will construct the
// m_table array with the correct size.
// Arguments: p_size: The size of the table
// p_hash: the hashing function.
// Return Value: None
// ----------------------------------------------------------------
HashTable(int p_size, unsigned long int (*p_hash)(KeyType))
: m_table(p_size) {
// set the size, hash function, and count.
m_size = p_size;
m_hash = p_hash;
m_count = 0;
}
// ----------------------------------------------------------------
// Name: Insert
// Description: Inserts a new key/data pair into the table.
// Arguments: p_key: the key
// p_data: the data attached to the key.
// Return Value: None
// ----------------------------------------------------------------
void Insert(KeyType p_key, DataType p_data) {
// create an entry structure.
Entry entry;
entry.m_data = p_data;
entry.m_key = p_key;
// get the hash value from the key, and modulo it
// so that it fits within the table.
int index = m_hash(p_key) % m_size;
// add the entry to the correct index, increment the count.
m_table[index].Append(entry);
m_count++;
}
// ----------------------------------------------------------------
// Name: Find
// Description: Finds a key in the table
// Arguments: p_key: the key to search for
// Return Value: a pointer to the entry that has the key/data,
// or 0 if not found.
// ----------------------------------------------------------------
Entry* Find(KeyType p_key) {
// find out which index the key should exist in
int index = m_hash(p_key) % m_size;
// get an iterator for the list in that index.
DListIterator<Entry> itr = m_table[index].GetIterator();
// search each item
while (itr.Valid()) {
// if the keys match, then return a pointer to the entry
if (itr.Item().m_key == p_key)
return &(itr.Item());
itr.Forth();
}
// no match was found, return 0.
return 0;
}
// ----------------------------------------------------------------
// Name: Remove
// Description: Removes an entry based on key
// Arguments: p_key: the key
// Return Value: true if removed, false if not found.
// ----------------------------------------------------------------
bool Remove(KeyType p_key) {
// find the index that the key should be in.
int index = m_hash(p_key) % m_size;
// get an iterator for the list in that index.
DListIterator<Entry> itr = m_table[index].GetIterator();
// search each item
while (itr.Valid()) {
// if the keys match, then remove the node, and return true.
if (itr.Item().m_key == p_key) {
m_table[index].Remove(itr);
m_count--;
return true;
}
itr.Forth();
}
// item wasn't found, return false.
return false;
}
// ----------------------------------------------------------------
// Name: Count
// Description: Gets the number of entries in the table.
// Arguments: None
// Return Value: Number of entries in the table.
// ----------------------------------------------------------------
int Count() {
return m_count;
}
// ----------------------------------------------------------------
// Name: m_size
// Description: This is the size of the table
// ----------------------------------------------------------------
int m_size;
// ----------------------------------------------------------------
// Name: m_count
// Description: This is the number of entries in the table.
// ----------------------------------------------------------------
int m_count;
// ----------------------------------------------------------------
// Name: m_table
// Description: This is the actual table, a list of linked
// lists of entries.
// ----------------------------------------------------------------
Array< DLinkedList< Entry > > m_table;
// ----------------------------------------------------------------
// Name: m_hash
// Description: a pointer to the hash function.
// ----------------------------------------------------------------
unsigned long int (*m_hash)(KeyType);
};
#endif
//array.h
最佳答案
您的Hashtable
构造函数要求哈希函数采用 KeyType
参数。
您正在创建 Hashtable
与 std::string
如KeyType
,但传递一个采用 char*
的哈希函数范围。这些不兼容。
要么使用 char*
进行哈希处理键类型,或更改哈希函数以使用 std::string
.
关于C++ 字符串哈希表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5715085/