Structures and Unions

December 24th, 2009 by Kevin | No Comments | Filed in C Programming

Structure

A structure in a C program is a user defined datatype which can be used to group together elements with different types but sharing a logical bonding between themselves.

struct Employee_
{
   int id;
   char* fname;
   char* lname;
   unsigned short age;
   char* address;
};

Here structure name is Employee_ with id, fname, lname, age, address as it’s members. A user defined datatype can be used as any existing datatype in a C program. So to declare a variable of this structure:

struct Employee_ emp;

Structures are heavily used in many of the projects using C. There is an even more convenient and better way which is used to declare and define structure data types and variables. This is by using the “typedef”.

typedef struct Employee_
{
   int id;
   char* fname;
   char* lname;
   unsigned char age;
   char* address;
}Employee;

Now we can declare a variable of this user defined datatype as:

Employee emp;

which looks very natural to declaring variables with built in data types. Note that we can also have arrays of user defined data types. To access the members of the structure, we use the dot or “.” operator. So to access the id, name, etc of the Employee structure

   emp.id = 1;
   emp.fname = "kevin";
   emp.lname = "rodrigues";
   printf("Name: %s %s\n", emp.fname, emp.lname);

We can also declare a pointer to a structure. This is quite useful when passing a structure into a function. Good programming practice suggests that we pass into a function only those arguments that we require. Sometimes the list of arguments can be quite large. So we can group them together in a structure and pass that structure instead. However a structure is passed call by value which will create a copy of it. Instead, we can just pass a pointer to that structure thus saving significant overhead and increasing program efficiency. To access the members of a structure using a pointer, we use the “->” or arrow operator.

void printRecord(Employee *pEmp)
{
   printf("Name: %s %s\n", pEmp->fname, pEmp->lname);
   printf("Age: %d\n", pEmp->age);
   printf("Address: %s\n", pEmp->address);
}

Self referential structures

One of the most important usage of structures in creating a self referential structure for use in data structures like link lists and trees. While it is illegal to use a structure declaration within itself, we can use a pointer to a structure as it’s own member.

typedef struct ListNode_   /* node of a link list */
{
   void* data;
   ListNode* pNext;
}ListNode;

typedef TreeNode_   /* node of a binary tree */
{
   void* data;
   TreeNode* pLeft;
   TreeNode* pRight;
}TreeNode;

Union

A union is also a user defined data type with logical members together. What makes it different from a structure, it that it can only hold value for one member at a time. The size of a union is set to the size of the largest member that it can hold. Suppose I want to print either an error code or an error message. Using a union as below

typedef union PrintVar_
{
   int ivar;
   float fvar;
   char* chrvar;
}PrintVar;

The members of a union can be accesssed similar to those of structures using a dot operator or with a pointer to a union using a “->” operator

   Printvar prnVar;
   Printvar *pVar;

   pVar = &prnVar;

   prnVar.ivar = 10;
   printf("ivar = %d\n", prnVar.ivar);
   prnVar.fvar = 3.14;
   printf("fvar = %d\n", pVar->fvar);

   pVar->chrvar = "hello";
   printf("chrvar = %s\n", prnVar.chrvar);

It is important to remember that at a time only one member of a union can be accessed because they share the same memory. So the last member which was assigned a value represents the current value present in the union variable. I have not been able to read projects using unions for their functionality.

Do you have any good examples of using unions which you could share with us?
 

Related Posts:

Tags: ,

Recursion

December 22nd, 2009 by Kevin | 2 Comments | Filed in C Programming, programming

Recursion is a technique in computer programming which allows us to compute the solution of a problem by defining the problem into smaller and smaller instances of itself. The concept of recursion is quite confusing to the new programmer. Let us try to understand this by the typical example of finding the factorial of a number.

A factorial of a number can be found by applying the following equation:

n! = n(n-1)(n-2)...1
eg: 4! = 4 x 3 x 2 x 1 = 24

A recursive C program to calculate the factorial of a number is shown below:

