#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>enum EntryType {Legitimate, Empty, Deleted};struct HashEntry {int Data;enum EntryType Info;
};struct HashTable {int TableSize;struct HashEntry * Cells; /* 存放条目的数组 */
};int Hash(int K, int TableSize) {return K % TableSize;
}struct HashTable *CreateTable() {struct HashTable *H;int i;H = (struct HashTable*)malloc(sizeof(struct HashTable));H->TableSize = 53; /* 得到素数作为表大小 */H->Cells =(struct HashEntry*)malloc(sizeof(struct HashEntry) * H->TableSize);for (i = 0; i < H->TableSize; i ++)H->Cells[i].Info = Empty;return H;
}int Find(struct HashTable *H, int K,int *CN) {int Pos, NewPos;int CNum = 0;Pos = Hash(K, H->TableSize);NewPos = Pos;while (H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != K ) {CNum ++;NewPos = Pos + CNum;if (NewPos >= H->TableSize)NewPos %= H->TableSize;}*CN=CNum+1;return NewPos;
}int FindX(struct HashTable *H, int K) {int Pos, NewPos;int CNum = 0,i=1;Pos = Hash(K, H->TableSize);NewPos = Pos;while (H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != K ) {CNum ++;i++;NewPos = Pos + CNum;if (NewPos >= H->TableSize)NewPos %= H->TableSize;}if( H->Cells[NewPos].Data == K){printf("%d\n",NewPos);}else{printf("not found");}
}void Insert(struct HashTable *H,int K) {int Pos,z;Pos = Find(H, K,&z);if (H->Cells[Pos].Info != Legitimate) {H->Cells[Pos].Info = Legitimate;H->Cells[Pos].Data = K;}
}int main()
{int i,j,z,CNum=0,l=0,m;struct HashTable *H;H=CreateTable();srand((int)time(NULL));printf("插入的随机数：\n"); for(i=0;i<30;i++){j=rand()%1001;Insert(H,j);m=Find(H,j,&z);CNum=CNum+z;if(i!=0&&i%10==0)printf("\n");printf("%4d ",j);}printf("\n");printf("哈希表中的数据：\n");int x;for(i=0;i<53;i++){if(i!=0&&i%10==0)printf("\n");if(H->Cells[i].Info == Legitimate){printf("%4d ",H->Cells[i].Data);l++ ;}else printf(" ");}printf("\n");printf("哈希表中的元素个数：\n"); printf("%d\n",l);printf("请输入查找值：\n");scanf("%d",&x);printf("查找结果：\n");FindX(H,x);printf("ASL=");printf("%.2lf\n",(double)CNum/l);return 0;
}