This document gives code for representative ADTs and algorithms discussed in Lectures. It's organised as a single long page, broken down by topic area. The code assumes that all collection types are made up of Items, where the Item type has equality, less than, greater than, comparison, and display functions available as eq(it1,it2), less(it1,it2), greater(it1,it2), cmp(it1,it2) and show(it). Sometimes, Items have keys which are integer or string values that uniquely identify the Item. They key value can be extracted from an Item using the key(it) function. ADTs are implemented via a pointer to a hidden representation type (e.g. the Stack type is a pointer to a StackRep structure).

Note: the code below has not been compiled; we make no guarantees that there are no bugs. This code is provided simply as a guide to how the algorithms were implemented.

Linear ADTs   ( Stacks ... Queues )

Stack ADT

Interface:

typedef struct StackRep *Stack;
// set up empty stack
Stack newStack(int);
// remove unwanted stack
void dropStack(Stack);
// insert an Item on top of stack
void StackPush(Stack,Item);
// remove Item from top of stack
Item StackPop(Stack);
// check whether stack is empty
Bool StackIsEmpty(Stack);

Implementation (via arrays):

typedef struct StackRep {
   Item *item;
   int top;
} StackRep;
// set up empty stack
Stack newStack(int n)
{
   Stack s;
   s = malloc(sizeof(StackRep));
   assert(s != NULL);
   s->item = malloc(n * sizeof(Item));
   assert(s->item != NULL);
   s->top = -1;
   return s;
}
// remove unwanted stack
void dropStack(Stack s)
{
   assert(s != NULL);
   free(s->item);
   free(s);
}
// insert Item on top of stack
void StackPush(Stack s, Item it)
{
   assert(s->top < MAXITEMS-1);
   s->top++;
   int i = s->top;
   s->item[i] = it;
}
// remove Item from top of stack
Item StackPop(Stack s)
{
   assert(s->top > -1);
   int i = s->top;
   Item it = s->item[i];
   s->top--;
   return it;
}
// check whether stack is empty
Bool StackIsEmpty(Stack s)
{
   return (s->top < 0);
}

Queue ADT

Interface:

typedef struct QueueRep *Queue;
// set up empty queue
Queue newQueue(int);
// remove unwanted queue
void dropQueue(Queue);
// insert Item at back of queue
void QueueJoin(Queue,Item);
// remove Item from front of queue
Item QueueLeave(Queue);
// check whether queue is empty
Bool QueueIsEmpty(Queue);

Implementation (via arrays):

typedef struct QueueRep {
   Item *item;  // array to hold Items
   int front;  // next Item to be removed
   int back;  // last Item added
   int nitems;  // # Items currently in queue
   int maxitems;  // size of array
} QueueRep;
// set up empty queue
Queue newQueue(int n)
{
   Queue q;
   q = malloc(sizeof(QueueRep));
   assert(q != NULL);
   q->item = malloc(n * sizeof(Item));
   assert(q->item != NULL);
   q->front = q->back = 0;
   q->nitems = 0; q->maxitems = n;
   return q;
}
// remove unwanted queue
void dropQueue(Queue q)
{
   assert(q != NULL);
   free(q->item);
   free(q);
}
// insert item on top of queue
void QueueJoin(Queue q, Item it)
{
   assert(q->nitems < q->maxitems);
   q->item[q->front] = it;
   q->nitems++;
   q->front = (q->front+1)%q->maxitems;
}
// remove item from front of queue
Item QueueLeave(Queue q)
{
   assert(q->nitems > 0);
   Item it = q->item[q->back];
   q->nitems--;
   q->back = (q->back+1)%q->maxitems;
   return it;
}
// check whether queue is empty
Bool QueueIsEmpty(Queue q)
{
   return (q->nitems == 0);
}

Priority Queue:

Interface:

typedef struct PQueueRep *PQueue;
create new empty priority queue
PQueue newPQueue(int size);
add item to priority queue
void PQJoin(PQueue q, Item it);
remove item from priority queue
Item PQLeave(PQueue q);
free up priority queue
void dropPQueue(PQueue q);

Implementation:

struct PQueueRep {
    int   nItems; // count of items
    Item *items;  // heap-array of Items
    int   size;   // size of array
}
// create a new empty queue
PQueue newPQueue(int size)
{
    PQueue q = malloc(sizeof(struct PQrep));
    assert(q != NULL);
    // indexes start from 1
    q->items = malloc(sizeof(Item) * (size+1));
    assert(q->items != NULL);
    q->nItems = 0;
    q->size = size;
    return q;
}
// add a new item into the queue
void PQJoin(PQueue q, Item it)
{
    assert(q != NULL && q->nItems < q->size);
    q->nItems++;
    q->items[q->nItems] = it;
    fixUp(q->items, q->nItems);
}
// remove item from priority queue
Item PQLeave(PQueue q)
{
    assert(q != NULL && q->nItems > 0);
    swap(q->items, 1, q->nItems);
    q->nItems--;
    fixDown(p->items, 1, q->nItems);
    return q->items[q->nItems+1];
}
free up priority queue
void dropPQueue(PQueue q)
{
    assert(q != NULL);
    free(q->items);
    free(q);
}
void fixUp(Item a[], int k)
{
   while (k > 1 && less(a[k/2],a[k])) {
      swap(a, k, k/2);
      k = k/2;  // integer division
   }
}
void fixDown(Item a[], int k, int N)
{
    while (2*k <= N) {
    int j = 2*k;
    // choose larger of two children
    if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        swap(a, k, j);
        k = j;
    }
}

Sorting  

Sorting problem:

