0

I have been working on this program awhile and I am almost done with it except for trying to get the output to look like what instructor wants. Here how the output should look:

BREAKING DOWN: list =     DUMP: (size = 4, first = 4, last = 3) 
    DUMP:   head = : 4 
    DUMP:   data = : 2 
    DUMP:   data = : 5 
    DUMP:   data = : 3 

BREAKING DOWN: list =     DUMP: (size = 2, first = 4, last = 2) 
    DUMP:   head = : 4 
    DUMP:   data = : 2 

BREAKING DOWN: list =     DUMP: (size = 1, first = 4, last = 4) 
    DUMP:   head = : 4 

BREAKING DOWN: list =     DUMP: (size = 1, first = 2, last = 2) 
    DUMP:   head = : 2 

MERGED: list  =     DUMP: (size = 2, first = 2, last = 4) 
    DUMP:   head = : 2 
    DUMP:   data = : 4 

BREAKING DOWN: list =     DUMP: (size = 2, first = 5, last = 3) 
    DUMP:   head = : 5 
    DUMP:   data = : 3 

BREAKING DOWN: list =     DUMP: (size = 1, first = 5, last = 5) 
    DUMP:   head = : 5 

BREAKING DOWN: list =     DUMP: (size = 1, first = 3, last = 3) 
    DUMP:   head = : 3 

MERGED: list  =     DUMP: (size = 2, first = 3, last = 5) 
    DUMP:   head = : 3 
    DUMP:   data = : 5 

MERGED: list  =     DUMP: (size = 4, first = 2, last = 5) 
    DUMP:   head = : 2 
    DUMP:   data = : 3 
    DUMP:   data = : 4 
    DUMP:   data = : 5

Here is my code it is pretty long. I am using a linked list to store the nodes. I have tried putting cout statements and using my dump() from my linked list in different parts of the code but I cant get the output right any help would be
much appreciated. CODE:

class node
{
  public:
    typedef int data_t;

    node(data_t d) { next = NULL; data = d; }

    node *next;
    data_t data;
};

class linked_list
{
  private:
    node *head;

  public:
    linked_list()
    {
        head = NULL;
    }

    int size()
    {
        int length = 0;
        node *sizeptr = head;
        while(sizeptr != NULL)
        {
            sizeptr = sizeptr->next;
            length++;
        }
        return length;
    }

    void add(int n, node::data_t d)
    {
        int number=0;
        node *tmp;
        node *nhp = new node(d);
        if(head == NULL){
            head=nhp;
        }else if(n == 0){
            nhp->next = head;
            head = nhp;
        }else{
            tmp=head;
            while((tmp->next != NULL) & (number < n-1)){
                tmp = tmp->next;
                number++;
            }
            nhp->next=tmp->next;
            tmp->next=nhp;
        }
    }

    void add_last(node::data_t d)
    {
        add(size(),d);
    }

    void add_first(node::data_t d)
    {
        add(0,d);
    }

    node::data_t get(int n)
    {
        int number=0;
        node *gptr = head;
        if(head == NULL){
            cout << "List is empty!" <<endl;
                return 0;
        }else if(n == 0){
            return gptr->data;
        }else if(n == size()-1){
            while(gptr->next != NULL)
            {
                gptr=gptr->next;
            }
            return gptr->data;

        }else if(n >= size()-1){
            cout << "non existent index" << endl;
            return 0;
        }else if((n > 0) & (n <= size()-1)){
            while(number < n)
            {
                gptr = gptr->next;
                number++;
            }
            return gptr->data;
        }

                return 0;
    }

    node::data_t get_first()
    {
        return get(0);
    }

    node::data_t get_last()
    {
        return get(size()-1);
    }

