实验八 哈希表问题.docx

HUNANUNIVERSITY程序设计训练报 告实验八：哈希表问题学生姓名 学生学号专业班级指导老师完成日期题目：哈希表问题2一、问题描述2二、问题分析2三、算法分析2四、详细设计2五、调试与测试9六、分析与总结9题目：哈希表问题一、问题描述随机生成一个含有1000个数据的测试数据，数据形式可以如下所示（测试数据不一定要和以下一样，可以自己设计）： Key Value 张三1 张三2 … 李四1 李四2 … 王五1 王五2 … 同时把该数据输出到一个文本文件中，将来用于比对。并使用哈希表存储数据、查找数据。二、问题分析1、使用哈希表存储以上数据（在存储数据时要考虑哈希函数的设计，冲突解决方法等问题）2、使用普通的链表存储以上数据3、比较两者运行时间三、算法分析首先生成1000个目标对象，包括姓名及其幸运数字。生成随机数，并存储于文件中。之后，将姓名进行处理，采用自定义和哈希函数，计算出其下标，并采用开散方法，将数据进行存储。同时采用也将数据构建出链表。查找时，先计算出所需要的下标值，再一次查找，输出对应的幸运数字，之后再用链表方式从头开始查找幸运数字。四、详细设计本题目中，采用哈希表和链表两种方法进行数据的查找。首先定义出1000个姓名；string firstName[10] = { Blue, Brown, White, Lee, Bush, Bruce, James, Hill, Owen, Shaw };string middleName[10] = {Solomon,Walker,Lucy,Jessica,Wendy,Zoe,Sam,Karl,Frank,Gary};string lastName[10] = {Luke,David,Marlin,Jim,Vector,Xavier,Robin,Madeline,Geogre,Sue};定义哈希表节点；class data{public: string key; int luckynum;};定义自己的哈希函数，实现不同姓名的区别存储； int HashFunction(string r){ int i; int sum=0; for(i=0; ir.length(); i++) sum+=i*(int)r[i]; return (sum) % 1000;}1000组随机数据随机生成，伴随在每一个姓名后面作为幸运数字，再保存到相应的文件中； void save(){ cout 正在计算每位成员的幸运数字中... endl; srand((unsigned)time(NULL));//用于产生随机数,生成成员幸运数字 //data tempData; ofstream out(E:\\LuckyNumber.txt); int idx = 0; for (int i = 0; i 10; i++) { for (int j = 0; j 10; j++) for (int k = 0; k 10; k++) { //数据生成 Data[idx].key = lastName[i]+· + middleName[j] +·+ firstName[k]; Data[idx].luckynum = rand() % 1000+1000; //将数据存于文件中 if (out.is_open()) { out Data[idx].key; out ; out Data[idx].luckynum; out endl; } idx++; } } out.close(); cout 每位成员幸运数字已生成完毕，存贮与E:\\LuckyNumber.txt endl;}构建哈希表，将每个位置的值放到合适位置，如果发生冲突，则向后放置； void putda