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