《编程珠玑》第 13 章──搜索

很多应用都需要搜索一组数组,以找到与特定项相关的信息。这一章主要讨论的是用于表示集合的数据结构。

接口

需要实现的接口函数如下:

1
2
3
4
5
6
7
class intSetImp{
public:
IntSetImp(int maxelements, int maxval);
void insert(int t);
int size();
void report(int *v);
}

IntSetImp 是初始化函数,insert 是插入新值的函数,size 函数返回总数量,report 函数将元素复制到内存 v 中。

实现方法

模板库

使用 C++ 标准模板库中的 set 模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class IntSetSTL {
public:
IntSetSTL(int maxelements, int maxval) {}

void insert(int t) {
S.insert(t);
};

int size() {
return (int) S.size();
}

void report(int *v) {
int j = 0;
set<int>::iterator i;
for (i = S.begin(); i != S.end(); ++i) {
v[j++] = *i;
}
}

private:
set<int> S;
};

整型数组

注意这里增加了一个哨兵,可以用来判断是不是到了最后。我一开始还用 n 来判断,感觉它这种方法的确是可以简化插入的函数的代码。

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
class IntSetArr {
public:
IntSetArr(int maxelements, int maxval) {
n = 0;
x = new int[maxelements + 1];
x[0] = maxval;
};

void insert(int t) {
int i = 0;
for (i = 0; x[i] < t; ++i) { ;
}
if (x[i] == t) {
return;
}
for (int j = n; j >= i; --j) {
x[j + 1] = x[j];
}
x[i] = t;
++n;
}

int size() {
return n;
}

void report(int *v) {
for (int i = 0; i <= n; ++i) {
v[i] = x[i];
}
}

private:
int n, *x;
};

链表

如果不能提前知道集合的大小,那么链表会是首选结构。并且插入的时候省去移动数组移动元素的开销。
这里同样使用了一个哨兵节点。而且这里插入的话使用的递归,和我一开始想的用顺序遍历有点不同。

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
class IntSetList {
public:
IntSetList(int maxelements, int maxval) {
sentinel = head = new node(maxval, nullptr);
n = 0;
}

void insert(int t) {
head = rinsert(head, t);
}

int size() {
return n;
}

void report(int *v) {
int j = 0;
for (node *p = head; p != sentinel; p = p->next) {
v[j++] = p->val;
}
}

private:
int n;

struct node {
int val;
node *next;

node(int v, node *p) {
val = v;
next = p;
}
};

node *head, *sentinel;

node *rinsert(node *p, int t) {
if (p->val < t) {
p->next = rinsert(p->next, t);
} else if (p->val > t) {
p = new node(t, p);
++n;
}
return p;
}
};

二分搜索树

report 函数使用中序遍历即可,它这里把 *v 先定义成内部的成员,注意 vn 需要在每次 report 时重置为 0。插入的话,同样使用递归。在二叉树中,很多问题用递归其实都比较好解决,如果用非递归,只能自己用栈或者队列来实现相似的效果了。

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
class IntSetBST {
public:
IntSetBST(int maxelements, int maxval) {
root = nullptr;
n = 0;
}

void insert(int t) {
root = rinsert(root, t);
}

int size() {
return n;
}

void report(int *x) {
v = x;
vn = 0;
traverse(root);
}

private:
int n, *v, vn;

struct node {
int val;
node *left, *right;

node(int i) {
val = i;
left = right = nullptr;
}
};

node *root;

node *rinsert(node *p, int t) {
if (!p) {
p = new node(t);
++n;
} else if (t < p->val) {
p->left = rinsert(p->left, t);
} else if (t > p->val) {
p->right = rinsert(p->right, t);
}
return p;
}

void traverse(node *p) {
if (!p) {
return;
}
traverse(p->left);
v[vn++] = p->val;
traverse(p->right);
}
};

位向量

这个其实就是利用了第一章的位图知识了,理解了第一章,这里也就比较好理解了。

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
class IntSetBitVec {
public:
IntSetBitVec(int maxelements, int maxval) {
hi = maxval;
x = new int[1 + hi / BITSPERWORD];
for (int i = 0; i <= hi; ++i) {
clr(i);
}
n = 0;
}

void insert(int t) {
if (test(t)) {
return;
}
set_i(t);
++n;
}

int size() {
return n;
}

void report(int *v) {
int j = 0;
for (int i = 0; i <= hi; ++i) {
if (test(i)) {
v[j++] = i;
}
}
}

private:
enum {
BITSPERWORD = 32,
SHIFT = 5,
MASK = 0x1F
};
int n, hi, *x;

void set_i(int i) {
x[i >> SHIFT] |= (1 << (i & MASK));
}

void clr(int i) {
x[i >> SHIFT] &= ~(1 << (i & MASK));
}

int test(int i) {
return x[i >> SHIFT] & (1 << (i & MASK));
}
};

箱序列

