Question

In: Computer Science

Extend the custom unorderedLinkedList class by adding the following operation: Find and delete the node with...

Extend the custom unorderedLinkedList class by adding the following operation:

Find and delete the node with the smallest info in the list. Delete only the first occurrence and traverse the list only once.

The function's prototype is deleteSmallest()

use this code

#include <ctime>

#include <iostream>

#include <random>

#include "unorderedLinkedList.h"

using namespace std;

int main()

{

default_random_engine e(1918);

uniform_int_distribution<int> u(10, 99);

int size = 12;

unorderedLinkedList ul;

while (ul.getnelts() < size)

{

int elt = u(e);

ul.append(elt);

ul.show(); cout << endl;

}

while (!ul.isEmpty())

{

int elt = u(e);

if (ul.delelt(elt))

{

ul.show();

cout << endl;

}

return 0;

}

#pragma once

#include <iostream>

using namespace std;

class unorderedLinkedList

{

private:

struct nodeType

{

int info;

nodeType* link;

};

public:

//constructor

unorderedLinkedList();

//destructor

~unorderedLinkedList();

//predicates

bool isEmpty();

//accessors

int find(int value);

int getnelts();

bool getelt(int where, int& elt);

bool member(int value);

//mutators

bool append(int elt);

bool delelt(int elt);

bool delat(int where);

bool insat(int where, int elt);

bool putelt(int where, int elt);

void copy(const unorderedLinkedList& original);

void show(ostream& sout = cout);

private:

void kill();

int size;

nodeType* head;

};

unorderedLinkedList::unorderedLinkedList()

{

size = 0;

head = nullptr;

}

unorderedLinkedList::~unorderedLinkedList()

{

kill();

}

bool unorderedLinkedList::isEmpty()

{

return size == 0;

}

int unorderedLinkedList::find(int elt)

{

int where = 0;

nodeType* node = head;

while (node != nullptr && node->info != elt)

{

node = node->link;

where++;

}

if (where == size)

return -1;

else

return where;

}

int unorderedLinkedList::getnelts()

{

return size;

}

bool unorderedLinkedList::getelt(int where, int& elt)

{

if (where < 0 || size <= where)

return false;

nodeType* node = head;

while (where > 0)

{

where--;

node = node->link;

}

elt = node->info;

return true;

}

bool unorderedLinkedList::member(int value)

{

int where = find(value);

return where != -1;

}

bool unorderedLinkedList::append(int elt)

{

return insat(size, elt);

}

bool unorderedLinkedList::delelt(int elt)

{

int where = find(elt);

if (where == -1)

return false;

else

return delat(where);

}

bool unorderedLinkedList::delat(int where)

{

if (where < 0 || size <= where)

return false;

nodeType* curr = head;

nodeType* pred = nullptr;

while (where > 0)

{

pred = curr;

curr = curr->link;

where--;

}

nodeType* temp = curr;

if (pred == nullptr)

head = curr->link;

else

pred->link = curr->link;

delete temp;

size--;

return true;

}

bool unorderedLinkedList::insat(int where, int elt)

{

if (where < 0 || size < where)

return false;

nodeType* node = new nodeType;

node->info = elt;

nodeType* curr = head;

nodeType* pred = nullptr;

while (where > 0)

{

pred = curr;

curr = curr->link;

where--;

}

if (pred == nullptr)

{

node->link = head;

head = node;

}

else

{

node->link = curr;

pred->link = node;

}

size++;

return true;

}

bool unorderedLinkedList::putelt(int where, int elt)

{

if (where < 0 || size <= where)

return false;

nodeType* curr = head;

while (where > 0)

{

curr = curr->link;

where--;

}

curr->info = elt;

return true;

}

void unorderedLinkedList::copy(const unorderedLinkedList& original)

{

if (this != &original)

{

kill();

size = original.size;

head = new nodeType;

head->info = original.head->info;

head->link = nullptr;

nodeType* tcurr = head;

nodeType* ocurr = original.head->link;

while (ocurr->link != nullptr)

{

nodeType* newnode = new nodeType;

newnode->info = ocurr->info;

newnode->link = nullptr;

tcurr->link = newnode;

tcurr = newnode;

ocurr = ocurr->link;

}

void unorderedLinkedList::show(ostream& sout)

{

nodeType* node = head;

while (node != nullptr)

{

sout << node->info << ' ';

node = node->link;

}

void unorderedLinkedList::kill()

{

nodeType* temp = nullptr;

nodeType* curr = head;

for (int k = 1; k <= size; ++k)

{

temp = curr;

curr = curr->link;

delete temp;

}

head = nullptr;

size = 0;

}

#include <ctime>

#include <iostream>

#include <random>

#include "unorderedLinkedList.h"

using namespace std;

int main()

{

int size = 12;

default_random_engine e(1918);

uniform_int_distribution<int> uelt(10, 99);

uniform_int_distribution<int> uidx(-size + 1, size - 1);

unorderedLinkedList ul;

while (ul.getnelts() < size)

{

int elt = uelt(e);

ul.append(elt);

ul.show(); cout << endl;

}

while (!ul.isEmpty())

{

int elt = uelt(e);

if (ul.delelt(elt))

{

ul.show();

cout << endl;

}

system("pause");

system("cls");

while (ul.getnelts() < size)

{

int idx = uidx(e);

int elt = uelt(e);

if (ul.insat(idx, elt))

{

ul.show(); cout << endl;

}

while (!ul.isEmpty())

{

int idx = uidx(e);

if (ul.delat(idx))

{

ul.show();

cout << endl;

}

system("pause");

return 0;

}

#pragma once

#include <algorithm>

#include <iterator>

#include <list>

using namespace std;

class unorderedLinkedList: public list<int>

{

public:

//predicates

bool isEmpty();

//accessors

int find(int elt);

int getnelts();

bool getelt(int widx, int& elt);

bool member(int elt);

//mutators

bool append(int elt);

bool delelt(int elt);

bool delat(int widx);

bool insat(int widx, int elt);

bool putelt(int widx, int elt);

void copy(const unorderedLinkedList& original);

void show(ostream& sout = cout);

};

//predicates

bool unorderedLinkedList::isEmpty()

{

return size() == 0;

}

int unorderedLinkedList::find(int elt)

{

list<int>::iterator wit = ::find(begin(), end(), elt);

if (wit == end())

return -1;

else

return distance(begin(), wit);

}

int unorderedLinkedList::getnelts()

{

return size();

}

bool unorderedLinkedList::getelt(int widx, int& elt)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

elt = *wit;

return true;

}

bool unorderedLinkedList::member(int elt)

{

return find(elt) != -1;

}

bool unorderedLinkedList::append(int elt)

{

return insat(size(), elt);

}

bool unorderedLinkedList::delelt(int elt)

{

list<int>::iterator wit = ::find(begin(), end(), elt);

if (wit == end())

return false;

else

{

erase(wit);

return true;

}

bool unorderedLinkedList::delat(int widx)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

erase(wit);

return true;

}

bool unorderedLinkedList::insat(int widx, int elt)

{

if (widx < 0 || size() < widx)

return false;

else if (widx == size())

{

push_back(elt);

return true;

}

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

insert(wit, elt);

return true;

}

bool unorderedLinkedList::putelt(int widx, int elt)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

*wit = elt;

return true;

}

void unorderedLinkedList::copy(const unorderedLinkedList& original)

{

if (this != &original)

{

erase(begin(), end());

::copy(original.begin(), original.end(), begin());

}

void unorderedLinkedList::show(ostream& sout)

{

::copy(begin(), end(), ostream_iterator<int>(sout, " "));

}

Solutions

Expert Solution

I have added the deleteSmallest() in unorderedLinkedList class . Please go through it and let me know if you have any doubt about it.

#include <ctime>

#include <iostream>

#include <random>

#include "unorderedLinkedList.h"

using namespace std;

int main()

{

default_random_engine e(1918);

uniform_int_distribution<int> u(10, 99);

int size = 12;

unorderedLinkedList ul;

while (ul.getnelts() < size)

{

int elt = u(e);

ul.append(elt);

ul.show(); cout << endl;

}

while (!ul.isEmpty())

{

int elt = u(e);

if (ul.delelt(elt))

{

ul.show();

cout << endl;

}

}

return 0;                   

}

#pragma once

#include <iostream>

using namespace std;






class unorderedLinkedList

{

private:

struct nodeType

{

int info;

nodeType* link;

};

public:

//constructor

unorderedLinkedList();

//destructor

~unorderedLinkedList();

//predicates

bool isEmpty();

//accessors

int find(int value);

int getnelts();

bool getelt(int where, int& elt);

bool member(int value);

//mutators

bool append(int elt);

bool delelt(int elt);

bool delat(int where);

bool insat(int where, int elt);

bool putelt(int where, int elt);

void copy(const unorderedLinkedList& original);

void show(ostream& sout = cout);

//Find and delete the node with the smallest info in the list. Delete only the first occurrence and traverse the list only once. 
void deleteSmallest();

private:

void kill();

int size;

nodeType* head;

};

unorderedLinkedList::unorderedLinkedList()

{

size = 0;

head = nullptr;

}

unorderedLinkedList::~unorderedLinkedList()

{

kill();

}

bool unorderedLinkedList::isEmpty()

{

return size == 0;

}

//newly added method 

void unorderedLinkedList::deleteSmallest(){
    nodeType *currentNode = head ;
    if(currentNode == NULL) 
     return ;
    
    int min = INT_MAX ; 
    
    while(currentNode !=NULL){
        if(currentNode->info <min){
            min = currentNode->info ;
        }
        currentNode = currentNode->link ; 
        
    }
    
    nodeType *tempCurrent = head ;
    nodeType *tempNext ;
    int minElement = min ;
    
    if(tempNode->info == minElement){
        tempNode = tempNode->next ;
        head = tempNode ; 
    }
    
    
    while(tempNode !=NULL){
        if(tempNode->info== minElement){
            tempNode->info = tempNode->link->info;
            tempNode->link = temp->link->link;
            break;
        }
        tempNode = tempNode->link ;
    }
    
    
    
}



int unorderedLinkedList::find(int elt)

{

int where = 0;

nodeType* node = head;

while (node != nullptr && node->info != elt)

{

node = node->link;

where++;

}

if (where == size)

return -1;

else

return where;

}

int unorderedLinkedList::getnelts()

{

return size;

}

bool unorderedLinkedList::getelt(int where, int& elt)

{

if (where < 0 || size <= where)

return false;

nodeType* node = head;

while (where > 0)

{

where--;

node = node->link;

}

elt = node->info;

return true;

}

bool unorderedLinkedList::member(int value)

{

int where = find(value);

return where != -1;

}

bool unorderedLinkedList::append(int elt)

{

return insat(size, elt);

}

bool unorderedLinkedList::delelt(int elt)

{

int where = find(elt);

if (where == -1)

return false;

else

return delat(where);

}

bool unorderedLinkedList::delat(int where)

{

if (where < 0 || size <= where)

return false;

nodeType* curr = head;

nodeType* pred = nullptr;

while (where > 0)

{

pred = curr;

curr = curr->link;

where--;

}

nodeType* temp = curr;

if (pred == nullptr)

head = curr->link;

else

pred->link = curr->link;

delete temp;

size--;

return true;

}

bool unorderedLinkedList::insat(int where, int elt)

{

if (where < 0 || size < where)

return false;

nodeType* node = new nodeType;

node->info = elt;

nodeType* curr = head;

nodeType* pred = nullptr;

while (where > 0)

{

pred = curr;

curr = curr->link;

where--;

}

if (pred == nullptr)

{

node->link = head;

head = node;

}

else

{

node->link = curr;

pred->link = node;

}

size++;

return true;

}

bool unorderedLinkedList::putelt(int where, int elt)

{

if (where < 0 || size <= where)

return false;

nodeType* curr = head;

while (where > 0)

{

curr = curr->link;

where--;

}

curr->info = elt;

return true;

}

void unorderedLinkedList::copy(const unorderedLinkedList& original)

{

if (this != &original)

{

kill();

size = original.size;

head = new nodeType;

head->info = original.head->info;

head->link = nullptr;

nodeType* tcurr = head;

nodeType* ocurr = original.head->link;

while (ocurr->link != nullptr)

{

nodeType* newnode = new nodeType;

newnode->info = ocurr->info;

newnode->link = nullptr;

tcurr->link = newnode;

tcurr = newnode;

ocurr = ocurr->link;

}

}

}

void unorderedLinkedList::show(ostream& sout)

{

nodeType* node = head;

while (node != nullptr)

{

sout << node->info << ' ';

node = node->link;

}

}

void unorderedLinkedList::kill()

{

nodeType* temp = nullptr;

nodeType* curr = head;

for (int k = 1; k <= size; ++k)

{

temp = curr;

curr = curr->link;

delete temp;

}

head = nullptr;

size = 0;

}

#include <ctime>

#include <iostream>

#include <random>

#include "unorderedLinkedList.h"

using namespace std;

int main()

{

int size = 12;

default_random_engine e(1918);

uniform_int_distribution<int> uelt(10, 99);

uniform_int_distribution<int> uidx(-size + 1, size - 1);

unorderedLinkedList ul;

while (ul.getnelts() < size)

{

int elt = uelt(e);

ul.append(elt);

ul.show(); cout << endl;

}

while (!ul.isEmpty())

{

int elt = uelt(e);

if (ul.delelt(elt))

{

ul.show();

cout << endl;

}

}

system("pause");

system("cls");

while (ul.getnelts() < size)

{

int idx = uidx(e);

int elt = uelt(e);

if (ul.insat(idx, elt))

{

ul.show(); cout << endl;

}

}

while (!ul.isEmpty())

{

int idx = uidx(e);

if (ul.delat(idx))

{

ul.show();

cout << endl;

}

}

system("pause");

return 0;

}

#pragma once

#include <algorithm>

#include <iterator>

#include <list>

using namespace std;

class unorderedLinkedList: public list<int>

{

public:

//predicates

bool isEmpty();

//accessors

int find(int elt);

int getnelts();

bool getelt(int widx, int& elt);

bool member(int elt);

//mutators

bool append(int elt);

bool delelt(int elt);

bool delat(int widx);

bool insat(int widx, int elt);

bool putelt(int widx, int elt);

void copy(const unorderedLinkedList& original);

void show(ostream& sout = cout);

};

//predicates

bool unorderedLinkedList::isEmpty()

{

return size() == 0;

}

int unorderedLinkedList::find(int elt)

{

list<int>::iterator wit = ::find(begin(), end(), elt);

if (wit == end())

return -1;

else

return distance(begin(), wit);

}

int unorderedLinkedList::getnelts()

{

return size();

}

bool unorderedLinkedList::getelt(int widx, int& elt)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

elt = *wit;

return true;

}

}

bool unorderedLinkedList::member(int elt)

{

return find(elt) != -1;

}

bool unorderedLinkedList::append(int elt)

{

return insat(size(), elt);

}

bool unorderedLinkedList::delelt(int elt)

{

list<int>::iterator wit = ::find(begin(), end(), elt);

if (wit == end())

return false;

else

{

erase(wit);

return true;

}

}

bool unorderedLinkedList::delat(int widx)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

erase(wit);

return true;

}

}

bool unorderedLinkedList::insat(int widx, int elt)

{

if (widx < 0 || size() < widx)

return false;

else if (widx == size())

{

push_back(elt);

return true;

}

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

insert(wit, elt);

return true;

}

}

bool unorderedLinkedList::putelt(int widx, int elt)

{

if (widx < 0 || size() <= widx)

return false;

else

{

list<int>::iterator wit = begin();

advance(wit, widx);

*wit = elt;

return true;

}

}

void unorderedLinkedList::copy(const unorderedLinkedList& original)

{

if (this != &original)

{

erase(begin(), end());

::copy(original.begin(), original.end(), begin());

}

}

void unorderedLinkedList::show(ostream& sout)

{

::copy(begin(), end(), ostream_iterator<int>(sout, " "));

}

deleteSmallest() method :

//newly added method 

void unorderedLinkedList::deleteSmallest(){
    nodeType *currentNode = head ;
    if(currentNode == NULL) 
     return ;
    
    int min = INT_MAX ; 
    
    while(currentNode !=NULL){
        if(currentNode->info <min){
            min = currentNode->info ;
        }
        currentNode = currentNode->link ; 
        
    }
    
    nodeType *tempCurrent = head ;
    nodeType *tempNext ;
    int minElement = min ;
    
    if(tempNode->info == minElement){
        tempNode = tempNode->next ;
        head = tempNode ; 
    }
    
    
    while(tempNode !=NULL){
        if(tempNode->info== minElement){
            tempNode->info = tempNode->link->info;
            tempNode->link = temp->link->link;
            break;
        }
        tempNode = tempNode->link ;
    }
    
    
    
}

Hope you got your answer ;)

