Structures & Unions - Defining Structures

Structures & Unions

1 Structures

A structure is a customised user-defined data type in C. It is by definition a collection of variables of any type that are referenced under one name, providing a convenient means of keeping related information together.

Some terminology :-

structure definition :- the template used to create structure variables.

structure elements :- the member variables of the structure type

Defining Structures

Syntax : struct tag ;

The keyword struct tells the compiler we are dealing with a structure and must be present whenever we refer to the new type, tag is an identifier which is the name given to the customised 'type'.

A variable of this new type can now be defined as follows for example. Note that the keyword struct has to be used in conjunction with our own name for the structure, tag.

struct tag variable ;

For Example :-

struct RECORD ;

struct RECORD person ;

The compiler will automatically allocate enough storage to accommodate all the elements. To find out how much storage is required one might do the following

size = sizeof ( person ) ;

or

size = sizeof( struct RECORD ) ;

NB : The name of a structure is not the address of the structure as with array names.

Accessing Structure Elements

For example define a complex type structure as follows.

struct complex cplx ; // defined at structure definition time

The elements of the structure are accessed using the dot operator, . , as follows

cplx.real = 10.0 ;

cplx.imag = 20.23 ;

scanf ( '%lf', &cplx.real ) ;

or if we want to access struct RECORD already defined

puts( person.name ) ;

or character by character

person.name[i] = 'a' ;

Thus we treat structure elements exactly as normal variables and view the dot operator as just another appendage like the indirection operator or an array index.

Initialising Structures

Structure elements or fields can be initialised to specific values as follows :-

struct id ;

struct id student = ;

Structure Assignment

The name of a structure variable can be used on its own to reference the complete structure. So instead of having to assign all structure element values separately, a single assignment statement may be used to assign the values of one structure to another structure of the same type.

For Example :-

struct x = , y ;

y = x ; // assigns values of all fields in x to fields in y

Creating more Complex Structures with Structures

Once again emphasising that structures are just like any other type in C we can create arrays of structures, nest structures, pass structures as arguments to functions, etc.

For example we can nest structures as follows creating a structure employee_log that has another structure as one of its members.

struct time ;

struct employee_log employee_

To access the hour field of time in the variable employee_1 just apply the dot operator twice

employee_1.start.hour =

Typically a company will need to keep track of more than one employee so that an array of employee_log would be useful.

struct employee_log workers[100] ;

To access specific employees we simply index using square braces as normal, e.g. workers[10]. To access specific members of this structure we simply apply the dot operator on top of the index.

workers[10].finish.hour = 10 ;

When structures or arrays of structures are not global they must be passed to functions as parameters subject to the usual rules. For example

function1( employee_1 ) ;

implements a call to function1 which might be prototyped as follows

void function1( struct employee_log emp ) ;

Note however that a full local copy of the structure passed is made so if a large structure is involved memory the overhead to simply copy the parameter will be high so we should employ call by reference instead as we will see in the next section.

Passing an array of structures to a function also follows the normal rules but note that in this case as it is impossible to pass an array by value no heavy initialisation penalty is paid - we essentially have call by reference. For example

function2( workers ) ;

passes an array of structures to function2 where the function is prototyped as follows.

function2( struct employee_log staff[ ] ) ;

Structure Pointers

As we have said already we need call by reference calls which are much more efficient than normal call by value calls when passing structures as parameters. This applies even if we do not intend the function to change the structure argument.

A structure pointer is declared in the same way as any pointer for example

struct address ;

struct address person ;

struct address *addr_ptr ;

declares a pointer addr_ptr to data type struct address.

To point to the variable person declared above we simply write

addr_ptr = &person ;

which assigns the address of person to addr_ptr.

To access the elements using a pointer we need a new operator called the arrow operator, ->, which can be used only with structure pointers. For example

puts( addr_ptr -> name ) ;

For Example :- Program using a structure to store time values.

#include <stdio.h>

struct time_var ;

void display ( const struct time_var * ) ; /* note structure pointer and const */

void main()

void display( const struct time_var *t )