个人感觉这个和桶排序的思想有那么一丁点类似,先按照范围放到一个又一个桶中,然后在桶中用链表来表示各个元素。

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
class IntSetBins {
public:
IntSetBins(int maxelements, int pmaxval) {
bins = maxelements;
maxval = pmaxval;
bin = new node *[bins];
sentinel = new node(maxval, nullptr);
for (int i = 0; i < bins; ++i) {
bin[i] = sentinel;
}
n = 0;
}

void insert(int t) {
int i = t / (1 + maxval / bins);
bin[i] = rinsert(bin[i], t);
}

int size() {
return n;
}

void report(int *v) {
int j = 0;
for (int i = 0; i < bins; ++i) {
for (node *p = bin[i]; p != sentinel; p = p->next) {
v[j++] = p->val;
}
}
}

private:
int n, bins, maxval;

struct node {
int val;
node *next;

node(int v, node *p) {
val = v;
next = p;
}
};

node **bin, *sentinel;

node *rinsert(node *p, int t) {
if (p->val < t) {
p->next = rinsert(p->next, t);
} else if (p->val > t) {
p = new node(t, p);
++n;
}
return p;
}
};

总结

集合表示初始化insertreport总时间空间
有序数组1mmO(m2)O\left(m^2\right)m
有序链表1mmO(m2)O\left(m^2\right)2m
二叉树1logm\log mmO(mlogm)O\left(m\log m\right)3m
m1mO(m)O\left(m\right)3m
位向量n1nO(n)O\left(n\right)nb\frac{n}{b}

习题

1. 答案 12.9 描述了生成有序随机整数集合的 Bob Floyd 算法。你能否用本章的几种 IntSet 实现该算法?这些结构在 Floyd 算法生成的非随机分布上性能如何?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void genfloyd(int m, int maxval) {
int *v = new int[m];
IntSetSTL S(m, maxval);
for (int i = maxval - m; i < maxval; ++i) {
int t = bigrand() % (i + 1);
int oldsize = S.size();
S.insert(t);
if (S.size() == oldsize) {
S.insert(i);
}
}
S.report(v);
for (int j = 0; j < m; ++j) {
cout << v[j] << endl;
}
}

3. 为集合类增加一个 find 函数,该函数用于判断给定的元素是否在集合中。你能否让该函数比 insert 更高效?

使用二分搜索

4. 为链表、箱和二分搜索树的递归插入函数重写相应的迭代版本,并度量运行时间的差别。

为了修改 node * 需要使用 node **,可以这样理解,用 node ** 才能使得 p 指针上一个指针的 next 信息还是 p 的地址,但是 p 所指向的内存中的 node 变了,换句话来说,这样的话,前一个指针才能按照原位置找到 p,但是你又想修改 p 所指的内容,就只能通过 p 指针来修改 p 中的信息。

1
2
3
4
5
6
7
8
9
10
void insert(int t) {
node **p;
for (p = &head; (*p)->val < t; p = &((*p)->next)) { ;
}
if ((*p)->val == t) {
return;
}
*p = new node(t, *p);
++n;
}

5. 9.1 节和答案 9.2 描述了 Chris Van Wyk 如何通过将可用结点保存在自已的结构中来避免多次调用存储分配器。说明如何将这一思想应用到链表、箱和二分搜索树实现的 IntSet 上。

首先构造足够的 node 数组空间。

1
freenode = new node[maxelms];

然后在插入函数中使用即可。

1
2
3
4
5
6
if (!p){
p = freenode++;
p->val = t;
p->left = p->right = nullptr;
n++;
}

.6 在各种 IntSet 实现上对下面的代码段计时,能够发现什么?

1
2
3
4
IntSetImp S(m, n);
for (int i = 0; i < m; ++i){
S.insert(i);
}

对于升序插入,数组和链表都是最好的情况,但是对于箱和二叉树则是最坏的情况,不然怎么需要平衡二叉树。

7. 我们的数组、链表和箱都使用了哨兵。说明如何将哨兵用于二分搜索树。

孩子是 nullptr 都改成孩子是 sentinel

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
class IntSetBST7 {
public:
IntSetBST7(int maxelements, int maxval) {
root = sentinel = new node(maxval);
n = 0;
freenode = (node *) malloc(maxelements * sizeof(struct node));
}

void insert(int t) {
node **p;
sentinel->val = t;
p = &root;
while ((*p)->val != t) {
if ((*p)->val > t) {
p = &((*p)->left);
} else {
p = &((*p)->right);
}
}
if ((*p) == sentinel) {
*p = freenode++;
(*p)->val = t;
(*p)->left = (*p)->right = sentinel;
n++;
}
}

private:
int n;

struct node {
int val;
node *left, *right;

node(int i);
};

node *root, *sentinel;
node *freenode;
};

8. 说明如何通过同时在很多位上进行操作来加速位向量的初始化和输出操作。这种方法在操作char、short、int、long或某种其他类型时是不是最有效的?

我觉得比如 int,用 int 类型的指针可以一次性将 32 位置为 0。输出的话也是输出 int,然后转为二进制就可以得到多个输出了。

9. 说明如何通过使用低开销的逻辑移位替代高开销的除法运算来对箱进行加速。

1
2
3
4
5
6
7
/* BINS */
goal = n/m
int binshift = 1;
for (int i = 2; i < goal; i *= 2){
binshift++;
}
p = &(bin[t >> binshift]);