Use C++ for the following: - Implement the ListLinked ADT (the declaration is gi
ID: 3891780 • Letter: U
Question
Use C++ for the following:
- Implement the ListLinked ADT (the declaration is given in ListLinked.h)
- Implement the following operations:
- constructor, assignment operator, destructor
- insert, remove, replace, clear
- isFull, isEmpty
- gotoBeginning, gotoEnd, gotoNext, gotoPrior, getCursor
- implement the function moveToBeginning() that removes the data item marked by the cursor and reinserts it at the beginning of the list (
- implement the function insertBefore(..) that will insert the new data item before the cursor or if the list is empty as the ?rst element of the list
**********************ListLinked.H****************
//--------------------------------------------------------------------
//
// Laboratory 5 ListLinked.h
//
// Class declaration for the linked implementation of the List ADT
//
//--------------------------------------------------------------------
#ifndef LISTLINKED_H
#define LISTLINKED_H
#pragma warning( disable : 4290 )
#include <stdexcept>
#include <iostream>
using namespace std;
template <typename DataType>
class List {
public:
List(int ignored = 0);
List(const List& other);
List& operator=(const List& other);
~List();
void insert(const DataType& newDataItem) throw (logic_error);
void remove() throw (logic_error);
void replace(const DataType& newDataItem) throw (logic_error);
void clear();
bool isEmpty() const;
bool isFull() const;
void gotoBeginning() throw (logic_error);
void gotoEnd() throw (logic_error);
bool gotoNext() throw (logic_error);
bool gotoPrior() throw (logic_error);
DataType getCursor() const throw (logic_error);
// Programming exercise 2
void moveToBeginning () throw (logic_error);
// Programming exercise 3
void insertBefore(const DataType& newDataItem) throw (logic_error);
void showStructure() const;
private:
class ListNode {
public:
ListNode(const DataType& nodeData, ListNode* nextPtr);
DataType dataItem;
ListNode* next;
};
ListNode* head;
ListNode* cursor;
};
#endif
************ListLinked.cpp**********
#include "ListLinked.h"
// ListNode member functions
template <typename DataType>
List<DataType>::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr)
{
this->dataItem = nodeData;
this->next = nextPtr;
}
// List member functions
template <typename DataType>
List<DataType>::List(int ignored = 0)
{
}
template <typename DataType>
List<DataType>::List(const List& other)
{
}
template <typename DataType>
List<DataType>& List<DataType>::operator=(const List& other)
{
}
template <typename DataType>
List<DataType>::~List()
{
}
template <typename DataType>
void List<DataType>::insert(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
void List<DataType>::remove() throw (logic_error)
{
}
template <typename DataType>
void List<DataType>::replace(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
void List<DataType>::clear()
{
}
template <typename DataType>
bool List<DataType>::isEmpty() const
{
return false;
}
template <typename DataType>
bool List<DataType>::isFull() const
{
return false;
}
template <typename DataType>
void List<DataType>::gotoBeginning() throw (logic_error)
{
}
template <typename DataType>
void List<DataType>::gotoEnd() throw (logic_error)
{
}
template <typename DataType>
bool List<DataType>::gotoNext() throw (logic_error)
{
return false;
}
template <typename DataType>
bool List<DataType>::gotoPrior() throw (logic_error)
{
return false;
}
template <typename DataType>
DataType List<DataType>::getCursor() const throw (logic_error)
{
DataType t;
return t;
}
template <typename DataType>
void List<DataType>::moveToBeginning () throw (logic_error)
{
}
template <typename DataType>
void List<DataType>::insertBefore(const DataType& newDataItem) throw (logic_error)
{
}
#include "show5.cpp"
***********show5.cpp**************
//--------------------------------------------------------------------
// show5.cpp: includes implementation of showStructure
//--------------------------------------------------------------------
#include "ListLinked.h"
template <typename DataType>
void List<DataType>::showStructure() const
// Outputs the items in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.
{
if ( isEmpty() )
{
cout << "Empty list" << endl;
}
else
{
for (ListNode* temp = head; temp != 0; temp = temp->next) {
if (temp == cursor) {
cout << "[";
}
// Assumes that dataItem can be printed via << because
// is is either primitive or operator<< is overloaded.
cout << temp->dataItem;
if (temp == cursor) {
cout << "]";
}
cout << " ";
}
cout << endl;
}
}
*************test5.cpp*************
//--------------------------------------------------------------------
//
// Laboratory 5 test5.cpp
//
// Test program for the operations in the List ADT
//
//--------------------------------------------------------------------
#include <iostream>
#include "config.h"
#include "ListLinked.cpp"
using namespace std;
void print_help();
int main()
{
#if LAB5_TEST1
List<int> testList; // Test list
int testData; // List data item
#else
List<char> testList; // Test list
char testData; // List data item
#endif
char cmd; // Input command
print_help();
do
{
testList.showStructure(); // Output list
cout << endl << "Command: "; // Read command
cin >> cmd;
if ( cmd == '+' || cmd == '=' || cmd == '#' )
cin >> testData;
switch ( cmd )
{
case 'H' : case 'h':
print_help();
break;
case '+' : // insert
cout << "Insert " << testData << endl;
testList.insert(testData);
break;
case '-' : // remove
cout << "Remove the data item marked by the cursor"
<< endl;
testList.remove();
break;
case '=' : // replace
cout << "Replace the data item marked by the cursor "
<< "with " << testData << endl;
testList.replace(testData);
break;
case '@' : // getCursor
cout << "Element marked by the cursor is "
<< testList.getCursor() << endl;
break;
case '<' : // gotoBeginning
testList.gotoBeginning();
cout << "Go to the beginning of the list" << endl;
break;
case '>' : // gotoEnd
testList.gotoEnd();
cout << "Go to the end of the list" << endl;
break;
case 'N' : case 'n' : // gotoNext
if ( testList.gotoNext() )
cout << "Go to the next data item" << endl;
else
cout << "Failed -- either at the end of the list "
<< "or the list is empty" << endl;
break;
case 'P' : case 'p' : // gotoPrior
if ( testList.gotoPrior() )
cout << "Go to the prior data item" << endl;
else
cout << "Failed -- either at the beginning of the "
<< "list or the list is empty" << endl;
break;
case 'C' : case 'c' : // clear
cout << "Clear the list" << endl;
testList.clear();
break;
case 'E' : case 'e' : // empty
if ( testList.isEmpty() )
cout << "List is empty" << endl;
else
cout << "List is NOT empty" << endl;
break;
case 'F' : case 'f' : // full
if ( testList.isFull() )
cout << "List is full" << endl;
else
cout << "List is NOT full" << endl;
break;
#if LAB5_TEST2
case 'M' : case 'm' : // In-lab Exercise 2
cout << "Move the data item marked by the cursor to the "
<< "beginning of the list" << endl;
testList.moveToBeginning();
break;
#endif
#if LAB5_TEST3
case '#' : // In-lab Exercise 3
cout << "Insert " << testData << " before the "
<< "cursor" << endl;
testList.insertBefore(testData);
break;
#endif
case 'Q' : case 'q' : // Quit test program
break;
default : // Invalid command
cout << "Inactive or invalid command" << endl;
}
}
while ( cin && cmd != 'Q' && cmd != 'q' );
if( ! cin )
{
// This is useful if students are testing the list with ints, instead of
// chars, and accidentally enter a non-digit char.
cout << "cin read errror" << endl;
}
return 0;
}
void print_help()
{
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Insert x after the cursor" << endl;
cout << " - : Remove the data item marked by the cursor" << endl;
cout << " =x : Replace the data item marked by the cursor with x"
<< endl;
cout << " @ : Display the data item marked by the cursor" << endl;
cout << " < : Go to the beginning of the list" << endl;
cout << " > : Go to the end of the list" << endl;
cout << " N : Go to the next data item" << endl;
cout << " P : Go to the prior data item" << endl;
cout << " C : Clear the list" << endl;
cout << " E : Empty list?" << endl;
cout << " F : Full list?" << endl;
cout << " M : Move data item marked by cursor to beginning "
<< "(" <<
#if LAB5_TEST2
" Active "
#else
"Inactive "
#endif
<< ": In-lab Ex. 2)" << endl;
cout << " #x : Insert x before the cursor "
<< " (" <<
#if LAB5_TEST3
" Active "
#else
"Inactive "
#endif
<< " : In-lab Ex. 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
Explanation / Answer
#include "ListLinked.h"
template <typename DataType>
List<DataType>::List(int ignored) {
head = NULL;
cursor = NULL;
}
template <typename DataType>
List<DataType>::List(const List& other) {
ListNode* copy = other.head;
while (copy != NULL) {
this->dataItem = copy->dataItem;
this->next = copy->next;
gotoNext();
copy = copy->next;
}
*this = other;
}
template <typename DataType>
List<DataType>& List<DataType>::operator=(const List& other) {
ListNode* copy = other.head;
while (copy != NULL) {
insert(copy->dataItem);
gotoNext();
copy = copy->next;
}
return *this;
}
template <typename DataType>
List<DataType>::~List() {
ListNode* trash;
ListNode* step = head;
while (step != NULL) {
trash = step;
step = step->next;
delete trash;
}
head = NULL;
}
template <typename DataType> //fixed problem with adding between nodes
void List<DataType>::insert(const DataType& newDataItem) throw (logic_error) {
if (!isEmpty()) {
ListNode* tempNode = cursor;
cursor = new ListNode(newDataItem, tempNode->next);
tempNode->next = cursor;
}
else if (isEmpty()) {
head = new ListNode(newDataItem, 0);
cursor = head;
}
}
template <typename DataType>
void List<DataType>::remove() throw (logic_error) {
ListNode* lostNode;
if (isEmpty()) {
cout << "Cannot remove from empty list." << endl;
}
else if (cursor == head) {
lostNode = head;
head = head->next;
gotoNext();
delete lostNode;
}
else {
ListNode* previous;
lostNode = cursor;
previous = head;
while( previous->next != cursor ) {
previous = previous->next;
}
if(cursor->next != NULL)
cursor = cursor->next;
else
cursor = head;
previous->next = lostNode->next;
delete lostNode;
lostNode = NULL;
}
}
template <typename DataType>
void List<DataType>::replace(const DataType& newDataItem) throw (logic_error) {
if(head != NULL)
cursor->dataItem = newDataItem;
}
//Dangling memory?
template <typename DataType>
void List<DataType>::clear() {
if (isEmpty()) {
cout << "List is already empty!" << endl;
}
else {
cursor = head;
ListNode *lostNode;
while(cursor != NULL){
lostNode = head;
head = head->next;
cursor = cursor->next;
delete lostNode;
}
head = NULL;
cursor = NULL;
}
}
template <typename DataType>
bool List<DataType>::isEmpty() const {
if (head == NULL && cursor == NULL) {
return true;
}
else {
return false;
}
}
//Assume list will never be full.
template <typename DataType>
bool List<DataType>::isFull() const {
return false;
}
template <typename DataType>
void List<DataType>::gotoBeginning() throw (logic_error) {
cursor = head;
}
template <typename DataType>
void List<DataType>::gotoEnd() throw (logic_error) {
while(cursor->next != NULL){
cursor = cursor->next;
}
}
template <typename DataType>
bool List<DataType>::gotoNext() throw (logic_error) {
if (!isEmpty()) {
if (cursor->next != NULL) {
cursor = cursor->next;
return true;
}
else {
return false;
}
}
else {
return false;
}
}
template <typename DataType>
bool List<DataType>::gotoPrior() throw (logic_error) {
if(cursor != head && head != NULL){
ListNode *findPrior = head;
while(findPrior->next != cursor)
findPrior = findPrior->next;
cursor = findPrior;
return true;
}
else
return false;
}
template <typename DataType>
DataType List<DataType>::getCursor() const throw (logic_error) {
if (!isEmpty()) {
return cursor->dataItem;
}
else{
ListNode* logic_error;
throw logic_error;
}
}
// Programming exercise 2
template <typename DataType>
void List<DataType>::moveToBeginning () throw (logic_error) {
if (cursor != head && head != NULL) {
ListNode* findPrior = head;
while(findPrior->next != cursor) {
findPrior = findPrior->next;
}
findPrior->next = cursor->next;
cursor->next = head;
head = cursor;
}
}
// Programming exercise 3
template <typename DataType>
void List<DataType>::insertBefore(const DataType& newDataItem) throw (logic_error) {
if (isEmpty()) {
head = new ListNode(newDataItem, 0);
cursor = head;
}
else {
if (cursor == head) {
ListNode *node = new ListNode(newDataItem, head);
head = node;
cursor = node;
}
else {
gotoPrior();
insert(newDataItem);
}
}
}
template <typename DataType>
void List<DataType>::showStructure() const {
// Outputs the items in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.
if ( isEmpty() )
{
cout << "Empty list" << endl;
}
else
{
for (ListNode* temp = head; temp != 0; temp = temp->next) {
if (temp == cursor) {
cout << "[";
}
// Assumes that dataItem can be printed via << because
// is is either primitive or operator<< is overloaded.
cout << temp->dataItem;
if (temp == cursor) {
cout << "]";
}
cout << " ";
}
cout << endl;
}
}
template <typename DataType>
List<DataType>::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr) {
dataItem = nodeData;
next = nextPtr;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.