首页 / 操作系统 / Linux / 使用C语言去掉字符串集合重复元素

有一种最直接的方法可以去掉一个集合中重复的元素，这种方法据说就是“交给下面去做”，然而有时候，你自己动手去做一下也是不错的。如果交给下面去做，最直接的选择就是使用map，在java中，我们有HashMap，TreeMap等等实现了map接口的类可用，c++中，同样有STL的同类集合可以使用，在各类高级语言中，就更不必说了，然而在c中，就没有那么幸运了，很多东西需要你来自己实现。根据《C语言内力修炼与软件工程》见 http://www.linuxidc.com/Linux/2011-12/50393p3.htm ，用c语言自行实现这个东西，其实对于软件工程而言没有必要，然而可以训练一下自己，增加一些内力。我不认为自己是个高手，更非大侠，然而因为我懂得少，只能自己重新来做，真恨自己没有在5年前多学习一些编程语言。先来简单分析一下需求，就是一个字符串集合中，去掉重复的字符串，换句话说就是每一个字符串只保留一个。题目没有说是否保持原有的字符串输入顺序，作为完美主义的我，我还是将其当成了一个隐含的需求。那么下一步就是将问题进行简化和转化，如果我们能将这一堆字符串进行排序，那么最终遍历这个排过序的字符串集合，发现和前一个相同的字符串就跳过不输出，对于排序，再简单不过了，至少N中排序算法，本文不讨论各种排序算法，只使用最简单的冒泡排序来分析。那么怎么保留原有的输入序呢？这也很简单，就是在排序元素中增加一个指向原有序的指针即可，另外还有一种方法，那就是排序过程仅仅是一个删除重复元素的过程，而不影响原有的输入序列，这个动态行为可以用二叉树的插入来实现，或者其它的AVL树以及红黑树都可以，本文不会去谈这几棵树的特性，只是用最简单的排序二叉树来分析。我们知道，在二叉树插入中，首先要进行一次查找，现在要做的是，如果没有找到相同的，则插入，如果找到了相同的，则不插入，同时为该元素置入删除标识。代码如下：

