哈希表题目集
哈希表都是用来快速判断一个元素是否出现集合里。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define HASH_SIZE 2000003 int hashtable[HASH_SIZE]; int occupied[HASH_SIZE]; int hash(int x) { return (x%HASH_SIZE+HASH_SIZE)%HASH_SIZE; } void insert(int x) { int idx=hash(x); while(occupied[idx]) { if(hashtable[idx]==x) { return; } idx=(idx+1)%HASH_SIZE; } hashtable[idx]=x; occupied[idx]=1; } int query(int x) { int idx=hash(x); while(occupied[idx]) { if(hashtable[idx]==x) return 1; idx=(idx+1)%HASH_SIZE; } return 0; } int main(int argc, char *argv[]) { int q; scanf("%d",&q); memset(occupied,0,sizeof(occupied)); while(q--) { char op[2]; int x; scanf("%s %d",op,&x); if(op[0]=='I') insert(x); else if(op[0]=='Q') { if(query(x)) printf("Yes\n"); else printf("No\n"); } } return 0; }#include <stdio.h> #include <stdlib.h> #include <string.h> #define HASH_SIZE 20011 typedef struct Node { char* key; struct Node* next; } Node; Node* hashTable[HASH_SIZE]; // 哈希函数 unsigned int hash(const char* str) { unsigned int h = 0; while (*str) { h = h * 131 + (*str++); } return h % HASH_SIZE; } // 插入并返回是否是新元素 int insert(const char* str) { unsigned int index = hash(str); Node* p = hashTable[index]; // 查找是否已存在 while (p) { if (strcmp(p->key, str) == 0) { return 0; } p = p->next; } // 插入新节点 Node* new_node = (Node*)malloc(sizeof(Node)); if (!new_node) return 0; new_node->key = (char*)malloc(strlen(str) + 1); if (!new_node->key) { free(new_node); return 0; } strcpy(new_node->key, str); new_node->next = hashTable[index]; hashTable[index] = new_node; return 1; } int main() { int n; scanf("%d", &n); // 初始化哈希表 for (int i = 0; i < HASH_SIZE; i++) { hashTable[i] = NULL; } int count = 0; // 分配缓冲区 char* buffer = (char*)malloc(2000001); if (!buffer) { printf("0\n"); return 1; } for (int i = 0; i < n; i++) { scanf("%s", buffer); count += insert(buffer); } printf("%d\n", count); // 释放内存 for (int i = 0; i < HASH_SIZE; i++) { Node* p = hashTable[i]; while (p) { Node* temp = p; p = p->next; free(temp->key); free(temp); } } free(buffer); return 0; }