為什么會(huì)有“數(shù)據(jù)結(jié)構(gòu)”？

近一年來(lái)，由于參與一套高中信息科技教材的編寫(xiě)，回過(guò)頭來(lái)思考了一些關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的認(rèn)識(shí)問(wèn)題，其中就包括本文的標(biāo)題。

記得40年前上大學(xué)的時(shí)候，上郭福順老師教的數(shù)據(jù)結(jié)構(gòu)課，對(duì)“數(shù)據(jù)結(jié)構(gòu)”這個(gè)術(shù)語(yǔ)是感到完全新奇的。因?yàn)椤皵?shù)據(jù)結(jié)構(gòu)”不像“高等數(shù)學(xué)”，至少以前還聽(tīng)說(shuō)過(guò)“數(shù)學(xué)”，于是“高等數(shù)學(xué)”也就不陌生（盡管其內(nèi)容和原來(lái)知道的數(shù)學(xué)很不一樣）。由此我聯(lián)想到，在給中學(xué)生介紹數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)的時(shí)候，是不是首先得回答一下“為什么會(huì)有‘?dāng)?shù)據(jù)結(jié)構(gòu)’”這個(gè)問(wèn)題，說(shuō)說(shuō)“數(shù)據(jù)結(jié)構(gòu)”這樣一個(gè)概念在計(jì)算機(jī)科學(xué)中的意義。

為此，首先翻書(shū)，國(guó)內(nèi)的國(guó)外的，在相關(guān)的資料遍歷之后發(fā)現(xiàn)，不少作者也都感覺(jué)需要在一開(kāi)始就談?wù)劇皵?shù)據(jù)結(jié)構(gòu)”的重要性，于是常常會(huì)有幾句相關(guān)的話(huà)放在緒論甚至前言中。概括起來(lái)大致有這樣幾種情況。其一，不回答為什么會(huì)有“數(shù)據(jù)結(jié)構(gòu)”，只是講“數(shù)據(jù)結(jié)構(gòu)”作為一門(mén)課程在計(jì)算機(jī)專(zhuān)業(yè)課程中的基礎(chǔ)地位；其二，引用Niklaus Wirth的經(jīng)典觀點(diǎn)：程序=算法+數(shù)據(jù)結(jié)構(gòu)，佐證學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”概念的重要性；其三，一開(kāi)始只是講“什么是數(shù)據(jù)結(jié)構(gòu)”，而讓對(duì)“為什么會(huì)有‘?dāng)?shù)據(jù)結(jié)構(gòu)’”的認(rèn)識(shí)隱含在其中。例如，維基百科上關(guān)于“Data Structure”的描述就是后者的一個(gè)代表：

In computer science, a data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

翻譯過(guò)來(lái)就是：

計(jì)算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)組織、管理和存儲(chǔ)的形態(tài)，以支持對(duì)數(shù)據(jù)的高效訪問(wèn)和修改。更準(zhǔn)確地講，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由若干數(shù)據(jù)、它們之間的關(guān)系，以及能在其上施行的操作構(gòu)成的一個(gè)集合。

其中的“以支持對(duì)數(shù)據(jù)的高效訪問(wèn)和修改”應(yīng)該就是關(guān)于數(shù)據(jù)結(jié)構(gòu)的目的性或意義的隱含了。這段話(huà)一句句讀來(lái)應(yīng)該找不出錯(cuò)。我的看法在于它描繪了一種“重心”偏離的意境，容易對(duì)回答“為什么會(huì)有‘?dāng)?shù)據(jù)結(jié)構(gòu)’？”這樣的問(wèn)題產(chǎn)生誤導(dǎo)，所以愿在此和有興趣的同仁商榷。

首先，關(guān)鍵問(wèn)題是這里提到的“數(shù)據(jù)”指的是什么？是計(jì)算機(jī)應(yīng)用層的數(shù)據(jù)還是計(jì)算機(jī)程序在運(yùn)行時(shí)“看到的”任何0或1串？我認(rèn)為大多數(shù)人的理解會(huì)是前者（在一些教材的描述中明顯是這個(gè)意思），尤其對(duì)剛開(kāi)始接觸計(jì)算機(jī)科學(xué)知識(shí)的人更是如此（恰恰是他們應(yīng)該作為這些描述的讀者對(duì)象?。?。于是，這里給出的畫(huà)面就是，數(shù)據(jù)結(jié)構(gòu)就是將計(jì)算機(jī)應(yīng)用數(shù)據(jù)按照某種方式組織起來(lái)的結(jié)構(gòu)，以便對(duì)它們進(jìn)行高效處理。

