有一種最直接的方法可以去掉一個集合中重復的元素,這種方法據說就是“交給下面去做”,然而有時候,你自己動手去做一下也是不錯的。如果交給下面去做,最直接的選擇就是使用map,在java中,我們有HashMap,TreeMap等等實現了map接口的類可用,c++中,同樣有STL的同類集合可以使用,在各類高級語言中,就更不必說了,然而在c中,就沒有那麼幸運了,很多東西需要你來自己實現。
根據《C語言內力修煉與軟件工程》見 http://www.linuxidc.com/Linux/2011-12/50393p3.htm ,用c語言自行實現這個東西,其實對於軟件工程而言沒有必要,然而可以訓練一下自己,增加一些內力。我不認為自己是個高手,更非大俠,然而因為我懂得少,只能自己重新來做,真恨自己沒有在5年前多學習一些編程語言。
先來簡單分析一下需求,就是一個字符串集合中,去掉重復的字符串,換句話說就是每一個字符串只保留一個。題目沒有說是否保持原有的字符串輸入順序,作為完美主義的我,我還是將其當成了一個隱含的需求。那麼下一步就是將問題進行簡化和轉化,如果我們能將這一堆字符串進行排序,那麼最終遍歷這個排過序的字符串集合,發現和前一個相同的字符串就跳過不輸出,對於排序,再簡單不過了,至少N中排序算法,本文不討論各種排序算法,只使用最簡單的冒泡排序來分析。那麼怎麼保留原有的輸入序呢?這也很簡單,就是在排序元素中增加一個指向原有序的指針即可,另外還有一種方法,那就是排序過程僅僅是一個刪除重復元素的過程,而不影響原有的輸入序列,這個動態行為可以用二叉樹的插入來實現,或者其它的AVL樹以及紅黑樹都可以,本文不會去談這幾棵樹的特性,只是用最簡單的排序二叉樹來分析。
我們知道,在二叉樹插入中,首先要進行一次查找,現在要做的是,如果沒有找到相同的,則插入,如果找到了相同的,則不插入,同時為該元素置入刪除標識。代碼如下:
- //
- // main.c
- // dup-del
- //
- // Created by ya zhao on 11-12-17.
- // Copyright 2011年 __MyCompanyName__. All rights reserved.
- //
-
- #include <stdio.h>
- #include <stdlib.h>
-
- 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;
- }