Jump to content
  • Advertisement
Sign in to follow this  
toogreat4u

Merge Sort Function

This topic is 3455 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to create a merge sort function that merges two linked lists in numerical order. This is something that I am doing for educational purposes in order to fully understand how linked lists work and how to build them correctly. My problem is I can not figure out how to get the linked list to recgonize when an element has been inserted and now the list needs to step to the next element. I understand looking at this code that I have several places where memory leaks in areas and I plan on cleaning that portion up later. Here is my code.
/* Write a function called merge_lists that takes two call-by-reference arguments that are pointer variables that point to the heads
 * of linked lists of values of type int.
 * The two linked lists are assumed to be sorted so that the number at the head is the smallest number, the number in the next node
 * is the next smallest, and so forth.
 * The function returns a pointer to the head of a new linked list that contains all of the nodes in the original two lists.
 * The nodes in this longer list are also sorted from smallest to largest values.
 * Note that your function will neither create nor destroy any nodes.
 * When the function call ends, the two pointer variable arguments should have the value NULL
 */

#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* link;
};

typedef Node* NodePtr;

void head_insert(NodePtr& head, int the_number);
NodePtr merge_list(NodePtr& list, NodePtr& list2);
void printList(NodePtr head);

int main()
{
	int numbers;
	NodePtr list = NULL;
	NodePtr list2 = NULL;
	for(int i = 1; i <= 4; i++)
	{
		cout << "Enter in element number " << i << ":\n";
		cin >> numbers;
		head_insert(list, numbers);
	}
	printList(list);
	for(int i = 1; i <= 4; i++)
	{
		cout << "Enter in element number " << i << ":\n";
		cin >> numbers;
		head_insert(list2, numbers);
	}
	printList(list2);
	NodePtr merged = NULL;
	merged = merge_list(list, list2);
	//printList(merged);
}

void printList(NodePtr head)
{
	NodePtr here;

	cout << "List contains:\n";
	for(here = head; here != NULL; here = here->link)
		cout << (here->data) << ' ';
	cout << endl;
}

void head_insert(NodePtr& head, int the_number)
{
	if(head == NULL || the_number <= head->data)
	{
		NodePtr temp_ptr;
		temp_ptr = new Node;

		temp_ptr->data = the_number;

		temp_ptr->link = head;
	
		head = temp_ptr;
		return;
	}
	else
		head_insert(head->link, the_number);
}

NodePtr merge_list(NodePtr& list, NodePtr& list2)
{
	NodePtr temp_ptr;
	temp_ptr = new Node;

	while(list != NULL || list2 != NULL)
	{
		if(list->data < list2->data)
		{
			temp_ptr->data = list->data;
			temp_ptr->link = new Node;
			temp_ptr = temp_ptr->link;
			list = list->link;
		}
		else 
		{
			temp_ptr->data = list2->data;
			temp_ptr->link = new Node;
			temp_ptr = temp_ptr->link;
			list2 = list2->link;
		}
		if(list == NULL)
		{
			temp_ptr->data = list2->data;
			temp_ptr->link = new Node;
			temp_ptr = temp_ptr->link;
			list2 = list2->link;
		}
		else if(list2 == NULL)
		{
			temp_ptr->data = list->data;
			temp_ptr->link = new Node;
			temp_ptr = temp_ptr->link;
			list = list->link;
		}
	}
	return temp_ptr;
}

I think I am very close to what needs to be done I just can't figure out why when I use temp_ptr->link = new Node, followed by temp_ptr = temp_ptr->link is not moving the linked list to the next node and placing data in it. Thanks for any help.

Share this post


Link to post
Share on other sites
Advertisement
Original post by toogreat4u


