有一種最直接的方法可以去掉一個集合中重復的元素，這種方法據說就是“交給下面去做”，然而有時候，你自己動手去做一下也是不錯的。如果交給下面去做，最直接的選擇就是使用map，在java中，我們有HashMap，TreeMap等等實現了map接口的類可用，c++中，同樣有STL的同類集合可以使用，在各類高級語言中，就更不必說了，然而在c中，就沒有那么幸運了，很多東西需要你來自己實現。

根據《C語言內力修煉與軟件工程》，用c語言自行實現這個東西，其實對于軟件工程而言沒有必要，然而可以訓練一下自己，增加一些內力。我不認為自己是個高手，更非大俠，然而因為我懂得少，只能自己重新來做，真恨自己沒有在5年前多學習一些編程語言。

先來簡單分析一下需求，就是一個字符串集合中，去掉重復的字符串，換句話說就是每一個字符串只保留一個。題目沒有說是否保持原有的字符串輸入順序，作為完美主義的我，我還是將其當成了一個隱含的需求。那么下一步就是將問題進行簡化和轉化，如果我們能將這一堆字符串進行排序，那么最終遍歷這個排過序的字符串集合，發現和前一個相同的字符串就跳過不輸出，對于排序，再簡單不過了，至少N中排序算法，本文不討論各種排序算法，只使用最簡單的冒泡排序來分析。那么怎么保留原有的輸入序呢？這也很簡單，就是在排序元素中增加一個指向原有序的指針即可，另外還有一種方法，那就是排序過程僅僅是一個刪除重復元素的過程，而不影響原有的輸入序列，這個動態行為可以用二叉樹的插入來實現，或者其它的AVL樹以及紅黑樹都可以，本文不會去談這幾棵樹的特性，只是用最簡單的排序二叉樹來分析。

我們知道，在二叉樹插入中，首先要進行一次查找，現在要做的是，如果沒有找到相同的，則插入，如果找到了相同的，則不插入，同時為該元素置入刪除標識。代碼如下：

// // main.c // dup-del // // Created by ya zhao on 11-12-17. // Copyright 2011年 __MyCompanyName__. All rights reserved. // #include #include struct sorted_order_str_map_with_thread { char *sorted_order_str; //保存排序后的字符串 char *normal_order_str; //保存原始字符串 int tag; //指示是否要刪除 struct sorted_order_str_map_with_thread *self; //指向原始的位置 }; void sort(struct sorted_order_str_map_with_thread smwt[], const int size, int (*cmp)(void *, void *), void (*swap)(void *q1, void *q2)); int cmp_node(void *, void *); //比較函數，如果相同則將其tag位設置為0，標示要刪除 int cmp_node(void *q1, void *q2) { int res; struct sorted_order_str_map_with_thread *cmp1, *cmp2; cmp1 = (struct sorted_order_str_map_with_thread*)q1; cmp2 = (struct sorted_order_str_map_with_thread*)q2; res = strcmp(cmp1->sorted_order_str, cmp2->sorted_order_str); if (res == 0) { struct sorted_order_str_map_with_thread *p = cmp2->self; p->tag = 0; } return res; } //交換函數，不光要交換元素，還要交換其self指針 void swap_node(void *q1, void *q2) { struct sorted_order_str_map_with_thread *swp1, *swp2,*temp; char *strTemp; swp1 = (struct sorted_order_str_map_with_thread*)q1; swp2 = (struct sorted_order_str_map_with_thread*)q2; strTemp = swp1->sorted_order_str; temp = (swp1->self); swp1->sorted_order_str = swp2->sorted_order_str; swp1->self = swp2->self; swp2->sorted_order_str = strTemp; swp2->self = temp; } //標準冒泡排序 void sort(struct sorted_order_str_map_with_thread smwt[], const int size, int (*cmp)(void *q1, void *q2), void (*swap)(void *q1, void *q2)) { int flag = 1; for (int i = 0; i < size - 1; i ++) { flag = 1; for (int j = 0; j < size - i - 1; j ++) { int res = 0; if ((res = cmp(&smwt[j], &smwt[j+1])) > 0) { swap(&smwt[j], &smwt[j+1]); flag = 0; } } if (flag == 1) break; } } int main (int argc, const char * argv[]) { int i = 0; //為了簡化，下面使用了最惡心的初始化方法。方便復制粘貼 struct sorted_order_str_map_with_thread smwt[20] = {{NULL, NULL, 0 NULL}}; smwt[0].sorted_order_str =smwt[0].normal_order_str = "323"; smwt[0].self = &smwt[0]; smwt[0].tag = 1; smwt[1].sorted_order_str = smwt[1].normal_order_str="223"; smwt[1].self = &smwt[1]; smwt[1].tag = 2; smwt[2].sorted_order_str =smwt[2].normal_order_str= "723"; smwt[2].self = &smwt[2]; smwt[2].tag = 3; smwt[3].sorted_order_str =smwt[3].normal_order_str= "823"; smwt[3].self = &smwt[3]; smwt[3].tag = 4; smwt[4].sorted_order_str =smwt[4].normal_order_str= "123"; smwt[4].self = &smwt[4]; smwt[4].tag = 5; smwt[5].sorted_order_str =smwt[5].normal_order_str= "423"; smwt[5].self = &smwt[5]; smwt[5].tag = 6; smwt[6].sorted_order_str =smwt[6].normal_order_str= "123"; smwt[6].self = &smwt[6]; smwt[6].tag = 7; smwt[7].sorted_order_str =smwt[7].normal_order_str= "723"; smwt[7].self = &smwt[7]; smwt[7].tag = 8; smwt[8].sorted_order_str = smwt[8].normal_order_str="523"; smwt[8].self = &smwt[8]; smwt[8].tag = 9; smwt[9].sorted_order_str =smwt[9].normal_order_str= "823"; smwt[9].self = &smwt[9]; smwt[9].tag = 10; sort(smwt, 10, cmp_node, swap_node); //下面使用了最惡心的輸出，經典### for (i = 0; i< 10; i++) { printf("###:%s tag:%d\n", smwt[i].normal_order_str, smwt[i].tag); } for (i = 0; i< 10; i++) { printf("@@@:%s tag:%d\n", smwt[i].sorted_order_str, smwt[i].tag); } for (i = 0; i< 10; i++) { if (smwt[i].tag != 0){ printf("@@@&&:%s\n", smwt[i].normal_order_str); } } return 0; }

