Assignment 9 - Reference Counting and a Linked List duc March 20th The assignmen
ID: 3731797 • Letter: A
Question
Assignment 9 - Reference Counting and a Linked List duc March 20th The assignment will give you practice writing constnictors and destictors, overloaded operator functions, and implementing a linked list. You will also employ a technique called reference connting. The Plan The goal of the assignment is to track a list of various (fruit) "items". You will read and process a trausaction file (partially displayed below). The transaction file coutains 5 types of transactions. You are to store a count of the items in a sorted linked list. Details The transaction file contains slightly over 100 random transaction entries. The five transaction type entries are: I, add "item·add the item to lhe inventory, or increase the count for that item 2 remove item: remove the item from the inventor or decrease the count for that item. If the item does not exist, print error message. 3. print inwentory - print the contents of the linked listin sorted order) as shown belovw 4. misspelled transactions (add, remove, or print may be misspelled) - print an error message, inchuding the line number in the file 5. biank lines -skip over these (but count the lines) Program Requirements own linked list. You may not use any S TL containers. 1. You must write your 2. The linked list must be maintained in sorted (alphabetical) order by the (fruit) item. 3. The linked list node must contain the item name (fruit namc) and a count of the number of that item that are added to the list.. 4. You must print out the contents of the linked list when a "print list" transaction record appears. See sample output below 5. You must write at lcast 2 classes, a "node" class and a "linked list" class. Both classes must contain constructors and the "linked list" class must have a destructor 6. You must include at least two overloaded operators as member functions. 7. The print function of your "linked list" class must be implemented as an overloaded insertion operator function.Explanation / Answer
Please find the code below to get the desired output.
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
LinkedList.cpp
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// A complete working C program to demonstrate all insertion methods
// on Linked List
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
// A linked list node
struct FruitLinkedList
{
int count;
string fruitname;
struct FruitLinkedList *next;
};
// Function to insert a given node in a sorted linked list
void sortedInsert(struct FruitLinkedList**, struct FruitLinkedList*);
// function to sort a singly linked list using insertion sort
void insertionSort(struct FruitLinkedList **head_ref)
{
// Initialize sorted linked list
struct FruitLinkedList *sorted = NULL;
// Traverse the given linked list and insert every
// node to sorted
struct FruitLinkedList *current = *head_ref;
while (current != NULL)
{
// Store next for next iteration
struct FruitLinkedList *next = current->next;
// insert current in sorted linked list
sortedInsert(&sorted, current);
// Update current
current = next;
}
// Update head_ref to point to sorted linked list
*head_ref = sorted;
}
/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct FruitLinkedList** head_ref, struct FruitLinkedList* new_node)
{
struct FruitLinkedList* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->count >= new_node->count)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->count < new_node->count)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* Given a reference (pointer to pointer) to the head of a list and
an int, inserts a new node on the front of the list. */
void add(struct FruitLinkedList** head_ref, string new_data)
{
/* 1. allocate node */
struct FruitLinkedList* new_node = (struct FruitLinkedList*) malloc(sizeof(struct FruitLinkedList));
/* 2. put in the data */
new_node->fruitname = new_data;
/* 3. Make next of new node as head */
new_node->next = (*head_ref);
/* 4. move the head to point to the new node */
(*head_ref) = new_node;
}
/* Given a node prev_node, insert a new node after the given
prev_node */
void addafter(struct FruitLinkedList* prev_node, string new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
/* 2. allocate new node */
struct FruitLinkedList* new_node =(struct FruitLinkedList*) malloc(sizeof(struct FruitLinkedList));
/* 3. put in the data */
new_node->fruitname = new_data;
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, appends a new node at the end */
void append(struct FruitLinkedList** head_ref, string new_data)
{
/* 1. allocate node */
struct FruitLinkedList* new_node = (struct FruitLinkedList*) malloc(sizeof(struct FruitLinkedList));
struct FruitLinkedList *last = *head_ref; /* used in step 5*/
/* 2. put in the data */
new_node->fruitname = new_data;
/* 3. This new node is going to be the last node, so make next of
it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node */
last->next = new_node;
return;
}
// This function prints contents of linked list starting from head
void print(struct FruitLinkedList *node)
{
while (node != NULL)
{
//printf(" %d ", node->count);
cout<<" "<< node->fruitname ;
node = node->next;
}
}
/* Given a reference (pointer to pointer) to the head of a list
and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct FruitLinkedList **head_ref, string key)
{
// Store head node
struct FruitLinkedList* temp = *head_ref, *prev;
// If head node itself holds the key to be deleted
if (temp != NULL && temp->fruitname == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->fruitname != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL) return;
// Unlink the node from linked list
prev->next = temp->next;
free(temp); // Free memory
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct FruitLinkedList* head = NULL;
//string strWords[] = NULL;
vector <string> colour;
colour.push_back("add apple");
colour.push_back("remove apple");
colour.push_back("add pineapple");
colour.push_back("print all");
// Print Strings stored in Vector
for (int i=0; i<colour.size(); i++) {
string str = colour[i];
string strWords[5];
short counter = 0;
for (short j = 0; j<str.length(); j++){
if (str[j] == ' ')
counter++;
else
strWords[counter] += str[j];
}
//cout<<strWords[0]<< " ";
if(strWords[0]=="add"){
add(&head, strWords[1]);
}
else if(strWords[0]=="remove"){
deleteNode(&head,strWords[1]);
}
else if(strWords[0]=="print"){
insertionSort(&head);
print(head);
}
else {
cout<<"Bad input : "<< strWords[1]<<" ";
}
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////