| |
/*
File: mergeSort.cpp
Author: Nuno Alves (nca@csa.bu.edu)
Purpose: To code a program that will mergesort a linked list of random
numbers.
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
//Node structure. This is the base of this program. This Node structure has
//a pointer to the next node (*next) and an integer value (data). If there
//is no next node, then the value of next is NULL.
struct Node {
Node(int d) : data(d), next(0) { }
Node *next;
int data;
};
// Makes a linked-list of a specified number of nodes, initializing the
// data member of each to a random number and then returns a pointer to
// the beginning of the list.
Node* makeList(int size)
{
//Declaration of variables that will help to implement the linked
//list
Node *pHead; //is a pointer head node
Node *pNode; //is a pointer to a node
Node *pPrev; //is a pointer to the previous node (of the current)
// Add items to linked list
for (int i = 0; i < size; i++)
{
// initialize a node with a random number from 1 to 100
pNode = new Node(1+rand()%100);
//defining the head object equal to the first member of the
//node
if (i==0)
pHead = pNode;
else
{
//setting up the next pointer of the previous
//Node to the current Node
pPrev->next = pNode;
}
//setting up the next pointer on current Node to NULL
pNode->next = NULL;
//creating a reference to the current Node (so we can
//later on update the next Node pointer
pPrev = pNode;
} //end of for Loop
return (pHead); //returns a pointer to the head node
}
// Takes a pointer to the first node of a linked list and displays the
// data values in the linked from beginning to end.
void display(Node *pHead)
{
//pointer to a current node
Node *pNode;
//if there is no objects in the list, then it is empty
if (pHead==NULL)
cout<<"The list is empty!\n";
//if there are nodes in the list, then display them
else
{
// Now display each item in list
for (pNode = pHead; pNode->next!=NULL; pNode = pNode->next)
cout<<"\n"<<pNode->data;
//display the last element of the linked list
cout<<"\n"<<pNode->data;
}
}
// Takes a pointer to the first node in a linked list and deallocates
// all of the nodes in the list.
void kill(Node *pHead)
{
//declaring two temporary variables that will store the contents of
//the nodes
Node *pNode_tmp;
Node *pNode;
//if pHead exists, then it will delete the elements of the linked list
if (pHead!=NULL)
{
//it will cycle through all linked list deleting the current member and
//setting the current pointer (pNode) to the next member so it can be
//deleted in the next cyle of the for loop.
for (pNode = pHead ; pNode->next!=NULL ; pNode = pNode_tmp)
{
pNode_tmp = pNode->next;
// cout<<pNode->data<<" was deleted \n";
delete pNode;
}
}
}
// Takes two pointers to the first nodes of sorted linked lists and
// rearranges the links to merge them into a single sorted linked list,
// returning a pointer to the beginning of the new list.
Node* merge(Node *a, Node *b)
{
//the way I implemented this function is very intereseting. First I
//add both nodes pointers into a single linked list (I join both
//lists). And the I simply applied the mergesort algorithm that the
//book so well explains.
Node *ptmp;
Node *sortedlist;
//the current min value is the first value of the list
int value=a->data;
//both nodes point to the same place, the begining of the list.
//I will not touch sortedlist, so that in the end I can simply
//send the result of ptmp and a operations. sortedlist will always
//point to the begining of the list which will be sorted as the
//program starts flowing
ptmp = a;
sortedlist=a;
//process of joining both lists, into a single list begining at a
while(ptmp->next!=NULL)
{
ptmp=ptmp->next;
}
ptmp->next=b;
//'a' can now be treated like an array as it is a continous
//linked list that needs to be sorted. 'a' is the head of the linked
//list. It is very easy now.
//mergesort algorithm, slightly adapted from the book. It does the same
//thing, but instead of using arrays, it uses linked lists.
while(a->next!=NULL)
{
value=a->data;
ptmp=a;
while(ptmp->next!=NULL)
{
ptmp=ptmp->next;
if (ptmp->data<value)
{
value=ptmp->data;
ptmp->data=a->data;
a->data=value;
}
}
a=a->next;
}
return(sortedlist);
}
// Takes a pointer to the first node of a linked list and breaks the
// list into two pieces, then recursively sorts each piece and merges the
// two sorted sublists using the merge function.
Node* mergeSort(Node *pHead)
{
Node *tmpNode;
Node *pNode;
//if there is an object
if (pHead->next!=NULL)
{
int i=0,size=0;
//calculating the size of the linkedlist
for(tmpNode=pHead;(tmpNode->next)!=NULL;tmpNode=tmpNode->next)
size++;
//puts tmpNode back in the origin of the linked list
tmpNode=pHead;
//beginning to split the list in two... first half will be with
//pHead
for(i=0;i<size/2;i++)
tmpNode=tmpNode->next;
//second half will be with pNode
pNode=tmpNode->next;
//breaking the chain here... so we can have two lists
tmpNode->next=NULL;
//merges the lists after recusively mergesorting them
pHead=mergeSort(pHead);
pNode = mergeSort(pNode);
pHead=merge(pHead,pNode);
}
return(pHead);
}
void main()
{
int size=0;
//some error checking against evil users
while (size<=0){
cout << "Enter list size: ";
cin >> size;
}
Node* p = makeList(size);
cout<<"\nThe original list is:";
display(p);
p=mergeSort(p);
cout <<"\n\nThe sorted list is:";
display(p);
cout<<"\n\n";
kill(p);
} |