[数据结构

2024-07-16 02:08| 来源: 网络整理| 查看: 265

首先是需要定义一个哈希表的结构以及一些相关的常数。其中 HashTable 就是哈希表结构。结构当中的 elem 为一个动态数组。

#define HASHSIZE 12 // 定义哈希表长为数组的长度 #define NULLKEY -32768 // 空关键码 typedef struct { int *elem; // 数据元素存储基址，动态分配数组 int count; // 当前数据元素个数 }HashTable; int m = 0; // 哈希表表长，全局变量一、哈希表基本操作 1.1 初始化操作

有了结构的定义，我们可以对哈希表进行初始化：

// 初始化哈希表 Status initHashTable(HashTable *H) { int i; m = HASHSIZE; H->count = m; H->elem = (int *)malloc(m*sizeof(int)); for (i = 0; ielem[i] = NULLKEY; return TRUE; } 1.2 构造哈希函数操作

为了插入时计算地址，我们需要定义哈希函数，哈希函数可以根据不同情况更改算法。这里我们使用的构造方法为除留余数法：

// 构造哈希函数 int hash(int key) { return key % m; // 构造方法为除留余数法 } 1.3 插入关键字操作

初始化完成后，我们可以对哈希表进行插入操作。假设我们插入的关键字集合就是前面的 {12,67,56,16,25,37,22,29,15,47,48,34}。这里使用开放定址法来避免哈希冲突：

// 插入关键字进哈希表 void insertHash(HashTable *hash, int key) { int addr = hashFun(key); // 求哈希地址 while (hash->elem[addr] != NULLKEY) // 如果不为空，则冲突 { addr = (addr + 1) % m; // 开放定址法的线性探测 } hash->elem[addr] = key; // 直到有空位后插入关键字 } 1.4 查找关键字操作

哈希表存在后，我们在需要时就可以通过哈希表查找要的记录。

// 哈希表查找关键字 Status searchHash(HashTable hash, int key, int *addr) { *addr = hashFun(key); // 求哈希地址，如果后面的hash.elem[*addr] == key，则说明查找成功，直接返回 while (hash.elem[*addr] != key) // 否则，使用开放定址法继续查找 { *addr = (*addr + 1) % m; // 开放定址法的线性探测 // 如果查找到NULLKEY | 循环回到原点，则说明关键字不存在，返回FALSE if (hash.elem[*addr] == NULLKEY || *addr == hashFun(key)) return FALSE; } return TRUE; }

可以看出，查找的代码与插入的代码非常类似，只需做一个不存在关键字的判断而已。

二、完整程序 #include #include #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如TRUE等 */ #define HASHSIZE 12 // 定义哈希表长为数组的长度 #define NULLKEY -32768 // 空关键字 typedef struct { int *elem; // 数据元素存储基址，动态分配数组 int count; // 当前数据元素个数 }HashTable; int m = 0; // 哈希表表长，全局变量 Status initHashTable(HashTable *hash); // 初始化哈希表 // 构造哈希函数 int hashFun(int key); // 初始化哈希表 Status initHashTable(HashTable *hash) { int i; m = HASHSIZE; hash->count = m; hash->elem = (int *)malloc(m*sizeof(int)); for (i = 0; ielem[i] = NULLKEY; return TRUE; } // 构造哈希函数 int hashFun(int key) { return key % m; // 构造方法为除留余数法 } // 插入关键字进哈希表 void insertHash(HashTable *hash, int key) { int addr = hashFun(key); // 求哈希地址 while (hash->elem[addr] != NULLKEY) // 如果不为空，则冲突 { addr = (addr + 1) % m; // 开放定址法的线性探测 } hash->elem[addr] = key; // 直到有空位后插入关键字 } // 哈希表查找关键字 Status searchHash(HashTable hash, int key, int *addr) { *addr = hashFun(key); // 求哈希地址，如果后面的hash.elem[*addr] == key，则说明查找成功，直接返回 while (hash.elem[*addr] != key) // 否则，使用开放定址法继续查找 { *addr = (*addr + 1) % m; // 开放定址法的线性探测 // 如果查找到NULLKEY | 循环回到原点，则说明关键字不存在，返回FALSE if (hash.elem[*addr] == NULLKEY || *addr == hashFun(key)) return FALSE; } return TRUE; } int main() { int arr[HASHSIZE] = {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}; // 要插入关键字 int key = 39; // 关键字 int addr; // 哈希地址 HashTable hash; // 初始化哈希表 initHashTable(&hash); // 插入关键字到哈希表 for (int i = 0; i

【本文地址】

[数据结构

[数据结构

今日新闻

推荐新闻