Question

In: Computer Science

In your app.cpp file, create a demo illustrating a scenario where storing numbers in a linked...

In your app.cpp file, create a demo illustrating a scenario where storing numbers in a linked list is more efficient than an array. Your demo should generate a sufficiently large number of random integers and insert them into both the list, and the array. Your demo should also provide the time it took to complete the operations in the array, and in the linked list. It should show that the linked list was faster.

app.cpp

#include <iostream>

#include <Array.h>

#include <LinkedList.h>

using namespace std;

int main(){

// Your code here...

return 0;

}

Support code-

Array.h

#ifndef Array_h

#define Array_h

#include <iostream>

#include <ostream>

struct ResizableArray {

// This is the poiner to the start of our array

long* data;

// Keep track of how much memory we have allocated

long size;

// Keep track of how much memory we have used

long counter;

// A default constructor

ResizableArray(){

// Start off by allocating memory for 1 int

data = new long[1];

// This means we have allocated for 1

size = 1;

// And we are currently using 0

counter = 0;

}

    // This is a copy constructor. It specifies what happens when

    // the array needs to be copied. In this case it performs

    // a deep copy, which is what we need

    ResizableArray(const ResizableArray& other){

        size = other.size;

        counter = other.counter;

        data = new long[other.size];

        for (long i = 0; i < other.size; i++){

            data[i] = other.data[i];

        }

    }

    // Overloading the == operator. Now we can compare

    // two ResizableArrays with the == operator

    bool operator==(const ResizableArray rhs) const {

        // If the sizes or counters are different, it's not a match

        if (size != rhs.size){

            return false;

        }

        if (counter != rhs.counter){

            return false;

        }

        // Assume the arrays match

        bool same = true;

        // And try to find a contradiction

        for (long i = 0; i < counter; i++){

            if (data[i] != rhs.data[i]){

                return false;

            }

        }

        

        // Colud not get a contradiction

        return true;

    }

// Print the contents we have

void print(){

for (long i = 0; i < counter; i++){

std::cout << data[i] << std::endl;

}

}

    // Get the value at a specified position

int get(long index){

return data[index];

}

    // Set the value at a specified position with a given integer

void set(long index, long value){

data[index] = value;

}

