pta 7-1散列表构造

### 构造散列表的方法 在构建散列表的过程中，通常会涉及以下几个核心部分： #### 1. 定义哈希表结构 哈希表可以被定义为一种动态分配内存的指针数组。通过 `typedef` 关键字来简化数据类型的声明[^1]。 ```c typedef struct TblNode { int key; struct TblNode *next; } HashTableNode; typedef struct TblNode* HashTable; ``` 上述代码片段展示了如何定义一个简单的链地址法中的节点以及整个哈希表的结构体类型。 --- #### 2. 设计哈希函数 为了将关键字映射到固定的地址范围 `[0, m-1]` 中，需要设计合适的哈希函数。常见的形式是取模运算 \(H(\text{key}) = \text{key} \% m\)，其中 \(m\) 是哈希表长度[^4]。 对于题目给定的关键字序列 `{31, 23, 17, 27, 19, 11, 13, 91, 61, 41}` 和哈希函数 \(H(\text{key}) = \text{key} \% 7\)[^2]，可以通过逐一代入计算得到对应的哈希地址如下： | **Key** | **Address (key % 7)** | |---------|------------------------| | 31 | 3 | | 23 | 2 | | 17 | 3 | | 27 | 6 | | 19 | 5 | | 11 | 4 | | 13 | 6 | | 91 | 0 | | 61 | 5 | | 41 | 6 | 可以看到存在多个关键字对应相同的哈希地址的情况（即冲突），因此需要采用某种策略解决这些冲突。 --- #### 3. 解决冲突——链地址法 当两个不同的关键字经过哈希函数计算后得到了相同的地址时，称为冲突。链地址法是一种有效的解决方案，它通过维护一系列指向同一地址的链表来存储冲突的数据项[^3]。 具体实现方式如下： - 创建大小为 \(m\) 的指针数组作为哈希表的基础框架。 - 对于每一个插入的关键字，先计算其哈希地址；如果该地址已被占用，则将其加入相应链表的头部或尾部。 以下是基于 C 语言的具体实现代码示例： ```c #include <stdio.h> #include <stdlib.h> // 节点定义 typedef struct Node { int key; struct Node *next; } ListNode; // 初始化哈希表 void initializeHashTable(ListNode **hashTable, int size) { for (int i = 0; i < size; ++i) { hashTable[i] = NULL; } } // 插入操作 void insertIntoHashTable(ListNode **hashTable, int key, int tableSize) { int address = key % tableSize; // 计算哈希地址 ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); newNode->key = key; newNode->next = hashTable[address]; // 将新节点插入链表头部 hashTable[address] = newNode; } // 打印哈希表内容 void printHashTable(ListNode **hashTable, int tableSize) { printf("Hash Table:\n"); for (int i = 0; i < tableSize; ++i) { printf("[%d]: ", i); ListNode *current = hashTable[i]; while (current != NULL) { printf("%d -> ", current->key); current = current->next; } printf("NULL\n"); } } int main() { const int TABLE_SIZE = 7; // 哈希表大小 ListNode **hashTable = (ListNode **)calloc(TABLE_SIZE, sizeof(ListNode *)); initializeHashTable(hashTable, TABLE_SIZE); int keys[] = {31, 23, 17, 27, 19, 11, 13, 91, 61, 41}; int numKeys = sizeof(keys)/sizeof(keys[0]); for (int i = 0; i < numKeys; ++i) { insertIntoHashTable(hashTable, keys[i], TABLE_SIZE); } printHashTable(hashTable, TABLE_SIZE); return 0; } ``` 运行以上程序将会输出构造完成后的哈希表状态。 --- #### 4. 平均查找长度计算 成功查找的平均查找长度 ASL 可以表示为所有关键字查找次数之和除以总关键字数。假设第 \(i\) 个关键字位于链表中第 \(k_i\) 位，则有: \[ASL_{success}=\frac{\sum k_i}{N}\] 根据前面所建好的哈希表，我们可以逐一统计每个关键字所在的位置并求得最终结果。 ---