数据结构实验十三

   1．掌握什么是哈希表和哈希函数。

   2．掌握哈希表的构建和哈希查找。

二、实验环境

   1．硬件：每个学生需配备计算机一台。操作系统：DOS或Windows：

   2．软件：DOS或Windows操作系统+Turbo C；

三、实验要求

   1．设计一个哈希表。哈希函数用除留余数法构造，用线性探测再散列处理冲突。

2．学生成绩报告单。任给任一学生学号即可打印出该生的成绩报告单。

3．学生学号可以不按照顺序。

四、实验内容

   1．在自己的U盘的“姓名+学号”文件夹中创建“实验13”，本次实验的所有程序和数据都要求存储到本文件夹中。

   2．现在某个学院有20名同学，每个同学记录包括：班级、学号、姓名和语文、数学、外语等三门课程成绩（学号为了2位整数）。

   3．以学号为主关键字，用除留余数法构造哈希函数（请先考虑除数P的选择原则是什么？），用线性探测再散列处理冲突构建哈希表。

   4．输入任何一个学生学号，输出该学生的信息。

   5．说明线性探测再散列处理的优缺点，用链地址法在实现。

五、代码如下

#include

#include

#include

#include

#define EQ(a,b) (a==b)

int hashsize[]={3,11,19,29,37};

//哈希表容量递增表，一个合适的素数序列,这里选择是三个元素，不做更多的纠缠

int m;//m的选择必须是不大于表长的最大素数

//数据元素定义

typedef struct {

    int number;

    char Class[10];

    char name[10];

    int chinese;

    int math;

    int english;

}student;

//哈希表

typedef struct{

    student *elem;     //数据元素存储基址，动态分配数组

    int count;         //当前数据元素的个数

    int sizeindx;      //当前的容量

}hashtable;

//hash函数

unsigned  Hash(int k){

    return k%m;  //除留余数法，除以的是一个不大于表长最大素数

}

//增量序列函数

int d(int i){

    return i;//线性探测再散列

}

//冲突处理方法

void ylx_collision(int k,int *p,int i){

    *p=(Hash(k)+d(i))%m;

}

//初始化函数

void  ylx_InitHashTabke(hashtable * H){

    int i;

H->count=0;

H->sizeindx=0;

    m=hashsize[0];

H->elem=(student*)malloc(m*sizeof(student)); //分配内存

    if(!H->elem)

        exit(0);

for(i=0;i     H->elem[i].number=0;//表示还未开始添加数据

}

//查找函数

int  ylx_search(hashtable h,int num,int *p,int *c){

    //在开放的哈希表中查找关键字为num的元素，假如成功，以p指示待查的数据元素

    //在表中的位置，并且返回状态，否则以p指示插入的位置，c记录冲突的位置，以供插入的时候参考

    *p=Hash(num);//求出哈希地址

    while(h.elem[*p].number!=0&&!EQ(num,h.elem[*p].number)){//该位置有记录，并且不等于等待查数据    

        (*c)++;//冲突加一

        if(*c            ylx_collision(num,p,*c);//求下一个探查地址

        }else break;

    }

    if(EQ(num,h.elem[*p].number))

        return 1;

    else return 0;

}

//对函数需要声明，下面需要用到

void  ylx_recreateHashTable(hashtable * h);

//插入函数，查找不成功，就插入元素到哈希表中，假如冲突过大，则重新建立哈希表

int ylx_InsertHash(hashtable *h,student e){

    int p,c=0;

    if(ylx_search(*h,e.number,&p,&c)){

        return -1;

    }

else if(csizeindx]/2){

     h->elem[p]=e;

     ++h->count;

        return 1;

    }

    else {//还未找到，但是冲突已经过大了

        ylx_recreateHashTable(h);//重建

        return 0;

    }

}

//重建哈希表函数

void  ylx_recreateHashTable(hashtable * h){

int i,count=h->count;

    student * p,*elem=(student*)malloc(count*sizeof(student));

    //动态生成存放哈希表的原有数据的存储空间

    p=elem;

for(i=0;i     if((h->elem+i)->number!=0)

         *p++=*(h->elem+i);

    }

h->count=0;

h->sizeindx++;

m=hashsize[h->sizeindx];

h->elem=(student*)realloc(h->elem,m*sizeof(student));//以新的存储容量存储表

    //还未填写记录的标志

    for(i=0;i     h->elem[i].number=0;

    //将原有的数据重新填写进去

    for(p=elem;p        ylx_InsertHash(h,*p);

    free(elem);//释放空间

}

///按照哈希地址遍历哈希表

void ylx_traversehash(hashtable h){

    int i;

    printf("哈希地址：0~~~~~~~%d\\n",m-1);

for(i=0;i        if(h.elem[i].number!=0){

            printf("学号：%d  班级：%s  姓名：%s  语文：%d  数学：%d  英语:%d   ",h.elem[i].number,h.elem[i].Class,h.elem[i].name,h.elem[i].chinese,h.elem[i].math,h.elem[i].english);

        }

    }

}

void main(){

    printf("开始输入数据：\n");

    printf("请输入您所需要的数据的个数：\n");

    int n;

    scanf("%d",&n);

    hashtable h;

    ylx_InitHashTabke(&h);

for(int i=0;i        student ss;

        printf("请输入插入的记录的学号，班级，姓名，语文成绩，数学成绩，和英语成绩\n");        scanf("%d%s%s%d%d%d",&ss.number,ss.Class,ss.name,&ss.chinese,&ss.math,&ss.english);

        ylx_InsertHash(&h,ss);

    }

    ylx_traversehash(h);

}

六、运行结果截图

七、实验总结与体会

    本次实验需要我们理解哈希函数和哈希表，掌握各种哈希函数和冲突解决办法，还需要我们掌握什么是哈希表和哈希函数，掌握哈希表的构建和哈希查找。