GameDev.netIntroduction to Pointers, Structures and Linked-Lists Part 6

Introduction to Pointers, Structures and Linked-Lists Part 6
Well, it has been a while since my last article. I have been holidaying away from regular Internet access. I had hoped to cover multiple indirection for advanced pointer use, but my advanced topic kept crashing my computer. I was looking for a more straightforward way of completing the task, but I decided to just give you a quick look at recursive functions. "What is a recursive function?" I hear you ask. Well, 'recursion' is a term that is used to mean that a function will call itself until it finally reaches a conclusion and unwinds itself all the way back through its calls. I do not think that words are going to describe this as well as examples. int RecursiveFunction (int i); int RecursiveFunction (int i) { printf("%d\n", i); if (i) RecursiveFunction(i-1); printf("%d\n", i); return i; } This is a reasonable example of simple recursion. The first line is the prototype of the function, and this must be placed up the top of your code. Effectively, all of your prototypes should be up the top of your code or in your header files. The output of a call to this function if called "RecursiveFunction(5);" would be "5,4,3,2,1,0,0,1,2,3,4,5" where the numbers are on alternating lines. Recursive functions can be used for finding out if a sentence is a palindrome or in our case for sorting a Linked List. Here is a look at a palindrome checker. int IsPalindrome (char str[80]); int IsPalindrome (char str[80]) { // Return true if this is the last letter if (strlen(str) == 1) return -1; printf("%c with %c\n", str[0], str[strlen(str)-1]); char buf[80]; // Return false if the alternate letters are not the same if (str[0] != str[strlen(str)-1]) return (0); // Sending the substring strcpy(buf, &str[1]); buf[strlen(buf)-1] = NULL; // Return the result of the Recursive call return IsPalindrome(buf); } Obviously this function needs "string.h" to be included with it, but you can get the idea. This function recursively calls itself back to the return statement. This is so that the true (-1) or false (0) value that is sent back makes its way to the calling function so that we can determine if the sentence is a palindrome or not. For example, if we fed the sentence "SATAN OSCILLATE MY METALLIC SONATAS" without the spaces into our function like this: ```
if (IsPalindrome("SATANOSCILLATEMYMETALLICSONATAS"))
printf("Is a Palindrome");
```
Then you get the output telling you that it is a Palindrome. There is a printing function in the IsPalindrome function so that you may track the progress of the recursions. Hopefully after studying this for a little while you will get the hang of recursive functions. Now, I did promise to rewrite the sorting function to be recursive. I actually wrote two versions that are recursive. The original function was long and at times very difficult to understand. Before I give you what I promised, here is the structure that we are dealing with, a doubly linked list: typedef struct strAddress *AddressPtr_t; typedef struct strAddress { char Name[31]; char Address[181]; char PhoneNo[13]; AddressPtr_t Next,Prev; } Address_t; The first rewrite of the original function was longer, but it was broken into three functions that were all required to do the original work. It was only slightly more readable: AddressPtr_t SortByNameInit(AddressPtr_t Cur) { //Get to the beginning again while (Cur && Cur->Prev) Cur = Cur->Prev; return Cur; } AddressPtr_t SortByNameRecursion(AddressPtr_t Cur) { // The middle loop iteration pointer AddressPtr_t Iter = Cur; // A boolean value for remembering whether the list was modified or not bool Changed = false; // Start the Sort // If there exists an element, Iter is the next element if (Iter) Iter->Next; // Reset the Modified switch for this iteration while (Iter) { // If it belongs before Cur, put it there if (strcmp(Cur->Name,Iter->Name) > 0) { // Remove Iter from its location if (Iter->Next) Iter->Next->Prev = Iter->Prev; Iter->Prev->Next = Iter->Next; // Insert Iter before Cur Iter->Prev = Cur->Prev; if (Iter->Prev) Iter->Prev->Next = Iter; Iter->Next = Cur; Cur->Prev = Iter; // Set modified flag Changed = true; } // Next iteration Iter = Iter->Next; } if (!Cur || !Changed) { // Basically keeps iterating until there are no changes and Cur = NULL return SortByNameInit(Cur); } else if (Changed) { Cur = SortByNameInit(Cur); return SortByNameRecursion(Cur); } else { // Go to the next value if (Cur) return SortByNameRecursion(Cur->Next); } return SortByNameInit(Cur); } AddressPtr_t SortByName(AddressPtr_t Cur) { Cur = SortByNameInit(Cur); Cur = SortByNameRecursion(Cur); return Cur; } SortByName() is called just the same is it was before, but the execution of it is slightly different. The highlighted lines above show where the recursive functions are. I tend to call a function recursively mostly on or after a return operator. The second rewrite of the sort function is broken up into four different functions. It is the most easily read of the group. It does not require deep tabbing to keep code blocks apart: AddressPtr_t Shuffle(AddressPtr_t Cur) { // This is the reverse of what was happening in SortByNameRec // because we are now sorting backwards AddressPtr_t Iter, Last = Cur; Iter = Last->Prev; // Search backwards down the list for the spot to put Cur while (Iter && (strcmp(Iter->Name, Cur->Name) > 0)) { // Keep hurtling backwards down the list Iter = Last->Prev; if (Iter) Last = Iter; } // If we aren't at the beginning of the list if (Iter) { // Instert Cur this far back down the list if (Cur->Prev) Cur->Prev->Next = Cur->Next; if (Cur->Next) Cur->Next->Prev = Cur->Prev; if (Iter->Next) Iter->Next->Prev = Cur; Iter->Next = Cur; Cur->Next = Iter->Next; Cur->Prev = Iter; } else if (Last) { // If this is the beginning of the list, // insert Cur at the beginning if (Cur->Prev) Cur->Prev->Next = Cur->Next; if (Cur->Next) Cur->Next->Prev = Cur->Prev; Last->Prev = Cur; Cur->Next = Last; Cur->Prev = NULL; } return Cur; } AddressPtr_t SortByNameRec(AddressPtr_t Cur) { AddressPtr_t Iter = NULL; // Ensure that we actually have a Cur before defining an Iter if (Cur) Iter = Cur->Next; // Ensure that we have an Iter before attempting a comparison if (Iter) // See if there needs to be a swap if (Iter && (strcmp(Cur->Name, Iter->Name) > 0)) { // Shuffle moves Iter down the list Shuffle(Iter); // Start sorting list from here onwards return SortByNameRec(Cur); } else // Sort from Next Item onwards return SortByNameRec(Cur->Next); return Cur; } AddressPtr_t SortByNameInit(AddressPtr_t Cur) { // return to the head of the list while (Cur && Cur->Prev) Cur = Cur->Prev; return Cur; } AddressPtr_t SortByName(AddressPtr_t Cur) { // Reorder the list to its head Cur = SortByNameInit(Cur); // Do the recursion sort Cur = SortByNameRec(Cur); // Reorder the list to its head Cur = SortByNameInit(Cur); return (Cur); } This is longer than the original, but I think you will agree with me that it is MUCH easier to read. I have decided to include the original function to underline my point. The original function is located at the end of this file before my conclusion. Anyway, the functionality of the above code is slightly different from the original. It is more efficient. Instead of just moving Iter behind Cur if they need to be swapped, the Shuffle function basically drops Iter down the list as far as it will go and therefore keeping the list behind Cur sorted. It also makes for pleasant reading. It is much healthier on the eyes. int SortByName(AddressPtr_t Cur) { // The middle loop iteration pointer AddressPtr_t Iter = Cur; // A boolean value for remembering whether the list was modified or not bool Changed; //Get to the beginning again while (Cur && Cur->Prev) Cur = Cur->Prev; // Start the Sort // If there exists an element, Iter is the next element if (Iter) Iter->Next; // Basically keeps iterating until there are no changes and Cur = NULL while (Changed || Cur) { // Reset the Modified switch for this iteration Changed = false; while (Iter) { // If it belongs before Cur, put it there if (strcmp(Cur->Name,Iter->Name) > 0) { // Remove Iter from its location if (Iter->Next) Iter->Next->Prev = Iter->Prev; Iter->Prev->Next = Iter->Next; // Insert Iter before Cur Iter->Prev = Cur->Prev; if (Iter->Prev) Iter->Prev->Next = Iter; Iter->Next = Cur; Cur->Prev = Iter; // Set modified flag Changed = true; } // Next iteration Iter = Iter->Next; } if (Changed) { // Start sorting from the beginning again //Get to the beginning again while (Cur && Cur->Prev) Cur = Cur->Prev; // If an element exists, Iter is the next element if (Cur) Iter = Cur->Next; } else { // Go to the next value if (Cur) Cur = Cur->Next; if (Cur) Iter = Cur->Next; } } return 0; } I hope that has helped you grasp this wonderful topic of recursion. It really does have a lot of fun possibilities and can be quite useful. I don't think that I have particularly demonstrated to you the more useful implementations, but I will leave it for you to play with. Now is the part where I try and coax you into joining me in my next article on Member Functions. I am sure that you don't need this by now, because you are so desperately dependent on my articles that it is for your own good to read them... Look forward to addicting you more Cheers, Chris Bennett (a.k.a. Dwarfsoft) Author: Chris Bennett aka Dwarfsoft
© 1999-2011 Gamedev.net. All rights reserved. |