Hello,
I am having trouble understanding linked lists. I have to make this program that takes input, stores it to a queue, outputs that input, then sorts it using mergesort and outputs it again. It all works except I'm not sure how to call the mergesort classes.

Here is the code:

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

using namespace std;

struct Item
{
    int value;
    Item *next;      
};

class mergeSort:Queue
{
     public:
            Item* divide(Item*);
            Item* merge(Item*, Item*);
            Item* mergesort(Item*);
            Item* mergesort(void);
};
Item *
divide(Item *a)
{
   Item *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;       
}

Item *
merge(Item *p, Item *q)
{
     Item *r, *start;
     
     if(p->value <= q->value)
     {
          r = p;
          p = p->next;            
     }           
     
     else
     {
         r = q;
         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;
}
	
Item *
mergesort(Item *p)
{
   Item *q;
   if(p != NULL)
   {
        if(p->next != NULL)
        {
            q = divide(p);
            p = mergesort(p);
            q = mergesort(q);
            p = merge(p, q);
        }
   }
   
   return p;
}

Item *
mergesort()
{
    //mergesort(sort.top);           
}

int 
main()
{

    int number;
    Queue sort;
    int num;
    Item *list;
    
    while(number != 0)
    {
           cout << "Enter a number: " << endl;
           cin >> number;   
           if(number != 0)
           { 
             sort.addToQueue(number); 
           } 
    } 
    
    cout << "Results: " << endl;
    sort.print();

    system("pause");
}

And:

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

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

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

Thanks!

Recommended Answers

All 5 Replies

You seem to have two classes, Queue and mergeSort. mergeSort is derived from Queue. mergeSort is using a different struct for it's nodes than Queue, which isn't helping. I suggest you use struct Data for the nodes in both classes.
As mergeSort is a Queue, in main() you'll be wanting to use mergeSort as your Queue instead of Queue. So replace "Queue sort;" by "mergeSort sort;".
Now, you should be able to do everything as you are already, but add "sort.mergesort();" to main() where you want to do the sorting.
Of course you'll have to uncomment the only line in mergesort().
Other problems:
The mergeSort methods aren't members of the class. E.g divide() should be mergeSort::divide().
Your naming is poor. mergesort is a verb and should not generally be used to name a class. If you have a queue which provides sorting, it could be a SortableQueue, but not a mergesort.
In Main() you call the Queue "sort". It isn't a "sort", it's a queue, so call it "queue". Just use the verbs for naming methods. I realise, that at this stage you just want to get something running and you don't see names as important, but it really does help. If you can't name it properly, you should ask yourself if you actually know what it's doing.
Inheritance problem - "class mergeSort:Queue" - make that "class mergeSort : public Queue", always do that when deriving classes, unless you have strong reasons not to.
In Main(), "number" is not initialised. That will cause annoying intermittant problems. Think about it.

Hopefully this gets you a bit further. Note that I haven't considered any details of the sorting or queue management code, so good luck with all that.

So about the struct, should I completely take the struct out of mergeSort? I tried doing, and changed everything in mergeSort to Data that and it caused errors. Then I tried making Item derive from Data, and changed everything to being Data items ,that caused some errors still.

Never mind, taking out the struct Item worked.
But now, you said that i need to change Queue sort to mergeSort sort, i did that and then an error was comming up in queue saying that addToQueue can not be accessed.

Never mind, taking out the struct Item worked.
But now, you said that i need to change Queue sort to mergeSort sort, i did that and then an error was comming up in queue saying that addToQueue can not be accessed.

Are you sure you did this:-
"Inheritance problem - "class mergeSort:Queue" - make that "class mergeSort : public Queue", always do that when deriving classes, unless you have strong reasons not to."

oh your right! Sorry, I don't know my problem this week, I keep forgetting stuff like that! I usually remember to do that and put mergeSort:: in front of all of the methods!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.