散列(C++实现)

散列的构成：散列函数，散列表的存储方式，散列表的冲突解决方法。

1.散列函数

较常用的散列函数有除留余数法，数字分析法，平方取中法，折叠法。

2.散列表的存储方式

闭散列法（开地址法），用数组存储；开散列法（链地址法），用邻接链表存储。

3.散列表的冲突解决方法

主要是针对闭散列中关键码位置冲突的问题，常用的方法有线性探查法，二次探查法，双散列法。

性能分析：在存储方式中，开散列法优于闭散列法；在散列函数中，除留余数法最优。

实现代码：

1 #include<iostream>
  2 using namespace std;
  3 enum kind{Active,Empty,Deleted};
  4 class ArrayHashTable{//闭散列法 
  5     public:
  6         ArrayHashTable(const int d,int sz=20){
  7             tableSize=sz;
  8             divitor=d;
  9             table=new int[tableSize];
 10             info=new kind[tableSize];
 11             for(int i=0;i<tableSize;i++){
 12                 table[i]=0;
 13                 info[i]=Empty;
 14             }
 15         }
 16         ~ArrayHashTable(){
 17             delete[] table;
 18             delete[] info;
 19         }
 20         bool findPos(int k,int &i){//寻找k关键码所在位置i 
 21             i=k%divitor;
 22             int j=i;
 23             do{
 24                 if(info[i]==Active&&table[i]==k)
 25                     return true;
 26                 if(info[i]==Empty) 
 27                     return false;
 28                 i=(i+1)%tableSize;        
 29             }
 30             while(j!=i);
 31             return false;
 32         }
 33         bool insert(int k){//插入关键码k 
 34             int i;
 35             if(findPos(k,i))
 36                 return false;
 37             if(info[i]!=Active){
 38                 table[i]=k;
 39                 info[i]=Active;
 40                 return true;    
 41             }else
 42                 return false;
 43         }
 44         bool remove(int k){//删除关键码k 
 45             int i;
 46             if(!findPos(k,i))
 47                 return false;
 48             table[i]=Deleted;
 49             return true;
 50         }
 51         int *getArray(){
 52             return table;
 53         }
 54     private:
 55         int divitor;
 56         int tableSize;
 57         int *table;
 58         kind *info;
 59 };
 60 
 61 
 62 class Node{
 63     public:
 64         int data;
 65         Node *next;
 66         Node(int d,Node *n=NULL){
 67             data=d;
 68             next=n;
 69         }
 70 };
 71 class LinkedHashTable{//开散列法
 72     public:
 73         LinkedHashTable(int d,int sz=20){
 74             tableSize=sz;
 75             divitor=d;
 76             hs=new Node*[sz];
 77             for(int i=0;i<sz;i++)
 78             hs[i]=new Node(0);
 79         }
 80         ~LinkedHashTable(){
 81             delete []hs;
 82         }
 83         bool findPos(int k,Node *&p,Node *&last){
 84             int i=k%divitor;
 85             last=hs[i];
 86             p=hs[i]->next;
 87             while(p!=NULL&&p->data!=k){
 88                 p=p->next;
 89                 last=last->next;
 90             } 
 91             if(p!=NULL&&p->data==k)
 92                 return true;
 93              else
 94                  return false;
 95         }
 96         bool insert(int k){
 97             Node *p,*last;
 98             int i=k%divitor;
 99             if(findPos(k,p,last))
100                 return false;
101             last->next=new Node(k);    
102             return true;
103         }
104         bool remove(int k){
105             Node *p,*last;
106             if(!findPos(k,p,last))
107                 return false;
108             last->next=p->next;
109             return true;
110         }
111         Node **getArray(){
112             return hs;
113         }
114     private:
115         int divitor;
116         int tableSize;
117         Node **hs;
118 };
119 
120 void test(Node *&q){
121     q=new Node(4);
122 } 
123 int main(){
124     //闭散列法 
125 //    ArrayHashTable *hs=new ArrayHashTable(11,12);
126 //    int a[]={37,25,14,36,49,68,57,11};
127 //    for(int i=0;i<8;i++)
128 //        hs->insert(a[i]);
129 //    int *array=hs->getArray();
130 //    for(int i=0;i<12;i++){
131 //        cout<<array[i]<<" ";
132 //    }
133 //    delete hs;
134 
135     //开散列法 
136 //    LinkedHashTable *hs=new LinkedHashTable(11,12);
137 //    int a[]={37,25,14,36,49,68,57,11};
138 //    for(int i=0;i<8;i++)
139 //        hs->insert(a[i]);
140 //    Node **array=hs->getArray();
141 //    for(int i=0;i<12;i++){
142 //        Node *p=array[i]->next;
143 //        while(p!=NULL){
144 //            cout<<p->data<<" ";
145 //            p=p->next;
146 //        }
147 //        cout<<endl;
148 //    }
149 //    delete hs;
150     return 0;
151 }

原文链接: https://www.cnblogs.com/ytz1996/p/6380060.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