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 10 months agoRelated Solutions
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)...
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?...
Extend the program by adding rules for the following family relationships (add more facts as you...
Use a priority queue to simulate prioritized jobs Priority Queue class Queue Class Node Class (Node...
- assume n = 2^100. consider the following problem. given an unsorted list of size n you...
- Can you please explain loop invariant for Heapsort, in which Min-Heapify and Build-Min-Heap are correct
- Bridgton Golf Academy is evaluating new golf practice equipment. The "Dimple-Max" equipment costs $140,000, has a...
- Question 1 (10 marks) As part of the fight to slow the progression of the COVID-19...
- SOC-p:How can deviance contribute to society and on the flip side how does it detract from...
- What action should be taken if an amount is found on a credit card statement that...
- On our text book (Ghillyer) you will find the phrase “Sustainable ethics is a culture are...