Standard trie — words and prefixes

#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 MAX_WORDS 100
#define MAX_LENGTH 50
#define MAX_NODES (1 + MAX_WORDS * MAX_LENGTH)
typedef struct Node { struct Node *child[26]; int terminal; } Node;
Node pool[MAX_NODES]; int used = 1, count = 0;
Node *root = &pool[0];

Each node has 26 letter links and a terminal marker. The pool is large enough for root plus the maximum allowed characters across 100 words of at most 50 letters each. Static storage begins zero-initialised.

int validWord(const char word[]) {
    if (!word[0]) return 0;
    for (int i = 0; word[i]; ++i) if (word[i] < 'a' || word[i] > 'z') return 0;
    return 1;
}

Reject an empty string or any character outside a through z. Return 1 only after every character passes; later child indexes therefore stay within 0–25.

const Node *follow(const char word[]) {
    const Node *p = root;
    for (int i = 0; word[i]; ++i) {
        p = p->child[word[i] - 'a']; if (!p) return NULL;
    }
    return p;
}

Starting at root, map each letter to word[i] - 'a' and follow its child. A missing child returns NULL. Otherwise return the final node, whose terminal flag can distinguish a whole word from a prefix.

void insert(const char word[]) {
    Node *p = root;
    for (int i = 0; word[i]; ++i) {
        int index = word[i] - 'a';
        if (!p->child[index]) p->child[index] = &pool[used++];
        p = p->child[index];
    }

For each letter obtain its 0–25 index. Allocate a zero-initialised pool entry only when that child link is absent, then advance p. Shared prefixes therefore share the same nodes.

    p->terminal = 1; ++count;
}

Set terminal at the final node and increase the distinct-word count. The driver avoids calling insert for an already terminal word.

/* 1 word: insert, 2 word: exact search, 3 prefix: prefix check, 0: exit.
   Nonempty lowercase a-z tokens, length at most 50; 100 distinct words. */
int main(void) {
    int command; char word[MAX_LENGTH + 1];
    while (readInt(&command)) {
        if (!command) return 0;
        if (command < 1 || command > 3 || !readToken(word,sizeof word) || !validWord(word)) return invalid();

The interface supports insert, exact search and prefix check. main validates the command, token capacity and lowercase rule before using any character as a child index. Word input is a token, not a line with spaces.

        const Node *p = follow(word);
        if (command == 2) puts(p && p->terminal ? "Found." : "Not found.");
        else if (command == 3) puts(p ? "Prefix exists." : "Prefix absent.");

follow can return a node for a prefix that was never inserted as a whole word. Exact search therefore needs both p and p->terminal. Prefix check needs only the path node p.

        else if (p && p->terminal) puts("Duplicate ignored.");
        else if (count == MAX_WORDS) puts("Trie is full.");
        else { insert(word); puts("Inserted."); }
    }
    return invalid();
}

An existing terminal path is a duplicate. Otherwise reject a full trie or create the new word. End-of-input without command 0 returns failure; the static pool requires no heap cleanup.