C 語言去重字符串集合：排序法與二叉樹法對比

問題背景

給定字符串數組，去除重複項並保持原始輸入順序。C 標準庫無現成 Map/Set，需自行實現。

方案一：排序 + 標記法

數據結構

struct Node {
    const char *sorted_str;   // 排序用副本
    const char *original_str; // 原始指針
    int tag;                  // 1=保留 0=刪除
    struct Node *self;        // 指向原始位置
};

流程

1. 構建結構體數組，self 指向自身
2. 按 sorted_str 冒泡排序
3. 排序過程中比較相鄰元素，相同則將後者 tag=0
4. 最終遍歷原始順序（通過 self 鏈），輸出 tag=1 的項

關鍵代碼

int cmp_node(void *a, void *b) {
    Node *n1 = (Node*)a, *n2 = (Node*)b;
    int res = strcmp(n1->sorted_str, n2->sorted_str);
    if (res == 0) n2->self->tag = 0; // 標記刪除
    return res;
}

void swap_node(void *a, void *b) {
    Node *n1 = (Node*)a, *n2 = (Node*)b, *tmp = n1->self;
    const char *ts = n1->sorted_str;
    n1->sorted_str = n2->sorted_str; n1->self = n2->self;
    n2->sorted_str = ts; n2->self = tmp;
}

方案二：二叉搜索樹去重

樹節點

struct TreeNode {
    struct StrNode *str_node; // 指向原始數組元素
    struct TreeNode *left, *right;
};

插入邏輯

TreeNode* add_node(TreeNode *root, StrNode *new_node, cmp_fn cmp) {
    if (!root) {
        root = calloc(1, sizeof(TreeNode));
        root->str_node = new_node;
        return root;
    }
    int r = cmp(new_node, root->str_node);
    if (r == 0) { new_node->tag = 0; return root; } // 重複標記
    if (r < 0) root->left = add_node(root->left, new_node, cmp);
    else root->right = add_node(root->right, new_node, cmp);
    return root;
}

特點

• 插入即去重，無需額外排序遍歷
• 平均 O(n log n)，退化 O(n²)；可升級為 AVL/紅黑樹保證平衡
• 原始數組順序天然保留，最後按 tag 輸出

工程建議

• 教學/嵌入式無 STL 環境可用上述手寫實現
• 生產代碼優先用成熟庫（uthash, glib, C++ STL unordered_set）
• 海量數據考慮外排序或布隆過濾器預過濾

摘自 黎明的豐收