Written by Luka Kerr on June 9, 2018

Doubly Linked List

Reversing List

  1. Swap the head and tail pointers, and set current to the new head
  2. Untill current isn’t NULL, swap next and previous values, and reset current to the new current->next (current->prev)
/*
  L: NULL<-1-><-2-><-3-><-4-><-5->NULL
*/

// If list is empty
if (L->head == NULL) {
  return;
}

Node tmp = L->head;
L->head = L->tail;
L->tail = tmp;
Node current = L->head;

while(current != NULL) {
  tmp = current->next;
  current->next = current->prev;
  current->prev = tmp;
  current = current->next;
}

Removing Value From List

  1. First check if list is null. If so, return
  2. Next iterate over the list and check whether the current value is equal to the value to remove
  3. If it is, we have 3 conditions:
    1. The current value is the head node
      • If there is a next node, set its previous pointer to the current’s previous node
      • If there is not a next node, set the head and tail both to NULL (emptying the list, since there is only one node to be removed)
    2. The current value is the tail node
      • If there is a previous node, set its next pointer to the currents next node
      • If there is not a previous node, set the head and tail both to NULL (emptying the list, since there is only one node to be removed)
    3. The current value is somewhere in the middle
      • Set the previous node’s next pointer to the current’s next node
      • Set the next node’s previous pointer to the current’s previous node
  4. Update the current node
/*
  to_remove: 2
  L: NULL<-1-><-2-><-3-><-2-><-5->NULL
*/

// If list is empty
if (L->head == NULL) {
  return;
}

// Set current to the first node
Node current = L->head;

// Iterate over the list
while(current != NULL) {
  // Value is the same as the value to be removed
  if (current->value == to_remove) {
    if (current == L->head) {
      if (current->next != NULL) {
        current->next->prev = current->prev;
      } else {
        L->head = NULL;
        L->tail = NULL;
      }
    } else if (current == L->tail) {
      if (current->prev != NULL) {
        current->prev->next = current->next;
      } else {
        L->head = NULL;
        L->tail = NULL;
      }
    } else {
      // If this condition is reached, there are at least a head and tail
      // so the current node must be in the middle somewhere
      current->prev->next = current->next;
      current->next->prev = current->prev;
    }
  }
  current = current->next;
}

Sorting

Properties

Selection Sort

// a[] is the array to sort, n is the number of items in a[]
void selectionSort(int a[], int n) {
  for (int i = 0; i < n-1; i++) {
    int min = i;
    for (int j = i+1; j < n; j++) {
      if (a[j] < a[min]) {
        min = j;
      }
    }
    swap(a[i], a[min]);
  }
}

Bubble Sort

// a[] is the array to sort, n is the number of items in a[]
void bubbleSort(int a[], int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {
      if (a[j] > a[j+1]) {
        swap(a[j], a[j+1]);
      }
    }
  }
}

Insertion Sort

// a[] is the array to sort, n is the number of items in a[]
void insertionSort(int a[], int n) {
  for (int i = 1; i < n; i++) {
    int backup = a[i];
    int j;

    for (j = i; j > 0; j--) {
      if (backup > a[j-1]) break;
      a[j] = a[j-1];
    }
    a[j] = backup;
  }
}

Shell Sort

void shellSort(int a[], int lo, int hi) {
  int hvals[8] = {701, 301, 132, 57, 23, 10, 4, 1};

  for (int g = 0; g < 8; g++) {
    int h = hvals[g];
    int start = lo + h;
    for (int i = start; i < hi; i++) {
      int val = a[i];
      for (int j = i; j >= start && less(val,a[j-h]); j -= h) {
        move(a, j, j-h);
      }
      a[j] = val;
    }
  }
}

Quicksort

void quicksort(Item a[], int lo, int hi) {
  int i; // index of pivot
  if (hi <= lo) return;
  i = partition(a, lo, hi);
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}

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;
}

Generics

Function pointers are used to pass a function with parameters into another function

