#include
#include
#include
typedef int KeyType;
typedef struct/*元素类型定义*/
{
KeyType key;/*关键字*/
int hi;/*冲突次数*/
}
DataType;
typedef struct/*散列表类型定义*/
{
DataType data;
int tableSize;/散列表的长度*/
int curSize;/*表中关键字个数*/
}HashTable;
void CreateHashTable(HashTable H,int m,int p,int hash[],int n);
int SearchHash(HashTable H,KeyType k);
void DisplayHash(HashTable H,int m);
void HashASL(HashTable H,int m);
void DisplayHash(HashTable H,int m)/输出散列表*/
{int i;
printf("散列表地址");
for(i=0;i<m;i++)
printf("%-5d",i);
printf("\n");
printf("关键字key: ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].key);
printf("\n");
printf("冲突次数: ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].hi);
printf("\n");
}
void CreateHashTable(HashTable H,int m,int p,int hash[],int n)
/构建一个空的散列表,并处理冲突*/
{
int i,sum,addr,di,k=1;
(*H).data=(DataType*)malloc(m*sizeof(DataType));/*散列表分配储存空间*/
if(!(*H).data)
exit(-1);
for(i=0;i<m;i++)/*初始化散列表*/
{
(*H).data[i].key=-1;
(*H).data[i].hi=0;}
for(i=0;i<n;i++)/*求散列函数地址并处理冲突*/
{
sum=0;/*冲突的次数*/
addr=hash[i]%p;/*利用除留余数法求散列函数地址*/
di=addr;
if((*H).data[addr].key==-1)/*如果不冲突则将元素储存在表中*/
{
(*H).data[addr].key=hash[i];
(*H).data[addr].hi=1;
}
else/*用线性探测再散列法处理冲突*/
{
do
{
di=(di+k)%m;
sum+=1;
}
while((*H).data[di].key!=-1);
(*H).data[di].key=hash[i];
(*H).data[di].hi=sum+1;
}
}
(*H).curSize=n;/*散列表中关键字个数为n*/
(*H).tableSize=m;/*散列表的长度*/
}
int SearchHash(HashTable H,KeyType k)/*在散列表H中查找关键字k的元素*/
{int d,d1,m;
m=H.tableSize;
d=d1=k%m;
while(H.data[d].key!=-1);/*求k的散列地址*/
{if(H.data[d].key==k)/*如果是要查找的关键字k,则返回k的位置*/
return d;
else
d=(d+1)%m;/*继续往后查找*/
if(d==d1)
return 0;
}
return 0;/*该位置不存在关键字k*/
}
void HashASL(HashTable H,int m)/*求散列表的平均查找长度*/
{float average=0;
int i;
for(i=0;i<m;i++)
average=average+H.data[i].hi;
average=average/H.curSize;
printf("平均查找长度ASL=%。2f",average);
printf("\n");}
int main()
{int hash[]={23,35,12,56,123,39,342,90};
int m=11,p=11,n=8,pos;
KeyType k;
HashTable H;
CreateHashTable(&H,m,p,hash,n);
DisplayHash(H,m);
k=123;
pos=SearchHash(H,k);
printf("关键字%d在散列表中的位置为:%\n",k,pos);
HashASL(H,m);
}
为什么运行之后不能查找元素所在位置和计算平均长度
要学会调试啊!一步步看看具体结果
代码粘贴错误太多
点击发表框工具栏上面的代码片图标,把代码放到代码片里,否则粘贴过来,容易出现错误,格式也很乱。
象这句话这样的格式就对了。
这个就是数据结构中哈希表的C语言实现版本的,你了解了哈希表的基本知识,这个算法就很简单了啊。