In: Computer Science
Write a program in C++ that efficiently implements a skip list that holds integers. Your program should: 1. Accurately implement the skip list ADT using a random number generator and nodes that contain an integer as well as the addresses of adjacent nodes to the left, right, up, and down. 2. Correctly implement the Insert, Search, and Delete operations. 3. Read a series of unique, newline-delineated integers from a file and insert them (one at a time in the order provided) into your skip list. If the number of nodes is not greater than 24 , print out the number of comparisons for each insertion, as well as the level at which each number is inserted (this should vary with each execution of your program!) 4. Repeat this process for each input file in sorted, “perfect”, and random order (these are the same input files you used for Assignment 4). 5. If the number of nodes is not greater than 24 , print a representation of your skip list to the console. Note: a simple series of space-separated numbers for each level is sufficient here. Overloading operator and using numeric_limits::max() and numeric_limits::min(). – The ctime library (#include ) is helpful for random number generation. Use srand(time(0)) to seed your number generator, and the rand() function to get your “coin flips.” Or you can use the C++ class random (#include ). – You may want your search function to return a pointer/iterator to the item it finds (this can simplify your delete function); you may also have to pass your insert function an integer by reference so that you can keep track of the comparison count. – In order to remove items from your skip list, simply call the delete function using the numbers in the file (you can also store the numbers in a vector or somewhere when you read them in so that you don’t have to read them in twice). DO NOT implement a function that deletes arbitrary elements from the skip list!
PLZ don't forget to give a thumbs up!
#include <bits/stdc++.h>
using namespace std;
// Class to implement node
class Node
{
public:
int key;
// Array to hold pointers to node of different level
Node **forward;
Node(int, int);
};
Node::Node(int key, int level)
{
this->key = key;
// Allocate memory to forward
forward = new Node*[level+1];
// Fill forward array with 0(NULL)
memset(forward, 0, sizeof(Node*)*(level+1));
};
// Class for Skip list
class SkipList
{
// Maximum level for this skip list
int MAXLVL;
// P is the fraction of the nodes with level
// i pointers also having level i+1 pointers
float P;
// current level of skip list
int level;
// pointer to header node
Node *header;
public:
SkipList(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);
void displayList();
};
SkipList::SkipList(int MAXLVL, float P)
{
this->MAXLVL = MAXLVL;
this->P = P;
level = 0;
// create header node and initialize key to -1
header = new Node(-1, MAXLVL);
};
// create random level for node
int SkipList::randomLevel()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while (r < P && lvl < MAXLVL)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
};
// create new node
Node* SkipList::createNode(int key, int level)
{
Node *n = new Node(key, level);
return n;
};
// Insert given key in skip list
void SkipList::insertElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for (int i = level; i >= 0; i--)
{
while (current->forward[i] != NULL &&
current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is desired position to
insert key.
*/
current = current->forward[0];
/* if current is NULL that means we have reached
to end of the level or current's key is not equal
to key to insert that means we have to insert
node between update[0] and current node */
if (current == NULL || current->key != key)
{
// Generate a random level for node
int rlevel = randomLevel();
// If random level is greater than list's current
// level (node with highest level inserted in
// list so far), initialize update value with pointer
// to header for further use
if (rlevel > level)
{
for (int i=level+1;i<rlevel+1;i++)
update[i] = header;
// Update the list current level
level = rlevel;
}
// create new node with random level generated
Node* n = createNode(key, rlevel);
// insert node by rearranging pointers
for (int i=0;i<=rlevel;i++)
{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
cout << "Successfully Inserted key " << key << "\n";
}
};
// Display skip list level wise
void SkipList::displayList()
{
cout<<"\n*****Skip List*****"<<"\n";
for (int i=0;i<=level;i++)
{
Node *node = header->forward[i];
cout << "Level " << i << ": ";
while (node != NULL)
{
cout << node->key<<" ";
node = node->forward[i];
}
cout << "\n";
}
};
// Driver to test above code
int main()
{
// Seed random number generator
srand((unsigned)time(0));
// create SkipList object with MAXLVL and P
SkipList lst(3, 0.5);
lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.insertElement(12);
lst.insertElement(19);
lst.insertElement(17);
lst.insertElement(26);
lst.insertElement(21);
lst.insertElement(25);
lst.displayList();
}