哈希查找

问题：找出字符串中第一个只出现一次的字符，字符串区分大小写。比如输入字符串ddFDfsdfdsllf,就应该输出F。
注：哈希查找算法的查找效率是很高的，是一种利用空间换时间思想的典型算法。
  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<string>
  4 #include<cctype>
  5 using namespace std;
  6 class Firstchar
  7 {
  8 public:
  9     int n;  //共52个大小写字母
 10     string s; //输入的字符串，只能含有大小写
 11     typedef struct Hash   //哈希表单元，存储字符和次数
 12     {
 13         char ch;
 14         int num;
 15     };
 16     Hash *HashTable;
 17     char first;    //第一次只出现一次的字符
 18 
 19     Firstchar(const string &str)
 20     {
 21         n = 52;
 22         HashTable = new Hash[n];
 23         if (!HashTable)
 24         {
 25             cout << "内存不足，程序退出！";
 26             exit(1);
 27         }
 28         int i;
 29         for (i = 0; i < n; i++)
 30         {
 31             HashTable[i].ch = '';
 32             HashTable[i].num = 0;
 33         }
 34         s = str;
 35     }
 36     ~Firstchar()
 37     {
 38         delete[] HashTable;
 39     }
 40 
 41     int HashFuction(char ch);  //哈希函数
 42     void LoadHashTable();        //装载哈希表
 43     char findOnlyOneChar();        //寻找最先出现的不重复字符
 44 
 45 };
 46 int Firstchar::HashFuction(char ch)   //哈希函数 小写字母存在0-25的位置，大写字母存在26-51的位置
 47 {
 48     if (islower(ch))
 49     {
 50         return ch - 'a';
 51     }
 52     else return ch - 'A' + n / 2;
 53 }
 54 
 55 void Firstchar::LoadHashTable()  //装载哈希表
 56 {
 57     int i;
 58     int pos;
 59     for (i = 0; i < s.length(); i++)
 60     {
 61         pos = HashFuction(s[i]);
 62         if (!HashTable[pos].ch)  //如果这个位置为空
 63         {
 64             HashTable[pos].ch = s[i];
 65             HashTable[pos].num = 1;
 66         }
 67         else
 68             HashTable[pos].num++;
 69     }
 70 }
 71 char Firstchar::findOnlyOneChar()
 72 {
 73     LoadHashTable();
 74     int position;
 75     for (int i = 0; i < s.length(); i++)
 76     {
 77         position = HashFuction(s[i]);
 78         if (this->HashTable[position].num == 1)  //该字符出现的次数为1
 79         {
 80             first = s[i];
 81             return first;
 82         }
 83     }
 84     return NULL;
 85 }
 86 
 87 void main()
 88 {
 89     string str;
 90     cout << "请输入一个字符串：";
 91     cin >> str;
 92     if (!cin.good())
 93     {
 94         cout << "输入异常！" << endl;
 95         exit(1);
 96     }
 97     for (int i = 0; i < str.length(); i++)
 98     {
 99         if (!islower(str[i]) && !isupper(str[i]))
100         {
101             cout << "字符串只能包含大小写字符！" << endl;
102             return;
103         }
104     }
105     Firstchar Firstchar(str);
106     char answer = Firstchar.findOnlyOneChar();
107     if (answer == '')
108     {
109         cout << "该字符串没有不重复的字符" << endl;
110     }
111     else
112     {
113         cout << "第一次出现的不重复字符为：" << answer << endl;
114     }
115     system("pause");
116 
117 }
坚持比努力更重要