[数据结构与算法]编写程序，新建一个容量不小于50的哈希表（采用线性探测法解决冲突），随机生成30个整数插入哈希表中，整数范围在[0，1000]之间。(C语言)

（1）从键盘输入一个整数，在哈希表中查找，若找到，输出下标，否则输出“not found”。

（2）输出该哈希表当前的查找成功ASL。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
enum EntryType{
    Legitimate,
    Empty,
    Deleted
};
struct HashEntry{
    int Data;
    enum EntryType Info;
};
struct HashTable{
    int TableSize;
    struct HashEntry *Cells;
};
int nextPrime(int num){
    num++;
    int i;
    while(1){
        int q=sqrt(num);
        for(i=2;i<=q;i++){
            if(num%i==0){
                break;
            }
        }
        if(i>q){
            return num;
        }
        num++;
    }
}
struct HashTable *createTable(int size){
    struct HashTable *H;
    H=(struct HashTable *)malloc(sizeof(struct HashTable));
    H->TableSize=nextPrime(size);
    H->Cells=(struct HashEntry *)malloc(sizeof(struct HashEntry)*H->TableSize);
    for(int i=0;i<H->TableSize;i++){
        H->Cells[i].Info=Empty;
    }
    return H;
}
int Hash(int num,int size){
    return num%size;
}
int Find(struct HashTable *H,int num){
    int pos;
    pos=Hash(num,H->TableSize);
    while(H->Cells[pos].Info!=Empty&&H->Cells[pos].Data!=num){
        pos++;
        pos=pos%H->TableSize;
    }
    return pos;
}
void Insert(struct HashTable *H,int num){
    int pos;
    pos=Find(H,num);
    if(H->Cells[pos].Info!=Legitimate){
        H->Cells[pos].Info=Legitimate;
        H->Cells[pos].Data=num;
    }
}
void show(struct HashTable *H){
    printf("此时哈希表为:");
    for(int i=0;i<H->TableSize;i++){
        if(H->Cells[i].Info==Legitimate){
            printf("  %d",H->Cells[i].Data);
        }else{
            printf("  #");
        }
    }
}
int gettotalASL(struct HashTable *H){
    int total=0;
    for(int i=0;i<H->TableSize;i++){
        if(H->Cells[i].Info==Legitimate){
            int count=1;
            int pos=Hash(H->Cells[i].Data,H->TableSize);
            while(H->Cells[pos].Info!=Legitimate||H->Cells[pos].Data!=H->Cells[i].Data){
                pos++;
                count++;
            }
            total+=count;
        }
    }
    return total;
}
int count(struct HashTable *H){
    int count=0;
    for(int i=0;i<H->TableSize;i++){
        if(H->Cells[i].Info==Legitimate){
            count++;
        }
    }
    return count;
}
int main(){
    struct HashTable *H;
    H=createTable(50);
    srand(time(NULL));
    for(int i=0;i<30;i++){
        int num=rand()%1001;
        Insert(H,num);
    }
    show(H);
    printf("\n\n");
    printf("请输入需要查找的数据:");
    int data;
    scanf("%d",&data);
    int result=Find(H,data);
    if(H->Cells[result].Info!=Legitimate){
        printf("not found\n\n");
    }else{
        printf("index=%d\n\n",result);
    }
    int asl=gettotalASL(H);
    printf("哈希表当前查找成功ASL=%lf",(double)asl/count(H));
    return 0;
}

?

?