1.1 從問題到程序

“數據結構”是計算機科學與技術專業的專業基礎課，也是十分重要的核心課程，其主要研究內容是數據之間的邏輯關系和物理實現，即探索有利的數據組織形式及存取方式。計算機系統軟件和應用軟件的設計、開發要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅僅依賴幾種計算機程序設計語言是不夠的，還必須學習和掌握數據結構的有關知識。

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題中抽象出一個適當的數學模型，然后設計或選擇一個解此數學模型的算法，再編寫程序并進行調試、測試，最后運行程序并得到答案（如圖1.1所示）。例如，求解梁架結構中應力數學模型的線性方程組，該方程組可以使用迭代算法來求解。

由于當時所涉及的運算對象是簡單的整型數據、實型數據或布爾型數據，所以程序設計者的主要精力集中于程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟/硬件的發展，非數值計算問題顯得越來越重要。據統計，當今處理非數值計算性問題占用了90%以上的機器時間。這類問題涉及的處理對象不再是簡單的數據類型，其形式更加多樣，結構更為復雜，數據元素之間的相互關系一般無法直接用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是設計出合適的數據結構，以便有效地解決問題。

【例1.1】 圖書信息檢索系統。在現代圖書館中，人們往往借助計算機圖書檢索系統來查找需要的圖書信息；或者直接通過圖書館信息系統進行圖書借閱。為此，需要將圖書信息分類編排，建立合適的數據結構進行存儲和管理，按照某種算法編寫相關程序，實現計算機自動檢索。由此，一個簡單的圖書信息檢索系統包括一張按圖書分類號和登錄號順序排列的圖書信息表，以及分別按作者、出版社等順序排列的各類索引表，如圖1.2所示。由這三張表構成的文件便是圖書信息檢索的數學模型，計算機的主要操作便是按照用戶的要求（如給定作者）通過不同的索引表對圖書信息進行檢索、查詢。

諸如此類的還有電話自動查號系統、學生信息查詢系統、倉庫庫存管理系統等。在這類數學模型中，計算機處理的對象之間通常存在著一種簡單的線性關系，這類數學模型是線性數據結構的。

【例1.2】 人機對弈問題。人機對弈是一個古老的人工智能問題，其解題思想是將對弈的策略事先存入計算機，策略包括對弈過程中所有可能的情況及響應的對策。在決定對策時，根據當前狀態，考慮局勢發展的趨勢做出最有利的選擇。因此，計算機操作的對象（數據元素）是對弈過程中的每一步棋盤狀態（格局），數據元素之間的關系由比賽規則決定。通常，這個關系不是線性的，因為從一個格局可以派生出多個格局，所以通常用樹形結構來表示，圖1.3所示的是井字棋對弈樹。

【例1.3】 教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些課程必須按規定的先后次序進行學習，有些則沒有次序要求。課程之間先修和后修的次序關系可用一個稱做圖的數據結構來表示，如圖1.4所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi,vj>，則表示課程i必須先于課程j進行學習。

由以上幾個例子可見，描述非數值計算問題的數學模型不再是數學方程，而是諸如表、樹、圖之類的數據結構。因此，數據結構課程是研究非數值計算的程序設計問題中計算機處理對象及它們之間關系和操作的學科。

學習數據結構的目的是了解和掌握計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。同時，通過算法訓練來提高學生的思維能力，通過程序設計的技能訓練來促進學生的綜合應用能力和專業素質的提高。