中信建设官方网站,北京小程序制作实惠华网天下,美食烹饪网站策划书,个人做淘宝客网站不能备案吗实现哈希表的方法有两种方法#xff1a;开放寻址法 、链地址法 开放寻址法#xff1a;在开放寻址法中#xff0c;所有的元素都存储在哈希表的数组中#xff0c;冲突发生时会探测下一个可用的位置#xff0c;直到找到一个空闲的位置。这种方法保持了元素的顺序#xff0c;…实现哈希表的方法有两种方法开放寻址法 、链地址法 开放寻址法在开放寻址法中所有的元素都存储在哈希表的数组中冲突发生时会探测下一个可用的位置直到找到一个空闲的位置。这种方法保持了元素的顺序但可能导致聚集clustering。 链地址法链地址法使用一个数组来存储指向链表头部的指针每个链表存储具有相同哈希值的元素。如果发生冲突新的元素将被添加到该链表的末尾。这种方法可以避免聚集但不保持元素的顺序。
链地址法
#include stdio.h
#include stdlib.h#define SIZE 20
typedef struct Node {int value;int key;struct Node* next;
}Node;typedef struct{Node *table[SIZE];
}HashTable; //初始化哈希表
void initHashTable(HashTable *ht){for (int i 0; i SIZE; i) {ht-table[i] NULL;}
} int getKey(int value){return value%SIZE;
}//向哈希表中插入数据 hash公式就是 value%20
void addvalue(int value,HashTable *ht){Node *node(Node*)malloc(sizeof(Node));node-valuevalue;int keygetKey(value);node-keykey;node-nextNULL;Node *tmpht-table[key];if(tmp!NULL){while(tmp-next){tmptmp-next; }tmp-nextnode;}else{ht-table[key]node; }
}//查看哈希表中是否包含此值
int containValue(int value,HashTable *ht){int keygetKey(value);if(key0){printf(查询非法数据);return -1;}Node* tmpht-table[key];if(tmpNULL) return 0;while(tmp){if(tmp-valuevalue) return 1;tmptmp-next;}return 0;
}// 释放哈希表内存
void freeHashTable(HashTable *ht) {for (int i 0; i SIZE; i) {Node *current ht-table[i];while (current ! NULL) {Node *temp current;current current-next;free(temp);}}
}int main(){HashTable table;initHashTable(table);addvalue(1,table);addvalue(3,table);addvalue(6,table);addvalue(7,table);addvalue(11,table);addvalue(23,table);addvalue(21,table);addvalue(27,table);addvalue(87,table);printf(%d\n,containValue(-1,table));freeHashTable(table);system(pause);return 0;
}
开放寻址法
#include stdio.h
#include stdlib.h#define SIZE 100typedef struct Node {int value;int key;struct Node* next;
}Node;typedef struct {Node* node[SIZE];int magnification;
}HashTable;void initHashTable(HashTable *ht){int i;for(i0;iSIZE;i){ht-node[i]NULL;}ht-magnification1;
}//获取索引-2:该元素已经无法插入-1:非法值
int getKey(int value,HashTable *ht){int keyvalue%SIZE;if(key0ht-node[key]!NULL){int i;for(ikey1;iSIZE;i){if(ht-node[i]NULL) return i;}return -2;}else if(ht-node[key]NULL){return key;}return -1;
}void pushToHt(int value,HashTable *ht){int keygetKey(value,ht);if(key-1){printf(非法值的查找\n);}else if(key-2){printf(%d插入失败\n,value);}else{Node *node(Node*)malloc(sizeof(Node));node-keykey;node-valuevalue;node-nextNULL;ht-node[key]node;}
}int containValue(int value,HashTable *ht){int keyvalue%SIZE;if(key-1){printf(查询非法数据\n);return -1;}else{return ht-node[key]!NULLht-node[key]-valuevalue?1:0;}
}int main(){HashTable ht;initHashTable(ht);pushToHt(1,ht);pushToHt(2,ht);pushToHt(23,ht);pushToHt(11,ht);pushToHt(12,ht);pushToHt(14,ht);pushToHt(5,ht);pushToHt(15,ht);pushToHt(31,ht);printf(%d\n,containValue(14,ht));system(pause);return 0;
}
