这两天看了第13章，看了好长一段时间，主要花在理解和编程实现上面，感觉自己的理解能力还有待提高。
这一章主要讲如何实现一个有序集合（Set），该集合插入元素时不能插入重复元素，每次插入完后集合中元素的排列是有序的。书上一共使用了6种数据结构实现这个集合：STL中的set（红黑数）、数组、链表、二分查找树、位向量、桶，使用了3种优化方案：哨兵（标记元素）、指针的指针（用于实现递归向迭代的转换）、块内存分配（一次性分配一大块内存，使用时从分配好的空间中取，不用每次用的时候new一次）。
下面就二分查找树的方法来举例说明如何使用这3种优化方法：
首先，实现一个未优化的方案，使用递归实现，没有使用哨兵，每次都比较一下是否到达链表尾，没有使用块内存分配，每次插入一个节点的时候分配一次内存，C++实现如下：
class IntSetBSTRecurse
{
private:
struct node
{
int val;
node *left, *right;
node (int t)
{
val = t;
left = right = 0;
}
};
int n, vn, *v;
node *root;
public:
IntSetBSTRecurse(int maxelements, int maxval) : n(0), root(0) { }
int size()
{
return n;
}
void insert(int t)
{
root = rinsert(root, t);
}
void report(int *x)
{
v = x;
vn = 0;
traverse(root);
}
~IntSetBSTRecurse()
{
deletenode(root);
}
private:
node* rinsert(node* p, int t)
{
if (!p)
{
p = new node(t);
++n;
}
else if (p->val < t)
p->right = rinsert(p->right, t);
else if (p->val > t)
p->left = rinsert(p->left, t);
return p;
}
void traverse(node* p)
{
if (p)
{
traverse(p->left);
v[vn++] = p->val;
traverse(p->right);
}
}
void deletenode(node* p)
{
if(p)
{
deletenode(p->left);
deletenode(p->right);
delete p;
p = 0;
}
}
};
然后把插入元素的函数改为迭代实现，暂不使用哨兵、块内存分配、指针的指针等优化方案，实现如下：
void insert(int t)
{
if (!root)
{
root = new node(t);
++n;
return;
}
node* p = root;
while (p)
{
if (t < p->val)
{
if (p->left)
p = p->left;
else
{
p->left = new node(t);
++n;
return;
}
}
else if (t > p->val)
{
if (p->right)
p = p->right;
else
{
p->right = new node(t);
++n;
return;
}
}
else
return;
}
}
可以看出，改成迭代的方式要考虑很多情况，代码比较复杂，可以使用指针的指针简化这种复杂性，不过这个有点难理解，需要画画图才能更好的理解（我比较笨，一眼没法看透）。
再使用上面3种优化方案，实现如下：
class IntSetBSTIterate
{
private:
struct node
{
int val;
node *left, *right;
node()
{
val = 0;
left = right = 0;
}
node(int t)
{
val = t;
left = right = 0;
}
node(int t, node* s)
{
val = t;
left = right = s;
}
};
node *root, *sentinel, *freenode, *pnewnode;
int n, *v, vn;
public:
IntSetBSTIterate(int maxelements, int maxval) : n(0), v(0), vn(0)
{
root = sentinel = new node(maxval, 0);
pnewnode = new node[maxelements];
freenode = pnewnode;
}
int size()
{
return n;
}
void insert(int t)
{
sentinel->val = t;
node **p = &root; // pointer to pointer
while ((*p)->val != t)
if (t < (*p)->val)
p = &((*p)->left);
else
p = &((*p)->right);
if (*p == sentinel) {
*p = freenode++;
(*p)->val = t;
(*p)->left = (*p)->right = sentinel;
n++;
}
}
void report(int *x)
{
node* p = root;
v = x;
vn = 0;
traverse(p);
}
~IntSetBSTIterate()
{
delete sentinel;
root = sentinel = 0;
delete[] pnewnode;
pnewnode = freenode = 0;
}
private:
void traverse(node* p)
{
if (p != sentinel)
{
traverse(p->left);
v[vn++] = p->val;
traverse(p->right);
}
}
};
上面使用freenode进行预分配内存，一次性把所有的内存都分配好，在插入时要用的内存时从已经分配好的内存块中取出使用；同时使用哨兵sentinel，让每个叶节点都指向哨兵，不用每次都担心指针是否指向最后的空元素，哨兵可以减少比较的次数；最后一个优化是使用指向指针的指针实现迭代，用法很巧妙，p指向的是节点的next指向的地址，改变*p的值就是改变next的指向，巧妙的插入一个节点，同时改变整个链表的指向。