回复 19楼 马后炮
由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了
///////////////////////////////////////////////////////////////////////
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///////////////////////////////////////////////////////////////////////
char FirstNotRepeatingChar(char* pString)
{
// invalid input
if(!pString)
return 0;
// get a hash table, and initialize it
const int tableSize = 256;
unsigned int hashTable[tableSize];
for(unsigned int i = 0; i < tableSize; ++ i)
hashTable[i] = 0;
// get the how many times each char appears in the string
char* pHashKey = pString;
while(*(pHashKey) != '\0')
hashTable[*(pHashKey++)] ++;
// find the first char which appears only once in a string
pHashKey = pString;
while(*pHashKey != '\0')
{
if(hashTable[*pHashKey] == 1)
return *pHashKey;
pHashKey++;
}
// if the string is empty
// or every char in the string appears at least twice
return 0;
}