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!
