编辑代码

#include <stdio.h>
#include <malloc.h>

#define MinTableSize 3

//typedef struct Cells *Cell;

/*
   存储元素的数组结构：
     Element：元素的数据
     Info：标志位 
*/ 
typedef struct Cells{
    int Element;
    /*
      初始化为0
      0：表示该位置为空
      1：位置已被占有
      2：该位置的元素已被删除
    */
    int Info;
}Cell[10];

/*
   哈希表的结构：
     TableSize:哈希表的大小
     TheCells：存储数据的数组
*/
typedef struct HashTbl *HashTable;
struct HashTbl{
    int TableSize;
    Cell TheCells;
}H;

HashTable InitializeTable(int TableSize);
int Find(int key,HashTable H);
void Insert(int Key,HashTable H);
int Hash(int Key,int TableSize);
int NextPrime(int TableSize);

int NextPrime(int TableSize){
    int result = TableSize;
    if(TableSize%2 == 0 ){
        return ++result;
    }else{
        return result;
    }
}

int Hash(int Key,int TableSize){
   int hash = Key % TableSize;
   return hash;
}

//插入元素
void Insert(int Key,HashTable H){
    int Pos;
    Pos = Find(Key,H);
    if(H->TheCells[Pos].Info == 0 && H->TheCells[Pos].Info !=1){
        //确认在此插入
        H->TheCells[Pos].Info = 1;
        //字符串类型的关键词需要strcpy函数
        H->TheCells[Pos].Element = Key;
    }
}

//开放地址法：平方探测法
int Find(int Key,HashTable H){
    int CurrentPos,NewPos;
    //记录冲突次数
    int CNum = 0;
    NewPos = CurrentPos = Hash(Key,H->TableSize);
    while(H->TheCells[NewPos].Info != 0 && 
    H->TheCells[NewPos].Element != Key){//字符串类型的关键词需要strcmp函数
        //判断冲突的奇偶次
        if(++CNum%2){
            //冲突数（CNUm）为奇数
            NewPos = CurrentPos + (CNum+1)/2 * (CNum+1)/2;
            //如果NewPos超出范围，把它拉回到TableSize的范围内
            while(NewPos >= H->TableSize){
                NewPos -= H->TableSize;
            }
        }else{
            //冲突数（CNUm）为偶数
            NewPos = CurrentPos - CNum/2 * CNum/2;
            while(NewPos < 0){
                NewPos += H->TableSize;
            }
        }
    }
    return NewPos;
}

HashTable InitializeTable(int TableSize){
    HashTable H;
    int i;
    if(TableSize < MinTableSize){
        printf("散列表太小");
        return NULL;
    }
    //分配散列表
    H = (HashTable)malloc(sizeof(struct HashTbl));
    if(H == NULL){
        printf("空间溢出");
    }
    H->TableSize = NextPrime(TableSize);
    //分配散列表 Cells
    //H->TheCells = (Cell *)malloc(sizeof(Cell)*H->TableSize);
    if(H->TheCells == NULL){
        printf("空间溢出");
    }
    for(int i = 0;i < H->TableSize;i++){
        H->TheCells[i].Info = 0;
    }
    return H;
}

int main () {
    HashTable hash = InitializeTable(5);
    int i,j;
    for(j = 0;j < hash->TableSize;j++){
        printf("输入第%d个数：\n",j);
        scanf("%d",&i);
        Insert(i,hash);
    }
    for(j = 0;j < hash->TableSize;j++){
        printf("%d ",hash->TheCells[j].Element);
    }
}