C++ (In each of the operations, there are comments within /* */ and // which sta
ID: 3791417 • Letter: C
Question
C++ (In each of the operations, there are comments within /* */ and // which states what each operation is looking for and some of the implementations has already been started. Need help with finishing the rest of the implementation for each of the following operations below. Thank you.)
Implement the ListArray ADT [the declaration is given in ListLinked.h, posted below]
Implement the following operations:
- implement the ListLinked ADT (the declaration is given in ListLinked.h)(60 points)
- 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 first element of the list
---------------------------------------------------------------------------------------------------------------------------------
#include "ListLinked.h"
// ListNode member functions
template
List::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr)
{
this->dataItem = nodeData;
this->next = nextPtr;
}
// List member functions
template
List::List(int ignored = 0)
{
//needs implementation
}
template
List::List(const List& other)
{
//needs implementation
}
template
List& List::operator=(const List& other)
{
/*
check self assignment;
Clear the list;
ListNode
*otherPtr =
other
.head;
ListNode
*holdCursor = 0;
while
(otherPtr != 0) {
insert(otherPtr->dataItem);
if
(otherPtr ==
other
.cursor) {
holdCursor = cursor;
}
otherPtr = otherPtr->next;
}
cursor = holdCursor;
}
*/
}
template
List::~List()
{
//needs implementation
}
template
void List::insert(const DataType& newDataItem) throw (logic_error)
{
/*
ListNode tmp ;
If list is empty:
tmp=new ListNode (newDataItem, 0);
Update cursor and head;
else
tmp=new ListNode
(newDataItem, cursor->next);
Update cursor;
*/
}
template
void List::remove() throw (logic_error)
{
/*
Check if list is empty;
ListNode *p;
// you need a pointer to removed item
P = cursor;
if (cursor == head){
In the case cursor is on the first node, you must set head to the next item of
the list.
head = head->next;
cursor = head;
Delete p;
}
Else if (cursor->next==0){
In this case, cursor is the last item of the list. First you must find immediately previous node of
cursor(define an auxiliary variable q):
For(q=head; q->next!=cursor; q=q->next)
;
q->next=0;
Then you must set cursor to the head.
}
Remove()
Else{
In this case, cursor is a middle item in the list. You can use similar idea as previous case.
For(q=head; q->next!=cursor; q=q->next)
;
Then you need :
q->next=cursor->next;
cursor= cursor->next;
Delete p;
}
*/
}
template
void List::replace(const DataType& newDataItem) throw (logic_error)
{
//needs implementation
}
template
void List::clear()
{
/*
cursor = head;
while (cursor != 0)
{
//Call remove function;
}
*/
}
template
bool List::isEmpty() const
{
//needs implementation
return false;
}
template
bool List::isFull() const
{
// needs implementation
return false;
}
template
void List::gotoBeginning() throw (logic_error)
{
//needs implementation
}
template
void List::gotoEnd() throw (logic_error)
{
//needs implementation
}
template
bool List::gotoNext() throw (logic_error)
{
//needs implementation
return false;
}
template
bool List::gotoPrior() throw (logic_error)
{
//needs implementation
return false;
}
template
DataType List::getCursor() const throw (logic_error)
{
//needs implementation
DataType t;
return 0;
}
template
void List::moveToBeginning () throw (logic_error)
{
//needs implementation
}
template
void List::insertBefore(const DataType& newDataItem) throw (logic_error)
{
//needs implementation
}
Explanation / Answer
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)
{
head = NULL;
cursor = NULL;
}
template <typename DataType>
List<DataType>::List(const List& other)
{
if (this != other){
ListNode *tmp = other->head;
this->head = other->head;
while (tmp->next!=NULL){
insert(tmp->dataItem);
tmp = tmp->next;
}
cursor = head;
}
}
template <typename DataType>
List<DataType>& List<DataType>::operator=(const List& other)
{
if (this != other){
ListNode *tmp = other->head;
this->head = other->head;
while (tmp->next!=NULL){
insert(tmp->dataItem);
tmp = tmp->next;
}
cursor = head;
}
return &this;
}
template <typename DataType>
List<DataType>::~List()
{
ListNode *tmp = head;
while (tmp->next != NULL){
head = tmp->next;
delete tmp;
tmp = head;
}
delete tmp;
}
template <typename DataType>
void List<DataType>::insert(const DataType& newDataItem) throw (logic_error)
{
if (head == NULL){ //EMPTY LIST
head = new ListNode(newDataItem, NULL);
cursor = head;
}
else{ //LIST NOT EMPTY
ListNode* newItem = new ListNode(newDataItem, cursor->next);
cursor->next = newItem;
cursor = cursor->next;
}
}
template <typename DataType>
void List<DataType>::remove() throw (logic_error)
{
ListNode *tmp = head;
if (tmp != NULL)
{
if (tmp == cursor){
cursor = cursor->next;
delete tmp;
head = cursor;
}else{
while (tmp->next != NULL){
if (tmp->next == cursor){
tmp->next = cursor->next;
delete cursor;
if (isEmpty()){
head = NULL;
cursor = NULL;
}
else{
if (tmp->next != NULL)
cursor = tmp->next;
else
cursor = head;
}
break;
}
tmp = tmp->next;
}
}
}
}
template <typename DataType>
void List<DataType>::replace(const DataType& newDataItem) throw (logic_error)
{
cursor->dataItem = newDataItem;
}
template <typename DataType>
void List<DataType>::clear()
{
cursor = head;
while (cursor->next != NULL){
head = cursor->next;
delete cursor;
cursor = head;
}
delete cursor;
head = NULL;
cursor = NULL;
}
template <typename DataType>
bool List<DataType>::isEmpty() const
{
if (head==NULL)
return true;
return false;
}
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)
{
ListNode* tmp = head;
while (tmp->next!=NULL)
tmp = tmp->next;
cursor = tmp;
}
template <typename DataType>
bool List<DataType>::gotoNext() throw (logic_error)
{
if (cursor->next != NULL){
cursor = cursor->next;
return true;
}
return false;
}
template <typename DataType>
bool List<DataType>::gotoPrior() throw (logic_error)
{
if (cursor == head)
return false;
ListNode* tmp = head;
while (tmp->next!=cursor)
tmp = tmp->next;
cursor = tmp;
return true;
}
template <typename DataType>
DataType List<DataType>::getCursor() const throw (logic_error)
{
return cursor->dataItem;
}
template <typename DataType>
void List<DataType>::moveToBeginning () throw (logic_error)
{
ListNode* tmp = head;
while (tmp->next!=cursor)
tmp = tmp->next;
tmp->next = cursor->next;
cursor->next = head;
head = cursor;
}
template <typename DataType>
void List<DataType>::insertBefore(const DataType& newDataItem) throw (logic_error)
{
if (cursor!=head && !isEmpty()){
ListNode* tmp = head;
while (tmp->next!=cursor)
tmp = tmp->next;
ListNode* newItem = new ListNode(newDataItem, cursor->next);
tmp->next = newItem;
newItem->next = cursor;
}
}
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);
private:
class ListNode
{
public:
ListNode(const DataType& nodeData, ListNode* nextPtr);
DataType dataItem;
ListNode* next;
};
ListNode* head;
ListNode* cursor;
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.