2、哈希表的构造与查找 #include <stdio.h> #include <stdlib.h> #define m 13 #define NULLKEY 0 typedef int KeyType; /* 假设关键字为整型 */ typedef struct { KeyType key; }RecordType; typedef RecordType HashTable[m]; int hash(KeyType k) { int h; h = k%m; return h; } int HashSearch( HashTable ht, KeyType K) { int h0; int i; int hi; h0=hash(K); if (ht[h0].key==NULLKEY) return (-1); else if (ht[h0].key==K) return (h0); else /* 用线性探测再散列解决冲突 */ { for (i=1; i<=m-1; i++) { hi=(h0+i) % m; if (ht[hi].key==NULLKEY) return (-1); else if (ht[hi].key==K) return (hi); } return (-1); } } int main() { int i,j; int n; int p; int hj; int k; int result; HashTable ht; for(i=0; i<m; i++) ht[i].key = NULLKEY; printf("请输入哈希表的元素个数:"); scanf("%d",&n); for(i=1; i<=n; i++) { printf("请输入第%d个元素:",i); fflush(stdin); scanf("%d",&p); j = hash(p); if (ht[j].key == NULLKEY) ht[j].key = p; else { for (i=1; i<=m-1; i++) { hj=(j+i) % m; if (ht[hj].key==NULLKEY) { ht[j].key = p; i = m; } } } } printf("请输入要查找的元素:"); fflush(stdin); scanf("%d",&k); result = HashSearch(ht,k); if(result == -1) printf("未找到!\n"); else printf("元素位置为%d\n",result); return 0; }

这段代码实现了一个基于哈希表的查找算法。其中，哈希表的大小为m，关键字为整型。哈希表中的每个元素是一个RecordType类型的结构体，其中只包含了一个整型关键字key。哈希函数hash(k)将关键字映射到哈希表中的一个位置，如果该位置已经被占用，则采用线性探测再散列的方法解决冲突。具体地，如果哈希表位置h0被占用，则依次检查h0+1, h0+2, ..., h0+m-1位置，找到第一个空位置或者关键字等于k的位置返回。如果找不到，则返回-1表示未找到。在main函数中，先读入哈希表的元素个数n和n个元素的值，然后读入要查找的元素k，最后调用HashSearch函数查找k在哈希表中的位置。如果找到，则返回对应位置的下标；否则返回-1表示未找到。