编程珠玑中的用箱生一定范围内生成整数的有序序列
问题：如何在[0,maxval]范围内生成一组有序不重复的m个整数
解决方案：可以采用有序数组和有序链表等线性结构，还可以采用二叉排序树。最后还可以采用箱和位向量这样的高效数据结构。
首先，简单的介绍下箱。
使用的是箱这样一种高效的数据结构来完成这样一个任务，箱结合了链表和位向量（位图）的特点,箱还具有散列的一些特点
*如果我们有0~99范围内的四个整数，就将它们放在4个箱中,箱0包含0~24的整数，箱1包含25~49的整数,箱2包含50~74的整数,箱3包含75~99的整数,
*例如26 31 42 59这4个数，如下所示
1号箱中 ->26
2号箱中 ->31 42
3号箱中 ->59
4号箱中 ->为空
这m 个箱可以看作一个散列,每个箱中的整数用有序链表表示，由于整数是均匀分布的，所以每个链表的期望长度为1
箱相对于位向量而言，在有一个有限范围内要生成的数相对稀疏一些就有明显的优势.
IntSet.h
1 #ifndef _h_IntSet
2 #define _h_IntSet
3
4 /*
5 *如何在[0,maxval]范围内生成一组有序不重复的m个整数
6 */
7
8
9 /*
10 *使用的是箱这样一种高效的数据结构来完成这样一个任务，箱结合了链表和位向量（位图）的特点,箱还具有散列的一些特点
11 */
12
13
14
15 class IntSet
16 {
17 public:
18 IntSet(int maxNums,int maxVal);
19 void insert(int val);
20 void report(int *arr);
21 int size(){return cnt;}
22 ~IntSet();
23 private:
24 int cnt,bins,maxVal;
25 struct Node
26 {
27 int val;
28 struct Node *next;
29 Node(int v,struct Node *pNext):val(v),next(pNext)
30 {}
31
32 void *operator new(size_t);//重载new，delete，自己管理内存,一次性分配好maxElements个结点
33 void operator delete(void *,size_t);
34
35 static Node *free_store;
36 static int num;
37 };
38
39 Node **bin,*sentinel;//sentinel作哨兵来用，sentinel指向值为maxVal的节点
40
41
42 void ListInsert(Node * &head,int val);//向head所指向的有序列表插入val，如果val已经存在，则什么也不做
43 };
44
45 #endif
IntSet.cpp
1 #include"IntSet.h"
2 #include<cstdio>
3 #include<cassert>
4 #include<iostream>
5
6 using namespace std;
7
8 /*
9 *如何在[0,maxval]范围内生成一组有序不重复的m个整数
10 */
11
12
13 /*
14 *使用的是箱这样一种高效的数据结构来完成这样一个任务，箱结合了链表和位向量（位图）的特点,箱还具有散列的一些特点
15 *如果我们有0~99范围内的四个整数，就将它们放在4个箱中,箱0包含0~24的整数，箱1包含25~49的整数,箱2包含50~74的整数,箱3包含75~99的整数,
16 *例如26 31 42 59这4个数，如下所示
17 *1号箱中 ->26
18 *2号箱中 ->31 42
19 *3号箱中 ->59
20 *4号箱中 ->为空
21 *这m 个箱可以看作一个散列,每个箱中的整数用有序链表表示，由于整数是均匀分布的，所以每个链表的期望长度为1
22 *箱相对于位向量而言，在有一个有限范围内要生成的数相对稀疏一些就有明显的优势.
23 */
24
25
26 IntSet::IntSet(int maxNums,int maxVal)
27 {
28 this->maxVal=maxVal;
29 bins=maxNums;
30
31 bin=new Node *[bins];
32 sentinel=new Node(maxVal,NULL);//sentinal作为所有箱中的有序列表的公共哨兵
33
34
35 for(int i=0;i<bins;i++)//初始中每个箱中元素有空
36 {
37 bin[i]=sentinel;
38 }
39
40 cnt=0;
41 }
42
43
44
45 //向head所指向的有序列表插入val，如果val已经存在，则什么也不做
46 void IntSet::ListInsert(Node * &head,int val)
47 {
48 Node *p=NULL,*lastP=NULL;
49 for(p=head;val>p->val;p=p->next)
50 {
51 lastP=p;
52 }
53
54 if(val==p->val)
55 {
56 return;
57 }
58 if(p==head)
59 {
60 head=new Node(val,head);
61 cnt++;
62 return;
63 }
64 else
65 {
66 Node *newNode=new Node(val,p);
67 lastP->next=newNode;
68 cnt++;
69 }
70 }
71
72 void IntSet::insert(int val)
73 {
74 int index=val/(maxVal/bins+1);
75
76 ListInsert(bin[index],val);
77 }
78
79 void IntSet::report(int *arr)
80 {
81 int j=0;
82 for(int i=0;i<bins;i++)
83 {
84 Node *p=bin[i];
85
86 for(;p!=sentinel;p=p->next)
87 {
88 arr[j++]=p->val;
89 }
90 }
91 assert(j==cnt);
92 }
93
94 IntSet::~IntSet()
95 {
96 for(int i=0;i<bins;i++)
97 {
98 Node *p=bin[i];
99 Node *lastP=p;
100
101 for(;p!=sentinel;)
102 {
103
104 lastP=p;
105 p=p->next;
106 delete lastP;
107
108 }
109 }
110
111 delete sentinel;
112 }
113
114
115 //重载new
116 void *IntSet::Node::operator new(size_t size)
117 {
118 Node *p;
119 if(free_store==NULL)
120 {
121 p=free_store=(Node *)(new char[num*size]);
122 for(int i=0;i<num-1;i++)
123 {
124 p->next=p+1;
125 p++;
126 //cout<<"yes!\n" ;
127 }
128 p->next=NULL;
129
130 }
131 p=free_store;
132 free_store=free_store->next;
133 return p;
134 }
135
136
137 void IntSet::Node::operator delete(void *p,size_t size)
138 {
139 ((Node *)p)->next=free_store;
140 free_store=(Node *)p;
141 }
测试.cpp
1、关于编程学习中一些环境变量的使用认知
2、无提示关闭网页浏览器
3、eclipse 常用设置（四）- 去掉资源搜索框的.class文件 及 隐藏maven父级项目的引用查找
4、ahjesus Axure RP 7.0注册码
5、CF712E
1 /*
2 *如何在[0,maxval]范围内生成一组有序不重复的m个整数
3 */
4
5
6 /*
7 *使用的是箱这样一种高效的数据结构来完成这样一个任务，箱结合了链表和位向量（位图）的特点,箱还具有散列的一些特点,
8 *本程序用stl中的set和用箱写的IntSet作比较，当最大整数固定为n=10^8时，m越大IntSet越具有绝对的优势.
9 */
10
11 #include<iostream>
12 #include<cstdlib>
13 #include<ctime>
14 #include<vector>
15 #include<set>
16 #include<fstream>
17 #include<cassert>
18 #include"IntSet.h"
19
20
21
22 using namespace std;
23
24
25
26
27 IntSet::Node *IntSet::Node::free_store=NULL;
28 int IntSet::Node::num=5000000;
29
30
31 int main()
32 {
33 vector<int>arrNum;
34
35 const int MaxVal=100000000;
36 const int MaxNum=5000000;
37
38
39
40
41
42 clock_t begin,end;
43
44
45 srand(time(NULL));
46
47
48 ofstream out1("data1.txt");
49 ofstream out2("data2.txt");
50
51 if(!out1||!out2)
52 {
53 return 1;
54 }
55
56
57
58
59 for(int i=0;i<MaxNum;i++)
60 {
61 arrNum.push_back(rand()%MaxVal);
62 }
63
64
65
66 begin=clock();
67
68 /*采用IntSet的方案*/
69 IntSet mySet(MaxNum,MaxVal);
70 for(i=0;i<arrNum.size();i++)
71 {
72 mySet.insert(arrNum[i]);
73 }
74
75 int *arrOut=new int[mySet.size()];
76
77 mySet.report(arrOut);
78
79
80
81 for(int j=0;j<mySet.size();j++)
82 {
83 out1<<arrOut[j]<<" ";
84 }
85
86 end=clock();
87 cout<<"\n"<<(end-begin)*1.0/CLOCKS_PER_SEC<<"秒"<<endl;
88
89
90 //采用set方案
91 begin=clock();
92 set<int>stlSet;
93
94 vector<int>::iterator iter;
95 for(iter=arrNum.begin();iter!=arrNum.end();iter++)
96 {
97 stlSet.insert(*iter);
98 }
99 set<int>::iterator iter_;
100
101 for(iter_=stlSet.begin();iter_!=stlSet.end();iter_++)
102 {
103 out2<<*iter_<<" ";
104 }
105
106
107 end=clock();
108 cout<<"\n"<<(end-begin)*1.0/CLOCKS_PER_SEC<<"秒"<<endl;
109
110
111
112
113 out1.close();
114 out2.close();
115 return 0;
116 }
stl中set用了17.754秒
IntSet用了1.74秒
优质内容筛选与推荐>>1、关于编程学习中一些环境变量的使用认知
2、无提示关闭网页浏览器
3、eclipse 常用设置（四）- 去掉资源搜索框的.class文件 及 隐藏maven父级项目的引用查找
4、ahjesus Axure RP 7.0注册码
5、CF712E