Курсовая работа - Сравнение эффективности различных подходов к хранению данных
Подождите немного. Документ загружается.
for(int i=0;i<data.size();i++)
{
sum+=data[i];
}
return (sum % size);
}
int compEQ(string a,string b) {
if (a.compare(b) ) return 1; else return 0;
}
template <class T>
int hash(T data,int hashTableSize) {
return ((int)data % hashTableSize);
}
template <class T>
int compEQ(T a,T b) {
if (a == b) return 1; else return 0;
}
typedef struct Node_ {
struct Node_ *next; /* next node */
int *data; /* data stored in node */
} Node;
template <class T>
class set_hash
{
private:
// Здесь данные, которые нужно скрыть, они для низкоуровнего
доступа
Node **hashTable;
int hashTableSize;
Node *first,*last;
int f_ind,l_ind;
int _size;
void find_begin(void)
{
if (_size == 0)
{
first = NULL;
f_ind = 0;
}
else
{
for (int i=0; i < hashTableSize; i++)
{
if (hashTable[i] != NULL)
{
first = (Node *)hashTable[i];
f_ind = i;
break;
}
}
}
}
void find_end(void)
{
Node *pointer;
if (_size == 0)
{
last = NULL;
l_ind = hashTableSize;
}
11
else
for (int i=hashTableSize; i > 0; i--)
{
if (hashTable[i] != NULL)
{
pointer = hashTable[i];
while (pointer->next != NULL)
{
pointer = pointer->next;
}
last = pointer;
l_ind = i;
break;
}
}
}
public:
set_hash (void);
~set_hash () {// Удаление объекта
};
int size() { // Возвращает размер
return _size;
};
int empty(){
if (_size == 0) return 1; else return 0;
};
void insert(T data) // Метод вставки
{
Node *p, *p0;
T *dat;
int bucket;
p = hashTable[hash(data,hashTableSize)];
while ((p!=NULL) && !compEQ(*(p->data), data))
p = p->next;
if (p == NULL) {
bucket = hash(data,hashTableSize);
p = (Node*) malloc(sizeof(Node));
if (p == 0) {
cout<<"out of memory (insertNode)\n";
exit(1);
}
p0 = hashTable[bucket];
hashTable[bucket] = p;
p->next = p0;
dat = (T*) malloc(sizeof(T));
*dat = data;
p->data = dat;
}
_size++;
};
void delete_item(T data) // Метод удаления элемента возвращает 1 -
//если объект был удален 0 - если объекта не было в set-е
{
Node *p0, *p;
int bucket;
/* find node */
p0 = NULL;
bucket = hash(data,hashTableSize);
p = hashTable[bucket];
while ((p != NULL) && !compEQ(*(p->data),
data)) {
12
p0 = p;
p = p->next;
}
if (!p) return;
/* p designates node to delete, remove it from
list */
if (p0 != NULL)
/* not first node, p0 points to previous node
*/
p0->next = p->next;
else
/* first node on chain */
hashTable[bucket] = p->next;
free(p);
_size--;
};
int find(T data) // Поиск
{
Node *p;
/*******************************
* find node containing data *
*******************************/
p = hashTable[hash(data,hashTableSize)];
while ((p!=NULL) && !compEQ(*(p->data), data))
p = p->next;
if (p == NULL) return 0; else return 1;
};
// Класс iterator
friend class iterator;
class iterator
{
private:
set_hash* s; // Ссылка на класс
int index; //Индекс
int TableIndex; // Индекс строки в таблице
Node *p; // Указатель на текущую лексему
public:
iterator() : index(0),TableIndex(0) {}
iterator(set_hash* st) {
s = st;
index = 0;
p = st->first;
TableIndex = st->f_ind;
}
iterator(set_hash* st, bool)
{
s = st;
index = st->_size-1;
p = st->last;
TableIndex = st->l_ind;
}
T& operator*() { return *(p->data); }
Node operator++() {
if (p != NULL)
if (p->next != NULL)
{
p = p->next;
}
else
13
do{
p = s->hashTable[++TableIndex];
}
while(!p);
index++;
} /*prefix form*/
bool operator==(const iterator& rv) const {
return index == rv.index;
}
iterator& operator=(const iterator& rv) {
s = rv.s;
index = rv.index;
p = rv.p;
TableIndex = rv.TableIndex;
return *this;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
};
iterator begin() {
find_begin();
return iterator(this);}
iterator end() {
find_end();
return iterator(this, true);
}
};
template <class T>
set_hash<T> :: set_hash ()
{
_size=0;
hashTableSize = HTBS;
hashTable = (Node **) malloc(hashTableSize * sizeof(Node *));
for(int i=0; i < hashTableSize; i++)
{
hashTable[i] = NULL;
}
}
int main(void)
{
set_hash<int> a;
for(int i=0;i<5;i++)
a.insert(i);
set_hash<int>::iterator iter;
for(iter = a.begin(); iter != a.end(); ++iter)
{
cout<<*iter<<endl;
}
cout<< a.find(2);
a.delete_item(2);
cout<< a.find(2);
}
14
2.2.Красно-черные деревья
#include<iostream>
#include<iterator>
#include<stdlib.h>
#define TS 100
#define NIL &sentinel
using namespace std;
typedef enum { BLACK, RED } nodeColor;
template <class T>
class set_RBT
{
private:
typedef struct Node_ {
struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
nodeColor color; /* node color BLACK, RED*/
T data; /* data stored in node */
} Node;
// Здесь данные, которые нужно скрыть, они для низкоуровнего
доступа
Node **ADRTable; // Table whith adreeses of data
int ADRTableSize;
Node sentinel;
Node *root; /* root of Red-Black tree */
Node **RBTree;
int TreeSize;
int _size;
void insertADR(Node *x)
{
Node **t;
t = (Node **)malloc((ADRTableSize+1) * sizeof(Node *));
for (int i = 0; i < ADRTableSize; i++)
{
t[i] = ADRTable[i];
}
t[ADRTableSize] = x;
ADRTable = t;
ADRTableSize++;
};
void deleteADR(Node *x)
{
Node **t;
int j=0;
t = (Node **)malloc((ADRTableSize-1) * sizeof(Node *));
for (int i = 0; i < ADRTableSize; i++)
{
if (ADRTable[i] != x) t[j++] = ADRTable[i];
}
ADRTable = t;
ADRTableSize--;
}
void rotateLeft(Node *x)
{
Node *y = x->right;
/* establish x->right link */
x->right = y->left;
15
if (y->left != NIL) y->left->parent = x;
/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent)
{
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
}
else { root = y; }
/* link x and y */
y->left = x;
if (x != NIL) x->parent = y;
};
void rotateRight(Node *x)
{
Node *y = x->left;
/* establish x->left link */
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent)
{
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
}
else { root = y; }
/* link x and y */
y->right = x;
if (x != NIL) x->parent = y;
};
void insertFixup(Node *x)
{
/* check Red-Black properties */
while (x != root && x->parent->color == RED)
{
/* we have a violation */
if (x->parent == x->parent->parent->left)
{
Node *y = x->parent->parent->right;
if (y->color == RED)
{
/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
/* uncle is BLACK */
if (x == x->parent->right)
{
/* make x a left child */
x = x->parent;
rotateLeft(x);
}
16
/* recolor and rotate */
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
}
else
{
/* mirror image of above code */
Node *y = x->parent->parent->left;
if (y->color == RED)
{
/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
/* uncle is BLACK */
if (x == x->parent->left)
{
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
};
void deleteFixup(Node *x)
{
while (x != root && x->color == BLACK)
{
if (x == x->parent->left)
{
Node *w = x->parent->right;
if (w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->right->color == BLACK)
{
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
17
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
}
else
{
Node *w = x->parent->left;
if (w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->left->color == BLACK)
{
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
};
Node *findNode(T data)
{
Node *current = root;
while(current != NIL)
if(data==current->data)
return (current);
else
if(data< current->data) current = current->left;
else current=current->right;
return(0);
};
void delete_lr(Node *x)
{
if (x->left != NIL) delete_lr(x->left);
if (x->right != NIL) delete_lr(x->right);
free(x);
}
public:
set_RBT (void)
{
_size=0;
18
sentinel.left = NULL;
sentinel.right = NULL;
sentinel.parent = NULL;
sentinel.color = BLACK;
sentinel.data = 0.0f;
root = NIL; /* root of Red-Black tree */
//cout << "!!!! "<<root->data<<endl;
TreeSize = TS;
//RBTree = (Node **) malloc(TreeSize * sizeof(Node *));
ADRTableSize = 0;
};
~set_RBT () {// Удаление объекта
if (root != NIL) delete_lr(root);
};
int size() { /*Возвращает размер*/ return _size; };
int empty(){ if (_size == 0) return 1; else return 0; };
void insert(T data) // Метод вставки
{
Node *current, *parent, *x;
bool nodEexist =0;
/* find where node belongs */
current = root;
parent = 0;
while (current != NIL)
{
if (data==current->data)
{
nodEexist =1;
cout<<"Exist ";
break;
}
parent = current;
if(data< current->data) current = current->left;
else current=current->right;
}
if(nodEexist ==0)
{
/* setup new node */
x = (Node*)malloc (sizeof(*x));
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;
/*save Addres in Table*/
_size++;
insertADR(x);
/* insert node in tree */
if(parent) {
if(data< parent->data)
parent->left = x;
else
parent->right = x;}
else { root = x; }
insertFixup(x);
}
};
19
int find(T data) // Поиск
{
Node *current= root;
while(current != NIL)
{
if(data==current->data)
{
return (1);
}
else
if(data< current->data)
{
current = current->left;
}
else
{current=current->right; }
return(0);
}
};
void delete_item(T data) // Метод удаления элемента возвращает 1 -
если объект
// был удален 0 - если объекта не было в set-
е
{
Node *z= findNode(data);
Node *x, *y;
if (!z || z == NIL) return;
if (z->left == NIL || z->right == NIL)
{
/* y has a NIL node as a child */
y = z;
}
else
{
/* find tree successor with a NIL node as a child */
y = z->right;
while (y->left != NIL) y = y->left;
}
/* x is y's only child */
if (y->left != NIL)
x = y->left;
else
x = y->right;
/* remove y from the parent chain */
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;
if (y != z) z->data = y->data;
if (y->color == BLACK)
deleteFixup (x);
_size--;
deleteADR(y);
free (y);
};
// Класс iterator
20