【编程珠玑】第十三章 搜索

一，概述

第十二章，介绍生成某个范围内随机数，并按顺序输出。

本章主要介绍，存储按序输出的容器或者说存放集合的方法。并实现按序插入，按序输出。

1）set容器

1>set容器小例子：

#include <iostream>
#include <set>
using  namespace std;

int main()
{
    set<int> S;
    S.insert(1);
    S.insert(3);
    S.insert(2);
    S.insert(1);
    set<int>::iterator p;
    for(p=S.begin();p!=S.end();p++)
    	cout<<*p<<" ";
    cout<<endl;

    cout<<"the total elements is:"<<S.size()<<endl;
    return 0;	
}

输出：1 2 3 //自动屏蔽重复元素

the total elements is: 3

2>set容器实现插入元素，并有序输出

class IntSetSTL {
private:
	set<int> S;
public:
	IntSetSTL(int maxelements, int maxval) { }//构造函数
	int size() { return S.size(); }
	void insert(int t) { S.insert(t);}//插入
	void report(int *v)//输出函数
	{	int j = 0;
		set<int>::iterator i;
		for (i = S.begin(); i != S.end(); ++i)
			v[j++] = *i;
	}
};

【注意】不管你按什么顺序输入，你得到的输出都是有序的。

2）数组（类似于插入排序）哨兵放最后

思路：初始化时候，取一个很大元素作为哨兵，哨兵永远置于元素最后。

插入时候遇到重复元素，返回

遇到比自己大的第一个元素，将该元素以及以后的元素后移一位，最后将该元素插入该位置

class IntSetArr {
private:
	int	n, *x;
public:
	IntSetArr(int maxelements, int maxval)
	{	x = new int[1 + maxelements];//先申请个数  +1  说明用到哨兵了
		n=0;
		x[0] = maxval; /* sentinel at x[n] */
	}
	int size() { return n; }
	void insert(int t)
	{	int i, j;
		for (i = 0; x[i] < t; i++)//遇到比要插入元素 t 还小的 就后走
			;
		if (x[i] == t)//说明数组中已经包含t
			return;
		for (j = n; j >= i; j--)//
			x[j+1] = x[j];
		x[i] = t;
		n++;
	}
	void report(int *v) //按序输出每一个元素
	{	for (int i = 0; i < n; i++)
			v[i] = x[i];
	}
};

3）链表（采用递归）依然采用哨兵

思路：node *rinsert(node *p, int t)是关键函数
注意调用的时候，p->next=rinsert(p->next,t); 如果小于则一直等于next
如果p-val > t 则 p =new node(t,p);说明第一个大于t的p被作为新节点（val=t）的next //细细体会，最好画图理解

<span style="font-size: 18px;">
</span>

