计算字符出现次数

解题思路

思路就是统计字符出现的次数，查询字符输出次数。
c解题就看如何构建数据结构了。

方法一

简单粗暴的hash。申请一个hash数组，下标表示字符的ascii码值，数组元素的值标志字符穿线的个数。
循环一遍就可以统计所有字符出现的次数。

#include<stdio.h>

int hashNum[91] = {0};

int main()
{
    char tempChar = 0;
    int  temp = 0;
    char inputChar = 0;

    while((tempChar = getchar()) != '\n') {
       temp = tempChar > 90 ? tempChar - 32 : tempChar;
       hashNum[temp]++;
    }

    scanf("%c", &inputChar);
    temp = inputChar > 90 ? inputChar - 32 : inputChar;
    printf("%d\n", hashNum[temp]);

    return 0;
}

方法二

构建hashTable。
构建一个数据结构hashTable，包hashNode节点，每个hashNode节点包括数据值和次数两个元素。
构建hash映射关系，将字符依次统计到连续的地址上。
查询的时候就根据hash关系查找，差找不到就依次查询表格。

#define HASH_MAX_SIZE 36
#define HASH_NULL_KEY

int hashSize = HASH_MAX_SIZE ;

typedef struct _HashNode {
    int key;    //字符的数值
    int val;    //字符的个数
}HashNode;

typedef struct _HashTable {
    int count;
    HashNode *table;
}HashTable;

int InitHashTable(HashTable *H, int size) 
{
    int i;

    hashSize = size;
    H->count = size;
    H->table = (HashNode *)malloc(H->count * sizeof(HashNode));
    if (!H->table) {
        return -1;
    }

    for (i = 0; i < hashSize; i++) {
        H->table[i].key = HASH_NULL_KEY;
        H->table[i].val = 0;
    }

    return 0;
}

int HashRelation(int key)
{
    return key % hashSize;
}

int InsertHashTable(HashTable *H, int key)
{
    int addr = HashRelation(key);

    while(H->table[addr].key != HASH_NULL_KEY) && (H->table[addr].key != key)) {
        addr = HashRelation(addr + 1);
        if(addr == HashRelation(key)) {
            return -1;
        }
    }

    H->table[addr].key = key;
    H->table[addr].val++;
}

int SearchHashTable(HashTable *H, int key)
{
    int addr = HashRelation(key);

    while(H->table[addr].key != key) {
        addr = HashRelation(addr + 1);
        if (addr == HashRelation(key)) {
            return -1;
        }
    }

    return H->table[addr].val;
}

eg：

这种题感觉就是 空间和时间的balance。
理想的情况下是想要做到时间上只循环一次，空间上每个字符都对应表格中的一个元素。
但是呢，当前的我做不到，找不到合适的函数，将散列的数据映射到连续的数据室行，并且一一对应。臣妾做不到。
很多算法题是不是也是这样呢，没有最优解，有当前最优解(局部最优解)，其本质是空间和时间的balance。除非有更高维度的数据结构出现(当然这个就是突破了)。