学步园

 题目：生成一个随机整数的有序集合

1 线性结构

数组  链表

2 二分搜索树

3 位向量

#include <iostream>

using namespace std;

enum {BITSPERWORD=32,SHIFT=5,MASK=0x1F};
class IntSetBitVec
{
public:
	IntSetBitVec(int maxelements,int maxval);
	void report(int *v);
	void insert(int t);
	int NumOfElements() {return n;}
private:
	int n,hi,*x;
	void set(int i) {       x[i>>SHIFT] |= (1<<(i&MASK));}
	void clr(int i) {       x[i>>SHIFT] &=~(1<<(i&MASK));}
	int test(int i) {return x[i>>SHIFT] &  (1<<(i&MASK)); }
};
IntSetBitVec::IntSetBitVec(int maxelements, int maxval)
{
	n=0;
	hi=maxval;
	x=new int[1+hi/BITSPERWORD];
	for(int i=0;i<=hi;i++)
		clr(i);
}
void IntSetBitVec::report(int *v)
{
	int j=0;
	for(int i=0;i<=hi;i++)
		if (test(i))
			v[j++]=i;
}

void IntSetBitVec::insert(int t)
{
	if (test(t))
	{
		return;
	}
	set(t);
	n++;
}

void GenSet(int m,int maxval)
{
	int *v=new int[m];
	IntSetBitVec intSet(m,maxval);
	while (intSet.NumOfElements()<m)
		intSet.insert(rand()%maxval);
	intSet.report(v);
	for (int i=0;i<m;i++)
	{
		cout<<v[i]<<" ";
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	GenSet(500,10000);
	return 0;
}

4  箱

#include <iostream>
using namespace std;
struct node
{
	int val;
	node* next;
	node(int v,node* p){val=v;next=p;}
};
class IntSetBins
{
public:
	IntSetBins(int maxelement,int pmaxval);
	void insert(int t);
	void report(int* v);
	int NumOfElements() {return n;}

private:
	node* rinsert(node* p,int t);
	int n,bins,maxval;
	
	node **bin,*sentinel;//sentinel 哨兵

};



IntSetBins::IntSetBins(int maxelement,int pmaxval)
{
	bins=maxelement;
	maxval=pmaxval;
	bin=new node*[bins];
	sentinel=new node(maxval,0);
	for (int i=0;i<bins;i++)
	{
		bin[i]=sentinel;
	}
	n=0;
}

node* IntSetBins::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;
}
void IntSetBins::insert(int t)
{
	int i=t/(1+maxval/bins);
	bin[i]=rinsert(bin[i],t);

}

void GenSet(int m,int maxval)
{
	int *v=new int[m];
	IntSetBins intSet(m,maxval);
	while (intSet.NumOfElements()<m)
		intSet.insert(rand()%maxval);
	intSet.report(v);
	for (int i=0;i<m;i++)
	{
		cout<<v[i]<<" ";
	}
}

void IntSetBins::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;
		}

}


int _tmain(int argc, _TCHAR* argv[])
{
	GenSet(100,10000);
	return 0;
}

5 上面这些数据结构和算法的平均性能如下

集合表示    初始化     insert      report       总时间       空间

数组                1               m             m         O(m*m)        m

链表                1               m             m         O(m*m)        2m

二叉树            1               logm        m       O(mlogm       3m

箱                    m               1              m         O(m)              3m

位相量             n                1               n           O(n)              n/b

将递归函数重写为迭代器版本可以使链表的速度提升为原来的3倍，但只能使箱提速10%.对于大多数数据结构来说，引入哨兵可以获得清晰、简单的代码，并缩短运行时间。