給定字元串，要求除去字元串中重複出現的字元

請編寫一個字元串過濾程式，若字元串中出現多個相同的字元，将非首次出現的字元過濾掉。比如字元串“abacacde”過濾結果為“abcde”。筆試會碰到這種題目，有的題目要求會多一條，就是不許重新配置設定存儲空間來臨時存儲字元串，即節省空間的原則。綜合兩個部落格的研究結果

（http://blog.csdn.net/luno1/article/details/7945227，http://blog.csdn.net/luno1/article/details/8001892），自己做下總結，同時也友善大家參考，分析完種種情況之後，會不由自主的想到，其實這就是對hash表的拓展應用。

首先看允許建立存儲空間的情形：

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

void string_filter(char *str,char *dest)

{

char *pin=str;

char *pout=dest;

int hash[26]={0};

while(*pin!='\0')

{

if(hash[*pin-'a']==0)//如果字元之前沒有出現，則将對應的hash數組中的位标記為1，表示字元已經出現。

{

hash[*pin-'a']=1;

*pout=*pin;

pout++;

pin++;

}

else

{

pin++;

}

}

*pout='\0';

}

void main()

{

char str[]="abacacde";

char *dest=(char*)malloc(strlen(str)+1);

string_filter(str,dest);

printf("%s\n",dest);

}

不許建立空間的情況：

char* remove_multiple_char(char* str)  

{  

    assert(str != NULL);  

    char* tmp = str;  

    char* tmp2 = str;  

    bool hash_table[256] = {false};  

    while(*tmp2 != '\0')  

    {  

        if (!hash_table[*tmp2 - '\0'])  

        {  

            hash_table[*tmp2 - '\0'] = true;  

            *tmp++ = *tmp2++;  

        }             

        else  

        {  

            tmp2++;  

        }  

    }  

    *tmp = '\0';  

    return str;  

}  

問題擴充，就是那個所謂的“和諧系統”：給定字元串str：abc，找出包含此字元串的所有字元串，比如a.....b...c, ac....b.....之類的都要找出來。這就是典型的對hash表的應用。還有，不知道大家還記得這個題目沒有，就是給定n-1個從1到n的數字，他們的順序被打亂，請線上性時間内找出沒有出現的那個數字，這個也是hash表的應用。相信大家如果能了解這幾個問題，以後遇到此類的變種問題會很快能想到應用hash表。