// takes in a pointer to a function that takes one parameter: a void *
void func(void *n, void (*fp) (void *)) {
  // use the function, passing in "n" - a void *
  fp(n)
}

An more concrete example:

// generic min function
void *min(void *el, void *el2, int (*compare) (void *, void *)) {
  if (compare(el, el2)) {
    return el;
  }
  return el2;
}

// compares two elements, takes in two void *
// converts them to integers and compares them
int cmp(void *item, void *item2) {
  return (*(int*)item < *(int*)item2);
}

int main(void) {
  int el = 5;
  int el2 = 20;
  int minimum = *(int*)min(&el, &el2, cmp);
  printf("min = %d\n", minimum); // prints 5;
}

Trees

Tree Data Structures

Binary Search Tree

Properties

typedef struct Node *BST;
typedef struct Node {
  int data;
  BST left, right;
} Node;

Splay Trees

Properties

tree1

AVL Trees

Properties

2-3-4 Trees

Properties

typedef struct Node {
  int order; // 2, 3 or 4
  int data[3]; // items in node
  struct Node *child[4]; // links to children
} Node;

tree2

Red-Black Trees

Properties

tree3

Tree Algorithms

Counting Nodes

To count nodes, we can use recursion:

int count(BSTree t) {
  if (t == NULL) {
    return 0
  } else {
    return 1 + count(t->left) + count(t->right);
  }
}

This algorithm can be modified to count different characteristics of the tree, such as number of odd nodes:

int countOdd(BSTree t) {
  if (t == NULL) {
    return 0
  } else {
    // if odd ret = 1, if even ret = 0
    int ret = (t->data % 2);
    return ret + countOdd(t->left) + countOdd(t->right);
  }
}

Counting Leaves

To count the number of leaves, we can use recursion:

int BSTreeNumLeaves(BSTree t) {
  // base case
  if (t == NULL) {
    return 0;
  }
  // if left and right are NULL, the node is a leaf
  if ((t->left == NULL) && (t->right == NULL)) {
    return 1;
  }
  int numleft = BSTreeNumLeaves(t->left);
  int numright = BSTreeNumLeaves(t->right);
  return (numleft + numright);
}

Finding A Node

To find a node, we can use recursion:

int BSTreeFind(BSTree t, int v) {
  if (t == NULL) { // base case: value doesn't exist in tree
    return 0;
  } else if (v < t->value) { // value is less, search on the left hand side
    return BSTreeFind(t->left, v);
  } else if (v > t->value) { // value is more, search on the right hand side
    return BSTreeFind(t->right, v);
  } else // found the value
    return 1;
}

Tree Traversal

Infix Order (LNR)

Visit left, root, right

void BSTreeInfix(BSTree t) {
  if (t == NULL) {
    return;
  }
  BSTreeInfix(t->left);
  showBSTreeNode(t);
  BSTreeInfix(t->right);
}

Postfix Order (LRN)

Visit left, right, root

void BSTreePostfix(BSTree t) {
  if (t == NULL) {
    return;
  }
  BSTreePostfix(t->left);
  BSTreePostfix(t->right);
  showBSTreeNode(t);
}

Prefix Order (NLR)

Visit root, left, right

void BSTreePrefix(BSTree t) {
  if (t == NULL) {
    return;
  }
  showBSTreeNode(t);
  BSTreePrefix(t->left);
  BSTreePrefix(t->right);
}

Tree Rotations

Left Rotation

function rotateLeft(Tree n1):
  if n1 is empty or right(n1) is empty:
    return n1

  Tree n2 = right(n1)
  right(n1) = left(n2)
  left(n2) = n1
  return n2

Right Rotation

function rotateRight(Tree n1):
  if n1 is empty or left(n1) is empty:
    return n1

  Tree n2 = left(n1)
  left(n1) = right(n2)
  right(n2) = n1
  return n2

Graphs

Graph Data Structures

Properties of a Graph

Terminology

graph2

graph3

graph1

graph4

Array of Edges

Properties

graph5

ADT

