(H)哈希散列问题.doc

实验七 哈希散列问题 需求分析 （1） 根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n = 5000。余下n行，每行一个字符串。表示已存在的图书记录。 第二部分，第一行是行数m，m = 1000。余下m行，每行一个字符串。表示要查询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出YES,如果不存在则输出NO。 概要设计 抽象数据类型 算法思想 基于的基本操作来实现问题 输入分为两部分 第一部分，第一行是行数n，n = 5000。余下n行，每行一个字符串。表示已存在的图书记录。 第二部分，第一行是行数m，m = 1000。余下m行，每行一个字符串。表示要查询的图书记录。 输出模块：输出为m行，如果被查的记录存在，则输出YES,如果不存在则输出NO。 。 算法流程 请输入要存储的书籍数目：//提示 等待输入 输出 //提示”YES”或“NO” 输入输出格式 输入： 4 a ans and hellocpp 9 a b an as ans and ande hellocbb hellocpp 输出： YES NO NO NO YES YES NO NO YES： 测试结果 五、#includeiostream #includestring using namespace std; //定义哈希散列函数 unsigned int hash_BKDE(char *str) { unsigned int seed = 131; unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash 0x7FFFFFFF)%5000; } //在主程序中存储元素并查找元素 int main() { int n; int i; int hash_num; //一个5000行100列的二维字符数组，保存存入的书籍名 char library[5000][100]; for(i=0;i5000;i++) strcpy(library[i],NULL); cout请输入要存储的书籍数目：; cinn; for(i=0;in;i++){ char name[100]; //输入一个字符串 cinname; //根据哈希函数算出映射值 hash_num=hash_BKDE(name); //如果该位置为空，则直接存入 //coutstrcmp(library[hash_num],NULL)endl; if(!strcmp(library[hash_num],NULL)) strcpy(library[hash_num],name); //否则找一个空的位置 else{ while(hash_num5000strcmp(library[++hash_num],NULL)) {cout(library[++hash_num]!=NULL)endl;}; //如果超出数组范围，则存储失败 if(hash_num==5000) cout存储失败endl; else {strcpy(library[hash_num],name);} } } //查找 //一个1000行的100列的二维数组，用来存储要查询的书籍名 char search[1000][100]; cout请输入要查找书籍的数目：; cinn; for(i=0;in;i++) { //输入一个字符串 cinsearch[i]; } //在library中查找 cout输出:endl; for(i=0;in;i++) { //获取映射值 hash_num=hash_BKDE(search[i]); //如果在library中为空，则为no if(!strcmp(library[hash_num],NULL)) coutNOendl; else {//如果不为空，判断是否相等 if(!strcmp(library[hash_num],search[i])) coutYESendl;