C語言表驅動法編程實踐

數(shù)據(jù)壓倒一切觉壶。如果選擇了正確的數(shù)據(jù)結構并把一切組織的井井有條或南，正確的算法就不言自明古劲。編程的核心是數(shù)據(jù)結構，而不是算法璃哟。

——Rob Pike?

說明

? ? ?本文基于這樣的認識：數(shù)據(jù)是易變的，邏輯是穩(wěn)定的喊递。

? ? ?本文例舉的編程實現(xiàn)多為代碼片段随闪，但不影響描述的完整性。

? ? ?本文例舉的編程雖然基于C語言骚勘，但其編程思想也適用于其他語言铐伴。

? ? ?此外，本文不涉及語言相關的運行效率討論俏讹。

1 概念提出

? ? ?所謂表驅動法(Table-Driven Approach)簡而言之就是用查表的方法獲取數(shù)據(jù)当宴。此處的“表”通常為數(shù)組，但可視為數(shù)據(jù)庫的一種體現(xiàn)泽疆。

? ? ?根據(jù)字典中的部首檢字表查找讀音未知的漢字就是典型的表驅動法户矢，即以每個字的字形為依據(jù)，計算出一個索引值殉疼，并映射到對應的頁數(shù)梯浪。相比一頁一頁地順序翻字典查字，部首檢字法效率極高瓢娜。

? ? ?具體到編程方面挂洛，在數(shù)據(jù)不多時可用邏輯判斷語句(if…else或switch…case)來獲取值；但隨著數(shù)據(jù)的增多眠砾，邏輯語句會越來越長虏劲，此時表驅動法的優(yōu)勢就開始顯現(xiàn)。

? ? ?例如，用36進制(A表示10柒巫，B表示11励堡，…)表示更大的數(shù)字，邏輯判斷語句如下：

?? ? 當然也可以用switch…case結構吻育，但實現(xiàn)都很冗長念秧。而用表驅動法(將numChar存入數(shù)組)則非常直觀和簡潔。如：

? ? ?像這樣直接將變量當作下數(shù)組下標來讀取數(shù)值的方法就是直接查表法布疼。

? ? ?注意摊趾，如果熟悉字符串操作，則上述寫法可以更簡潔：

? ? ?使用表驅動法時需要關注兩個問題：一是如何查表游两，從表中讀取正確的數(shù)據(jù)砾层；二是表里存放什么，如數(shù)值或函數(shù)指針贱案。前者參見1.1節(jié)“查表方式”內(nèi)容肛炮，后者參見1.2節(jié)“實戰(zhàn)示例”內(nèi)容。

1.1 查表方式

? ? ?常用的查表方式有直接查找宝踪、索引查找和分段查找等侨糟。

1.1.1 直接查找

? ? ?即直接通過數(shù)組下標獲取到數(shù)據(jù)。如果熟悉哈希表的話瘩燥，可以很容易看出這種查表方式就是哈希表的直接訪問法秕重。

? ? ?如獲取星期名稱，邏輯判斷語句如下：

? ? ?而實現(xiàn)同樣的功能厉膀，可將這些數(shù)據(jù)存儲到一個表里：

? ? ?類似哈希表特性溶耘，表驅動法適用于無需有序遍歷數(shù)據(jù)，且數(shù)據(jù)量大小可提前預測的情況服鹅。

? ? ?對于過于復雜和龐大的判斷凳兵，可將數(shù)據(jù)存為文件，需要時加載文件初始化數(shù)組企软，從而在不修改程序的情況下調(diào)整里面的數(shù)值庐扫。

? ? ?有時，訪問之前需要先進行一次鍵值轉換仗哨。如表驅動法表示端口忙閑時聚蝶，需將槽位端口號映射為全局編號。所生成的端口數(shù)目大小的數(shù)組藻治，其下標對應全局端口編號碘勉，元素值表示相應端口的忙閑狀態(tài)。

1.1.2 索引查找

? ? ?有時通過一次鍵值轉換桩卵，依然無法把數(shù)據(jù)(如英文單詞等)轉為鍵值验靡。此時可將轉換的對應關系寫到一個索引表里倍宾，即索引訪問。

