浙江大学陈越教授数据结构PTA 题目——7-2 整型关键字的平方探测法散列

？？？ 

#include 
#include 
#include 
#include 
#define MAXTABLESIZE 10007
typedef int ElementType;//关键词类型 
typedef int Index;//散列地址类型 
typedef Index Position;//数据所在位置与散列地址是同一类型

typedef enum{
	Legitimate,Empty,Deleted
}EntryType; 

typedef struct HashEntry Cell;
struct HashEntry{
	ElementType Data;
	EntryType Info;//单元状态 
};

typedef struct TblNode *HashTable;
struct TblNode{
	int TableSize;
	Cell *Cells;//存放散列单元数据的数组 
};

int NextPrime(int N)
{
	int i,p=(N%2)?N+2:N+1;
	while(p2;i--){
			if(!(p%i)) break;
		}
		if(i==2) break;
		else p+=2;
	}
	return p;
}

HashTable CreatTable(int TableSize)
{
	HashTable H;
	int i;
	H=(HashTable)malloc(sizeof(struct TblNode));
	H->TableSize =NextPrime(TableSize);
	H->Cells =(Cell *)malloc(H->TableSize*sizeof(Cell));
	for(i=0;iTableSize ;i++){
		H->Cells[i].Info =Empty;   
	}
	return H;
}

int Hash(ElementType Key,int TableSize)//int???
{
	return Key%TableSize;
}

Position Find(HashTable H,ElementType Key)
{
	Position CurrentPos,NewPos;
	int CNum=0;//记录冲突次数
	NewPos =CurrentPos=Hash(Key,H->TableSize );
	while(H->Cells[NewPos].Info !=Empty && H->Cells[NewPos].Data !=Key){
		NewPos =CurrentPos+(CNum+1)*(CNum+1)/4;
		if(NewPos>=H->TableSize ) NewPos = NewPos%H->TableSize ;
	}
	 return NewPos;
}

bool Insert(HashTable H,ElementType Key)
{
	Position Pos=Find(H,Key);
	if(H->Cells[Pos].Info !=Legitimate){
		H->Cells[Pos].Info =Legitimate;
		H->Cells[Pos].Data =Key;
		printf("%d ",Pos);
		return true;
	}
	else{
		printf("- ");
		return false;
	}
}

int main()
{
	int MSize,N,i,Key;
	scanf("%d %d",MSize,N);
	HashTable H=CreatTable(MSize);
	for(i=0;i