2.1: Bricks

Now that the context in which problems will be solved and programs written has been presented, it is time to start studying seriously the effect of choice of data structure on the problem solution. Before we explore some simple examples, the two basic data structures?/FONT>records and arrays?/FONT>must be understood, along with the two basic operations on them?/FONT>selection and traversal.

A record is a data structure made up of a fixed number of information items, not necessarily of the same type. In C records are of the type structure. In the text the two words record and structure will be used interchangeably. An array is a data structure made up of a fixed number of information items in sequence; all items are required to be of the same type. Records and arrays have boundless applications. Records are useful when the items are to be referred to by name, while arrays are useful when the items are to be referred to by their positions in the sequence. The fundamental importance of the array was recognized quite early in the development of programming languages; the structure, or record, has only recently been incorporated in many languages. Pointers are variables that

1. Refer or point to memory locations for variables

2. Point to data structures, or

3. Link the components of a data structure together

Records and arrays are the bricks out of which more complex data structures are built, and pointers are the mortar holding them together.

Just as a builder asks for bricks and mortar, programmers in a high-level language ask for data structures to help build their solutions. A data structure is specified by declaring a variable name to be of a specific type. Some languages restrict the choice of type to individual variables or to arrays of type int, float, or char. C includes these, plus other types such as records, pointers, and unions. However, it does not have type boolean, which is found in other languages. C does allow the user to give new names to types.

Records and arrays allow related items of information to be treated as a group. The individual pieces of information in a record (structure) are called members in C. In most languages they are termed fields, but this word has a special meaning in C. Since that meaning is never utilized in this text, both member and field will be used for the elements of a record. In the case of arrays the individual pieces of information are called entries. The merit of records and arrays lies in the fact that they allow random access to any one of their fields or entries. Random access is accomplished by direct location of the desired piece of information, without regard to sequence. This means that access to an item may be accomplished in a fixed amount of time, no matter what item was previously accessed. This contrasts with sequential access, where the time required to access an item depends on the number of items stored between that item and the last item accessed, since each of the intermediate items must be accessed. With random access, any member of a record or any entry of an array may be accessed in a fixed amount of time, typically a few millionths or billionths of a second.

Both records and arrays provide the means to treat related items as a unit, and both generalize the idea of variables containing one item to variables containing many items. Records will be discussed next, then arrays.

2.1.1 Structures or Records in C

2.1.2 Arrays in C

2.1.3 Two-Dimensional Arrays

2.1.4 Representation of Records in Arrays

2.1.5 Variable-Length Records

2.1.6 The Use of Unions in C

2.1.7 Address Calculation without Access