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

一，概述
        第十二章，介绍生成某个范围内随机数，并按顺序输出。
        本章主要介绍，存储按序输出的容器或者说存放集合的方法。并实现按序插入，按序输出。
        1）set容器
              1>set容器小例子：
[html]
#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容器实现插入元素，并有序输出
[html]
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）数组（类似于插入排序）哨兵放最后
            思路：初始化时候，取一个很大元素作为哨兵，哨兵永远置于元素最后。
                       插入时候遇到重复元素，返回
                                      遇到比自己大的第一个元素，将该元素以及以后的元素后移一位，最后将该元素插入该位置
[html]
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 //细细体会，最好画图理解
[html]
<span style="font-size:18px;">
</span>
[html]
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

补充：软件开发 , 其他 ,