Lecture 12

Data Structures

Computer Science is the study of complex systems. There are two types of model that can be used to describe a complex system.
  1. Data Models
  2. Functional Models
Anything but a trivial problem will involve both types of model. So far we have only looked at a functional models (in the form of algorithms).

To solve a problem, it is vital that both types of model are considered.

C data types:

These data types have two properties associated with them:
  1. how they are stored.
  2. operation that are permitted on them.
For a new data type we will have to provide both of these properties.

The basic data types in C are extremely primitive (in abstract terms), but the language allows new types to be defined using typedef and struct e.g.

 

Pointers

In order to understand data types in C, it is vital to understand pointers. All data is stored in memory, the location of the data in memory memory is called the address of the data. An address is a number and this number can be stored just like any other - this is a pointer.

In C, a pointer is defined by putting a * after the name of any other data type.
e.g

        int *i;  // i is an "int *" i.e. a pointer to an int.
        char *c; // c is a "char *" i.e. a pointer to a char.
        student *st;  // st is a pointer to a student;
Initially the pointer will not hold the address of any data, it must be set to an address by:
  1. Allocating space in the memory for the data using malloc.
  2. Assigning the pointer to an address that contains valid data. e.g. using the &operator or from another pointer.
        char *name="martin";
        int *x;
        int j;
        char *c;

        x=&j;
        c=(char *)malloc(100);
Pointers can be manipulated in the same way as an integer. In C it is common to use a pointer to reference a structure. e.g.
 

Arrays

An array is an indexed collection of data with a fixed size.

Pointers allow arrays by storing data sequentially in memory. The pointer holds the address of the first item in the array. In order to access other items, an offset is added to the pointer.

Multidimensional arrays are stored by a mapping from a one dimensional array, or by using an array of pointers.

Lists

Arrays have a fixed size and shape, other data structures do not. These can be created using pointers and structs.

A list is an ordered collection of data items. There are a number of important operations on lists.

  1. Insertion - Add an item to the list
  2. Deletion - Delete an item from the list
  3. Lookup - Find an item in the list
  4. Retrieve - Return the n'th item in the list
  5. Head - Return the first item in the list
  6. Tail - Return the last item in the list
At first sight it seems that a list can always be stored using an array. This is true if the list is small and we know that it will not grow beyond a certain size.

Often, a list must be kept in order. In this case, adding and removing items will be time consuming and may involve moving many other list items.

A better representation is a Linked List: