Programming Forums > Application Development > C++

jason999x · Feb 17th, 2008, 9:26 PM

how does one do a recursive insertion sort on a linked list, particularly with these given parameters:

InsertSortR(std::string ItemName, ListItemNode* &node);

Also, how does one do a recursive traverse of a linked list, AND something else at the same time, such as add up values in that linked list?

Sane · Feb 17th, 2008, 10:19 PM

I'll answer your second question. Maybe that will help you think up the answer to your first question.

(Toggle Plain Text)

function sumlist(linkedListNode node), returns an integer:
    if node is null:
        return 0
    else:
        Look at the current node here
        
        Once we're done looking, continue traversing and summing as we go
        return node.value + sumlist(node.next)

jason999x · Feb 19th, 2008, 5:11 PM

thanks but they do seem to be separate things... I don't think I ever clearly explained myself on the whole traverse thing... it's confusing because I can't figure out where the variable to be added onto is in this massive scheme of classes, i/o, and pointers. But InsertSortR should be more clear, I just need to know how to implement it!

Wizard1988 · Feb 19th, 2008, 8:21 PM

Because you are traversing the list recursively it is acting somewhat like a stack.
Once you take a look at a node you return its value + the value of the next, this keeps on going until you hit the last node when you return the value of all the nodes added up.

Hopefully this clears it up.

Sane · Feb 19th, 2008, 10:47 PM

Quote:

Originally Posted by jason999x

But InsertSortR should be more clear, I just need to know how to implement it!

InsertSort will be very similar to the psuedocode I posted. Simply compare the value of the current node against the one passed through the function. If it should be inserted before the current node, then create a new node, link it to the next, and return the new node. In the even that the current node is not modified, it should return itself. The calling function should reassign the next node to the return value of the recursion. All done. Want that in psuedocode, or will that ruin the fun?

Feb 17th, 2008, 9:26 PM	#1
jason999x Newbie Join Date: Feb 2008 Posts: 6 Rep Power: 0	Linked Lists: Insertion Sort, RECURSIVELY how does one do a recursive insertion sort on a linked list, particularly with these given parameters: InsertSortR(std::string ItemName, ListItemNode* &node); Also, how does one do a recursive traverse of a linked list, AND something else at the same time, such as add up values in that linked list?

Feb 17th, 2008, 10:19 PM	#2
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Linked Lists: Insertion Sort, RECURSIVELY I'll answer your second question. Maybe that will help you think up the answer to your first question. (Toggle Plain Text) function sumlist(linkedListNode node), returns an integer: if node is null: return 0 else: Look at the current node here Once we're done looking, continue traversing and summing as we go return node.value + sumlist(node.next) function sumlist(linkedListNode node), returns an integer: if node is null: return 0 else: Look at the current node here Once we're done looking, continue traversing and summing as we go return node.value + sumlist(node.next) __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Feb 19th, 2008, 5:11 PM	#3
jason999x Newbie Join Date: Feb 2008 Posts: 6 Rep Power: 0	Re: Linked Lists: Insertion Sort, RECURSIVELY thanks but they do seem to be separate things... I don't think I ever clearly explained myself on the whole traverse thing... it's confusing because I can't figure out where the variable to be added onto is in this massive scheme of classes, i/o, and pointers. But InsertSortR should be more clear, I just need to know how to implement it!

Feb 19th, 2008, 8:21 PM	#4
Wizard1988 Professional Programmer Join Date: Oct 2005 Location: Chitown Posts: 417 Rep Power: 4	Re: Linked Lists: Insertion Sort, RECURSIVELY Because you are traversing the list recursively it is acting somewhat like a stack. Once you take a look at a node you return its value + the value of the next, this keeps on going until you hit the last node when you return the value of all the nodes added up. Hopefully this clears it up. __________________ JG-Webdesign

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pointers and Linked Lists	BstrucT	C	8	Feb 11th, 2008 2:33 AM
Linked Lists	Eric the Red	C++	6	Mar 19th, 2006 12:47 AM
Linked list insertion at the tail	elford	Java	9	Jan 7th, 2006 9:04 AM
Changing Array structures to Linked Lists?	kalulu	C	4	Nov 29th, 2005 6:33 AM
Circularly Linked Lists	Silme	C	15	Nov 4th, 2005 7:58 PM

Programming Forums > Application Development > C++

Linked Lists: Insertion Sort, RECURSIVELY