问题描述
本章是围绕着搜索问题展开讨论的，搜索问题形形色色。编译器查询变量名以得到其类型和地址，拼写检查器查字典以确保单词拼写正确，电话号码簿程序查询用户名以得到其电话号码，因特网域名服务器查找域名来发现IP地址，上述引用以及很多类似的应用都需要搜索一组数据，以找到与特定项相关的信息。 本章继续讨论上一章的问题：生成[0,maxval]范围内m个随机整数的有机序列，不允许重复。 定义了5个数据结构来解决这个问题：
下面详细给出其思想与程序实现。
公有接口
将待生成的数据结构称为IntSet，指整数集合，用下面的C++类来表示：
#ifndef _INTSETIMP_H_#define _INTSETIMP_H_/**//* 《编程珠玑》第十三章 搜索 * 定义一个所有实体类的公共接口 *//**/class IntSetImp{public:};#endif
如上所示，类IntSetImp的构造函数将集合初始化为空，该函数有两个参数，分别表示集合元素的最大个数和集合元素的最大值；insert函数向集合中添加一个新的不重复整数，而report函数是将 所有元素按顺序写入向量v中。
有序数组结构
首先，使用整数数组这样一个最简单的结构来建立第一个集合实现：
#ifndef _INTSETARRAY_H_#define _INTSETARRAY_H_#include <iostream>/************************************************************************//* * 方案一：使用有序数组作为数据结构解决该问题 *//************************************************************************/class IntSetArray {private:int n;int *x;public:IntSetArray(int maxelements, int maxval){x = new int[1 + maxelements];n = 0;x[0] = maxval;}int size(){return n;}//采用直接插入，按照升序插入数据void insert(int t){int i;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++;}void report(int *v){for (int i = 0; i < n; i++)v[i] = x[i];}};#endif
以上代码为用有序数组作为数据结构解决目标的问题的类实现代码，构造函数中为数组分配空间（多分配一个元素的空间给哨兵用）；insert函数顺序搜索数组，采用直接插入算法插入目标元素，不插入重复数据； main主测试程序代码如下：
/************************************************************************//* 《编程珠玑》第十三章 搜索问题* 问题：程序的输入包含两个整数m和n，其中m<n。输出是0~n-1范围内m个随机整数的有序列表，不允许重复* 方案一：用有序数组数据结构实现*//************************************************************************/#include <iostream>#include <algorithm>#include <cstdlib>#include “IntSetImp.h”#include “IntSetArray.h”using namespace std;bigRand(){return RAND_MAX * rand() + rand();}randint(int l, int u){return l + bigRand() % (u – l + 1);}randArray(int m, int n){int *x = new int[n];IntSetArray arr(m , n);while (arr.size() < m)arr.insert(bigRand() % n);arr.report(x);for (int i = 0; i < m; i++)cout << x[i] << “\t”;cout << endl;}int main(){int m = 5, n = 10;while (cin >> n >> m){randArray(m, n);}system(“pause”);return 0;}
运行结果：
有序链表结构
如果事先知道集合的大小，那么数组是一种比较理想的结构，因为数组是有序的，我们可以用二分搜索建立一个运行时间为O(logn)的成员函数。 如果事先不知道集合的大小，那么链表将是表示集合的首选结构，而且链表还能省去插入时元素移动的开销。 结构具体实现如下：
#ifndef _INTSETLIST_H_#define _INTSETLIST_H_#include <iostream>/************************************************************************//** 方案二：使用有序链表作为数据结构解决该问题*//************************************************************************/class IntSetList{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;}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 report(int *v){int j = 0;for (node *p = head; p != sentinel; p = p->next)v[j++] = p->val;}};#endif看了哪些风景，遇到哪些人。尽管同学说，去旅行不在于记忆，