Note that even though we are not changing any values in the structure variable we still employ call by reference for speed and efficiency. To clarify this situation the const keyword has been employed.

Dynamic allocation of structures

The memory allocation functions may also be used to allocate memory for user defined types such as structures. All malloc() basically needs to know is how much memory to reserve.

For Example :-

struct coordinate ;

struct coordinate *ptr ;

ptr = (struct coordinate * ) malloc( sizeof ( struct coordinate ) ) ;

2 Bit--Fields

Bit--fields are based directly on structures with the additional feature of allowing the programmer to specify the size of each of the elements in bits to keep storage requirements at a minimum. However bit--field elements are restricted to be of type int ( signed or unsigned ).

For Example :-

struct clock time ;

This time structure requires 17 bits to store the information now so the storage requirement is rounded up to 3 bytes. Using the normal structure format and 32-bit integer elements we would require 12 bytes so we achieve a substantial saving.

Bit--fields can be used instead of the bitwise operators in system level programming, for example to analyse the individual bits of values read from a hardware port we might define the following bit-field.

struct status ;

If we are interested in bit 15 only we need only do the following

struct status ;

There are two further restrictions on the use of bit--fields

Cannot take the address of a bit--field variable

Cannot create an array of bit--field variables

Can you suggest reasons for this ?

3 Unions

A union is data type where the data area is shared by two or more members generally of different type at different times.

For Example :-

union u_tag uval ;

The size of uval will be the size required to store the largest single member, 4 bytes in this case to accommodate the floating point member.

Union members are accessed in the same way as structure members and union pointers are valid.

uval.ival =

uval.cval = 'c' ;

When the union is accessed as a character we are only using the bottom byte of storage, when it is accessed as a short integer the bottom two bytes etc. It is up to the programmer to ensure that the element accessed contains a meaningful value.

A union might be used in conjunction with the bit-field struct status in the previous section to implement binary conversions in C.

For Example :-

union conversion number ;

We can load number with an integer

scanf( '%u', &number.num );

Since the integer and bit--field elements of the union share the same storage if we now access the union as the bit--field variable bits we can interpret the binary representation of num directly.

i.e. if ( uvar.bits.bit15 )

putchar( '1' ) ;

else

putchar('0') ;

if ( uvar.bits.bit0 )

putchar( '1' ) ;

else

putchar('0') ;

Admittedly rather inefficient and inelegant but effective.

4 Enumerations

An enumeration is a user defined data type whose values consist of a set of named integer constants, and are used for the sole purpose of making program code more readable.

Syntax: enum tag [ enum_var ] ;

where tag is the name of the enumeration type, value_list is a list of valid values for the enumeration, and where enum_var is an actual variable of this type.

For Example :-

enum colours shade ;

// values red - 0, green - 1, blue - 2, orange - 3

enum day ;

enum day weekday ;

// values are 1, 2, 3, 21, 22, 23, 24

Variables declared as enumerated types are treated exactly as normal variables in use and are converted to integers in any expressions in which they are used.

For Example :-

int i ;

shade = red ; // assign a value to shade enum variable

i = shade ; // assign value of enum to an int

shade = 3 ; // assign valid int to an enum, treat with care

5 The typedef Keyword

C makes use of the typedef keyword to allow new data type names to be defined. No new type is created, an existing type will now simply be recognised by another name as well. The existing type can be one of the in-built types or a user-defined type.

Syntax : typedef type name ;

where type is any C data type and name is the new name for this type.

For Example :-

typedef int INTEGER ;

INTEGER i ; // can now declare a variable of type 'INTEGER'

typedef double * double_ptr ;

double_ptr ptr ; // no need of * here as it is part of the type

typedef struct coords xycoord ; // xycoord is now a type name in C

xycoord coord_var ;

The use of typedef makes program code easier to read and when used intelligently can facilitate the porting of code to a different platform and the modification of code. For example in a first attempt at a particular program we might decide that floating point variables will fill our needs. At a later date we decide that all floating point variables really should be of type double so we have to change them all. This problem is trivial if we had used a typedef as follows :-

