Sunday, February 21, 2010

Chapter 2: Basic Abstract Data Types. Problem 2.3.b

//program to merge n sorted lists
//in this program, n = 10.

#include <iostream>
using namespace std;

struct NODE
{
int nValue;
NODE* next;
};

void CreateLists(NODE** lists, int nLists);
NODE* CreateSortedList(int nStart, int nInc, int nTotal);
void PrintLists( NODE** list, int nLists);
void PrintList( NODE* list);
NODE* MergeAllSortedLists(NODE** lists, int nLists);
bool MoreThanOneListRemaining(NODE** lists, int nLists);

void main()
{
//array of sorted lists
NODE* lists[10] = { 0 }; //Note: In C, there is no easy way to initialize all elements (not considering memset) - except if you want to initialize
//all elements to 0 - which is what I want in this case.

CreateLists(lists,sizeof(lists)/sizeof(lists[0]));
PrintLists(lists,sizeof(lists)/sizeof(lists[0]));
NODE* newList = MergeAllSortedLists(lists, sizeof(lists)/sizeof(lists[0]));
PrintList(newList);
}

void CreateLists(NODE** lists, int nLists) //Pass array by reference
{
if( !lists )
return;

int nStart = 0;
int nInc = 2;
for( int n = 0; n < nLists; n++ )
{
lists[n] = CreateSortedList(nStart,nInc,10);
//Just to add some variety to the lists created
nStart += 10;
if( nInc == 2 )
nInc = 1;
else
nInc = 2;
}
}

//Creates a sorted list of nTotal elements.
//First element assigned a value nStart.
//Second element = nStart+nInc
//and so on...
NODE* CreateSortedList(int nStart, int nInc, int nTotal)
{
NODE* head = NULL;
NODE* curr = NULL;
for( int i = 0; i < nTotal; i++ )
{
NODE* newNode = new NODE;
newNode->nValue = nStart;
newNode->next = NULL;
if( !head )
{
//first node
head = newNode;
curr = head;
}
else
{
//second node onwards
curr->next = newNode;
curr = curr->next;
}
nStart += nInc;
}
return head;
}

void PrintLists( NODE** list, int nLists)
{
for( int n = 0; n < nLists; n++ )
{
PrintList(list[n]);
}
}

void PrintList( NODE* list)
{
if( !list )
{
cout << "Empty list." << endl;
return;
}
cout << "List is --> " << endl;
for( NODE* curr = list; curr != NULL; curr = curr->next )
cout << curr->nValue << " ";
cout << endl << "<-- End of list." << endl;
}

//the main function that does the sorting
NODE* MergeAllSortedLists(NODE** lists, int nLists)
{
if( !lists )
return NULL;

NODE* newList = NULL;
NODE* nodeToTake = NULL;
NODE* currNode = NULL;
int nListToInc = 0; //This points to the list from a node is taken

//Continue until we have just one list left
while( MoreThanOneListRemaining(lists,nLists) )
{
nListToInc = -1;
for( int n = 0; n < nLists; n++ )
{
//find the node that we want to append to our new list
if( lists[n] )
{
if( nodeToTake )
{
if( nodeToTake->nValue > (lists[n])->nValue )
{
nodeToTake = lists[n];
nListToInc = n;
}
}
else
{
nodeToTake = lists[n];
nListToInc = n;
}
}
}
if( nListToInc == -1 )
{
cout << "Error in logic." << endl;
return NULL;
}
else
{
lists[nListToInc] = (lists[nListToInc])->next;
}
//we have our node that we want to append to the new list
if( !newList )
{
newList = nodeToTake;
currNode = newList;
}
else
{
currNode->next = nodeToTake;
currNode = currNode->next;
}
nodeToTake = NULL;
}

//At this point, we'll have one list left
NODE* lastList = NULL;
for( int n = 0; n < nLists; n++ )
{
if( lists[n] )
{
lastList = lists[n];
break;
}
}
if( lastList )
currNode->next = lastList;

return newList;
}

//returns true if valid elements in array > 1.
//return false if valid elements in array <= 1.
bool MoreThanOneListRemaining(NODE** lists, int nLists)
{
if( !lists )
return false;
int nCount = 0;
for( int n = 0; n < nLists; n++ )
{
if( lists[n] )
nCount++;
}
return (nCount > 1 ? true : false);
}



No comments:

Post a Comment