C語(yǔ)言的驅(qū)動(dòng)法編程詳細(xì)解析（超多代碼案例）
[導(dǎo)讀]數(shù)據(jù)壓倒一切。如果選擇了正確的數(shù)據(jù)結(jié)構(gòu)并把一切組織的井井有條，正確的算法就不言自明。編程的核心是數(shù)據(jù)結(jié)構(gòu)，而不是算法。——RobPike說(shuō)明本文基于這樣的認(rèn)識(shí)：數(shù)據(jù)是易變的，邏輯是穩(wěn)定的。本文例舉的編程實(shí)現(xiàn)多為代碼片段，但不影響描述的完整性。本文例舉的編程雖然基于C語(yǔ)言，但其編程...
數(shù)據(jù)壓倒一切。如果選擇了正確的數(shù)據(jù)結(jié)構(gòu)并把一切組織的井井有條，正確的算法就不言自明。編程的核心是數(shù)據(jù)結(jié)構(gòu)，而不是算法。
——Rob Pike
本文基于這樣的認(rèn)識(shí)：數(shù)據(jù)是易變的，邏輯是穩(wěn)定的。本文例舉的編程實(shí)現(xiàn)多為代碼片段，但不影響描述的完整性。
本文例舉的編程雖然基于C語(yǔ)言，但其編程思想也適用于其他語(yǔ)言。此外，本文不涉及語(yǔ)言相關(guān)的運(yùn)行效率討論。
所謂表驅(qū)動(dòng)法(Table-Driven Approach)簡(jiǎn)而言之就是用查表的方法獲取數(shù)據(jù)。此處的“表”通常為數(shù)組，但可視為數(shù)據(jù)庫(kù)的一種體現(xiàn)。
根據(jù)字典中的部首檢字表查找讀音未知的漢字就是典型的表驅(qū)動(dòng)法，即以每個(gè)字的字形為依據(jù)，計(jì)算出一個(gè)索引值，并映射到對(duì)應(yīng)的頁(yè)數(shù)。相比一頁(yè)一頁(yè)地順序翻字典查字，部首檢字法效率極高。
具體到編程方面，在數(shù)據(jù)不多時(shí)可用邏輯判斷語(yǔ)句(if…else或switch…case)來(lái)獲取值；但隨著數(shù)據(jù)的增多，邏輯語(yǔ)句會(huì)越來(lái)越長(zhǎng)，此時(shí)表驅(qū)動(dòng)法的優(yōu)勢(shì)就開(kāi)始顯現(xiàn)。例如，用36進(jìn)制(A表示10，B表示11，…)表示更大的數(shù)字，邏輯判斷語(yǔ)句如下：
當(dāng)然也可以用switch…case結(jié)構(gòu)，但實(shí)現(xiàn)都很冗長(zhǎng)。而用表驅(qū)動(dòng)法(將numChar存入數(shù)組)則非常直觀和簡(jiǎn)潔。如：
像這樣直接將變量當(dāng)作下數(shù)組下標(biāo)來(lái)讀取數(shù)值的方法就是直接查表法。
注意，如果熟悉字符串操作，則上述寫(xiě)法可以更簡(jiǎn)潔：
使用表驅(qū)動(dòng)法時(shí)需要關(guān)注兩個(gè)問(wèn)題：一是如何查表，從表中讀取正確的數(shù)據(jù)；二是表里存放什么，如數(shù)值或函數(shù)指針。前者參見(jiàn)1.1節(jié)“查表方式”內(nèi)容，后者參見(jiàn)1.2節(jié)“實(shí)戰(zhàn)示例”內(nèi)容。
常用的查表方式有直接查找、索引查找和分段查找等。
即直接通過(guò)數(shù)組下標(biāo)獲取到數(shù)據(jù)。如果熟悉哈希表的話，可以很容易看出這種查表方式就是哈希表的直接訪問(wèn)法。
如獲取星期名稱(chēng)，邏輯判斷語(yǔ)句如下：
類(lèi)似哈希表特性，表驅(qū)動(dòng)法適用于無(wú)需有序遍歷數(shù)據(jù)，且數(shù)據(jù)量大小可提前預(yù)測(cè)的情況。
對(duì)于過(guò)于復(fù)雜和龐大的判斷，可將數(shù)據(jù)存為文件，需要時(shí)加載文件初始化數(shù)組，從而在不修改程序的情況下調(diào)整里面的數(shù)值。
有時(shí)，訪問(wèn)之前需要先進(jìn)行一次鍵值轉(zhuǎn)換。如表驅(qū)動(dòng)法表示端口忙閑時(shí)，需將槽位端口號(hào)映射為全局編號(hào)。所生成的端口數(shù)目大小的數(shù)組，其下標(biāo)對(duì)應(yīng)全局端口編號(hào)，元素值表示相應(yīng)端口的忙閑狀態(tài)。
有時(shí)通過(guò)一次鍵值轉(zhuǎn)換，依然無(wú)法把數(shù)據(jù)(如英文單詞等)轉(zhuǎn)為鍵值。此時(shí)可將轉(zhuǎn)換的對(duì)應(yīng)關(guān)系寫(xiě)到一個(gè)索引表里，即索引訪問(wèn)。
如現(xiàn)有100件商品，4位編號(hào)，范圍從0000到9999。此時(shí)只需要申請(qǐng)一個(gè)長(zhǎng)度為100的數(shù)組，且對(duì)應(yīng)2位鍵值。但將4位的編號(hào)轉(zhuǎn)換為2位的鍵值，可能過(guò)于復(fù)雜或沒(méi)有規(guī)律，最合適的方法是建立一個(gè)保存該轉(zhuǎn)換關(guān)系的索引表。采用索引訪問(wèn)既節(jié)省內(nèi)存，又方便維護(hù)。比如索引A表示通過(guò)名稱(chēng)訪問(wèn)，索引B表示通過(guò)編號(hào)訪問(wèn)。
通過(guò)確定數(shù)據(jù)所處的范圍確定分類(lèi)(下標(biāo))。有的數(shù)據(jù)可分成若干區(qū)間，即具有階梯性，如分?jǐn)?shù)等級(jí)。此時(shí)可將每個(gè)區(qū)間的上限(或下限)存到一個(gè)表中，將對(duì)應(yīng)的值存到另一表中，通過(guò)第一個(gè)表確定所處的區(qū)段，再由區(qū)段下標(biāo)在第二個(gè)表里讀取相應(yīng)數(shù)值。注意要留意端點(diǎn)，可用二分法查找，另外可考慮通過(guò)索引方法來(lái)代替。
如根據(jù)分?jǐn)?shù)查績(jī)效等級(jí)：
上述兩張表(數(shù)組)也可合并為一張表(結(jié)構(gòu)體數(shù)組)，如下所示：
該表結(jié)構(gòu)已具備的數(shù)據(jù)庫(kù)的雛形，并可擴(kuò)展支持更為復(fù)雜的數(shù)據(jù)。其查表方式通常為索引查找，偶爾也為分段查找；當(dāng)索引具有規(guī)律性(如連續(xù)整數(shù))時(shí)，退化為直接查找。
使用分段查找法時(shí)應(yīng)注意邊界，將每一分段范圍的上界值都考慮在內(nèi)。找出所有不在最高一級(jí)范圍內(nèi)的值，然后把剩下的值全部歸入最高一級(jí)中。有時(shí)需要人為地為最高一級(jí)范圍添加一個(gè)上界。
同時(shí)應(yīng)小心不要錯(cuò)誤地用“<”來(lái)代替“<=”。要保證循環(huán)在找出屬于最高一級(jí)范圍內(nèi)的值后恰當(dāng)?shù)亟Y(jié)束，同時(shí)也要保證恰當(dāng)處理范圍邊界。
本節(jié)多數(shù)示例取自實(shí)際項(xiàng)目。表形式為一維數(shù)組、二維數(shù)組和結(jié)構(gòu)體數(shù)組；表內(nèi)容有數(shù)據(jù)、字符串和函數(shù)指針?；诒眚?qū)動(dòng)的思想，表形式和表內(nèi)容可衍生出豐富的組合。
問(wèn)題：統(tǒng)計(jì)用戶輸入的一串?dāng)?shù)字中每個(gè)數(shù)字出現(xiàn)的次數(shù)。
普通解法主體代碼如下：
這種解法的缺點(diǎn)顯而易見(jiàn)，既不美觀也不靈活。其問(wèn)題關(guān)鍵在于未將數(shù)字字符與數(shù)組aDigitCharNum下標(biāo)直接關(guān)聯(lián)起來(lái)。
以下示出更簡(jiǎn)潔的實(shí)現(xiàn)方式：
上述實(shí)現(xiàn)考慮到0也為數(shù)字字符。該解法也可擴(kuò)展至統(tǒng)計(jì)所有ASCII可見(jiàn)字符。
問(wèn)題：對(duì)給定年份和月份的天數(shù)進(jìn)行校驗(yàn)(需區(qū)分平年和閏年)。
普通解法主體代碼如下：
——Rob Pike
說(shuō)明
本文基于這樣的認(rèn)識(shí)：數(shù)據(jù)是易變的，邏輯是穩(wěn)定的。本文例舉的編程實(shí)現(xiàn)多為代碼片段，但不影響描述的完整性。
本文例舉的編程雖然基于C語(yǔ)言，但其編程思想也適用于其他語(yǔ)言。此外，本文不涉及語(yǔ)言相關(guān)的運(yùn)行效率討論。
1 概念提出
所謂表驅(qū)動(dòng)法(Table-Driven Approach)簡(jiǎn)而言之就是用查表的方法獲取數(shù)據(jù)。此處的“表”通常為數(shù)組，但可視為數(shù)據(jù)庫(kù)的一種體現(xiàn)。
根據(jù)字典中的部首檢字表查找讀音未知的漢字就是典型的表驅(qū)動(dòng)法，即以每個(gè)字的字形為依據(jù)，計(jì)算出一個(gè)索引值，并映射到對(duì)應(yīng)的頁(yè)數(shù)。相比一頁(yè)一頁(yè)地順序翻字典查字，部首檢字法效率極高。
具體到編程方面，在數(shù)據(jù)不多時(shí)可用邏輯判斷語(yǔ)句(if…else或switch…case)來(lái)獲取值；但隨著數(shù)據(jù)的增多，邏輯語(yǔ)句會(huì)越來(lái)越長(zhǎng)，此時(shí)表驅(qū)動(dòng)法的優(yōu)勢(shì)就開(kāi)始顯現(xiàn)。例如，用36進(jìn)制(A表示10，B表示11，…)表示更大的數(shù)字，邏輯判斷語(yǔ)句如下：
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';}當(dāng)然也可以用switch…case結(jié)構(gòu)，但實(shí)現(xiàn)都很冗長(zhǎng)。而用表驅(qū)動(dòng)法(將numChar存入數(shù)組)則非常直觀和簡(jiǎn)潔。如：
CHAR aNumChars[] = {'0', '1', '2', /*3~9*/'A', 'B', 'C', /*D~Y*/'Z'};CHAR ucNumChar = aNumChars[ucNum % sizeof(aNumChars)];像這樣直接將變量當(dāng)作下數(shù)組下標(biāo)來(lái)讀取數(shù)值的方法就是直接查表法。
注意，如果熟悉字符串操作，則上述寫(xiě)法可以更簡(jiǎn)潔：
CHAR ucNumChar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[ucNum];使用表驅(qū)動(dòng)法時(shí)需要關(guān)注兩個(gè)問(wèn)題：一是如何查表，從表中讀取正確的數(shù)據(jù)；二是表里存放什么，如數(shù)值或函數(shù)指針。前者參見(jiàn)1.1節(jié)“查表方式”內(nèi)容，后者參見(jiàn)1.2節(jié)“實(shí)戰(zhàn)示例”內(nèi)容。
1.1 查表方式
常用的查表方式有直接查找、索引查找和分段查找等。
1.1.1 直接查找
即直接通過(guò)數(shù)組下標(biāo)獲取到數(shù)據(jù)。如果熟悉哈希表的話，可以很容易看出這種查表方式就是哈希表的直接訪問(wèn)法。
如獲取星期名稱(chēng)，邏輯判斷語(yǔ)句如下：
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];類(lèi)似哈希表特性，表驅(qū)動(dòng)法適用于無(wú)需有序遍歷數(shù)據(jù)，且數(shù)據(jù)量大小可提前預(yù)測(cè)的情況。
對(duì)于過(guò)于復(fù)雜和龐大的判斷，可將數(shù)據(jù)存為文件，需要時(shí)加載文件初始化數(shù)組，從而在不修改程序的情況下調(diào)整里面的數(shù)值。
有時(shí)，訪問(wèn)之前需要先進(jìn)行一次鍵值轉(zhuǎn)換。如表驅(qū)動(dòng)法表示端口忙閑時(shí)，需將槽位端口號(hào)映射為全局編號(hào)。所生成的端口數(shù)目大小的數(shù)組，其下標(biāo)對(duì)應(yīng)全局端口編號(hào)，元素值表示相應(yīng)端口的忙閑狀態(tài)。
1.1.2 索引查找
有時(shí)通過(guò)一次鍵值轉(zhuǎn)換，依然無(wú)法把數(shù)據(jù)(如英文單詞等)轉(zhuǎn)為鍵值。此時(shí)可將轉(zhuǎn)換的對(duì)應(yīng)關(guān)系寫(xiě)到一個(gè)索引表里，即索引訪問(wèn)。
如現(xiàn)有100件商品，4位編號(hào)，范圍從0000到9999。此時(shí)只需要申請(qǐng)一個(gè)長(zhǎng)度為100的數(shù)組，且對(duì)應(yīng)2位鍵值。但將4位的編號(hào)轉(zhuǎn)換為2位的鍵值，可能過(guò)于復(fù)雜或沒(méi)有規(guī)律，最合適的方法是建立一個(gè)保存該轉(zhuǎn)換關(guān)系的索引表。采用索引訪問(wèn)既節(jié)省內(nèi)存，又方便維護(hù)。比如索引A表示通過(guò)名稱(chēng)訪問(wèn)，索引B表示通過(guò)編號(hào)訪問(wèn)。
1.1.3 分段查找
通過(guò)確定數(shù)據(jù)所處的范圍確定分類(lèi)(下標(biāo))。有的數(shù)據(jù)可分成若干區(qū)間，即具有階梯性，如分?jǐn)?shù)等級(jí)。此時(shí)可將每個(gè)區(qū)間的上限(或下限)存到一個(gè)表中，將對(duì)應(yīng)的值存到另一表中，通過(guò)第一個(gè)表確定所處的區(qū)段，再由區(qū)段下標(biāo)在第二個(gè)表里讀取相應(yīng)數(shù)值。注意要留意端點(diǎn)，可用二分法查找，另外可考慮通過(guò)索引方法來(lái)代替。
如根據(jù)分?jǐn)?shù)查績(jī)效等級(jí)：
#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];}上述兩張表(數(shù)組)也可合并為一張表(結(jié)構(gòu)體數(shù)組)，如下所示：
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;}該表結(jié)構(gòu)已具備的數(shù)據(jù)庫(kù)的雛形，并可擴(kuò)展支持更為復(fù)雜的數(shù)據(jù)。其查表方式通常為索引查找，偶爾也為分段查找；當(dāng)索引具有規(guī)律性(如連續(xù)整數(shù))時(shí)，退化為直接查找。
使用分段查找法時(shí)應(yīng)注意邊界，將每一分段范圍的上界值都考慮在內(nèi)。找出所有不在最高一級(jí)范圍內(nèi)的值，然后把剩下的值全部歸入最高一級(jí)中。有時(shí)需要人為地為最高一級(jí)范圍添加一個(gè)上界。
同時(shí)應(yīng)小心不要錯(cuò)誤地用“<”來(lái)代替“<=”。要保證循環(huán)在找出屬于最高一級(jí)范圍內(nèi)的值后恰當(dāng)?shù)亟Y(jié)束，同時(shí)也要保證恰當(dāng)處理范圍邊界。
1.2 實(shí)戰(zhàn)示例
本節(jié)多數(shù)示例取自實(shí)際項(xiàng)目。表形式為一維數(shù)組、二維數(shù)組和結(jié)構(gòu)體數(shù)組；表內(nèi)容有數(shù)據(jù)、字符串和函數(shù)指針?；诒眚?qū)動(dòng)的思想，表形式和表內(nèi)容可衍生出豐富的組合。
1.2.1 字符統(tǒng)計(jì)
問(wèn)題：統(tǒng)計(jì)用戶輸入的一串?dāng)?shù)字中每個(gè)數(shù)字出現(xiàn)的次數(shù)。
普通解法主體代碼如下：
INT32U aDigitCharNum[10] = {0}; /* 輸入字符串中各數(shù)字字符出現(xiàn)的次數(shù) */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; }}這種解法的缺點(diǎn)顯而易見(jiàn)，既不美觀也不靈活。其問(wèn)題關(guān)鍵在于未將數(shù)字字符與數(shù)組aDigitCharNum下標(biāo)直接關(guān)聯(lián)起來(lái)。
以下示出更簡(jiǎn)潔的實(shí)現(xiàn)方式：
for(; dwStrIdx < dwStrLen; dwStrIdx ){ aDigitCharNum[szDigits[dwStrIdx] - '0'] ;}上述實(shí)現(xiàn)考慮到0也為數(shù)字字符。該解法也可擴(kuò)展至統(tǒng)計(jì)所有ASCII可見(jiàn)字符。
1.2.2 月天校驗(yàn)
問(wèn)題：對(duì)給定年份和月份的天數(shù)進(jìn)行校驗(yàn)(需區(qū)分平年和閏年)。
普通解法主體代碼如下：
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) 
下載文檔