typedef float FLOATING ;

To remedy the situation we modify the user defined type as follows

typedef double FLOATING ;

6 Linked Lists

When we have needed to represent collections of data up until now we have typically used data structures such as arrays whose dimensions were fixed at compile time or which were dynamically allocated as required. These arrays could have been arrays of basic data types, e.g. doubles, or could have been arrays of structures when more complex data needed to be represented.

However this method of representing data, while perfectly adequate in many situations, is limited and can be very inefficient when we are dealing with situations where the data collection has to be modified at run-time.

For example if we are dealing with an ordered list of records and we need to insert a new record, for John say, in the correct position in the list we might have to go through the following steps.

Expand the memory space allocated to the array to take one more record.

2. Determine the correct position in the array at which to insert the element - position 3.

3. Reposition the data so that the appropriate position is left unused.

4. Insert the new element into the list.

Whatever our internal representation of the data, steps 1,2 & 4 will have to be carried out in one form or another. However step 3 can be avoided if we represent the data in an alternate fashion.

If we can represent our data as a chain of inter-connected records as illustrated below where each record has its own memory space and knows which record comes before and after it we have a much more flexible structure.

Now when we want to insert a new record in position we still must allocate the appropriate amount of memory to store it (note in this case it is a discrete block) and we still must figure out which position it belongs in but we no longer have to manipulate the position of the other records in memory. These will now stay exactly where they are but we will have to inform the records before and after the position at which we wish to insert that they will be pointing to a different record.

Using the normal terminology we say we have a list of nodes linked together by pointer links. To insert a new item into the list we break an existing link and create two new links incorporating the new node into the list.

Nodes or Self-Referential Structures

A structure that contains a pointer member that points to a structure of the same type as itself is said to be a self-referential structure. For example :-

struct node ;

This defines a new type, struct node, which has a pointer member, nextnode, which points to a structure of the same type as itself. This node pointer allows this current node to be linked to another and so a list of linked nodes can be built up.

Note that even though the structure is not fully defined when the nextnode field is specified the compiler does not have a problem as all it needs to know is that there is such a type.

The above definition of struct node allows us to build a singly linked list i.e. each node only knows where the node following it is located. A null pointer is used to indicate the end of a linked list structure.

The diagram below illustrates how this node structure would be used to represent our linked list above. Each node contains two fields the actual data and a pointer link to the next node. The final node in the list contains a null pointer link as indicated by the slash in the diagram.

Connecting the Nodes

The basic building block in a linked list is just a C structure so we can initialise it in the same way as any other structure. For example in our above situation to allocate and initialise the first node we might do the following :-

struct node *node_1 ;

node_1 = ( struct node *)malloc( sizeof ( struct node ) ) ;

strcpy( node_1->name, "Alan" ) ;

node_1->nextnode = NULL ;

This block of code initialises this node only and because the nextnode pointer is assigned a null pointer value it designates it as the final (and only) node in the list.

If we want to add on an item to the list we can do the following :-

struct node *node_2 ;

node_2 = ( struct node *)malloc( sizeof ( struct node ) ) ;

strcpy( node_2->name, "Ben" ) ;

node_2->nextnode = NULL ;

node_1->nextnode = node_

Note that it is only the last line of code that adds the item onto the list. The remaining code just allocates storage and initialises a new node as before.

We now have a linked list with two nodes. The node pointer node_1 points to the first element in the list which is normally called the list head. As all the nodes in the list are connected via their link pointer this is in fact a pointer to the complete linked list so we wouldn't need to store node_2, etc. at all. The last node has a null pointer which identifies it as the last node in the linked list and is called the list tail.

Operations on Linked Lists

When working with linked lists we will need to perform a number of operations quite often so it makes sense to build up a library of these at the outset. We will need to be able to insert items into the list, remove items from the list, traverse the list, etc.

We will continue to use our definition of a node except that we will typedef it as follows :-

typedef struct node list_node ;

Note in this case we cannot use the typedef name to declare nextnode as this name is not in existence at that point.

