首页 > 代码库 > 如何生成[0,maxval]范围内m个随机整数的无重复的有序序列

如何生成[0,maxval]范围内m个随机整数的无重复的有序序列

在这里我们将待生成的数据结构称为IntSet,接口定义如下:

class IntSetImp{public:    IntSetImp(int maxelements,int maxval);    void insert(int t);    int size();    void report(int *v);//将集合中的元素写入到向量v中};

 

一个使用的范例是:

void gensets(int m,int maxval){    int *v = new int[m];    IntSetImp S(m,maxval);    while(S.size()<m) {        S.insert(bigrand()%maxval);    }    S.report(v);    for (int i = 0; i < m; ++i)    {        cout<<v[i]<<"\n";    }}

 

下面我们来探讨如何实现这个问题,用各种数据结构来实现我们想要的功能以及比较他们的性能。

1:使用强大而通用的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 IntSetArray{private:    int n,*x;//n保存元素个数,x保存数组public:    IntSetArray(int maxelements,int maxval)    {        x=new int[1+maxelements];        n=0;        x[0]=maxval;//maxval 作为哨兵,总是位于已排序元素的最后    }    int size(){return n;}    void insert(int t)    {        int i;//record        for(i=0;x[i]<t;i++) ;        if(x[i]==t) return;//already in array        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];        }    }};

 

如果实现知道数组(集合)的大小,那么数组将会是一种比较较理想的结构,因为数组是有序的,并且支持随机访问,可以用二分搜索建立一个运行时间为O(logN)的搜索函数

3:但如果不知道集合的大小,那么链表将会是表示集合的首选结构,并且链表还能省去插入时元素移动的开销

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)    {        head=sentinel=new node(maxval,0);        n=0;    }    int size(){return n;}    int 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;    }};

 4:下面考虑支持快速搜索和插入的结构--二分搜索树

class IntSetBST{private:    int n,*v,vn;    struct node    {        int val;        node *left,*right;        node(int i){val=i;left=right=0;}    };    void rinsert(p,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);        return p;    }    void traverse(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);}};

 

 

5:现在我们将看到一个更高级的结构,利用整数特性的结构--位向量

class IntSetBitVec{private:    enum { BITSPERWORD=32,SHIFT=5,MASK=0x1F;};//BITSPERWORD和 SHIFT 是对应的, 0x1F的是31,即是11111,五位的掩码    int n,*x,hi;    void set(int i) {          x[i>>SHIFT] |=  (1<<(i & MASK));}//i & MASK 取出i的后五位,1<<(i & MASK)=2的(i & MASK)次幂    void clr(int i) {          x[i>>SHIFT] &= ~(1<<(i & MASK));}    void test(int i){ return x[i>>SHIFT] &   (1<<(i & MASK));}  /*i = 42 --> i&MASK        1<<(i&MASK)     ~(1<<10)      i>>SHIFT    42=101010  101010        1<<10=2^10     =~10000000000 =101010>>5              & 11111       =10000000000    = 01111111111 =1              -------               001010=10     clr(i) --> x[i>>SHIFT]=0    set(i) --> x[i>>SHIFT]=0|2的(i & MASK)次幂=2的(i & MASK)次幂      test(i) -> 如果已经set(i) 2的(i & MASK)次幂 & 2的(i & MASK)次幂=2的(i & MASK)次幂 返回True                 否则 0 & 。。。=0 返回False     */    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(i)) return;        set(t);        n++;    }    void report(int *v)    {        int j=0;        for (int i = 0; i < hi; ++i)        {            if(test(i)) v[j++]=i;        }    }};

 

位向量的不足是如果n比较大,需要的内存也是比较大的

6:最后的一个数据结构结合了链表和位向量的优点,她在箱序列中放入整数

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);        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;    }    ~IntSetBins();};

 

如何生成[0,maxval]范围内m个随机整数的无重复的有序序列