int fact(int n)
{
   if(n < 0)
   {
      return 0;
   }
   else if(n == 0 || n == 1)
   {
      return 1;
   }
   else
   {
      return n * fact(n - 1);    /* recursively calling fact() with a smaller instance */
   }
}

This program works as following:

fact(4) = 4 * fact(3)                                             /* winding phase */
                  fact(3) = 3 * fact(2)
                                fact(2) = 2 * fact(1)
                                              fact(1) = 1         /* terminating condition */
                                fact(2) = (2)*(1)                 /* unwinding phase */
                  fact(3) = (3)*(2)
fact(4) = (4)*(6)
24                                                                /* recursion complete */

As can be seen, during the winding phase, the function fact() is called recursively and each functions gets a stack frame on the stack. Every recursive function should have a terminating condition else it will continue recursively till the stack runs out of space and we get a stack overflow. After the terminating condition is the unwinding phase where the results of each recursive call are computed by the results from the previous recursive call and finally we get the solution.

It should be noted that a problem can be solved without using recursion as well but applying recursion makes the solution more simple and elegant in most cases. However, the disadvantage of recursion is the increased cost of maintaining the stack frame for each recursive function call. In the above example, we can see that for each recursive call during the winding phase, the function frame has to be maintained in the stack so that during the unwinding phase, we can use the values to compute the solution for that instance and pass it on further down.

A solution to this problem is to reduced the number of stack frames used by using tail recursion. A tail recursive function is one which is the last executable statement of a recursive function and whose return value will not be used in an expression. This is better explained by writing the above program to calculate a factorial using a tail recursive function.

int facttail(int n, int a)
{
   if(n < 0)
   {
      return 0;
   }
   else if(n == 0)
   {
      return 1;
   }
   else if(n == 1)
   {
      return a;
   }
   else
   {
      facttail(n - 1, n * a);
   }
}

The program works as following:

facttail(4, 1) = facttail(3, 4)                                               /* winding phase */
                     facttail(3, 4) = facttail(2, 12)
                                      facttail(2, 12) = facttail(1, 24)
                                                        facttail(1, 24) = 24  /* terminating condition */

Observe that there is no unwinding phase necessary if we use a tail recursive function. How this helps is that many compilers can optimize tail recursion. When the compiler notices tail recursion, it will overwrite the function frame rather than maintain a frame for each recursive function. This is because there is no need to maintain a frame for each function call as there is no unwinding phase and the return of the function does not matter because it is not included in an expression and it is also the last executable statement of the function.

 

Related Posts:

Tags: , ,

Pointer to a function

December 20th, 2009 by Kevin | 1 Comment | Filed in C Programming

In a C program, we can have a pointer to a function which gives us a pointer to a specific block of executable code. The code to be executed is determined at the run time depending on the address assigned to the function pointer. This helps us create programs which can emulate the polymorphic capabilities of any object oriented programming language.

A function pointer is declared as

return-type (* function-pointer-name)(type arg1, type arg2. ...);

Following code excerpt shows an example how a function pointer can be used to design polymorphism in C.

struct MediaObject_
{
   ...........
   void (*play)(int ); /* declaration of a function pointer */
}MediaObject;

playAudio(int sound)
{
   ............
}

playVideo(int sound)
{
   ............
}

void main()
{
   MediaObject mediaObj;
   MediaType mediaType = getMediaType();

   if(mediaType == AUDIO)
   {
       mediaObj.play = playAudio; /* function pointer assignment */
   }
   else if(mediaType == VIDEO)
   {
      mediaObj.play = playVideo; /* function pointer assignment */
   }

   /* play function pointer can be used for audio or video*/
   mediaObj.play(100);
}

Care should be taken to provide some value to your function pointer before it is actually used. Since a function pointer is a variable, you will not get any compilation errors if you do not initialize it but your program will give an ugly crash at runtime.

 

Related Posts:

Tags: , ,

« Older Entries