C++ Data Structure Lab 3 Linked List Objectives: 1. Get yourself familiar with t
ID: 642590 • Letter: C
Question
C++ Data Structure
Lab 3 Linked List Objectives: 1. Get yourself familiar with the forward Linked List creation and operations. 2. Manipulate pointers 3. Create [inked node by is-a or has-a Overview 1. A stock in a portfolio contains a stock symbol (e.g. AAPL), a cost (i.e. purchase price), and the number of shares. 2. Write the stock class. 3. Write a program that creates a forward linked list of at least 20 elements. where each element holds a stock. The stock symbol is a string which you can generate randomly or just do Al. A2. etc. The cost and number of shares are randomly generated between 0 and 99. Print the list. 4. Write the function retumMiddleList to find the middle element of the linked list in one pass. Print the this element and the position of this element (starting at zero) in relation to the head (where the head = 0. the element pointed to by the head t 1. the element pointed to by the previous etc). S. Split the list in half at the middle element to create two entirely separate* linked lists of near equal size (+1- 1) and print the two lists. In other words. write the ?split in half? function. Discussions 1. Can you try both is-a and has-a implementation for node? What do you like or don?t like? 2. If you add a length field. finding middle is fairly easy to do. What if you do not have length? 3. Do you do add to list when you create a new stock? 4. What if the stock portfolio is on a disk file? Notes: How to convert int to string so that we can concatenate A1, A2? Try the simple test with string stream:Explanation / Answer
Program Code:
#ifndef StockHeader
#define StockHeader
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
//typedef string ElementType;
class Stock
{
private:
class Node
{
public:
string data;
double cost;
int num_stocks;
Node * next;
Node( ): data( ), next( NULL )
{ }
Node(string initData, double costStock, int number )
{
data = initData ;
cost = costStock;
num_stocks = number;
next = NULL ;
}
}; // end of Node class
typedef Node * NodePointer;
public:
Stock( );
/* Construct a List object
Precondition: none.
Postcondition: An empty List object has been constructed.
*/
Stock( const Stock &source );
/* Construct a copy of a List object.
Precondition: None.
Postcondition: A copy of source has been constructed.
*/
~Stock( );
/* Destroys a List object.
Precondition: None.
Postcondition: Any memory allocated to the List object has been freed.
*/
const Stock & operator=( const Stock &rightSide );
/* Assign a copy of a List object to the current object.
Precondition: none
Postcondition: A copy of rightside has been assigned to this
object. A constant reference to this list is returned.
*/
int getSize( ) const;
/* Returns the size of the list (number of items in the list)
Precondition: none
Postcondition: The return value is the number of items in the list.
*/
bool empty( ) const;
/* Check if this List is empty
Precondition: none
Postcondition: The return value is true if this List object is empty;
otherwise the return value is false.
*/
void insert(string initData, double costStock, int number, int index );
/* Insert a value into this List at a given index
Precondition: The index is valid (0 <= index <= the list size).
The first position is index 0, the second position is index 1, etc.
Postcondition: dataval has been inserted into the list at the position
determined by index (provided there is room and index is a legal
position).
*/
void erase( int index );
/* Remove the value from this List at a given index.
Precondition: The list is not empty and index is valid
(0 <= index < the list size).
Postcondition: the element at position index has been
removed (provided index is a legal position).
*/
void display( ostream &out ) const;
/* Display the contents of this List
Precondition: ostream out is open
Postcondition: the items in this List have been output to stream out
*/
void returnMiddleList();
/*Displays the Middle element data in the List
Precondition: Use getSize() method to get the size divide it into half and set as mid
Postcondition: use iterator to go the mid-1 position so that it prints the exact mid element
*/
void splitInHalf();
/* Displays the splitted lists
Precondition: Create two Stock objects into which the two list elements are stored
Postcondition: Use an iterator and store the first half elements of the list into List1 by checking the condition
whether the i < mid
If i>mid then store the other half into the second list List2.
Display the elements of the List1
Display the elements of the List2
*/
private:
NodePointer has_a;
int mySize;
}; // end of List class
#endif
//List.cpp
#include "stdafx.h"
#include "StockHeader.h"
//Construct empty List
Stock::Stock()
{
has_a = NULL;
mySize = 0;
}
//Construct copy of source List
Stock::Stock( const Stock &source )
{
has_a = NULL;
mySize = 0; //check the code, the value of mySize is
//changed
int index = 0;
NodePointer current = source.has_a;
while(current != NULL)
{
insert(current->data,current->cost, current->num_stocks, index++);
current = current->next;
}
}
Stock::~Stock( )
{
for(int i = 0; i <= mySize; i++)
erase(i);
}
const Stock & Stock::operator=( const Stock &rightSide )
{
int index = 0;
NodePointer current = rightSide.has_a;
while(current != NULL)
{
insert(current->data,current->cost, current->num_stocks, index++);
current = current->next;
}
return *this;
}
int Stock::getSize( ) const
{
return mySize;
}
bool Stock::empty( ) const
{
if(mySize == -1)
return true;
return false;
}
void Stock::insert( string initData, double costStock, int number, int index )
{
if(index == 0)
{
NodePointer NewNode = new Node;
NewNode->data = initData;
NewNode->cost = costStock;
NewNode->num_stocks = number;
NewNode->next = has_a;
has_a = NewNode;
mySize++;
}
else if(index > 0 && index <= (mySize + 1))
{
NodePointer current = has_a;
for(int i = 0; i < index - 1; i++)
current = current->next;
NodePointer NewNode = new Node;
NewNode->data = initData;
NewNode->cost = costStock;
NewNode->num_stocks = number;
NewNode->next = current->next;
current->next = NewNode;
mySize++;
}
}
void Stock::erase( int index )
{
if(has_a != NULL)
{
if(index == 0)
{
NodePointer temp = has_a;
has_a = temp->next;
delete temp;
mySize--;
}
else if(index > 0 && index <= (mySize + 1))
{
NodePointer current = has_a;
for(int i = 0; i < index -1; i++)
current = current->next;
NodePointer temp = current->next;
if(temp!=NULL) //check the condition that has //been modified
current->next = temp->next;
delete temp;
mySize--;
}
}
}
void Stock::display( ostream &out ) const
{
NodePointer current = has_a;
cout<<"Stock Symbol Cost Number of Shares"<<endl;
cout<<"---------------------------------------------"<<endl;
while(current != NULL)
{
out << current->data << " " << current->cost <<" " <<current->num_stocks<< endl;
current = current->next;
}
}
void Stock::returnMiddleList()
{
int mid=getSize()/2;
NodePointer current = has_a;
if(mid == 0)
{
cout<<current->data<<" "<<current->cost<<" "<<current->num_stocks<<endl;
}
else if(mid > 0 && mid <= (mySize + 1))
{
for(int i = 0; i <mid-1; i++)
current = current->next;
cout<<current->data<<" "<<current->cost<<" "<<current->num_stocks<<endl;
}
}
void Stock::splitInHalf()
{
int mid=getSize()/2;
NodePointer current = has_a;
Stock List1;
Stock List2;
int k=0;
//logic to split the the list into two halves
for(int i = 0; i <getSize(); i++)
{
if(i<mid)
{
List1.insert(current->data, current->cost, current-> num_stocks, i);
current=current->next;
}
else
{
List2.insert(current->data, current->cost, current-> num_stocks, k);
current=current->next;
k++;
}
}
//display the first half elements in the list
cout<<"The first half: "<<endl;
List1.display(cout);
//display the second half elements in the the list
cout<<"The second half: "<<endl;
List2.display(cout);
}
// StockLinkedList.cpp : Defines the entry point for the console application.
#include <iostream>
#include <string>
#include <time.h>
#include <sstream>
#include "StockHeader.h"
using namespace std;
int main(int argc, char const *argv[])
{
srand(time(NULL));
string s;
Stock Test;
double cost;
int num_shares;
int i;
//generating random numbers and stock symbols
for(i=0;i<20; i++)
{
stringstream ss;
ss << "A" <<rand() % 20 +1;
s=ss.str();
cost=rand()%99;
num_shares=rand()%99;
//insert the elements into the list using the insert method
Test.insert(s, cost, num_shares, i);
}
cout<<endl;
//display the list elements
cout<<"The Main list is: "<<endl;
Test.display(cout);
cout<<endl;
//print the middle element data of the list by calling the
//returnMiddleList method
cout<<"The middle element of the list is: "<<endl;
Test.returnMiddleList();
cout<<endl;
//split the list into two halves and display the contents of the two list
//by calling the splitInHalf method
cout<<"Splitting the List into two halves: "<<endl;
Test.splitInHalf();
system ("pause");
return 0;
}
Sample Output:
The Main list is:
Stock Symbol Cost Number of Shares
---------------------------------------------
A11 21 50
A6 51 78
A11 29 6
A8 63 27
A17 46 47
A17 83 62
A19 70 21
A1 29 36
A16 48 22
A15 27 90
A6 46 16
A5 11 30
A4 9 60
A19 55 63
A14 87 59
A20 7 61
A3 63 90
A9 30 61
A19 87 76
A7 53 86
The middle element of the list is:
A15 27 90
Splitting the List into two halves:
The first half:
Stock Symbol Cost Number of Shares
---------------------------------------------
A11 21 50
A6 51 78
A11 29 6
A8 63 27
A17 46 47
A17 83 62
A19 70 21
A1 29 36
A16 48 22
A15 27 90
The second half:
Stock Symbol Cost Number of Shares
---------------------------------------------
A6 46 16
A5 11 30
A4 9 60
A19 55 63
A14 87 59
A20 7 61
A3 63 90
A9 30 61
A19 87 76
A7 53 86
Press any key to continue . . .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.