Pre-condition: a[0..N-1] contain Items
Post-condition: forall i:0..N-2,  key(a[i]) ≤ key(a[i+1])

Selection sort:

void selectionSort(int a[], int lo, int hi)
{
   int i, j, min;
   for (i = lo; i < hi; i++) {
      min = i;
      for (j = i+1; j <= hi; j++) {
         if (less(a[j],a[min])) min = j;
      }
      swap(a[i], a[min]);
   }
}

Bubble sort:

void bubbleSort(int a[], int lo, int hi)
{
   int i, j;
   for (i = lo; i < hi; i++) {
      for (j = hi; j > i; j--) {
         if (less(a[j], a[j-1])) {
            swap(a[j], a[j-1]);
         }
      }     
   }
}

Bubble sort with Early Exit:

void bubbleSort(int a[], int lo, int hi)
{
   int i, j, nswaps;
   for (i = lo; i < hi; i++) {
      nswaps = 0;
      for (j = hi; j > i; j--) {
         if (less(a[j], a[j-1])) {
            swap(a[j], a[j-1]);
            nswaps++;
         }
      }
      if (nswaps == 0) break;
   }
}

Insertion sort:

void insertionSort(int a[], int lo, int hi)
{
   int i, j, val;
   for (i = lo+1; i <= hi; i++) {
      val = a[i];
      for (j = i; j > lo; j--) {
         if (!less(val,a[j-1])) break;
         a[j] = a[j-1];
      }
      a[j] = val;
   }
}

Shell sort:

void shellSort(int a[], int lo, int hi)
{
    int n = (hi-lo) + 1; 
    int i, j, h;

    //calculate starting h value
    for (h = 1; h <= (n - 1)/9; h = (3 * h) + 1) {
          printf("%d ",h);
    }
    
    for (; h > 0; h /= 3) {
      
       for (i = h; i < n; i++) {
            int key = a[i];
            for (j = i; j >= h && key <  a[j - h] ; j -=h) {
                a[j] = a[j - h];
            }
            a[j] = key;
        }
    }
   
}
 
}

Quicksort: (with median-of-three partitioning)

void quicksort(Item a[], int lo, int hi)
{
   int i; // index of pivot
   if (hi <= lo) return;
   medianOfThree(a, lo, hi);
   i = partition(a, lo+1, hi-1);
   quicksort(a, lo, i-1);
   quicksort(a, i+1, hi);
}
void medianOfThree(Item a[], int lo, int hi)
{
   int mid = (lo+hi)/2;
   if (less(a[mid],a[lo])) swap(a, lo, mid);
   if (less(a[hi],a[mid])) swap(a, mid, hi);
   if (less(a[mid],a[lo])) swap(a, lo, mid);
   // now, we have a[lo] ≤ a[mid] ≤ a[hi]
   // swap a[mid] to a[lo+1] to use as pivot
   swap(a, lo+1, mid);
}
int partition(Item a[], int lo, int hi)
{
   Item v = a[lo];  // pivot
   int  i = lo+1, j = hi;
   for (;;) {
      while (less(a[i],v) && i < j) i++;
      while (less(v,a[j]) && j > i) j--;
      if (i == j) break;
      swap(a,i,j);
   }
   j = less(a[i],v) ? i : i-1;
   swap(a,lo,j);
   return j;
}

Mergesort:

void mergesort(Item a[], int lo, int hi)
{
   int mid = (lo+hi)/2; // mid point
   if (hi <= lo) return;
   mergesort(a, lo, mid);
   mergesort(a, mid+1, hi);
   merge(a, lo, mid, hi);
}
void merge(Item a[], int lo, int mid, int hi)
{
   int  i, j, k, nitems = hi-lo+1;
   Item *tmp = malloc(nitems*sizeof(Item));

   i = lo; j = mid+1; k = 0;
   // scan both segments, copying to tmp
   while (i <= mid && j <= hi) {
     if (less(a[i],a[j]))
        tmp[k++] = a[i++];
     else
        tmp[k++] = a[j++];
   }
   // copy items from unfinished segment
   while (i <= mid) tmp[k++] = a[i++];
   while (j <= hi) tmp[k++] = a[j++];

   //copy tmp back to main array
   for (i = lo, k = 0; i <= hi; i++, k++)
      a[i] = tmp[k];
   free(tmp);
}

Searching   ( Binary Search ... BSTs ... Balanced Trees ... HashTables )

Binary Search

Binary search in array:

// search for key k in array a[]
// - returns index of location for k
// - doesn't indicate whether key is actually there or not
int findInArray(Key k, Item a[], int lo, int hi)
{
    if (hi <= lo) return lo;
    int mid = (hi+lo)/2;
    int diff = cmp(k, key(a[mid]));
    if (diff < 0)
        return findInArray(k, a, lo, mid);
    else if (diff > 0)
        return findInArray(k, a, mid+1, hi);
    else
        return mid;
}

Binary Search Trees (BSTs)

BST Interface:

typedef struct Node *Tree;
// create an empty Tree
Tree newTree();
// free memory associated with Tree
void dropTree(Tree);
// display a Tree (sideways)
void showTree(Tree);
// insert a new item into a Tree
Tree TreeInsert(Tree, Item);
// delete item with given key from Tree
Tree TreeDelete(Tree, Key);
// check whether item with given key is in Tree
int TreeFind(Tree, Key);
// compute depth of Tree
int TreeDepth(Tree);
// count #nodes in Tree
int TreeNumNodes(Tree);

BST Implementation:

