C++ Assignment
Project 1 - NodeList
Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well.
struct ListNode { int element; ListNode *next; }
Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and should not directly link nodes from l1to l2(i.e. the nodes inserted into l1should be copies of the nodes from l2.)
void concatenate(const List& l2);
Write a function to insert a number as the new ith node of a linked list. Nodes initially in positions i, i+1, ..., nshould be shifted to positions
void insertith(const int& value, const size_t& i);
Write a function to remove duplicate entries in a linked list. For example, given the list (5, 2, 2, 5, 3, 9, 2)as input, your function should change the list so that on return from the function it contains (5, 2, 3, 9).
void removeDups();
The following appendfunction has been implemented and may be helpful for you!
void List::append( const int& data );
Sample testing driver code
int reserved_driver_main() { List l1; List l2; // test 1, insertith l1.insertith(1, 0); l1.insertith(5, 0); stringstream ss1; ss1 << l1; std::cout << ss1.str() << std::endl; if(ss1.str() == "5 -> 1 -> NULL (size: 2)"){ std::cout << "1.1. insert ith successfully inserted; test passed" << std::endl; } else { std::cout << "1.1. insert ith did not successfully insert; test failed" << std::endl; } l1.makeEmpty(); // test 2, remove dupes l1.insert(4); l1.insert(5); l1.insert(6); l1.insert(7); l1.remove(7); l1.insert(4); l1.insert(4); l1.insert(5); l1.removeDups(); stringstream ss2; ss2 << l1; std::cout << ss2.str() << std::endl; if(ss2.str() == "5 -> 4 -> 6 -> NULL (size: 3)"){ std::cout << "2.1. successfully removed duplicates; test passed" << std::endl; } else { std::cout << "2.1. did not successfully remove duplicates; test failed" << std::endl; } l1.makeEmpty(); // test 3, concatenate l1.insert(7); l1.insert(6); l1.insert(5); l1.insert(4); l2.insert(11); l2.insert(10); l2.insert(9); l2.insert(8); l1.concatenate(l2); stringstream ss3; ss3 << l1; std::cout << ss3.str() << std::endl; if(ss3.str() == "4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> NULL (size: 8)"){ std::cout << "3.1. successfully concatenated two lists; test passed" << std::endl; } else { std::cout << "3.1. did not successfully concatenate two lists; test failed" << std::endl; } l1.makeEmpty(); l2.makeEmpty(); // test 4, concatenate empty list l1.insert(4); l1.insert(5); l1.insert(6); l1.insert(7); l1.concatenate(l2); stringstream ss4; ss4 << l1; std::cout << ss4.str() << std::endl; if(ss4.str() == "7 -> 6 -> 5 -> 4 -> NULL (size: 4)"){ std::cout << "4.1. successfully concatenated empty list; test passed" << std::endl; } else { std::cout << "4.1. did not successfully concatenate empty list; test failed" << std::endl; } l1.makeEmpty(); return 0; }
List.cpp
#include "List.h"
#include "ListNode.h"
List::List() {
head = NULL;
listSize = 0;
}
List::~List() {
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> makeEmpty();"
<< std::endl;
#endif
makeEmpty();
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> delete( head );"
<< std::endl;
#endif
delete( head );
}
bool List::isEmpty() const {
return( head == NULL );
}
void List::makeEmpty() {
while (head != NULL) {
remove( head->getElement()
);
}
}
int List::size() const {
return( listSize );
}
void List::insert( const int& data ) {
// place data into a ListNode at the front of the
list
// it will move the head node to behind the node
// we create dynamically
ListNode* temp = head;
ListNode* newnode = new ListNode( data );
head = newnode;
newnode->setNext( temp );
listSize++;
}
void List::append( const int& data ) {
// adds an element to the end of the list
if ( isEmpty() ) {
head = new ListNode( data );
} else {
// find the end of the list
ListNode* temp = head;
while (temp->getNext() != NULL)
temp = temp->getNext();
// add node
temp->setNext( new ListNode( data ) );
}
listSize++;
}
void List::remove( const int& data ) {
ListNode* current = head;
ListNode* previous = NULL;
ListNode* nodeToRemove = NULL;
while (current != NULL) {
// have we found it at the current
node???
if (current->getElement() ==
data) {
// found it at
head node
if (previous ==
NULL) {
nodeToRemove = head;
head = head->getNext();
}
// found it
inside the list somewhere
else {
nodeToRemove = current;
// skip the current node
previous->setNext( current->getNext()
);
}
delete(
nodeToRemove );
listSize--;
break;
}
// keep looking
else {
previous =
current;
current =
current->getNext();
}
}
}
std::ostream& operator << ( std::ostream& outs,
const List& l) {
return( l.printList( outs ) );
}
std::ostream& operator << ( std::ostream& outs,
const List* l) {
return( l->printList( outs ) );
}
std::ostream& List::printList( std::ostream& outs )
const {
if (isEmpty())
outs << "Empty List" <<
std::endl;
else {
ListNode* current = head;
while (current != NULL) {
outs <<
current->getElement() << " -> ";
current =
current->getNext();
}
outs << "NULL (size: "
<< size() << ")";
}
return( outs );
}
// ---------- implemented methods ------------
void List::concatenate( const List& B ) {
// Insert code here...
}
void List::insertith( const int& data, const size_t& i)
{
// Insert code here...
}
void List::removeDups() {
// Insert code here...
}
'
List.h
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"
// comment this line to suppress output in the destructor
// this may be useful for identifying where your program is having
memory issues!
#define SHOW_DESTRUCTOR_CALLS
class List {
public:
List();
~List();
// Implement these!
void concatenate( const List& B);
void insertith( const int& data, const size_t& i);
void removeDups();
//-----------------
bool isEmpty() const;
int size() const;
void makeEmpty();
void insert( const int& data );
void append( const int& data );
void remove( const int& data );
friend std::ostream& operator << (
std::ostream& outs, const List& l );
friend std::ostream& operator << (
std::ostream& outs, const List* l );
private:
ListNode* head;
int listSize;
std::ostream& printList( std::ostream& outs )
const;
};
#endif
ListNode.cpp
#include <iostream>
#include "ListNode.h"
ListNode::ListNode( const int& theElement,
ListNode* nextNode ) : element( theElement ),
next( nextNode ) {
}
const int ListNode::getElement() const {
return( element );
}
void ListNode::setNext( ListNode * nextNode ) {
next = nextNode;
}
ListNode * ListNode::getNext() const {
return( next );
}
//ListNode.h
#ifndef LISTNODE_H
#define LISTNODE_H
class ListNode {
private:
int element;
ListNode *next;
public:
ListNode(const int& theElement, ListNode*
nextNode);
ListNode(const int& theElement);
const int getElement() const;
void setNext(ListNode * nextNode);
ListNode *getNext() const;
};
#endif // !LISTNODE_H
//ListNode.cpp
#include <iostream>
#include "ListNode.h"
ListNode::ListNode(const int& theElement,ListNode* nextNode)
: element(theElement), next(nextNode) {
}
ListNode::ListNode(const int& theElement) :
element(theElement), next(nullptr) {
}
const int ListNode::getElement() const {
return(element);
}
void ListNode::setNext(ListNode * nextNode) {
next = nextNode;
}
ListNode * ListNode::getNext() const {
return(next);
}
//List.h
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"
// comment this line to suppress output in the destructor
// this may be useful for identifying where your program is having
memory issues!
#define SHOW_DESTRUCTOR_CALLS
class List {
public:
List();
~List();
// Implement these!
void concatenate(const List& B);
void insertith(const int& data, const size_t&
i);
void removeDups();
//-----------------
bool isEmpty() const;
int size() const;
void makeEmpty();
void insert(const int& data);
void append(const int& data);
void remove(const int& data);
friend std::ostream& operator <<
(std::ostream& outs, const List& l);
friend std::ostream& operator <<
(std::ostream& outs, const List* l);
private:
ListNode * head;
int listSize;
std::ostream& printList(std::ostream& outs) const;
};
#endif
//List.cpp
#include<iostream>
#include "List.h"
#include"ListNode.h"
using namespace std;
List::List() {
head = NULL;
listSize = 0;
}
List::~List() {
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> makeEmpty();"
<< std::endl;
#endif
makeEmpty();
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> delete( head );"
<< std::endl;
#endif
delete(head);
}
bool List::isEmpty() const {
return(head == NULL);
}
void List::makeEmpty() {
while (head != NULL) {
remove(head->getElement());
}
}
int List::size() const {
return(listSize);
}
void List::insert(const int& data) {
// place data into a ListNode at the front of the
list
// it will move the head node to behind the node
// we create dynamically
ListNode* temp = head;
ListNode* newnode = new ListNode(data);
head = newnode;
newnode->setNext(temp);
listSize++;
}
void List::append(const int& data) {
// adds an element to the end of the list
if (isEmpty()) {
head = new ListNode(data);
}
else {
// find the end of the list
ListNode* temp = head;
while (temp->getNext() !=
NULL)
temp =
temp->getNext();
// add node
temp->setNext(new
ListNode(data));
}
listSize++;
}
void List::remove(const int& data) {
ListNode* current = head;
ListNode* previous = NULL;
ListNode* nodeToRemove = NULL;
while (current != NULL) {
// have we found it at the current
node???
if (current->getElement() ==
data) {
// found it at
head node
if (previous ==
NULL) {
nodeToRemove = head;
head = head->getNext();
}
// found it
inside the list somewhere
else {
nodeToRemove = current;
// skip the current node
previous->setNext(current->getNext());
}
delete(nodeToRemove);
listSize--;
break;
}
// keep looking
else {
previous =
current;
current =
current->getNext();
}
}
}
std::ostream& operator << (std::ostream& outs,
const List& l) {
return(l.printList(outs));
}
std::ostream& operator << (std::ostream& outs,
const List* l) {
return(l->printList(outs));
}
std::ostream& List::printList(std::ostream& outs) const
{
if (isEmpty())
outs << "Empty List" <<
std::endl;
else {
ListNode* current = head;
while (current != NULL) {
outs <<
current->getElement() << " -> ";
current =
current->getNext();
}
outs << "NULL (size: "
<< size() << ")";
}
return(outs);
}
// ---------- implemented methods ------------
void List::concatenate(const List& B) {
// Insert code here...
ListNode *currentB = B.head;
while (currentB != NULL) {
this->append(currentB->getElement());
currentB =
currentB->getNext();
}
}
void List::insertith(const int& data, const size_t& i)
{
// Insert code here...
if (this->size() < i || i < 0) {
cout << "List is smaller "
<< endl;
}
else {
ListNode *temp = new
ListNode(data);
if (i == 0) {
temp->setNext(this->head);
this->head =
temp;
}
else {
int position =
i;
ListNode
*current = this->head;
while (current
!= NULL && position > 0) {
current = current->getNext();
position--;
}
temp->setNext(current->getNext());
current->setNext(temp);
}
listSize++;
}
}
void List::removeDups() {
// Insert code here...
ListNode *curr1, *curr2, *duplicate;
curr1 = this->head;
/* Pick elements one by one */
while (curr1 != nullptr && curr1->getNext()
!= nullptr)
{
curr2 = curr1;
//compare curr1 element in
remaining list
while (curr2->getNext() !=
nullptr)
{
/* If duplicate
then delete it */
if
(curr1->getElement() ==
curr2->getNext()->getElement())
{
/* sequence of steps is important here */
duplicate = curr2->getNext();
curr2->setNext(curr2->getNext()->getNext());
delete(duplicate);
listSize--;
}
else {
curr2 = curr2->getNext();
}
}
curr1 = curr1->getNext();
}
}
//main.cpp
#include"List.h"
#include "ListNode.h"
#include<iostream>
#include<sstream>
using namespace std;
int main() {
List l1;
List l2;
// test 1, insertith
l1.insertith(1, 0);
l1.insertith(5, 0);
stringstream ss1;
ss1 << l1;
std::cout << ss1.str() << std::endl;
if (ss1.str() == "5 -> 1 -> NULL (size: 2)")
{
std::cout << "1.1. insert ith
successfully inserted; test passed" << std::endl;
}
else {
std::cout << "1.1. insert ith
did not successfully insert; test failed" << std::endl;
}
l1.makeEmpty();
// test 2, remove dupes
l1.insert(4);
l1.insert(5);
l1.insert(6);
l1.insert(7);
l1.remove(7);
l1.insert(4);
l1.insert(4);
l1.insert(5);
l1.removeDups();
stringstream ss2;
ss2 << l1;
std::cout << ss2.str() << std::endl;
if (ss2.str() == "5 -> 4 -> 6 -> NULL (size:
3)") {
std::cout << "2.1.
successfully removed duplicates; test passed" <<
std::endl;
}
else {
std::cout << "2.1. did not
successfully remove duplicates; test failed" <<
std::endl;
}
l1.makeEmpty();
// test 3, concatenate
l1.insert(7);
l1.insert(6);
l1.insert(5);
l1.insert(4);
l2.insert(11);
l2.insert(10);
l2.insert(9);
l2.insert(8);
l1.concatenate(l2);
stringstream ss3;
ss3 << l1;
std::cout << ss3.str() << std::endl;
if (ss3.str() == "4 -> 5 -> 6 -> 7 -> 8
-> 9 -> 10 -> 11 -> NULL (size: 8)") {
std::cout << "3.1.
successfully concatenated two lists; test passed" <<
std::endl;
}
else {
std::cout << "3.1. did not
successfully concatenate two lists; test failed" <<
std::endl;
}
l1.makeEmpty();
l2.makeEmpty();
// test 4, concatenate empty list
l1.insert(4);
l1.insert(5);
l1.insert(6);
l1.insert(7);
l1.concatenate(l2);
stringstream ss4;
ss4 << l1;
std::cout << ss4.str() << std::endl;
if (ss4.str() == "7 -> 6 -> 5 -> 4 -> NULL
(size: 4)") {
std::cout << "4.1.
successfully concatenated empty list; test passed" <<
std::endl;
}
else {
std::cout << "4.1. did not
successfully concatenate empty list; test failed" <<
std::endl;
}
l1.makeEmpty();
system("pause");
return 0;
}
//output:
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...
#include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList(); void displayList(); LinkedList(void) {head = NULL;} ~LinkedList(void) {destroyList();} }; int LinkedList::insertNode(float num) { struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL; newNode = new ListNode; if(newNode == NULL) { cout << "Error allocating memory for new list member!\n"; return 1; } newNode->value = num; newNode->next = NULL; if(head==NULL) { cout << "List...
C++ programming language: In this program you will create a simplified bag that acts like a stack meaning that the Last item inserted is the First Item that comes out. Your backend implementation must use a linked list. The code should pass the test (there's only 1) and there should be no memory leaks. Note that passing the test does not ensure full credit! The functions are listed in the suggested order of implementation but you may implement them in...
Requirements: Finish all the functions which have been declared inside the hpp file. Details: string toString(void) const Return a visible list using '->' to show the linked relation which is a string like: 1->2->3->4->5->NULL void insert(int position, const int& data) Add an element at the given position: example0: 1->3->4->5->NULL instert(1, 2); 1->2->3->4->5->NULL example1: NULL insert(0, 1) 1->NULL void list::erase(int position) Erase the element at the given position 1->2->3->4->5->NULL erase(0) 2->3->4->5->NULL //main.cpp #include <iostream> #include <string> #include "SimpleList.hpp" using std::cin; using...
I have the following c++ data structures assignment: Copy Constructors, Destructors, and Assignment Operators An understanding of how to implement copy constructors, destructors, and assignment operators is essential when working with data structures using dynamic memory allocation. Failure to implement these methods correctly can and probably will result in memory leaks. In this project, you are provided with a working implementation of a doubly-linked list in which the copy constructor, destructor, and assignment operator methods are not complete. To complete...
Given list.h, main.cpp, i need to write list.cpp. having a lot of problems. please help. list.h: ////////////////////////////////////////////////////////////////////////// #ifndef LIST_H #define LIST_H ////////////////////////////////////////////////////////////////////////// namespace CS170 { struct node { int value; node *next; }; class list { public: // Constructor for list. Creates an empty list list(); /* Destructor for list. Empty the list and release the allocated memory */ ~list(); // Prints out the values contained in the list void print_list() const; // Returns the current size of the list...
C++ - I have a doubly linked list, but I haven't been able to get the "reverse list" option in the code to work(It's option #in the menu in the program). I received this guidance for testing: Test 4 cases by entering (in this order) c,a,z,k,l,m This tests empty list, head of list, end of list and middle of list. Then delete (in this order) a,z,l. This tests beginning, end and middle deletes. This exhaustively tests for pointer errors. #include...
Hi I got error C2660 : 'valuein' : function does not take 2 parameters in visual studio 2013 this is my code so far #include <cstdlib> #include <list> #include <iostream> using namespace std; struct node { int data; node* next; }; void initialize(node*p); void insert(int data,int n); void remove(int b,int pos); bool empty(node*); void length(); bool valuein(int c); int reportvalue(int value); void ptintlist(); int menu(); int main() { struct node*head=NULL; char commands; int value; ...
C++ Linux Question : Remove Nth Node from end of list Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. (i.e. n is greater than 0) Follow up: Could you do this in one pass? Hint: Maintain two pointers and update one with...
Please fill in this code to reverse a linked list: (written in C/C++) #include #include #include using namespace std; /* Link list node */ struct Node { int data; // your code here }; /* Function to reverse the linked list */ static void reverse(struct Node** head_ref) { // your code here } /* Function to push a node */ void push(struct Node** head_ref, int new_data) { // your code here } /* Function to print linked list */ void...