Linked Lists Objectives • Get yourself familiar with the forward linked list cre

Question

Linked Lists

Objectives
• Get yourself familiar with the forward linked list creation and operations

• Manipulate pointers

• Do NOT use any STL containers

Overview
1. We wish to maintain several stocks in a linked list. Each stock has a stock symbol (STLstring), a cost (double, i.e. purchase price), the number of shares (int). One needs apointer to the next node in the linked list. There are at least the following three

approaches

:• Approach 1class stockNode {string symbol; double cost; int shares; stockNode *next; };

• Approach 2class stock {string symbol; double cost; int shares; };class stockNode {stock info; stockNode *next; };

• Approach 3class stock {string symbol; double cost; int shares; };class stockNode: public stock {stockNode *next; };

please choose approach 2 or 3.

2. Write a main program (lab4Main.cpp) that creates a forward linked list of at least 10elements, where each element holds a stock, without keeping track of list length. Noneed to have a separate stockDB class. This means the main program itself is equivalentto the stockDB class. In the main program for each stock, you can hard-code a stocksymbol (or just do S1, S2, etc.), cost, and shares (or you can randomly generate any ofthese three). Alternatively, you could choose to reading a stock file, which might beeasier.

3. From the main program, print the list.

4. Write the function "returnMiddleList" in the main program to find the middle elementof the linked list in one pass.

• This function splits the input list in half at the middle element to create twoentirely separate output linked lists of near equal size (+/- 1). In other words, write the "split in half" function.

• For each of the following cases, print the two output lists

a. The input list is an empty list.

b The input list has only one element.

c The input list has odd number of elements (> 1)

Explanation / Answer

/********************************/
/********* StockNode.H **********/
/********************************/

#include <string>
#include <iostream>

using namespace std;
class StockNode
{
friend class Folder;
private:
string symbol;
double cost;
int shares;
StockNode *next;
public:
StockNode();
StockNode(string&, double&, int&);
};

/********************************/
/************ Stock.H ***********/
/********************************/

#include <string>
using namespace std;

class StockNode;
class Stock
{
private:
StockNode *root;
public:
Folder();
~Folder();
void addNode(string&, double&, int&);
void traverseList();
}

/********************************/
/********* StockNode.cpp ********/
/********************************/

#include "StockNode.h"

StockNode::StockNode()//used for when root is allocated memort in the Folder class constructor
{

}

StockNode::StockNode(string& n, double& g, int& i)
{
symbol = n;
cost = g;
shares = i;
next = NULL;
}

/********************************/
/********* Stock.cpp ************/
/********************************/
#include "Stock.h"
#include "StockNode.h"

Stock::Stock()
{
//allocate memory for root
root = new StockNode();
root = NULL;
}

Stock::~Stock()
{
//free memory once Folder class has gone out of scope
delete root;
}

void Stock::addNode(string& name, double &co, int &sh)
{
StockNode *new_stock = new StockNode (name, co, sh);//create a new node
  
if (root == NULL)//empty link list
{
root = new_stock;
return;
}

else
{
  
StockNode *temp_node = root;//declares a Node data type to start at root node
  
while (temp_node->next != NULL)//traverses to the end of the link list
{
temp_node = temp_node->next;
}

temp_node->next = new_stock;
}
}

void Stock::traverseList()
{
StockNode *temp_node = root;
  
while (temp_node != NULL)
{
cout<<temp_node->name<<endl;
temp_node = temp_node->next;
}
}

/********************************/
/*********** main.cpp ***********/
/********************************/

#include <iostream>
#include <string>
//must include header files
#include "Stock.h"
#include "StockNode.h"

using namespace std;

void returnMiddleList(StockNode* new_stock, StockNode* &first, StockNode* &second)
{
first = NULL:
second = NULL;

//Trivial Cases
if(!new_stock)
{
return;
}

first = new_stock;
StockNode* slow = new_stock;
StockNode* fast = new_stock->next;

while(fast)
{
if(fast->next)
{
fast = fast->next->next;
}else{
break;
}

slow = slow->next;
}

//slow points the end of first half;
second = slow->next;
slow->next = NULL; //need to set this to end first half
}

int main()
{
//declare variables
Stock rec;
string name;
double cost;
int shares;

//put some garbage values in linked list
for(int i=0; i<10; i++)
{
name = "S" + to_string(i); //to_string() works in c++ 11
cost = 2.44;
shares = 1;
rec.addNode(name,cost,shares);
}

//Print out the linked list members
rec.traverseList();

//get two linked lists, equal halves, if possible, else +-1
StockNode *s1, *s2;
returnMiddleList(rec.root, s1, s2);

system ("pause");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.