原文发表于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下编译通过。
当然不见得这个就是效率很高的,我只是想通过这篇文章给大家编程时拓宽思路,比如位状态变化就是一个比较好的存储信息的方式。
如果想要查表效率很高,我觉得可以根据用户的具体输入,经过简单数学运算可以得到离结果最近的查表起始点,然后查找。
如果对于位操作比较感兴趣的可以参考我的前面的《简单介绍编程中位运算的使用》。
Comments are closed.