程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 使用C語言去掉字符串集合重復元素

使用C語言去掉字符串集合重復元素

編輯:關於C

有一種最直接的方法可以去掉一個集合中重復的元素,這種方法據說就是“交給下面去做”,然而有時候,你自己動手去做一下也是不錯的。如果交給下面去做,最直接的選擇就是使用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 <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; 


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

// 
//  main.c 
//  test-xcode 
// 
//  Created by ya zhao on 11-12-17. 
//  Copyright 2011年 __MyCompanyName__. All rights reserved. 
// 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
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比較好

摘自 黎明的豐收

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved