首页 > 代码库 > 散列(C++实现)
散列(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 class Node{ 61 public: 62 int data; 63 Node *next; 64 Node(int d,Node *n=NULL){ 65 data=http://www.mamicode.com/d; 66 next=n; 67 } 68 }; 69 class LinkedHashTable{ 70 public: 71 LinkedHashTable(int d,int sz=20){ 72 tableSize=sz; 73 divitor=d; 74 hs=new Node*[sz]; 75 for(int i=0;i<sz;i++) 76 hs[i]=new Node(0); 77 } 78 ~LinkedHashTable(){ 79 delete []hs; 80 } 81 bool findPos(int k,Node *&p,Node *&last){ 82 int i=k%divitor; 83 last=hs[i]; 84 p=hs[i]->next; 85 while(p!=NULL&&p->data!=k){ 86 p=p->next; 87 last=last->next; 88 } 89 if(p!=NULL&&p->data=http://www.mamicode.com/=k) 90 return true; 91 else 92 return false; 93 } 94 bool insert(int k){ 95 Node *p,*last; 96 int i=k%divitor; 97 if(findPos(k,p,last)) 98 return false; 99 last->next=new Node(k); 100 return true; 101 } 102 bool remove(int k){ 103 Node *p,*last; 104 if(!findPos(k,p,last)) 105 return false; 106 last->next=p->next; 107 return true; 108 } 109 Node **getArray(){ 110 return hs; 111 } 112 private: 113 int divitor; 114 int tableSize; 115 Node **hs; 116 }; 117 118 void test(Node *&q){ 119 q=new Node(4); 120 } 121 int main(){ 122 // ArrayHashTable *hs=new ArrayHashTable(11,12); 123 // int a[]={37,25,14,36,49,68,57,11}; 124 // for(int i=0;i<8;i++) 125 // hs->insert(a[i]); 126 // int *array=hs->getArray(); 127 // for(int i=0;i<12;i++){ 128 // cout<<array[i]<<" "; 129 // } 130 // delete hs; 131 132 133 // LinkedHashTable *hs=new LinkedHashTable(11,12); 134 // int a[]={37,25,14,36,49,68,57,11}; 135 // for(int i=0;i<8;i++) 136 // hs->insert(a[i]); 137 // Node **array=hs->getArray(); 138 // for(int i=0;i<12;i++){ 139 // Node *p=array[i]->next; 140 // while(p!=NULL){ 141 // cout<<p->data<<" "; 142 // p=p->next; 143 // } 144 // cout<<endl; 145 // } 146 // delete hs; 147 return 0; 148 }
散列(C++实现)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。