SHARE
TWEET

Algo3

Quebonamade Oct 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALGO2 IS1 213B LAB03
  2. //MACIEJ DOMINIAK
  3. //dm44308@zut.edu.pl
  4. #include <iostream>
  5. #include <ctime>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. using namespace std;
  9. class Node
  10. {
  11.     public:
  12.     int key,height;
  13.     double d_variable;
  14.     char ch_variable;
  15.     Node** forward;
  16.     //node constructor
  17.     Node(int key, int level)
  18.     {
  19.         this->key = key;
  20.         this->height = level;
  21.         this->d_variable = rand();
  22.         this->ch_variable = 'T';
  23.         forward = new Node * [level];
  24.         for (int i = 0; i < level; i++)
  25.         {
  26.             forward[i] = NULL;
  27.         }
  28.     }
  29. };
  30. class Skiplist
  31. {
  32.     public:
  33.     Node* HEADER;
  34.     int MAX_LEVEL;
  35.     float PROB;
  36.     int size;
  37.  
  38.     //constructor   DONE
  39.     Skiplist(int MAX_LEVEL,float PROB)
  40.     {
  41.         this->MAX_LEVEL = MAX_LEVEL;
  42.         this->PROB = PROB;
  43.         size = 0;
  44.         HEADER = new Node(-1,MAX_LEVEL);
  45.     }
  46.  
  47.     //generates random level including probability MAYBE??
  48.     int randomLevel()
  49.     {
  50.         int level = 1;
  51.         int r = rand() % 100;
  52.         while ((r < PROB * 100) && (level < MAX_LEVEL))
  53.         {
  54.             level++;
  55.             r = rand() % 100;
  56.         }
  57.         return level;
  58.     }
  59.  
  60.     //inserts one element to the list MAYBE??
  61.     void insertElement(int key)
  62.     {
  63.         Node* current = HEADER;
  64.         Node** update = new Node * [MAX_LEVEL];
  65.         for (int i = 0; i < MAX_LEVEL; i++)
  66.         {
  67.             update[i] = NULL;
  68.         }
  69.         for (int i = MAX_LEVEL - 1; i >= 0; i--)
  70.         {
  71.             while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
  72.             {
  73.                 current = current->forward[i];
  74.             }
  75.             update[i] = current;
  76.  
  77.         }
  78.         current = current->forward[0];
  79.         if (current == NULL || current->key != key)
  80.         {
  81.             int r_level = randomLevel();
  82.             Node* new_node = new Node(key, r_level);
  83.             for (int i = 0; i < new_node->height; i++)
  84.             {
  85.                 new_node->forward[i] = update[i]->forward[i];
  86.                 update[i]->forward[i] = new_node;
  87.             }
  88.             size++;
  89.             return;
  90.         }
  91.         if (current->key = key)
  92.         {
  93.             current->ch_variable = 'D';
  94.         }
  95.     }
  96.  
  97.     //shows all elements  THATS JUST FOR ME
  98.     void showAll()
  99.     {
  100.         Node* current = HEADER->forward[0];
  101.         if (current == NULL)return;
  102.         while (current != NULL)
  103.         {
  104.             cout << endl << "Key value:" << current->key<<' '<<current<<endl;
  105.             current = current->forward[0];
  106.         }
  107.     }
  108.  
  109.     //inserts many elements to the list  DONE
  110.     void insertManyElements(int amount)
  111.     {
  112.         int j = 0;
  113.         while (j < amount)
  114.         {
  115.             Node* current = HEADER;
  116.             int key = (4 * rand()) % 999901 + 99;
  117.             Node** update = new Node * [MAX_LEVEL];
  118.             for (int i = 0; i < MAX_LEVEL; i++)
  119.             {
  120.                 update[i] = NULL;
  121.             }
  122.             for (int i = MAX_LEVEL - 1; i >= 0; i--)
  123.             {
  124.                 while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
  125.                 {
  126.                     current = current->forward[i];
  127.                 }
  128.                 update[i] = current;
  129.  
  130.             }
  131.             current = current->forward[0];
  132.             if (current == NULL || current->key != key)
  133.             {
  134.                 int r_level = randomLevel();
  135.                 Node* new_node = new Node(key, r_level);
  136.                 for (int i = 0; i < new_node->height; i++)
  137.                 {
  138.                     new_node->forward[i] = update[i]->forward[i];
  139.                     update[i]->forward[i] = new_node;
  140.                 }
  141.                 size++;
  142.                 j++;
  143.                 continue;
  144.             }
  145.             if (current->key = key)
  146.             {
  147.                 current->ch_variable = 'D';
  148.             }
  149.         }
  150.     }
  151.  
  152.     //finds element in a list  DONE
  153.     Node* findElement(int key)
  154.     {
  155.         Node* current = HEADER;
  156.         for (int i = MAX_LEVEL-1; i >= 0; i--)
  157.         {
  158.             while (current->forward[i] && current->forward[i]->key < key)
  159.                 current = current->forward[i];
  160.         }
  161.         current = current->forward[0];
  162.         if (current==NULL)
  163.             return NULL;
  164.         if(current->key==key)
  165.         {
  166.             return current;
  167.         }
  168.         else
  169.         {
  170.             return NULL;
  171.         }
  172.     }
  173.  
  174.     //returns an array of how many nodes there are in particular levels DONE
  175.     void howManyNodes()
  176.     {
  177.         int *tab=new int[MAX_LEVEL];
  178.         int sum=0;
  179.         for (int i = 0; i < MAX_LEVEL; i++)
  180.         {
  181.             tab[i] = 0;
  182.         }
  183.         for (int i = MAX_LEVEL - 1; i >= 0; i--)
  184.         {
  185.             Node* jump = HEADER->forward[i];
  186.             while (jump != NULL)
  187.             {
  188.                 tab[i]++;
  189.                 jump = jump->forward[i];
  190.             }
  191.             sum += tab[i];
  192.            
  193.         }
  194.         for (int i = 0; i < MAX_LEVEL; i++)
  195.         {
  196.             cout << endl << "Level " << i << " has:" << tab[i] << " nodes";
  197.         }
  198.         cout << endl << "Sum of all nodes equals:" << sum;
  199.     }
  200.  
  201.     //shows X first elements DONE
  202.     void showFirstElements(int amount)
  203.     {
  204.         if (amount > size)return;
  205.         Node* current = HEADER->forward[0];
  206.         cout <<endl<< "These are first " << amount << " elements:";
  207.         for (int i = 0; i < amount; i++)
  208.         {
  209.             cout << current->key << ' ';
  210.             current = current->forward[0];
  211.         }
  212.     }
  213.  
  214.     //shows Y last elements DONE
  215.     void showLastElements(int amount)
  216.     {
  217.         if (amount > size)return;
  218.         int skip = size - amount;
  219.         Node* current = HEADER->forward[0];
  220.         cout << endl << "These are last " << amount << " elements:";
  221.         for (int i = 0; i < size; i++)
  222.         {
  223.             if (i >= skip)cout << current->key<<' ';
  224.             current = current->forward[0];
  225.         }
  226.     }
  227.  
  228.     //deletes an element from a list
  229.     void deleteElement(int key)
  230.     {
  231.         Node* current = HEADER;
  232.         Node** update = new Node * [MAX_LEVEL];
  233.         for (int i = 0; i < MAX_LEVEL; i++)
  234.         {
  235.             update[i] = NULL;
  236.         }
  237.         for (int i = MAX_LEVEL - 1; i >= 0; i--)
  238.         {
  239.             while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
  240.             {
  241.                 current = current->forward[i];
  242.             }
  243.             update[i] = current;
  244.  
  245.         }
  246.         current = current->forward[0];
  247.         if (current == NULL)
  248.         {
  249.             return;
  250.         }
  251.         if (current->key == key)
  252.         {
  253.             for (int i = 0; i < current->height; i++)
  254.             {
  255.                 update[i]->forward[i] = current->forward[i];
  256.             }
  257.             delete current;
  258.             size--;
  259.         }
  260.         else
  261.         {
  262.             return;
  263.         }
  264.     }
  265.  
  266.     //deletes entire list
  267.     void deleteList()
  268.     {
  269.         Node* current = HEADER->forward[0];
  270.         for (int i = MAX_LEVEL - 1; i >= 0; i--)
  271.             HEADER->forward[i] = NULL;
  272.         while (current->forward[0] != NULL)
  273.         {
  274.             Node* previous;
  275.             previous = current;
  276.             current = current->forward[0];
  277.             delete previous;
  278.         }
  279.     }
  280.  
  281. };
  282. int main()
  283. {
  284.     srand(unsigned(time(NULL)));
  285.  
  286.     Skiplist my_list(5, 0.5);
  287.    
  288.  
  289.     return 0;
  290. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top