typedef struct GraphRep {
  Edge *edges; // array of edges
  int nV;      // #vertices (numbered 0..nV-1)
  int nE;      // #edges
  int n;       // size of edge array
} GraphRep;

Adjacency Matrix

Properties

graph6

ADT

typedef struct GraphRep {
  int **edges; // adjacency matrix
  int nV;      // #vertices
  int nE;      // #edges
} GraphRep;

Adjacency List

Properties

graph7

ADT

typedef struct GraphRep {
  Node **edges;  // array of lists
  int nV;        // #vertices
  int nE;        // #edges
} GraphRep;

typedef struct Node {
  Vertex v;
  struct Node *next;
} Node;

Graph Algorithms

Finding A Path

Steps:

Can be achieved with a depth first search or breadth first search.

// array of visited
int *visited;

int DFS(Graph g, int v, int dest) {
  // set the vertex to visited
  visited[v] = 1;

  // for each vertex in the graph
  for (int w = 0; w < g->nV; w++) {
    // if the given vertex (v) is adjacent to the current vertex (w)
    // and it hasn't been visited
    if (adjacent(g, v, w) && visited[w] == 0) {
      // set it to visited
      visited[w] = 1;

      // if w is the dest, return true
      if (w == dest) {
        return 1;
      } else if (DFS(g, w, dest)) {
        return 1;
      }
    }
  }
  return 0;
}

int hasPath(Graph g, Vertex src, Vertex dest) {
  // first check if src and dest are connected by an edge
  if (adjacent(g, src, dest)) {
    return 1;
  }

  // sets all in visited to 0
  visited = calloc(g->nV, sizeof(int));

  // perform depth first search
  int exists = DFS(g, src, dest);

  free(visited);

  return exists;
}

Find And Dispay Shortest Path

void findPath(Graph g, Vertex src, Vertex dest) {
  // array of visited
  int *visited = calloc(g->nV, sizeof(int));

  // array of path predecessor vertices
  Vertex *path = malloc(g->nV * sizeof(Vertex));

  Queue q = newQueue();
  QueueJoin(q, src);
  visited[src] = 1;

  int isFound = 0;

  // while queue not empty and vertex dest not found
  while (!emptyQ(q) && !isFound) {
    Vertex y, x = QueueLeave(q);
    for (y = 0; y < g->nV; y++) {
      if (!g->edges[x][y]) {
        continue;
      }
      path[y] = x;
      if (y == dest) {
        isFound = 1;
        break;
      }
      if (!visited[y]) {
        QueueJoin(q, y);
        visited[y] = 1;
      }
    }
  }

  if (isFound) {
    // display path in dest..src order
    for (Vertex v = dest; v != src; v = path[v]) {
      printf("%d<-", v);
    }
    sprintf("%d\n", src);
  }
}

Dijkstra’s Algorithm

dist[]  // array of cost of shortest path from source
pred[]  // array of predecessor in shortest path from source

function Dijkstra(Graph, source):

  vSet = all vertices of Graph

  for each vertex v in Graph:
    dist[v] = INFINITY
    pred[v] = -1

  dist[source] = 0

  while vSet is not empty:
    u = vertex in vSet with min dist[u]
    remove u from vSet

    for each neighbor v of u:
      alt = dist[u] + length(u, v)
      if alt < dist[v]:
        dist[v] = alt
        pred[v] = u

  return dist[], pred[]

Hamilton Path

int *visited; // array of nV bools
int hamiltonPath(Graph g, Vertex v, Vertex w, int d) {
  if (v == w) return (d == 0) ? 1 : 0;
  visited[v] = 1;

  for (int t = 0; t < g->nV; t++) {
    if (!neighbours(g, v, t)) continue;
    if (visited[v] == 1) continue;
    if (hamiltonPath(g, t, w, d-1)) return 1;
  }

  visited[v] = 0;
  return 0;
}

int hasHamiltonPath(Graph g, Vertex src, Vertex dest) {
  visited = calloc(g->nV, sizeof(int));
  int res = hamiltonPath(g, src, dest, g->nV-1);
  free(visited);
  return res;
}

