Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
0Likes
Dislike

Introduction to Pointers, Structures and Linked-Lists Part 6

By Chris Bennett aka Dwarfsoft | Published Sep 30 2004 04:44 AM in General Programming

cur iter return function list cur->prev addressptr_t iter->next cur->next
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



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.



<span class="codekeyword">int</span> RecursiveFunction (<span class="codekeyword">int</span> i);

<span class="codekeyword">int</span> RecursiveFunction (<span class="codekeyword">int</span> i)

{

  printf("%d\n", i);

  <span class="codekeyword">if</span> (i) RecursiveFunction(i-1);

  printf("%d\n", i);

  <span class="codekeyword">return</span> 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.



<span class="codekeyword">int</span> IsPalindrome (<span class="codekeyword">char</span> str[80]);

<span class="codekeyword">int</span> IsPalindrome (<span class="codekeyword">char</span> str[80])

{

  <span class="codecomment">// Return true if this is the last letter</span>

  <span class="codekeyword">if</span> (strlen(str) == 1) <span class="codekeyword">return</span> -1;



  printf("%c with %c\n", str[0], str[strlen(str)-1]);



  <span class="codekeyword">char</span> buf[80];

  <span class="codecomment">// Return false if the alternate letters are not the same</span>

  <span class="codekeyword">if</span> (str[0] != str[strlen(str)-1]) <span class="codekeyword">return</span> (0);



  <span class="codecomment">// Sending the substring</span>

  strcpy(buf, &str[1]);

  buf[strlen(buf)-1] = NULL;



  <span class="codecomment">// Return the result of the Recursive call</span>

  <span class="codekeyword">return</span> 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:



<span class="codekeyword">if</span> (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:



<span class="codekeyword">typedef struct</span> strAddress *AddressPtr_t;

<span class="codekeyword">typedef struct</span> strAddress

{

  <span class="codekeyword">char</span> Name[31];

  <span class="codekeyword">char</span> Address[181];

  <span class="codekeyword">char</span> 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)

{

  <span class="codecomment">//Get to the beginning again</span>

  <span class="codekeyword">while</span> (Cur && Cur->Prev)

    Cur = Cur->Prev;

  <span class="codekeyword">return</span> Cur;

}



AddressPtr_t SortByNameRecursion(AddressPtr_t Cur)

{

  <span class="codecomment">// The middle loop iteration pointer</span>

  AddressPtr_t Iter = Cur;



  <span class="codecomment">// A boolean value for remembering whether the list was modified or not</span>

  <span class="codekeyword">bool</span> Changed = <span class="codekeyword">false</span>;



  <span class="codecomment">// Start the Sort

  // If there exists an element, Iter is the next element</span>

  <span class="codekeyword">if</span> (Iter) Iter->Next;

  <span class="codecomment">// Reset the Modified switch for this iteration</span>

  <span class="codekeyword">while</span> (Iter)

  {

    <span class="codecomment">// If it belongs before Cur, put it there</span>

    <span class="codekeyword">if</span> (strcmp(Cur->Name,Iter->Name) > 0)

    {

      <span class="codecomment">// Remove Iter from its location</span>

      <span class="codekeyword">if</span> (Iter->Next) Iter->Next->Prev = Iter->Prev;

      Iter->Prev->Next = Iter->Next;

      

      <span class="codecomment">// Insert Iter before Cur</span>

      Iter->Prev = Cur->Prev;

      <span class="codekeyword">if</span> (Iter->Prev) Iter->Prev->Next = Iter;

      Iter->Next = Cur;

      Cur->Prev = Iter;

      

      <span class="codecomment">// Set modified flag</span>

      Changed = <span class="codekeyword">true</span>;

    }

    <span class="codecomment">// Next iteration</span>

    Iter = Iter->Next;

  }

  <span class="codekeyword">if</span> (!Cur || !Changed)

  {

    <span class="codecomment">// Basically keeps iterating until there are no changes and Cur = NULL</span>

    <span class="codekeyword">return </span>SortByNameInit(Cur);

  } <span class="codekeyword">else if </span>(Changed)

  {

    Cur = SortByNameInit(Cur);          

    <span class="codekeyword">return</span> SortByNameRecursion(Cur);

  } <span class="codekeyword">else</span>

  {

    <span class="codecomment">// Go to the next value</span>

    <span class="codekeyword">if</span> (Cur) <span class="codekeyword">return</span> SortByNameRecursion(Cur->Next);

  }

  <span class="codekeyword">return</span> SortByNameInit(Cur);

}



AddressPtr_t SortByName(AddressPtr_t Cur)

{

  Cur = SortByNameInit(Cur);

  Cur = SortByNameRecursion(Cur);

  <span class="codekeyword">return</span> 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)

{

  <span class="codecomment">// This is the reverse of what was happening in SortByNameRec

  // because we are now sorting backwards</span>

  AddressPtr_t Iter, Last = Cur;

  Iter = Last->Prev;



  <span class="codecomment">// Search backwards down the list for the spot to put Cur</span>

  <span class="codekeyword">while</span> (Iter && (strcmp(Iter->Name, Cur->Name) > 0))

  {

    <span class="codecomment">// Keep hurtling backwards down the list</span>

    Iter = Last->Prev;

    <span class="codekeyword">if</span> (Iter) Last = Iter;

  }



  <span class="codecomment">// If we aren't at the beginning of the list</span>

  if (Iter)

  {

    <span class="codecomment">// Instert Cur this far back down the list</span>

    <span class="codekeyword">if</span> (Cur->Prev) Cur->Prev->Next = Cur->Next;

    <span class="codekeyword">if</span> (Cur->Next) Cur->Next->Prev = Cur->Prev;

    <span class="codekeyword">if</span> (Iter->Next) Iter->Next->Prev = Cur;

    Iter->Next = Cur;

    Cur->Next = Iter->Next;

    Cur->Prev = Iter;

  } <span class="codekeyword">else if</span> (Last)

  {

    <span class="codecomment">// If this is the beginning of the list,

    // insert Cur at the beginning</span>

    <span class="codekeyword">if</span> (Cur->Prev) Cur->Prev->Next = Cur->Next;

    <span class="codekeyword">if</span> (Cur->Next) Cur->Next->Prev = Cur->Prev;

    

    Last->Prev = Cur;

    Cur->Next = Last;

    Cur->Prev = NULL;

  }

  <span class="codekeyword">return</span> Cur;

}





AddressPtr_t SortByNameRec(AddressPtr_t Cur)

{

  AddressPtr_t Iter = NULL;

  <span class="codecomment">// Ensure that we actually have a Cur before defining an Iter</span>

  <span class="codekeyword">if</span> (Cur) Iter = Cur->Next;

  

  <span class="codecomment">// Ensure that we have an Iter before attempting a comparison</span>

  <span class="codekeyword">if</span> (Iter)

    <span class="codecomment">// See if there needs to be a swap</span>

    <span class="codekeyword">if</span> (Iter && (strcmp(Cur->Name, Iter->Name) > 0))

    {

      <span class="codecomment">// Shuffle moves Iter down the list</span>

      Shuffle(Iter);

      <span class="codecomment">// Start sorting list from here onwards</span>

      <span class="codekeyword">return</span> SortByNameRec(Cur);

    } <span class="codekeyword">else</span>

      <span class="codecomment">// Sort from Next Item onwards</span>

      <span class="codekeyword">return</span> SortByNameRec(Cur->Next);

  <span class="codekeyword">return</span> Cur;

}



AddressPtr_t SortByNameInit(AddressPtr_t Cur)

{

  <span class="codecomment">// return to the head of the list</span>

  <span class="codekeyword">while</span> (Cur && Cur->Prev)

    Cur = Cur->Prev;



  <span class="codekeyword">return</span> Cur;

}



AddressPtr_t SortByName(AddressPtr_t Cur)

{

  <span class="codecomment">// Reorder the list to its head</span>

  Cur = SortByNameInit(Cur);



  <span class="codecomment">// Do the recursion sort</span>

  Cur = SortByNameRec(Cur);



  <span class="codecomment">// Reorder the list to its head</span>

  Cur = SortByNameInit(Cur);

  <span class="codekeyword">return</span> (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.



<span class="codekeyword">int</span> SortByName(AddressPtr_t Cur)

{

  <span class="codecomment">// The middle loop iteration pointer</span>

  AddressPtr_t Iter = Cur;



  <span class="codecomment">// A boolean value for remembering whether the list was modified or not</span>

  <span class="codekeyword">bool</span> Changed;



  <span class="codecomment">//Get to the beginning again</span>

  <span class="codekeyword">while</span> (Cur && Cur->Prev)

    Cur = Cur->Prev;



  <span class="codecomment">// Start the Sort

  // If there exists an element, Iter is the next element</span>

  <span class="codekeyword">if</span> (Iter) Iter->Next;



  <span class="codecomment">// Basically keeps iterating until there are no changes and Cur = NULL</span>

  <span class="codekeyword">while</span> (Changed || Cur)

  {

    <span class="codecomment">// Reset the Modified switch for this iteration</span>

    Changed = false;

    <span class="codekeyword">while</span> (Iter)

    {

      <span class="codecomment">// If it belongs before Cur, put it there</span>

      <span class="codekeyword">if</span> (strcmp(Cur->Name,Iter->Name) > 0)

      {

        <span class="codecomment">// Remove Iter from its location</span>

        <span class="codekeyword">if</span> (Iter->Next) Iter->Next->Prev = Iter->Prev;

        Iter->Prev->Next = Iter->Next;



        <span class="codecomment">// Insert Iter before Cur</span>

        Iter->Prev = Cur->Prev;

        <span class="codekeyword">if</span> (Iter->Prev) Iter->Prev->Next = Iter;

        Iter->Next = Cur;

        Cur->Prev = Iter;



        <span class="codecomment">// Set modified flag</span>

        Changed = true;

      }

      <span class="codecomment">// Next iteration</span>

      Iter = Iter->Next;

    }

    <span class="codekeyword">if</span> (Changed)

    {

      <span class="codecomment">// Start sorting from the beginning again

      //Get to the beginning again</span>

      <span class="codekeyword">while</span> (Cur && Cur->Prev)

        Cur = Cur->Prev;

      <span class="codecomment">// If an element exists, Iter is the next element</span>

      <span class="codekeyword">if</span> (Cur) Iter = Cur->Next;

    } <span class="codekeyword">else</span>

    {

      <span class="codecomment">// Go to the next value</span>

      <span class="codekeyword">if</span> (Cur) Cur = Cur->Next;

      <span class="codekeyword">if</span> (Cur) Iter = Cur->Next;

    }

  }

  <span class="codekeyword">return</span> 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
© Copyright Chris Bennett , 2001








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS