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 = : 5Here 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;