1. //   
2. //  main.c   
3. //  dup-del   
4. //   
5. //  Created by ya zhao on 11-12-17.   
6. //  Copyright 2011年 __MyCompanyName__. All rights reserved.   
7. //   
8.   
9. #include <stdio.h>   
10. #include <stdlib.h>   
11.   
12. struct sorted_order_str_map_with_thread {  
13.     char *sorted_order_str;  //保存排序后的字符串   
14.     char *normal_order_str;  //保存原始字符串   
15.     int tag;                //指示是否要删除   
16.     struct sorted_order_str_map_with_thread *self; //指向原始的位置   
17. };  
18.   
19. void sort（struct sorted_order_str_map_with_thread smwt[], const int size,  
20.                     int （*cmp）（void *, void *）,  
21.                     void （*swap）（void *q1, void *q2））;  
22. int cmp_node（void *, void *）;  
23. //比较函数，如果相同则将其tag位设置为0，标示要删除   
24. int cmp_node（void *q1, void *q2）  
25. {  
26.     int res;  
27.     struct sorted_order_str_map_with_thread *cmp1, *cmp2;  
28.     cmp1 = （struct sorted_order_str_map_with_thread*）q1;  
29.     cmp2 = （struct sorted_order_str_map_with_thread*）q2;  
30.     res = strcmp（cmp1->sorted_order_str, cmp2->sorted_order_str）;  
31.     if （res == 0） {  
32.         struct sorted_order_str_map_with_thread *p = cmp2->self;  
33.         p->tag  = 0;  
34.     }  
35.     return res;  
36. }  
37. //交换函数，不光要交换元素，还要交换其self指针   
38. void swap_node（void *q1, void *q2）  
39. {  
40.     struct sorted_order_str_map_with_thread *swp1, *swp2,*temp;  
41.     char *strTemp;  
42.     swp1 = （struct sorted_order_str_map_with_thread*）q1;  
43.     swp2 = （struct sorted_order_str_map_with_thread*）q2;  
44.     strTemp = swp1->sorted_order_str;  
45.     temp = （swp1->self）;  
46.     swp1->sorted_order_str = swp2->sorted_order_str;  
47.     swp1->self = swp2->self;  
48.     swp2->sorted_order_str = strTemp;  
49.     swp2->self = temp;  
50. }  
51.   
52. //标准冒泡排序   
53. void sort（struct sorted_order_str_map_with_thread smwt[], const int size,  
54.                 int （*cmp）（void *q1, void *q2）,  
55.                 void （*swap）（void *q1, void *q2））  
56. {  
57.     int flag = 1;  
58.     for （int i = 0; i < size - 1; i ++） {  
59.         flag = 1;  
60.         for （int j = 0; j < size - i - 1; j ++） {  
61.             int res = 0;  
62.             if （（res = cmp（&smwt[j], &smwt[j+1]）） > 0） {  
63.                 swap（&smwt[j], &smwt[j+1]）;  
64.                 flag = 0;  
65.             }  
66.         }  
67.           
68.         if （flag == 1）  
69.             break;  
70.     }  
71. }  
72.   
73. int main （int argc, const char * argv[]）  
74. {  
75.     int i = 0;  
76.     //为了简化，下面使用了最恶心的初始化方法。方便复制粘贴   
77.     struct sorted_order_str_map_with_thread smwt[20] = {{NULL, NULL, 0 NULL}};  
78.     smwt[0].sorted_order_str =smwt[0].normal_order_str =  "323";  
79.     smwt[0].self = &smwt[0];  
80.     smwt[0].tag = 1;  
81.     smwt[1].sorted_order_str = smwt[1].normal_order_str="223";  
82.     smwt[1].self = &smwt[1];  
83.     smwt[1].tag = 2;  
84.     smwt[2].sorted_order_str =smwt[2].normal_order_str= "723";  
85.     smwt[2].self = &smwt[2];  
86.     smwt[2].tag = 3;  
87.     smwt[3].sorted_order_str =smwt[3].normal_order_str= "823";  
88.     smwt[3].self = &smwt[3];  
89.     smwt[3].tag = 4;  
90.     smwt[4].sorted_order_str =smwt[4].normal_order_str= "123";  
91.     smwt[4].self = &smwt[4];  
92.     smwt[4].tag = 5;  
93.     smwt[5].sorted_order_str =smwt[5].normal_order_str= "423";  
94.     smwt[5].self = &smwt[5];  
95.     smwt[5].tag = 6;  
96.     smwt[6].sorted_order_str =smwt[6].normal_order_str= "123";  
97.     smwt[6].self = &smwt[6];  
98.     smwt[6].tag = 7;  
99.     smwt[7].sorted_order_str =smwt[7].normal_order_str= "723";  
100.     smwt[7].self = &smwt[7];  
101.     smwt[7].tag = 8;  
102.     smwt[8].sorted_order_str = smwt[8].normal_order_str="523";  
103.     smwt[8].self = &smwt[8];  
104.     smwt[8].tag = 9;  
105.     smwt[9].sorted_order_str =smwt[9].normal_order_str= "823";  
106.     smwt[9].self = &smwt[9];  
107.     smwt[9].tag = 10;  
108.   
109.     sort（smwt, 10, cmp_node, swap_node）;  
110.     //下面使用了最恶心的输出，经典###   
111.     for （i = 0; i< 10; i++） {  
112.         printf（"###:%s    tag:%d ", smwt[i].normal_order_str, smwt[i].tag）;  
113.     }  
114.     for （i = 0; i< 10; i++） {  
115.             printf（"@@@:%s  tag:%d ", smwt[i].sorted_order_str, smwt[i].tag）;  
116.     }  
117.     for （i = 0; i< 10; i++） {  
118.         if （smwt[i].tag ！= 0）{  
119.         printf（"@@@&&:%s ", smwt[i].normal_order_str）;  
120.         }  
121.     }  
122.     return 0;  
123. }