Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //ALGO2 IS1 213B LAB03
- //MACIEJ DOMINIAK
- //dm44308@zut.edu.pl
- #include <iostream>
- #include <ctime>
- #include <stdio.h>
- #include <stdlib.h>
- using namespace std;
- class Node
- {
- public:
- int key,height;
- double d_variable;
- char ch_variable;
- Node** forward;
- //node constructor
- Node(int key, int level)
- {
- this->key = key;
- this->height = level;
- this->d_variable = rand();
- this->ch_variable = 'T';
- forward = new Node * [level];
- for (int i = 0; i < level; i++)
- {
- forward[i] = NULL;
- }
- }
- };
- class Skiplist
- {
- public:
- Node* HEADER;
- int MAX_LEVEL;
- float PROB;
- int size;
- //constructor DONE
- Skiplist(int MAX_LEVEL,float PROB)
- {
- this->MAX_LEVEL = MAX_LEVEL;
- this->PROB = PROB;
- size = 0;
- HEADER = new Node(-1,MAX_LEVEL);
- }
- //generates random level including probability MAYBE??
- int randomLevel()
- {
- int level = 1;
- int r = rand() % 100;
- while ((r < PROB * 100) && (level < MAX_LEVEL))
- {
- level++;
- r = rand() % 100;
- }
- return level;
- }
- //inserts one element to the list MAYBE??
- void insertElement(int key)
- {
- Node* current = HEADER;
- Node** update = new Node * [MAX_LEVEL];
- for (int i = 0; i < MAX_LEVEL; i++)
- {
- update[i] = NULL;
- }
- for (int i = MAX_LEVEL - 1; i >= 0; i--)
- {
- while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
- {
- current = current->forward[i];
- }
- update[i] = current;
- }
- current = current->forward[0];
- if (current == NULL || current->key != key)
- {
- int r_level = randomLevel();
- Node* new_node = new Node(key, r_level);
- for (int i = 0; i < new_node->height; i++)
- {
- new_node->forward[i] = update[i]->forward[i];
- update[i]->forward[i] = new_node;
- }
- size++;
- return;
- }
- if (current->key = key)
- {
- current->ch_variable = 'D';
- }
- }
- //shows all elements THATS JUST FOR ME
- void showAll()
- {
- Node* current = HEADER->forward[0];
- if (current == NULL)return;
- while (current != NULL)
- {
- cout << endl << "Key value:" << current->key<<' '<<current<<endl;
- current = current->forward[0];
- }
- }
- //inserts many elements to the list DONE
- void insertManyElements(int amount)
- {
- int j = 0;
- while (j < amount)
- {
- Node* current = HEADER;
- int key = (4 * rand()) % 999901 + 99;
- Node** update = new Node * [MAX_LEVEL];
- for (int i = 0; i < MAX_LEVEL; i++)
- {
- update[i] = NULL;
- }
- for (int i = MAX_LEVEL - 1; i >= 0; i--)
- {
- while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
- {
- current = current->forward[i];
- }
- update[i] = current;
- }
- current = current->forward[0];
- if (current == NULL || current->key != key)
- {
- int r_level = randomLevel();
- Node* new_node = new Node(key, r_level);
- for (int i = 0; i < new_node->height; i++)
- {
- new_node->forward[i] = update[i]->forward[i];
- update[i]->forward[i] = new_node;
- }
- size++;
- j++;
- continue;
- }
- if (current->key = key)
- {
- current->ch_variable = 'D';
- }
- }
- }
- //finds element in a list DONE
- Node* findElement(int key)
- {
- Node* current = HEADER;
- for (int i = MAX_LEVEL-1; i >= 0; i--)
- {
- while (current->forward[i] && current->forward[i]->key < key)
- current = current->forward[i];
- }
- current = current->forward[0];
- if (current==NULL)
- return NULL;
- if(current->key==key)
- {
- return current;
- }
- else
- {
- return NULL;
- }
- }
- //returns an array of how many nodes there are in particular levels DONE
- void howManyNodes()
- {
- int *tab=new int[MAX_LEVEL];
- int sum=0;
- for (int i = 0; i < MAX_LEVEL; i++)
- {
- tab[i] = 0;
- }
- for (int i = MAX_LEVEL - 1; i >= 0; i--)
- {
- Node* jump = HEADER->forward[i];
- while (jump != NULL)
- {
- tab[i]++;
- jump = jump->forward[i];
- }
- sum += tab[i];
- }
- for (int i = 0; i < MAX_LEVEL; i++)
- {
- cout << endl << "Level " << i << " has:" << tab[i] << " nodes";
- }
- cout << endl << "Sum of all nodes equals:" << sum;
- }
- //shows X first elements DONE
- void showFirstElements(int amount)
- {
- if (amount > size)return;
- Node* current = HEADER->forward[0];
- cout <<endl<< "These are first " << amount << " elements:";
- for (int i = 0; i < amount; i++)
- {
- cout << current->key << ' ';
- current = current->forward[0];
- }
- }
- //shows Y last elements DONE
- void showLastElements(int amount)
- {
- if (amount > size)return;
- int skip = size - amount;
- Node* current = HEADER->forward[0];
- cout << endl << "These are last " << amount << " elements:";
- for (int i = 0; i < size; i++)
- {
- if (i >= skip)cout << current->key<<' ';
- current = current->forward[0];
- }
- }
- //deletes an element from a list
- void deleteElement(int key)
- {
- Node* current = HEADER;
- Node** update = new Node * [MAX_LEVEL];
- for (int i = 0; i < MAX_LEVEL; i++)
- {
- update[i] = NULL;
- }
- for (int i = MAX_LEVEL - 1; i >= 0; i--)
- {
- while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
- {
- current = current->forward[i];
- }
- update[i] = current;
- }
- current = current->forward[0];
- if (current == NULL)
- {
- return;
- }
- if (current->key == key)
- {
- for (int i = 0; i < current->height; i++)
- {
- update[i]->forward[i] = current->forward[i];
- }
- delete current;
- size--;
- }
- else
- {
- return;
- }
- }
- //deletes entire list
- void deleteList()
- {
- Node* current = HEADER->forward[0];
- for (int i = MAX_LEVEL - 1; i >= 0; i--)
- HEADER->forward[i] = NULL;
- while (current->forward[0] != NULL)
- {
- Node* previous;
- previous = current;
- current = current->forward[0];
- delete previous;
- }
- }
- };
- int main()
- {
- srand(unsigned(time(NULL)));
- Skiplist my_list(5, 0.5);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement