C 語言 O(1) 查表法巧解字元對應：ASCII 碼直接定址技巧

C 語言 O(1) 查表法巧解字元對應：ASCII 碼直接定址技巧

核心思想

字元型別 char 僅 256 種可能值 (0~255)。預先建立長度 256 的陣列，以字元 ASCII 碼為索引，存放對應結果。查找時直接 table[ch]，時間複雜度 O(1)。

範例：小寫字母映射為逆序大寫

輸入 'a' 輸出 'Z'，'b'→'Y' ... 'z'→'A'。

程式碼實作

#include <stdio.h>

void build_table(char table[256]) {
    for (int i = 0; i < 256; ++i) table[i] = 0; // 初始化
    char upper = 'Z';
    for (char c = 'a'; c <= 'z'; ++c) {
        table[(unsigned char)c] = upper--;
    }
}

int main() {
    char table[256];
    build_table(table);

    int ch = getchar();
    if (ch != EOF) {
        putchar(table[(unsigned char)ch]);
    }
    return 0;
}

應用場景

• 字元分類 (是否數字、字母、空白)。
• 編碼轉換 (如 ROT13、大小寫翻轉)。
• 關鍵字/保留字快速查找 (編譯器前端)。
• 簡易哈希表雛形：鍵空間小且連續時極高效。

注意事項

• 索引轉型 (unsigned char) 避免 char 有號擴展導致負索引。
• 空間換時間：256 位元組極小，現代系統完全可接受。
• 若鍵空間大 (如 Unicode)，改用真正哈希表。

此技巧是「空間換時間」經典案例，也是哈希表思想的最簡形式。