Computer Science is the study of complex systems. There are two types of
model that can be used to describe a complex system.
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:
int, long, unsigned
char, unsigned char
a pointer to one of the above
For a new data type we will have to provide both of these properties.
how they are stored.
operation that are permitted on them.
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.
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
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.
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.
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.
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.
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.
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
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: