資料結構設計
- 雜湊表長度固定為 13（素數，減少衝突）；
- 關鍵字為非負整數；
- 用
NIL = -1 表示空位，DEL = -2 表示已刪除位置（懶惰刪除）。
核心操作
#define NIL -1
#define DEL -2
#define SIZE 13
int HashTable[SIZE];
// 雜湊函數：除留餘數法
int hash(int key) { return key % SIZE; }
// 插入：線性探測尋找 NIL 或 DEL 位置
void InsertHashTable(int key) {
for (int i = 0; i < SIZE; i++) {
int idx = (hash(key) + i) % SIZE;
if (HashTable[idx] == NIL || HashTable[idx] == DEL) {
HashTable[idx] = key;
break;
}
}
}
// 查找：遇到 NIL 即失敗；遇到 DEL 繼續探測
int HashSearch(int key) {
for (int i = 0; i < SIZE; i++) {
int idx = (hash(key) + i) % SIZE;
if (HashTable[idx] == key) return idx;
if (HashTable[idx] == NIL) return -1;
}
return -1;
}
// 刪除：標記為 DEL，不物理移除
void DeleteHashTable(int key) {
int idx = HashSearch(key);
if (idx != -1) HashTable[idx] = DEL;
else printf("無此關鍵字!\n");
}
主程式測試流程
int main() {
// 初始化
for (int i = 0; i < SIZE; i++) HashTable[i] = NIL;
// 建表、插入、刪除、查找、列印互動
// ...
return 0;
}
關鍵點總結
- 線性探測公式：
(hash(key) + i) % SIZE；
- 刪除必須標記 DEL，否則會斷開後續元素的查找鏈；
- 負載因子超過 0.7 時應考慮重雜湊擴容（本範例為教學固定大小）。
