Question

In: Computer Science

Write a program in C++ that efficiently implements a skip list that holds integers. Your program...

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!

Solutions

Expert Solution

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();

}


Related Solutions

Please write code in C, thank you. Write a program that reads a list of integers,...
Please write code in C, thank you. Write a program that reads a list of integers, and outputs whether the list contains all even numbers, odd numbers, or neither. The input begins with an integer indicating the number of integers that follow. Assume that the list will always contain less than 20 integers. Ex: If the input is: 5 2 4 6 8 10 the output is: all even Ex: If the input is: 5 1 3 5 7 9...
Write a program that implements a stack of integers, and exercises the stack based on commands...
Write a program that implements a stack of integers, and exercises the stack based on commands read from cin. To do this, write a class called Stack with exactly the following members: class Stack { public: bool isEmpty(); // returns true if stack has no elements stored int top(); // returns element from top of the stack // throws runtime_error("stack is empty") int pop(); // returns element from top of the stack and removes it // throws runtime_error("stack is empty")...
Implementing a Stack Write a program that implements a stack of integers, and exercises the stack...
Implementing a Stack Write a program that implements a stack of integers, and exercises the stack based on commands read from cin. To do this, write a class called Stack with exactly the following members: class Stack { public: bool isEmpty(); // returns true if stack has no elements stored int top(); // returns element from top of the stack // throws runtime_error("stack is empty") int pop(); // returns element from top of the stack and removes it // throws...
Write a C++ program to read in a list of 10 integers from the keyboard. Place...
Write a C++ program to read in a list of 10 integers from the keyboard. Place the even numbers into an array called even, the odd numbers into an array called odd, and the negative numbers into an array called negative. Keep track of the number of values read into each array. Print all three arrays after all the numbers have been read. Print only the valid elements (elements that have been assigned a value). a. Use main( ) as...
(C++) Write a program that reads a list of integers from the keyboard and print out...
(C++) Write a program that reads a list of integers from the keyboard and print out the smallest number entered. For example, if user enters 0 3 -2 5 8 1, it should print out -2. The reading stops when 999 is entered.
***C++ Coding*** Write a program for sorting a list of integers in ascending order using the...
***C++ Coding*** Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Please include comments to understand code. Requirements Implement the following functions: int readData( int **arr) arr is a pointer to pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr. The first integer number in the file is the number of intergers....
C++ Write a program for sorting a list of integers in ascending order using the bubble...
C++ Write a program for sorting a list of integers in ascending order using the bubble sort algorithm Requirements Implement the following functions: Implement a function called readData int readData( int **arr) arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr. The first integer number in the file is the number of intergers. After the first number,...
a)     Write a program that reads a list of integers, and outputs all even integers in the...
a)     Write a program that reads a list of integers, and outputs all even integers in the list. For example, if the input list is [1, 2, 13, 14, 25], the output list should be [2, 14]. b)    Based on your code for part (a), write a program that reads a list of integers, and reports True if all numbers in the list are even, and False otherwise. Example: For input [1, 2, 13, 14, 25], the output should be False. Your...
C++ code please: Write a program that first gets a list of integers from input. The...
C++ code please: Write a program that first gets a list of integers from input. The input begins with an integer indicating the number of integers that follow. Then, get the last value from the input, which indicates how much to multiply the array by. Finally, print out the entire array with each element multiplied by the last input. Assume that the list will always contain less than 20 integers. Ex: If the input is 4 4 8 -4 12...
write a C/C++ program that implements the banker's algorithm. Verify your implementation using the data from...
write a C/C++ program that implements the banker's algorithm. Verify your implementation using the data from the textbook as well as the attached, but unverified (meaning that it is possible the system is already in an unsafe state), file. The file format is as follows: Line 1 contains a number of resources (m). Line 2 contains the quantity for each resource (I.e., the resource vector. Line 3 contains the number of processes (n). Lines 4 through 3+n contain the Claim...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT