need to do the function Suffix_maxes in the linked list #ifndef LIST_H #define L

Question

need to do the function Suffix_maxes in the linked list

#ifndef LIST_H
#define LIST_H

#include <algorithm>
#include <iostream>

/**
* class List<T>
*
* General description: class for storing and manipulating sequences of items
* where item type is specified via template.
*
* Underlying organization: the implementation uses a singly-linked list data structure
* with pointers to both the front (first node) and back (last node) of the list.
*
* A private struct Node is used to represent individual nodes in a list.
*/

template <typename T>
class List
{
private:

struct Node
{
T data;
Node *next;

Node(const T &d = T{}, Node *n = nullptr)
: data{d}, next{n} {}
};

/* Data members of List class: a front and back pointer */
Node *front;
Node *back;
int list_size;
public:
// constructor
List() {
front = nullptr;
back = nullptr;
list_size = 0;
}

// destructor
~List() {
clear();
}
/**
* Disclaimer: C++ conventions tell us that we should have a couple
* of additional constructors here (a copy constructor, assignment operator
* etc.)
*
* However, to keep things simple for now we will ignore that convention
* (since the exposure to C++ is pretty variable it seems -- some students
* having taken 141 before last semester; some students coming from 107,
* etc.)
*/

/**
* function: clear
* desc: makes the calling list empty (but the list still
* exists).
*/
void clear()
{
Node *p = front;
Node *pnext;

while (p != nullptr)
{
pnext = p->next;
delete p;
p = pnext;
}
front = back = nullptr;
}

int length() const
{
return list_size;
}
public:
/**
* function: is_empty
* desc: Returntrue if the list is empty, false otherwise.
*/
bool is_empty() const
{
return front == nullptr;
}

/**
* function: print
* desc: self-evident: simply prints the elements/values of the list in order.
*/
void print() const
{
Node *p = front;

std::cout << "[ ";
while (p != nullptr)
{
std::cout << p->data << " ";
p = p->next;
}
std::cout << "] ";
}

/**
* function: push_front
* desc: adds a new element to the front of the list (calling object) containing val.
* Equivalently, you can think of this as an "prepend" operation.
*/
void push_front(const T &data)
{
front = new Node(data, front);

if (back == nullptr)
back = front;
list_size++;
}

/**
* function: pop_front
* desc: if the list (calling object) is non-empty, the first element (front of list)
* is removed and the value it stored is 'passed back' to the caller via the reference
* parameter val. In this case (non-empty list), true is returned for success.
*
* Otherwise (the list is empty), false is returned and the reference parameter val has
* no meaning.
*/
bool pop_front(T &val)
{
Node *tmp;

if (front == nullptr)
return false;
val = front->data;

tmp = front;
front = front->next;
delete tmp;
if (front == nullptr)
back = nullptr;
list_size++;

return true;

}

/**
* function: push_back
* desc: adds a new element to the end of the list (calling object) containing val.
* Equivalently, you can think of this as an "append" operation.
*/
void push_back(const T &val)
{
Node *tmp = new Node(val, nullptr);

if (front == nullptr)
{
front = back = tmp;
}
else
{
back->next = tmp;
back = tmp;
list_size--;
}
}

/**
* function: remove_first
* desc: removes first ocflience of x (if any) in given list (calling object).
* if a match is found (and removed), true is returned.
* Otherwise (no match found), false is returned and the list is unchanged.
*/
bool remove_first(const T &x)
{
Node *p, *tmp;
T dummy;

if (front == nullptr)
return false;
if (front->data == x)
{
pop_front(dummy);
return true;
}
p = front;
while (p->next != nullptr)
{
if (x == p->next->data)
{
tmp = p->next;
p->next = tmp->next;
if (tmp == back)
back = p;
delete tmp;
return true;
}
p = p->next;
}
return false;
}

/**
* function: slow_remove_all
* desc: removes all occurrences of x (if any) in given list (calling object).
* returns number of matches found/deleted. Relative order of undeleted elements
* is unchanged.
*
* approach: repeatedly calls remove_first until it fails.
*
* Note: function is designated with the slow_ prefix because, in the worst case, it can
* take quadratic time.
*/
int slow_remove_all(const T &x)
{
int n = 0;

while (remove_first(x))
n++;
return n;
list_size--;
}

/**
* function: is_sorted
* desc: returns true if elements in list are in sorted order from
* smallest to largest (duplicates allowed); returns false otherwise.
*
* Note: requires that type T has the > operator defined on it (perhaps via
* operator overloading as in the case of the string class)
*/
bool is_sorted() const
{
Node *p = front;

while (p != nullptr && p->next != nullptr)
{
if (p->data > p->next->data)
return false;
p = p->next;
}
return true;
}

int count(const T &x) const
{
int frequency = 0;

if (this->is_empty())
return frequency;

Node* temp1 = front;
while (temp1 != nullptr) {

if (temp1->data == x)
frequency++;
temp1 = temp1->next;
}
return frequency;

}

bool pop_back(T &data)
{
if(front == nullptr)
return false;
else{
Node *temp1 = front;
while(temp1->next->next != nullptr) {
temp1 = temp1->next;
}
this->back = temp1;
temp1=temp1->next ;
data = temp1-> data;
delete (temp1);
return true;
  

}

/*
* TODO
*
* function: suffix_maxes
*
* desc: constructs a new list of the same length as the calling object
* with the value stored at position i of the new list is the MAXIMUM
* value in the suffix (or tail) of the calling list starting from
* position i.
*
* This new list is returned and the calling list is unchanged.
*
* Example:
*
* Given List: [6, -18, 12, 4, 1, 7, 2, 5 4]
* ^^^^^^^^^^^^^^^^
*
* New list: [12, 12, 12, 7, 7, 7, 5, 5, 4]
* ^
*
* (as a sub-example, the marked entry in the new list
* (marked with '^') is the max of the marked suffix in the
* given list (marked with a bunch of '^'s).
*
* REQUIREMENTS:
*
* Total Runtime: O(n)
* Calling list is unchanged.
*
*/
List<T> *suffix_maxes() const
{
return nullptr;
}

Explanation / Answer

List<T> *suffix_maxes() const

{

if(front == nullptr)

return false;

int len = length();

if(len==0)

return nullptr;

int *arr = new int[len];

int i = 0;

Node *tmp = front;

while(tmp != nullptr){

arr[i++] = tmp->data;

tmp = tmp->next;

}

int max = arr[len-1];

Node *ret = new Node(max, nullptr);

for(int j = len-2; j>=0 ; --j){

if(max < arr[j])

max = arr[j];

ret = new Node(max, ret);

}

return ret;

}

--------------------------------------------------------------------------------------------------
Test and Let me know the results

Comment and let me know , If there is something I will help.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.