当前位置:首页 > 公众号精选 > C语言编程
[导读]数据压倒一切。如果选择了正确的数据结构并把一切组织的井井有条,正确的算法就不言自明。编程的核心是数据结构,而不是算法。——RobPike说明本文基于这样的认识:数据是易变的,逻辑是稳定的。本文例举的编程实现多为代码片段,但不影响描述的完整性。本文例举的编程虽然基于C语言,但其编程...

数据压倒一切。如果选择了正确的数据结构并把一切组织的井井有条,正确的算法就不言自明。编程的核心是数据结构,而不是算法。


——Rob Pike

说明


本文基于这样的认识:数据是易变的,逻辑是稳定的。本文例举的编程实现多为代码片段,但不影响描述的完整性。
本文例举的编程虽然基于C语言,但其编程思想也适用于其他语言。此外,本文不涉及语言相关的运行效率讨论。

1 概念提出


所谓表驱动法(Table-Driven Approach)简而言之就是用查表的方法获取数据。此处的“表”通常为数组,但可视为数据库的一种体现。
根据字典中的部首检字表查找读音未知的汉字就是典型的表驱动法,即以每个字的字形为依据,计算出一个索引值,并映射到对应的页数。相比一页一页地顺序翻字典查字,部首检字法效率极高。
具体到编程方面,在数据不多时可用逻辑判断语句(if…else或switch…case)来获取值;但随着数据的增多,逻辑语句会越来越长,此时表驱动法的优势就开始显现。例如,用36进制(A表示10,B表示11,…)表示更大的数字,逻辑判断语句如下:
if(ucNum < 10){ ucNumChar = ConvertToChar(ucNum);}else if(ucNum == 10){ ucNumChar = 'A';}else if(ucNum == 11){ ucNumChar = 'B';}else if(ucNum == 12){ ucNumChar = 'C';}//... ...else if(ucNum == 35){ ucNumChar = 'Z';}
当然也可以用switch…case结构,但实现都很冗长。而用表驱动法(将numChar存入数组)则非常直观和简洁。如:
CHAR aNumChars[] = {'0', '1', '2', /*3~9*/'A', 'B', 'C', /*D~Y*/'Z'};CHAR ucNumChar = aNumChars[ucNum % sizeof(aNumChars)];
像这样直接将变量当作下数组下标来读取数值的方法就是直接查表法。
注意,如果熟悉字符串操作,则上述写法可以更简洁:
CHAR ucNumChar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[ucNum];
使用表驱动法时需要关注两个问题:一是如何查表,从表中读取正确的数据;二是表里存放什么,如数值或函数指针。前者参见1.1节“查表方式”内容,后者参见1.2节“实战示例”内容。

1.1 查表方式


常用的查表方式有直接查找、索引查找和分段查找等。

1.1.1 直接查找


即直接通过数组下标获取到数据。如果熟悉哈希表的话,可以很容易看出这种查表方式就是哈希表的直接访问法。
如获取星期名称,逻辑判断语句如下:
if(0 == ucDay){ pszDayName = "Sunday";}else if(1 == ucDay){ pszDayName = "Monday";}//... ...else if(6 == ucDay){ pszDayName = "Saturday";}
而实现同样的功能,可将这些数据存储到一个表里:
CHAR *paNumChars[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};CHAR *pszDayName = paNumChars[ucDay];
类似哈希表特性,表驱动法适用于无需有序遍历数据,且数据量大小可提前预测的情况。
对于过于复杂和庞大的判断,可将数据存为文件,需要时加载文件初始化数组,从而在不修改程序的情况下调整里面的数值。
有时,访问之前需要先进行一次键值转换。如表驱动法表示端口忙闲时,需将槽位端口号映射为全局编号。所生成的端口数目大小的数组,其下标对应全局端口编号,元素值表示相应端口的忙闲状态。

1.1.2 索引查找


有时通过一次键值转换,依然无法把数据(如英文单词等)转为键值。此时可将转换的对应关系写到一个索引表里,即索引访问。
如现有100件商品,4位编号,范围从0000到9999。此时只需要申请一个长度为100的数组,且对应2位键值。但将4位的编号转换为2位的键值,可能过于复杂或没有规律,最合适的方法是建立一个保存该转换关系的索引表。采用索引访问既节省内存,又方便维护。比如索引A表示通过名称访问,索引B表示通过编号访问。

