05-09-2012, 04:27 PM
C Programming: Data Structures and Algorithms
C Programming.pdf (Size: 787.82 KB / Downloads: 43)
Basics
We will begin this section by reviewing C skills that are particularly important to the
study of data structures and algorithms, including typedefs, pointers and arrays, and
dynamic memory allocation. Next we will define a set of utilities that will be useful in
implementing the data structures that we will discuss in the remainder of the course. By
the end of this section you will be ready to complete your first project.
Objectives
At the conclusion of this section, and with the successful completion of your first project,
you will have demonstrated the ability to:
• Use typedef to declare the basic types used to represent a data structure;
• Use dynamic memory allocation to create the components of a data structure; and
• Implement core utilities to serve as the foundation of a software development
project.
Typedef
In most C projects, the typedef statement is used to create equivalence names for other C
types, particularly for structures and pointers, but potentially for any type. Using typedef
equivalence names is a good way to hide implementation details. It also makes your code
more readable, and improves the overall portability of your product.
Typedef and Portability
Typedef is frequently used to improve code portability. To cite a simple example,
suppose you had a need to declare a data structure that was guaranteed to occupy the
same amount of memory on every platform. If this structure had integer fields you might
be tempted to declare them to be either short or long, believing that these types would
always translate to two- or four-byte integers, respectively. Unfortunately ANSI C makes
no such guarantee. Specifically, if you declare a field to be type long, it will break when
you try to port your code to an Alpha running Digital UNIX, where an int is four bytes,
and a long is eight bytes. To avoid this problem you can use typedef in conjunction with
conditional compilation directives to declare integer equivalence types
Typedef and Structures
To create a structure variable suitable for describing a street address, and to pass the
variable to a routine that could print it, you might use code like that shown in Figure 1-1,
which explicitly declares all structure components using the struct keyword. Normally,
however, you would declare equivalence names for the address structure using typedef,
and then declare structure variables and parameters using the equivalence names, as
shown in Figure 1-2. Note that, in this example, one typedef statement was used to create
two equivalence names: ADDRESS_t, which is equivalent to struct address_s, and
ADDRESS_p_t, which is equivalent to struct address_s*. This is a very common
technique in modern C usage.
Typedef and Functions
Recall that the type of a function is a combination of the function’s return type, and the
number and type of each of the function’s parameters. Typedef can be used to declare an
equivalence name for a function type, and, subsequently, the equivalence name can be
used to declare a prototype for a function of that type. One use of this is to reduce
repetition when declaring many functions of the same type. For example, if you are
implementing a standard sort algorithm, you will need to define a prototype for a
compare function; specifically, a function used to determine whether one object is greater
than another.