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