需不需要這么做？當(dāng)然需要，但我以為那不是“數(shù)據(jù)結(jié)構(gòu)”的主要意義。

盡管數(shù)據(jù)結(jié)構(gòu)的采用在許多情況下就是應(yīng)用數(shù)據(jù)的一種組織，例如工程計(jì)算中用的數(shù)組，每個(gè)元素就對(duì)應(yīng)一個(gè)現(xiàn)實(shí)中的物理量；社會(huì)網(wǎng)絡(luò)分析中的圖，每一個(gè)節(jié)點(diǎn)就對(duì)應(yīng)一個(gè)人的有關(guān)屬性參數(shù)。但在我看來(lái)，計(jì)算機(jī)程序用數(shù)據(jù)結(jié)構(gòu)，本質(zhì)上是為了支持算法邏輯，而不是應(yīng)用層數(shù)據(jù)的組織。常常，一個(gè)數(shù)據(jù)結(jié)構(gòu)的采用與應(yīng)用層數(shù)據(jù)并沒(méi)有直接的關(guān)系，而是旨在對(duì)計(jì)算過(guò)程的有效引導(dǎo)。

稍微考慮一下就能想到許多例子。例如為了實(shí)現(xiàn)廣度優(yōu)先搜索，典型做法是用一個(gè)隊(duì)列（一種數(shù)據(jù)結(jié)構(gòu)）來(lái)控制搜索的過(guò)程，而不是把被搜索的數(shù)據(jù)組織成隊(duì)列結(jié)構(gòu)；再例如二叉樹(shù)的采用，常常就是因?yàn)樗惴ㄟ壿嫷男枰瑯?shù)中非葉節(jié)點(diǎn)包含的，就不是輸入的應(yīng)用層數(shù)據(jù)，而是程序運(yùn)行中產(chǎn)生的中間數(shù)據(jù)或控制數(shù)據(jù)。也許我們可以說(shuō)，數(shù)據(jù)結(jié)構(gòu)更多地是為了“控制”，而不是為了“數(shù)據(jù)”。為了“提高效率”沒(méi)錯(cuò)，但要認(rèn)識(shí)到既包括執(zhí)行效率，也包括編程效率。

因此，顯式或隱含強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)是應(yīng)用問(wèn)題數(shù)據(jù)的組織形態(tài)，在我看來(lái)，是學(xué)理重心的偏離。如果要強(qiáng)調(diào)數(shù)據(jù)，則應(yīng)該指明是程序“看見(jiàn)的”、編程人員體會(huì)得到的數(shù)據(jù)含義會(huì)更有教益。那樣的數(shù)據(jù)除了程序的輸入數(shù)據(jù)外，還包含中間結(jié)果數(shù)據(jù)和控制數(shù)據(jù)。

簡(jiǎn)言之，在數(shù)據(jù)結(jié)構(gòu)課程（和教材）中，我們應(yīng)該開(kāi)宗明義地講數(shù)據(jù)結(jié)構(gòu)是為算法邏輯服務(wù)的（而不講是應(yīng)用數(shù)據(jù)之間關(guān)系的表達(dá)），從而讓學(xué)生從一開(kāi)始就試圖體會(huì)、并在后續(xù)學(xué)習(xí)過(guò)程中不斷磨礪一種更有價(jià)值的觀念，這種磨礪包括認(rèn)識(shí)到是計(jì)算機(jī)存儲(chǔ)器線(xiàn)性編址的簡(jiǎn)單性，與程序邏輯的復(fù)雜性之間的鴻溝，導(dǎo)致了數(shù)據(jù)結(jié)構(gòu)的必要性，等等。我想，這也是對(duì)Niklaus Wirth的“程序=算法+數(shù)據(jù)結(jié)構(gòu)”的一種恰當(dāng)解釋。

* 注：此文發(fā)表在《計(jì)算機(jī)教育》2019.1