?如現(xiàn)有100件商品胜嗓，4位編號高职，范圍從0000到9999。此時只需要申請一個長度為100的數(shù)組辞州，且對應2位鍵值怔锌。但將4位的編號轉換為2位的鍵值，可能過于復雜或沒有規(guī)律变过，最合適的方法是建立一個保存該轉換關系的索引表埃元。采用索引訪問既節(jié)省內(nèi)存，又方便維護媚狰。比如索引A表示通過名稱訪問岛杀，索引B表示通過編號訪問。

1.1.3 分段查找

?通過確定數(shù)據(jù)所處的范圍確定分類(下標)崭孤。有的數(shù)據(jù)可分成若干區(qū)間类嗤，即具有階梯性，如分數(shù)等級辨宠。此時可將每個區(qū)間的上限(或下限)存到一個表中遗锣，將對應的值存到另一表中，通過第一個表確定所處的區(qū)段嗤形，再由區(qū)段下標在第二個表里讀取相應數(shù)值精偿。注意要留意端點，可用二分法查找派殷，另外可考慮通過索引方法來代替。

? ? ?如根據(jù)分數(shù)查績效等級：

? ? ?上述兩張表(數(shù)組)也可合并為一張表(結構體數(shù)組)墓阀，如下所示：

? ? ?該表結構已具備的數(shù)據(jù)庫的雛形毡惜，并可擴展支持更為復雜的數(shù)據(jù)。其查表方式通常為索引查找斯撮，偶爾也為分段查找经伙；當索引具有規(guī)律性(如連續(xù)整數(shù))時，退化為直接查找勿锅。

? ? ?使用分段查找法時應注意邊界帕膜，將每一分段范圍的上界值都考慮在內(nèi)。找出所有不在最高一級范圍內(nèi)的值溢十，然后把剩下的值全部歸入最高一級中垮刹。有時需要人為地為最高一級范圍添加一個上界。

? ? ?同時應小心不要錯誤地用“<”來代替“<=”张弛。要保證循環(huán)在找出屬于最高一級范圍內(nèi)的值后恰當?shù)亟Y束荒典，同時也要保證恰當處理范圍邊界酪劫。

1.2 實戰(zhàn)示例

??? 本節(jié)多數(shù)示例取自實際項目。表形式為一維數(shù)組寺董、二維數(shù)組和結構體數(shù)組覆糟；表內(nèi)容有數(shù)據(jù)、字符串和函數(shù)指針遮咖√沧郑基于表驅動的思想，表形式和表內(nèi)容可衍生出豐富的組合御吞。

1.2.1 字符統(tǒng)計

? ? ?問題：統(tǒng)計用戶輸入的一串數(shù)字中每個數(shù)字出現(xiàn)的次數(shù)麦箍。

? ? ?普通解法主體代碼如下：

? ? ?這種解法的缺點顯而易見，既不美觀也不靈活魄藕。其問題關鍵在于未將數(shù)字字符與數(shù)組aDigitCharNum下標直接關聯(lián)起來内列。

? ? ?以下示出更簡潔的實現(xiàn)方式：

? ? ?上述實現(xiàn)考慮到0也為數(shù)字字符。該解法也可擴展至統(tǒng)計所有ASCII可見字符背率。

1.2.2 月天校驗

? ? ?問題：對給定年份和月份的天數(shù)進行校驗(需區(qū)分平年和閏年)话瞧。

? ? ?普通解法主體代碼如下：

? ? ?以下示出更簡潔的實現(xiàn)方式：

1.2.3 名稱構造

? ? ?問題：根據(jù)WAN接口承載的業(yè)務類型(Bitmap)構造業(yè)務類型名稱字符串。

? ? ?普通解法主體代碼如下：

? ? ?以下示出C語言中更簡潔的實現(xiàn)方式：

? ? ?新的實現(xiàn)將數(shù)據(jù)和邏輯分離寝姿，維護起來非常方便交排。只要邏輯(規(guī)則)不變，則唯一可能的改動就是數(shù)據(jù)(paSvrNames)饵筑。

1.2.4 值名解析