To declare the linked list we simply declare a pointer to one of these structure types.

list_node *ptr_head = NULL ;

Traversing a List

In many list operations we will need to process the information in each node, for example to print the complete information in the list; this is termed traversing a list.

An iterative version of a print_list function might be as follows :-

void print_list( list_node *p_head )

whereas a recursive version might be implemented as follows :-

void print_list( list_node *p_head )

Inserting a Node

There are a variety of ways this function can be implemented - inserting a node in the correct order, at the head, at the tail, by position, etc. For our example we will write a function to insert a new node in the correct order assuming the node has been fully created before being passed to us.

void insert( list_node **p_head, list_node *new )  

if ( prev == NULL ) // head position

else

Removing a Node

We will implement this as a function which finds the node by the name field, unlinks it from the list and returns a pointer to the removed node without freeing its associated memory.

list_node *delete( list_node **p_head, char *name )

if ( prev == NULL ) // removing head position

else

Note the use of double indirection to type list_node in each of the above functions. Can you explain why this is necessary ?

The following main function is a trivial illustration of how to use the above functions in practice.

void main()

What we have discussed in the example above is one of the more general variations of a linked list. Many different implementations can be implemented with slightly different functionality - for example we can implement doubly linked lists, stacks (LIFO) or queues (FIFO) using the same basic building blocks.

Efficiency Considerations

As described previously pointers should be used to implement call-by-reference in passing large user defined data items to functions to reduce the copying overhead involved in call-by-value. If implementing a typical call-by-value situation use of the const keyword can protect us from inadvertent modification of the referenced argument.

Care should be taken not to go overboard in defining large complicated data structures without need and to use them appropriately.

For example when dealing with lists of data of any type a normal array may sometimes be a better choice as a data structure rather than a linked list. The big advantage a linked list has over a linear array is that you can insert or delete items at will without shifting the remaining data.

However the extra overhead involved in setting up the linked list, both the calls to malloc() to allocate each new element and the 'extra' pointer associated with each element, may not justify its selection.

Suppose we need to keep a list of integers. Then most of the storage is taken up with the extra pointer information used solely for maintaining the list ( the pointer to the next element and the pointer to each integer ).

8 Exercises

Write a program which will simulate the action of a digital clock continuously as closely as possible. Use a structure to hold the values of hours, minutes and seconds required. Your program should include a function to display the current time and to update the time appropriately using a delay function/loop to simulate real time reasonably well. Pointers to the clock structure should be passed to the display and update functions rather than using global variables.

Complex numbers are not supported as a distinct type in C but are usually implemented by individual users as user defined structures with a set of functions representing the operations possible on them. Define a data type for complex values and provide functions to support addition, subtraction, multiplication and division of these numbers. Use call by reference to make these functions as efficient as possible and try to make their use as intuitive as you can.

Write a program which will

(a) set up an array of structures which will hold the names, dates of birth, and addresses of a number of employees.

(b) assign values to the structure from the keyboard.

(c) sort the structures into alphabetical order by name using a simple bubble sort algorithm.

(d) print out the contents of a specific array element on demand.

Use a combination of bit--fields and unions in C to print out the bit patterns of any unsigned

integer values input at the keyboard.

BCD (Binary Coded Decimal) codes are commonly used in industrial applications to represent

decimal numbers. Here four bits are used to represent each decimal digit , e.g.

0000 ==> 0

0001 ==> 1

1001 ==> 9

Thus short int can be used to represent a four digit decimal number.

Use Bit--Fields to implement conversion routines to encode a decimal number into BCD format and back again.

Redo problem 1 using a bit--field structure as an illustration of how memory requirements may

be reduced. Compare the old and new memory requirements for data storage.

Using a doubly linked list data structure write a program that maintains an alphabetically ordered list of student registration records. The information held in each record should include the student's name, student identity number, address, course, etc. Your program should allow the user to add on records to the list, to remove records from the list, to amend records and to produce a screen dump of all records. Use distinct functions for all major operations if possible.

Use a FIFO implementation of a linked list to represent a queue of people entered by the user.