1.1 數據結構課程討論的內容

Pascal語言之父、結構化程序設計的先驅、著名的瑞士科學家沃思（Niklaus Wirth）教授曾出版過一本著名的書籍《算法+數據結構=程序》，他認為：程序是計算機指令的組合，用來控制計算機的工作流程，完成一定的邏輯功能以實現某種任務；算法是程序的邏輯抽象，是解決某類客觀問題的策略；數據結構是現實世界中的數據及其之間關系的反映，它可以從邏輯結構和存儲（物理）結構兩個層面刻畫，其中客觀事物自身所具有的結構特點，被稱為邏輯結構，而具有這種邏輯結構的數據在計算機存儲器中的組織形式則被稱為存儲結構。可見，這個等式反映了算法、數據結構對于程序設計的重要性。通過學習本課程，讀者將體會到在解決一個現實問題時應該如何采用一種合適的方法（算法），又應該如何編寫一個高效率程序，并通過計算機實現問題的求解。

1.1.1 求解問題舉例

人們利用計算機是為了能快速解決實際的應用問題，而程序是人們編寫的，它是計算機按照人的旨意進行問題處理的指令的集合。因而要利用計算機實現問題的求解，就需要完成一個從問題到程序的實現過程。此過程的主要步驟歸納如下：

（1）確定問題求解的數學模型（或邏輯結構）：對問題進行深入分析，確定處理的數據對象是什么，再根據數據對象的邏輯關系給出其數學模型。

（2）確定存儲結構：根據數據對象的邏輯結構及其所需完成的功能，選擇一種合適的組織形式將數據對象映射到計算機的存儲器中。

（3）設計算法：討論要解決問題的策略，即確定求解問題的具體步驟。

（4）編程并測試結果：根據算法編寫程序并上機測試，直至得到問題的最終解。

由此可見，程序設計的本質在于解決兩個主要問題：一是根據實際問題選擇一種“好”的數據結構；二是設計一個“好”的算法。后者的好壞在很大程度上取決于前者。例如：

問題一：N個數的選擇問題。假設有N個數，要求找出N個數中第k大的那個數。

要解決這個問題，首先要考慮的就是這N個數的取值范圍是什么。也就是說，只有明確了這N個數在計算機中是如何組織的，才能決定采用何種求解問題的策略。

解決此問題的一種算法是將N個數讀入一個數組中，再通過冒泡排序方法對N個數以遞減順序排序，最后在已排序數組中的第k個元素就是所要求的解。這種策略實施的前提是內存中有足夠的空間能夠容納這N個數。然而，若空間不夠，又該如何處理呢？

解決此問題的另一種算法是先將N個數的前k個數讀入一個數組，并以遞減順序進行排序，再將剩下的數逐個讀入，將它與數組中的第k個數進行比較。如果它不大于第k個數，則忽略；否則就將它插入數組中的適當位置，使數組仍然保持有序，同時數組中的最后一個數被擠出數組。當剩下的所有數都處理完畢時，數組中位于第k個位置上的數就是所要求的解。

這兩種算法用程序實現其編碼都很簡單，但哪種算法更好呢？當N和k都充分大（大于106）時，這兩種算法的程序在合理時間內都不能結束，它們需要計算機處理若干天后才能計算完畢，這是不切實際的，所以它們都不能被認為是好的算法。在第7章將給出解決這個問題的更好算法。

問題二：生產訂單的自動查詢問題。在一個訂單管理系統中，有一個實體“生產訂單統計表”，實體中包括若干個訂單記錄，它們按照每個生產訂單的訂單號遞增順序排列，如表1-1所示。現要求查找“張三”制作的所有訂單信息。

在研究如何查找滿足指定條件的訂單信息時，首先必須考慮生產訂單統計表在計算機中是如何組織的、每一訂單包括哪些信息項、各訂單之間又是按什么順序存放的，是按訂單號遞增的順序存放？還是按物料名稱的順序存放？或是按制單人的姓氏順序存放？然后才能根據特定的查找要求去確定某種查找方法。

上述問題中要求查找“張三”制作的所有訂單信息，也就是說若在生產訂單統計表中有該人制作的訂單，則輸出相關的所有訂單信息；否則就輸出該人制作的訂單不存在。要解決這個問題，首先應將生產訂單統計表中的數據映射到計算機的存儲器中，從而形成生產訂單統計表的存儲結構。如何設計查找算法則取決于統計表的存儲結構。一種算法可以將表中數據順序地存儲到計算機中，查找時從表的第一行記錄開始到最后一行記錄為止，依次核對制單人的姓名是否存在與“張三”相同的記錄。若存在，則可獲得該人制作的一個訂單行信息；若找遍整個表均無此制單人，則說明沒有該人制作的訂單。這種算法在訂單數不多的情況下是可行的，但是當訂單數很多時是不實用的。另一種算法可以先將生產訂單統計表順序地存放，再按制單人的姓氏建立一張索引表，存儲結構如圖1-1所示。查找時首先在索引表中核對姓氏，然后根據索引表中的地址找到對應的指針桶，再根據指針桶中的地址直接到生產訂單統計表的指定地址中查對制單人的姓名。注意，這時已經不需要查找其他不同姓氏的行信息了。相比之下，第二種查找算法比第一種算法更為高效。在第6章將給出更多的實現查找操作的算法。

問題三：城市網絡的鋪設問題。假設需為城市的n個小區之間鋪設網絡線路（任意兩個小區之間都可以鋪設），n個小區只需鋪設n-1條線路，就能使n個小區網絡相通。然而，由于地理環境不同等因素導致各條線路所需投資不同，問題是采用怎樣的設計方案才能使總投資最低？

根據各小區之間的地理位置關系及各線路所需的投資情況，確定這個問題的數學模型可用一個圖來描述。假設該圖如圖1-2所示，其中頂點表示城市，頂點之間的連線及其上面的數值表示可以鋪設的線路及所需經費。求解該問題的算法可以簡單地描述為：在可以鋪設的所有線路中選取n-1條，使得這n-1條線路既能連通n個小區，又使總投資最低。實際上，這是一個求“圖的最小生成樹”的問題，圖1-2對應的最小生成樹可用圖1-3來描述，這個圖給出的就是一種求解問題的設計方案。有關求圖的最小生成樹的具體算法將在第6章中進行詳細討論。

1.1.2 本課程討論的內容

數據結構，與數學、計算機硬件和軟件有著十分密切的關系。它是介于數學、計算機硬件和軟件之間的一門計算機類和電子信息類相關專業的核心課程之一，是高級程序設計語言、編譯原理、操作系統、數據庫、人工智能等課程的基礎。同時，數據結構技術也廣泛應用于信息科學、系統工程、應用數學以及各種工程技術領域。

從上節討論的幾個求解問題可知，用計算機來解決一個具體問題，總是圍繞以下三個主要步驟進行：

（1）抽象出所求解問題中需要處理的數據對象的邏輯結構（數學模型）。

（2）根據問題求解的功能特性，實現對抽象數據的存儲結構表述。

（3）確定并實現為求解問題而需進行的操作或運算。

事實上，只有這三者的結合，才能清晰地刻畫出數據結構的本質特性。因此，通常在本課程中討論數據結構，既要討論在解決問題時各種可能遇到的典型的邏輯結構，又要討論這些邏輯結構在計算機中的存儲映射（存儲結構）。此外，還要討論數據結構上的相關操作及其實現。與此同時，為了構造出好的數據結構并加以實現，還必須考慮其實現方法的性能優劣。因此，“數據結構”課程的內容體系可用表1-2進行歸納。