? ? ?問題：根據(jù)枚舉變量取值輸出其對應的字符串埃篓，如PORT_FE(1)輸出“Fe”。

? ? ?以下給出NameParser的簡單應用示例：

? ? ?gUniNameMap在實際項目中有十余個條目根资，若采用邏輯鏈實現(xiàn)將非常冗長架专。

1.2.5 取值映射

? ? ?問題：不同模塊間同一參數(shù)枚舉值取值可能有所差異，需要適配玄帕。

? ? ?此處不再給出普通的switch…case或if…else if…else結構部脚，而直接示出以下表驅動實現(xiàn)：

? ? ?相應地，從loopMIBState映射到loopMEState需要定義一個ConvertLoopMIBStateToMEState函數(shù)裤纹。更進一步委刘，所有類似的一對一映射關系都必須如上的映射(轉換)函數(shù)，相當繁瑣鹰椒。

? ? ?事實上锡移，從抽象層面看，該映射關系非常簡單漆际。提取共性后定義帶參數(shù)宏淆珊，如下所示：

? ? 參數(shù)取值轉換時直接調(diào)用統(tǒng)一的映射器宏，如下：

? ? ?另舉一例：

1.2.6 版本控制

?問題：控制OLT與ONU之間的版本協(xié)商奸汇。ONU本地設置三比特控制字套蒂，其中bit2(MSB)~bit0(LSB)分別對應0x21钞支、0x30和0xAA版本號；且bitX為0表示上報對應版本號操刀，bitX為1表示不上報對應版本號烁挟。其他版本號如0x20、0x13和0x1必須上報骨坑，即不受控制撼嗓。

? ? ?最初的實現(xiàn)采用if…else if…else結構，代碼非常冗長欢唾，如下：

? ? 以下示出C語言中更簡潔的實現(xiàn)方式(基于二維數(shù)組)：

1.2.7 消息處理

? ? ?問題：終端輸入不同的打印命令且警，調(diào)用相應的打印函數(shù)蜡感，以控制不同級別的打印个扰。

? ? ?這是一段消息(事件)驅動程序。本模塊接收其他模塊(如串口驅動)發(fā)送的消息精绎，根據(jù)消息中的打印級別字符串和開關模式祟霍，調(diào)用不同函數(shù)進行處理杏头。常見的實現(xiàn)方法如下：

? ? ?以下示出C語言中更簡潔的實現(xiàn)方式：

? ? ?這種表驅動消息處理實現(xiàn)的優(yōu)點如下：

增強可讀性，消息如何處理從表中一目了然沸呐。

增強可擴展性醇王。更容易修改，要增加新的消息崭添，只要修改數(shù)據(jù)即可寓娩，不需要修改流程。

降低復雜度呼渣。通過把程序邏輯的復雜度轉移到人類更容易處理的數(shù)據(jù)中來棘伴，從而達到控制復雜度的目標。

主干清晰屁置，代碼重用焊夸。

? ? ?若各索引為順序枚舉值，則建立多維數(shù)組(每維對應一個索引)缰犁，根據(jù)下標直接定位到處理函數(shù)淳地，效率會更高怖糊。

? ? ?注意帅容，考慮到本節(jié)實例中l(wèi)ogOam/logPon或nologOam/nologPon等函數(shù)本質上是基于打印級別的比特操作，因此可進一步簡化伍伤。以下例舉其相似實現(xiàn)：

1.2.8 掩碼表

參見《采用掩碼方式簡化產(chǎn)品國家地區(qū)支持能力的表示》一文并徘。

該例實現(xiàn)中用到消息、掩碼扰魂、函數(shù)指針等概念麦乞。

2 編程思想

? ? ?表驅動法屬于數(shù)據(jù)驅動編程的一種蕴茴，其核心思想在《Unix編程藝術》和《代碼大全2》中均有闡述。兩者均認為人類閱讀復雜數(shù)據(jù)結構遠比復雜的控制流程容易姐直，即相對于程序邏輯倦淀，人類更擅長于處理數(shù)據(jù)。

? ? ?本節(jié)將由Unix設計原則中的“分離原則”和“表示原則”展開声畏。

