还有一个问题就是rehash函数中再散列得到的表为什么能直接覆盖到原表上?
#include <stdlib.h>
#include <stdio.h>
struct HashTable;
struct TableEntry;
typedef int ElementType;
typedef int Position;
typedef int Index;
typedef struct HashTable *Tbl;
typedef struct TableEntry Cell;
int Hash(ElementType x,int TblSize);
Tbl Initialize(int tablesize);
Position Find(Tbl T,ElementType x);
void Insert(Tbl T,ElementType x);
void Show(Tbl T);
Tbl Rehash(Tbl T);
enum KindOfEntry{Legitimate,Empty,Delete};
struct HashTable
{
int size;
Cell *thecells;
};
struct TableEntry
{
ElementType value;
enum KindOfEntry Info;
};
#include "Open adress.h"
int Hash(ElementType x,int TblSize)
{
return x % TblSize;
}
Tbl Initialize(int tablesize){
Tbl T = malloc(sizeof(struct HashTable));
T->size = tablesize;
T->thecells = malloc(sizeof(struct TableEntry)*T->size);
for (int i = 0;i < T->size;i++)
{
T->thecells[i].Info = Empty;
T->thecells[i].value = -1;
}
return T;
}
Position Find(Tbl T,ElementType x){
Position CurrentPos;
int CollisionNum = 0;
CurrentPos = Hash(x,T->size);
while (T->thecells[CurrentPos].value != x && T->thecells[CurrentPos].Info != Empty)
{
CurrentPos += 2*++CollisionNum - 1;
if (CurrentPos >= T->size)
CurrentPos -= T->size;
}
return CurrentPos;
}
void Insert(Tbl T,ElementType x){
Position P = Find(T,x);
if (T->thecells[P].Info = Empty)
{
T->thecells[P].Info = Legitimate;
T->thecells[P].value = x;
}
}
void Show(Tbl T){
for (int i = 0;i<T->size;i++)
{
if (T->thecells[i].Info != Delete)
printf("%d\n",T->thecells[i].value);
}
}
Tbl Rehash(Tbl T){
int oldsize = T->size;
Cell *oldcells = T->thecells;
T = Initialize(2 * oldsize); //为什么可以覆盖原有的?
for (int i = 0;i < oldsize;i++)
{
if (T->thecells[i].Info = Legitimate)
Insert(T,T->thecells[i].value);
}
free(oldcells);
return T;
}
int main()
{
Tbl T = Initialize(10);
Insert(T,89);
Insert(T,18);
Insert(T,49);
Insert(T,58);
Insert(T,69);
Show(T);
printf("\n");
Tbl T1 = Rehash(T);
Show(T1);
system("pause");
return 0;
}