typedef struct Node *Link;
typedef struct Node {
    Item value;
    Link left, right;
} Node;
// make a new node containing an Item
static Link newNode(Item it)
{
    Link new = malloc(sizeof(Node));
    assert(new != NULL);
    new->value = it;
    new->left = new->right = NULL;
    return new;
}
// create a new empty Tree
Tree newTree()
{
    return NULL;
}
// free memory associated with Tree
void dropTree(Tree t)
{
    if (t == NULL) return;
    dropTree(t->left);
    dropTree(t->right);
    free(t);
}
// display a Tree (sideways)
void showTree(Tree t)
{
    void doShowTree(Tree);
    doShowTree(t);
}
// insert a new value into a Tree
Tree TreeInsert(Tree t, Item it)
{
    if (t == NULL) return newNode(it);
    int diff = cmp(key(it),key(t->value));
    if (diff == 0)
        t->value = it;
    else if (diff < 0)
        t->left = TreeInsert(t->left, it);
    else if (diff > 0)
        t->right = TreeInsert(t->right, it);
    return t;
}
// insert a new value as root of Tree
Tree insertAtRoot(Tree t, Item it)
{ 
   if (t == NULL) return newNode(it);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0) {
      t->left = insertAtRoot(t->left, it);
      printf("rotateR(%d)\n",t->value);
      t = rotateR(t);
   }
   else if (diff > 0) {
      t->right = insertAtRoot(t->right, it);
      printf("rotateL(%d)\n",t->value);
      t = rotateL(t);
   }
   return t;
}

// delete item with given key from Tree
Tree TreeDelete(Tree t, Key k)
{
    Tree deleteRoot(Tree);

    if (t == NULL)
        return NULL;
    int diff = cmp(k,key(t->value));
    if (diff == 0)
        t = deleteRoot(t);
    else if (diff < 0)
        t->left = TreeDelete(t->left, k);
    else if (diff > 0)
        t->right = TreeDelete(t->right, k);
    return t;
}
// delete root of tree
Tree deleteRoot(Tree t)
{
    Link newRoot;
    // if no subtrees, tree empty after delete
    if (t->left == NULL && t->right == NULL) {
        free(t);
        return NULL;
    }
    // if only right subtree, make it the new root
    else if (t->left == NULL && t->right != NULL) {
        newRoot = t->right;
        free(t);
        return newRoot;
    }
    // if only left subtree, make it the new root
    else if (t->left != NULL && t->right == NULL) {
        newRoot = t->left;
        free(t);
        return newRoot;
    }
    // else (t->left != NULL && t->right != NULL)
    // so has two subtrees
    // - find inorder successor (grab value)
    // - delete inorder successor node
    // - move its value to root
    Link parent = t;
    Link succ = t->right; // not null!
    while (succ->left != NULL) {
        parent = succ;
        succ = succ->left;
    }
    int succVal = succ->value;
    t = TreeDelete(t,succVal);
    t->value = succVal;
    return t;
}
// check whether item with given key is in Tree
int TreeFind(Tree t, Key k)
{
    if (t == NULL) return 0;
    int res, diff = cmp(k,key(t->value));
    if (diff < 0)
        res = TreeFind(t->left, k);
    else if (diff > 0)
        res = TreeFind(t->right, k);
    else // (diff == 0)
        res = 1;
    return res;
}
// compute depth of Tree
int TreeDepth(Tree t)
{
    if (t == NULL)
        return 0;
    else {
        int ldepth = TreeDepth(t->left);
        int rdepth = TreeDepth(t->right);
        //return 1 + (ldepth > rdepth)?ldepth:rdepth;
        if (ldepth > rdepth)
            return 1+ldepth;
        else
            return 1+rdepth;
    }
}
// count #nodes in Tree
int TreeNumNodes(Tree t)
{
    if (t == NULL) return 0;
    return 1 + TreeNumNodes(t->left)
             + TreeNumNodes(t->right);
}

Balanced Trees

typedef struct node * link;

struct treeImp{
    link root;
};

struct node{
    Item item;
    link left;
    link right;
    int size; //Keeps track of the number of nodes in each sub-tree
};

static link emptyTree = NULL;


static link NEW (Item item, link l, link r, int size){ 
    link newLink = malloc (sizeof *newLink); 
  
    newLink->item = item; 
    newLink->left = l; 
    newLink->right = r; 
    newLink->size = size;
    return newLink;
}

//Initialises a tree
//In this implementation, a tree is not just a pointer to the root node
//but is a struct which contains a pointer to the root node.
Tree TREEinit(int balanceStrategy){
    Tree t = malloc(sizeof(struct treeImp));
    assert(t!= NULL);
    if(emptyTree == NULL){
      emptyTree = NEW(NULLitem,NULL,NULL,0);
    }
    t->root = emptyTree;
    
    srand(time(NULL)); //seed random number generator for insertRandom
    
    return t;
}

//returns the size of the tree
int TREEcount(Tree tree){
    if(tree->root == NULL) return 0;
    return tree->root->size;
}



void TREEdestroy(Tree t){
    assert(t != NULL);
    destroyNodes(t->root);
    free(emptyTree);
    free(t);
}

// A recursive version of standard BST insertion
// Modified to update the size counters
// inserts duplicates
link insert (link currentLink, Item item) { 
  
   if (currentLink == emptyTree) {
       return (NEW (item, emptyTree, emptyTree, 1));
   }
   if (less (key (item), key (currentLink->item))) {
       currentLink->left = insert (currentLink->left, item);
   } else  {
       currentLink->right = insert (currentLink->right, item);
   }
   currentLink->size++;
   return (currentLink);
}