分離原則：策略同機制分離撞叽，接口同引擎分離

? ? ?機制即提供的功能；策略即如何使用功能插龄。

? ? ?策略的變化要遠遠快于機制的變化愿棋。將兩者分離，可以使機制相對保持穩(wěn)定均牢，而同時支持策略的變化糠雨。

? ? ?代碼大全中提到“隔離變化”的概念，以及設計模式中提到的將易變化的部分和不易變化的部分分離也是這個思路徘跪。

表示原則：把知識疊入數(shù)據(jù)以求邏輯質樸而健壯

? ? ?即使最簡單的程序邏輯讓人類來驗證也很困難甘邀，但就算是很復雜的數(shù)據(jù)，對人類來說真椿，還是相對容易推導和建模的鹃答。數(shù)據(jù)比編程邏輯更容易駕馭。在復雜數(shù)據(jù)和復雜代碼中選擇突硝，寧可選擇前者测摔。更進一步，在設計中解恰，應該主動將代碼的復雜度轉移到數(shù)據(jù)中去(參考“版本控制”)锋八。

? ? ?在“消息處理”示例中，每個消息處理的邏輯不變护盈，但消息可能是變化的挟纱。將容易變化的消息和不容易變化的查找邏輯分離，即“隔離變化”腐宋。此外紊服，該例也體現(xiàn)消息內(nèi)部的處理邏輯(機制)和不同的消息處理(策略)分離。

? ? ?數(shù)據(jù)驅動編程可以應用于：

函數(shù)級設計胸竞，如本文示例欺嗤。

程序級設計，如用表驅動法實現(xiàn)狀態(tài)機卫枝。

系統(tǒng)級設計煎饼，如DSL。

? ? ?注意校赤，數(shù)據(jù)驅動編程不是全新的編程模型吆玖，只是一種設計思路筒溃，在Unix/Linux開源社區(qū)應用很多。數(shù)據(jù)驅動編程中沾乘，數(shù)據(jù)不但表示某個對象的狀態(tài)怜奖，實際上還定義程序的流程，這點不同于面向對象設計中的數(shù)據(jù)“封裝”翅阵。

3 附錄

3.1 網(wǎng)友觀點

? ? ?(以下觀點摘自博客園網(wǎng)友“七心葵”的回帖烦周，非常具有啟發(fā)性。)

? ? ?Booch的《面向對象分析與設計》一書中怎顾，提到所有的程序設計語言大概有3個源流：結構化編程读慎；面向對象編程；數(shù)據(jù)驅動編程槐雾。

? ? ?我認為數(shù)據(jù)驅動編程的本質是“參數(shù)化抽象”的思想夭委，不同于OO的“規(guī)范化抽象”的思想。

? ? ?數(shù)據(jù)驅動編程在網(wǎng)絡游戲開發(fā)過程中很常用募强，但是少有人專門提到這個詞株灸。

? ? ?數(shù)據(jù)驅動編程有很多名字：元編程，解釋器/虛擬機擎值，LOP/微語言/DSL等慌烧。包括聲明式編程、標記語言鸠儿、甚至所見即所得的拖放控件屹蚊，都算是數(shù)據(jù)驅動編程的一種吧。

? ? ?數(shù)據(jù)驅動編程可以幫助處理復雜性进每，和結構化編程汹粤、OO 均可相容。(正交的角度)

?? ? 將變和不變的部分分離田晚，策略和機制分離嘱兼，由此聯(lián)想到的還有：(數(shù)據(jù)和代碼的分離，微語言和解釋器的分離贤徒，被生成代碼和代碼生成器的分離)芹壕；更近一步：(微內(nèi)核插件式體系結構)?

?元編程應該說是更加泛化的數(shù)據(jù)驅動編程，元編程不是新加入一個間接層接奈，而是退居一步踢涌，使得當前的層變成一個間接層。元編程分為靜態(tài)元編程(編譯時)和動態(tài)元編程(運行時)鲫趁，靜態(tài)元編程本質上是一種

代碼生成技術或者編譯器技術斯嚎；動態(tài)元編程一般通過解釋器(或虛擬機)加以實現(xiàn)利虫。

