0

因此，我正在尝试为分配创建一个简单的哈希数据结构。实际上，除了当我尝试将哈希中的键与通过引用传递给函数的字符串进行比较时，一切正常。比较时出现段错误，我试图重写它，但我不断收到相同的段错误或编译错误。我只是不确定在尝试比较时我无法访问什么。我只能假设它是 ->GetKey 但我可以在它下面的打印功能中访问它。

#ifndef MYSTRINGMAP_H
#define MYSTRINGMAP_H

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

const int BASE_SIZE = 10;

template <typename T>
class HashEntry
{
  private:
    string m_key;
    T m_value;
  public:
    HashEntry( string k , T v ) : m_key( k ), m_value( v ) {}
    string& getKey() { return m_key; }
    T& getValue() { return m_value; }
};

template <typename T>
class MyStringMap
{
  private:
    HashEntry<T> **m_table;
    int m_size;
    int hash( const string &s ) const;
  public:
    MyStringMap()
    {
      m_table = new HashEntry<T>*[BASE_SIZE];
      m_size = BASE_SIZE;
      for( int i = 0 ; i < m_size ; ++i )
      {
        m_table[i] = NULL;
      }
    }
    int size() const;
    bool isEmpty() const { return ( size() == 0 ); }
    const T& valueOf( const string& key ) const;
    void clear();
    void insert( const string& key , const T& val );
    void remove( const string& k );
    void print() const;
};

template <typename T>
int MyStringMap<T>::hash( const string &s ) const
{
  int hashval = 0;
  for( unsigned int i = 0 ; i < s.length() ; ++i )
  {
    char c = s.at(i);
    hashval += int(c);
  }

  return hashval;
}

template <typename T>
int MyStringMap<T>::size() const
{
  int s = 0;
  for( int i = 0 ; i < m_size ; ++i )
  {
    if( m_table[i] != NULL )
    {
      ++s;
    }
  }

  return s;
}

template <typename T>
const T& MyStringMap<T>::valueOf( const string& key ) const
{
  int hashval = hash( key );
  hashval = hashval % m_size;
  while( m_table[hashval] != NULL && hash( m_table[hashval]->getKey() ) != hash( key ) )
  {
    hashval = ( hashval + 1 ) % m_size;
  }

  if( m_table[hashval] == NULL )
  {
    string err = "ERROR [valueOf] Key not found.";
    throw err;
  }
  else
  {
    return m_table[hashval]->getValue();
  }
}

template <typename T>
void MyStringMap<T>::clear()
{
  for( int i = 0 ; i < m_size ; ++i )
  {
    if( m_table[i] != NULL )
    {
      delete m_table[i];
    }
  }
  delete m_table;
  m_table = new HashEntry<T>*[BASE_SIZE];
  m_size = BASE_SIZE;
  for( int i = 0 ; i < m_size ; ++i )
  {
    m_table[i] = NULL;
  }

  return;
}

template <typename T>
void MyStringMap<T>::insert( const string& key , const T& val )
{
  if( size() >= m_size )
  {
    int tempsize = m_size * 2;
    HashEntry<T>** temp;
    temp = new HashEntry<T>*[( m_size * 2 )];
    for( int i = 0 ; i < m_size ; ++i )
    {
      temp[i] = m_table[i];
    }
    clear();
    m_table = temp;
    m_size = tempsize;
  }

  int hashval = hash( key );
  hashval = hashval % m_size;
  while( m_table[hashval] != NULL && hash( m_table[hashval]->getKey() ) != hash( key ) )
  {
    hashval = ( hashval + 1 ) % m_size;
  }
  if( m_table[hashval] != NULL )
  {
    delete m_table[hashval];
  }
  m_table[hashval] = new HashEntry<T>( key, val );

  return;
}

template <typename T>
void MyStringMap<T>::remove( const string& k )
{
  int removeIndex = -1;
  for( int i = 0 ; i < m_size ; ++i )
  {
    if( hash( m_table[i]->getKey() ) == hash( k ))
    {
      removeIndex = i;
    }
  }

if( removeIndex >= 0 )
{
  delete m_table[removeIndex];
  m_table[removeIndex] = NULL;
}


  return;
}

template <typename T>
void MyStringMap<T>::print() const
{
  for( int i = 0 ; i < m_size ; ++i )
  {
    if( m_table[i] != NULL )
    {
      cout << endl << "< " << m_table[i]->getKey() << ", " << m_table[i]->getValue() << " > ";
    }
  }
  cout << endl;

  return;
}

#endif

至于我们得到的测试仪：

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

// --------------------------------------------------------------
void test0()
{
  MyStringMap<char> grades;

  cout << endl;  
  cout << "--- Test 0 ----" << endl;
  cout << "Is Empty? " << boolalpha << grades.isEmpty() << endl; 
  cout << "Size = " << grades.size()  << endl;


  grades.insert("Nate",'A');
  grades.insert("George",'C');
  grades.insert("Karl",'F');
  grades.insert("John",'B');
  grades.insert("Will",'B');  

  cout << endl;
  cout << "Is Empty? " << boolalpha << grades.isEmpty() << endl; 
  cout << "Size = " << grades.size()  << endl;

  grades.print();


  return;
}

