Structures, Unions, and Enumerations
A
structure is a collection of values (members), possibly of different types. A
union is similar to a structure, except that its members share the same
storage; as a result, a union can store one member at a time, but not all
members simultaneously. An enumeration is an integer type whose values are
named by the programmer.
Structure Variables
The
only data structure we've covered so far is the array. Arrays have two important
properties. First, all elements of an array have the same type. Second, to
select an array element, we specify its position (as an integer subscript).
The
properties of a structure are quite different from those of an array. The elements of
a structure (its members, in C parlance) aren't required to have the
same type. Furthermore, the members of a structure have names; to select a
particular member, we specify its name, not its position.
Structures
may sound familiar, since most programming languages provide a similar feature.
In some languages, structures are called records, and members arc known
as fields.
Declaring Structure Variables
When we
need to store a collection of related data items, a structure is a logical
choice. For example, suppose that we need to keep track of parts in a
warehouse. The information that we'll need to store for each part might include
a part number (an integer), a part name (a string of characters), and the
number of parts on hand (an integer). To create variables that can store all
three items of data, we might use a declaration such as the following:
struct {
int number;
char name[NAME_LEN+1]; int
on_hand; } parti, part2;
Each structure variable has three members: number (the part number),
name (the name of the part), and on_hand (the quantity on hand). Notice that
this declaration has the same form as other variable declarations in C: struct
{ ... } specifies a type, while parti and part2 are variables of that type.
The
members of a structure are stored in memory in the order in which they're
declared. In order to show what the parti variable looks like in memory, let's
assume that (I) parti is located at address 2000. (2) integers occupy four
bytes, (3) NAME_LEN has the
value 25, and (4) there are no gaps between the
members.
Operations
on Structures
Since
the most common array operation is subscripting selecting an element by
position it's not surprising that the most common operation on a structure is
selecting one of its members. Structure members are accessed by name, though,
not by position.
To access
a member within a structure, we write the name of the structure first. then a
period, then the name of the member. For example, the following statements will
display the values of parti's members:
printf("Part
number: %d\n", part1.number);
printf("Part name: %s\n”, part1.name);
printf("Quantity
on hand: %d\n", part1.on_hand);
The
members of a structure are lvalues, so they can appear on the left side of an
assignment or as the operand in an increment or decrement expression.
Structure Types
Although
the previous section showed how to declare structure variables, it
failed to discuss an important issue: naming structure types. Suppose
that a program needs to declare several structure variables with identical
members. If
all the variables can be declared at one time, there's no problem. But if we
need to declare the variables at different points in the program, then life
becomes more difficult. If we write
struct
{
int
number;
char name[NAME_LEN+1]; int on_hand; } part1;
in one place and
struct
{
int
number;
char name[NAME_LEN+1]; int on_hand; } part2;
in
another, we'll quickly run into problems. Repeating the structure information
will bloat the program. Changing the program later will be risky, since we
can't easily guarantee that the declarations will remain consistent.
But
those aren't the biggest problems. According to the rules of C. part1 and part2
don't have compatible types. As a result, part1 can't be assigned to part2. and
vice versa. Also, since we don't have a name for the type of part1 or part2, we
can't use them as arguments in function calls.
To
avoid these difficulties, we need to be able to define a name that represents a
type of structure, not a particular structure variable. As it turns
out. C provides two ways to name structures: we can either declare a
"structure tag" or use typedef to define a type name.
Declaring a Structure Tag
A structure tag is a name used to identify a
particular kind of structure. The following example declares a structure tag
named part:
struct part {
int number;
char name[NAME_LEN+1];
int on_hand;
};
Notice the semicolon that follows
the right brace it must be present to terminate the declaration.
Defining a Structure Type
As an
alternative to declaring a structure tag, we can use typedef to define a
genuine type name. For example, we could define a type named Part in the following
way:
typedef
struct { int number;char name[NAME_LEN+1]; int on_hand; } Part;;
Note that
the name of the type. Part, must come at the end, not after the word struct.
We can use Part in
the same way as the built-in types. For example, we might use it to declare
variables:
Part part1, part2;
Since
Part is a typedef name, we're not allowed to write struct Part. All Part
variables, regardless of where they're declared, are compatible.
When it
comes time to name a structure, we can usually choose either to declare a
structure tag or to use typedef. However, as we'll see later, declaring a
structure tag is mandatory when the structure is to be used in a linked list.
Arrays
of Structures
One
of the most common combinations of arrays and structures is an array whose
elements are structures. An array of this kind can serve as a simple database.
For example, the following array of part structures is capable of storing
information about 100 parts:
struct
part inventory[100];
Unions
A union, like a structure, consists of one or more
members, possibly of different types. However, the compiler allocates only enough
space for the largest of the members, which overlay each other within this
space. As a result, assigning a new value to one member alters the values of
the other members as well.
To
illustrate the basic properties of unions, let's declare a union variable, u.
with two members:
union { int i; double d;} u;
Notice how the declaration of a
union closely resembles a structure declaration:
struct { int i ; double d; } s;
In fact, the structure s and the union u differ in just one
way: the members of s are stored at different addresses in memory, while
the members of u are stored at the same address. Here's what s and u
will look like in memory (assuming that int values require four bytes and
double values lake eight bytes).
Enumerations
In many
programs, we'll need variables that have only a small set of meaningful values.
A Boolean variable, for example, should have only two possible values:
"true" and "false." A variable that stores the suit of a
playing card should have only four potential values: "clubs,"
"diamonds," "hearts," and "spades." The obvious
way to deal with such a variable is to declare it as an integer and have a set
of codes that represent the possible values of the variable:
int s; /* s will store a suit */
s = 2; /* 2 represents
"hearts" */
Although
this technique works, it leaves much to be desired. Someone reading the program
can't tell that s has only four possible values, and the significance of 2
isn't immediately apparent.
Dynamic
Storage Allocation
C's
data structures are normally fixed in size. For example, the number of elements
in an array is fixed once the program has been compiled. (In C99, the length of
a variable-length array is determined at run lime, but it remains fixed for the
rest of the array's lifetime.) Fixed-size data structures can be a problem,
since we're forced to choose their sizes when writing a program: we can't
change the sizes without modifying the program and compiling it again.
Consider
the inventory program which allows the
user to add parts to a database. The database is stored in an array of length
100. To enlarge the capacity of the database, we can increase the size of the
array and recompile the program. But no matter how large we make the array,
there's always the possibility that it will fill up. Fortunately, all is not
lost. C supports dynamic storage allocation: the ability to allocate
storage during program execution. Using dynamic storage allocation, we can
design data structures that grow (and shrink) as needed.
Although
it's available for all types of data, dynamic storage allocation is used most
often for strings, arrays, and structures. Dynamically allocated structures are
of particular interest, since we can link them together to form lists, trees,
and other data structures.
No comments:
Post a Comment