给定字符串，要求除去字符串中重复出现的字符

http://blog.csdn.net/zzran/article/details/8006941

2012

请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“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表。