哈希查找的实现与分析报告(顺序).docx.docx

目 录1 课程设计内容11.1 课程设计目的11.2 课程设计要求11.3 课程设计背景12 概要设计22.1 程序模块结构图22.2 主界面模块说明22.3读取学生信息模块说明23 详细设计33.1 建立哈希表33.2计算哈希值33.3读取文件43.4显示所有学生信息63.5查找学生信息73.6界面显示93.7主函数104 问题与解决12小 结13参考文献131 课程设计内容1.1 课程设计目的课程设计题目：哈希查找的实现与分析（1）掌握哈希函数的构造原则及哈希表的生成方法，并能在解决实际问题时灵活应用。（2）掌握哈希查找的基本过程及其适用场合。（3）巩固在散列查找时解决冲突的方法，并比较各种方法的特点。（4）掌握平均查找长度ASL的计算方法。1.2 课程设计要求程序要求实现的功能有：（1）所有数据从文本文件Hash.txt中读取。（2）根据实际问题自行构造合理的哈希函数，要求采用开放定址法或拉链法，解决Hash表的冲突。（3）严格按照哈希表构造的一般原则进行编程（不能简单地将文件中的数据读到一个数组里，再从数组里完成相应的查找功能）。（4）计算该哈希表查找成功时的ASL，并在课设报告中给出具体分析过程。（5）如果一个班级中有两个同学抽中此题，则要求学号在前面的同学用拉链法，学号在后面的同学用开放定址法来解决冲突。1.3 课程设计背景哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈希函数的参数经过精心设计，内存空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。2 概要设计2.1 程序模块结构图哈希查找程序 界面显示查找学生信息 显示学生信息 读取文件主函数程序结构模块图2.2 主界面模块说明主界面提供程序运行时出现的界面，此界面必须要有我想要实现功能的组件。具体而言，它需要有菜单，读取文件的菜单选项，关闭程序的菜单选项，还需要考虑好什么样的布局方式和界面美观性。2.3读取学生信息模块说明选项1读取文件显示在主界面上，使得看起来简洁清楚。3 详细设计3.1 建立哈希表#includestdio.h#includestdlib.h#includeconio.h#includestring.h#define MAX 50typedef struct _student{int key;int tag;char number[9];char name[10];char Major[31];char score[5];} *student,ST;typedef struct _Hash{student data[MAX];} *Hash,Hs;3.2计算哈希值我通过以学号的ASCII值之和作为关键字来计算key void Save(student S,Hash H){int key=0;int i;for(i=0;i9;i++)key=key+S-number[i];//学号的ASCII值之和作为关键字S-key=key%MAX;while(1){if(H-data[S-key]-tag!=0){H-data[S-key]=S;H-data[S-key]-tag=0;break;}elseS-key=(S-key+1)%50;}}3.3读取文件在程序的同一目录下，系统可以取读文件。void ReadFile(Hash H){char data[57];int i,j,k,m,n;student S;FILE *fp;if((fp=fopen(Hash.txt,r))==NULL){printf(文件未能正常打开\n);exit(0);}上面的代码是读取文件失败。下面是成功读取文件Hash.txt的代码。 H=(Hash)malloc(sizeof(Hs));for(i=0;i50;i++)H-data[i]=(student)malloc(sizeof(ST));while(1){S=(student)malloc(sizeof(ST));fgets(data,sizeof(data),fp);if(feof(fp)!=0)//若文件读到末尾，则返回return;j=0;k=0;m=0;for(i=0;i56;i++){if(i9)S-number[i]=data[i];if(i9i1