69-哈希表的实现

野性酷女 2022-12-26 13:29 90阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
**定义结构体**

#define TABLESIZE 13
    
    typedef int KeyType;//键值的类型
    typedef struct
    {
        
    	KeyType key;//学生信息或者学号
    	//......其他数据成员 姓名
    	//......其他数据成员 
    }DataType;//存储的数据类型
    
    typedef struct Node
    {
        
    	DataType data;
    	struct Node *next;
    }List;
    
    typedef struct Hash
    {
        
    	List *hash_table[TABLESIZE];
    }ListHash;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

**哈希表的实现，Hash函数：除留余数法 用单链表实现**

#incldue"hash.h"
    #include<string.h>
    #include<stdlib.h>
    
    void InitListhash(ListHash *hash)//初始化哈希
    {
        
    	if(hash==NULL) exit(0);
    	for(int i=0;i<TABLESIZE;++i)
    	{
        
    		hash->hash_table[i]=NULL;
    	}
    }
    
    
    static int HashFun(KeyType key)
    {
        
    	return key%TABLESIZE;
    }
    
    static List *AppyNode(DataType val,List *next)//定义新结点
    {
        
    	List *s=(List *)malloc(sizeof(List));
    	if(s==NULL) return NULL;
    	s->data=val;
    	s->next=next;
    	return s;
    }
    
    
    
    bool SearchNot(ListHash *hash,KeyType key)//判断 没有搜索到？
    {
        
    	List *p=hash->hash_table[HashFun(key)];
    	while(p!=NULL)
    	{
        
    		if(p->data.key==key)
    		{
        
    			return false;
    		}
    		p=p->next;
    	}
    	return true;
     } 
     
     
    List *Search(Listhash *hash,KeyType key)//搜索
    {
        
    	List *p=hash->hash_table[HashFun(key)];
    	while(p!=NULL)
    	{
        
    		if(p->data.key==key)
    		{
        
    			return p;
    		}
    		p=p->next;
    	}
    	return NULL;
    }
    
    bool PushListHash(ListHash *hash,DataType val)//放入数据
    {
        
    	if(hash==NULL) exit(0);
    	if(SearchNot(hash,val.key))
    	{
        
    		int index=HashFun(val.key);
    		List *new_node=AppyNode(val,hash->hash_table[index]);
    		if(new_node==NULL) return false;
    		hash->hash_table[index]=new_node;
    		return true;
    	}
    	else
    	{
        
    		return false;
    	}
    }
    
    bool PopListHash(ListHash *hash,KeyType key)//取出数据
    {
        
    	if(hash==NULL) exit(0);
    	List *p=hash->hash_table[HashFun(key)];
    	List *pr=NULL;//前驱
    	while(p!=NULL)
    	{
        
    		if(p->data.key==key)
    		{
        
    			if(pr==NULL)
    			{
        
    				hash->hash_table[HashFun(key)]=p->next;
    			}
    			else
    			{
        
    				pr->next=p->next;
    			}
    			free(p);
    			return true;
    		}
    		pr=p;
    		p=p->next;
    	}
    	return false;
    }
    
    void DestroyListHash(ListHash *hash)//销毁
    {
        
    	if(hash==NULL) exit(0);
    	for(int i=0;i<TABLESIZE;++i)
    	{
        
    		List *p=hash->hash_table[i];
    		while(p!=NULL)
    		{
        
    			hash->hash_table[i]=p->next;
    			free(p);
    			p=hash->hash_table[i];
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d33df9cb3f3c4c9cb90b99bdacc840bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5a6990d9cd6c4f659897f0d14a9c3b2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/f0695672ab4b439a9f960205e60f7a66.png