    void insert(long index, long value){

if (index < size){

for(long i = counter; i > index; i--){

data[i] = data[i-1];

}

data[index] = value;

counter++;

if (counter == size){

long oldSize = size;

size = size * 2;

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

}

else{

int oldSize = size;

while (index+1 >= size){

size *=2;

}

if (size > oldSize){

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

for (long i = counter; i < index; i++){

data[i] = 0;

}

data[index] = value;

counter = index + 1;

}

}

// Store a new value in the array

void append(long value){

// The very first time this is called

// we know we have enough storage allocated

// because we allocated space for 1 int

// so we store it

data[counter] = value;

// and increase the counter

counter++;

// If we are out of space, i.e. we have

// stored as much as we have allocated

// then we need to increase our storage space

if (counter == size){

// Just for convenience, store the old size

long oldSize = size;

// Let's double the amount of storage we have

size = size * 2;

// Allocate another chunk of memory

// twice as big as the first

long* newArr = new long[size];

// Copy all elements from the old location

// to the new location

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

// Release the old location

delete[] data;

// Make our data pointer point to the new location

data = newArr;

}

}

    

    // This is called a destructor. It simply releases the

    // memory we have been using.

    ~ResizableArray(){

        delete[] data;

    }

};

// This is an overload of the << operator, which allows us

// to print out the ResizableArray with cout <<

std::ostream& operator<<(std::ostream& os, const ResizableArray& arr) {

for (long i = 0; i < arr.counter; i++){

        os << arr.data[i] << " ";

    }

return os;

}

#endif

LinkedList.h

#ifndef LinkedList_h

#define LinkedList_h

#include <iostream>

#include <ostream>

struct Node{

    long data;

    Node* next;

    Node (){

        data = 0;

        next = NULL;

    }

    Node (long n){

        data = n;

        next = NULL;

    }

};

struct LinkedList{

    Node* head;

    Node* last;

    LinkedList(){

        head = NULL;

        last = NULL;

    }

    LinkedList(const LinkedList& other){

        head = NULL;

        if (other.head != NULL){

            Node* temp = other.head;

            while (temp != NULL){

                append(temp->data);

                temp = temp->next;

            }

        }

        last = other.last;

    }

    void append (long n){

        if (head == NULL){

            head = new Node(n);

            last = head;

        }

        else{

            Node* theNode = new Node(n);

            last->next = theNode;

            last = last->next;

        }

    }

    void prepend(long n){

        Node* temp = new Node(n);

        temp->next = head;

        head = temp;

    }

    bool operator==(const LinkedList& other) const {

        Node* ours = head;

        Node* theirs = other.head;

        while (ours != NULL){

            if (theirs == NULL){

                return false;

            }

            if (ours->data != theirs->data){

                return false;

            }

            else{

                ours = ours->next;

                theirs = theirs->next;

            }

        }

        return theirs == NULL;

    }

    ~LinkedList(){

        Node* temp = head;

        while (temp != NULL){

            head = head->next;

            delete temp;

            temp = head;

        }

    }

};

std::ostream& operator<< (std::ostream& os, const LinkedList& theList){

    Node* temp = theList.head;

    while (temp != NULL){

        os << temp->data << " ";

        temp = temp->next;

    }

    return os;

}

#endif

TimeSupport.h

//

// A small library for timing our programs

//

#ifndef TimeSupport_h

#define TimeSupport_h

#include <chrono>

typedef enum {

sec,

mill

} Unit;

typedef std::chrono::time_point<std::chrono::high_resolution_clock> timestamp;

long time_diff(timestamp start, timestamp end, Unit u = mill){

if (u == mill){

auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();

return (long) diff;

}

else{

auto diff = std::chrono::duration_cast<std::chrono::seconds>(end-start).count();

return (long) diff;

}

}


timestamp current_time(){

return std::chrono::high_resolution_clock::now();

}

#endif

RandomSupport.h

//

// A small library for sampling random numbers from a uniform distribution

//

#ifndef RandomSupport_h

#define RandomSupport_h

#include <random>

int call_counter = 0;

typedef std::uniform_int_distribution<long> uniform_distribution;

typedef std::mt19937 randomizer;

randomizer new_randomizer(){

randomizer rng;

rng.seed(std::random_device()());

return rng;

}

uniform_distribution new_distribution(long start, long end){

uniform_distribution dist(start, end);

return dist;

}

long sample(uniform_distribution& dist, randomizer& r){

call_counter++;

return dist(r);

}

#endif




Solutions

Expert Solution

app.cpp

#include <iostream>

#include <Array.h>

#include <LinkedList.h>

using namespace std;

int main(){

// Your code here...

return 0;

}

Support code-

Array.h

#ifndef Array_h

#define Array_h

#include <iostream>

#include <ostream>

struct ResizableArray {

// This is the poiner to the start of our array

long* data;

// Keep track of how much memory we have allocated

long size;

// Keep track of how much memory we have used

long counter;

// A default constructor

ResizableArray(){

// Start off by allocating memory for 1 int

data = new long[1];

// This means we have allocated for 1

size = 1;

// And we are currently using 0

counter = 0;

}

    // This is a copy constructor. It specifies what happens when

    // the array needs to be copied. In this case it performs

    // a deep copy, which is what we need

    ResizableArray(const ResizableArray& other){

        size = other.size;

        counter = other.counter;

        data = new long[other.size];

        for (long i = 0; i < other.size; i++){

            data[i] = other.data[i];

        }

    }

    // Overloading the == operator. Now we can compare

    // two ResizableArrays with the == operator

    bool operator==(const ResizableArray rhs) const {

        // If the sizes or counters are different, it's not a match

        if (size != rhs.size){

            return false;

        }

        if (counter != rhs.counter){

            return false;

        }

        // Assume the arrays match

        bool same = true;

        // And try to find a contradiction

        for (long i = 0; i < counter; i++){

            if (data[i] != rhs.data[i]){

                return false;

            }

        }

        

        // Colud not get a contradiction

        return true;

    }

// Print the contents we have

void print(){

for (long i = 0; i < counter; i++){

std::cout << data[i] << std::endl;

}

}

    // Get the value at a specified position

int get(long index){

return data[index];

}

    // Set the value at a specified position with a given integer

void set(long index, long value){

data[index] = value;

}

    void insert(long index, long value){

if (index < size){

for(long i = counter; i > index; i--){

data[i] = data[i-1];

}

data[index] = value;

counter++;

if (counter == size){

long oldSize = size;

size = size * 2;

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

}

else{

int oldSize = size;

while (index+1 >= size){

size *=2;

}

if (size > oldSize){

long* newArr = new long[size];

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

delete[] data;

data = newArr;

}

for (long i = counter; i < index; i++){

data[i] = 0;

}

data[index] = value;

counter = index + 1;

}

}

// Store a new value in the array

void append(long value){

// The very first time this is called

// we know we have enough storage allocated

// because we allocated space for 1 int

// so we store it

data[counter] = value;

// and increase the counter

counter++;

// If we are out of space, i.e. we have

// stored as much as we have allocated

// then we need to increase our storage space

if (counter == size){

// Just for convenience, store the old size

long oldSize = size;

// Let's double the amount of storage we have

size = size * 2;

// Allocate another chunk of memory

// twice as big as the first

long* newArr = new long[size];

// Copy all elements from the old location

// to the new location

for (long i = 0; i < oldSize; i++) {

newArr[i] = data[i];

}

// Release the old location

delete[] data;

// Make our data pointer point to the new location

data = newArr;

}

}

    

    // This is called a destructor. It simply releases the

    // memory we have been using.

    ~ResizableArray(){

        delete[] data;

    }

};

// This is an overload of the << operator, which allows us

// to print out the ResizableArray with cout <<

std::ostream& operator<<(std::ostream& os, const ResizableArray& arr) {

for (long i = 0; i < arr.counter; i++){

        os << arr.data[i] << " ";

    }

return os;

}

#endif

LinkedList.h

#ifndef LinkedList_h

#define LinkedList_h

#include <iostream>

#include <ostream>

struct Node{

    long data;

    Node* next;

    Node (){

        data = 0;

        next = NULL;

    }

    Node (long n){

        data = n;

        next = NULL;

    }

};

struct LinkedList{

    Node* head;

    Node* last;

    LinkedList(){

        head = NULL;

        last = NULL;

    }

    LinkedList(const LinkedList& other){

        head = NULL;

        if (other.head != NULL){

            Node* temp = other.head;

            while (temp != NULL){

                append(temp->data);

                temp = temp->next;

            }

        }

        last = other.last;

    }

    void append (long n){

        if (head == NULL){

            head = new Node(n);

            last = head;

        }

        else{

            Node* theNode = new Node(n);

            last->next = theNode;

            last = last->next;

        }

    }

    void prepend(long n){

        Node* temp = new Node(n);

        temp->next = head;

        head = temp;

    }

    bool operator==(const LinkedList& other) const {

        Node* ours = head;

        Node* theirs = other.head;

        while (ours != NULL){

            if (theirs == NULL){

                return false;

            }

            if (ours->data != theirs->data){

                return false;

            }

            else{

                ours = ours->next;

                theirs = theirs->next;

            }

        }

        return theirs == NULL;

    }

    ~LinkedList(){

        Node* temp = head;

        while (temp != NULL){

            head = head->next;

            delete temp;

            temp = head;

        }

    }

};

std::ostream& operator<< (std::ostream& os, const LinkedList& theList){

    Node* temp = theList.head;

    while (temp != NULL){

        os << temp->data << " ";

        temp = temp->next;

    }

    return os;

}

#endif

TimeSupport.h

//

// A small library for timing our programs

//

#ifndef TimeSupport_h

#define TimeSupport_h

#include <chrono>

typedef enum {

sec,

mill

} Unit;

typedef std::chrono::time_point<std::chrono::high_resolution_clock> timestamp;

long time_diff(timestamp start, timestamp end, Unit u = mill){

if (u == mill){

auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();

return (long) diff;

}

else{

auto diff = std::chrono::duration_cast<std::chrono::seconds>(end-start).count();

return (long) diff;

}

}

timestamp current_time(){

return std::chrono::high_resolution_clock::now();

}

#endif

RandomSupport.h

//

// A small library for sampling random numbers from a uniform distribution

//

#ifndef RandomSupport_h

#define RandomSupport_h

#include <random>

int call_counter = 0;

typedef std::uniform_int_distribution<long> uniform_distribution;

typedef std::mt19937 randomizer;

randomizer new_randomizer(){

randomizer rng;

rng.seed(std::random_device()());

return rng;

}

uniform_distribution new_distribution(long start, long end){

uniform_distribution dist(start, end);

return dist;

}

long sample(uniform_distribution& dist, randomizer& r){

call_counter++;

return dist(r);

}

#endif


The main code can show the some error

please check


Related Solutions

Create a supply and demand graph illustrating the scenario, the shock, and the predicted effects on...
Create a supply and demand graph illustrating the scenario, the shock, and the predicted effects on wages and employment: Scenario #1 Airbnb has housed over 150 million guests in over 65,000 cities since 2008. Do a bit of research on what Airbnb is and how cities and the hotel industry has been responding to it. Using standard supply and demand graphs from the course, model the labor market for hotel workers, pre-Airbnb, and show how Airbnb has likely affected the...
Based on the following scenario and numbers, could you create a Cash Flow Statement? Scenario: Your...
Based on the following scenario and numbers, could you create a Cash Flow Statement? Scenario: Your team has been hired to provide financial analysis for a start-up company, Bobble in Style, which produces customized bobble heads. The bobble heads are made out of less rigid materials and are more true to life than those of competitors. The company inventors, Mr. and Mrs. Lee, are going to pitch their idea to Shark Tank in a few months, but first they need...
a/  write  4 numbers from your choice b/ Write a java code to create a linked list containing...
a/  write  4 numbers from your choice b/ Write a java code to create a linked list containing the 4 numbers
Create a subclass of BinaryTree whose nodes have fields for storing preorder, post-order, and in-order numbers....
Create a subclass of BinaryTree whose nodes have fields for storing preorder, post-order, and in-order numbers. Write methods preOrderNumber(), inOrderNumber(), and postOrderNumbers() that assign these numbers correctly. These methods should each run in O(n) time.
Create a linked list of Poem objects using the Poem.java file provided. You may create Poem...
Create a linked list of Poem objects using the Poem.java file provided. You may create Poem objects by hard coding (minimum 4), reading from a file, or getting user input. Print the list using ListIterator. Here is Poem.Java: public class Poem {    private String title;    private String poet;    /**    * No arg constructor    */    public Poem()    {        title = "not set";        poet = "not set";    }    /**...
Create a program that generates a file of random numbers, and then prints them in neat...
Create a program that generates a file of random numbers, and then prints them in neat fashion to another file, and also saves to that file the average and standard deviation of those numbers. I) First, you would need to generate a file of random numbers that consists of N random numbers (100 < N < 1000). Each random digit should be a real number (type double) between 0 and 50. This file and its digits would now serve as...
This is c++ Create a program where you create, display, search, delete elements within a linked...
This is c++ Create a program where you create, display, search, delete elements within a linked list. Watch your function arguments. Pointer parameters are passed by reference to some functions and by value to others. Functions to make: copy : copies element in linked list destroy all: destroys all elements in linked list wherethisgoes:user  enters element and returns where the element is located insert sorted: inserts element create using linked lists with a head pointer and so forth
Using C++, you will create a program, where you will create two doubly linked lists. These...
Using C++, you will create a program, where you will create two doubly linked lists. These doubly linked lists will contain integers within them. Using the numbers in both of these linked lists, you add the numbers together, and insert the addition of the two numbers into a singly linked list. the input can be from the user or you just write the input. for example, if one number in the doubly linked list is 817 and in the other...
Create a second page of your diagram (in the same file) and on it create a...
Create a second page of your diagram (in the same file) and on it create a Diagram 0 DFD of CSIES using the following information: The CSIES has within it the following processes and data store: PROCESS PAYMENT. This process interfaces with both the student and InsureRight Insurance Company. It receives the payment from the student and sends the payment to the InsureRight Insurance Company. It receives a receipt from the insurance company and sends a receipt to the student....
Outline and create a scenario of your own example where you could differentiate SIX (6) views...
Outline and create a scenario of your own example where you could differentiate SIX (6) views on the concept of sympathy to empathy. Decide which one is harder to comprehend and why?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT