Collision resolution — separate chaining

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define SIZE 11
typedef struct Node { int key; struct Node *next; } Node;
Node *table[SIZE];

The table has 11 bucket pointers, initially NULL in static storage. Each Node stores one key and its next node in that bucket’s chain.

int insert(int key) {
    int index = key % SIZE;
    for (Node *p = table[index]; p; p = p->next) if (p->key == key) return 2;

Hash by key % SIZE. Follow only that bucket’s linked list, returning status 2 if the same key is already present.

    Node *p = malloc(sizeof *p); if (!p) return 0;
    p->key = key; p->next = table[index]; table[index] = p; return 1;
}

Return 0 if malloc fails, leaving the existing chain untouched. Otherwise store key, link p to the old bucket head, then make p the new head and return 1. Colliding keys share a chain rather than probing other buckets.

void display(void) {
    for (int i = 0; i < SIZE; ++i) {
        printf("%d:",i); for (Node *p = table[i]; p; p = p->next) printf(" %d",p->key);
        if (!table[i]) printf(" _");
        putchar('\n');
    }
}

For each index print its label, then traverse and print its keys. An empty bucket shows an underscore. New keys appear first within their bucket because insertion prepends them.

void destroy(void) {
    for (int i = 0; i < SIZE; ++i) {
        Node *p = table[i]; while (p) { Node *next = p->next; free(p); p = next; }
        table[i] = NULL;
    }
}

For each bucket save the next link before freeing the current node, then continue. After a chain is released set its table entry to NULL.

int main(void) {
    int n, key; if (!readInt(&n) || n < 0 || n > 100) return invalid();
    if (!n) display();

Require n from 0 to 100. If no insertion is requested, display the empty bucket structure once.

    for (int i = 0; i < n; ++i) {
        if (!readInt(&key) || key < 0) { destroy(); return invalid(); }
        int result = insert(key);
        puts(result == 2 ? "Duplicate ignored." : result ? "Inserted." : "Allocation failed; table unchanged.");
        display();

A bad key triggers destroy before returning invalid input. A valid key receives duplicate, success or allocation-failure text, followed by a complete table display.

    }
    destroy(); return 0;
}

Destroy the chains and return success. Fixed bucket pointers do not automatically free the heap nodes they identify.