问题描述

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。

基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。

测试数据

取读者周围较熟悉的30个人名。

选作内容

（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

源码

代码在VS中运行会出错，建议在VC或CB中编译（此处使用「线性探测法」实现，可前往查看「链地址法」实现）

#include <stdio.h>
#include <time.h>   //time用到的头文件
#include <stdlib.h> //随机数srand用到的头文件
#include <ctype.h>  //toascii()用到的头文件
#include <string.h> //查找姓名时比较字符串用的头文件
#include <windows.h>
#define HASH_LEN 50 //哈希表的长度
#define P 47        //小于哈希表长度的P
#define NAME_LEN 30 //姓名表的长度

typedef struct //姓名表
{
    char *name;   //名字的拼音
    int hashCode; //拼音所对应的ASCII和
} NAME;

typedef struct //哈希表
{
    char *name; //名字的拼音
    int key;    //拼音所对应的ASCII总和，即关键字
    int si;     //查找长度
} HASH;

NAME Name[HASH_LEN]; //全局定义姓名表,最大长度为50
HASH Hash[HASH_LEN]; //全局定义哈希表，最大长度为50
int i, j;            //全局定义随机数,循环用的i、j

/**
 * 获取姓名的 ASCII 之和
 */
int gethashCode(char *name)
{
    int s = 0;
    for (j = 0; *(name + j) != '\0'; j++)
    {
        s += toascii(*(name + j));
    }
    return s;
}

void InitName()
{ //姓名表的初始化
    Name[0].name = "lvsongxian";
    Name[1].name = "yuanlei";
    Name[2].name = "daiziwen";
    Name[3].name = "chenyonghui";
    Name[4].name = "zhangliang";
    Name[5].name = "liubei";
    Name[6].name = "sunshangxiang";
    Name[7].name = "liyuanfang";
    Name[8].name = "huge";
    Name[9].name = "liuyifei";
    Name[10].name = "anyixuan";
    Name[11].name = "wangbaoqiang";
    Name[12].name = "yangyiming";
    Name[13].name = "hujing";
    Name[14].name = "guowen";
    Name[15].name = "xuyang";
    Name[16].name = "lilu";
    Name[17].name = "shenjinfeng";
    Name[18].name = "xuhui";
    Name[19].name = "huangjing";
    Name[20].name = "guanyu";
    Name[21].name = "chenlong";
    Name[22].name = "huangliang";
    Name[23].name = "liyan";
    Name[24].name = "haojian";
    Name[25].name = "zhangfei";
    Name[26].name = "shuxiang";
    Name[27].name = "sunyingjie";
    Name[28].name = "wangbo";
    Name[29].name = "zhaoqing";
    for (i = 0; i < NAME_LEN; i++) //将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
    {
        Name[i].hashCode = gethashCode(Name[i].name);
    }
}

void CreateHash()
{                                  //建立哈希表
    for (i = 0; i < HASH_LEN; i++) //清空哈希表，未经此操作将储存空数据
    {
        Hash[i].name = "\0";
        Hash[i].key = 0;
        Hash[i].si = 0;
    }
    for (i = 0; i < NAME_LEN; i++)
    {
        int si = 1;                       // 查找长度默认为1
        int adr = (Name[i].hashCode) % P; //除留余数法H(name)=name%P，除数为P=47

        if (Hash[adr].si != 0) //如果冲突，使用线性探测法处理冲突
        {
            int currAddr = adr;
            //从冲突下一个位置开始探测,到达最后一个再从第一个开始
            do
            {
                si++; // 查找长度+1
                adr = (adr + 1) % HASH_LEN;
            } while (Hash[adr].si != 0 && adr != currAddr);

            // 直到回到当前位置时还没找到，说明哈希表已经满了
            if (adr == currAddr)
            {
                printf("哈希表已满\n");
                return;
            }
        }
        Hash[adr].key = Name[i].hashCode;
        Hash[adr].name = Name[i].name;
        Hash[adr].si = si;
    }
}

