辨析《數(shù)據(jù)結(jié)構(gòu)》教學(xué)中幾個(gè)容易誤解的問題

黃靜，張連堂

（廣州商學(xué)院，信息技術(shù)與工程學(xué)院，廣州511363）

1 關(guān)于教材中算法類型Status

在不少院校所用的教材中，絕大部分過程型算法都標(biāo)注為Status作為返回類型，似乎不符合一般編程理念。但是編者通常采用類語言描述算法，Status的意圖是：告訴學(xué)習(xí)者這樣的算法執(zhí)行結(jié)果總有一個(gè)狀態(tài)存在，通常用宏定義的方法把不同的返回狀態(tài)進(jìn)行預(yù)定義，例如：

然后在相關(guān)算法的描述函數(shù)中用return返回正確的狀態(tài)（OK），用exit作為出口報(bào)錯(cuò)（ERROR或OVERFLOW），例如不少教材中存在類似于“算法1”的描述。其本意是該算法無返回類型，給出一個(gè)狀態(tài)（Status）標(biāo)志。執(zhí)行結(jié)果錯(cuò)誤時(shí)退出，并且給出描述錯(cuò)誤性質(zhì)的狀態(tài)標(biāo)識(shí)符，執(zhí)行正確時(shí)返回正確狀態(tài)[1]。

算法1.關(guān)于Status的解釋說明

但是，這樣的算法對于初學(xué)者而言非常容易誤解和混淆，因?yàn)樵谝话阏Z言編程時(shí)過程型函數(shù)是沒有返回類型的，并且無論是何種情況，一個(gè)算法內(nèi)部混用exit和return有悖常理，讓初學(xué)者很是迷茫。需要澄清的是：編者僅僅是從算法的角度來描述算法執(zhí)行的過程以及所有可能的執(zhí)行狀態(tài)，用類語言為學(xué)習(xí)者闡述一個(gè)清晰的思想方法。只要理解了算法，對于有語言基礎(chǔ)的學(xué)習(xí)者而言，用標(biāo)準(zhǔn)的編程語言，把算法轉(zhuǎn)換成嚴(yán)謹(jǐn)?shù)暮瘮?shù)付諸于實(shí)現(xiàn)，并不困難。

當(dāng)然，我們還是建議授課者在講授算法時(shí)，盡可能把類語言描述的算法更加貼近于標(biāo)準(zhǔn)語言的策略和方法，不要在同一個(gè)算法中混用exit和return，并且，盡可能不用exit作為算法出口，以免無形中給學(xué)習(xí)者建立一種錯(cuò)誤的編程理念。因?yàn)閑xit在不少語言中都會(huì)退出程序的執(zhí)行，造成非法中斷。算法執(zhí)行結(jié)果不管是正確還是錯(cuò)誤，都用return返回相應(yīng)的狀態(tài)標(biāo)識(shí)符，調(diào)用者函數(shù)自然可以通過不同的標(biāo)識(shí)符進(jìn)行后續(xù)判斷和處理。

這樣不僅僅便于講授，而且便于學(xué)習(xí)者清晰地理解和掌握，更有利于實(shí)踐應(yīng)用中用所選定的語言實(shí)現(xiàn)算法。

2 靜態(tài)鏈表不同于順序結(jié)構(gòu)

靜態(tài)意指在存儲(chǔ)器中申請、分配一組地址連續(xù)的存儲(chǔ)單元，使用過程中一般不能改變其大小，計(jì)算機(jī)語言中常以數(shù)組類型定義實(shí)現(xiàn)；鏈表意指通過存儲(chǔ)器地址來關(guān)聯(lián)數(shù)據(jù)元素之間的邏輯關(guān)系。

總之，一般意義上的“鏈表”在整個(gè)可用存儲(chǔ)空間中實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，數(shù)據(jù)元素之間的邏輯關(guān)系用存儲(chǔ)器地址進(jìn)行關(guān)聯(lián)，其存儲(chǔ)位置不一定連續(xù)；而“靜態(tài)鏈表”是在某一個(gè)地址連續(xù)的局部存儲(chǔ)空間內(nèi)實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)，數(shù)據(jù)元素的存儲(chǔ)位置雖然有可能是順序的，但元素之間的邏輯關(guān)系由局部空間相對位置序號來關(guān)聯(lián)，不一定連續(xù)，其本質(zhì)依然是鏈表結(jié)構(gòu)，而不是順序表結(jié)構(gòu)。如一個(gè)n+1分量的靜態(tài)數(shù)組，圖1為四個(gè)客觀數(shù)據(jù)66、77、36、69在計(jì)算機(jī)內(nèi)存中的順序存儲(chǔ)結(jié)構(gòu)，圖2為靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)。

