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 agoRelated Solutions
Java Language Add a method (deleteGreater ()) to the LinkedList class to delete the node with...
Implement a function to find a node in a binary search tree. Using the following class...
The programming language is Python Instructions: Create a function that will delete a node in a...
public class MyLinked { static class Node { public Node (double item, Node...
The following passage refers to the operation of a free-market economy. Delete the words (in italics)...
in java This class will require the following fields: Node<T> head: the first Node in the...
Write methods contains and remove for the BinarySearchTree class. Use methods find and delete to do...
In C++, write a member method delete() that deletes a node from a linked list at...
1- Function 1: to delete a node in the head of the list. 2- Function 2:...
1. Can you extend an abstract class? In what situation can you not inherit/extend a class?...
- D. Explain what it means for recommendations to be specific and actionable. E. Discuss how charts...
- Capital Toys’ management is considering eliminating product A, which has been showing a loss for several...
- Computer Networks IT 210 Please Use your own words . sorry No handwriting no copy paste...
- The Coronavirus will obviously impact the economy of big organizations like FIFA or the NBA but...
- Question: what is the difference between rights of assertion and observation assertion. Include which financial statements...
- how to read a csv file in php and make a html table? I can't use...
- ABC Inc. is evaluating a project that will increase annual sales by $230,000 and annual cash...