Now, I am confused about this function. I have no Ideal to solove it, anyone cou

Question

Now, I am confused about this function. I have no Ideal to solove it, anyone could help to finish the function filter()?

template <typename T>
class List
{
private:
// struct for singly-linked list nodes
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;

public:
// constructor
List() {
    front = nullptr;
    back = nullptr;
}

// destructor
~List() {
    clear();
}

/**
     * TODO
     * function: filter_leq
     *
     * description: removes all elements of the given list (lst) which
     *       are less than or equal to a given value (cutoff)
     *      
     *       A list containing the removed elements is returned.
     *
     * examples:
     *
     *   EX1:    lst: [4, 9, 2, 4, 8, 12, 7, 3]
     *       cutoff: 4
     *
     *       after call:
     *           lst: [9, 8, 12, 7]
     *           returned list: [4, 2, 4, 3]
     *
     *       -----------------------------------------
     *   EX2:    lst: [6, 5, 2, 1]
     *       cutoff: 6
     *
     *       after call:
     *           lst: []
     *          returned list: [6, 5, 2, 1]
     *
     * REQUIREMENTS:
     *
     *   RUNTIME: THETA(n) where n is the length of the given list
     *
     *       ORDERING: the ordering of the returned list should be the same as
     *                  in the given list
     *
     *       MEMORY:    for full credit, no new nodes should be allocated or deallocated;
     *           you should just "re-use" the existing nodes. HOWEVER, you will
     *           need to allocate a LIST structure itself (i.e., for the returned
     *           list).
     *          
     */
List<T> *filter_leq(const T &cutoff)
{

    return nullptr;
}

Explanation / Answer

#include<iostream>

using namespace std;

template<typename T>

class List

{

private:

struct Node

{

T data;

Node *next;

Node(const T &d = T{}, Node *n = NULL)

: data{d}, next{n} {}

};

/* Data members of List class: a front and back pointer */

Node *front;

Node *back;

public:

List(){

front=NULL;

back=NULL;

}

void addnode(T d){

Node *newnode =new Node(d);

if(front==NULL)

front=newnode;

else

back->next=newnode;

back=newnode;

}

void printlist(){

Node *temp=front;

while(temp){

cout<<temp->data<<" ";

temp=temp->next;

}

}

List<T> filter_leq( T &cutoff)

{  

Node* temp = front, *prev,*temp2=NULL;

List<T> newlist;

if (temp != NULL && temp->data <= cutoff)

{

front = temp->next; // Changed head

newlist.front = temp;

newlist.back =temp;

temp2=newlist.front; // free old head

return newlist;

}

while (temp != NULL)

{

prev = temp;

temp = temp->next;

if(temp->data <= cutoff){

if(newlist.front==NULL){

newlist.front = temp;

newlist .back =temp;

temp2=newlist.front; }

if (temp == NULL) newlist;

newlist.back =temp;

temp2->next=temp;

temp2=temp2->next;

prev->next = temp->next;

if(back==temp)back=prev;}

}

return newlist;

}

};

int main(){

int n,num,cutoff;

List<int> list,newlist;

cout<<"Enter length of list : ";

cin>>n;

cout<<"enter element of list ";

for(int i=0;i<n;i++){

cin>>num;

list.addnode(num);

}

list.printlist();

cout<<"Enter cutoff : ";

cin>>cutoff;

newlist=list.filter_leq(cutoff);

list.printlist();

cout<<" ";

newlist.printlist();

cout<<" ";

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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