圖1 順序存儲(chǔ)

圖2 靜態(tài)鏈表

因?yàn)榻⒃陧樞蚩臻g的靜態(tài)鏈表插入、刪除都無需移動(dòng)元素，在工程實(shí)踐中有著非常獨(dú)到的優(yōu)勢，例如：在數(shù)據(jù)庫設(shè)計(jì)中，排序是重要的算法，拋棄數(shù)據(jù)庫表記錄之間本來的順序關(guān)系，增加一個(gè)記憶記錄號的字段，引入靜態(tài)鏈表理念表示記錄之間的邏輯關(guān)系，應(yīng)用“地址排序”算法實(shí)現(xiàn)排序，可以消除一般排序算法中多余的記錄移動(dòng)，極大地增強(qiáng)數(shù)據(jù)庫的安全性[2]。

3 客觀世界的數(shù)組不同于計(jì)算機(jī)語言中的數(shù)組

《數(shù)據(jù)結(jié)構(gòu)》課程中講述的數(shù)組是客觀世界中數(shù)據(jù)元素的一類邏輯結(jié)構(gòu)關(guān)系，例如通訊錄、賬目表、數(shù)學(xué)中的矩陣，等等，與計(jì)算機(jī)毫無關(guān)系；而計(jì)算機(jī)程序設(shè)計(jì)語言中的數(shù)組，是語言提供的一種數(shù)據(jù)類型，是存儲(chǔ)數(shù)據(jù)的一種策略：“順序存儲(chǔ)結(jié)構(gòu)”，它申請一組地址連續(xù)的存儲(chǔ)單元保存外來數(shù)據(jù)。兩者是兩個(gè)完全不同的概念。

客觀世界的數(shù)組存入計(jì)算機(jī)時(shí)，既可以用語言定義的數(shù)組類型實(shí)現(xiàn)，也可以用其他存儲(chǔ)方案（例如鏈表）實(shí)現(xiàn)。例如四個(gè)客觀數(shù)據(jù)構(gòu)成的一個(gè)數(shù)組66、77、36、69，在圖1中用語言的數(shù)組實(shí)現(xiàn)為順序存儲(chǔ)，圖2中用語言的數(shù)組實(shí)現(xiàn)為靜態(tài)鏈表，還可以用動(dòng)態(tài)指針實(shí)現(xiàn)為一般鏈表。如圖3所示。

圖3 動(dòng)態(tài)鏈表

4 關(guān)于廣義表表尾的理解

廣義表是線性結(jié)構(gòu)的延伸，把線性表中的元素按照先后順序分為兩個(gè)部分，第一部分是表中的第一個(gè)元素被稱為表頭，第二部分是除去表頭以外的所有元素構(gòu)成的子表被稱為表尾[2]，例如，表：

這里的B表看起來相對A表更長，其實(shí)表中只有兩個(gè)元素，反而短于A表，第一個(gè)元素是（a，d），它本身就是表頭；第二個(gè)元素是（b，c），它本身并不是B表的表尾，表尾是由元素（b，c）構(gòu)成的子表（（b，c））；這個(gè)概念是不能理解錯(cuò)的。

簡而言之，表頭相當(dāng)于一個(gè)群體中的“領(lǐng)導(dǎo)”，它既是可以“單數(shù)名詞”也可以是“復(fù)數(shù)名詞”，就是說，領(lǐng)導(dǎo)可以是一個(gè)人，也可以是多人構(gòu)成的一個(gè)相對小群體；表尾是“群眾”，它在任何情況下都是“復(fù)數(shù)名詞”。就是說，表尾是除去領(lǐng)導(dǎo)外的所有人構(gòu)成的從屬于“領(lǐng)導(dǎo)”的“群體”，而不是除去領(lǐng)導(dǎo)外的所有人。

