int i,adr; adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在
哈希表中 }
void CreateHT(HashTable ha,KeyType x[],int n,int m,int p) //创建哈希表
{ } else { } n++;
i=1; do {
adr=(adr+1) % p; i++;
//i记录x[j]发生冲突的次数
//发生冲突时采用线性探查法解决冲突
ha[adr].key=k; ha[adr].count=1;
} while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY); ha[adr].key=k; ha[adr].count=i;
{
int i,n1=0; for (i=0;i //哈希表置初值 { ha[i].key=NULLKEY; ha[i].count=0; } } int SearchHT(HashTable ha,int p,KeyType k) { int i=0,adr; adr=k % p; while (ha[adr].key!=NULLKEY && ha[adr].key!=k) { } if (ha[adr].key==k) return adr; //查找失败 //查找成功 i++; //采用线性探查法找下一个地址 //在哈希表中查找关键字k for (i=0;i InsertHT(ha,&n1,x[i],p); adr=(adr+1) % p; else } return -1; int DeleteHT(HashTable ha,int p,int k,int *n) //删除哈希表中关键字k { } void DispHT(HashTable ha,int n,int m) //输出哈希表 { float avg=0; int i; printf(\哈希表地址:\\t\for (i=0;i printf(\int adr; adr=SearchHT(ha,p,k); if (adr!=-1) { } else //在哈希表中未找到该关键字 ha[adr].key=DELKEY; n--; //哈希表长度减1 //在哈希表中找到该关键字 return 1; return 0; printf(\ printf(\哈希表关键字:\\t\ for (i=0;i if (ha[i].key==NULLKEY || ha[i].key==DELKEY) printf(\ \ //输出3个空格 else printf(\ printf(\ printf(\搜索次数:\\t\for (i=0;i if (ha[i].key==NULLKEY || ha[i].key==DELKEY) printf(\ \ //输出3个空格 else printf(\ printf(\ for (i=0;i if (ha[i].key!=NULLKEY && ha[i].key!=DELKEY) avg=avg+ha[i].count; avg=avg/n; printf(\平均搜索长度ASL(%d)=%g\\n\ void main() { int x[]={16,74,60,43,54,90,46,31,29,88,77}; int n=11,m=13,p=13,i,k=29; HashTable ha; CreateHT(ha,x,n,m,p); printf(\printf(\查找关键字29:\\n\i=SearchHT(ha,p,k); if (i!=-1) printf(\ else printf(\未找到%d\\n\ k=77; printf(\删除关键字%d\\n\DeleteHT(ha,p,k,&n); DispHT(ha,n,m); i=SearchHT(ha,p,k); if (i!=-1) printf(\ else printf(\未找到%d\\n\ } printf(\插入关键字%d\\n\InsertHT(ha,&n,k,p); DispHT(ha,n,m); printf(\ 四，实验小结 1、通过本次实验，加深了我对查找表的认识。 2、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。 3、二叉排序树查找：通过一系列的查找和插入过程形成的树。之所以叫做排序树，因为按照中序遍历可得一个有序的序列。