// --------------------------------------------------------------
void test1()
{
  MyStringMap<string> thelist;

  cout << endl;
  cout << "--- Test 1 ----" << endl;
  cout << "Is Empty? " << boolalpha << thelist.isEmpty() << endl; 
  cout << "Size = " << thelist.size()  << endl;


  thelist.insert("Fry","Naughty");
  thelist.insert("Leela","Naughty");
  thelist.insert("Hermes","Naughty");
  thelist.insert("Qubert","Naughty");
  thelist.insert("Zoidberg","Nice");  
  thelist.insert("Scruffy","Naughty");
  thelist.insert("Bender","Naughty");
  thelist.insert("Zapp","Naughty");
  thelist.insert("Kiff","Naughty");

  thelist.insert("Leela","Nice");  

  cout << endl;
  cout << "Is Empty? " << boolalpha << thelist.isEmpty() << endl; 
  cout << "Size = " << thelist.size()  << endl;

  thelist.print();

  cout << endl;
  cout << "Testing remove" << endl;
  cout << "Removing non-Humans" << endl;  

  thelist.remove("Leela");
  thelist.remove("Zoidberg");
  thelist.remove("Bender");  
  thelist.remove("Kiff");    

  thelist.remove("Nixon");    

  thelist.print();


  cout << endl;
  cout << "Testing Lookup" << endl;

  try 
  {
    cout << "Fry? " << thelist.valueOf("Fry") << endl;  
    cout << "Hermes? " << thelist.valueOf("Hermes") << endl;  
    cout << "Qubert? " << thelist.valueOf("Qubert") << endl;  

    cout << "Nixon? ";
    cout << thelist.valueOf("Nixon") << endl;  
  }
  catch (string s)
  {
    cout << "ERROR : " << s << endl;
  }

  cout << endl;
  //cout << "End of test #1" << endl;
  return;
}

// --------------------------------------------------------------
// --------------------------------------------------------------
// --------------------------------------------------------------
int main ()
{
  cout << "MAP TESTER!!" << endl;

  test0();
  test1();


  //cout << "Q?";
  //cin.ignore();
  //cin.get();

  return 0;
}

.h 是：

#ifndef ABSTRACTSTRINGMAP_H
#define ABSTRACTSTRINGMAP_H

#include <iostream>
#include <string>
using namespace std;


template < typename T >
class AbstractStringMap
{

public:

   /*** ---- Accessor Operations ---- */

// Purpose: Accessor function for the number of elements in the Map
// Returns: number of elements in the Map 
  virtual int size() const = 0;


// Purpose: Checks if a Map is empty
// Returns: 'true' if the Map is empty
//     'false' otherwise  
  virtual bool isEmpty() const = 0;


// Purpose: Returns the value associated with a key.
// Parameters: key of the value to be found 
// Returns: 
//     If The Map contains Key then return the value associated with Key.
//     If The Map does not contains Key then THROW SOMETHING!!!
  virtual const T& valueOf(const string& key) const = 0;



  /*** ---- Mutator Operations ---- */

// Purpose: Clears the Map
// Postconditions: an empty Map
  virtual void clear() = 0;


// Purpose: Inserts an element into a Map
// Parameters: Key and  Value to be added to the Map
// Postconditions: The Map now contains the pair < Key, Value >
//     if the Map already contains a value associated with Key,
//     replace it with the parameter Val
  virtual void insert(const string& key, const T& val) = 0;


// Purpose: Removes an element from the Map
// Parameters: K, the Key to remove
// Postconditions: the map does not contains a pair with k as Key
  virtual void remove(const string& k) = 0;


  /*** ---- Output Operations ---- */

// Purpose: Prints the Map with pretty formatting
// No partucular order is required.
  virtual void print() const = 0;


  /*** ---- Utility Functions Operations ---- */

// Purpose: Hashes a string into an integer.
// you shall use this function for your hash-table.
private:
  virtual int hash(const string &s) const = 0;                  

};


#endif
4

1 回答 1

0

错误是，当您调整表的大小时，insert您将指针从旧表复制到新表，但之后您调用clear删除相同的指针。

中的调整大小代码insert有另一个错误，因为它不会重新散列条目，而是将它们复制到与以前相同的插槽，即使表大小已更改。这意味着在调整表格大小后，许多条目将占用错误的插槽。

另一个错误是在remove

if( hash( m_table[i]->getKey() ) == hash( k ))

应该

if(m_table[i] != NULL && hash( m_table[i]->getKey() ) == hash( k ))

但这仍然留下“不比较键错误”（见评论），所以真的应该是

if(m_table[i] != NULL && m_table[i]->getKey() == k)

但是另一个错误是这个版本的 remove 没有使用散列，它只是对整个表进行线性搜索。

我认为在这段代码上还有一些工作要做。

于 2013-05-10T12:05:41.373 回答