作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

template<typename T, typename Key = unsigned int>
class hash
{
 struct node
 {
  Key _key;
  T _data;
  node *_next;
  node(const Key &key, const T &x) : _key(key), _data(x), _next(NULL)  {  }
 };

 node **_head;
 unsigned int _mod;

public:

 hash(unsigned int mod = 13) : _mod(mod)
 {
  assert(mod);
  _head = new node*[_mod];
  memset(_head, 0, sizeof(node *) * _mod);
 }

 ~hash()
 {
  clear();
  delete[] _head;
 }

 void clear()
 {
  for(int i = 0; i < _mod; i++)
  {
   for(node *p; _head[i]; )
   {
    p = _head[i], _head[i] = _head[i]->_next;
    delete p;
   }
   _head[i] = NULL;
  }
 }

 void visit(void func(unsigned int, const Key &, const T &))
 {
  for(int i = 0; i < _mod; i++)
   for(node *p = _head[i]; p; p = p->_next)
    func(i + 1, p->_key, p->_data);
 }

 void push(const Key &key, const T &x)
 {
  unsigned int i = (unsigned int)key % _mod;

  if(_head[i])
  {
   for(node *p = _head[i]; p && p->_key != key; p = p->_next)
   {
    if(!p->_next)
    {
     p->_next = new node(key, x);
     break;
    }
   }
  }
  else
   _head[i] = new node(key, x);
 }
 
 T * find(const Key &key)
 {
  unsigned int i = (unsigned int)key % _mod;

  for(node *p = _head[i]; p; p = p->_next)
  {
   if(p->_key == key)
    return &p->_data;
  }

  return NULL;
 }

 void pop(const Key &key)
 {
  unsigned int i = (unsigned int)key % _mod;

  node *t = NULL, *pre = NULL;

  if(_head[i])
  {
   if(_head[i]->_key == key)
    t = _head[i], _head[i] = _head[i]->_next; 
   else
   {
    for(pre = _head[i], t = pre->_next; t; t = t->_next)
    {
     if(t->_key == key)
     {
      pre->_next = t->_next;
      break;
     }
    }
   }
  }

  if(t)
   delete t;

 }

 void pop(const Key &key, T &data)
 {
  unsigned int i = (unsigned int)key % _mod;

  node *t = NULL, *pre = NULL;

  if(_head[i])
  {
   if(_head[i]->_key == key)
    t = _head[i], _head[i] = _head[i]->_next; 
   else
   {
    for(pre = _head[i], t = pre->_next; t; t = t->_next)
    {
     if(t->_key == key)
     {
      pre->_next = t->_next;
      break;
     }
    }
   }
  }

  if(t)
  {
   data = t->_data;
   delete t;
  }

 } 
};   

相关软件：