Java之表驱动法

    表驱动分为三种，分别是：直接索引、索引表、阶梯索引。一般直接索引使用比较广泛，也容易想到。今天在网上看到了一笔试题，统计一个字符串中第一次出现且频率最高的字符。看到这道题以后，我觉得使用表驱动能很快、很容易地解决问题，下面是我使用表驱动给出的解法。

public static char statMostRateChar(String str) {
    if (str != null && !"".equals(str)) {
        int charsStat[] = new int[128];
        int charsFirstIdx[] = new int[128];
        int strLen = str.length();
        
        for (int ch = 0; ch < 128;ch++) {
        	charsFirstIdx[ch] = strLen;
        }
        
        // 統計字符出現的次數
        for (int idx = 0; idx < strLen; idx++) {
            charsStat[str.charAt(idx)]++;
            // 记录字符第一次出现的位置
            if (idx < charsFirstIdx[str.charAt(idx)]) {
            	charsFirstIdx[str.charAt(idx)] = idx;
            }
        }

        int mostRateChar = 0;
        for (int ch = 1; ch < 128; ch++) {
            if (charsStat[ch] == 0) {
        	continue;
            }
            // 找频率出现最高的字符
            if (charsStat[mostRateChar] < charsStat[ch]) {
            	mostRateChar = ch;
            	// 出现频率一样时，选择出现在前面的数
            } else if (charsStat[mostRateChar] == charsStat[ch]&&
            		charsFirstIdx[mostRateChar] > charsFirstIdx[ch]) {
            	mostRateChar = ch;
            }
        }

        return (char) mostRateChar;
    } else {
        return '\0';
    }
}

    这是我对表驱动的一点认识，我觉得选择表驱动，提高代码的执行效率以及可读性，但同时却牺牲了存储空间。如果在不浪费大量空间的前提下，表驱动的确是一个不错的选择。

评论

6 楼 jupiterpan 2009-12-06  

想法不错, 不过有点问题. 256不够用, 中文也可以存成char型, 此时charStat数组会越界.

5 楼 Qaohao 2009-08-11  

呵呵，谢谢楼上支持！以后还请多多指点。

4 楼 Qaohao 2009-08-11  

修改后的结果。
public static char statMostRateChar(String str) {
    if (str != null && !"".equals(str)) {
        int charsStat[] = new int[256];
        int charsFirstIdx[] = new int[256];
        int strLen = str.length();
       
        for (int ch = 0; ch < 256;ch++) {
        charsFirstIdx[ch] = strLen;
        }
       
        // 統計字符出現的次數
        for (int idx = 0; idx < strLen; idx++) {
            charsStat[str.charAt(idx)]++;
            // 记录字符第一次出现的位置
            if (idx < charsFirstIdx[str.charAt(idx)]) {
            charsFirstIdx[str.charAt(idx)] = idx;
            }
        }

        int mostRateChar = 0;
        for (int ch = 1; ch < 256; ch++) {
        if (charsStat[ch] == 0) {
        continue;
        }
            // 找频率出现最高的字符
        if (charsStat[mostRateChar] < charsStat[ch]) {
            mostRateChar = ch;
            // 出现频率一样时，选择出现在前面的数
            } else if (charsStat[mostRateChar] == charsStat[ch]&&
            charsFirstIdx[mostRateChar] > charsFirstIdx[ch]) {
            mostRateChar = ch;
            }
        }

        return (char) mostRateChar;
    } else {
        return '\0';
    }
}

3 楼 night_stalker 2009-08-11  

Qaohao 写道

呵呵。楼主说的很有道理！
首先，我确实糊涂了，这个的确不能拿到第一次出现且频率最高的字符。对于你后面得那两处异议，首先256，是因为java中字符占两个字节，所以使用了256；第二处就是关于表驱动，虽然我说是表驱动有些牵强，但是我觉得思想接近，如果我们一定按照书中说的那样，我觉得就有些教条。不过还是很感谢楼主对我关注！多谢指教。

吐槽点太多了 …… 忍不住回帖 ……

2 楼 Qaohao 2009-08-11  

呵呵。楼主说的很有道理！
首先，我确实糊涂了，这个的确不能拿到第一次出现且频率最高的字符。对于你后面得那两处异议，首先256，是因为java中字符占两个字节，所以使用了256；第二处就是关于表驱动，虽然我说是表驱动有些牵强，但是我觉得思想接近，如果我们一定按照书中说的那样，我觉得就有些教条。不过还是很感谢楼主对我关注！多谢指教。

1 楼 icefishc 2009-08-11  

有些问题 charsStat中字母的顺序不是原字符串中字母的顺序,  这个程序无法保证你的题目中要求的那个"第一次"
解决办法很简单 把每个字母第一次出现的位置保留下来就成了

 int charsStat[] = new int[256];  

这个256有些怪异? ASCII  extension ??

另外一个问题是把这东西归为表驱动似乎有点勉强.
按照Code Complete中的定义 表驱动是指用表中的信息来代替逻辑语句.
不知道这个术语到底是从哪来的 Code Complete也不是啥特标准的东西 但这东西看的人比较多咱们暂且用它