C 語言移除字串集合重複元素：排序法與二元樹法

問題描述

給定字串陣列，移除重複項並保留原始輸入順序。C 標準庫無現成 Set/Map，需自行實作。

方法一：排序 + 標記法

1. 建立結構體陣列，含：排序用字串、原始字串、原始索引、刪除標記。
2. 以冒泡排序（或 qsort）按字串排序。
3. 排序過程中比較相鄰元素，若相同則標記後者為刪除。
4. 最後按原始索引順序輸出未被標記者。

struct Item {
    const char *sort_key;   // 排序鍵值
    const char *orig_str;   // 原始字串
    int         orig_idx;   // 原始順序
    int         tag;        // 1=保留, 0=刪除
    struct Item *self;      // 指向原始陣列元素
};

int cmp(void *a, void *b) {
    Item *x = (Item*)a, *y = (Item*)b;
    int r = strcmp(x->sort_key, y->sort_key);
    if (r == 0) y->self->tag = 0; // 標記重複
    return r;
}
void swap(void *a, void *b) { /* 交換 sort_key 與 self 指標 */ }
// 排序後遍歷原始陣列，tag==1 者輸出

方法二：二元搜尋樹 (BST) 插入去重

1. 定義樹節點含字串指標與刪除標記。
2. 插入時先搜尋：找到相同字串 → 標記重複、不插入；未找到 → 插入葉節點。
3. 最後遍歷原始陣列，輸出未標記者。

struct Node {
    const char *str;
    int tag;           // 1=唯一, 0=重複
    Node *left, *right;
};

Node* insert(Node *root, const char *s, int *tag_ptr) {
    if (!root) {
        root = malloc(sizeof(Node));
        root->str = s; root->tag = 1; root->left = root->right = NULL;
        *tag_ptr = 1;
    } else {
        int cmp = strcmp(s, root->str);
        if (cmp == 0) { *tag_ptr = 0; }           // 重複
        else if (cmp < 0) root->left  = insert(root->left,  s, tag_ptr);
        else              root->right = insert(root->right, s, tag_ptr);
    }
    return root;
}
// 主程式：對每個輸入字串呼叫 insert，tag 回傳是否重複

效能比較

工程建議

• 教學/練習：自行實作上述演算法強化基本功。
• 生產代碼：直接使用成熟庫（C++ std::unordered_set、Glib GHashTable、CCAN htable 等）。
• 若必須用純 C 且無依賴，BST 或排序法均可接受，注意 BST 最差情況需改用 AVL/Red-Black 樹。