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

比眉伴天荒 2023-06-04 04:58 25阅读 0赞

在这里我们将待生成的数据结构称为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();
    };

转载于:https://www.cnblogs.com/qwj-sysu/p/4048534.html