C语言平方取中法建立哈希表,链地址法解决冲突
时间: 2023-07-15 16:11:38 浏览: 57
平方取中法是哈希函数的一种常用方法,它可以将关键字映射到哈希表的地址空间中。具体思路是,首先对关键字进行平方运算,然后取中间若干位作为哈希值。实现过程如下:
1. 将关键字进行平方运算,得到平方结果;
2. 取平方结果的中间若干位作为哈希值;
3. 将哈希值对哈希表长度取模,得到最终的哈希地址。
C语言代码实现如下:
```c
int hash(int key, int table_size) {
int square = key * key;
int middle = (square / 100) % 10000; // 取中间4位
return middle % table_size; // 取模,得到哈希地址
}
```
对于哈希冲突的解决方法,链地址法是一种常用的方法。它将哈希表中每个位置的元素都组成一个链表,发生哈希冲突时,将新元素插入到对应位置的链表末尾即可。具体实现过程如下:
1. 对于哈希表中的每个位置,都设置一个指针,指向该位置的链表头节点;
2. 当需要插入一个元素时,首先根据哈希函数计算出该元素的哈希地址;
3. 检查该位置的链表是否为空,若为空,则直接插入元素,否则遍历链表,查找是否已经存在相同的元素;
4. 若找到相同的元素,则不插入,否则将元素插入到链表末尾。
C语言代码实现如下:
```c
typedef struct Node {
int key;
struct Node *next;
} Node;
Node *hash_table[MAX_SIZE];
void insert(int key) {
int index = hash(key, MAX_SIZE);
Node *p = hash_table[index];
while (p != NULL) {
if (p->key == key) {
return; // 已经存在相同元素,不插入
}
p = p->next;
}
// 新建节点,插入到链表末尾
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->key = key;
new_node->next = hash_table[index];
hash_table[index] = new_node;
}
```
这样,我们就可以利用平方取中法和链地址法来实现哈希表了。