哈希表---C语言实现

哈希的基本理解---按照某种函数存储地址

冲突问题：

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define SIZE 20

struct 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);  //key%SIZE

   //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 table

      hashIndex %= 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 cell

   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1){

      //go to next cell

      ++hashIndex;

      //wrap around the table

      hashIndex %= 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 empty

   while(hashArray[hashIndex] != NULL){

      if(hashArray[hashIndex]->key == key){

         struct DataItem* temp = hashArray[hashIndex];

         //assign a dummy item at deleted position

         hashArray[hashIndex] = dummyItem;

         return temp;

      }

      //go to next cell

      ++hashIndex;

      //wrap around the table

      hashIndex %= SIZE;

   }       

   return NULL;       

}

// 显示所示数据项

void display(){

   int i = 0;

   for(i = 0; i<SIZE; i++) {

      if(hashArray[i] != NULL)

         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);

   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");

   }

}

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/82356679