class IntSetList {
private:
	int	n;
	struct node {
		int val;
		node *next;
		node(int i, node *p) { val = i; 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;
	}
public:
	IntSetList(int maxelements, int maxval)  //初始化函数时候，将哨兵置于第一个
	{	sentinel = head = new node(maxval, 0);
		n = 0;
	}
	int size() { return n; }
	void insert(int t) { head = rinsert(head, t); } //调用递归插入函数
	void insert2(int t)
	{	node *p;
		if (head->val == t)
			return;
		if (head->val > t) {
			head = new node(t, head);
			n++;
			return;
		}
		for (p = head; p->next->val < t; p = p->next)
			;
		if (p->next->val == t)
			return;
		p->next = new node(t, p->next);
		n++;
	}
	void insert3(int t)//类似数组的插入
	{	node **p;
		for (p = &head; (*p)->val < t; p = &((*p)->next))//找到第一个大于等于p的节点
			;
		if ((*p)->val == t)
			return;
		*p = new node(t, *p);//创建节点的同时，将节点插入到正确位置
		n++;
	}
	void report(int *v)//输出整个链表
	{	int j = 0;
		for (node *p = head; p != sentinel; p = p->next)
			v[j++] = p->val;
	}
};

第二种实现方法（链表非递归）：主要是找到第一个大于t的节点，然后插入到其前面。

class IntSetList2 {
private:
	int	n;
	struct node {
		int val;
		node *next;
	};
	node *head, *sentinel, *freenode;
public:
	IntSetList2(int maxelements, int maxval)//最大元素个数和哨兵
	{	sentinel = head = new node;
		sentinel->val = maxval;
		freenode = new node[maxelements];
		n = 0;
	}
	int size() { return n; }
	void insert(int t)
	{	node **p;
		for (p = &head; (*p)->val < t; p = &((*p)->next))
			;
		if ((*p)->val == t)
			return;
		freenode->val = t; //将t插入到第一个大于t的元素的前面
		freenode->next = *p;
		*p = freenode++;
		n++;
	}
	void report(int *v)
	{	int j = 0;
		for (node *p = head; p != sentinel; p = p->next)
			v[j++] = p->val;
	}
};

4）二分搜索树（类似链表）

class IntSetBST {
private:
	int	n, *v, vn;
	struct node {
		int val;
		node *left, *right;
		node(int v) { val = v; left = right = 0; }
	};
	node *root;
	node *rinsert(node *p, int t)
	{	if (p == 0) {
			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);
		} // do nothing if p->val == t
		return p;
	}
	void traverse(node *p)//中序遍历输出
	{	if (p == 0)
			return;
		traverse(p->left);
		v[vn++] = p->val;
		traverse(p->right);
	}
public:
	IntSetBST(int maxelements, int maxval) { root = 0; n = 0; }
	int size() { return n; }
	void insert(int t) { root = rinsert(root, t); }
	void report(int *x) { v = x; vn = 0; traverse(root); }
};

第二种实现方法 （习题7答案，采用哨兵）

class IntSetBST2 {
private:
	int	n, *v, vn;
	struct node {
		int val;
		node *left, *right;
	};
	node *root, *freenode, *sentinel;

	void traverse(node *p)
	{	if (p == sentinel)
			return;
		traverse(p->left);
		v[vn++] = p->val;
		traverse(p->right);
	}
public:
	IntSetBST2(int maxelements, int maxval)
	{	root = sentinel = new node;  
		n = 0;
		freenode = new node[maxelements];
	}
	int size() { return n; }

	void insert(int t)
	{	sentinel->val = t;
		node **p = &root;       //指向指针的指针
		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) { v = x; vn = 0; traverse(root); }
};

5）专门用于整数处理的数据结构

class IntSetBitVec {
private:
	enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
	int	n, hi, *x;
	void set(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)); }
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;
	}
	int size() { return n; }
	void insert(int t)
	{	if (test(t))
			return;
		set(t);
		n++;
	}
	void report(int *v)
	{	int j=0;
		for (int i = 0; i < hi; i++)
			if (test(i))
				v[j++] = i;
	}
};

解释：其中i>>SHIFT 相当于 i/32得到对应数组下标【二进制右移5位相当于十进制除以32】
i&MASK相当于 i mod 32，因为每一个数32位。最大只能左移32位。

1<<(i&MASK)相当于获得2的(i&MASK)次幂，就是1左移(i&MASK)位

i=[0,31] 标记在数组第一位 i=[32,63] 标记在数组第二位

下面看一个例子：

#include <iostream>

using namespace std;
int a[10] = {0};
const int shift = 5;
const int maskl = 0x1F;
void setB(int i)
{
 a[i>>shift] |=1<<(i&maskl);
}
void cls(int i)
{
 a[i>>shift] &=~(1<<(i&maskl));
}
int test(int i)
{
 return a[i>>shift] &(1<<(i&maskl));
}
int main()
{
 int num[] = {1,2,3,5,6,4,7,8,9};
 cout<<a[0]<<"   a[0]"<<endl;
 for (int i=0;i<9;i++)
 {
  setB(num[i]);
  cout<<num[i]<<endl;
  cout<<a[0]<<"   a[0]"<<endl;
 }
 for (int i=0;i<9;i++)
 {
  if (test(num[i]))
  {
   cout<<num[i]<<" is set"<<endl;
  }
  else
  {
   cout<<num[i]<<"is not set"<<endl;
   cout<<a[0]<<endl;
  }
 }
 system("pause");
}

