Unit 1: Data structure implementation

cint fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
int fib(int n)  { return n <= 1 ? n : fib(n - 1) + fib(n - 2); }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, via, to, from);
}

• Insert at position pos: shift elements right from the end, then place the item and increase n.
• Delete at position pos: shift elements left from pos + 1 and decrease n.
• Matrix multiplication: possible only if columns of A = rows of B.

cfor (i = 0; i < m; i++)
    for (j = 0; j < p; j++) {
        c[i][j] = 0;
        for (k = 0; k < n; k++)
            c[i][j] += a[i][k] * b[k][j];
    }

c/* Merge two sorted arrays a[m] and b[n] into c[] */
int i = 0, j = 0, k = 0;
while (i < m && j < n) c[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
while (i < m) c[k++] = a[i++];
while (j < n) c[k++] = b[j++];

cint linear(int a[], int n, int key) {
    for (int i = 0; i < n; i++) if (a[i] == key) return i;
    return -1;
}
int binary(int a[], int n, int key) {      /* a[] must be sorted */
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

cvoid bubble(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
}
void insertion(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}
int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}
void quick(int a[], int lo, int hi) {
    if (lo < hi) { int p = partition(a, lo, hi); quick(a, lo, p - 1); quick(a, p + 1, hi); }
}

c#define MAX 50
int stack[MAX], top = -1;
void push(int x) { if (top == MAX - 1) printf("Overflow"); else stack[++top] = x; }
int pop() { if (top == -1) { printf("Underflow"); return -1; } return stack[top--]; }

Postfix evaluation: for each symbol, if it is a digit push it; if it is an operator, pop b then a, compute a op b and push the result.

• Recursive factorial: long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
• Circular queue with modulo arithmetic:

cint q[MAX], front = -1, rear = -1;
void enqueue(int x) {
    if ((rear + 1) % MAX == front) { printf("Queue full"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    q[rear] = x;
}

cstruct node { int data; struct node *next; };
struct node *start = NULL;

void insert_begin(int x) {
    struct node *t = malloc(sizeof(struct node));
    t->data = x;
    t->next = start;
    start = t;
}
void delete_begin() {
    if (start == NULL) { printf("Underflow"); return; }
    struct node *t = start;
    start = start->next;
    free(t);
}

• Doubly linked list nodes add a prev pointer; when inserting, update both neighbours' links.
• Circular list creation: the last node's next points to start; traversal stops when the pointer comes back to start.