这是算法导论习题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)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}

版权声明:

本作品采用知识共享署名 2.5 中国大陆许可协议进行许可,欢迎转载,但转载请注明来自远行’s Life,并保持转载后文章内容的完整。本人保留所有版权相关权利。

本文链接:http://xiaopengcheng.top/2012/03/20/无穷大数组上如何直接寻址来实现字典?/