Question
I know how to do this problem using an array, but I do not understand linkedlist. Please help. implement the LinkedList ADT [the declaration is
I know how to do this problem using an array, but I do not understand linkedlist. Please help.
implement the LinkedList ADT [the declaration is given in ListLinked.h]
- implement the following operations:
- constructor, copy constructor, assignment operator, destructor; (30 pts)
- insert; (10 pts)
- implement the LinkedList ADT [the declaration is given in ListLinked.h]
- implement the following operations:
- remove, replace, clear; (30 pts)
- isFull, isEmpty; (10 pts)
- gotoBeginning, gotoEnd, gotoNext, gotoPrior, getCursor; (20 pts)
- finish Test Plan 5-1, and change data type from a character to an integer (change the value of LAB5_TEST1 from 0 to 1 in config.h) to finish Test Plan 5-2;
config.h:
/**
* Linked List class (Lab 5) configuration file.
* Activate test #N by defining the corresponding LAB5_TESTN to have the
value 1.
*/
#define LAB5_TEST1 0 // 1 means test with int instead of char
#define LAB5_TEST2 0 // Activate moveToBeginning (prog exercise 2)
#define LAB5_TEST3 0 // Activate insertBefore (prog exercise 3)
ListLinked.h:
//--------------------------------------------------------------------
//
// Laboratory 5 ListLinked.h
//
// Class declaration for the linked implementation of the List ADT
//
//--------------------------------------------------------------------
#ifndef LISTLINKED_H
#define LISTLINKED_H
#include
#include
using namespace std;
template
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
List
nextPtr)
{
this->dataItem = nodeData;
this->next = nextPtr;
}
// List member functions
template
List
{
}
template
List
{
}
template
List
{
}
template
List
{
}
template
void List
(logic_error)
{
}
template
void List
{
}
template
void List
(logic_error)
{
}
template
void List
#include "ListLinked.h"
// ListNode member functions
template
List
nextPtr)
{
this->dataItem = nodeData;
this->next = nextPtr;
}
// List member functions
template
List
{
}
template
List
{
}
template
List
{
}
template
List
{
}
template
void List
(logic_error)
{
}
template
void List
{
}
template
void List
(logic_error)
{
}
template
void List
{
}
template
bool List
{
return false;
}
template
bool List
{
return false;
}
template
void List
{
}
template
void List
{
}
template
bool List
{
return false;
}
template
bool List
{
return false;
}
template
DataType List
{
DataType t;
return t;
}
template
void List
{
}
template
void List
(logic_error)
{
}
{
}
template
bool List
{
return false;
}
template
bool List
{
return false;
}
template
void List
{
}
template
void List
{
}
template
bool List
{
return false;
}
template
bool List
{
return false;
}
template
DataType List
{
DataType t;
return t;
}
template
void List
{
}
template
void List
(logic_error)
{
}
#include "show5.cpp"
show5.cpp:
//--------------------------------------------------------------------
// show5.cpp: includes implementation of showStructure
//--------------------------------------------------------------------
template
void List
// 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
#include "config.h"
#include "ListLinked.cpp"
using namespace std;
void print_help();
int main()
{
#if LAB5_TEST1
List
int testData; // List data item
#else
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;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started