Well Connected

/*
  Adjacency Matrix implementation
*/
int wellConnected(Graph g) {
  // create an int[] that holds the count of connections per vertex
  int *connections = calloc(g->nV, sizeof(int));

  // iterate over each vertex, and if an edge between i and j exists, increment
  // the connection count for i
  for (int i = 0; i < g->nV; i++) {
    for (int j = 0; j < g->nV; j++) {
      if (g->edges[i][j]) {
        connections[i]++;
      }
    }
  }

  // for each vertex, if the connection count is 2 or more, increment the total
  // well connected count, and return it
  int count = 0;
  for (int i = 0; i < g->nV; i++) {
    if (connections[i] >= 2) {
      count++;
    }
  }
  return count;
}

void depthFirst(Graph g, int src) {
  int *visited = calloc(g->nV,sizeof(int));

  // create a stack and add src to it
  Stack s = newStack();
  StackPush(s, src);

  // while the stack is not empty, pop the top vertex off and visit it
  while (!StackEmpty(s)) {
    Vertex y, x = StackPop(s);

    if (visited[x]) continue;
    visited[x] = 1;

    // push all of the neighbors onto the stack if not visited already
    for (y = g->nV-1; y >= 0; y--) {
      if (!g->edges[x][y]) continue;
      if (!visited[y]) StackPush(s,y);
    }
  }
}

void breadthFirst(Graph g, Vertex src) {
  int *visited = calloc(g->nV,sizeof(int));

  // create a queue and add the src to it
  Queue q = newQueue();
  QueueJoin(q, src);

  // while the queue is not empty, remove the FIFO element from the queue and visit it
  while (!QueueEmpty(q)) {
    Vertex y, x = QueueLeave(q);

    if (visited[x]) continue;
    visited[x] = 1;

    // add each of the neighbors to the queue if not already visited
    for (y = 0; y < g->nV; y++) {
      if (!g->edges[x][y]) continue;
      if (!visited[y]) QueueJoin(q,y);
    }
  }
}

Heaps

Properties

Insertion

Deletion

Algorithms

Check if a binary tree is a heap

int isHeap(BTree t) {
  if (t == null) {
    return 1;
  }

  int leftHeap = isHeap(t->left);
  int rightHeap = isHeap(t->right);

  int isHeap = 1;

  // check for each node that its value is greater than its children nodes
  // for a min-heap, check for less than
  if (t->left != NULL) {
    if (t->value < t->left->value) {
      isHeap = 0;
    }
  }
  if (t->right != NULL) {
    if (t->value < t->right->value) {
      isHeap = 0;
    }
  }

  // returns 1 if heap, 0 otherwise
  return (isHeap && leftHeap && rightHeap);
}

Hash Tables

Properties

Seperate Chaining

Linear Probing

Double Hashing

function insert(HashTable ht, Item it):
  n = size(ht)
  key = key(it)

  // generate initial hash and second hash
  h = hash(key, n)
  inc = hash2(key, hash2(ht))

  // loop over hash table, incrementing by inc after each iteration
  for j = 0; j < n; j += inc:
    ix = (h + j) % n
    if ht[ix] == Empty:
      ht[ix] = it
      return

Text Processing Algorithms

Pattern Matching Algorithms

Given two strings $T$ (text) and $P$ (pattern), the pattern matching problem consists of finding a substring in $T$ equal to $P$.

Brute Force

Boyer-Moore Algorithm

text1

c a b c d
L(c) 2 3 1 -1

text6

Knuth-Morris-Pratt Algorithm

text2

$j$ 0 1 2 3 4 5
$P_j$ a b a a b a
$F(j)$ 0 0 1 1 2 3

Tries

#define ALPHABET_SIZE 26
typedef char *Key;
typedef struct Node *Trie;
typedef struct Node {
  bool finish;
  char data;
  Trie child[ALPHABET_SIZE];
} Node;

text3

Compressed Tries

text4

Text Compression

Huffman Coding

text5