?
? ? ? ?再散列之后散列函數要重新計算。
// kaifangliaobiao.cpp : 定義控制臺應用程序的入口點。
//使用平方探測解決沖突問題時，散列表至少空一半時，總能插入一個新的元素#include "stdafx.h"
#include<iostream>
using namespace std;#ifndef HashQuad
typedef unsigned int Index;
typedef Index Position;struct HashTbl;
typedef struct HashTbl *HashTable;HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(int key, HashTable H);
void Insert(int key, HashTable H);
int Retrieve(Position P, HashTable H);
HashTable Rehash(HashTable H);
#endif // !HashQuad
#define MinTableSize 10enum KindOfEntry{Legitimate,Empty,Delete};struct HashEntry
{int key;enum KindOfEntry Info;
};typedef struct HashEntry Cell;struct HashTbl
{int TableSize;Cell *TheCell;
};int Hash(int key, int tableSize)
{return key%tableSize;
}int NextPrime(int n)
{if (n % 2 == 0) n++; //1.排除掉偶數for (;; n += 2){bool isPrime = 1; //2.標志位for (int i = 3; i*i <= n; i += 2)if (n%i == 0) {isPrime = 0;break;}if (isPrime)return n;}
}HashTable InitializeTable(int TableSize) //初始化函數
{HashTable H;int i;if (TableSize < MinTableSize){cout << "Table is too small";return NULL;}H = (HashTable)malloc(sizeof(HashTbl)); //1.初始化散列表地址if (H == NULL)cout << "out of space";H->TableSize = NextPrime(TableSize); //2.用素數初始化散列表大小H->TheCell = (Cell *)malloc(sizeof(Cell)*H->TableSize); //3.申請一個表頭if (H->TheCell == NULL)cout << "out of space";for (i = 0; i < H->TableSize; i++)H->TheCell[i].Info = Empty; //4.為每一個表項賦狀態空return H;
}Position Find(int key, HashTable H) //用平方探測散列法查找
{Position CurrentPos; //1.要返回的地址int CollisionNum; //2.偏移的位置量CollisionNum = 0;CurrentPos = Hash(key, H->TableSize);while (H->TheCell[CurrentPos].Info!=Empty&&H->TheCell[CurrentPos].key!=key) //3.檢測表項狀態{CurrentPos += 2 * ++CollisionNum - 1; //4.偏移if (CurrentPos >= H->TableSize) //5.滿則折返CurrentPos -= H->TableSize;}return CurrentPos;
}void Insert(int key, HashTable H)
{Position Pos;Pos = Find(key, H);if (H->TheCell[Pos].Info != Legitimate){H->TheCell[Pos].Info = Legitimate;H->TheCell->key = key;}
}HashTable Rehash(HashTable H) //再散列
{int i, oldSize;Cell *OldCells;OldCells = H->TheCell; //1.記錄舊散列表的信息oldSize = H->TableSize;H = InitializeTable(2 * oldSize); //2.創建兩倍大小的新散列表for (i = 0; i < oldSize; i++) { //3.循環復制信息if (OldCells[i].Info == Legitimate)Insert(OldCells[i].key, H);}free(OldCells);return H;
}int main()
{return 0;
}
?
