C语言实现哈希表

C语言实现哈希表

哈希表

1、哈希表的创建

#define MAX 10
#define NULL_KEY -1
typedef int data_type;
typedef struct{
  data_type *ele;
  int n;

}hash_table;

hash_table *create_hash_table(){
hash_table * ht=(hash_table *)malloc(sizeof(hash_table));
ht->n=0;
ht->ele=(data_type *)malloc(sizeof(data_type)*MAX);
for(int i=0;i<MAX;i++){
  ht->ele[i]=NULL_KEY;
}
return ht;
}

2、判满

int is_full(hash_table *ht){
  return ht->n==MAX?1:0;
}

3、使用开放地址法解决冲突

void insert_hash_table(hash_table *ht,data_type key){
  if(is_full(ht)){
  printf("hash is full\n");
      return;
  }
  int index=key%MAX;
  while(ht->ele[index]!=NULL_KEY){
      index=(index+1)%MAX;
  }
  ht->ele[index]=key;
  ht->n++;
  return;
}

4、查找key

int search_hash_key(hash_table *ht,data_type key){
int index=key%MAX;
while(ht->ele[index]!=key){
  index=(index+1)%10;
  //找了一圈没找到,或者找到-1了
  if(index==key%MAX||ht->ele[index]==NULL_KEY){
      return -1;
  }
}
return index;

}

5、遍历哈希表

void print_hash(hash_table *ht){
  for(int i=0;i<MAX;i++){
      printf("%d ",ht->ele[i]);
  }
  return;
}

6、使用链地址法

#define MAX 7
typedef int data_type;

typedef struct node{
    struct node *next;
    data_type data;
}hash_node;
//二重指针是用来存放指针的地址
//使用指针数组(二重指针)保存
hash_node **create_hash_table(){
  hash_node **ht=(hash_node **)malloc(sizeof(hash_node *)*MAX);
  memset(ht,0,sizeof(hash_node *)*MAX);
  for(int i=0;i<MAX;i++){
      ht[i]=NULL;
  }
  return ht;
}
//插入数据
void insert_hash_data(hash_node **h,data_type key){
  int index=key%MAX;
  hash_node **p=NULL;
  hash_node *temp=NULL;
for(p=&h[index];*p !=NULL;p=&((*p)->next)){
    if((*p)->data>key){
      break;
      }
  }
  temp=(hash_node *)malloc(sizeof(hash_node));
  temp->data=key;
  //*p是前一个节点的next里面存放的地址
  temp->next=*p;
  *p=temp;
  return;

}

void printf_hash_table(hash_node **h){
  int i=0;
  hash_node **p=NULL;
  for(int i=0;i<MAX;i++){
      printf("index=%d :",i);
      for(p=&h[i];*p!=NULL;p=&((*p)->next)){
          printf("%d ",(*p)->data);
      }
      putchar('\n');
  }
  return;
}
THE END
喜欢就支持一下吧
点赞14 分享
评论 共1条
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片