?數(shù)據(jù)驅動編程當然也不應該說是“反抽象的”挨厚，但的確與“OO抽象”的思維方式是迥然不同堡僻，涇渭分明的，如TAOUP一書中所述：“在Unix的模塊化傳統(tǒng)和圍繞OO語言發(fā)展起來的使用模式之間疫剃，存在著緊張的對立關系”應該說數(shù)據(jù)驅動編程的思路與結構化編程和OO是正交的钉疫，更類似一種“跳出三界外，不在五行中”的做法巢价。

? ? ?編程和人的關系

? ? ?人類心智的限制牲阁，一切的背后都有人的因素作為依據(jù)：

? ? ?a 人同時關注的信息數(shù)量：7+-2 (所以要分模塊)

? ? ?b 人接收一組新信息的平均時間5s (所以要簡單，系統(tǒng)總的模塊數(shù)不要太多)

? ? ?c 人思維的直觀性(人的視覺能力和模糊思維能力)壤躲，這意味這兩點：

? ? ?A “直”——更善于思考自己能直接接觸把玩的東西城菊；(所以要“淺平透”、使用具象的設計碉克，要盡量代碼中只有順直的流程)凌唬，

? ? ?B “觀”——更善于觀圖而不是推算邏輯；(所以要表驅動法漏麦，數(shù)據(jù)驅動編程客税，要UML，要可視化編程——當然MDA是太理想化了)

? ? ?d 人不能持續(xù)集中注意力(人在一定的代碼行數(shù)中產(chǎn)生的bug數(shù)量的比例是一定的撕贞，所以語言有具有表現(xiàn)力更耻，要體現(xiàn)表達的經(jīng)濟性)

? ? ?所以要機制與策略分離，要數(shù)據(jù)和代碼分離(數(shù)據(jù)驅動編程)捏膨，要微語言秧均，要DSL，要LOP……

? ? ?e 人是有創(chuàng)造欲号涯，有現(xiàn)實利益心的(只要偶可能總是不夠遵從規(guī)范熬北，或想創(chuàng)造規(guī)范謀利——只要成本能承受，在硬件領域就不行)

? ? ?另外诚隙，開一個有意思的玩笑讶隐，Unix編程藝術藝術的英文縮寫為TAOUP，我覺得可以理解為UP之TAO——向上拋出之道——將復雜的易變的邏輯作為數(shù)據(jù)或更高層代碼拋給上層久又！

3.2 函數(shù)指針

? ? ?“消息處理”一節(jié)示例中的函數(shù)指針有點插件結構的味道巫延。可對這些插件進行方便替換地消，新增炉峰，刪除，從而改變程序的行為脉执。而這種改變疼阔，對事件處理函數(shù)的查找又是隔離的(隔離變化)。

? ? ?函數(shù)指針非常有用，但使用時需注意其缺陷：無法檢查參數(shù)(parameter)和返回值(return value)的類型婆廊。因為函數(shù)已經(jīng)退化成指針迅细，而指針不攜帶這些類型信息。缺少類型檢查淘邻，當參數(shù)或返回值不一致時茵典，可能會造成嚴重的錯誤。

? ? ?例如宾舅，定義三個函數(shù)统阿，分別具有兩個參數(shù)：

? ? ?int max(int x, int y)? {? return x>y?x:y; ?}

? ? ?int min(int x, int y)? {? return x

? ? ?int add(int x, int y)? {? return x+y; ?}

? ? ?而處理函數(shù)卻定義為：

? ? ?int process(int x, int y, int (*f)()) ?{ ?return (*f)(x, y); ?}

?其中，第三個參數(shù)是一個沒有參數(shù)且返回int型變量的函數(shù)指針筹我。但后面卻用process(a,b,max)的方式進行調(diào)用扶平，max帶有兩個參數(shù)。若編譯器未檢查出錯誤蔬蕊，而又不小心將return

(*f)(x,y);寫成return (*f)(x);蜻直，那么后果可能很嚴重。

? ? ?因此在C語言中使用函數(shù)指針時袁串，一定要小心"類型陷阱"概而。