【拓展】如何输出一个数的二进制表示

#include <iostream>
using namespace std; 
int main()
{
    int n;
    cout << "input n:";
    cin >> n;
    for(int i=1; i<=32; i++)
    {
       cout << (n<0?1:0); //如果首位为1则为负数 所以小于0 
       n = n<<1;//左移一位
    }
    
    cout << endl;
   
   return 0;
}

利用库函数

#include <stdio.h> 
#include <stdlib.h> 

int   main() 
{ 
        int   i   =   31; 
        char   s[10]; 
  
        itoa(i,   s,   2);     //转换成字符串，进制基数为2 
        printf( "%s ",s);     //输出 

}

用法：char *itoa(int value, char *string, int radix);

　int value 被转换的整数，char *string 转换后储存的字符数组，int radix 转换进制数，如2,8,10,16 进制等

功能：把一整数转换为字符串。

【另一个】atoi （array to integer） ：把字符串转化为整数

int atoi(const char *nptr);

用法：char *str = "12345.67";

　　 n = atoi(str); //输出12345

6）箱（类似散列表）

思路：每一个箱表示一定范围的整数，并用链表链接起来。链表插入采用有序插入，见：3）链表

class IntSetBins {
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;
	}
public:
	IntSetBins(int maxelements, int pmaxval)
	{	bins = maxelements;
		maxval = pmaxval;
		bin = new node*[bins];
		sentinel = new node(maxval, 0);
		for (int i = 0; i < bins; i++)
			bin[i] = sentinel;
		n = 0;
	}
	int size() { return n; }
	void insert(int t)
	{	int i = t / (1 + maxval/bins);  // CHECK !  映射到某个箱子中
		bin[i] = rinsert(bin[i], t);
	}
	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;
	}
};

二，习题

1）12章的代码

void getSet(int m,int n)//在0 -- n-1 中挑选m个 随机数 
{
    srand(time(NULL));//这个很关键 
    set<int> S;
    for(int i=n-m;i<n;++i)
    {
        int t=rand()%(i+1);
        if(S.find(t) == S.end())
                S.insert(t);
        else
                S.insert(i);
    } 
    set<int>::iterator j;
    for(j=S.begin();
         j!=S.end();++j)
    cout<<*j<<" "; 
}

感觉最关键是要想到，i从n-m开始，如果在i之前找到无重复的数，则insert。否则insert( i )

其实用IntSetSTL 类实现差不多。

2）更改的更健壮，添加错误检查（插入数据是否在范围内，集合是否插满），析构函数（不解释）

3）find( t ) //对于有序集合来说，采用二分查找很合适

4）链表的迭代版本（见上文）核心插入代码如下

void insert(int t)
{	node **p;
	for (p = &head; (*p)->val < t; p = &((*p)->next))
			;
	if ((*p)->val == t)
		return;
	freenode->val = t; //将t插入到第一个大于t的元素的前面
	freenode->next = *p;
	*p = freenode++;
	n++;
}

5）为了避免每次都创造结点（新建一个结点，调用一次存储分配）。

可以一次申请一个结点数组 freenode =new node[maxelements];

用的时候，node p =freenode++; //保证freenode 总是指向当前可用空间

7）感觉答案有些疑惑。哨兵为当前值，放到每个null结点。然后用**p 查找插入位置。这里是不是没有考虑重复插入的问题？？

9）将除法操作变为右移操作，乘法操作变为左移操作。注意 >> << 移位操作符都是二进制移位

除以 4 相当于 >>2 除以8 相当于 >>3 那么除以 6呢？？