// A recursive function that inserts the new item 
// at the root of the tree. This is used in randomInsert
link insertAtRoot(link currentLink, Item item){
    if(currentLink == emptyTree){
        return (NEW(item,emptyTree,emptyTree,1));
    } 
    //size gets updated by the rotate functions
    if (less (key (item), key (currentLink->item))) {
        currentLink->left = insertAtRoot (currentLink->left, item);
        currentLink = rotRight(currentLink);
    } else {
        currentLink->right = insertAtRoot (currentLink->right, item);
        currentLink = rotLeft(currentLink);
    } 
  
    return (currentLink);
  
}

// Randomly inserts either at the leaf of the tree or the root
link insertRandom(link currentLink, Item item){
 
  if (currentLink == emptyTree) {
    return (NEW (item, emptyTree, emptyTree, 1));
  }
  //Prob 1/N
  if(rand() < RAND_MAX/(currentLink->size+1)){
    return insertAtRoot(currentLink,item);
  } else if (less (key (item), key (currentLink->item))) {
    currentLink->left = insertRandom (currentLink->left, item);
  } else {
    currentLink->right = insertRandom (currentLink->right, item);
  } 
  currentLink->size++;
  return (currentLink);
}



// Performs a standard recursive search for the key in the given tree
// returns 1 if found and 0 otherwise
int searchR(link  t, Key k){
    int returnVal;
    if (t == NULL || t == emptyTree){
        returnVal =  0;
    }else if (less(k,t->item)){
	    returnVal =  searchR(t->left, k);
    }else if (greater(k,t->item)){
	    returnVal =  searchR(t->right, k);
    }else{
        returnVal =  1;
    }
    return returnVal;
}


static link rotLeft (link currentTree) {
	if(currentTree == NULL || currentTree == emptyTree                  
                           || currentTree->right == emptyTree){
        return currentTree;
    }
    link rotLTree = currentTree->right;
    currentTree->right = rotLTree->left;
    rotLTree->left = currentTree;
	rotLTree->left->size = rotLTree->left->left->size + rotLTree->left->right->size +1;
    rotLTree->size = rotLTree->left->size + rotLTree->right->size + 1;
    return rotLTree;
}


static link rotRight (link currentTree) {
	if(currentTree == NULL || currentTree == emptyTree 
                           || currentTree->left == emptyTree){
        return currentTree;
    }
    link rotRTree = currentTree->left;
    currentTree->left = rotRTree->right;
    rotRTree->right = currentTree;
	rotRTree->right->size = rotRTree->right->left->size + rotRTree->right->right->size + 1;
    rotRTree->size = rotRTree->right->size+ rotRTree->left->size+1;
    return rotRTree;
}



// partition tree at node with position pos (counting from 0) in the
// sorted sequence of all items, node become new root node.
link partitionR (link currentTree, int pos) {
    if(currentTree == NULL || currentTree == emptyTree)
        return currentTree;
    int leftSubtreeSize = currentTree->left->size;
    if (leftSubtreeSize > pos) {
        currentTree->left = partitionR (currentTree->left, pos);
        currentTree = rotRight (currentTree) ;
    } else if (leftSubtreeSize < pos) {
        currentTree->right = 
        partitionR (currentTree->right, pos - 1 - leftSubtreeSize);
        currentTree = rotLeft (currentTree) ;    
    }
    return currentTree;
}

link balance(link tree){
    if(tree->size >=2){
        tree = partitionR(tree,tree->size/2);
        tree->left = balance(tree->left);
        tree->right = balance(tree->right);
    }
    return tree;
}

link insertSplay (link tree, Item item) {
    Key v = key (item);
    if (tree == emptyTree)
        return (NEW (item, emptyTree, emptyTree, 1)); 
  
    if (less (v, key(tree->item))) {
        if (tree->left == emptyTree) {
            return (NEW (item, emptyTree, tree, tree->size+1));
        }
        if (less (v, key (tree->left->item))) {
            tree->left->left = insertSplay (tree->left->left, item);
            tree = rotRight (tree); 
        } else {
            tree->left->right = insertSplay (tree->left->right, item);
            tree->left = rotLeft (tree->left);
        }
            return rotRight (tree);
    } else {
        if (tree->right == emptyTree) {
            return (NEW (item, tree, emptyTree, tree->size+1));
        }
        if (less (key (tree->right->item), v)) {
            tree->right->right = insertSplay (tree->right->right, item);
            tree = rotLeft (tree);
        } else {
            tree->right->left = insertSplay (tree->right->left, item);
            tree->right = rotRight (tree->right);
        }
        return rotLeft (tree);
     }
}

//The function should perform rotations on all
//items in the search path in a similar way to that of
//splay tree insertion - except no node is actually inserted
 
//The node that contains the key
//should be rotated up and returned as the root of the tree
//and *found should be set to 1
    
//If the key was not found, the last node on the search
//path should be rotated up to the root of the tree
//and found should be set to 0

//returns the new root of the tree 
//sets the value of *found to 0 or 1
link searchSplay (link n, Key k, int * found){
  
    link returnVal = emptyTree;

    if (n == emptyTree) {
        // item not found
        *found = 0;
        returnVal =  n;  
    }else if (eq(key(n->item),k)) {
        *found = 1;    // item found, store true
        returnVal =  n;  
    } else if (less (k, key (n->item))) {
        if (n->left == emptyTree){
            *found = 0;// item not found
            //returnVal =  rotateRight(n);
            returnVal = n;
        }else if(eq(key(n->left->item),k)){
            *found = 1;
            returnVal =  rotRight(n);
        }else{
            if (less (k, key(n->left->item))) {
                /* left-left */
                n->left->left = searchSplay (n->left->left, k, found);
              
                n = rotRight (n);
               
            } else {
                /* left-right */
                n->left->right = searchSplay (n->left->right, k, found);
                n->left = rotLeft (n->left);
            }
            returnVal =  rotRight (n);
        }
   } else {
         //printf("At node %s\n",n->item); 
       if (n->right == emptyTree){
            *found = 0;// item not found
            //returnVal =  rotateLeft(n);
            returnVal = n;
        }else if(eq(key(n->right->item),k)){
            *found = 1;
            returnVal =  rotLeft(n);
        } else{
            if (less (key(n->right->item), k)) {
                /* right-right */
                n->right->right = searchSplay (n->right->right, k, found);
               
                n = rotLeft (n);
                
            } else {
                /* right-left */
                n->right->left = searchSplay (n->right->left, k, found);
                n->right = rotRight (n->right);
            }
            
            returnVal =  rotLeft (n);
        }
   }
   return returnVal;
   
}

