这是算法导论习题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
表示，如果Huge[i](直接寻址，假设i就是key)有效，则表示其在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;
}