jianwei.sun
BAN USERwhat do you mean by boundary elements.
- jianwei.sun October 28, 2008I agree, it's nlogn,
But if sort is nlogn, and the problem of "how to find if there exists a pair of number in an array such that the sum of them is K" is also nlogn.
Then the solution is still nlogn, which is asked.
The first function MoveNode is a helper function, it will be called by algorithm SortMerge().
bool MoveNode
(SimpleListElementStructure<int>** sourceList,
SimpleListElementStructure<int>** destinationList)
{
/*This is a variant on Push(). Instead of creating a new node
and pushing it onto the given list, MoveNode() takes two lists,
removes the front node from the second list and pushes
it onto the front of the first. This turns out to be a handy
utility function to have for several later problems.*/
if(*sourceList==0)
{
return false; // do nothing.
}
SimpleListElementStructure<int>* firstNode=*sourceList;
*sourceList=(*sourceList)->next;
firstNode->next=*destinationList;
*destinationList=firstNode;
return true;
};
SimpleListElementStructure<int>* SortMerge
(SimpleListElementStructure<int>* firstList,
SimpleListElementStructure<int>* secondList)
{
SimpleListElementStructure<int> dummyNode;
dummyNode.next=0;
SimpleListElementStructure<int>* tail=&dummyNode;
while(firstList!=0 && secondList!=0)
{
if(firstList->datum<secondList->datum)
{
MoveNode( &firstList,&(tail->next));
tail=tail->next;
}
else
{
MoveNode( &secondList,&(tail->next));
tail=tail->next;
}
}
if(firstList==0)
{
while(secondList!=0)
{
MoveNode( &secondList,&(tail->next));
tail=tail->next;
}
}
else if(secondList==0)
{
while(firstList!=0)
{
MoveNode(&firstList,&(tail->next));
tail=tail->next;
}
}
return dummyNode.next;
};
The difference between "new" and "malloc" is that, if you use new, you are not only allocate the memory for the object, but also call the constructor for the object.
For example
Class Simple
{
public:
Simple()
{//constructor code.
}
}
If you "new" the class, the constructor code will be called, if you use malloc, only memory for the class will be allocated, no constructor code will be called.
The question doesn't seem to complete, can somebody amend it a little bit?
- jianwei.sun October 31, 2008