#include "stdafx.h"

#include <iostream>

using namespace std;

void FirstNoRepeatCh(const char str[], char& ch);

int main(int argc, char* argv[])

{

	const char* str = "cdceasafggsfrrtkkxx";

	char ch = '@';

	FirstNoRepeatCh(str,ch);

	if(ch == '@')

		cout<<"No Find!"<<endl;

	else

		cout<<ch<<endl;

	return 0;

}

//自己编写，即第一种思路

/*void FirstNoRepeatCh(const char str[], char& ch)

{

	int HashTable[256] = {0};

	while(*str != '\0')

	{

		if(HashTable[*str] == 0)  //用Hash表（哈希表）来判断字符是否重复出现

		{

			char* pch = (char*)(str+1);

			bool chFind = false;

			while(*pch != '\0' && !chFind)

			{

				if(*str == *pch)

					chFind = true;

				pch++;

			}

			if(chFind)

				HashTable[*str] = 1;

			else

			{

				ch = *str;

				break;

			}

		}

		str++;

	}

}*/

//此为第二种思路+自己编写

void FirstNoRepeatCh(const char str[], char& ch)

{

	if(!str)

		return;

	const int TableSize = 256;

	int HashTable[TableSize] = {0};

	char* pch = (char*)str;

	while(*str != '\0')

	{

		HashTable[*str]++;

		str++;

	}

	bool chFind = false;

	while(*pch != '\0' && !chFind)

	{

		if(HashTable[*pch] == 1)

		{

			ch = *pch;

			chFind = true;

		}

		pch++;

	}

}

/*//标准答案

///////////////////////////////////////////////////////////////////////

// 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;  //最好用const int

      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;

} */

//注意：根据评论可知，若第二次遍历Hash表，则会得到仅出现一次的最小字符