1.1 數據結構的研究內容

計算機主要用于數值計算時，一般要經過如下幾個步驟：首先從具體問題抽象出數學模型，然后設計一個解此數學模型的算法，最后編寫程序，進行測試、調試，直到解決問題。在此過程中尋求數學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間的關系，然后用數學語言加以描述，即建立相應的數學方程。例如，用計算機進行全球天氣預報時，就需要求解一組球面坐標系下的二階橢圓偏微分方程；預測人口增長情況的數學模型為常微分方程。求解這些數學方程的算法是計算數學研究的范疇，如高斯消元法、差分法、有限元法等算法。數據結構主要研究非數值計算問題，非數值計算問題無法用數學方程建立數學模型，下面通過三個實例加以說明。

【例1.1】 學生學籍管理系統。

高等院校教務處使用計算機對全校的學生情況作統一管理。學生的基本信息，包括學生的學號、姓名、性別、籍貫、專業等，如表1.1所示。每個學生的基本情況按照不同的順序號，依次存放在“學生基本信息表”中，根據需要對這張表進行查找。每個學生的基本信息記錄按順序號排列，形成了學生基本信息記錄的線性序列，呈一種線性關系。

諸如此類的線性表結構還有圖書館的書目管理系統、庫存管理系統等。在這類問題中，計算機處理的對象是各種表，元素之間存在簡單一對一的線性關系，因此這類問題的數學模型就是各種線性表，施加于對象上的操作有查找、插入和刪除等。這類數學模型稱為“線性”的數據結構。

【例1.2】 人機對弈問題。

計算機之所以能和人對弈是因為已經將對弈的策略在計算機中存儲好。由于對弈的過程是在一定規則下隨機進行的，所以，為使計算機能靈活對弈，就必須把對弈過程中所有可能發生的情況及相應的對策都加以考慮。以最簡單的井字棋為例，初始狀態是一個空的棋盤格局。對弈開始后，每下一步棋，則構成一個新的棋盤格局，且相對于上一個棋盤格局的可能選擇可以有多種形式，因而整個對弈過程就如同圖1.1所示的“一棵倒長的樹”。在這棵“樹”中，從初始狀態（根）到某一最終格局（葉子）的一條路徑，就是一次具體的對弈過程。

人機對弈問題的數學模型就是如何用樹結構表示棋盤和棋子等，算法是博弈的規則和策略。諸如此類的樹結構還有計算機的文件系統、一個單位的組織機構等。在這類問題中，計算機處理的對象是樹結構，元素之間是一對多的層次關系，施加于對象上的操作有查找、插入和刪除等。這類數學模型稱為“樹”的數據結構。

【例1.3】 最短路徑問題。

從城市A到城市B有多條線路，但每條線路的交通費不同，那么，如何選擇一條線路，使得從城市A到城市B的交通費用最少呢？解決的方法是，可以把這類問題抽象為圖的最短路徑問題。如圖1.2所示，圖中的頂點代表城市，有向邊代表兩個城市之間的通路，邊上的權值代表兩個城市之間的交通費。求解A到B的最少交通費用，就是要在有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。

最短路徑問題的數學模型就是圖結構，算法是求解兩點之間的最短路徑。諸如此類的圖結構還有網絡工程圖和網絡通信圖等，在這類問題中，元素之間是多對多的網狀關系，施加于對象上的操作依然有查找、插入和刪除等。這類數學模型稱為“圖”的數據結構。

從上面三個實例可以看出，非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹和圖的數據結構。因此，簡單地說，數據結構是一門研究非數值計算程序設計中的操作對象，以及這些對象之間的關系和操作的學科。

20世紀60年代初期，“數據結構”有關的內容散見于操作系統、編譯原理等課程中。1968年，“數據結構”作為一門獨立的課程被列入美國一些大學計算機科學系的教學計劃，同年，著名計算機科學家D.E.Knuth教授發表了《計算機程序設計藝術》第一卷《基本算法》。這是第一本較系統地闡述“數據結構”基本內容的著作。之后，隨著大型程序和大規模文件系統的出現，結構化程序設計成為程序設計方法學的主要研究方向，人們普遍認為程序設計的實質就是對所處理的問題選擇一種好的數據結構，并在此結構基礎上施加一種好的算法，著名科學家Wirth教授的《算法+數據結構=程序》正是這種觀點的集中體現。

目前，數據結構在計算機科學中是一門綜合性的專業基礎課。數據結構的研究不僅涉及計算機硬件（特別是編碼理論、存儲裝置和存取方法等）的研究范圍，而且和計算機軟件的研究有著密切的關系，無論是編譯程序還是操作系統都涉及數據元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數據，以使查找和存取數據元素更為方便。因此，可以認為數據結構是介于數學、計算機硬件和軟件三者之間的一門核心課程。

有關“數據結構”的研究仍不斷發展，一方面，面向各專門領域中特殊問題的數據結構正在研究和發展；另一方面，從抽象數據類型的觀點來討論數據結構，已成為一種新的趨勢，越來越被人們所重視。