• 09/30/04 10:44 AM
    Sign in to follow this  
    Followers 0

    Introduction to Pointers, Structures and Linked-Lists Part 6

    General and Gameplay Programming

    Myopic Rhino

    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
    Contact: dwarfsoft@hotmail.com
    April 11, 2001
    (C) Copyright Chris Bennett , 2001

    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    There are no reviews to display.