NodePtr merge_list(NodePtr& list, NodePtr& list2)
{
NodePtr temp_ptr;
// You're supposed to merge two existings lists, why are you allocating
// a new node here? Shouldn't be doing that.
temp_ptr = new Node;

while(list != NULL || list2 != NULL)
{
// Suppose list == NULL && list2 != NULL, then the following
// line crashes.
if(list->data < list2->data)
{
temp_ptr->data = list->data;
// Shouldn't be allocating here either!
temp_ptr->link = new Node;
temp_ptr = temp_ptr->link;
list = list->link;
}
else
{
temp_ptr->data = list2->data;
// Shouldn't be allocating here either!
temp_ptr->link = new Node;
temp_ptr = temp_ptr->link;
list2 = list2->link;
}
if(list == NULL)
{
temp_ptr->data = list2->data;
// Shouldn't be allocating here either!
temp_ptr->link = new Node;
temp_ptr = temp_ptr->link;
list2 = list2->link;
}
else if(list2 == NULL)
{
temp_ptr->data = list->data;
// Shouldn't be allocating here either!
temp_ptr->link = new Node;
temp_ptr = temp_ptr->link;
list = list->link;
}
}
return temp_ptr;
}

[/quote]

How about the following version for the merge: (Lost the references to pointers, not necessary here)

NodePtr merge_list(NodePtr list, NodePtr list2)
{
// Assume there doesn't exist a node that points to either list or list2,
// i.e. list && list2 must both be heads of a list. Otherwise, we'll be
// merging this structure into a tree.

NodePtr newList = NULL; // We'll use this to point to the last node as we go.
NodePtr newHead = NULL; // Points to the head of the new list.

while(list || list2) // While still got an element in either list.
{
NodePtr next = NULL;

// If both lists nonempty and list1 smaller than list2, or if
// only list1 is nonempty and list2 is empty, then pick list1.
if ((list && list2 && list->data <= list2->data) || (list && !list2))
{
next = list;
list = list->link;
}
else // Otherwise, we pick element from list2.
{
next = list2;
list2 = list2->link;
}

if (!newList) // If we're adding the first element, save the head.
{
newList = next;
newHead = next;
}
else
{
newList->link = next;
newList = newList->link;
}
}

// End the list.
newList->link = NULL;

return newHead;
}



Just wrote it from the top of my head, so it goes with the usual disclaimers.

Share this post


Link to post
Share on other sites
Thank you very much, that helps clear it up quite a bit. I do have a question however, how come you return newHead instead of newList? I see that newHead = next, and next is a pointer value that is constantly changed based on the if statements so I am guessing because next is changed from list to list2 that the newHead references all the places where next has been manipulated.

Share this post


Link to post
Share on other sites
Quote:
Original post by toogreat4u
Thank you very much, that helps clear it up quite a bit. I do have a question however, how come you return newHead instead of newList?


I return newHead since that will end up pointing to the *first* element of the merged list, which is exactly what is wanted. If you returned a pointer to any other element of the merged list, you couldn't "see" the whole merged list as you can't travel back the nodes of a singly-linked list. Note also, that I dropped the references to pointers from the function definition, which is deliberate to avoid unexpected things from happening in the caller's end.

Quote:

I see that newHead = next, and next is a pointer value that is constantly changed based on the if statements so I am guessing because next is changed from list to list2 that the newHead references all the places where next has been manipulated.


I think you're mixing 'pointers' and 'references to pointers' here. I didn't deliberately use references to pointers to make the function simpler to reason about. The roles of newHead and newList are as follows:

newHead is updated exactly once during the first iteration of the loop. It will be set to point to the first node of the merged list. During subsequent iterations, the value of newHead will never change. Therefore this makes sure that when the function returns, it will return a pointer to the first node of the merged list, which is what we want.

newList will, at the beginning of each iteration, point to the last element of the so-far merged list. After we've picked the next minimal node N to extract from list1 or list2, we will append it to the end of the merged list. To do this, we make N the new last node by setting newLink->link to point to N, and updating newList to point to the new end node N.

After the loop terminates, we set newList->link = NULL to make sure that there are no rogue pointers there (in fact, there can never be due to list1 and list2 being complete intact lists), but I just wanted to do it to make more explicit what's going on.

Note that this merge procedure works in-place and destroys the two original lists we were working with. The old list nodes will now be part of the new merged list.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!