选取哈希函数H（k）=（k）MOD 11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

好的，我可以回答这个问题。根据哈希函数H（k）=（k）MOD 11，我们可以得到关键字序列的散列地址如下：

22 ->
41 -> 8
53 -> 9
46 -> 2
30 -> 8 (冲突，需要再散列)
13 -> 2 (冲突，需要再散列)
01 -> 1
67 -> 1 (冲突，需要再散列)

通过二次探测再散列处理冲突，我们可以得到以下哈希表：

-> 22
1 -> 01
2 -> 46
3 ->
4 ->
5 ->
6 ->
7 ->
8 -> 41
9 -> 53
10 ->

在等概率情况下，查找成功时的平均查找长度为(1+2+3+4+5+6+7+8+9)/9=5。

相关问题

选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对

哈希函数h(k)=k mod 11，对键k进行哈希处理得到的散列地址为h(k)。

假设我们有一组键为{3, 15, 6, 10, 8, 20, 7, 9, 12, 4}的数据需要进行散列处理，并且散列地址的范围为0-10。对于每个键k，我们先通过哈希函数h(k)计算出其散列地址，然后使用线性探测来处理冲突。

首先，我们将数据依次插入到散列表中：
- 3的散列地址为3，直接插入；
- 15的散列地址为4，直接插入；
- 6的散列地址为6，直接插入；
- 10的散列地址为10，直接插入；
- 8的散列地址为8，直接插入；
- 20的散列地址为9，直接插入；
- 7的散列地址为7，直接插入；
- 9的散列地址为9，发生冲突，使用线性探测找到下一个空闲位置为10，插入；
- 12的散列地址为1，直接插入；
- 4的散列地址为4，发生冲突，使用线性探测找到下一个空闲位置为5，插入。

经过上述处理，我们得到的散列表为：
0: 空
1: 12
2: 空
3: 3
4: 15, 4
5: 空
6: 6
7: 7
8: 8
9: 20, 9
10: 10

通过使用哈希函数h(k)=k mod 11和线性探测的方法，我们成功地将数据存储到了散列表中，并解决了冲突的问题。

用C语言代码实现哈希表的构造和查找算法，要求：用除留余数法构造哈希函数，分别用一次探测再散列、二次探测再散列解决冲突。

好的，以下是哈希表的构造和查找算法的C语言代码实现，包括除留余数法构造哈希函数和一次探测再散列、二次探测再散列解决冲突：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// 哈希表节点结构体
typedef struct HashNode {
    char *key;  // 键
    int value;  // 值
} HashNode;

// 哈希表结构体
typedef struct HashTable {
    HashNode **nodes;  // 指向节点指针的指针，即二级指针
    int size;          // 哈希表大小
} HashTable;

// 创建哈希表
HashTable *createHashTable() {
    HashTable *hashTable = malloc(sizeof(HashTable));
    hashTable->nodes = malloc(sizeof(HashNode *) * TABLE_SIZE);
    memset(hashTable->nodes, 0, sizeof(HashNode *) * TABLE_SIZE);
    hashTable->size = TABLE_SIZE;
    return hashTable;
}

// 除留余数法构造哈希函数
int hash(char *key) {
    int hashVal = 0;
    while (*key != '\0') {
        hashVal = (hashVal * 31 + *key) % TABLE_SIZE;
        key++;
    }
    return hashVal;
}

// 插入键值对
void insert(HashTable *hashTable, char *key, int value) {
    int index = hash(key);  // 计算哈希值
    HashNode *node = malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    if (hashTable->nodes[index] == NULL) {
        // 插入到空节点
        hashTable->nodes[index] = node;
    } else {
        // 冲突，使用一次探测再散列解决
        int i;
        for (i = index + 1; i != index; i = (i + 1) % TABLE_SIZE) {
            if (hashTable->nodes[i] == NULL) {
                hashTable->nodes[i] = node;
                return;
            }
        }
        // 一次探测再散列失败，使用二次探测再散列解决
        int step = 1;
        for (i = index + step * step; i != index; i = (i + (++step) * step) % TABLE_SIZE) {
            if (hashTable->nodes[i] == NULL) {
                hashTable->nodes[i] = node;
                return;
            }
        }
    }
}

// 查找键对应的值
int lookup(HashTable *hashTable, char *key) {
    int index = hash(key);  // 计算哈希值
    if (hashTable->nodes[index] == NULL) {
        // 未找到节点
        return -1;
    } else if (strcmp(hashTable->nodes[index]->key, key) == 0) {
        // 找到节点
        return hashTable->nodes[index]->value;
    } else {
        // 冲突，使用一次探测再散列解决
        int i;
        for (i = index + 1; i != index; i = (i + 1) % TABLE_SIZE) {
            if (hashTable->nodes[i] == NULL) {
                // 未找到节点
                return -1;
            } else if (strcmp(hashTable->nodes[i]->key, key) == 0) {
                // 找到节点
                return hashTable->nodes[i]->value;
            }
        }
        // 一次探测再散列失败，使用二次探测再散列解决
        int step = 1;
        for (i = index + step * step; i != index; i = (i + (++step) * step) % TABLE_SIZE) {
            if (hashTable->nodes[i] == NULL) {
                // 未找到节点
                return -1;
            } else if (strcmp(hashTable->nodes[i]->key, key) == 0) {
                // 找到节点
                return hashTable->nodes[i]->value;
            }
        }
    }
}

int main() {
    HashTable *hashTable = createHashTable();
    insert(hashTable, "apple", 1);
    insert(hashTable, "banana", 2);
    insert(hashTable, "cat", 3);
    insert(hashTable, "dog", 4);
    insert(hashTable, "elephant", 5);
    printf("banana: %d\n", lookup(hashTable, "banana"));
    printf("cat: %d\n", lookup(hashTable, "cat"));
    printf("elephant: %d\n", lookup(hashTable, "elephant"));
    printf("fox: %d\n", lookup(hashTable, "fox"));
    return 0;
}

上述代码中，`HashTable` 结构体包含一个指向节点指针的指针 `nodes` 和哈希表大小 `size`，节点结构体 `HashNode` 包含键 `key` 和值 `value`。首先使用 `createHashTable` 函数创建哈希表，然后使用 `hash` 函数计算键的哈希值，接着使用 `insert` 函数将键值对插入哈希表中，如果出现冲突，则使用一次探测再散列或二次探测再散列解决。最后使用 `lookup` 函数查找键对应的值，如果未找到节点，则返回 `-1`。

在 `main` 函数中，首先创建哈希表，然后插入若干个键值对，接着使用 `lookup` 函数查找键对应的值，并输出结果。

需要注意的是，上述代码中的哈希表大小为 10，即 `TABLE_SIZE` 宏定义的值，可以根据实际情况进行调整。