Ниже приведен полный листинг классов, использовавшихся в главе 13 для представления наборов целых чисел. Исходный код целиком можно скачать с сайта книги.
class IntSetSTL { private.
set S , publ i с
IntSetSTL( l nt maxelements . int maxval) { } mt size() { return 5 size(). } void insert (int t) { S msert(t),} void report(int *v)
{ i nt j - 0 . set iterator i ,
for (i=5 begin(), i > = S end(). ++i ) v[J + +] - ,
class IntSetArr { private- int n, *x, publiс
IntSetArr(int maxelements, int maxval)
{ x = new int[1 + maxelements], n=0 .
x[0] = maxval, /* sentinel at x[n] */}
int size( ) { return n , } void insert(int t)
{ int 1. J.
for (i = 0, x[i] < t. i++)
if (x[i] == t)
return. for (j = n. j >= 7. j--) x[j+l] = x[j]. x[i] = t. n+ +}
void report(int *v)
{ for (int i = 0. i < n, l++) v[i] = x[i ].}
class IntSetList { private int n, struct node { int va1. node *next.
node(int i, node *p) { val = i, next = p, }}.
node *head , *sent inel, node *rinsert(node *p. int t)
{ if (p->va1 < t) {
p->next = rinsert(p->next. t).
} else if (p->va1 > t) { p = new node(t, p) , n++.}
return p.}
publ i с
IntSetList(i nt maxelements, int maxval)
{ sentinel - head = new node(maxval, 0). n = 0.}
int slze() { return n , }
void insert(int t) { head = rinsert(head. t), } void report(int *v)
{ int j = 0,
for (node *p = head, p l= sentinel, p = p->next) v[j++] = p->val ,}
} -
class IntSetBST { private
int n, *v. vn, struct node { int val.
node *1 eft. *right:
node(int v) { val = v, left = right = 0, }}
node *root,
node *rinsert(node *p, int t)
{ lf (p == 0) {
p = new node(t) , n++ ,
} else if (t < p->val) { p->left = nnsert(p->left. t),
} else if (t > p->val) { p - > r i g h t = nnsert(p->nght. t).
} // do nothing if p->val == t return p,}
void traverse(node *p)
{ if (p == 0) return, t raverse(p->1 eft), v[vn++] = p->val; traverse(p->right),}
publi с ¦
IntSetBST(int maxelements, int maxval) { root = 0, n = 0. } int sizeO { return n; }
void insert(int t) { root = rinsert(root. t), } void report(int *x) { v = x, vn = 0, t ra verse (root) , }
class IntSetBitVec { private.
enum { BITSPERWORD = 32, SHIFT = 5, MASK = OxlF }. int n, hi, *x.
void set (i nt i) { x[i»SHIFT] |* (l«(i & MASK)), } void cl r (i nt i) { x[ i >>SH I FT] & = ~(l«(i & MASK)), } int test(int i) {return x[i>>SHIFT] & С1<<Сl& MASK)), } publi с .
IntSetBitVec(int maxelms. int maxval)
{ hi = maxval,
x - new int[l+hi/BITSPERWORD], for (int i = 0; i < hi, i ++) clr(i ) , n = 0.}
int size() { return n, } void insert(int t)
{ i f (test(t)) ret urn , set(t) ; n + +:}
void report(int *v)
{ int j = 0.
for (i nt i = 0; i < hi. i++) i f (test(i))
v [ J ++ ] =* i ;}} class IntSetBins { pri vate
i nt n, bi ns , maxval , struct node { l nt val; node *next;
node(int v, node *р) { val = v; next = p, }}•
node **bin, *sentinel; node *rinsert(node *p. int t)
{ if (p->val < t) {
p->next - nnsert(p->next, t).
} else if (p->va1 > 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 ++) bi n[l ] * sentinel , n - 0;}
int sizeO { return n, } void i nsert(int t)
{ int i ~ t / (1 + maxva1/bins) , // CHECK 1 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 :}
}. |
Главная
Каталог файлов
