原文发表于2009年3月7日
今天解皞同学询问了一道编程题，要求是用表驱动法也就是查表的办法解决，题目（部分）如下：
映射关系如下：
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字。
可能最近一个链表的项目做晕头了，我的第一反应竟然是链表，后来想了下，这个应该使用普通数组的表结构会比较合理，我给出的建表方案如下：
映射关系是连续的，假设没有映射是1，那么映射关系应该是1-9这九个数字，化为数组下标应该是0-8。然后知道这是个一对多的关系，首先0对Q和Z、1对A、B和C……假设数组就是0~8的。
如何才能将一个数组下标对应的空间包含相应的多个联系呢？
我们可以通过状态位来判断，这里需要用到点位运算的知识。
设二元序列如下：
<0000 0001, A>
<0000 0010, B>
<0000 0100, C>
<0000 1000, D>
<0001 0000, E>
<0010 0000, F>
<0100 0000, G>
（省略若干）
大家应该能看出什么规律了，二进制的一位代表一个状态位，那么我们可以通过这些状态位索引字母A-Z。
那么一个无符号长整型（unsigned long）即可包含全部大写字母表的信息，比如包含A、B和C的信息，只要将A、B和C的二进制状态位按位或即可。
因此可以得到一张编码表：
<0x2010000> <Q, Z>
<0x0000007> <A, B, C>
<0x0000038> <D, E, F>
<0x00001c0> <G, H, I>
<0x0000e00> <J, K, L>
<0x0007000> <M, N, O>
<0x0068000> <P, R, S>
<0x0380000> <T, U, V>
<0x1c00000> <W, X, Y>
然后可以通过查这张表，然后用检测某位的方式判断映射关系，检测某位只需要按位与判断结果是否为0即可。
下面给出源代码：
#include <stdio.h> int main(void) { unsigned long letter_table[9] = {0x2010000, 0x0000007, 0x0000038, 0x00001c0, 0x0000e00, 0x0007000, 0x0068000, 0x0380000, 0x1c00000}; int get_letter, i; puts("Enter letter [A-Z] ?"); get_letter = getchar(); if(get_letter < 0x41 || get_letter > 0x5a) { fprintf(stderr, "Error letter must A-Z"); return 1; } for(i = 0; i < 9; i++) { if((((unsigned long)(0x1 << (get_letter - 0x41))) & letter_table[i]) != 0) { if(i != 0) printf("found it! @ %c = %d\n", get_letter, i + 1); else printf("letter %c without number.\n", get_letter); break; } } return 0; } |
以上源代码在Dev-CPP GCC下编译通过。
当然不见得这个就是效率很高的，我只是想通过这篇文章给大家编程时拓宽思路，比如位状态变化就是一个比较好的存储信息的方式。
如果想要查表效率很高，我觉得可以根据用户的具体输入，经过简单数学运算可以得到离结果最近的查表起始点，然后查找。
如果对于位操作比较感兴趣的可以参考我的前面的《简单介绍编程中位运算的使用》。