C++ help Use the scientific method to perform an experiment to see whether a dat
ID: 3689349 • Letter: C
Question
C++ help
Use the scientific method to perform an experiment to see whether a data structure’s operation is consistent with its theoretical big-O running time.
The assignment is to perform this kind of analysis on the following nine data structure operations:
Add to front - singly linked list
Add to front - doubly linked list
Add to front - vector
Add to back - singly linked list
Add to back - doubly linked list
Add to back - vector
Clear - singly linked list
Clear - doubly linked list
Clear - vector
This skeleton code must be improved to do those 9 operations above. Here is the skeleton code.
#include "stdafx.h"
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <forward_list>
#include <list>
#include <vector>
using namespace std;
// Use a constant random number seed so behavior is consistent from run to run.
const int RANDOM_SEED = 0xC0DE;
// int value that is different from all randomly-generated ints.
const int DISTINCT_INT = -1; // Random ints are always non-negative.
// std::forward_list does not have a push back function, so we have to write
// our own.
void forward_list_push_back(forward_list<int>& the_list, int n, int element) {
forward_list<int>::iterator ptr = the_list.begin();
for (int i = 0; i < (n - 1); ++i)
++ptr;
the_list.insert_after(ptr, element);
}
int main()
{
// Seed the random number generator.
srand(RANDOM_SEED);
// Query user for structure size n.
int millions;
for (bool done = false; !done;) {
cout << "Enter a positive integer n, in units of millions: ";
cin >> millions;
if (cin && (millions > 0)) {
done = true;
}
else {
cout << "Invalid entry, try again." << endl;
}
}
const int n = millions * 1000000;
// Build a master forward_list, list, and vector, each containing the
// same collection of elements, that will be reused for each trial.
// These data structures are declared const to make sure we don't modify
// them by mistake.
cout << "Creating data structures with n=" << millions << " million...";
vector<int> randoms;
for (int i = 0; i < n; ++i) {
randoms.push_back(rand());
}
const forward_list<int> master_forward_list(randoms.begin(), randoms.end());
const list<int> master_list(randoms.begin(), randoms.end());
const vector<int> master_vector(randoms.begin(), randoms.end());
randoms.clear();
cout << "done" << endl;
// Each of the following trials is in its own anonymous scope, between the
// { } braces. This makes it so that each trial's local temp variable does
// not interfere with any of the other trials' code.
{
cout << "Add to back - singly linked list" << endl;
forward_list<int> temp = master_forward_list;
forward_list_push_back(temp, n, DISTINCT_INT);
}
{
cout << "Add to back - doubly linked list" << endl;
list<int> temp = master_list;
temp.push_back(DISTINCT_INT);
}
return 0;
}
Explanation / Answer
Sample code logic for single linked list
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int info;
struct node *next;
}*start;
class single_llist
{
public:
node* create_node(int);
void insert_begin();
void insert_last();
single_llist()
{
start = NULL;
}
};
/*Creating Node */
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}
/* Inserting element in beginning*/
void single_llist::insert_begin()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
cout<<"Element Inserted at beginning"<<endl;
}
/*Inserting Node at last*/
void single_llist::insert_last()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}
/*clear all- single linked list*/
void deleteList(list *head)
{
list *current = head;
list *temp;
while(nodes != NULL)
{
temp = current;
current = current->next;
free(temp);
}
}
Sample code logic for double linked list
#include<iostream>
using namespace std;
class doubleLinkedList
{
private:
class node
{
public:
int data;
node* next;
node* prev;
node(int x)
{
data = x;
next = NULL;
prev = NULL;
}
};
public:
node* head;
node* tail;
int count;
doubleLinkedList(); //default constructor
~doubleLinkedList();
void addFront(int); //add item to front of linked list
void addBack(int); //add item to back of linked list
};
//constructor
doubleLinkedList::doubleLinkedList(){
head = tail = NULL;
count = 0;
}
//destructor
doubleLinkedList::~doubleLinkedList(){
node* current = head;
while(current != NULL)
{
node* previous = current;
current = current->next;
delete previous;
}
head = tail = NULL;
count = 0;
}
//add item to front of linked list
void doubleLinkedList::addFront(int x){
node* n = new node(x);
n->next = head;
n->prev = NULL;
if (head != NULL)
head->prev = n;
head = n;
count++;
if (tail == NULL)
tail = n;
}
//add item to back of linked list
void doubleLinkedList::addBack(int x){
node* n = new node(x);
if (head == nullptr)
head = n; //this was your main problem!
if (tail != nullptr)
tail->next = n;
n->next = nullptr;
n->prev = tail;
tail = n;
count++;
}
Sample code logic for vector
#include <iostream>
#include <list>
int main ()
{
std::list<int> mylist (2,100); // two ints with a value of 100
mylist.push_front (200);
mylist.push_front (300);
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << ' ';
int myint;
std::cout << "Please enter some integers (enter 0 to end): ";
do {
std::cin >> myint;
mylist.push_back (myint);
} while (myint);
std::cout << "mylist stores " << int(mylist.size()) << " numbers. ";
mylist.clear();
return 0;
}
note-by using the above code samples with modifications the given question can be answered.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.