CSC270 October 7 Tutorial: Useful C for Assignment 2

Multidimensional arrays
[ King 8.2 ]

To create a two-dimensional array of type T:

   T array[dim1][dim2];

This array is stored in the variable `array' and has dimensions 
`dim1 x dim2'.  You can think of the dimensions as

  - rows and columns, or
  - x and y, or
  - anything else

To initialize an array:

  int arcs[ MAX_ROWS ][ MAX_COLS ];

  for (i=0; i < MAX_ROWS; i++)
    for (j=0; j < MAX_COLS; j++)
      arcs[i][j] = -1;

Note that the subscripts are separate like `arcs[i][j]'.  
Do not combine them like `arcs[i,j]'.



Arrays as function arguments

If you declare an array as

  int a[ DIM1 ][ DIM2 ];

then any function that takes it as a parameter should have a declaration
in the parameter list like

  void f( int a[ DIM1 ][ DIM2 ] )

The array dimensions should be included in the parameter list!  While
this is not always necessary, it's easy to remember this rule and it
doesn't hurt.

For one-dimensional arrays, there are two methods of defining the
parameters.  If the array is declared as

  int a[ DIM ];

You can use either of these parameter forms:

  void f( int a[ DIM ] )
  void f( int *a )

We'll talk next week about pointers (the *) and why the second form
works.



Dynamic allocation of one-dimensional arrays
[ King 17.3 ]

You'll need to allocate one-dimensional arrays dynamically when you
convert between graph representations in Assignment 2.

If you don't know the array size before the program starts, the array
has to be allocated `dynamically'.  Normally, you would define an
array of KNOWN size as

  int nodes[ NUM_NODES ];

But if the `nodes' array is of unknown size you would define it as

  int *nodes;

(This says that `nodes' is a `pointer to int'.  We'll discuss pointers
in the next tutorial.  For now, use this as a template for dynamic
array allocation.)

If you find that the array has some size, say `n', then you can create
an array of n ints as

  nodes = (int *) malloc( n * sizeof(int) );

Now `nodes' can be treated just like any array of n ints.  For example,

  for (i=0; i < n; i++)
    nodes[i] = -1;

WARNING: The elements of the array are not initialized to any
particular values!  They don't usually contain zeroes, so you have to
initialize the array yourself.  This is also true of arrays of known
size defined before compilation.



Structs
[ King 16.1, 16.2, 16.3 ]

An array is a collection of elements which are

  - all of the same type
  - referred to by an index

A `structure' is a collection of elements which are

  - of possibly different types
  - referred to by a name

A structure usually stores a collection of related items.  A poor
implementation of a string would store an array of characters and a
length:

  struct {
    int  length;
    char str[100];
  } string1, string2;

This statement defines two variables, `string1' and `string2'.  Each
variable contains two components called `length' and `str'.  To refer
to the components, we use the dot notation.  In general, the form is

  variable_name.field_name

Each component of the structure is called a `field'.  

For example, to initialize the strings (which don't have a terminating
'\0' character, since the length field gives this information):

  string1.length = 2;
  string1.str[0] = 'x';
  string1.str[1] = 'y';

  for (i=0; i < NUM_BLANKS; i++)
    string2.str[i] = ' ';
  string2.length = NUM_BLANKS;



Arrays of structs

Note that an array can be a component of a structure.  Similarly, we
can have an array of structures:

  struct {
    int index;
    int num_adj_nodes;
    int adj_nodes[100];
  } nodes[20];

This defines an array of 20 nodes, where each node is a structure with
three fields: index, num_adj_nodes, and adj_nodes.  This structure
could store a node in a graph and the indices of adjacent nodes (`adj'
stands for `adjacent').  In the code below, every node is made
adjacent to node 0:

  for (i=0; i < 20; i++) {
    nodes[i].index = i;
    nodes[i].num_adj_nodes = 1;
    nodes[i].adj_nodes[0] = 0;
  }



Making your own structure types

It's tedious to type the whole structure definition every time you
want to declare a new variable.  C allows you to avoid this by
defining a new type that is a structure:

  typedef struct {
    int index;
    int num_adj_nodes;
    int adj_nodes[100];
  } NODE;

This is a definition of a TYPE called `NODE'.  It is NOT a declaration
of a variable called `NODE'.  

Typically, people use uppercase letters or a Capitalized Word for
their own type names.  It helps when reading the program.

After defining a new type, you can use it wherever you want:

  NODE a, b, c;
  NODE nodes[20];

These statements declare three variables -- a, b, and c -- of the NODE
type, along with an array of 20 nodes.  Much cleaner code is produced
if you make the appropriate typedefs like this.

Such variables are used in the normal way:

  a.index = 0;
  a.num_adj_nodes = 0;

  nodes[5].index = 5;
  nodes[5].num_adj_nodes = 1;
  nodes[5].adj_nodes[0] = 1;