数据结构学习——6

一、哈夫曼树

二、图

三、算法——查找

HASH表

散列存储——（HASH实现）保留除数法（取余法）

Hash表具体实现

hash.h

/*===============================================
*   文件名称：hash.h
*   创 建 者：青木莲华 
*   创建日期：2025年08月01日
*   描    述：hash表实现
================================================*/
#ifndef __HASH_H__
#define __HASH_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_h;
typedef struct
{
    data_h *data;
    int length;         //长度
    int p;              //质数
}hash_t;

//init
hash_t *hash_init(int m);
//最大质数
int big_prime(int m);
//create
int hash_create(hash_t *hp,int arr[],int n);
//show
void hash_show(hash_t *hp);
//search
int hash_search(hash_t *hp,int key);
#endif

hash.c

/*===============================================
*   文件名称：hash.c
*   创 建 者：青木莲华 
*   创建日期：2025年08月01日
*   描    述：Hash实现
================================================*/
#include "hash.h"
//init
hash_t *hash_init(int m)
{
    hash_t *hp = (hash_t *)malloc(sizeof(hash_t));
    if(hp == NULL)
        return NULL;
    int len = (int)m / 0.75;                //根据长度扩充Hash表大小

    hp->length = len;
    //printf("len = %d\n",hp->length);
    hp->p = big_prime(m);
    //printf("p = %d\n",hp->p);

    hp->data = (data_h *)malloc(sizeof(data_h) * hp->length);
    if(hp->data == NULL)
    {
        free(hp);
        return NULL;
    }
    for(int i = 0 ; i < len ;i++)
        hp->data[i] = -1;
    return hp;
}
//最大质数
int big_prime(int m)
{
    int i;
    for(; m > 1 ; m--)
    {
        for(i = 2 ; i < m ; i++)
            if(m % i == 0)
                break;
        if(m == i)
            return m;
    }
    return 0;
}

//create
int hash_create(hash_t *hp,int arr[],int n)
{
    int i,hash_val;
    for(i = 0 ; i < n ; i++)
    {
        hash_val = arr[i] % hp->p;
        while(hp->data[hash_val] != -1)
        {
            hash_val = (hash_val + 1) % hp->length;
        }
        hp->data[hash_val] = arr[i];
        printf("insert : arr[%d] = %d ----->  hash[%d] = %d\n",
                i,arr[i],hash_val,hp->data[hash_val]);
    }
    return 1;
}
//show
void hash_show(hash_t *hp)
{
    int i = 0;
    for(; i < hp->length ; i++)
    {
        if(hp->data[i] != -1)
            printf("hash[%d] = %d\t",i,hp->data[i]);
        if((i+1) % 4 == 0)
            printf("\n");
    }
}
//search
int hash_search(hash_t *hp,int key)
{
    int count,hash_val = key % hp->p;
    while(hp->data[hash_val] != key && count < hp->length)
    {
        hash_val = (hash_val + 1) % hp->length;
        count++;
    }
    if(hp->data[hash_val] == key)
    {
        printf("Success ，hash_val = %d\n",hash_val);
        return hash_val;
    }
    else
    {
        printf("Not found!\n");
        return -1;
    }
}

main.c

/*===============================================
*   文件名称：main.c
*   创 建 者：青木莲华 
*   创建日期：2025年08月01日
*   描    述：Hash实现
================================================*/
#include "hash.h"

int main(int argc, char *argv[])
{ 
    int arr[15] = {15,67,44,32,18,
                   11,74,26,55,89,
                   93,54,41,65,9};
    hash_t *hp = hash_init(15);  
    hash_create(hp,arr,15);
    hash_show(hp);
    hash_search(hp,100);
    hash_search(hp,74);
    return 0;
} 

运行截图