Previous Table of Contents Next


3.7.6. Linked Data Structures

One extremely common use of C’s structure types is building linked data structures, such as trees and linked lists. The basic idea is to declare a member within a structure as a pointer to another instance of the same structure. For example, an elementary linked list node, used (for sake of example) to build lists of integers, might look like

struct list
       {
       int item;
       struct list *next;
        };

and a binary tree node (to be used for storing strings) might look like

struct tree
       {
       char *item;
       struct tree *left, *right;
        };

(Naturally, the type of data actually stored in the node depends on the application; practical node structures might have item members of various types, or multiple data members in addition to the link pointers.) These “recursive” structures are perfectly permissible; the compiler is quite willing to accept the declaration of a structure that contains a pointer to itself. Though the link pointers might look at first as if they point to “the same” structure, they almost always point to other instances of the same structure. Typically, null pointers are used to record links that do not exist (that is, for the ends of linked lists, or for leaf nodes of trees).

Working with linked data structures provides nice examples of the uses of structures, pointers, and dynamic memory allocation. For example, here is a function that inserts a new node at the beginning of a linked list, returning a pointer to the new list:

#include <stdlib.h>
struct list *
listprepend(int n, struct list *oldlist)
{
       struct list *new = malloc(sizeof(struct list));
       if(new != NULL)
               {
               new->item = n;
               new->next = oldlist;
               }
       return new;
}

A few simple calls set up a sample list:

struct list *base = NULL;
base = listprepend(1, base);
base = listprepend(2, base);
base = listprepend(3, base);

Traversing the list is particularly straightforward:

struct list *lp;
for(lp = base; lp != NULL; lp = lp->next)
        printf(“%d\n”, lp->item);

The variable lp steps from node to node, starting at the base of the list and pointing to each node in turn until the null pointer marking the end of the list is found. In this for loop, therefore, the loop control variable is not even an integer (let alone one that steps from, say, 1 to 10). Yet this is a perfectly legal and common loop, illustrating the generality of the for loop while preserving the familiar initialize/test/increment pattern.

Working with binary trees is also straightforward. Here is a function for traversing one, using the classic inorder recursive algorithm:

void treeprint(struct tree *t)
{
       if(t == NULL)
             return;
       treeprint(t->left);
       printf(“%s\n”, t->item);
       treeprint(t->right);
}

The function calls itself recursively, but the first test is whether the node pointer being examined is null, in which case the recursive descent terminates.

3.8. The C Preprocessor

C incorporates a macro preprocessor that operates conceptually before the compiler proper performs full lexical analysis and parsing. The main operations provided by the preprocessor are source file inclusion, macro definition and replacement, and conditional compilation.

All operations performed by the preprocessor are initiated by preprocessor directives, all of which begin with the # character. Preprocessor directives are unique in C in that their source layout matters: The # must be the first nonwhitespace character on the line, the directive cannot be split among several lines unless explicitly continued with the \ character, and no other source code (with the exception of comments) can follow on the same line as a directive.

3.8.1. Source File Inclusion #include)

Lines of the form

#include <name>

and

#include “filename

indicate that externally supplied text is to be inserted into the stream of source code seen by the compiler, just as if the programmer had typed it in manually. The externally supplied text, commonly known as a “header” or “header file,” typically contains declarations and definitions that must be consistent among several source files. Placing the definitions and declarations in a header file and then using #include to copy them, verbatim, into each of the source files ensures that they will, in fact, be consistent (and may also lessen the typing burden).

The #include <name> form indicates that the external text is supplied by the compiler in some standard, central repository. For example, #include <stdio.h> brings in definitions and declarations pertaining to C’s standard I/O library, including the definitions of EOF and the FILE type, external prototype function declarations for functions such as printf and getchar, and so on.

The #include “filename form indicates that the external text is supplied by the programmer, in an additional source file named filename. Typically, the preprocessor searches for the requested file in the current directory or in the same directory as the source file doing the #include, although the exact rules are compiler dependent. The compiler may provide a way for the programmer to request additional directories where header files should be searched for. If no file by the given name is found, the preprocessor finally searches the standard, central repository, as if the #include <…> form had been used.


Previous Table of Contents Next