数据结构8-哈希表

数据结构8-哈希表

1. 动态分配内存方式：

#include <stdio.h>
#include <stdlib.h>#define SIZE 20struct DataItem {int data;   int key;
};struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;//获取键值
int hashCode(int key) {return key % SIZE;
}//查找
struct DataItem *search(int key) {//get the hash int hashIndex = hashCode(key);  //move in array until an empty while(hashArray[hashIndex] != NULL) {if(hashArray[hashIndex]->key == key)return hashArray[hashIndex]; //go to next cell++hashIndex;//wrap around the tablehashIndex %= SIZE;}        return NULL;        
}//插入
void insert(int key,int data) {struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));item->data = data;  item->key = key;//get the hash int hashIndex = hashCode(key);//move in array until an empty or deleted cellwhile(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {//go to next cell++hashIndex;//wrap around the tablehashIndex %= SIZE;}hashArray[hashIndex] = item;
}//删除
struct DataItem* delete(struct DataItem* item) {int key = item->key;//get the hash int hashIndex = hashCode(key);//move in array until an emptywhile(hashArray[hashIndex] != NULL) {if(hashArray[hashIndex]->key == key) {struct DataItem* temp = hashArray[hashIndex]; //assign a dummy item at deleted positionhashArray[hashIndex] = dummyItem; return temp;}//go to next cell++hashIndex;//wrap around the tablehashIndex %= SIZE;}      return NULL;        
}//打印全部
void display() {int i = 0;for(i = 0; i < SIZE; i++) {if(hashArray[i] != NULL && hashArray[i]->key != -1) {printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);} else {printf(" ~~ ");}}printf("\n");
}
//主函数
int main() {dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));dummyItem->data = -1;  dummyItem->key = -1; insert(1, 20);insert(2, 70);insert(42, 80);insert(4, 25);insert(12, 44);insert(14, 32);insert(17, 11);insert(13, 78);insert(37, 97);insert(21, 88);display();item = search(37);if(item != NULL) {printf("Element found: %d\n", item->data);} else {printf("Element not found\n");}delete(item);item = search(37);if(item != NULL) {printf("Element found: %d\n", item->data);} else {printf("Element not found\n");}item = search(1);printf("Element found: %d\n", item->data);item = search(21);printf("Element found: %d\n", item->data);
}

2.数组方式

#include <stdio.h>
#include <stdlib.h>#define SIZE 10
#define EMPTY -1struct DataItem {int data;   int key;
} hashArray[SIZE];// Initialize the hash table
void init()
{int i;for (i = 0; i < SIZE; i++) {hashArray[i].key = EMPTY;}
}int hashCode(int key) {return key % SIZE;
}void insert(int key,int data) {int i=0;struct DataItem item;item.data = data;  item.key = key;int hashIndex = hashCode(key);while (hashArray[hashIndex].key != EMPTY) {// Go to next cell++hashIndex;// Wrap around the tablehashIndex %= SIZE;if(i++ > SIZE){printf("data inset full-- key:%d,data:%d error\r\n",key,data);break;}}hashArray[hashIndex] = item;
}struct DataItem *search(int key) {int hashIndex = hashCode(key);  while (hashArray[hashIndex].key != key) {// Go to next cell++hashIndex;// Wrap around the tablehashIndex %= SIZE;}return &hashArray[hashIndex];
}void display() {int i;for(i = 0; i<SIZE; i++) {if (hashArray[i].key != EMPTY){printf(" (%d,%d)",hashArray[i].key,hashArray[i].data);} else {printf(" ~~ ");}}printf("\n");
}int main() {init();insert(1, 20);insert(2, 70);insert(42, 80);insert(4, 25);insert(12, 44);insert(14, 32);insert(17, 11);insert(13, 78);insert(37, 97);insert(11, 1);insert(21, 3);display();struct DataItem *item;item = search(37);if(item != NULL) {printf("Element found: %d\n", item->data);} else {printf("Element not found\n");}item = search(2);printf("Element found: %d\n", item->data);item = search(12);printf("Element found: %d\n", item->data);return 0;
}