    void remove(int n)
    {
        int number=0;
        node *tmp, *current;
        if(head == NULL){
         cout << "The list is empty!" << endl;
        }else{
            current=head;
            if(current->next==NULL){
                delete(current);
                head=NULL;
            }else if(n == 0){
                current=head;
                head=head->next;
                delete(current);
            }else if(n > size()-1){
                cout << "nonexistent indez" << endl;
            }else{
                while((current->next != NULL) & (number < n))
                {
                    tmp = current;
                    current = current->next;
                    number++;
                }
            tmp->next=current->next;
            delete(current);
            }
        }
  }

    void remove_first()
    {
        remove(0);
    }

    void remove_last()
    {
        remove(size()-1);
    }

    void dump()
    {
        node *tptr;

        cout << "     DUMP: (size = " << size() << ", first = " << get_first()
<<", last = " << get_last() << ")\n" ;
        if (head == NULL) {
            cout << "    DUMP: head = NULL\n\n";
            return;
        }
        tptr = head;

        cout << "    DUMP:   head = : " << tptr->data << endl;
        while (tptr->next != NULL) {
            tptr = tptr->next;
        cout << "    DUMP:   data = : " << tptr->data << endl;
        }
        cout << endl;
    }
};
class mergesort
{

  public:

    mergesort(int ar[], int len);

    void mergesortlink(linked_list& list);

    void merge(linked_list& list1, linked_list& list2, linked_list& list);
};




  mergesort::mergesort(int ar[], int len)
  {
      int i;

      linked_list alist;


      for (i=0; i<len; i++){
      alist.add_last(ar[i]);
      }
      alist.dump();

      mergesortlink(alist);

      for(i=0;i<len;i++)
      {
          ar[i] = alist.get_first();
          alist.remove_first();
      }
  }


  void mergesort::mergesortlink(linked_list& list)
  {
      int i;
      int d;
      linked_list list1;
      linked_list list2;

      int n = list.size();
      if(n < 2){
          return;
      }
      for (i=1; i <= (n+1)/2; i++)
      {
          d = list.get_first();
          list.remove(0);
          list1.add_last(d);
   }

      for (i=1; i <= n/2; i++)
      {
          d = list.get_first();
          list.remove(0);
          list2.add_last(d);
      }

    mergesortlink(list1);
    mergesortlink(list2);

    merge(list1,list2,list);

  }


  void mergesort::merge(linked_list& list1, linked_list& list2, linked_list& list)
  {
      int d,d1,d2;

      while(list1.size()!=0 && list2.size()!=0)
      {

          d1 = list1.get_first();
          d2 = list2.get_first();

          if(d1 < d2)
          {
              d = list1.get_first();
              list1.remove(0);
              list.add_last(d);
              list.dump();
          }else{
              d = list2.get_first();
              list2.remove(0);
              list.add_last(d);
              list.dump();
          }
      }

      if(list1.size()==0)
      {

          while(list2.size()!=0)
          {
              d = list2.get_first();
              list2.remove(0);
              list.add_last(d);
              list.dump();
          }
      }

      if(list2.size()==0)
      {
          while(list1.size()!=0)
          {
              d = list1.get_first();
              list1.remove(0);
              list.add_last(d);
              list.dump();
          }

      }

  }
int main(void)
{

    int ar[100];

    int i, v, len;

    for (i=0; i<100; i++) {
        cout << "enter a number (-1 to quit): ";
        cin >> v;

        if (v < 0) break;

        ar[i] = v;
    }

    len = i;

    cout << "main:  before sort:\n";
    for (i=0; i<len; i++) {
        cout << "main:  ar[" << i << "] = " << ar[i] << endl;
    }

    mergesort ms(ar, len);
    cout << "main:  after sort:\n";
    for (i=0; i<len; i++) {
        cout << "main:  ar[" << i << "] = " << ar[i] << endl;
    }

//      return 0;
2
Contributors
1
Reply
2
Views
12 Years
Discussion Span
Last Post by 1o0oBhP
0

what exact problem do you have? is it the merging and sorting? try traversing the second list, adding each element to the first. This will merge two lists. To sort use any method you like, but it may be easy to convert the complete list to an array OR overload the [] operator to work like an array subscript operator. I have posted a c/c++ snippet about linked list if it helps

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.