(C++) Implement the linked list and test the functionality of it using tests. Wr
ID: 3735223 • Letter: #
Question
(C++) Implement the linked list and test the functionality of it using tests.
Write your Test first and then implement your functions. Don't use Templates. Please state all steps clearly.
EXPRESSIONSTREAM is given in the end.
--------------------------------------
QUEUE.H
#ifndef QUEUE_H
#define QUEUE_H
#include "linked_list.h"
namespace lab0 {
class queue {
private:
linked_list storage_structure;
public:
queue();
queue(std::string &data);
queue(const queue &original);
virtual ~queue();
queue &operator=(const queue &RHS);
bool isEmpty() const;
unsigned queueSize() const;
std::string top() const;
void enqueue(const std::string &data);
void dequeue();
friend std::ostream& operator<<(std::ostream& stream, queue& RHS);
friend std::istream& operator>>(std::istream& stream, queue& RHS);
};
}
#endif
--------------------------------------
QUEUE.CPP
namespace lab0{
queue::queue() { }
queue::queue(std::string &data) { }
queue::queue(const queue &original) { }
queue::~queue() { }
queue &queue::operator=(const queue &RHS) { }
bool queue::isEmpty() const { return false; }
unsigned queue::queueSize() const { return 0; }
std::string queue::top() const { }
void queue::enqueue(const std::string &data) { }
void queue::dequeue() { }
std::ostream& operator<<(std::ostream &stream, queue &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, queue &RHS) { return stream; }
}
--------------------------------------
STACK.H
#ifndef STACK_H
#define STACK_H
#include "linked_list.h"
namespace lab0 {
class stack {
private:
linked_list storage_structure;
public:
stack();
stack(std::string &data);
stack(const stack &original);
virtual ~stack();
stack &operator=(const stack &RHS);
bool isEmpty() const;
unsigned queueSize() const;
std::string top() const;
void push(const std::string &data);
void pop();
friend std::ostream& operator<<(std::ostream& stream, stack& RHS);
friend std::istream& operator>>(std::istream& stream, stack& RHS);
};
}
#endif
--------------------------------------
STACK.CPP
#include "stack.h"
namespace lab0{
stack::stack() { }
stack::stack(std::string &data) { }
stack::stack(const stack &original) { }
stack::~stack() { }
stack &stack::operator=(const stack &RHS) { }
bool stack::isEmpty() const { return false; }
unsigned stack::queueSize() const { return 0; }
std::string stack::top() const { }
void stack::push(const std::string &data) { }
void stack::pop() { }
std::ostream& operator<<(std::ostream &stream, stack &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, stack &RHS) { return stream; }
}
--------------------------------------
LINKED_LIST.H
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include "node.h"
#include
namespace lab0 {
class linked_list {
node *head, *tail;
public:
linked_list();
explicit linked_list(std::string &data);
linked_list(const linked_list &original);
virtual ~linked_list();
linked_list &operator=(const linked_list &RHS);
friend std::ostream& operator<<(std::ostream& stream, linked_list& RHS);
friend std::istream& operator>>(std::istream& stream, linked_list& RHS);
bool isEmpty() const;
unsigned listSize() const;
std::string get_value_at(unsigned location);
void insert(const std::string input, unsigned location = 0 );
void append(const std::string input);
void remove(unsigned location = 0);
void sort();
};
}
#endif
--------------------------------------
LINKED_LIST.CPP
#include
namespace lab0 {
linked_list::linked_list() { }
linked_list::linked_list(std::string &data) { }
linked_list::linked_list(const linked_list &original) { }
linked_list::~linked_list() { }
linked_list &lab0::linked_list::operator=(const linked_list &RHS) { }
bool linked_list::isEmpty() const { return false; }
unsigned linked_list::listSize() const { return 0; } //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
void linked_list::insert(const std::string input, unsigned int location) { //create a node from the input string and put it into the linked list at the given location node *prev; node *current; node *temp = new node (input); current = head; }
void linked_list::append(const std::string input) { } //create a new node and put it at the end/tail of the linked list
void linked_list::remove(unsigned location) { } //Remove the node at the given location
std::ostream& operator<<(std::ostream &stream, linked_list &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, linked_list &RHS) { return stream; }
void linked_list::sort() { } //Perform selection sort on the linked list
std::string linked_list::get_value_at(unsigned location) { }
}
--------------------------------------
NODE.H
#ifndef NODE_H
#define NODE_H
#include
namespace lab0 {
class node {
public:
node *next;
std::string data;
explicit node(const std::string &data) : data(data), next(nullptr){};
};
}
#endif
--------------------------------------
FANCYCALCULATOR.H
#ifndef CALCULATOR_H
#define CALCULATOR_H
#include "stack.h"
#include "queue.h"
#include "expressionstream.h"
#include
namespace lab0{
class calculator{
lab0::queue infix_expression;
lab0::queue postfix_expression;
void parse_to_infix(std::string &input_expression); //PRIVATE function used for converting input string into infix notation
void convert_to_postfix(lab0::queue infix_expression); //PRIVATE function used for converting infix FIFO to postfix
public:
calculator(); //Default constructor
calculator(std::string &input_expression); // Constructor that converts input_expression to infix and postfix upon creation
friend std::istream& operator>>(std::istream& stream, calculator& RHS); //Store the infix and postfix expression in calculator
int calculate(); //Return the calculation of the postfix expression
friend std::ostream& operator<<(std::ostream& stream, calculator& RHS); //Stream out overload. Should return in the format "Infix: #,#,#,# Postfix: #,#,#,#"
};
}
#endif
--------------------------------------
FANCYCALCULATOR.CPP
#include "fancy_calculator.h"
#include "stack.h"
#include "queue.h"
namespace lab0{
void calculator::parse_to_infix(std::string &input_expression) { }
void calculator::convert_to_postfix(lab0::queue infix_expression) { }
calculator::calculator() { }
calculator::calculator(std::string &input_expression) { }
std::istream &operator>>(std::istream &stream, calculator &RHS) { return stream; }
int calculator::calculate() { return 0; }
std::ostream &operator<<(std::ostream &stream, calculator &RHS) { return stream; }
bool is_number(std::string input_string);
bool is_operator(std::string input_string);
int get_number(std::string input_string);
std::string get_operator(std::string input_string);
int operator_priority(std::string operator_in);
}
--------------------------------------
EXPRESSIONSTREAM.CPP //THIS IS ALREADY DONE.
#include "expressionstream.h"
namespace lab1 {
bool is_number(char c);
expressionstream::expressionstream(const std::string &string_in) : buffer(string_in) {
current_pos = buffer.begin();
next_position = current_pos;
skip_white_space();
}
void expressionstream::skip_white_space() {
while (*current_pos == ' ' && current_pos != buffer.end()) ++current_pos;
while (*next_position == ' ' && next_position != buffer.end()) ++next_position;
}
std::string expressionstream::get_number() {
bool is_negative = false;
std::string::iterator number_start;
//check if the number is negative, this is used to skip any white space after '-'
if (*current_pos == '-') is_negative = true;
//find beginning of number
number_start = current_pos;
while (number_start != buffer.end() && !is_number(*number_start))++number_start;
//find ending of number
next_position = number_start;
while (next_position != buffer.end() && is_number(*next_position))++next_position;
//create and return number using position iterators
return (is_negative) ? '-' + std::string(number_start, next_position) : std::string(number_start,
next_position);
}
bool expressionstream::is_negative() {
//after finding a '-' check if it is minus or negative by checking previous character
//create an iterator to the previous character
std::string::iterator negative_check = next_position - 1;
//move backward until reach non-whitespace
while (negative_check != buffer.begin() && *negative_check == ' ') --negative_check;
//if the previous character is not a number and not a close parenthesis the number is negative
//EXAMPLE: the following should get negatives on the 13's but not the 5's : "-13-(-13-(5--13)-5)--13"
return (!is_number(*negative_check) && *negative_check != ')');
}
std::string expressionstream::get_next_token() {
//move the current_position iterator forward then get the "current" token
current_pos = next_position;
return get_current_token();
}
std::string expressionstream::get_current_token() {
skip_white_space();
//check for end of buffer
if (current_pos == buffer.end()) return "";
//reset next position each time current token is called
//this should stop the 'next_position' from drifting on
//consecutive "get_current_token()" calls
next_position = current_pos;
if (next_token_is_int())
return get_number();
//if token is not a number then it is one character long
//setting the 'next_position' iterator forward one will
//return one character
++next_position;
return std::string(current_pos, next_position);
}
bool expressionstream::next_token_is_int() {
skip_white_space();
if (is_number(*next_position))
return true;
if (*next_position != '-')
return false;
return is_negative();
}
bool expressionstream::next_token_is_op() {
skip_white_space();
if (next_token_is_int()) return false;
return (*next_position == '+' || *next_position == '-' || *next_position == '*' || *next_position == '/');
}
bool expressionstream::next_token_is_paren_open() {
skip_white_space();
return *next_position == '(';
}
bool expressionstream::next_token_is_paren_close() {
skip_white_space();
return *next_position == ')';
}
bool is_number(char c) {
return (c >= '0' && c <= '9');
}
}
Explanation / Answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int data;
struct node *next;
}*start;
/*
* Class Declaration
*/
class single_llist
{
public:
node* nodecr(int);
void insertfirst();
void insertpos();
void insertlast();
void delete_pos();
void sort();
void search();
void update();
void reverse();
void display();
single_llist()
{
start = NULL;
}
};
/*
* Main :contains menu
*/
main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
while (1)
{
cout<<endl<<"---------------------------------"<<endl;
cout<<endl<<"Operations on singly linked list"<<endl;
cout<<endl<<"---------------------------------"<<endl;
cout<<"1.Insert Node at beginning"<<endl;
cout<<"2.Insert node at last"<<endl;
cout<<"3.Insert node at position"<<endl;
cout<<"4.Sort Link List"<<endl;
cout<<"5.Delete a Particular Node"<<endl;
cout<<"6.Update Node Value"<<endl;
cout<<"7.Search Element"<<endl;
cout<<"8.Display Linked List"<<endl;
cout<<"9.Reverse Linked List "<<endl;
cout<<"10.Exit "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Inserting Node at Beginning: "<<endl;
sl.insertfirst();
cout<<endl;
break;
case 2:
cout<<"Inserting Node at Last: "<<endl;
sl.insertlast();
cout<<endl;
break;
case 3:
cout<<"Inserting Node at a given position:"<<endl;
sl.insertpos();
cout<<endl;
break;
case 4:
cout<<"Sort Link List: "<<endl;
sl.sort();
cout<<endl;
break;
case 5:
cout<<"Delete a particular node: "<<endl;
sl.delete_pos();
break;
case 6:
cout<<"Update Node Value:"<<endl;
sl.update();
cout<<endl;
break;
case 7:
cout<<"Search element in Link List: "<<endl;
sl.search();
cout<<endl;
break;
case 8:
cout<<"Display elements of link list"<<endl;
sl.display();
cout<<endl;
break;
case 9:
cout<<"Reverse elements of Link List"<<endl;
sl.reverse();
cout<<endl;
break;
case 10:
cout<<"Exiting..."<<endl;
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Creating Node
*/
node *single_llist::nodecr(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->data = value;
temp->next = NULL;
return temp;
}
}
/*
* Inserting element in beginning
*/
void single_llist::insertfirst()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *p;
temp = nodecr(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::insertlast()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s;
temp = nodecr(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}
/*
* Insertion of node at a given position
*/
void single_llist::insertpos()
{
int value, pos, counter = 0;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s, *ptr;
temp = nodecr(value);
cout<<"Enter the postion at which node to be inserted: ";
cin>>pos;
int i;
s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos == 1)
{
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (pos > 1 && pos <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{
ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<"Positon out of range"<<endl;
}
}
/*
* Sorting Link List
*/
void single_llist::sort()
{
struct node *ptr, *s;
int value;
if (start == NULL)
{
cout<<"The List is empty"<<endl;
return;
}
ptr = start;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->data > s->data)
{
value = ptr->data;
ptr->data = s->data;
s->data = value;
}
}
ptr = ptr->next;
}
}
/*
* Delete element at a given position
*/
void single_llist::delete_pos()
{
int pos, i, counter = 0;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the position of value to be deleted: ";
cin>>pos;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start = s->next;
}
else
{
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter)
{
s = start;
for (i = 1;i < pos;i++)
{
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else
{
cout<<"Position out of range"<<endl;
}
free(s);
cout<<"Element Deleted"<<endl;
}
}
/*
* Update a given Node
*/
void single_llist::update()
{
int value, pos, i;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the node postion to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start->data = value;
}
else
{
for (i = 0;i < pos - 1;i++)
{
if (s == NULL)
{
cout<<"There are less than "<<pos<<" elements";
return;
}
s = s->next;
}
s->data = value;
}
cout<<"Node Updated"<<endl;
}
/*
* Searching an element
*/
void single_llist::search()
{
int value, pos = 0;
bool flag = false;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the value to be searched: ";
cin>>value;
struct node *s;
s = start;
while (s != NULL)
{
pos++;
if (s->data == value)
{
flag = true;
cout<<"Element "<<value<<" is found at position "<<pos<<endl;
}
s = s->next;
}
if (!flag)
cout<<"Element "<<value<<" not found in the list"<<endl;
}
/*
* Reverse Link List
*/
void single_llist::reverse()
{
struct node *ptr1, *ptr2, *ptr3;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
if (start->next == NULL)
{
return;
}
ptr1 = start;
ptr2 = ptr1->next;
ptr3 = ptr2->next;
ptr1->next = NULL;
ptr2->next = ptr1;
while (ptr3 != NULL)
{
ptr1 = ptr2;
ptr2 = ptr3;
ptr3 = ptr3->next;
ptr2->next = ptr1;
}
start = ptr2;
}
/*
* Display Elements of a link list
*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = start;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<"NULL"<<endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.