0

Hello,
I need to make this program sort the numbers entered with merge sort then print them. I am having trouble calling merge sort and getting it to print.

Here is the code:

#include <iostream>
#include "queueLinkedList.cpp"

using namespace std;

/*struct Item : Data
{
    int value;
    Item *next;      
};*/

class mergeSort : public Queue
{
     public:
            Data* divide(Data*);
            Data* merge(Data*, Data*);
            Data* mergesort(Data*);
            Data* mergesort(void);
            Queue queue;
};

Data *
mergeSort::divide(Data *a)
{
   Data *b, *c;
   
   b = a;
   c = a->next;
   c = c->next;
   
   while(c != NULL)
   {
       c = c->next;
       b = b->next;
       
       if(c != NULL)
          c = c->next;
   }    
   
   c = b->next;
   b->next = NULL;
   
   return c;       
}

Data *
mergeSort::merge(Data *p, Data *q)
{
     Data *r, *start;
     int num;
     if(p->value <= q->value)
     {
          r = p;
          num = p->value;
          addToQueue(num);
          p = p->next; 
          print();           
     }           
     
     else
     {
         r = q;
         num = q->value;
         addToQueue(num);
         q = q->next;    
     }
     
     start = r;
     
     while(p != NULL && q != NULL)
     {
         if(p->value <= q->value)
         {
              r->next = p;
              r = p;
              p = p->next;         
         }
         
         else
         {
             r->next = q;
             r = q;
             q = q->next;
         }
     }
     
     if(p == NULL)
          r->next = q;
     else
         r->next = p;
         
     return start;
}
	
Data *
mergeSort::mergesort(Data *p)
{
   Data *q;
   if(p != NULL)
   {
        if(p->next != NULL)
        {
            q = divide(p);
            p = mergesort(p);
            q = mergesort(q);
            p = merge(p, q);
        }
   }
   return p;
}

Data *
mergeSort::mergesort()
{
    mergeSort(top);  
}

int 
main()
{

    int number = -1;
    Data *list;
    mergeSort sort;
    
    while(number != 0)
    {
           cout << "Enter a number: " << endl;
           cin >> number;   
           if(number != 0)
           { 
             sort.addToQueue(number); 
           } 
    } 
    
    cout << "Results: " << endl;
    sort.print();
    
    sort.mergesort();
    
    cout << "Sorted results: " << endl;
    sort.print();

    system("pause");
}
/**********************************************
* A program that stores data to a linked list *
* Tests if linked list is full or empty       *
* Adds or removes data from linked list       *
* Author: Kimberlie Davis                     *
* Version: 3/26/09                            *
***********************************************/
#include <iostream>

using namespace std;

struct Data
{
   int value;
   Data *next;
};
class Queue
{
 private:
        int fill, remove;
        Data *rear;
        
 public:
        Queue(void);
        void initialize(void);
        int takeAway(void);
        bool full(void);
        bool empty(void);
        void addToQueue(int);
        Data *top;
        int print(void);
        //Data * returnTop(void);
};

/*
* Constructor
* Initializes fill, remove and count
*/
Queue::Queue(void)
{ 
      top = NULL; 
      rear = NULL;
     
}

/*
* method initialize
* Reinitializes the variables
*/
void
Queue::initialize()
{ 
}
/*
* Method takeAway
* Removes items from the list
*/
int
Queue::takeAway()
{
      Data *p;
      char letter;
      initialize();
      if(top == NULL)
        cout << "Queue Overflow" << endl;
      else
      {
            p = top;
            letter = p->value;
            top = p->next;
            delete p;
            if(top == NULL)
                   rear = NULL;
            return letter;
           
      }  
}

/*
* method full
* Returns true if list is full
*/
bool
Queue::full()
{
      if(rear == NULL)
      {
         cout << "Queue Overflow" << endl;
         return true;
      }
      else
         return false; 
}

/*
* method empty
* returns true if list is empty
*/
bool
Queue::empty()
{
      if(top == NULL)
      {
         cout << "Queue Empty" << endl;
         return true;
      }
      else
         return false;           
}

/*
* method addToQueue
* Takes in value from user
* Adds the value to the list
*/
void 
Queue::addToQueue(int number)
{
          Data *p;
          p = new Data;
          p->value = number;
          
          if(top == NULL)
          {
              top = p;
              rear = p;
          }
          
          else
          {
             rear->next = p;
             rear = p;   
          }
          
          p->next = NULL;
                 
}

/*Data *
Queue::returnTop()
{
    return top;              
}*/
int
Queue::print()
{
      Data *p;
      p = new Data;
      p = top;
     // Data *p;
      //p = new Data;
      int num;

      
      while(top != NULL)
      {
         num = p->value;
         top = p->next;
         p = p->next; 
              
         cout <<  num << endl;     
      }        
}
1
Contributor
1
Reply
3
Views
8 Years
Discussion Span
Last Post by christiangirl
0

I got it partly figured out, top was being set to NULL in the print() method. So I made it so top won't be NULL anymore.

But I'm still having a problem, I think because when I addToQueue in merge its adding to what is already there.

This question has already been answered. 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.