3. Common Structures

3. Common Structures (Section 3.1)

Let us stick with structural definitions for the moment, and briefly survey the main kinds of data types, from a structural point of view.

3.1. Atomic Data Types

First of all, there are atomic data types. These are data types that are defined without imposing any structure on their values. Boolean, our first example, is an atomic type. So are characters, as these are typically defined by enumerating all the possible values that exist on a given computer.

3.2. Structured Data Types

The opposite of atomic is structured. A structured data type has a definition that imposes structure upon its values. As we saw above, fractions normally are a structured data type.

In many structured data types, there is an internal structural relationship, or organization, that holds between the components. For example, if we think of an array as a structured type, with each position in the array being a component, then there is a structural relationship of `followed by': we say that component N is followed by component N+1.

Structural Relationships

Not all structured data types have this sort of internal structural relationship. Fractions are structured, but their is no internal relationship between the sign, numerator, and denominator. But many structured data types do have an internal structural relationship, and these can be classified according to the properties of this relationship.

Linear Structure:

The most common organization for components is a linear structure. A structure is linear if it has these 2 properties:

Property P1

Each element is `followed by' at most one other element.

Property P2

No two elements are `followed by' the same element.

An array is an example of a linearly structured data type. We generally write a linearly structured data type like this: A->B->C->D (this is one value with 4 parts).

• counter example 1 (violates P1): A points to B and C B<-A->C
• counter example 2 (violates P2): A and B both point to C A->C<-B

Dropping Constraint P1: If we drop the first constraint and keep the second we get a tree structure or hierarchy: no two elements are followed by the same element. This is a very common structure too, and extremely useful. We'll study it in considerable detail.

Counter example 1 is a tree, but counter example 2 is not.

More complex example:

A is followed by B C D, B by E F, C by G. We are not allowed to add any more arcs that point to any of these nodes (except possibly A - see cyclic structures below).

Dropping both P1 and P2:

If we drop both constraints, we get a graph. In a graph, there are no constraints on the relations we can define.

Cyclic Structures: All the examples we've seen are acyclic. This means that there is no sequence of arrows that leads back to where it started. Linear structures are usually acyclic, but cyclic ones are not uncommon.

Example of cyclic linear structure: A B C D A

Trees are virtually always acyclic.

Graphs are often cyclic, although the special properties of acyclic graphs make them an important topic of study.

Example: Add an edge from G to D, and from E to A.