為什么會有“數據結構”？

近一年來，由于參與一套高中信息科技教材的編寫，回過頭來思考了一些關于算法和數據結構的認識問題，其中就包括本文的標題。

記得40年前上大學的時候，上郭福順老師教的數據結構課，對“數據結構”這個術語是感到完全新奇的。因為“數據結構”不像“高等數學”，至少以前還聽說過“數學”，于是“高等數學”也就不陌生（盡管其內容和原來知道的數學很不一樣）。由此我聯(lián)想到，在給中學生介紹數據結構相關知識的時候，是不是首先得回答一下“為什么會有‘數據結構’”這個問題，說說“數據結構”這樣一個概念在計算機科學中的意義。

為此，首先翻書，國內的國外的，在相關的資料遍歷之后發(fā)現，不少作者也都感覺需要在一開始就談談“數據結構”的重要性，于是常常會有幾句相關的話放在緒論甚至前言中。概括起來大致有這樣幾種情況。其一，不回答為什么會有“數據結構”，只是講“數據結構”作為一門課程在計算機專業(yè)課程中的基礎地位；其二，引用Niklaus Wirth的經典觀點：程序=算法+數據結構，佐證學習“數據結構”概念的重要性；其三，一開始只是講“什么是數據結構”，而讓對“為什么會有‘數據結構’”的認識隱含在其中。例如，維基百科上關于“Data Structure”的描述就是后者的一個代表：

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.

翻譯過來就是：

計算機科學中的數據結構，是數據組織、管理和存儲的形態(tài)，以支持對數據的高效訪問和修改。更準確地講，一個數據結構是由若干數據、它們之間的關系，以及能在其上施行的操作構成的一個集合。

其中的“以支持對數據的高效訪問和修改”應該就是關于數據結構的目的性或意義的隱含了。這段話一句句讀來應該找不出錯。我的看法在于它描繪了一種“重心”偏離的意境，容易對回答“為什么會有‘數據結構’？”這樣的問題產生誤導，所以愿在此和有興趣的同仁商榷。

首先，關鍵問題是這里提到的“數據”指的是什么？是計算機應用層的數據還是計算機程序在運行時“看到的”任何0或1串？我認為大多數人的理解會是前者（在一些教材的描述中明顯是這個意思），尤其對剛開始接觸計算機科學知識的人更是如此（恰恰是他們應該作為這些描述的讀者對象！）。于是，這里給出的畫面就是，數據結構就是將計算機應用數據按照某種方式組織起來的結構，以便對它們進行高效處理。

需不需要這么做？當然需要，但我以為那不是“數據結構”的主要意義。

盡管數據結構的采用在許多情況下就是應用數據的一種組織，例如工程計算中用的數組，每個元素就對應一個現實中的物理量；社會網絡分析中的圖，每一個節(jié)點就對應一個人的有關屬性參數。但在我看來，計算機程序用數據結構，本質上是為了支持算法邏輯，而不是應用層數據的組織。常常，一個數據結構的采用與應用層數據并沒有直接的關系，而是旨在對計算過程的有效引導。

稍微考慮一下就能想到許多例子。例如為了實現廣度優(yōu)先搜索，典型做法是用一個隊列（一種數據結構）來控制搜索的過程，而不是把被搜索的數據組織成隊列結構；再例如二叉樹的采用，常常就是因為算法邏輯的需要，樹中非葉節(jié)點包含的，就不是輸入的應用層數據，而是程序運行中產生的中間數據或控制數據。也許我們可以說，數據結構更多地是為了“控制”，而不是為了“數據”。為了“提高效率”沒錯，但要認識到既包括執(zhí)行效率，也包括編程效率。

因此，顯式或隱含強調數據結構是應用問題數據的組織形態(tài)，在我看來，是學理重心的偏離。如果要強調數據，則應該指明是程序“看見的”、編程人員體會得到的數據含義會更有教益。那樣的數據除了程序的輸入數據外，還包含中間結果數據和控制數據。

簡言之，在數據結構課程（和教材）中，我們應該開宗明義地講數據結構是為算法邏輯服務的（而不講是應用數據之間關系的表達），從而讓學生從一開始就試圖體會、并在后續(xù)學習過程中不斷磨礪一種更有價值的觀念，這種磨礪包括認識到是計算機存儲器線性編址的簡單性，與程序邏輯的復雜性之間的鴻溝，導致了數據結構的必要性，等等。我想，這也是對Niklaus Wirth的“程序=算法+數據結構”的一種恰當解釋。

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