這是算法導(dǎo)論習(xí)題11.1-4。
具體題目如下：
組實(shí)現(xiàn)直接尋址hash.jpg)
解決該題目的要點(diǎn)：
1.由于是無窮大的數(shù)組，所以無法事先初始化該數(shù)組。
2.所提供的方案必須是O（1）。
3.使用的額外空間只能是O（n），這樣平均到每一個(gè)項(xiàng)上的空間都是O（1）。
一時(shí)之間好像沒有一點(diǎn)頭緒，在幾個(gè)群里面發(fā)問了，網(wǎng)上搜了很久也沒有找到答案，后面一群里有個(gè)高人給了個(gè)鏈接，里面有解法。
鏈接地址：http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html，這篇文章里面另外給了個(gè)pdf，這個(gè)pdf估計(jì)是解法
的來源。偽代碼寫得不給力，不過前面的英文描述卻很清晰。說實(shí)話，這個(gè)方法很巧妙。
解法大概的意思如下：
開一個(gè)額外的數(shù)組A，A[0]表示A數(shù)組元素的數(shù)目(當(dāng)然不包括A[0]本身)，A[i]代表插入的第i個(gè)元素的key。假設(shè)原來的無窮大數(shù)組用Huge
表示，如果Huge[i](直接尋址，假設(shè)i就是key)有效，則表示其在A數(shù)組中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，則表示i這個(gè)位置已經(jīng)有元素插入了。
插入：A[0]++;A[A[0]] = key; Huge[key] = A[0];
搜索: A[Huge[i]] == i && Huge[i] <= A[0] && Huge[i] > 0 則return true;
刪除: 先搜索該位置是否有元素, 如果Search(key)成功，則先把Huge[ A[A[0]] ] = Huge[key]，
然后交換A[A[0]]和A[Huge[key]]，A[0]--即可。
所有操作都是O（1），平均到每一個(gè)項(xiàng)，使用的空間都是O（1）。
我用代碼實(shí)現(xiàn)的模擬如下：
#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)
int nHuge[INF];
//假設(shè)這個(gè)巨大的數(shù)組是無法初始化的
vector<
int> vA;
void Init()
{
vA.push_back(0);
//添加A[0]表示元素的數(shù)目
}
void Insert(
int nKey)
{
vA[0]++;
nHuge[nKey] = vA[0];
vA.push_back(nKey);
}
bool Search(
int nKey)
{
if (nHuge[nKey] > 0 && nHuge[nKey] <= vA[0] && vA[nHuge[nKey]] == nKey)
{
return true;
}
return false;
}
void Delete(
int nKey)
{
if (Search(nKey))
{
nHuge[ vA[vA[0]] ] = nHuge[nKey];
//將huge的最后一個(gè)元素中存儲的A數(shù)組的索引改為nHuge[nKey]
swap(vA[vA[0]], vA[nHuge[nKey]]);
//交換key
--vA[0];
vA.erase(vA.end() - 1);
}
}
#define MAX (10)
int main()
{
Init();
int i;
for (i = 0; i < MAX; ++i)
{
Insert(i);
}
for (i = 0; i < MAX; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
printf("\n");
Delete(4);
Delete(9);
Delete(1);
for (i = 0; i < MAX * 2; ++i)
{
printf("Search:%d %s\n", i, Search(i) ==
true? "Success" : "Failure");
}
return 0;
}