Published with kind permission of DevCentral
Copyright © 1998 Interface Technologies, Inc. All Rights Reserved.

Dynamic data structures allocate blocks of memory from the heap as required and link those blocks together into some kind of structure that uses pointers. When a structure no longer needs a block, it will return it to the heap for reuse.

The following two examples show the correspondence between Pascal code and C code using the heap. The first example allocates an integer block, fills it, writes it, and disposes of it. In Pascal, it looks like this:

 program samp;  
 var    
     p:^integer;  
 begin    
     new(p);    
     p^:=10;    
     writeln(p^);    
     dispose(p);  
 end.

The same code in C looks like this:

 #include <stdio.h> 
 
 void main()  
 {    
     int *p; 
     p = (int *) malloc (sizeof(int));    
     *p = 10;    
     printf("%d\n",*p);    
     free(p);  
 } 

This code is really useful only for demonstrating the process of allocating, deallocating, and using a block in C. The malloc line does the same thing as the new statement does in Pascal. It allocates a block of memory of the size specified---in this case, sizeof(int) bytes. The sizeof command in C returns the size, in bytes, of any type. The code could just as easily have said malloc(4), since sizeof(int) equals four bytes on most UNIX machines. Using sizeof, however, makes the code much more portable and readable.

The malloc function returns a pointer to the allocated block. This pointer is generic. Using the pointer without typecasting generally produces a type warning from the compiler. The (int *) typecast converts the generic pointer returned by malloc into a pointer to an integer, which is what p expects. The dispose statement in Pascal is replaced by free in C. It returns the specified block to the heap for reuse.

The second example illustrates the same functions as the previous example, but it uses a record instead of an integer. In Pascal, the code looks like this:

 program samp;  
 type    
     rec=record      
         i:integer;      
         f:real;      
         c:char;    
     end;  
 var    
     p:^rec;  
 begin    
     new(p);    
     p^.i:=10;    
     p^.f:=3.14;    
     p^.c='a';   
     writeln(p^.i,p^.f,p^.c);    
     dispose(p);  
 end.

In C, the code looks like this:

 #include <stdio.h> 
 
 struct rec 
 { 
     int i; 
     float f; 
     char c; 
 }; 
 
 void main() 
 { 
     struct rec *p; 
      p=(struct rec *) malloc (sizeof(struct rec)); 
     (*p).i=10; 
     (*p).f=3.14; 
     (*p).c='a'; 
     printf("%d %f %c\n",(*p).i,(*p).f,(*p).c); 
     free(p); 
 }

Note the following line:

 (*p).i=10; 

Many wonder why the following doesn't work:

 *p.i=10; 

The answer has to do with the precedence of operators in C. The result of the calculation 5+3*4 is 17, not 32, because the * operator has higher precedence than + in most computer languages. In C, the . operator has higher precedence than *, so parentheses force the proper precedence. See tutorial 14 for more information on precedence.

Most people tire of typing (*p).i all the time, so C provides a shorthand notation. The following two statements are exactly equivalent, but the second is easier to type:

 (*p).i=10;  
 p->i=10;

You will see the second more often than the first when referencing records pointed to by a pointer.

A more complex example of dynamic data structures is a simple stack library, one that uses a dynamic list and includes functions to init, clear, push, and pop. The library's header file looks like this:

 /* Stack Library -  
    This library offers the minimal stack operations
    for a stack of integers (easily changeable) */ 
  
 typedef int stack_data; 
 
 extern void stack_init();  
 /* Initializes this library. 
     Call first before calling anything. */ 
  
 extern void stack_clear();  
 /* Clears the stack of all entries. */ 
  
 extern int stack_empty();  
 /* Returns 1 if the stack is empty, 0 otherwise. */ 
  
 extern void stack_push(stack_data d);  
 /* Pushes the value d onto the stack. */ 
  
 extern stack_data stack_pop();  
 /* Returns the top element of the stack,
    and removes that element. Returns garbage if
    the stack is empty. */

The library's code file follows:

 #include "stack.h"  
 #include <stdio.h> 
  
 /* Stack Library - This library offers the minimal
    stack operations  for a stack of integers */ 
  
 struct stack_rec  
 {    
     stack_data data;    
     struct stack_rec *next;  
 }; 
  
 struct stack_rec *top=NULL; 
  
 void stack_init()  
 /* Initializes this library. Call before
      calling anything else. */  
 {    
     top=NULL;  
 } 
  
 void stack_clear()  
 /* Clears the stack of all entries. */  
 {    
     stack_data x; 
   
     while (!stack_empty())      
     x=stack_pop();  
 } 
  
 int stack_empty()  
 /* Returns 1 if the stack is empty, 0 otherwise. */  
 {    
     if (top==NULL)      
         return(1);   
     else      
         return(0);  
 }  
 
 void stack_push(stack_data d)  
 /* Pushes the value d onto the stack. */  
 {   
     struct stack_rec *temp; 
     temp=(struct stack_rec *)
         malloc(sizeof(struct stack_rec)); 
     temp->data=d;    
     temp->next=top;    
     top=temp;  
 } 
 
 stack_data stack_pop()  
 /* Returns the top element of the stack, and
    removes that element. Returns garbage if the
    stack is empty. */   
 {    
     struct stack_rec *temp;    
     stack_data d=0; 
      if (top!=NULL)    
     {      
         d=top->data;      
         temp=top;      
         top=top->next;      
         free(temp);    
     }    
     return(d);  
 }

Note how this library practices information hiding: Someone who can see only the header file cannot tell if the stack is implemented with arrays, pointers, files, or in some other way. Note also that C uses NULL in place of the Pascal nil. NULL is defined in stdio.h, so you will almost always have to include stdio.h when you use pointers.

C Errors to Avoid

• Forgetting to include parentheses when you reference a record, as in (*p).i above.
• Failing to dispose of any block you allocate. For example, you should not say top=NULL in the stack function, because that action orphans blocks that need to be disposed.
• Forgetting to include stdio.h with any pointer operations so that you have access to NULL.

Exercises

• Add a dup, a count, and an add function to the stack library to duplicate the top element of the stack, return a count of the number of elements in the stack, and add the top two elements in the stack.
• Build a driver program and a makefile, and compile the stack library with the driver to make sure it works.