热身赛一级赛题1：基于cortex-m3-emulator实现哈希表并测试验证

1. 简介

基于矽璓模拟器cortex-m3-emulator，实现哈希表，支持链地址法解决哈希冲突，并编写测试程序在shell终端打印结果。

2. 数据结构设计说明

（1）用拉链法解决数据冲突，设计两个结构体，一个表示哈希映射的种类，另一个表示每种映射下的冲突值。

//结点结构体
typedef struct LNode
{
    int data;//存储值
    struct LNode *next;
}LNode,*Linklist;

//构建哈希表结构体
typedef struct HashTable
{
    Linklist list;
    int count;//记录该结点下共发生冲突结点个数
}HashTable;

（2）哈希函数的设置,通过余5进行哈希映射

//哈希函数 计算
int Hash(int key)
{
    return key % 5;
}

(3) 哈希表的构建

//初始化哈希表函数
void InitHashTable (HashTable *h)
{
    //初始化链表表头
    h->list=(LNode *)malloc(max * sizeof(LNode));
    h->count=0;

    //初始化
    for(int i=0;i<max;i++)
    {
        h->list[i].data=N;
        h->list[i].next=NULL;
    }
    printf("哈希表已初始化\n");
}

(4) 插入函数的设置，如果哈希映射相同则产生冲突，用拉链发接到后面

//关键字插入函数
void InsertKey(HashTable *h,int key,int i)
{
    //获取下标
    int id=Hash(key);
    printf("\n插入关键字%d,哈希地址=%d\n",key,id);
    //判断是否插入关键字
    if(h->list[id].data==N)
    {
        //未发生冲突
        h->list[id].data=key;
        printf("第%d个数已插入\n",i+1,id);
    }
    else
    {
        //发生冲突，插入新结点
        LNode *node;
        node=(LNode *)malloc(sizeof(LNode));
        node->data=key;
        node->next=h->list[id].next;
        h->list[id].next=node;
        printf("发生冲突，第%d个数已插入\n",i+1,id);
    }
    h->count++;
}

(5)查找函数的设置，先计算在哪个哈希映射里，再从头到尾查找。

//关键字查找
LNode *Search(HashTable h,int key)
{
    int id=Hash(key);
    LNode *head=&h.list[id];//获取头结点
    while(head!=NULL&&head->data!=key)//找到关键字对应结点
    {
        head=head->next;
    }
    return head;

}

(6) 按打表的形式打出哈希表

//打印哈希表
void show(HashTable h)
{
    for(int i=0;i<5;i++)
    {
        printf("%d\t",i);
    }
    printf("\n");
    LNode *node;
    int j=0;
    int count=0;
    int flag=1;
    while(flag)
    {
        flag=0;
        for(int i=0;i<max;i++)
        {
            j=0;
            node=&h.list[i];
            while(j<count&&node)
            {
                node=node->next;
                j++;
            }
            if(node&&node->data!=N)
            {
                printf("%d\t",node->data);
                flag=1;
            }
            else
            {
                printf(" \t");
            }
        }
        count++;
        printf("\n");
    }
}

3. 测试程序说明

本实验输入送过随机值产生，测试结果用打标形式展示。

 srand((unsigned)time(NULL));
    for(int i=0;i<max;i++)
    {
//        scanf("%d",&key);
        key=rand()%100;
        printf("已输入关键字：%d",key);
//        key=i;
        InsertKey(&h,key,i);
    }

4. 运行结果

首先产生10个随机值，将他们膜5运算得到对应的哈希映射，如果发生冲突则接到后面。

之后对结果进行验证，测试数据是否在已建立的哈希表中