散列数据结构C++描述

落日映苍穹つ 2022-06-17 23:51 203阅读 0赞

本文进行两种散列的实现——线性开型寻址散列，链表散列

散列表——一种动态集合结构，它仅支持Insert，Search和Delete操作

基本规则：关键字key，index=fun(key),T\[index\]卫星数据，函数fun即散列函数。  
查找一个元素的期望时间为O(1)  
  
直接寻址表：关键字全域比较小，使用数组完全存储，一一对应。Insert，Search和Delete操作都是O(1)  
散列表：关键字全域较大，可能出现碰撞。  
解决碰撞之方法：  
1）找到合适的散列函数。精心选择散列函数，并且仍然要解决可能出现的碰撞，该方法不太彻底。  
2）链接法（实现）  
给定一个能存放n个元素、具有m个槽位的散列表T，定义T的装载因子a=n/m,即一个链中平均存储的元素数。  
任何元素散列到m个槽中每一个的可能性是相同的，且与其他元素已被散列到什么位置上是独立无关的。  
这称为简单一致散列。一次成功查找为O(1+a),a=n/m,插入删除O(1)，注a（书中为阿尔法）  
3）开放寻址方法（例如线性开行寻址散列）  
所有的元素都存放在散列表中，没有链表（即没有元素存放在散列表外），装载因子不大于1。  
插入一个元素是，可以连续的检查散列表的各项，直到找到一个空槽来放置待插入的关键字时为止。  
  
  
设计散列函数（算法设计略）  
启发式方法：乘法散列和除法散列  
随机化方法：全域散列  
  
线性开型寻址散列实现  
对散列表元素的删除操作执行起来比较困难；但可以解决，方法是：  
删除槽i时，在将槽i的中设置一个特定的值DELETED，而不用NIL。当然相应的Hash-Search和Hash-Insert都要配合修改。  
这样查找时间不依赖于装载因子a了。因此， 在必须删除关键字的应用中，往往采用链接法来解决碰撞。  
  
**以下实现的删除方法，是在下信手胡写，并不正确。**

// file hash.h
    #ifndef HashTable_
    #define HashTable_
    
    #include <iostream>
    #include <stdlib.h>
    #include "xcept.h"
    
    using namespace std;
    template<class E, class K>
    class HashTable
    {
       public:
          HashTable(int divisor = 11);
          ~HashTable() {delete [] ht; delete [] empty;}
          bool Search(const K& k, E& e) const;
          HashTable<E,K>& Insert(const E& e);
          HashTable<E,K>& Delete(E& e);
          void Output();// output the hash table
       private:
          int hSearch(const K& k) const;
          int D; // hash function divisor
          E *ht; // hash table array
          bool *empty; // 1D array
    };
    
    template<class E, class K>
    HashTable<E,K>::HashTable(int divisor)
    {// Constructor.
       D = divisor;
    
       // allocate hash table arrays
       ht = new E [D];
       empty = new bool [D];
    
       // set all buckets to empty
       for (int i = 0; i < D; i++)
          empty[i] = true;
    }
    
    template<class E, class K>
    int HashTable<E,K>::hSearch(const K& k) const
    {// Search an open addressed table.
     // Return location of k if present.
     // Otherwise return insert point if there is space.
       int i = k % D; // home bucket
       int j = i;     // start at home bucket
       do {
          if (empty[j] || ht[j] == k) return j;
          j = (j + 1) % D;  // next bucket
          } while (j != i); // returned to home?
    
       return j;  // table full
    }
    
    template<class E, class K>
    bool HashTable<E,K>::Search(const K& k, E& e) const
    {// Put element that matches k in e.
     // Return false if no match.
       int b = hSearch(k);
       if (empty[b] || ht[b] != k) return false;
       e = ht[b];
       return true;
    }
    
    template<class E, class K>
    HashTable<E,K>& HashTable<E,K>::Insert(const E& e)
    {// Hash table insert.
       K k = e; // extract key
       int b = hSearch(k);
    
       // check if insert is to be done
       if (empty[b]) {empty[b] = false;
                      ht[b] = e;
                      return *this;}
    
       // no insert, check if duplicate or full
       if (ht[b] == k) throw BadInput(); // duplicate
       throw NoMem(); // table full
    }
    
    template<class E, class K>
    HashTable<E,K>& HashTable<E,K>::Delete(E& e)
    {// Hash table insert.
       K k = e; // extract key
       int b = hSearch(k);
    
       // check if insert is to be done
       if (empty[b])
       {
           cout << "没有该元素。" << endl;
           return *this;
       }
       empty[b] = true;
       int count = 0;
       int index = b+1;
       while (index != b)
       {
           if (index >= D)
               index -= D;
           K key;
           if (!empty[index])
           {
               key = ht[index];
               if ((key % D) != index)
                   count++;
           }
           index++;
       }
       cout << "count=" << count << endl;
       E *temp = new E[count];
       index = b+1;
       int i = 0;
       while (index != b)
       {
           if (index >= D)
               index -= D;
           K key;
           if (!empty[index] && i < count)
           {
               key = ht[index];
               if ((key % D) != index)
               {
                   temp[i] = ht[index];
                   empty[index] = true;
                   i++;
               }
           }
           index++;
       }
       for (i = 0;i < count;i++)
           Insert(temp[i]);
       delete[] temp;
       return *this;
    }
    template<class E, class K>
    void HashTable<E,K>::Output()
    {
       for (int i = 0; i< D; i++) {
          if (empty[i]) cout << "empty" << endl;
          else cout << ht[i] << endl;}
    }
    
    #endif

