Курсовая работа - Сравнение эффективности различных подходов к хранению данных
Подождите немного. Документ загружается.
/* friend class iterator;
class iterator
{
private:
set_RBT* s; // Ссылка на класс
int index; //Индекс
public:
iterator() : index(0) {}
iterator(set_RBT* st) : index(0), s(st) {}
iterator(set_RBT* st, bool) : index(st->ADRTableSize), s(st) {}
T& operator*() { return s->ADRTable[index]->data; }
T operator++() { return s->ADRTable[++index]->data; } //prefix
form
T operator++(int) { return s->ADRTable[index++]->data; }
//postfix form
iterator& operator+=(int amount) {
index+=amount;
return *this;
}
bool operator==(const iterator& rv) const {
return index == rv.index;
}
iterator& operator=(const iterator& rv) {
s = rv.s;
index = rv.index;
return *this;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
};
iterator begin() {return iterator(this);}
iterator end() {return iterator(this, true);}*/
};
int main(void)
{
randomize();
set_RBT<float> t;
int maxnum =TS;
float a;
/*
for (int ct = maxnum; ct; ct--)
{
a = rand() % 9 + 1;
cout<<"rand "<<a<<endl;
if (t.find(a) == 1)
{
t.delete_item(a);
cout<<"del "<<a<<endl;
}
else
{
t.insert(a);
cout<<"ins "<<a<<endl;
21
}
} */
for(int i=0;i<100;i++)
{
a = (float)i;
t.insert(a);
cout<<"a"<<a<<endl;
if(a==5)
{
t.delete_item(a);
cout<<"del 5 "<<t.find(a)<<endl;
}
}
for(int i=2;i<100;i++)
{
a = (float)i;
if (t.find(a) == 1) t.delete_item(a);
cout<<"a"<<a<<endl;
}
t.delete_item(1);
cout<<"del 1 "<<t.find(1)<<endl;
cin>>a;
return 0;
}
2.3.Слоеные списки (скип-листы)
#include<iostream>
#include<iterator>
#include <stdio.h>
#include <stdlib.h>
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
#define MAXLEVEL 15
template <class T>
class set_skip
{
private:
// Здесь данные, которые нужно скрыть, они для низкоуровнего
доступа
typedef struct Node_ {
T data; /* user's data */
struct Node_ *forward[1]; /* skip list forward pointer */
} Node;
typedef struct {
Node *hdr; /* list Header */
int listLevel; /* current level of list */
} SkipList;
SkipList list;
int _size;
public:
set_skip (void)
{
int i;
_size = 0;
if ((list.hdr = (Node *)malloc(sizeof(Node) + MAXLEVEL*sizeof(Node
*))) == 0) {
printf ("insufficient memory (initList)\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list.hdr->forward[i] = list.hdr;
22
list.listLevel = 0;
};
~set_skip () {// Удаление объекта
};
int size() { // Возвращает размер
return _size;
};
void insert(T data) // Метод вставки
{
int i, newLevel;
Node *update[MAXLEVEL+1];
Node *x;
/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != list.hdr && compLT(x-
>forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if ((x != list.hdr) && compEQ(x->data,
data)) return;
/* determine level */
for (newLevel = 0; rand() < RAND_MAX/2
&& newLevel < MAXLEVEL; newLevel++);
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel;
i++)
update[i] = list.hdr;
list.listLevel = newLevel;
}
/* make new node */
if ((x = (Node*)malloc(sizeof(Node) +
newLevel*sizeof(Node *))) == 0) {
printf ("insufficient memory (insertNode)\
n");
exit(1);
}
x->data = data;
/* update forward links */
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
_size++;
return;
};
void delete_item(T data) // Метод удаления элемента возвращает 1 -
если объект
// был удален 0 - если объекта не было в
set-е
{
int i;
Node *update[MAXLEVEL+1], *x;
/*******************************************
* delete node containing data from list *
*******************************************/
23
/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while ( x->forward[i] != list.hdr
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == list.hdr
|| !compEQ(x->data, data)) return;
/* adjust forward pointers */
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
_size--;
free (x);
/* adjust header level */
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == list.hdr))
list.listLevel--;
};
int find(T data) // Поиск
{
int i;
Node *x = list.hdr;
/*******************************
* find node containing data *
*******************************/
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != list.hdr
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
}
x = x->forward[0];
if (x != list.hdr && compEQ(x->data, data)) return (1);
return(0);
};
T& operator[] (int index)
{
Node *x = list.hdr;
int i=0;
while (i != (index+1))
{
i++;
x = x->forward[0];
}
return x->data;
};
class iterator
{
private:
set_skip* s; // Ссылка на класс
24
int index; //Индекс
public:
iterator() : index(0) {}
iterator(set_skip* st) : index(0), s(st) {}
iterator(set_skip* st, bool) : index(st->_size), s(st) {}
T& operator*()
{
Node *x = s->list.hdr;
int i=0;
while (i != (index+1))
{
i++;
x = x->forward[0];
}
return x->data;
}
T operator++() {
Node *x = s->list.hdr;
int i=0;
index++;
while (i != (index+1))
{
i++;
x = x->forward[0];
}
return x->data;
} //prefix form
T operator++(int) {
Node *x = s->list.hdr;
int i=0;
while (i != (index+1))
{
i++;
x = x->forward[0];
}
index++;
return x->data;
} //postfix form
iterator& operator+=(int amount) {
index+=amount;
return *this;
}
bool operator==(const iterator& rv) const {
return index == rv.index;
}
iterator& operator=(const iterator& rv) {
s = rv.s;
index = rv.index;
return *this;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
};
iterator begin() {return iterator(this);}
iterator end() {return iterator(this, true);}
};
25
int main (void)
{
set_skip<int> t;
for (int i=0; i < 100; i++)
t.insert(i);
for (int i=0; i < 100; i++)
cout<<t[i]<<" ";
for (int i=0; i < 100; i++)
cout<<t.find(i)<<" ";
cout<<endl<<*(t.end());
int j;
cin>>j;
}
26