static void destroyNodes(link n){
    if( n != emptyTree){
        destroyNodes(n->left);
        destroyNodes(n->right);
        free(n->item);
        free(n);
    }
}

Hashing

Hash table Interface:

typedef struct HashTabRep *HashTable;
// create an empty HashTable
HashTable newHashTable(int);
// free memory associated with HashTable
void dropHashTable(HashTable);
// insert a new value into a HashTable
void hashTableInsert(HashTable, Item);
// delete a value from a HashTable
void hashTableDelete(HashTable, Key);
// get Item from HashTable using Key
Item *hashTableSearch(HashTable, Key);

Hash Table Implementation: (separate chains)

#include "List.h"  // use Lists of Items
typedef struct HashTabRep {
   List *lists;  // lists of Items
   int   nslots; // # elements in array
   int   nitems; // # items stored in HashTable
} HashTabRep;
// convert key to index
static int hash(Key k, int N)
{
   int h = ... convert key to int
   return h % N;
}
// create an empty HashTable
HashTable newHashTable(int N)
{
   HashTable new = malloc(sizeof(HashTable));
   assert(new != NULL);
   new->lists = malloc(N*sizeof(List));
   assert(new->items != NULL);
   int i;
   for (i = 0; i < N; i++)
      new->lists[i] = newList();
   new->nslots = N;
   new->nitems = 0;
   return new;   
}
// free memory associated with HashTable
void dropHashTable(HashTable ht)
{
   free(ht->lists);
   free(ht);
}
// insert a new value into a HashTable
void hashTableInsert(HashTable ht, Item it)
{
   Key k = key(it);
   int i = hash(k, ht->nslots);
   ListInsert(ht->lists[i], it);
}
// delete a value from a HashTable
void hashTableDelete(HashTable ht, Key k)
{
   int i = hash(k, ht->nslots);
   ListDelete(ht->lists[i], k);
}
// get Item from HashTable using Key
Item *hashTableSearch(HashTable ht, Key k)
{
   int i = hash(k, ht->nslots);
   return ListSearch(ht->lists[i], k);
}

Hash Table Implementation: (linear probing)