xcept.h文件

// exception classes for various error types
    
    #ifndef Xcept_
    #define Xcept_
    
    #include <new>
    
    // bad initializers
    class BadInitializers {
       public:
          BadInitializers() {}
    };
    
    // insufficient memory
    class NoMem {
       public:
          NoMem() {}
    };
    
    // change new to throw NoMem instead of xalloc
    void my_new_handler()
    {
       throw NoMem();
    };
    
    //new_handler Old_Handler_ = set_new_handler(my_new_handler);
    //set_new_handler(my_new_handler);
    // improper array, find, insert, or delete index
    // or deletion from empty structure
    class OutOfBounds {
       public:
          OutOfBounds() {}
    };
    
    // use when operands should have matching size
    class SizeMismatch {
       public:
          SizeMismatch() {}
    };
    
    // use when zero was expected
    class MustBeZero {
       public:
          MustBeZero() {}
    };
    // use when zero was expected
    class BadInput {
       public:
          BadInput() {}
    };
    
    #endif

hash.cpp测试实例

// test hash table with linear open addressing
    
    #include <iostream>
    #include "hash.h"
    
    class element {
       friend int main(void);
       public:
          operator long() const {return key;}
    //   private: g++ has a problem with main a friend
          int data;
          long key;
    };
    
    int main(void)
    {
       HashTable<element, long> h(11);
       element e;
       e.key = 80;
       h.Insert(e);
       e.key = 40;
       h.Insert(e);
       e.key = 65;
       h.Insert(e);
       h.Output();
       e.key = 58;
       h.Insert(e);
       e.key = 24;
       h.Insert(e);
       cout << ' ' << endl;
       h.Output();
       e.key = 2;
       h.Insert(e);
       e.key = 13;
       h.Insert(e);
       e.key = 46;
       h.Insert(e);
       e.key = 16;
       h.Insert(e);
       e.key = 7;
       h.Insert(e);
       e.key = 21;
       h.Insert(e);
       cout << ' ' << endl;
       h.Output();
       e.key = 99;
     try {h.Insert(e);}
       catch (NoMem)
          {cout  << " No memory for 99" << endl;}
       cout << "delete 24" << endl;
       e.key = 24;
       h.Delete(e);
       h.Output();
       cout << "delete 15,there is not the element" << endl;
       e.key = 15;
       h.Delete(e);
       h.Output();
       e.key = 2;
       h.Delete(e);
       h.Output();
       return 0;
    }

makefile文件

hash:hash.o hash.o xcept.h
            g++ -o hash hash.o
    hash.o:hash.cpp hash.h xcept.h
            g++ -c hash.cpp hash.h xcept.h
            g++ -c hash.h
            g++ -c xcept.h
    clean:
            rm -f hash *.o *.gch

输出结果：

empty
    empty
    empty
    80
    empty
    empty
    empty
    40
    empty
    empty
    65
     
    empty
    empty
    24
    80
    58
    empty
    empty
    40
    empty
    empty
    65
     
    7
    21
    24
    80
    58
    2
    13
    40
    46
    16
    65
     No memory for 99
    delete 24
    count=7
    21
    empty
    2
    80
    58
    13
    46
    40
    16
    7
    65
    delete 15,there is not the element
    没有该元素。
    21
    empty
    2
    80
    58
    13
    46
    40
    16
    7
    65
    count=6
    21
    empty
    13
    80
    58
    46
    16
    40
    7
    empty
    65

链接法实现