生成[0 maxval]范围内m个整数的随机有序序列.

1,借助于容器set实现.

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

class IntSetSTL
{
public:
    IntSetSTL(int max,int num){}
    int size(){ return S.size(); }
    void insert(int t){ S.insert(t); }
    void report(int* v)
    {
        int i=0;
        for(set<int>::iterator ite=S.begin();ite!=S.end();ite++)
            v[i++]=*ite;
    }
private:
    set<int> S;
};

void generateSetSTL(int m,int maxVal)
{
    int* v=new int[m];
    IntSetSTL stl(maxVal,m);
    while(stl.size()<m)
        stl.insert(rand()%(1+maxVal));
    stl.report(v);
    for(int i=0;i<m;i++)
        cout<<v[i]<<endl;
    cout<<endl;
    delete[] v;

}

int main ()
{
    srand(time(0));
    const int maxVal=100;
    const int m=10;
    generateSetSTL(m,maxVal);
	return 0 ;
}

2,用数组实现

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

class IntSetArray
{
public:
    IntSetArray(int maxVal,int m)
    {
        a=new int[m+1];
        //设置一个哨兵
        n=0;
        a[0]=maxVal;
    }
    int size(){ return n; }
    void insert(int t)
    {
        int i;
        for(i=0;a[i]<t;i++)
            ;
        if(a[i]==t)
            return;
        for(int j=size();j>=i;j--)
            a[j+1]=a[j];
        a[i]=t;
        n++;
    }
    void report(int* v)
    {
        for(int i=0;i<size();i++)
            v[i]=a[i];
    }
private:
    int* a;
    int n;
};

void generateSetArray(int m,int maxVal)
{
    int* v=new int[m];
    IntSetArray array(maxVal,m);
    while(array.size()<m)
        array.insert(rand()%maxVal);
    array.report(v);
    for(int i=0;i<m;i++)
        cout<<v[i]<<endl;
    cout<<endl;
    delete[] v;

}

int main ()
{
    srand(time(0));
    const int maxVal=100;
    const int m=10;
    generateSetArray(m,maxVal);
	return 0 ;
}

3,用链表实现

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

struct Node
{
    Node(int i,Node* p):val(i),next(p){}
    int val;
    Node* next;
};

class IntSetList
{
public:
    IntSetList(int maxVal,int m)
    {
        sentinel=head=new Node(maxVal,NULL);
        n=0;
    }
    int size(){ return n; }
    void insert(int t)
    {
        head=rinsert(head,t);
    }
    void report(int* v)
    {
        int i=0;
        for(Node* p=head;p!=sentinel;p=p->next)
            v[i++]=p->val;
    }
private:
    //这里nb的递归
    Node* rinsert(Node* p,int t)
    {
        if( t>(p->val) )
            p->next=rinsert(p->next,t);
        else if( t<(p->val) )
        {
            p=new Node(t,p);
            n++;
        }
        return p;
    }
    Node* head;
    //哨兵节点
    Node* sentinel;
    int n;
};

void generateSetList(int m,int maxVal)
{
    int* v=new int[m];
    IntSetList list(maxVal,m);
    while(list.size()<m)
        list.insert(rand()%maxVal);
    list.report(v);
    for(int i=0;i<m;i++)
        cout<<v[i]<<endl;
    cout<<endl;
    delete[] v;

}

int main ()
{
    srand(time(0));
    const int maxVal=100;
    const int m=10;
    generateSetList(m,maxVal);
	return 0 ;
}

4,用二叉搜索树实现

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

struct Node
{
    Node(int i):val(i),lchild(NULL),rchild(NULL){}
    int val;
    Node* lchild;
    Node* rchild;
};

class IntSetBST
{
public:
    IntSetBST(int maxVal,int m):root(NULL),n(0){}
    int size(){ return n; }
    void insert(int t)
    {
        root=rinsert(root,t);
    }
    void report(int* x)
    {
        v=x;
        vn=0;
        traverse(root);
    }
private:
    //这里nb的递归
    Node* rinsert(Node* p,int t)
    {
        if(p==NULL)
        {
            p=new Node(t);
            n++;
        }
        else if( t>(p->val) )
        {
            p->rchild=rinsert(p->rchild,t);
        }
        else if( t<(p->val) )
        {
            p->lchild=rinsert(p->lchild,t);
        }
        return p;
    }
    void traverse(Node* p)
    {
        if(p==NULL)
            return;
        traverse(p->lchild);
        v[vn++]=p->val;
        traverse(p->rchild);
    }
    Node* root;
    int n;
    int *v,vn;
};

void generateSetBST(int m,int maxVal)
{
    int* v=new int[m];
    IntSetBST bst(maxVal,m);
    while(bst.size()<m)
        bst.insert(rand()%maxVal);
    bst.report(v);
    for(int i=0;i<m;i++)
        cout<<v[i]<<endl;
    cout<<endl;
    delete[] v;

}

int main ()
{
    srand(time(0));
    const int maxVal=100;
    const int m=10;
    generateSetBST(m,maxVal);
	return 0 ;
}

5,用比特位向量实现.

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

class IntSetBitVector
{
public:
    IntSetBitVector(int maxVal,int m):hi(maxVal),n(0),x(new int[maxVal/BITSPERWORD+1])
    {
        for(int i=0;i<hi;i++)
            clear(i);
    }
    int size(){ return n; }
    void insert(int t)
    {
        if(!test(t))
        {
            set(t);
            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};
    void set(int i)
    {
        x[i>>SHIFT]|=(1<<(i&MASK));
    }
    void clear(int i)
    {
        x[i>>SHIFT]&=~( 1<<(i&MASK) );
    }
    int test(int i)
    {
        return x[i>>SHIFT]&(1<<(i&MASK));
    }

    int n,hi;
    int* x;
};

void generateSetBitVector(int m,int maxVal)
{
    int* v=new int[m];
    IntSetBitVector bitVector(maxVal,m);
    while(bitVector.size()<m)
        bitVector.insert(rand()%maxVal);
    bitVector.report(v);
    for(int i=0;i<m;i++)
        cout<<v[i]<<endl;
    cout<<endl;
    delete[] v;

}

int main ()
{
    srand(time(0));
    const int maxVal=100;
    const int m=10;
    generateSetBitVector(m,maxVal);
	return 0 ;
}