哈希表实验报告

1. 实验目的：掌握HASH表的建立和查表技术。 2. 实验内容：

1. 编写函数实现线性探查HASH表的插入和查找算法。 2. 编写主函数完成以下功能：

3. 定义一个长度为128的HASH表；

4. 随机产生120个0~255之间的不重复的伪随机整数，依次插入到HASH表中；HASH函数为H(k)= k*0.618 mod 127； 5. 查找存在的和不存在的关键字；

6. 编写函数，统计该HASH表的平均查找长度； 7. 变换关键字个数，观察平均查找长度的变化； 8. 变换HASH函数，观察平均查找长度的变化； 9. 编写函数实现HASH表的删除算法。 3. 实验步骤

1. 运行已经给出的代码：产生随机数和查找功能已经实现。 2. 编写统计哈希表平均查找长度的函数。 int asl(int keys[], int n) {

//计算平均查找长度ASL并返回结果。参照find函数。 int i,h,ASL=0; for(i=0;i

n=1;//n用来记录查找长度 h=hash(keys[i]);

while((HashTable[h].key!=-1)&&(HashTable[h].key!=keys[i])) {

n++;h=(h+1)%M; }

ASL=ASL+n;//把查找长度累加起来

}

ASL=ASL/KeyNum;//计算平均查找长度 return ASL; }

3. 编写选作的哈希表的删除算法。根据给出的关键字h在表中查找，

不符合则用-1标记key即不进行操作，找到则用999标记Key即删除。

void del(int k)//HASH表的删除 { int h; h=hash(k);

while((HashTable[h].key!=-1)&&(HashTable[h].key!=k)) h=(h+1)%M;//查找关键字k

if(HashTable[h].key==-1); //没有发现k，不进行操作 else HashTable[h].key=999; //找到k后，用999标记 }

同时需要在主函数中添加删除功能的显示，为了显示删除后的变化，将删除后的表打印出来。 while(ch_=='y') {//删除关键字 _flushall();

printf(\scanf(\输入要删除的关键字 del(key);

printf(\

_flushall(); ch_=getchar(); }

printf(\输出删除关键字后的哈希表 for(i=0; i #include #include

#define M 130 //Hash表长度 #define KeyNum 130 //关键字个数 struct element { int key; int otherterm; };

typedef struct element DATATYPE; DATATYPE HashTable[M]; int hash(int k) {

return ((int)(k*0.618)7); }

void insert(int k) //HASH表的建立相关算法。 { int h; h=hash(k);

while(HashTable[h].key!=-1) h=(h+1)%M; HashTable[h].key=k; }

int find(int k) //HASH表的查找相关算法。 { int h; h=hash(k);

while((HashTable[h].key!=-1)&&(HashTable[h].key!=k)) h=(h+1)%M; if(HashTable[h].otherterm==1) return -1; else if(HashTable[h].key==-1) return -1; else return h; }

int Delete(int k) //HASH表的删除相关算法。 { int h; h=find(k); if(h!=-1) {

HashTable[h].otherterm=1; return 1;