无穷大数组上如何直接寻址来实现字典？

这是算法导论习题11.1-4。
具体题目如下：

解决该题目的要点：
1.由于是无穷大的数组，所以无法事先初始化该数组。
2.所提供的方案必须是O（1）。
3.使用的额外空间只能是O（n），这样平均到每一个项上的空间都是O（1）。

一时之间好像没有一点头绪，在几个群里面发问了，网上搜了很久也没有找到答案，后面一群里有个高人给了个链接，里面有解法。链接地址：

http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html

这篇文章里面另外给了个pdf，这个pdf估计是解法的来源。伪代码写得不给力，不过前面的英文描述却很清晰。说实话，这个方法很巧妙。

解法大概的意思如下：
开一个额外的数组A，A[0]表示A数组元素的数目(当然不包括A[0]本身)，A[i]代表插入的第i个元素的key。假设原来的无穷大数组用Huge
表示，如果Hugei有效，则表示其在A数组中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，则表示i这个位置已经有元素插入了。

插入：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），平均到每一个项，使用的空间都是O（1）。

我用代码实现的模拟如下：

#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)

int nHuge[INF];//假设这个巨大的数组是无法初始化的
vector<int> vA;

void Init()
{
    vA.push_back(0);//添加A[0]表示元素的数目
}

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的最后一个元素中存储的A数组的索引改为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;
}