下面的一種方法使用了標準的二叉樹插入，注意，插入僅僅是為了刪除重復元素，實際上，各種語言各種庫的標準Map實現很多也是使用了樹，比如java.util中的TreeMap就是使用了紅黑樹。下面直接給出代碼，基于排序二叉樹的代碼：

// // main.c // test-xcode // // Created by ya zhao on 11-12-17. // Copyright 2011年 __MyCompanyName__. All rights reserved. // #include #include #include struct string_node { char *string; int tag; //標示是否被刪除 }; //標準排序二叉樹 struct string_tree { struct string_node *strn; struct string_tree* left,*right; }; struct string_tree *add_node(struct string_tree *, struct string_node *str, int (*cmp)(struct string_node *, struct string_node *)); int normalcmp(struct string_node *, struct string_node *); //簡單的字符串比較 int normalcmp(struct string_node *n1, struct string_node *n2) { return strcmp (n1->string,n2->string); } int main(int argc, char **argv) { int j = 0; for (j = 0; j < 1; j++) { struct string_tree *root; struct string_node str[9] = {{"123",1},{"456",1},{"234",1},{"123",1},{"347",1},{"129",1},{"888",1}, {"568",1}, {"456",1}}; root = NULL; int i = 0; while (i<9) { root = add_node(root, &str[i], normalcmp); i ++; } i=0; while (i<9){ if (str[i].tag) { printf("&&&:%s\n", str[i].string); } i++; } } return 0; } struct string_tree *add_node(struct string_tree *p, struct string_node *new, int (*cmp)(struct string_node *n1, struct string_node *n2)) { int cmp_ret; if (p == NULL) { p = (struct string_tree *)calloc(1, sizeof(struct string_tree)); p->strn = (struct string_node*)calloc(1, sizeof(struct string_node)); memcpy(p->strn, new, sizeof(struct string_node)); p->left = p->right = NULL; } else if ((cmp_ret = cmp(new, p->strn)) == 0) { new->tag =0; } else if (cmp_ret < 0) { p->left = add_node(p->left, new, cmp); } else { p->right = add_node(p->right, new, cmp); } return p; }

經過測試，自己實現的上述算法效率還可以，當然這里不該去比較效率，留下個思路即可，在沒有庫可用的情況下，也可以自己實現它。在現實中，特別是在軟件工程中，還是使用現成的map比較好。