数据压倒一切。如果选择了正确的数据结构并把一切组织的井井有条,正确的算法就不言自明。编程的核心是数据结构,而不是算法——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 31 || onutime.day29 || onutime.day28 || onutime.day30 || onutime.day> (bit)) & 0x1)const char* pasvrnames[] = {_internet, _tr069, _voip, _other};const int8u ucsvrnamenum = sizeof(pasvrnames) / sizeof(pasvrnames[0]);void setservertype(char *pszsvrtype, int16u wsvrtype){ int8u ucidx = 0;for(; ucidx pszname; }//ansi标准禁止对void指针进行算法操作;gnu标准则指定void*算法操作与char*一致。//若考虑移植性,可将pvmap类型改为int8u*,或定义int8u*局部变量指向pvmap。 pvmap += sizeof(t_name_parser); }if(null != pszdefname) {return pszdefname; }else {static int8u szname[12] = {0}; //max:0xffffffffsprintf(szname, 0x%x, dwelem);return szname; }}以下给出nameparser的简单应用示例://uni端口类型值名映射表结构体定义typedef struct{ int32u dwporttype; int8u* pszportname;}t_port_name;//uni端口类型解析器t_port_name guninamemap[] = { {1, fe}, {3, pots}, {99, vuni}};const int32u uni_nam_map_num = (int32u)(sizeof(guninamemap)/sizeof(t_port_name));void nameparsertest(void){ int8u uctestindex = 1;printf([%s] result: %s!, __function__, uctestindex++,strcmp(unknown, nameparser(guninamemap, uni_nam_map_num, 0, unknown)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(defname, nameparser(guninamemap, uni_nam_map_num, 0, defname)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(fe, nameparser(guninamemap, uni_nam_map_num, 1, unknown)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(pots, nameparser(guninamemap, uni_nam_map_num, 3, unknown)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(vuni, nameparser(guninamemap, uni_nam_map_num, 99, null)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(unknown, nameparser(guninamemap, uni_nam_map_num, 255, unknown)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(0xabcd, nameparser(guninamemap, uni_nam_map_num, 0xabcd, null)) ? error : ok);printf([%s] result: %s!, __function__, uctestindex++,strcmp(nullponiter, nameparser(null, uni_nam_map_num, 0xabcd, null)) ? error : ok);} guninamemap在实际项目中有十余个条目,若采用逻辑链实现将非常冗长。
1.2.5 取值映射
问题:不同模块间同一参数枚举值取值可能有所差异,需要适配。 此处不再给出普通的switch…case或if…else if…else结构,而直接示出以下表驱动实现:
typedef struct{ portstate loopmestate; portstate loopmibstate;}loopmapstruct;static loopmapstruct s_cesloop[] = { {no_loop, e_ds1_looptype_noloop}, {payload_loop, e_ds1_looptype_payloadloop}, {line_loop, e_ds1_looptype_lineloop}, {pon_loop, e_ds1_looptype_otherloop}, {ces_loop, e_ds1_looptype_inwardloop}};portstate convertloopmestatetomibstate(portstate vportstate){ int32u num = 0, ii; num = array_num(s_cesloop);for(ii = 0; ii 4]) { elemdest = map[ucmapidx][(direction)&0x0f]; break; } } if(ucmapidx == ucmapnum) { elemdest = (defaultval); } }while(0) 参数取值转换时直接调用统一的映射器宏,如下: static int8u gcesloopmap[][2] = { {no_loop, e_ds1_looptype_noloop}, {payload_loop, e_ds1_looptype_payloadloop}, {line_loop, e_ds1_looptype_lineloop}, {pon_loop, e_ds1_looptype_otherloop}, {ces_loop, e_ds1_looptype_inwardloop}};array_mapper(gcesloopmap, tpara.dwparaval[0], dwloopconf, 0x01, e_ds1_looptype_noloop);
另举一例:
#define ces_default_jitterbuf (int32u)2000 /* 默认jitterbuf为2000us,而1帧=125us */#define ces_jitterbuf_step (int32u)125 /* jitterbuf步长为125us,即1帧 */#define ces_default_queuesize (int32u)5#define ces_default_max_queuesize (int32u)7#define array_num(array) (sizeof(array) / sizeof((array)[0])) /* 数组元素个数 */typedef struct{ int32u dwjitterbuffer; int32u dwframeperpkt; int32u dwqueuesize;}queue_size_map;/* gcesqueuesizemap也可以(jitterbuffer / frameperpkt)值为索引,更加紧凑 */static queue_size_map gcesqueuesizemap[]= { {1,1,1}, {1,2,1}, {2,1,2}, {2,2,1}, {3,1,3}, {3,2,1}, {4,1,3}, {4,2,1}, {5,1,4}, {5,2,3}, {6,1,4}, {6,2,3}, {7,1,4}, {7,2,3}, {8,1,4}, {8,2,3}, {9,1,5}, {9,2,4}, {10,1,5}, {10,2,4}, {11,1,5}, {11,2,4}, {12,1,5}, {12,2,4}, {13,1,5}, {13,2,4}, {14,1,5}, {14,2,4}, {15,1,5}, {15,2,4}, {16,1,5}, {16,2,4}, {17,1,6}, {17,2,5}, {18,1,6}, {18,2,5}, {19,1,6}, {19,2,5}, {20,1,6}, {20,2,5}, {21,1,6}, {21,2,5}, {22,1,6}, {22,2,5}, {23,1,6}, {23,2,5}, {24,1,6}, {24,2,5}, {25,1,6}, {25,2,5}, {26,1,6}, {26,2,5}, {27,1,6}, {27,2,5}, {28,1,6}, {28,2,5}, {29,1,6}, {29,2,5}, {30,1,6}, {30,2,5}, {31,1,6}, {31,2,5}, {32,1,6}, {32,2,5}};/*********************************************************** 函数名称:calcqueuesize* 功能描述:根据jitterbuffer和frameperpkt计算queuesize* 注意事项:配置的最大缓存深度* = 2 * jitterbuffer / frameperpkt* = 2 * n packet = 2 ^ queuesize* jitterbuffer为125us帧速率的倍数,* frameperpkt为每个分组的帧数,* queuesize向上取整,最大为7。**********************************************************/int32u calcqueuesize(int32u dwjitterbuffer, int32u dwframeperpkt){ int8u ucidx = 0, ucnum = 0; //本函数暂时仅考虑e1 ucnum = array_num(gcesqueuesizemap); for(ucidx = 0; ucidx uclength = 0x1f;if (goamctrlcode == 0){ vosmemcpy(pstsendtlv->aucversionlist, ctc_oui, 3); pstsendtlv->aucversionlist[3] = 0x30; vosmemcpy(&(pstsendtlv->aucversionlist[4]), ctc_oui, 3); pstsendtlv->aucversionlist[7] = 0x21; vosmemcpy(&(pstsendtlv->aucversionlist[8]), ctc_oui, 3); pstsendtlv->aucversionlist[11] = 0x20; vosmemcpy(&(pstsendtlv->aucversionlist[12]), ctc_oui, 3); pstsendtlv->aucversionlist[15] = 0x13; vosmemcpy(&(pstsendtlv->aucversionlist[16]), ctc_oui, 3); pstsendtlv->aucversionlist[19] = 0x01; vosmemcpy(&(pstsendtlv->aucversionlist[20]), ctc_oui, 3); pstsendtlv->aucversionlist[23] = 0xaa;}else if (goamctrlcode == 1){ vosmemcpy(pstsendtlv->aucversionlist, ctc_oui, 3); pstsendtlv->aucversionlist[3] = 0x30; vosmemcpy(&(pstsendtlv->aucversionlist[4]), ctc_oui, 3); pstsendtlv->aucversionlist[7] = 0x21; vosmemcpy(&(pstsendtlv->aucversionlist[8]), ctc_oui, 3); pstsendtlv->aucversionlist[11] = 0x20; vosmemcpy(&(pstsendtlv->aucversionlist[12]), ctc_oui, 3); pstsendtlv->aucversionlist[15] = 0x13; vosmemcpy(&(pstsendtlv->aucversionlist[16]), ctc_oui, 3); pstsendtlv->aucversionlist[19] = 0x01;}//此处省略goamctrlcode == 2~6的处理代码else if (goamctrlcode == 7){ vosmemcpy(&(pstsendtlv->aucversionlist), ctc_oui, 3); pstsendtlv->aucversionlist[3] = 0x20; vosmemcpy(&(pstsendtlv->aucversionlist[4]), ctc_oui, 3); pstsendtlv->aucversionlist[7] = 0x13; vosmemcpy(&(pstsendtlv->aucversionlist[8]), ctc_oui, 3); pstsendtlv->aucversionlist[11] = 0x01;} 以下示出c语言中更简洁的实现方式(基于二维数组): /*********************************************************************** 版本控制字数组定义* goamctrlcode: bitmap控制字。bit-x为0时上报对应版本,bit-x为1时屏蔽对应版本。* ctrl_vers_num: 可控版本个数。* ctrl_code_num: 控制字个数。与ctrl_vers_num有关。* goamverctrlmap: 版本控制字数组。行对应控制字,列对应可控版本。 元素值为0时不上报对应版本,元素值非0时上报该元素值。* note: 该数组旨在实现“数据与控制隔离”。后续若要新增可控版本,只需修改 -- ctrl_vers_num -- goamverctrlmap新增行(控制字) -- goamverctrlmap新增列(可控版本)**********************************************************************/#define ctrl_vers_num 3#define ctrl_code_num (1
aucversionlist[index], ctc_oui, 3);index += 3;pstsendtlv->aucversionlist[index++] = 0x20;vosmemcpy(&pstsendtlv->aucversionlist[index], ctc_oui, 3);index += 3;pstsendtlv->aucversionlist[index++] = 0x13;vosmemcpy(&pstsendtlv->aucversionlist[index], ctc_oui, 3);index += 3;pstsendtlv->aucversionlist[index++] = 0x01;pstsendtlv->uclength = info_type_vers_len + index;
1.2.7 消息处理
问题:终端输入不同的打印命令,调用相应的打印函数,以控制不同级别的打印。 这是一段消息(事件)驱动程序。本模块接收其他模块(如串口驱动)发送的消息,根据消息中的打印级别字符串和开关模式,调用不同函数进行处理。常见的实现方法如下:
void logall(void){ g_log_control[0] = 0xffffffff;}void noanylog(void){ g_log_control[0] = 0;}void logoam(void){ g_log_control[0] |= (0x01 << function_oam);}void nologoam(void){ g_log_control[0] &= ~(0x01 << function_oam);}//... ...void logexec(char *name, int8u enable){ ctcoamlog(function_oam,log %s %d,name,enable);if (enable == 1) /*log*/ {if (strcasecmp(name,all) == 0) { /*字符串比较,不区分大小写*/ logall(); } else if (strcasecmp(name,oam) == 0) { logoam(); } else if (strcasecmp(name,pon) == 0) { logpon();//... ... } else if (strcasecmp(name,version) == 0) { logversion(); }else if (enable == 0) /*nolog*/ {if (strcasecmp(name,all) == 0) { noanylog(); } else if (strcasecmp(name,oam) == 0) { nologoam(); } else if (strcasecmp(name,pon) == 0) { nologpon();//... ... } else if (strcasecmp(name,version) == 0) { nologversion(); }else {printf(bad log para); }} 以下示出c语言中更简洁的实现方式: typedef struct{ oam_log_off = (int8u)0, oam_log_on = (int8u)1}e_oam_log_mode;typedef func_status (*oamloghandler)(void);typedef struct{ char *pszlogcls; /* 打印级别 */ e_oam_log_mode elogmode; /* 打印模式 */ oamloghandler fnloghandler; /* 打印函数 */}t_oam_log_map;t_oam_log_map goamlogmap[] = { {all, oam_log_off, noanylog}, {oam, oam_log_off, nologoam},//... ... {version, oam_log_off, nologversion}, {all, oam_log_on, logall}, {oam, oam_log_on, logoam},//... ... {version, oam_log_on, logversion}};int32u goamlogmapnum = sizeof(goamlogmap) / sizeof(t_oam_log_map);void logexec(char *pszname, int8u ucswitch){ int8u ucidx = 0;for(; ucidx bitn)。 * bit0~n分别对应e_log_type各枚举值(除log_all外)。 * bitx为0时关闭日志类型对应的日志功能,bitx为1时则予以打开。 * 变量范围:该变量为四字节整型静态全局变量,即支持32种日志类型。 * 访问说明:通过getomcilogctrl/setomcilogctrl/omcilogctrl函数访问/设置控制字。 *****************************************************************************/static int32u gomcilogctrl = 0;//日志类型字符串数组,下标为各字符串所对应的日志类型枚举值。static const int8u* palogtypename[] = {norm, frame, pon, ethernet, internet,multicast, qos, ces, voip, alarm,performance, version, xdsl, db};static const int8u uclogtypenamenum = sizeof(palogtypename) / sizeof(palogtypename[0]);static void setgloballogctrl(e_log_type elogtype, int8u uclogswitch){if(log_on == uclogswitch) gomcilogctrl = log_all;else gomcilogctrl = 0;}static void setspecificlogctrl(e_log_type elogtype, int8u uclogswitch){if(log_on == uclogswitch) set_bit(gomcilogctrl, elogtype);else clr_bit(gomcilogctrl, elogtype);}void omcilogctrl(char *pszlogtype, int8u uclogswitch){if(0 == strncasecmp(pszlogtype, all, log_type_cmp_len)) { setgloballogctrl(log_all, uclogswitch);return; } int8u ucidx = 0;for(ucidx = 0; ucidx y?x:y; }int min(int x, int y) { return x 其中,第三个参数是一个没有参数且返回int型变量的函数指针。但后面却用process(a,b,max)的方式进行调用,max带有两个参数。若编译器未检查出错误,而又不小心将return (*f)(x,y);写成return (*f)(x);,那么后果可能很严重。
因此在c语言中使用函数指针时,一定要小心类型陷阱。
1.2MHz ThinSOT升压转换器采用单节电池供电节省电路板空间
对互阻抗放大器的评估(第 1 部分)
三极管的分类、工作原理及功能应用
中芯国际董事会宣布,刘遵义获委任为公司第二类独立非执行董事
韩国计划用5G取代有线网络办公
C语言驱动编程详解
创维25NF8800的IC2总线调整的又一法
赛灵思公司宣布在会上展示在光纤网络上的技术领先优势
虹科与CTC正式合作,致力于提供更优质的工业加速度计解决方案!
韩国三家移动运营商推出了RCS平台来取代短信服务
东软载波智能照明系统助力提升应用场景舒适度
南方电网公司正在全面推进智能电网建设
GitHub上给老照片上色的一个项目:DeOldify
机械锻压机操作步骤
光缆的储存方法
电机新时代,深圳复兴伟业让电机控制更加智能、可靠!
GPRS无线指纹身份验证系统的应用研究
基于ARM在cpu上做神经网络加速
嵌套堆叠区域对电气和机械设计性能精确控制
语音识别芯片NRK3301丨在智能茶吧机的应用