#include "List.h"  // use Lists of Items
typedef struct HashTabRep {
   Item *items;  // lists of Items
   int   nslots; // # elements in array
   int   nitems; // # items stored in HashTable
} HashTabRep;
// convert key to index
static int hash(Key k, int N)
{
   int h = ... convert key to int
   return h % N;
}
// create an empty HashTable
HashTable newHashTable(int N)
{
   HashTabRep *new = malloc(sizeof(HashTabRep));
   assert(new != NULL);
   new->items = malloc(N*sizeof(Item));
   assert(new->items != NULL);
   int i;
   for (i = 0; i < N; i++)
      new->items[i] = NoItem;
   new->nslots = N; new->nitems = 0;
   return new;

}
// free memory associated with HashTable
void dropHashTable(HashTable ht)
{
   free(ht->items);
   free(ht);
}
// insert a new value into a HashTable
void hashTableInsert(HashTable ht, Item it)
{
   int N = ht->nslots;
   Item *data = ht->items;
   Key k = key(it);
   int ix, j, i = hash(k,N);
   for (j = 0; j < N; j++) {
      ix = (i+j)%N;
      if (cmp(k,key(data[ix]) == 0)
         break;
      else if (data[ix] == NoItem)
         break;
   }
   if (j < N) {
      data[ix] = it;
      ht->nitems++;
   }
}
// delete a value from a HashTable
void hashTableDelete(HashTable ht, Key k)
{
   int N = ht->nslots;
   Item *data = ht->items;
   int j, i = hash(k,N);
   for (j = 0; j < N; j++) {
      int ix = (i+j)%N;
      if (cmp(k,key(data[ix]) == 0)
         break;
      else if (data[ix] == NoItem)
         return; // k not in table
   }
   data[ix] = NoItem;
   ht->nitems--;
   // clean up probe path
   j = ix+1;
   while (data[j] != NoItem) {
      Item it = data[j];
      data[j] = NoItem;
      ht->nitems--;
      insert(ht, it);
      j = (j+1)%N);
   }
}
// get Item from HashTable using Key
Item *hashTableSearch(HashTable ht, Key k)
{
   int N = ht->nslots;
   Item *data = ht->items;
   int j, i = hash(k,N);
   for (j = 0; j < N; j++) {
      int ix = (i+j)%N;
      if (cmp(k,key(data[ix]) == 0)
         return &(data[ix]);
   }
   return NULL;

}

Graphs

Representation

Graph Interface:

// visible data structures for Graphs
typedef struct GraphRep *Graph;
// vertices denoted by integers 0..N-1
typedef int Vertex;
// edges are pairs of vertices (end-points)
typedef struct { Vertex v; Vertex w; } Edge;
// auxiliary operations on graphs
int  validV(Graph,Vertex); // validity check
Edge mkEdge(Graph, Vertex, Vertex); // edge creation
int  neighbours(Graph, Vertex, Vertex); // edge existence
// core operations on graphs
// make new graph with nV vertices
Graph newGraph(int nV);
// free memory allocated to graph
void  dropGraph(Graph);
// show "printable" representation of graph
void  showGraph(Graph);
// add new edge to a graph
void  insertE(Graph, Edge);
// remove an edge from a graph
void  removeE(Graph, Edge);
// returns #vertices & array of edges
int   edges(Graph, Edge *, int);

Implementation of Auxiliary Operations:

// is a vertex valid in a given Graph?
static int validV(Graph g, Vertex v)
{
   return (g != NULL && v >= 0 && v < g->nV);
}
// make an Edge value
Edge mkEdge(Graph g, Vertex v, Vertex w)
{
   assert(validV(g,v) && validV(g,w));
   Edge e = {v,w}; // struct assignment
   return e;
}

Adjacency Matrix Representation:

typedef struct GraphRep {
   int    nV;    // #vertices
   int    nE;    // #edges
   Bool **edges; // matrix of booleans
} GraphRep;
// check whether two vertices are connected
int neighbours(Graph g, Vertex v, Vertex w)
{
	assert(validV(g,v) && validV(g,w));
	return g->edges[v][w];
}
// make new graph with nV vertices
Graph newGraph(int nV)
{
   assert(nV >= 0);
   int i, j;
   int **e = malloc(nV * sizeof(int *));
   assert(e != NULL);
   for (i = 0; i < nV; i++) {
      e[i] = malloc(nV * sizeof(int));
      assert(e[i] != NULL);
      for (j = 0; j < nV; j++)
         e[i][j] = FALSE;
   }
   Graph g = malloc(sizeof(GraphRep));
   assert(g != NULL);
   g->nV = nV;  g->nE = 0;  g->edges = e;
   return g;
}
// free memory allocated to graph
void  dropGraph(Graph g)
{
   assert(g != NULL);
   int i;
   for (i = 0; i < g->nV; i++)
      free(g->edges[i]);
   free(g->edges);
   free(g);
}
// show "printable" representation of graph
void  showGraph(Graph g)
{
   assert(g != NULL);
   printf("V=%d, E=%d\n", g->nV, g->nE);
   int i, j;
   for (i = 0; i < g->nV; i++) {
      int nshown = 0;
      for (j = i+1; j < g->nV; j++) {
         if (g->edges[i][j] != 0) {
            printf("%d-%d ",i,j);
            nshown++;
         }
      }
      if (nshown > 0) printf("\n");
   }
}
// add new edge to a graph
void insertE(Graph g, Edge e)
{
   assert(g != NULL);
   assert(validV(g,e.v) && validV(g,e.w));
   if (g->edges[e.v][e.w]) return;
   g->edges[e.v][e.w] = 1;
   g->edges[e.w][e.v] = 1;
   g->nE++;
}
// remove an edge from a graph
void removeE(Graph g, Edge e)
{
   assert(g != NULL);
   assert(validV(g,e.v) && validV(g,e.w));
   if (!g->edges[e.v][e.w]) return;
   g->edges[e.v][e.w] = 0;
   g->edges[e.w][e.v] = 0;
   g->nE--;
}
// returns #vertices & array of edges
int edges(Graph g, Edge *es, int nE)
{
   assert(g != NULL && es != NULL);
   assert(nE >= g->nE);
   int i, j, n = 0;
   for (i = 0; i < g->nV; i++) {
      for (j = i+1; j < g->nV; j++) {
         if (g->edges[i][j] != 0) {
            assert(n < nE);
            es[n++] = mkEdge(g,i,j);
         }
      }
   }
   return n;
}

Adjacency List Representation:

typedef struct vNode *VList;
struct vNode { Vertex v; vList next; };
typedef struct graphRep GraphRep;
struct graphRep {
   int   nV;     // #vertices
   int   nE;     // #edges
   VList *edges; // array of lists
};
// check whether two vertices are connected
int neighbours(Graph g, Vertex v, Vertex w)
{
   assert(validV(g,v) && validV(g,w));
   VList curr;
   curr = g->edges[v];
   while (curr != NULL) {
      if (curr->v == w) return 1;
   }
   return 0;
}
// make new graph with nV vertices
Graph newGraph(int nV)
{
   int i, j;
   VList *e = malloc(nV * sizeof(VList));
   assert(e != NULL);
   for (i = 0; i < nV; i++) e[i] = NULL;
   Graph g = malloc(sizeof(GraphRep));
   assert(g != NULL);
   g->nV = nV;  g->nE = 0;  g->edges = e;
   return g;
}
// free memory allocated to graph
void  dropGraph(Graph g)
{
   assert(g != NULL);
   int i;
   for (i = 0; i < g->nV; i++)
      freeVList(g->edges[i]);
   free(g);
}
// show "printable" representation of graph
void  showGraph(Graph)
{
   assert(g != NULL);
   printf("V=%d, E=%d\n", g->nV, g->nE);
   int i;
   for (i = 0; i < g->nV; i++) {
      vNode *n = g->edges[i];
      while (n != NULL) {
         printf("%d-%d ",i,n->v);
         n = n->next;
      }
      if (g->edges[i] != NULL) printf("\n");
   }
}
// add new edge to a graph
void  insertE(Graph g, Edge e)
{
   assert(g != NULL);
   assert(validV(g,e.v) && validV(g,e.w));
   int orig = length(g->edges[e.v]);
   g->edges[e.v] = insertVList(g->edges[e.v], e.w);
   g->edges[e.w] = insertVList(g->edges[e.w], e.v);
   if (length(g->edges[e.v]) > orig) g->nE++;
}
// remove an edge from a graph
void  removeE(Graph g, Edge e)
{
   assert(g != NULL);
   assert(validV(g,e.v) && validV(g,e.w));
   int orig = length(g->edges[e.v]);
   g->edges[e.v] = deleteVList(g->edges[e.v], e.w);
   g->edges[e.w] = deleteVList(g->edges[e.w], e.v);
   if (length(g->edges[e.v]) < orig) g->nE--;
}
// returns #vertices & array of edges
int edges(Graph g, Edge *es, int nE)
{
   VList curr;
   assert(g != NULL && es != NULL);
   assert(nE >= g->nE);
   int w, n = 0;
   for (w = 0; w < g->nV; w++) {
      curr = g->edges[w];
      while (curr != NULL) {
         if (w < curr->v)
            es[n++] = mkEdge(g,w,curr->v);
         curr = curr->next;
      }
   }
   return n;
}

Traversal

Path Checking:

int count;
int *pre;  // array of booleans
               // indexed by vertex 0..V-1
Vertex *st;  // array of Vertices
				// indexed by vertex 0..V-1
// DFS : depth-first search
int hasPath(Graph g, Vertex src, Vertex dest)
{
   int i;
   count = 0;
   pre = malloc(g->nV*sizeof(int));
   for (i = 0; i < g->nV; i++) pre[i] = -1;
   int result = dfsPathCheck(g, src, dest);
   free(pre);
   return result;
}
int dfsPathCheck(Graph g, Vertex v, Vertex dest)
{
   pre[v] = count++;
   Vertex w;
   for (w = 0; w < g->nV; w++) {
      if (g->edges[v][w] && w == dest)
         return 1; // found path
      if (g->edges[v][w] && pre[w] == -1)
         return dfsPathCheck(g, w);
   }
   return 0; // no path from src to dest
}

// BFS : breadth-first search
int hasPath(Graph g, Vertex src, Vertex dest)
{
   count = 0;
   pre = malloc(g->nV*sizeof(int));
   for (i = 0; i < g->nV; i++) pre[i] = -1;
   
   Queue q = newQueue();
   QueueJoin(q,src);
   int isFound = 0;
   while (!QueueIsEmpty(q) && !isFound) {
      Vertex y, x = QueueLeave(q);
      if (pre[x] != -1) continue;
      for (y = 0; y < g->nV; y++) {
         if (!g->edges[x][y]) continue;
         if (y == dest) { isFound = 1; break; }
         if (pre[y] == -1) { QueueJoin(q,y); }
      }
   }
   dropQueue(q);
   free(pre);
   return isFound;
}

Find and Display Shortest Path:

int findPath(Graph g, Vertex src, Vertex dest)
{
   count = 0;
   int i;
   // array of "been visited" flags
   pre = malloc(g->nV * sizeof(int));
   for (i = 0; i < g->nV; i++) pre[i] = -1;
   // array of path predecessor vertices (they form a spanning tree)
   Vertex *st= malloc(g->nV * sizeof(Vertex));
   for (i = 0; i < g->nV; i++) st[i] = -1;
   Queue q = newQueue();
   QueueJoin(q, src); 
   visited[src] = count++;
   int isFound = 0;
   while (!emptyQ(q) && !isFound) {
      Vertex y, x = QueueLeave(q);
      for (y = 0; y < g->nV; y++) {
         if (!g->edges[x][y]) continue;
         st[y] = x;
         if (y == dest) { isFound = 1; break; }
         if (pre[y] == -1) {
            QueueJoin(q, y);
            pre[y] = count++;
         }
      }
   }
   if (isFound) {
      // display path in dest..src order
      Vertex v;
      for (v = dest; v != src; v = st[v])
          printf("%d<-", v);
      printf("%d\n", src);
   }
   free(st);
   free(pew);
   dropQueue(q);
}

Weighted Graphs

Graph Interface:

// visible data structures for Graphs
typedef struct GraphRep *Graph;
// vertices denoted by integers 0..N-1
typedef int Vertex;
// edges are end-points + weight
typedef struct { Vertex src; Vertex dest; float weight; } Edge;
// auxiliary operations on graphs
int validV(Graph,Vertex); // validity check
Edge mkEdge(Graph, Vertex, Vertex, float); // edge creation
int neighbours(Graph, Vertex, Vertex); // edge existence
float compareE(Edge e1, Edge e2); // compare edge weights
// core operations on graphs
// make new graph with nV vertices
Graph newGraph(int nV);
// free memory allocated to graph
void  dropGraph(Graph);
// show "printable" representation of graph
void  showGraph(Graph);
// add new edge to a graph
void  insertE(Graph, Edge);
// remove an edge from a graph
void  removeE(Graph, Edge);
// returns #vertices & array of edges
int   edges(Graph, Edge *, int);

Implementation of Auxiliary Operations:

// is a vertex valid in a given Graph?
static int validV(Graph g, Vertex v)
{
   return (g != NULL && v >= 0 && v < g->nV);
}
// make an Edge value
Edge mkEdge(Graph g, Vertex v, Vertex w)
{
   assert(validV(g,v) && validV(g,w));
   Edge new;
   new.src = src;
   new.dest = dest;
   new.weight = weight;
   return new;
}
// compare Edge weights
int compareE(Edge e1, Edge e2)
{
   return e1.weight - e2.weight;
}

Adjacency Matrix Representation:

// since 0 is a valid weight, can't use it for "no edge"
// need a distinguished value to indicate "no edge"
#define NO_EDGE MAXFLOAT  // imaginary distinguished float value
typedef struct GraphRep {
   int    nV;    // #vertices
   int    nE;    // #edges
   Bool **edges; // matrix of booleans
} GraphRep;
// check whether two vertices are connected
int neighbours(Graph g, Vertex v, Vertex w)
{
	assert(validV(g,v) && validV(g,w));
	return (g->edges[v][w] != NO_EDGE);
}
// make new graph with nV vertices
Graph newGraph(int nV)
{
   assert(nV >= 0);
   int i, j;
   float **e = malloc(nV * sizeof(float *));
   assert(e != NULL);
   for (i = 0; i < nV; i++) {
      e[i] = malloc(nV * sizeof(float));
      assert(e[i] != NULL);
      for (j = 0; j < nV; j++)
         e[i][j] = NO_EDGE;
   }
   Graph g = malloc(sizeof(GraphRep));
   assert(g != NULL);
   g->nV = nV;  g->nE = 0;  g->edges = e;
   return g;
}
// free memory allocated to graph
void  dropGraph(Graph g)
{
   assert(g != NULL);
   int i;
   for (i = 0; i < g->nV; i++)
      free(g->edges[i]);
   free(g->edges);
   free(g);
}
// show "printable" representation of graph
void  showGraph(Graph g)
{
   assert(g != NULL);
   printf("V=%d, E=%d\n", g->nV, g->nE);
   int i, j;
   for (i = 0; i < g->nV; i++) {
      int nshown = 0;
      for (j = i+1; j < g->nV; j++) {
         float wt = g->edges[i][j];
         if (wt != NO_EDGE) {
            printf("%d-%0.1f-%d ",i,wt,j);
            nshown++;
         }
      }
      if (nshown > 0) printf("\n");
   }
}
// add new edge to a graph
void insertE(Graph g, Edge e)
{
   assert(g != NULL);
   Vertex v = e.src, w = e.dest;
   assert(validV(g,v) && validV(g,w));
   if (G->edges[v][w] == NO_EDGE) g->nE++;
   g->edges[v][w] = e.weight;
}
// remove an edge from a graph
void removeE(Graph g, Edge e)
{
   assert(g != NULL);
   Vertex v = e.src, w = e.dest;
   assert(validV(g,v) && validV(g,w));
   if (g->edges[v][w] == NO_EDGE) return;
   g->edges[v][w] = NO_EDGE;
   g->edges[w][v] = NO_EDGE;
   g->nE--;
}
// returns #vertices & array of edges
int edges(Graph g, Edge *es, int nE)
{
   assert(g != NULL && es != NULL);
   assert(nE >= g->nE);
   int i, j, n = 0;
   for (i = 0; i < g->nV; i++) {
      for (j = i+1; j < g->nV; j++) {
         if (g->edges[i][j] != NO_EDGE) {
            assert(n < nE);
            es[n++] = mkEdge(g,i,j);
         }
      }
   }
   return n;
}

Minimum Spanning Tree (Kruskal):

typedef Graph MSTree; // an MST is a specialised Graph
// assumes existence of list-of-edges ADT
MSTree kruskalFindMST(Graph g)
{
   Graph mst = newGraph(); //MST initially empty
   EdgeList eList; //sorted list of edges
   int i;  Edge e;  int eSize = sizeof(Edge);
   edges(eList, g->nE, g);
   eList = qsort(sorted, g->nE, eSize, compareE);
   for (i = 0; mst->nE < g->nV-1; i++) {
      e = eList[i];
      insertE(mst, e);
      if (hasCycle(mst)) removeE(mst, e);
   }
}

Minimum Spanning Tree (Prim):

void prim(Graph g, int st[], float dist[]){
    Vertex v,i;
    PriQ pq = initPriQ(g->nV);
    int * visited = malloc(sizeof(int)*g->nV);
    for(v=0;v < g->nV;v++){
        visited[v] = -1;
        st[v] = -1;
        dist[v] = NO_EDGE; //infinity
        insert(pq,newItem(dist[v],v));
    }
    
    st[0] = 0; 
    dist[0] = 0;   
    increasePriority(pq,0,0);
    while(!isEmpty(pq)){
     
        v = (delMin(pq))->value; 
	    visited[v] = 1;
        for(i=0;inV;i++){
	    if(g->adj[v][i] != NO_EDGE && visited[i] == -1){
	        if(g->adj[v][i] < dist[i]){ 
                       dist[i] = g->adj[v][i];
                       increasePriority(pq,i,dist[i]);
                       st[i] = v;
                }
            }
        }
    }
    free(visited);
}

Single-source Shortest Path (Dijkstra):

void dijkstra(Graph g,Vertex s,int st[],float dist[]){
    int v,t;
    PriQ pq = initPriQ(g->nV);
    //insert each vertex into the pq
    for(v=0;v< g->nV;v++){
        st[v] = -1;
        dist[v] = NO_EDGE; //represents infinity
        Item i = newItem(dist[v],v);
        insert(pq,i);
    } 
    dist[s] = 0.0; //set start veretex dist to 0 
    increasePriority(pq,s,dist[s]); // update pq
    while(!isEmpty(pq)){
         v = value(delMin(pq));
         if(dist[v] != NO_EDGE)
             for(t = 0;t < g->nV;t++){
	         if(g->adj[v][t] != NO_EDGE){
	             if(dist[v] + g->adj[v][t] < dist[t]){                    
	                  dist[t] = dist[v] + g->adj[v][t];
                      increasePriority(pq,t,dist[t]);
                      st[t] = v;
	             }
             }
         }
    }
}