Lecture 17

Using data structures to store information.

When a data structure, such as a tree or linked list is used to store information, the data is split into two parts.

Key Data
Non Key Data

Key data is information used to order the data and non key data is the rest. The key should be chosen carefully so that it uniquely identifies the data. examples:

Key	Non Key
Student ID	Name,Address,Marks
Course Code	Name,Department,Campus
License Plate	Make,Model,Colour

Using a data structure such a a tree, it is easy to search for data using the key. We can still perform searches based on non key data but it will be more time consuming because the whole tree must be searched.

Hash Tables

It is often the case that data must be stored so that searching is very fast. The response time of a system is often determined by the speed at which it can retrieve data.

A tree is an efficient data structure, but it is not the fastest possible method for data retrieval. The fastest method would be to use an indexed array. If the whole key is converted into a number then that number could be used as the index into an array. Searching would simply involve looking up data in the array. If there are only limited values for the key then this could be useful, unfortunately this is rarely possible.

A hash table is a combination of an indexed array and a linked list. The key is used to generate a number (called the hash value) ,this number will not be unique to every key. The function used to generate the number from the key is called the hashing function. Since the hash value is not unique there will be a number of keys for each hash value. These are stored as a linked list. The hash value is used to index an array and then the linked list for that value is searched.

For example:

A simple hash function for words may be the ASCII value of the first character. The table will have 256 entries and each linked list will be a list of words which have the same first character.

The efficiency of hashing will depend on how randomly the hash function distributes key values into hash values. Our simple example would not be very efficient because there are more words starting with 't' than with '&'. A better hash function may be to add together all the characters in the key and use this value modulus 256.

Abstract Data Types.

In 'C' we can define new types using 'typedef struct'. This only creates a part of the type - how the type is stored. Along with this we must also write functions to perform operation of the data type.

Some languages provide a more complete way of creating new types - Abstract Data Types (ADTs). An ADT comprises the storage of the type and the operations allowed on the type. Languages such as Ada,C++, Haskell and Java allow ADTs. In C we must use functions.

Example: Complex numbers:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
  double r, i;
} complex;

complex cset(double r, double i) {
  complex t;

  t.r = r;
  t.i = i;
  return t;
}

complex cadd(complex x, complex y) {
  complex t;

  t.r = x.r + y.r;
  t.i = x.i + y.i;
  return t;
}

complex csub(complex x, complex y) {
  complex t;

  t.r = x.r - y.r;
  t.i = x.i - y.i;
  return t;
}

complex cmult(complex x, complex y) {
  complex t;

  t.r = x.r * y.r - x.i * y.i;
  t.i = x.r * y.i + x.i * y.r;
  return t;
}

void cprint(complex x) {
  printf("[%f,%f]\n",x.r,x.i);
}


void main() {
   int j,k;
   double q=6.2832/8;
   complex x[8],a[8];
   //
   // This program caclulates an 8 point discrete fourier transform
   // which is defined as:
   //   a[k]=sum_j(x[j]*(cos(q*j*k)+isin(q*j*k)))
   // where a[] and x[] are arrays of complex numbers

   puts("Input Data");
   for(j=0;j<8;j++) {
     x[j]=cset(10*cos((double)j*3.1415926/6),0);
     cprint(x[j]);
   }
   puts("DFT");
   for(k=0;k<8;k++) { 
      a[k]=cset(0,0);
      for(j=0;j<8;j++) 
         a[k]=cadd(a[k],cmult(x[j],cset(cos(q*j*k),sin(q*j*k))));
      cprint(a[k]);
   }
}

This program contains a data structure and some functions that perform operations on it. These definitions allow us to use complex numbers without having to worry about how to perform arithmetic on them. The main program performs a fourier transform, it would be considerably longer and harder to follow without the ADT.

Summary

Pointers
Arrays
Linked Lists
Stacks
Queues
Implementing Stacks and Queues Using Arrays
Trees
Hash Tables
Abstract Data Types