signed

QiShunwang

“诚信为本、客户至上”

C语言 散列表 分离链接法

2021/6/3 14:08:23   来源:

运行结果正确
怎么说呢,散列表最重要的还是怎么设计散列函数,解决冲突还是很简单的
在这里插入图片描述
完整代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
 //定义链表
 typedef struct list_node *list_point ;
 struct list_node{
 	int val;
 	list_point next;
 };
 //定义散列表
 typedef struct table_node *table_point;
 struct table_node{
 	int table_size;
 	//这里稍微讲一下,这个arr是数组,只是用指针表示罢了 
 	//毕竟指针和数组就是同一个东西嘛 
 	list_point *arr;
 } ;
 void init_table(int table_size,table_point	&t);
 void hash(int val,int table_size,int &result);
 void find(int val,table_point t,list_point	&pos);
 void insert(int val,table_point p);
 void tra(table_point t);
int main(){
	table_point t;
	init_table(10,t);
	insert(77,t);
	insert(67,t);
	insert(57,t);
	list_point pos;
	find(67,t,pos);
	printf("值为67的散列表地址为\n %d\n",pos);
	printf("遍历散列表的结果为\n");
	tra(t);
	return 0;
}
//最简单的映射函数
void hash(int val,int table_size,int &result){
	result=val%table_size;
} 
//初始化散列表
void init_table(int table_size,table_point	&t){
	//初始化表
	 t=(table_point)malloc(sizeof(struct table_node));
	 t->table_size=table_size;
	 //初始化表里的数组
	 t->arr=(list_point*)malloc(table_size*sizeof(struct list_node));
	 //初始化每个数组元素(每个链表) 
	 for(int i=0;i<table_size;i++){
	 	t->arr[i]=(list_point)malloc(sizeof(struct list_node));
 		t->arr[i]->next=NULL;
 	}
	 
} 
//查找
void find(int val,table_point t,list_point	&pos){
	//先计算出哈希码值
	int result;
	hash(val,t->table_size,result);
	//将哈希码对应的链表取出来
	list_point list=t->arr[result];
	//因为链表头不放东西,所以从下一个开始找 
	list_point p=list->next; 
	 //开始找
	 while(p){
 		if(p->val==val){
		 	break;
		 } 
		p=p->next;
 	} 
 	pos=p;
} 
//插入
void insert(int val,table_point p){
	//首先找一下这个val是不是已经有了,有了就不要插进去了
	list_point pos;
	find(val,p,pos);
	if(pos==NULL){
		//新建一个链表节点 
		list_point new1=(list_point)malloc(sizeof(struct list_node));
		//把散列表里的链表也拿出来用
		int result;
		hash(val,p->table_size,result);
		 list_point origin=p->arr[result];
		 //把这个链表节点new1插进 origin
		 new1->next=origin->next;
		 new1->val=val;
		 origin->next=new1;
	} 
	else{
		printf("\n兄弟,这个元素已经有了\n");
		return;
	}
} 
//遍历整个散列表
void tra(table_point t){
	list_point p;
	for(int i=0;i<t->table_size;i++){
		//抓取一个链表
		 p=t->arr[i]->next;
		 //遍历这个链表
		 while(p){
 			printf("%d  ",p->val);
 			p=p->next;
 		} 
 		printf("NULL  \n");
	}
}