嵌入式学习-数据结构-Day6

Day6

思维导图

哈希

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node
{
        //数据元素
        int data;
        //指针域：下一个节点的地址
        struct Node *next;
}*node;

//  计算小于等于m的最大质数
int Prime(int m)
{
        for(int i=m;i>=2;i--)
        {
                //判断i是否是素数
                //12: 2 3  4 6
                int flag=1;
                for(int j=2;j<=sqrt(i);j++)
                {
                        if(i%j==0)
                        {
                                flag=0;
                                break;
                        }
                }
                if(flag==1)
                        return i;
        }
}
 // 创建节点
node create_node()
{
        node s=(node)malloc(sizeof(struct Node));
        if(NULL==s)
                return NULL;
        s->data=0;
        s->next=NULL;
        return s;
}
// 插入哈希表
void insert_hash(node hash[],int key,int p)
{
        int index=key%p;
        //插入到hash[index]为头指针的单链表中

        //创建新节点
        node s=create_node();
        if(NULL==s)
                return;
        s->data=key;
        if(hash[index]==NULL)
                hash[index]=s;
        else
        {
                s->next=hash[index];
                hash[index]=s;
        }
}
// 循环输出哈希表
void output(node hash[],int m)
{
        for(int i=0;i<m;i++)
        {
                //hash[i]类似单链表的head
                printf("%d:",i);
                node q=hash[i];
                while(q!=NULL)
                {
                        printf("%-4d",q->data);
                        q=q->next;
                }
                puts("NULL");
        }
}
 // 哈希查找
int search_hash(node hash[],int key,int p)
{
        int index=key%p;
        //查找hash[index]该链表中是否存在查找元素key
        node q=hash[index];
        if(q==NULL)
                return -1;
        while(q!=NULL)
        {
                if(q->data==key)
                        return 0;
                q=q->next;
        }
        return -1;
}
int main(int argc, const char *argv[])
{
        //数组
        int arr[]={41,54,67,25,51,8,22,26,11,16};

        //把数组元素通过哈希函数存到哈希表
        //哈希表
        //数组长度
        int len=sizeof(arr)/sizeof(arr[0]);
        //哈希表长度
        int m=len*4/3;
        int p=Prime(m);
        node hash[m];
        //防止野指针
        for(int i=0;i<m;i++)
        {
                hash[i]=NULL;
        }

        //把数组存储到哈希表
        for(int i=0;i<len;i++)
        {
                insert_hash(hash,arr[i],p);
        }

        //遍历哈希表
        output(hash,m);

        //查找
        int key;
        printf("plase enter key:");
        scanf("%d",&key);
        int flag=search_hash(hash,key,p);
        if(flag==-1)
                puts("unexists");
        else
                puts("exists");
        return 0;
}

运行