实验九 哈希表的查找操作

一、实验目的
1．掌握哈希表、哈希函数与哈希冲突的概念。
2．掌握哈希表的构造方法及其计算机的表示与实现。
3．掌握哈希表查找算法的实现。
二、实验内容
1．以开放地址法中的线性探测再散列法处理冲突，实现哈希表的建立、查找和插入操作。
2．以链地址法，也叫拉链法处理冲突，实现哈希表的建立，查找和插入操作。

三、实验要求
1．以开放地址法中的线性探测再散列法处理冲突，实现哈希表的建立查找和插入操作。
（1）设哈希表长为20，用除留余数法构造一个哈希函数。
（2）输入哈希表中记录的个数n(n<=20）和各记录的关键字值，然后以开放地址法中的线性探测再散列法作为解决冲突的方法，建立一个开放地址哈希表，并输出已经建立的哈希表。
（3）输入一个待查找记录的关键字key，完成开放地址哈希表的查找操作，如果查找成功，则函数返回查找到的记录在哈希表中的位置值，否则给出查找失败的提示信息。

2．以链地址法，也叫拉链法处理冲突，实现哈希表的建立，查找和插入操作。
（1）设哈希表长为13，用除留余数法构造一个哈希函数。
（2）输入哈希表中记录的个数12和各记录的关键字序列(19,14,23, 01,68,20,84,27,55,11,10,79),然后以链地址法或叫拉链法作为解决冲突的方法，建立一个链地址哈希表,并输出已经建立的哈希表。
（3）输入一个待查找记录的关键字key，完成链地址哈希表的查找操作，如果查找成功，则函数返回查找到的记录在哈希表中的位置值，否则给出查找失败的提示信息。
四、详细程序清单

//1.哈希表_线性探测再散列 
#include<stdio.h>
#include<stdlib.h>

#define HASHSIZE 20//定义哈希表长
#define M 19 //定义除留余数法中的质因数
#define SUCCESS 1//查找成功 
#define UNSUCCESS 0//查找失败 
#define DUPLICATE -1//表中已有与e有相同关键字的元素

typedef int Keytype;
typedef struct {
  Keytype key;
  int other;
}Elemtype;
typedef struct {
  Elemtype r[HASHSIZE];
  int length;
}Hashtable;

int p;//哈希地址 

int Hash(int k)//哈希函数 
{
    p=k%M;
    return p;
}

int SearchHash(Hashtable H,Keytype K)//查找 
{
    p=Hash(K);  //求得哈希地址
    while(H.r[p].key!=NULL&&K!=H.r[p].key)
    p=(p+1)%M;//线性探测再散列处理冲突 
    if (K==H.r[p].key) return SUCCESS;//查找成功 
    else return UNSUCCESS;//查找失败 
} 

int InsertHash(Hashtable &H,Elemtype e)//插入 
{
    if(SearchHash(H,e.key)==SUCCESS)
    return DUPLICATE;//表中已有与e有相同关键字的元素
    H.r[p].key=e.key;
    ++H.length; 
}

void CreateHashTable(Hashtable &H,int n)//创建哈希表
{
    Elemtype e;
    int flag; 
    printf("输入各元素：");
    while(n--)
    {
        scanf("%d",&e.key);
        flag=InsertHash(H,e);
        if(flag==DUPLICATE) 
        {
            printf("有重复值，重新输入\n");
            n++; 
        }
    }   
}

void Show(Hashtable H,int n)//输出哈希表 
{
    printf("哈希表为（*代表空值）：\n");
    printf(" =============================================================\n丨");
    for(int i=0;i<HASHSIZE;i++)
    printf("%2d ",i);
    printf("丨\n丨");
    for(int i=0;i<HASHSIZE;i++)
    {
        if(H.r[i].key!=NULL)
        printf("%2d ",H.r[i].key);
        else printf(" * ");
    }
    printf("丨\n =============================================================\n");
}

int main()
{
    int n;
    Keytype e;
    Hashtable H;
    Elemtype x;
    for(int i=0;i<HASHSIZE;i++) H.r[i].key=NULL;//初始化哈希表 
    printf("输入关键字个数：");
    scanf("%d",&n);
    CreateHashTable(H,n);
    Show(H,n);
    while(1)
    {
        printf("输入要查找的值：");
        scanf("%d",&e);
        if(SearchHash(H,e)) printf("查找成功，位置为%d\n",p);
        else printf("查找失败\n");
        printf("输入要插入的值：");
        scanf("%d",&x);
        InsertHash(H,x); 
        Show(H,n);
    }
}

//2.哈希表_链地址法 
#include<stdio.h>
#include<stdlib.h>

#define M 13//定义除留余数法中的质因数
#define HASHSIZE 13 //定义哈希表长

typedef int Keytype;  
typedef struct hnode{
    Keytype  key;
    struct hnode *next;
}Hnode,*Hlink;//链表中的结点类型
Hlink head[HASHSIZE]; //静态数组，定义哈希表类型
int p;//哈希地址 

int Hash(int k)//哈希函数 
{
    int p;
    p=k%M;
    return p;
}

void InsertHashLink(Keytype e)//插入 
{
    Hlink t;
    int i;
    t=(Hlink)malloc(sizeof(hnode));  
    t->key=e;
    t->next=NULL;
    i=Hash(e);
    if(head[i]->key==NULL)
    {
        head[i]=t;  
    }
    else
    {
        t->next=head[i];
        head[i]=t;  
    }
}

void CreateHashLink(int n)////创建哈希表,头插法 
{
    Hlink t;
    Keytype e;
    int i;
    printf("请输入元素：");
    while(n--)
    {
        scanf("%d",&e);
        InsertHashLink(e);
    }
}

void Show()//输出哈希表
{
    Hlink t;
    for(int i=0;i<=HASHSIZE;i++)
    {
        t=head[i];
        printf("%2d：",i);
        while(t!=NULL)
        {
            if(t->key==NULL) break;
            printf("%d->",t->key);
            t=t->next;
        }
    printf("NULL\n");
    }   
}

void SearchHashLink(Keytype K)//查找
{
    Hlink t;
    for(int i=0;i<=HASHSIZE;i++)
    {
        t=head[i];
        while(t!=NULL)
        {
            if(t->key==K)
            {
                printf("查找成功，位置在第head[%d]中\n",i);
                return;
            }
            t=t->next;
        }
    }
    printf("查找失败\n");
}

int main()
{
    int n,p;
    Keytype e;
    for(int i=0;i<=HASHSIZE;i++)//初始化
    {
        head[i]=(Hlink)malloc(sizeof(hnode));  
        head[i]->key=NULL; 
        head[i]->next=NULL;
    } 
    printf("输入关键字个数：");
    scanf("%d",&n);
    CreateHashLink(n);
    printf("哈希链表为：\n");
    Show();
    while(1)
    {
        printf("输入要查找的值：");
        scanf("%d",&e);
        SearchHashLink(e);
        printf("输入要插入的值：");
        scanf("%d",&e);
        InsertHashLink(e);
        Show();     
    }
}

五、程序运行结果

1.哈希表_线性探测再散列

2.哈希表_链地址法

六、实验心得体会
1.用除留余数法构造哈希函数不是一个好方法，冲突次数太多。书上写的如果冲突次数大于表长一半就要重建哈希表（我没写这个）。
2.用线性探测再散列法解决冲突也不是一个很好的方法，比较次数有可能很多，在查找时会增加麻烦。
3.链地址法有点像邻接表，创建表我是用的单链表的头插法。
4.刚开始学《数据结构》的时候，觉得里面写的都是伪代码，后来逐渐觉得这就是C语言代码，比如开始不能理解为什么函数返回OK、UNSUCCESS之类的而不是返回0、1数值？为什么要先typedef int Keytype;再 Keytype key;而不是直接int key;？后来我才逐渐理解、认可这种可读性高的写法并且学习，这次就是使用的这种写法。这也许就是代码风格的提升吧。
5.我感觉我输出的哈希表还是挺直观、好看的。