I need help answering this question. Extend the class linkedListType by adding t
ID: 666142 • Letter: I
Question
I need help answering this question.
Extend the class linkedListType by adding the following operations:
(a) Find and delete the node with the smallest info from the list. (Delete only the first occurrence and traverse the list only once.)
(b) Find and delete all occurrences of a given info from the list. (Traverse the list only once.)
Add these as abstract functions in the class linkedListType and provide the definitions of these functions in the class unorderedLinkedList. Also, write a program to test these functions.
Hint: To remember the current smallest info, extra pointers (assume small and trailSmall) are required, in addition to current and trailCurrent. I need in C++.
If you need more information just let me know thanks.
Explanation / Answer
Answer:
#include "stdafx.h"
#include<iostream>
using std::cout;
using std::cin;
#ifndef H_NodeType
#define H_NodeType
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template <class Type>
class linkedListIterator
{
public :
linkedListIterator( );
linkedListIterator( nodeType<Type> *ptr );
Type operator*( );
linkedListIterator<Type> operator++( );
bool operator==( const linkedListIterator<Type> &right) const;
bool operator!=( const linkedListIterator<Type> &right) const;
private:
nodeType<Type> *current;
};
template<class Type>
linkedListIterator<Type>::linkedListIterator( )
{
current = NULL;
}
template<class Type>
linkedListIterator<Type>::linkedListIterator
( nodeType<Type> *ptr )
{
current = ptr;
}
template<class Type>
Type linkedListIterator<Type>::operator*( )
{
return current->info;
}
template<class Type>
linkedListIterator<Type> linkedListIterator<Type>::operator++( )
{
current = current->link;
return *this;
}
template<class Type>
bool linkedListIterator<Type>::operator==( const linkedListIterator<Type>& right) const
{
return ( current == right.current );
}
template<class Type>
bool linkedListIterator<Type>::operator!=( const linkedListIterator<Type>& right) const
{
return ( current != right.current );
}
template<class Type>
class linkedListType
{
public :
linkedListType( );
linkedListType(const linkedListType<Type>& otherList);
const linkedListType<Type>& operator=( const linkedListType<Type>& );
void initializeList( );
bool isEmptyList( ) const;
void print( ) const;
int length( ) const;
void destroyList( );
Type front( ) const;
Type back( ) const;
virtual bool search( const Type& searchItem ) const=0;
virtual void insertFirst( const Type& newItem ) = 0;
virtual void insertLast( const Type& newItem ) = 0;
virtual void deleteNode( const Type& deleteItem ) = 0;
virtual void deleteSmallest( ) = 0;
virtual void deleteAllSmall( ) = 0;
linkedListIterator<Type> begin( );
linkedListIterator<Type> end();
~linkedListType( );
protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;
private:
void copyList( const linkedListType<Type>& otherList);
};
template<class Type>
linkedListType<Type>::linkedListType( )
{
first = NULL;
last = NULL;
count = 0;
}
template<class Type>
linkedListType<Type>::linkedListType
(const linkedListType<Type>& otherList)
{
first = NULL;
copyList( otherList );
}
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>
& otherList)
{
if ( this != &otherList )
copyList( otherList);
return *this;
}
template<class Type>
void linkedListType<Type>::initializeList( )
{
destroyList( );
}
template<class Type>
bool linkedListType<Type>::isEmptyList( ) const
{
return ( first == NULL );
}
template<class Type>
void linkedListType<Type>::print() const
{
nodeType<Type> *current;
current = first;
while( current != NULL )
{
cout << current->info << " ";
current = current->link;
}
}
template<class Type>
int linkedListType<Type>::length() const
{
return count;
}
template<class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp;
while ( first != NULL )
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template<class Type>
Type linkedListType<Type>::front() const
{
assert( first != NULL );
return first->info;
}
template<class Type>
Type linkedListType<Type>::back() const
{
assert( last!= NULL );
return last->info;
}
template<class Type>
linkedListIterator<Type> linkedListType<Type>::begin()
{
linkedListIterator<Type> temp( first );
return temp;
}
template<class Type>
linkedListIterator<Type> linkedListType<Type>::end()
{
linkedListIterator<Type> temp( NULL );
return temp;
}
template<class Type>
linkedListType<Type>::~linkedListType()
{
destroyList();
}
template <class Type>
void linkedListType<Type>::copyList
( const linkedListType<Type>& otherList )
{
nodeType<Type> *newNode;
nodeType<Type> *current;
if ( first != NULL )
destroyList();
if ( otherList.first == NULL )
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first;
count = otherList.count;
first = new nodeType<Type>;
first->info = current->info;
first->link = NULL;
last = first;
current = current->link;
while ( current != NULL )
{
newNode = new nodeType<Type>;
newNode->info = current->info;
newNode->link = NULL;
last->link = newNode;
last = newNode;
current = current->link;
}
}
}
template <class Type>
class unorderedLinkedList : public linkedListType<Type>
{
public :
bool search( const Type& searchItem ) const;
void insertFirst( const Type& newItem );
void insertLast( const Type& newItem );
void deleteNode( const Type& deleteItem );
void deleteSmallest( );
void deleteAllSmall( );
};
template <class Type>
bool unorderedLinkedList<Type>::search( const Type& searchItem ) const
{
nodeType<Type> *current;
current = first;
while ( current != NULL )
if ( current->info == searchItem )
return true;
else
current = current->link;
return false;
}
template <class Type>
void unorderedLinkedList<Type>::insertFirst( const Type& newItem)
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = first;
first = newNode;
count++;
if ( last == NULL )
last = newNode;
}
template <class Type>
void unorderedLinkedList<Type>::insertLast( const Type& newItem )
{
nodeType<Type> *newNode;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
if ( first == NULL )
{
first = newNode;
last = newNode;
count++;
}
else
{
last->link = newNode;
last = newNode;
count++;
}
}
template <class Type>
void unorderedLinkedList<Type>::deleteNode
( const Type& deleteItem )
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
bool found;
if (first == NULL)
cout << " Cannot delete from an empty list.";
else
{
if (first->info == deleteItem)
{
current = first;
first = first->link;
count--;
if (first == NULL)
last = NULL;
delete current;
}
else
{
found = false;
trailCurrent = first;
current = first->link;
while ( current != NULL && !found )
{
if ( current->info != deleteItem )
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}
if (found)
{
trailCurrent->link = current->link;
count--;
if (last == current)
last = trailCurrent;
delete current;
}
else
cout << " The item to be deleted is"<< "not in the list.";
}
}
}
template <class Type>
void unorderedLinkedList<Type>::deleteSmallest()
{
if ( first == NULL )
{
cout<<" There were no elements in the list to delete.";
return;
}
nodeType<Type> *current;
current = first;
Type item = current->info;
current = current->link;
while ( current != NULL )
{
if ( item > current->info )
item = current->info;
current = current->link;
}
deleteNode( item );
}
template <class Type>
void unorderedLinkedList<Type>::deleteAllSmall( )
{
if ( first == NULL )
{
cout <<" There were no elements in the list to delete.";
return;
}
nodeType<Type> *current;
current = first;
Type item = current->info;
int count = 1;
current = current->link;
while ( current != NULL )
{
if ( current->info == item )
count++;
if ( item > current->info )
{
item = current->info;
count = 1;
}
current = current->link;
} for ( int i = 0; i < count; i++ )
deleteNode( item );
}
int main( )
{
cout<<"*************************PROGRAM*********************************";
cout<<" Find and Delete the node with the smallest info in the list and"
<<" Find and Delete all occurrences of a given info from the list .";
unorderedLinkedList<int> myList;
cout << " Inserting random numbers into the list.";
myList.insertFirst( 3 );
myList.insertFirst( 15 );
myList.insertFirst( 22 );
myList.insertLast( 1);
myList.insertFirst( 31);
myList.insertFirst( 48 );
myList.insertFirst( 57 );
myList.insertFirst( 87 );
myList.insertFirst( 67 );
cout << " The elements in the list : ";
myList.print( );
cout << " Deleting all occurrences of the smallest element.";
myList.deleteAllSmall( );
cout << " The elements in the list : ";
myList.print();
cout <<" Deleting first occurrence of the smallest element.";
myList.deleteSmallest( );
cout << " The elements in the list : ";
myList.print( );
cout << " ";
system( "pause" );
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.