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.

Data Models
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:

int, long, unsigned
char, unsigned char
float, double
a pointer to one of the above

These data types have two properties associated with them:

how they are stored.
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.

#include <stdio.h>
#include <stdlib.h>
typedef unsigned char byte;
typedef struct _image {
   int width;
   int height;
   byte data[100][100]; 
} image;

typedef struct _student {
   char name[64];
   int id;
   int marks;
   image picture;
} student;

void main() {
   int i;
   student a59102[100];
   
   for(i=0;i<100;i++) {
       strcpy(a59102[i].name,"Fred Bloggs");
       a59102[i].id=rand()%1000000+97000000;
       a59102[i].marks=rand()%100;
   }
   for(i=0;i<100;i++) {
       printf("%s %d %d\n",a59102[i].name,a59102[i].id,a59102[i].marks);
   }
   
}

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:

Allocating space in the memory for the data using malloc.
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.

#include <stdio.h>
#include <stdlib.h>
typedef unsigned char byte;
typedef struct _image {
   int width;
   int height;
   byte data[100][100]; 
} image;

typedef struct _student {
   char name[64];
   int id;
   int marks;
   image *picture;
} student;

void main() {
   int i;
   student a59102[100];
   
   for(i=0;i<100;i++) {
       strcpy(a59102[i].name,"Fred Bloggs");
       a59102[i].id=rand()%1000000+97000000;
       a59102[i].marks=rand()%100;
   }
   a59102[50].picture=malloc(sizeof(image));
   a59102[50].picture->width=32;
   (*a59102[50].picture).height=32; 

   for(i=0;i<100;i++) {
       printf("%s %d %d\n",a59102[i].name,a59102[i].id,a59102[i].marks);
   }
   
}

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.

char name[64];
float points[100];

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

int table[32][32];
int *table[32]

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.

Insertion - Add an item to the list
Deletion - Delete an item from the list
Lookup - Find an item in the list
Retrieve - Return the n'th item in the list
Head - Return the first item in the list
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: