内容发布更新时间 : 2024/12/28 5:50:48星期一 下面是文章的全部内容请认真阅读。
xxx大学实验报告
课程名称 数据结构 实验项目 实验三 查找和排序(一)——查找 院 系 信息学院计类系 专业班级 计类1501 姓 名 学 号 指导老师 日 期
批改日期 成 绩
一 实验目的
1．掌握哈希函数——除留余数法的应用； 2. 掌握哈希表的建立； 3. 掌握冲突的解决方法； 4. 掌握哈希查找算法的实现。
二 实验内容及要求
实验内容：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并计算平均查找长度（设每个记录的查找概率相等）。
实验要求：1. 哈希表定义为定长的数组结构；2. 使用线性探测再散列或链地址法解决冲突；3. 散列完成后在屏幕上输出数组内容或链表；4. 输出等概率查找下的平均查找长度；5. 完成散列后，输入关键字完成查找操作，要分别测试查找成功与不成功两种情况。
注意：不同解决冲突的方法会使得平均查找长度不同，可尝试使用不同解决冲突的办法，比较平均查找长度。（根据完成情况自选，但至少能使用一种方法解决冲突）
三 实验过程及运行结果
#include
#define q 13 int sign=2;
typedef struct Hash {
int date; //值域 int sign; //标记 }HashNode;
void compare(HashNode H[],int p,int i,int key[]) //线性冲突处理 {
p++;
if(H[p].sign!=0) {
sign++;
compare(H,p,i,key); } else {
H[p].date=key[i]; H[p].sign=sign; sign=2; } }
void Hashlist(HashNode H[],int key[]) {
int p;
for(int i=0;i<12;i++) {
p=key[i]%q;
if(H[p].sign==0) {
H[p].date=key[i]; H[p].sign=1; } else
compare(H,p,i,key);
} }
int judge(HashNode H[],int num,int n) //{
查找冲突处理 n++;
if(n>=hashsize) return 0; if(H[n].date==num) {
printf(\位置\\t 数据\\n\
printf(\ return 1; } else
judge(H,num,n); }
int search(char num,HashNode H[]) //查找 {
int n;
n= num % q;
if(H[n].sign==0) {
printf(\失败\ return 0; }
if(H[n].sign!=0&&H[n].date==num) {
printf(\位置\\t 数据\\n\
printf(\ }
else if(H[n].sign!=0&&H[n].date!=num) {
if(judge(H,num,n)==0) return 0; }
return 1; }
int main(void) {
int key[q]={19,14,23,1,68,20,84,27,55,11,10,79}; float a=0;
HashNode H[hashsize];