• API
• FAQ
• Tools
• Archive
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:
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;
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.     {
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;
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.     {
101.         if (current == NULL)return;
102.         while (current != NULL)
103.         {
104.             cout << endl << "Key value:" << current->key<<' '<<current<<endl;
105.             current = current->forward;
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.         {
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;
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.     {
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;
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.         {
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;
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;
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;
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;
225.         }
226.     }
227.
228.     //deletes an element from a list
229.     void deleteElement(int key)
230.     {
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;
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.     {
270.         for (int i = MAX_LEVEL - 1; i >= 0; i--)
272.         while (current->forward != NULL)
273.         {
274.             Node* previous;
275.             previous = current;
276.             current = current->forward;
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.

Top