Write a C program for the following question. The codes are given below. Deep Co
ID: 3589583 • Letter: W
Question
Write a C program for the following question. The codes are given below.
Deep Copy Constructor reference Code: ***Just a REFERENCE***
LinkedBag::LinkedBag(const LinkedBag& aBag)
{
itemCount = aBag.itemCount;
Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node* newChainPtr = headPtr; // Points to last node in new chain
origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of new chain
} // end if
} // end copy constructor
LinkedList.cpp Code:
#include "LinkedList.h"
#include <cassert>
LinkedList::LinkedList() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
void LinkedList::clear()
{
while (!isEmpty())
remove(1);
} // end clear
int LinkedList::getLength() const
{
return itemCount;
} // end getLength
bool LinkedList::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
ItemType LinkedList::getEntry(int position) const
{
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end getEntry
bool LinkedList::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
Node* prevPtr = getNodeAt(newPosition - 1);
// Insert new node after node to which prevPtr points
newNodePtr->setNext(prevPtr->getNext());
prevPtr->setNext(newNodePtr);
}
itemCount++; // Increase count of entries
}
return ableToInsert;
} // end insert
bool LinkedList::remove(int position)
{
bool ableToRemove = (position >= 1) && (position <= itemCount);
if (ableToRemove)
{
Node* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
}
else
{
// Find node that is before the one to remove
Node* prevPtr = getNodeAt(position - 1);
// Point to node to remove
curPtr = prevPtr->getNext();
// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext(curPtr->getNext());
}
// Return node to system
curPtr->setNext(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--; // Decrease count of entries
}
return ableToRemove;
} // end remove
ItemType LinkedList::replace(int position, const ItemType& newEntry)
{
bool ableToReplace = (position >= 1) && (position <= itemCount);
if (ableToReplace)
{
Node* entryPtr = getNodeAt(position);
ItemType oldEntry = entryPtr->getItem();
entryPtr->setItem(newEntry);
return oldEntry;
}
else
{
std::string message = "replace() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end replace
Node* LinkedList::getNodeAt(int position) const
{
// Debugging check of precondition
assert( (position >= 1) && (position <= itemCount) );
// Count from the beginning of the chain
Node* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
} // end getNodeAt
LinkedList::~LinkedList()
{
clear();
} // end destructor
LinkedList.h Code:
#ifndef LINKED_LIST_
#define LINKED_LIST_
#include "Node.h"
#include <string>
using namespace std;
typedef int ItemType;
class LinkedList
{
private:
Node* headPtr; // Pointer to first node in the chain;
int itemCount; // Current count of list items
// Locates a specified node in this linked list.
Node* getNodeAt(int position) const;
public:
LinkedList();
// Copy constructor and destructor are supplied by compiler
bool isEmpty() const;
int getLength() const;
bool insert(int newPosition, const ItemType& newEntry);
bool remove(int position);
void clear();
ItemType getEntry(int position) const;
ItemType replace(int position, const ItemType& newEntry);
virtual ~LinkedList();
}; // end ArrayList
#endif
LinkedListTest.cpp Code:
#include "LinkedList.h"
#include <iostream>
int main()
{
LinkedList list;
for (int i = 1; i <= 10; i++)
{
list.insert(i, 100 + i);
}
cout << "length [10]: " << list.getLength() << endl;
cout << "isEmpty [0]: " << list.isEmpty() << endl;
list.remove(3);
cout << "length [9]: " << list.getLength() << endl;
int entry = list.getEntry(3);
cout << "Entry [104]: " << entry << endl;
list.replace(3, 999);
entry = list.getEntry(3);
cout << "Entry [999]: " << entry << endl;
cout << "list: ";
for (int i = 1; i <= list.getLength(); i++)
{
cout << list.getEntry(i) << " ";
}
cout << endl;
list.clear();
cout << "length [0]: " << list.getLength() << endl;
cout << "isEmpty [1]: " << list.isEmpty() << endl;
}
Node.cpp Code:
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
Node.h Code:
#ifndef NODE_
#define NODE_
#include <string>
using namespace std;
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
You are going to implement a Doubly Linked List. Your class will be called DoublyLinkedList Its best to start with a copy of the implementation for a regular Linked List discussed in class, and make the appropriate adjustments for it to become a doubly linked list. • Keep all the existing methods (suitably modified) • Add a tail pointer to the implementation Add a Copy Constructor that does a deep copy. (Use the Bag copy constructor as a reference) • Add another new constructor that takes a (singly) Linked List as an argument and creates the Doubly Linked List from it: DoublyLinkedList (const LinkedList & linkedList). You will create new Nodes for the doubly linked list - you will not modify the list passed in - rather, you will copy from it. You will, of course, need to include your regular LinkedList header and cpp file for this to compile. Add a method void reverse () which reverses the list. This method should not make a copy of the list, nor should it allocate any new nodes, nor should it swap data between nodes – it must reverse the list simply by modifying pointers. • Add the a method vectorExplanation / Answer
LinkedBag::LinkedBag(const LinkedBag& aBag)
{
itemCount = aBag.itemCount;
Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node* newChainPtr = headPtr; // Points to last node in new chain
origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of new chain
} // end if
} // end copy constructor
LinkedList.cpp Code:
#include "LinkedList.h"
#include <cassert>
LinkedList::LinkedList() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
void LinkedList::clear()
{
while (!isEmpty())
remove(1);
} // end clear
int LinkedList::getLength() const
{
return itemCount;
} // end getLength
bool LinkedList::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
ItemType LinkedList::getEntry(int position) const
{
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet)
{
Node* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else
{
std::string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end getEntry
bool LinkedList::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
if (ableToInsert)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// Attach new node to chain
if (newPosition == 1)
{
// Insert new node at beginning of chain
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
}
else
{
// Find node that will be before new node
Node* prevPtr = getNodeAt(newPosition - 1);
// Insert new node after node to which prevPtr points
newNodePtr->setNext(prevPtr->getNext());
prevPtr->setNext(newNodePtr);
}
itemCount++; // Increase count of entries
}
return ableToInsert;
} // end insert
bool LinkedList::remove(int position)
{
bool ableToRemove = (position >= 1) && (position <= itemCount);
if (ableToRemove)
{
Node* curPtr = nullptr;
if (position == 1)
{
// Remove the first node in the chain
curPtr = headPtr; // Save pointer to node
headPtr = headPtr->getNext();
}
else
{
// Find node that is before the one to remove
Node* prevPtr = getNodeAt(position - 1);
// Point to node to remove
curPtr = prevPtr->getNext();
// Disconnect indicated node from chain by connecting the
// prior node with the one after
prevPtr->setNext(curPtr->getNext());
}
// Return node to system
curPtr->setNext(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--; // Decrease count of entries
}
return ableToRemove;
} // end remove
ItemType LinkedList::replace(int position, const ItemType& newEntry)
{
bool ableToReplace = (position >= 1) && (position <= itemCount);
if (ableToReplace)
{
Node* entryPtr = getNodeAt(position);
ItemType oldEntry = entryPtr->getItem();
entryPtr->setItem(newEntry);
return oldEntry;
}
else
{
std::string message = "replace() called with an empty list or ";
message = message + "invalid position.";
throw(message);
}
} // end replace
Node* LinkedList::getNodeAt(int position) const
{
// Debugging check of precondition
assert( (position >= 1) && (position <= itemCount) );
// Count from the beginning of the chain
Node* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
} // end getNodeAt
LinkedList::~LinkedList()
{
clear();
} // end destructor
LinkedList.h Code:
#ifndef LINKED_LIST_
#define LINKED_LIST_
#include "Node.h"
#include <string>
using namespace std;
typedef int ItemType;
class LinkedList
{
private:
Node* headPtr; // Pointer to first node in the chain;
int itemCount; // Current count of list items
// Locates a specified node in this linked list.
Node* getNodeAt(int position) const;
public:
LinkedList();
// Copy constructor and destructor are supplied by compiler
bool isEmpty() const;
int getLength() const;
bool insert(int newPosition, const ItemType& newEntry);
bool remove(int position);
void clear();
ItemType getEntry(int position) const;
ItemType replace(int position, const ItemType& newEntry);
virtual ~LinkedList();
}; // end ArrayList
#endif
LinkedListTest.cpp Code:
#include "LinkedList.h"
#include <iostream>
int main()
{
LinkedList list;
for (int i = 1; i <= 10; i++)
{
list.insert(i, 100 + i);
}
cout << "length [10]: " << list.getLength() << endl;
cout << "isEmpty [0]: " << list.isEmpty() << endl;
list.remove(3);
cout << "length [9]: " << list.getLength() << endl;
int entry = list.getEntry(3);
cout << "Entry [104]: " << entry << endl;
list.replace(3, 999);
entry = list.getEntry(3);
cout << "Entry [999]: " << entry << endl;
cout << "list: ";
for (int i = 1; i <= list.getLength(); i++)
{
cout << list.getEntry(i) << " ";
}
cout << endl;
list.clear();
cout << "length [0]: " << list.getLength() << endl;
cout << "isEmpty [1]: " << list.isEmpty() << endl;
}
Node.cpp Code:
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
Node.h Code:
#ifndef NODE_
#define NODE_
#include <string>
using namespace std;
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.