If you still have any doubts please let me know in the comment box. Thanks! happy learning ;)

venereology answered 1 year ago

Next > < Previous

Related Solutions

Java Language Add a method (deleteGreater ()) to the LinkedList class to delete the node with...

Java Language Add a method (deleteGreater ()) to the LinkedList class to delete the node with the higher value data. Code: class Node { int value; Node nextNode; Node(int v, Node n) { value = v; nextNode = n; } Node (int v) { this(v,null); } } class LinkedList { Node head; //head = null; LinkedList() { } int length() { Node tempPtr; int result = 0; tempPtr = head; while (tempPtr != null) { tempPtr = tempPtr.nextNode; result =...

Implement a function to find a node in a binary search tree. Using the following class...

Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() { root = new...

The programming language is Python Instructions: Create a function that will delete a node in a...

The programming language is Python Instructions: Create a function that will delete a node in a Linked List based on position number. On below example, if you want to delete position #2, it will remove the Banana (arrangement of nodes below is Apple, Banana, Cherry, Grapes, Orange). myLinkedList = LinkedList() myLinkedList.append("Banana") myLinkedList.append("Cherry") myLinkedList.append("Grapes") myLinkedList.append("Orange") myLinkedList.prepend("Apple") myLinkedList.deleteByPositionNum(2) node = myLinkedList.head while node: print(node.value, " ") node = node.next_node You may start with the function head: def deleteByPositionNum(self, positionNum):

public class MyLinked { static class Node { public Node (double item, Node...

public class MyLinked { static class Node { public Node (double item, Node next) { this.item = item; this.next = next; } public double item; public Node next; } int N; Node first; // remove all occurrences of item from the list public void remove (double item) { // TODO } Write the remove function. Do NOT add any fields to the node/list classes, do...

in java This class will require the following fields: Node<T> head: the first Node in the...

in java This class will require the following fields: Node<T> head: the first Node in the chain Node<T> tail: the last Node in the chain int size: Keeps a count of the number of Nodes in the chain Your LinkedList class must also support the following public methods. LinkedList(): A default constructor sets both pointers to null and sets the size to 0. int size(): Returns the size of the LinkedList. void push_back(T): Creates a new Node and assigns it...

The following passage refers to the operation of a free-market economy. Delete the words (in italics)...

The following passage refers to the operation of a free-market economy. Delete the words (in italics) which are incorrect. In a totally free-market economy, the quantities of each type of good that are bought and sold, and the amounts of factors of production (labour, land and capital) that are used, are determined by the decisions of individual households and firms through the interaction of demand and supply. In goods markets, households are demanders and firms are suppliers. In...

Write methods contains and remove for the BinarySearchTree class. Use methods find and delete to do...

Write methods contains and remove for the BinarySearchTree class. Use methods find and delete to do the work

1. Can you extend an abstract class? In what situation can you not inherit/extend a class?...

1. Can you extend an abstract class? In what situation can you not inherit/extend a class? 2. Can you still make it an abstract class if a class does not have any abstract methods?

In C++, write a member method delete() that deletes a node from a linked list at...

In C++, write a member method delete() that deletes a node from a linked list at a random position. (It should first randomly generate that position. and then delete that node).

1- Function 1: to delete a node in the head of the list. 2- Function 2:...

1- Function 1: to delete a node in the head of the list. 2- Function 2: to delete a node in the end of the list. 3- Function 3: to delete a node in the middle of the list. Ask the user the value of the node to delete. 4- Test the three functions in the main() and display the new list after each delete. #include <iostream> using namespace std; struct node { int num; node * nextptr; }*head,*curnode; node...

Subjects