1.1.3 分段查找


通过确定数据所处的范围确定分类(下标)。有的数据可分成若干区间,即具有阶梯性,如分数等级。此时可将每个区间的上限(或下限)存到一个表中,将对应的值存到另一表中,通过第一个表确定所处的区段,再由区段下标在第二个表里读取相应数值。注意要留意端点,可用二分法查找,另外可考虑通过索引方法来代替。
如根据分数查绩效等级:
#define MAX_GRADE_LEVEL (INT8U)5DOUBLE aRangeLimit[MAX_GRADE_LEVEL] = {50.0, 60.0, 70.0, 80.0, 100.0};CHAR *paGrades[MAX_GRADE_LEVEL] = {"Fail", "Pass", "Credit", "Distinction", "High Distinction"};
static CHAR* EvaluateGrade(DOUBLE dScore){ INT8U ucLevel = 0; for(; ucLevel < MAX_GRADE_LEVEL; ucLevel ) { if(dScore < aRangeLimit[ucLevel]) return paGrades[ucLevel]; } return paGrades[0];}
上述两张表(数组)也可合并为一张表(结构体数组),如下所示:
typedef struct{ DOUBLE aRangeLimit; CHAR *pszGrade;}T_GRADE_MAP;
T_GRADE_MAP gGradeMap[MAX_GRADE_LEVEL] = { {50.0, "Fail"}, {60.0, "Pass"}, {70.0, "Credit"}, {80.0, "Distinction"}, {100.0, "High Distinction"}};
static CHAR* EvaluateGrade(DOUBLE dScore){ INT8U ucLevel = 0; for(; ucLevel < MAX_GRADE_LEVEL; ucLevel ) { if(dScore < gGradeMap[ucLevel].aRangeLimit) return gGradeMap[ucLevel].pszGrade; } return gGradeMap[0].pszGrade;}
该表结构已具备的数据库的雏形,并可扩展支持更为复杂的数据。其查表方式通常为索引查找,偶尔也为分段查找;当索引具有规律性(如连续整数)时,退化为直接查找。
使用分段查找法时应注意边界,将每一分段范围的上界值都考虑在内。找出所有不在最高一级范围内的值,然后把剩下的值全部归入最高一级中。有时需要人为地为最高一级范围添加一个上界。
同时应小心不要错误地用“<”来代替“<=”。要保证循环在找出属于最高一级范围内的值后恰当地结束,同时也要保证恰当处理范围边界。

1.2 实战示例


本节多数示例取自实际项目。表形式为一维数组、二维数组和结构体数组;表内容有数据、字符串和函数指针。基于表驱动的思想,表形式和表内容可衍生出丰富的组合。

1.2.1 字符统计


问题:统计用户输入的一串数字中每个数字出现的次数。
普通解法主体代码如下:
INT32U aDigitCharNum[10] = {0}; /* 输入字符串中各数字字符出现的次数 */INT32U dwStrLen = strlen(szDigits);
INT32U dwStrIdx = 0;for(; dwStrIdx < dwStrLen; dwStrIdx ){ switch(szDigits[dwStrIdx]) { case '1': aDigitCharNum[0] ; break; case '2': aDigitCharNum[1] ; break; //... ... case '9': aDigitCharNum[8] ; break; }}
这种解法的缺点显而易见,既不美观也不灵活。其问题关键在于未将数字字符与数组aDigitCharNum下标直接关联起来。
以下示出更简洁的实现方式:
for(; dwStrIdx < dwStrLen; dwStrIdx ){ aDigitCharNum[szDigits[dwStrIdx] - '0'] ;}
上述实现考虑到0也为数字字符。该解法也可扩展至统计所有ASCII可见字符。

1.2.2 月天校验


问题:对给定年份和月份的天数进行校验(需区分平年和闰年)。
普通解法主体代码如下:
switch(OnuTime.Month){ case 1: case 3: case 5: case 7: case 8: case 10: case 12: if(OnuTime.Day>31 || OnuTime.Day<1) { CtcOamLog(FUNCTION_Pon,"Don't support this Day: %d(1~31)!!!\n", OnuTime.Day); retcode = S_ERROR; } break; case 2: if(((OnuTime.Year%4 == 0)
本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