5 Hash表處理沖突的開放定址散列法

開放定址散列法一般分為線性和非線性兩類；假設(shè)用于計(jì)算Hash表地址的Hash函數(shù)為H（key），其中key為表中元素的主關(guān)鍵字。

對于線性探測再散列而言，散列算法[3]為：

這個(gè)描述從本質(zhì)上完全變了味道，如果這樣設(shè)計(jì)算法，將會(huì)造成部分地址永遠(yuǎn)不能被尋到，這一點(diǎn)應(yīng)當(dāng)引起清醒的認(rèn)識(shí)。

對于非線性的二次探測再散列而言，散列算法為：

實(shí)踐中，不少情況下其散列速度相對于線性探測再散列而言更快，但是，有一個(gè)根本性的問題一直被不少人所忽視，試想：當(dāng)在基本Hash地址H（key）確定后，如果i比較大，-i2就是一個(gè)絕對值更大的負(fù)數(shù)，計(jì)算出的Hi（key）就有可能企圖向左越過0點(diǎn)取某一個(gè)負(fù)數(shù)作為地址，這是無意義的。這里我們給出一個(gè)較為合理的解決方案，把散列算法修改為：

其中，i和di的條件不變，這樣就完全克服了二次探測再散列自身存在的弊端。例如，對于給定的關(guān)鍵字集合{19，01，23，14，55，11，68，82，36}，設(shè)定哈希函數(shù)H（key）=key MOD 11（表長m=11），采取二次探測再散列構(gòu)造哈希表，如果用常規(guī)的（6）式進(jìn)行散列，其中的關(guān)鍵字01對應(yīng)的哈希地址是1，關(guān)鍵字55對應(yīng)的哈希地址是0，關(guān)鍵字11將在0地址沖突，第一次散列d1=12=1，改地址已經(jīng)被占用，第二次散列d2=-12=-1，顯然這個(gè)地址子虛烏有，毫無意義。

改用式（8）進(jìn)行散列，可得表1所示散列表：

表1 關(guān)鍵字集合{19，01，23，14，55，11，68，82，36}散列表（二次探測再散列）

完全克服了負(fù)數(shù)地址的錯(cuò)誤現(xiàn)象。

6 B_樹及其教學(xué)用語

6.1 B_樹不容淡化

B_樹作為一種平衡多路查找樹，在不少院校的教學(xué)過程中通常被忽視，其實(shí)，B_樹是一個(gè)非常重要而不易淡化的查找表結(jié)構(gòu)，對于保存在外存中的大文件而言，查找過程中如果一次調(diào)取一條記錄入內(nèi)存，速度非常之慢，一次調(diào)取一批記錄入內(nèi)存，形成一種高速緩存效應(yīng)，并且實(shí)現(xiàn)多路平衡查找，就可極大地提高查找效率，工程中非它莫屬，應(yīng)用極廣，實(shí)踐中所有查找算法都沒有B_樹更有效，在當(dāng)今的大數(shù)據(jù)時(shí)代，B_樹的在系統(tǒng)開發(fā)中的作用將越來越被業(yè)界廣泛關(guān)注。

6.2 教學(xué)用語不可混亂

在教學(xué)實(shí)踐中，時(shí)不時(shí)能聽到一些教師在講到“B_樹”和“B+樹”時(shí)，對他們的稱謂比較混亂，例如有人把“B_樹”叫做“B減樹”，學(xué)生們聽起來也沒有什么質(zhì)疑，因?yàn)楹竺嬷v到“B+樹”時(shí)讀為“B加樹”，那么“B_樹”讀為“B減樹”是合情合理，但筆者認(rèn)為這是一種毫無依據(jù)的杜撰。

“B+樹”的“+”號意指對原始“B_樹”的改進(jìn)，而“B_樹”中的下劃線只是一個(gè)標(biāo)記，作用是強(qiáng)調(diào)前面的字母“B”表示“平衡多路查找”，“B_樹”是對“平衡二叉樹”本質(zhì)的改進(jìn)，筆者認(rèn)為教學(xué)過程中語言描述應(yīng)該稱之為“B樹”不應(yīng)講成“B減樹”。

如上幾點(diǎn)理解為個(gè)人觀點(diǎn)，僅供參考。