Write the following function with the same parameters in C++ given List.H void m

Question

Write the following function with the same parameters in C++ given List.H

void merge_with(List<T> &other) {

}

function: merge_with
     *
     * description: assumes both list a and b are in
     *    sorted (non-descending) order and merges them
     *    into a single sorted list with the same
     *    elements.
     *
     *    This single sorted list is stored in a while
     *    b becomes empty.
     *
     *    if either of given lists are not sorted,
     *    we blame the caller and the behavior is
     *    implementation dependent -- i.e., don't worry
     *    about it!
     *
     *      Condition in which both parameters are the same
     *      list (not merely "equal"), the function simply
     *      does nothing and returns. This can be tested
     *      with simple pointer comparison.
     *
     *    Example:
     *
     *        a: [2 3 4 9 10 30]
     *        b: [5 8 8 11 20 40]
     *
     *        after call a.merge_with(b):
     *
     *           a: [2 3 4 5 8 8 9 10 11 20 30 40]
     *           b: []
     *
     *
     * REQUIREMENTS:
     *
     *    Runtime Must be linear in the length of the
     *    resulting merged list (or using variables above,
     *    O(a.length()+b.length()).
     *
     * should not allocate ANY new list
     *    nodes -- it should just re-link existing
     *    nodes.
     */

********************************************LIST.H*****************************************

#ifndef LIST_H
#define LIST_H

#include <algorithm>
#include <iostream>
using namespace std;

/**
* 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 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();
}
/**
     * 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;
    lengthOfList = 0;
}

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;
  

}

/**
    * 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;
    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;
    }
}

/**
    * function: remove_first
    * desc: removes first occurrence 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;
}

Explanation / Answer

void merge_with(List a , List b)

{

List* aa =&a;

List* bb=&b;

if(a.isempty())

return ;

if(b.isempty())

return ;

while(!b.empty()&&bb->data<aa->data)

{

push_front(a,bb->data);

pop_front(b);

aa=&a;

bb=&b;

}

while(!b.empty())

{

if(bb->data >aa->data)

{

aa=aa->next;

continue;

}

Node* x= new Node(bb->data);

Node* xc=aa->next;

aa->next=x;

x->next=xc;

b.pop_front();

bb=&b;

}

return ;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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