Home » Codes » C » C Top Codes

C Top Codes

C Linked List Program

A linked list stores data in nodes. Each node has a value and a pointer to the next node, so the nodes can be anywhere in memory. This program creates a list, prints it, deletes a value and frees all the memory.

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *insertEnd(struct Node *head, int value) {
    struct Node *node = malloc(sizeof(struct Node));
    node->data = value;
    node->next = NULL;

    if (head == NULL) return node;

    struct Node *p = head;
    while (p->next != NULL) p = p->next;
    p->next = node;
    return head;
}

void display(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next) {
        printf("%d -> ", p->data);
    }
    printf("NULL\n");
}

struct Node *deleteValue(struct Node *head, int value) {
    struct Node *prev = NULL, *p = head;

    while (p != NULL && p->data != value) {
        prev = p;
        p = p->next;
    }
    if (p == NULL) return head;          // not found

    if (prev == NULL) head = p->next;    // first node
    else prev->next = p->next;
    free(p);
    return head;
}

void freeList(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    struct Node *head = NULL;

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);
    display(head);

    head = deleteValue(head, 20);
    display(head);

    freeList(head);
    return 0;
}

Output:

Output of the above program is

10 -> 20 -> 30 -> NULL
10 -> 30 -> NULL

How it works

  • insertEnd() creates a node with malloc() and adds it after the last node.
  • deleteValue() finds the node, links the previous node to the next one, and frees the deleted node.
  • freeList() frees every node, so there is no memory leak.
Note: The functions return the head, because the head can change (for example when the first node is deleted). Related: Structures, Dynamic Memory Allocation and Pointer to Structure.

C Binary Search Program

Binary search finds a value in a sorted array. It checks the middle element and throws away half of the array each time, so it is much faster than linear search for big arrays.

#include <stdio.h>

int binarySearch(int a[], int size, int key) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main(void) {
    int a[] = {5, 12, 19, 27, 33, 48, 56, 71};
    int size = sizeof(a) / sizeof(a[0]);

    int pos = binarySearch(a, size, 33);
    if (pos != -1) printf("33 found at index %d\n", pos);

    pos = binarySearch(a, size, 40);
    if (pos == -1) printf("40 not found\n");
    return 0;
}

Output:

Output of the above program is

33 found at index 4
40 not found

How it works

  • The array must be sorted in ascending order.
  • If the middle value is smaller than the key, the key can only be in the right half. Otherwise it is in the left half.
  • For 8 elements it needs at most 4 steps. For 1 million elements it needs only about 20 steps.
Note: We write low + (high - low) / 2 instead of (low + high) / 2, to avoid an integer overflow for very big arrays. Related: C Arrays and Functions.

C Student Records Program Using Structure and File

This program saves the records of students in a file with fwrite(), and then reads them back with fread(). A structure keeps the data of one student. A binary file stores the structure as it is in memory.

#include <stdio.h>

struct Student {
    int roll;
    char name[20];
    float marks;
};

int main(void) {
    struct Student list[3] = {
        {1, "Robin", 85.5f},
        {2, "Maria", 92.0f},
        {3, "John", 78.5f}
    };
    struct Student s;

    // write the records
    FILE *fp = fopen("records.dat", "wb");
    if (fp == NULL) {
        printf("Cannot open the file\n");
        return 1;
    }
    fwrite(list, sizeof(struct Student), 3, fp);
    fclose(fp);

    // read the records back
    fp = fopen("records.dat", "rb");
    if (fp == NULL) return 1;

    printf("Roll  Name    Marks\n");
    while (fread(&s, sizeof(struct Student), 1, fp) == 1) {
        printf("%-5d %-7s %.1f\n", s.roll, s.name, s.marks);
    }
    fclose(fp);
    return 0;
}

Output:

Output of the above program is

Roll Name Marks
1 Robin 85.5
2 Maria 92.0
3 John 78.5

How it works

  • fwrite(ptr, size, count, file) writes count items of size bytes each.
  • fread() returns the number of items read, so the loop stops at the end of the file.
  • The mode "wb" and "rb" means binary write and read.
Note: The binary file is not readable in a text editor, and it can differ on another computer (because of padding and byte order). For files to share, use text files. Related: File Handling and Structures.

C Stack Program Using Array

A stack follows the rule “last in, first out” (LIFO). The last item which is pushed is the first one to come out, like a pile of plates. Here we make a stack with an array.

#include <stdio.h>

#define MAX 5

int stack[MAX];
int top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack[++top] = value;
}

int pop(void) {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack[top--];
}

int peek(void) {
    return (top == -1) ? -1 : stack[top];
}

int main(void) {
    push(10);
    push(20);
    push(30);

    printf("Top element: %d\n", peek());
    printf("Popped: %d\n", pop());
    printf("Popped: %d\n", pop());
    printf("Top element: %d\n", peek());

    pop();
    pop();     // stack is empty now
    return 0;
}

Output:

Output of the above program is

Top element: 30
Popped: 30
Popped: 20
Top element: 10
Stack underflow

How it works

  • top is the index of the last item. It is -1 when the stack is empty.
  • push() increases top and stores the value. pop() returns the value and decreases top.
  • We check top before each operation, to avoid overflow (full stack) and underflow (empty stack).
Note: Stacks are used in function calls, undo operations and checking the brackets of an expression. Related: C Arrays and Functions.

C Matrix Multiplication Program

To multiply matrix A (r1 x c1) with matrix B (c1 x c2), the number of columns of A must be equal to the number of rows of B. The result has r1 rows and c2 columns. Each element is the sum of the products of a row of A and a column of B.

#include <stdio.h>

int main(void) {
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int b[3][2] = {{7, 8}, {9, 10}, {11, 12}};
    int result[2][2] = {{0, 0}, {0, 0}};

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            printf("%4d", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Output:

Output of the above program is

58 64
139 154

How it works

  • The first element is 1*7 + 2*9 + 3*11 = 58.
  • The loop i goes through the rows of A, j through the columns of B, and k adds the products.
  • The result matrix must start with zeros, because we use +=.
Note: The time taken is proportional to r1 x c2 x c1, so it grows fast for big matrices. Related: Two Dimensional Arrays and Nested Loops.