Question: Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct
Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well.
struct ListNode { int element;
ListNode *next;
}
1. Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1) and l2 = (4, 5), after return from concatenate(l1,l2) the list l1 should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2 and should not directly link nodes from l1 to l2 (i.e. the nodes inserted into l1 should be copies of the nodes from l2.)
Precondition: h1 and h2 are head pointers of linked lists. The lists may be empty or non-empty. Postcondition: A copy of list h2 is concatenated (added to the end) of list h1. List h2 should be unchanged by the function. //
NOTE: The nodes added to the list h1 must be copies of the nodes in list h2. void concatenate(Node*& h1, Node* h2);
2. Write a function to insert a number as the new ith node of a linked list. Nodes initially in positions i, i+1, ..., n should be shifted to positions
Precondition: head_ptr is the head pointer of a linked list. The list may be empty or non-empty. Postcondition: The number value is inserted as the ith member of the list head_ptr. If the list head_ptr has fewer than i-1 nodes in it, then value is inserted as the last node in the list. void insertith(Node*& head_ptr, int value, size_t i);
void insertith(Node*& head_ptr, int value, size_t i);
3. Write a function to remove duplicate entries in a linked list. For example, given the list (5, 2, 2, 5, 3, 9, 2) as input, your function should change the list so that on return from the function it contains (5, 2, 3, 9).
Precondition: head_ptr is the head pointer of a linked list. The list may be empty or non-empty. Postcondition: Each node in the list must have a unique element value. void removeDups(Node*& head_ptr);
You will also notice the function as shown below. This is not required of you but implementing this helper can make the rest of the assignment more manageable.
void List::append( const int& data );
MAIN.CPP
#include
#include
#include "List.h"
#include "ListNode.h"
using namespace std;
enum CHOICE { PRINT1STLIST, PRINT2NDLIST, QUIT, INSERT, REMOVE, ISEMPTY, MAKEEMPTY, CONCATENATE, INSERTITH, REMOVEDUPS };
CHOICE menu();
int main(int argc, char* argv[])
{
List l;
List l2;
CHOICE c;
int value, pos;
do {
c = menu();
switch( c ) {
case PRINT2NDLIST:
cout << l2;
break;
case PRINT1STLIST:
cout << l;
break;
case ISEMPTY:
if (l.isEmpty()) {
cout << "list is empty" << endl;
}
else {
cout << "list is not empty" << endl;
}
break;
case MAKEEMPTY:
l.makeEmpty();
break;
case INSERT:
cout << "enter an int to insert:";
cin >> value;
l.insert( value );
break;
case REMOVE:
cout << "enter an int to remove:";
cin >> value;
l.remove( value );
break;
case CONCATENATE:
cout << "doing concatenation" << endl;
l.concatenate(l2);
break;
case INSERTITH:
cout << "enter an int to insert:";
cin >> value;
cout << "enter the position to insert into:";
cin >> pos;
cout << "inserting into ith position" << endl;
l.insertith(value, pos);
break;
case REMOVEDUPS:
cout << "removing duplicates" << endl;
l.removeDups();
break;
}
} while (c != QUIT);
return( 0 );
}
CHOICE menu() {
char c;
CHOICE result;
cout << "i(S)empty (M)akeEmpty (I)nsert (R)emove Print(1)stList Print(2)ndList (C)concatentate I(N)sertIth R(E)moveDups (Q)uit:";
cin >> c;
switch( c ) {
case 'C':
case 'c':
result = CONCATENATE;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'N':
case 'n':
result = INSERTITH;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case '1':
result = PRINT1STLIST;
break;
case '2':
result = PRINT2NDLIST;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'E':
case 'e':
result = REMOVEDUPS;
break;
default:
result = menu();
}
return( result );
}
LIST.H
#ifndef LIST_H
#define LIST_H
#include
#include "ListNode.h"
class List {
public:
List();
~List();
// Implement these!
void concatenate( const List& B);
void insertith( const int& data, const size_t& i);
void removeDups();
//-----------------
bool isEmpty() const;
int size() const;
void makeEmpty();
void insert( const int& data );
void remove( const int& data );
friend std::ostream& operator << ( std::ostream& outs, const List& l );
friend std::ostream& operator << ( std::ostream& outs, const List* l );
private:
ListNode* head;
int listSize;
std::ostream& printList( std::ostream& outs ) const;
//Implement this!!
void append( const int& data );
};
#endif
LIST.CPP
#include "List.h"
#include "ListNode.h"
#include "Settings.h"
List::List() {
head = NULL;
listSize = 0;
}
List::~List() {
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> makeEmpty();" << std::endl;
#endif
makeEmpty();
#ifdef SHOW_DESTRUCTOR_CALLS
std::cout << "about to--> delete( head );" << std::endl;
#endif
delete( head );
}
bool List::isEmpty() const {
return( head == NULL );
}
void List::makeEmpty() {
while (head != NULL) {
remove( head->getElement() );
}
}
int List::size() const {
return( listSize );
}
void List::insert( const int& data ) {
// place data into a ListNode at the front of the list
// it will move the head node to behind the node
// we create dynamically
ListNode* temp = head;
ListNode* newnode = new ListNode( data );
head = newnode;
newnode->setNext( temp );
listSize++;
}
void List::remove( const int& data ) {
ListNode* current = head;
ListNode* previous = NULL;
ListNode* nodeToRemove = NULL;
while (current != NULL) {
// have we found it at the current node???
if (current->getElement() == data) {
// found it at head node
if (previous == NULL) {
nodeToRemove = head;
head = head->getNext();
}
// found it inside the list somewhere
else {
nodeToRemove = current;
// skip the current node
previous->setNext( current->getNext() );
}
delete( nodeToRemove );
listSize--;
break;
}
// keep looking
else {
previous = current;
current = current->getNext();
}
}
}
std::ostream& operator << ( std::ostream& outs, const List& l) {
return( l.printList( outs ) );
}
std::ostream& operator << ( std::ostream& outs, const List* l) {
return( l->printList( outs ) );
}
std::ostream& List::printList( std::ostream& outs ) const {
if (isEmpty())
outs << "Empty List" << std::endl;
else {
outs << "List has " << size() << " elements: " << std::endl;
ListNode* current = head;
while (current != NULL) {
outs << current->getElement() << " -> ";
current = current->getNext();
}
outs << " NULL";
outs << std::endl;
}
return( outs );
}
// ---------- implemented methods ------------
void List::concatenate( const List& B ) {
// Insert code here...
}
void List::insertith( const int& data, const size_t& i) {
// Insert code here...
}
void List::removeDups() {
// Insert code here...
}
SETTINGS.H
// uncomment to show destructor calls #define SHOW_DESTRUCTOR_CALLS
LISTNODE.CPP
#include
#include "ListNode.h"
ListNode::ListNode( const int& theElement,
ListNode* nextNode ) : element( theElement ), next( nextNode ) {
}
const int ListNode::getElement() const {
return( element );
}
void ListNode::setNext( ListNode * nextNode ) {
next = nextNode;
}
ListNode * ListNode::getNext() const {
return( next );
}
LISTNODE.H
#ifndef LISTNODE_H
#define LISTNODE_H
#include
class ListNode {
public:
ListNode( const int& theElement = 0, ListNode * nextNode = NULL );
const int getElement() const;
void setNext( ListNode * nextNode );
ListNode * getNext() const;
private:
int element;
ListNode* next;
};
#endif
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help