数据结构课程设计--哈希表实验报告

针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。

福 建 工 程 学 院

课 程 设 计

课程： 算法与数据结构 题目： 哈希表 专业： 网络工程 班级： xxxxxx班 座号： xxxxxxxxxxxx 姓名： xxxxxxx

2011年 12 月 31 日

针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。

实验题目：哈希表

一、 要解决的问题

针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓

名为关键字设计哈希表，并完成相应的建表和查表程序。

基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。

运行的环境：Microsoft Visual C++ 6.0

二、算法基本思想描述

设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，

人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。

三、设计

1、数据结构的设计和说明

（1）结构体的定义

typedef struct //记录 {

NA name; NA xuehao; NA tel; }Record;

录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 {

Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable;

哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。

2、关键算法的设计

（1）姓名的折叠处理

针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。

long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss;

strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++;

printf("\nsum====================%d",sum); return sum; }

（2）建立哈希表

1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m;

n=fold(str); //先将用户名进行折叠处理

m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值

}Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突 { int i,q; i=c/2+1;

while(i<HASHSIZE){ if(c%2==0){ c++;

q=(p+i*i)%HASHSIZE; if(q>=0) return q; else i=c/2+1; } else{

q=(p-i*i)%HASHSIZE; c++;

if(q>=0) return q; else i=c/2+1; } }

return UNSUCCESS; }

void benGetTime();

针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。

void CreateHash1(HashTable* H,Record* a) //建表，以人的姓名为关键字，建立相应的散列表 { int i,p=-1,c,pp;

system("cls"); //若哈希地址冲突，进行冲突处理

benGetTime();

for(i=0;i<NUM_BER;i++){ c=0;

p=Hash1(a[i].name); pp=p;

while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0){

printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出 continue;

} //无法解决冲突，跳入下一循环 }

H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入 H->count++;

printf("第%d个记录冲突次数为%d。\n",i+1,c); //需要显示冲突次数时输出 }

printf("\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count); benGetTime(); }

（3）查找哈希表

void SearchHash1(HashTable* H,int c) //在通讯录里查找姓名关键字，若查找成功，显示信息

{int p,pp;NA str;

system("cls"); //c用来记录冲突次数,查找成功时显示冲突次数

benGetTime();

printf("\n请输入要查找记录的姓名：\n"); scanf("%s",str);

p=Hash1(str); pp=p;

while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1)) pp=collision(p,c);

if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){

printf("\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c); printf("

姓

名

：

%s\n

学

号

：

%s\n

电

话

号

码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);

针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。

}

else printf("\n此人不存在，查找不成功!\n"); benGetTime(); }

（4）显示哈希表

void ShowInformation(Record* a) //显示输入的用户信息 {int i; system("cls");

for( i=0;i<NUM_BER;i++) printf("\n}

（5）主函数的设计

void main(int argc, char* argv[]) {Record a[MAXSIZE];

int c,flag=1,i=0; HashTable *H;

H=(HashTable*)malloc(LEN); for(i=0;i<HASHSIZE;i++){ H->elem[i]=NULL; H->size=HASHSIZE; H->count=0; } while (1) { int num;

printf("\n ");

printf("\n 欢迎使用同学通讯录录入查找系统 "); printf("\n 哈希表的设计与实现");

printf("\n 【1】. 添加用户信息 "); printf("\n 【2】. 读取所有用户信息 …… 此处隐藏：7786字，全部文档内容请下载后查看。喜欢就下载吧 ……