void DisplayName() //显示姓名表
{
    printf("\n地址 \t\t 姓名 \t\t 关键字\n");
    for (i = 0; i < NAME_LEN; i++)
        printf("%2d %18s \t\t  %d  \n", i, Name[i].name, Name[i].hashCode);
}

void DisplayHash() // 显示哈希表
{
    float asl = 0.0;
    printf("\n\n 地址 \t\t 姓名 \t\t 关键字 \t 搜索长度\n"); //显示的格式
    for (i = 0; i < HASH_LEN; i++)
    {
        printf("%2d %18s \t\t  %d \t\t  %d\n", i, Hash[i].name, Hash[i].key, Hash[i].si);
        asl += Hash[i].si;
    }
    asl /= NAME_LEN; //求得ASL
    printf("\n\n平均查找长度：ASL(%d)=%f \n", NAME_LEN, asl);
}

// 查询
void FindName()
{
    char name[20] = {0};
    int hashCode = 0, si = 1;

    printf("\n请输入想要查找的姓名的拼音:");
    scanf("%s", name);
    getchar();

    hashCode = gethashCode(name); //求出姓名的拼音所对应的ASCII作为关键字
    int adr = hashCode % P;       //除留余数法去地址
    int j = 0;

    // 如果hash地址为空，则直接认为不存在
    if (Hash[adr].key == 0)
    {
        printf("\n没有想要查找的人!\n");
        return;
    }
    // 如果hashCode和name都相等
    if (Hash[adr].key == hashCode && 0 == strcmp(Hash[adr].name, name))
    {
        printf("\n姓名:%s   关键字:%d   地址:%d   查找长度为: 1\n", Hash[adr].name, hashCode, adr);
    }
    // 如果不相等，则进行线性探测搜索
    else
    {
        int currAddr = adr;
        //从冲突下一个位置开始探测,到达最后一个再从第一个开始
        do
        {
            si++; // 查找长度+1
            adr = (adr + 1) % HASH_LEN;
            // 如果找到，直接break跳出循环
            if (Hash[adr].key == hashCode && 0 == strcmp(Hash[adr].name, name))
            {
                printf("\n姓名:%s   关键字:%d   地址:%d   查找长度为:%d\n", Hash[adr].name, hashCode ,adr , si);
                break;
            }
        } while (adr != currAddr);

        // 直到回到当前位置时还没找到，说明不存在
        if (adr == currAddr)
        {
            printf("\n没有想要查找的人!\n");
            return;
        }
    }
}

void view() //交互界面
{
    printf("=======================================================\n");
    printf("=                                                     =\n");
    printf("=                   人名哈希表                        =\n");
    printf("=                                                     =\n");
    printf("=  A: 打印姓名表                 B: 打印哈希表        =\n");
    printf("=                                                     =\n");
    printf("=  C: 查找                       D: 退出程序          =\n");
    printf("=                                                     =\n");
    printf("=======================================================\n");
}

int main() //主函数
{
    char c;
    int a = 1;
    InitName();   //调用初始化姓名表函数
    CreateHash(); //调用创建哈希表函数
    view();       //调用交互界面函数
    while (a)
    {
        printf("\n输入选项:");
        scanf("%c", &c);
        getchar();
        switch (c) //根据选择进行判断，直到选择退出时才可以退出
        {
        case 'A':
        case 'a':
            DisplayName();
            break; //打印姓名表
        case 'B':
        case 'b':
            DisplayHash();
            break; //打印哈希表
        case 'C':
        case 'c':
            FindName();
            break; //调用查找函数
        case 'D':
        case 'd':
            a = 0;
            break; //退出循环，终止程序
        default:
            printf("\n请输入正确的选择!\n");
            break;
        }
    }
    return 0;
}

下一篇：链地址法