Unit 1: Data structure implementation

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

cint binRec(int a[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;
    return key < a[mid] ? binRec(a, low, mid - 1, key) : binRec(a, mid + 1, high, key);
}

cstruct node { char word[30]; struct node *left, *right; };
struct node *insert(struct node *t, const char *w) {
    if (t == NULL) {
        t = malloc(sizeof *t); strcpy(t->word, w); t->left = t->right = NULL;
    } else if (strcmp(w, t->word) < 0) t->left = insert(t->left, w);
    else if (strcmp(w, t->word) > 0) t->right = insert(t->right, w);
    return t;
}
void inorder(struct node *t) {                 /* prints words in dictionary order */
    if (t) { inorder(t->left); printf("%s\n", t->word); inorder(t->right); }
}
struct node *search(struct node *t, const char *w) {
    while (t && strcmp(w, t->word)) t = strcmp(w, t->word) < 0 ? t->left : t->right;
    return t;
}

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

cvoid heapify(int a[], int n, int i) {          /* max-heap; flip comparisons for min-heap */
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) { int t = a[i]; a[i] = a[largest]; a[largest] = t; heapify(a, n, largest); }
}
void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);       /* build heap */
    for (int i = n - 1; i > 0; i--) {
        int t = a[0]; a[0] = a[i]; a[i] = t;                     /* move max to end */
        heapify(a, i, 0);
    }
}

c/* coefficient array: p[i] is the coefficient of x^i */
void addPoly(int p[], int q[], int r[], int deg) {
    for (int i = 0; i <= deg; i++) r[i] = p[i] + q[i];
}
void printPoly(int r[], int deg) {
    for (int i = deg; i >= 0; i--) if (r[i]) printf("%+dx^%d ", r[i], i);
}
/* (3x^2 + 2x + 5) + (x^2 - 4) → 4x^2 + 2x + 1 */

• 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++];

cvoid swapVal(int a, int b) { int t = a; a = b; b = t; }      /* caller unchanged */
void swapRef(int *a, int *b) { int t = *a; *a = *b; *b = t; } /* caller swapped */

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.

c/* Reverse a singly linked list */
struct node *reverse(struct node *head) {
    struct node *prev = NULL, *next;
    while (head) { next = head->next; head->next = prev; prev = head; head = next; }
    return prev;
}
/* Update: change the first occurrence of old to new */
void update(struct node *h, int old, int new) { for (; h; h = h->next) if (h->data == old) { h->data = new; return; } }

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

c/* Three queues for priorities 1 (high), 2 and 3; dequeue serves the highest non-empty queue */
#define N 10
int q[3][N], f[3] = {0, 0, 0}, r[3] = {-1, -1, -1};
void enqueue(int item, int pr) {
    if (r[pr - 1] == N - 1) { printf("Queue %d full\n", pr); return; }
    q[pr - 1][++r[pr - 1]] = item;
}
int dequeue(void) {
    for (int p = 0; p < 3; p++)
        if (f[p] <= r[p]) return q[p][f[p]++];
    printf("All queues empty\n"); return -1;
}

• Store the graph as an adjacency matrix int adj[MAX][MAX] and keep a visited[] array.
• DFS: recursive — mark the vertex visited, print it and call DFS on each unvisited neighbour.
• BFS: use a queue — enqueue the start vertex; repeatedly dequeue, print and enqueue unvisited neighbours.
• Dijkstra: keep dist[], pick the unvisited vertex with minimum distance each round and relax its neighbours.

c#include <time.h>
clock_t start = clock();
quickSort(a, 0, n - 1);                      /* algorithm under test */
double secs = (double)(clock() - start) / CLOCKS_PER_SEC;
printf("n = %d, time = %.4f s, comparisons = %ld\n", n, secs, comparisons);

• Run each algorithm for n = 1,000, 10,000 and 100,000 on random, sorted and reverse-sorted data, count comparisons with a global counter, and plot time against n to confirm O(n²) versus O(n log n) growth.