小結

應用計算機求解現實世界中的問題，最關鍵的是要考慮處理對象在計算機中的表示、處理方法和效率，這就是“數據結構”課程的研究內容，它涉及數據的邏輯結構，數據的存儲結構和數據的操作三個方面。為了使讀者能更快、更好地了解數據結構，適應本書的后述內容，我們在本章中介紹了數據類型、抽象數據類型等基本概念和術語，討論了數據的邏輯結構和存儲結構，并對算法的定義、描述和性能分析等做了詳細的闡述。

本章開頭以三個不同問題的求解實例來說明利用計算機求解問題的過程實質上是一個抽象出問題中數據的邏輯結構，建立數據的存儲結構和設計求解問題的算法，最后選擇某種編程語言來實現算法，并在計算機上測試運行的整個過程。

數據的邏輯結構其實就是從具體問題抽象出來的數學模型，它反映了事物的組成結構和組成結構中數據元素之間的邏輯關系。根據數據元素之間邏輯關系的特性來分，可將數據結構分為集合、線性結構、樹形結構和圖形結構四大類。

數據的存儲結構是各種邏輯結構在計算機中的一種存儲映象，它反映了具有某種邏輯關系的數據元素在計算機中是如何組織和實現的，是邏輯結構在計算機中的物理存儲表示。同一種邏輯結構可以采用不同的映象方式來建立不同的存儲結構。常用的映象方式有順序映象、鏈式映象、索引映象和散列映象，所形成的存儲結構分別稱為順序存儲結構、鏈式存儲結構、索引存儲結構和散列存儲結構。

數據的存儲結構通常用程序設計語言中的數據類型來加以描述。對于簡單數據可直接使用程序設計語言中內置的基本數據類型來描述；對于復雜數據則要根據實際情況，引用自定義的數據類型。

抽象數據類型是指一個數據值的集合和定義在這個集合上的一組操作。使用抽象數據類型可以在很大程度上幫助用戶獨立于程序的實現細節，更好地理解問題的本質內容，從而達到數據抽象和信息隱藏的目的。

算法是對特定問題求解步驟的一種描述，它是由有限條指令序列組成的。算法應具備有窮性、確定性、有效性、輸入和輸出五個性質。

算法設計與算法分析是保證計算機能快速、高效地實現問題求解的兩個重要環節。算法設計的根本任務，是針對各類實際問題設計出高效率的算法，并研究設計算法的規律和方法。常用的設計方法有窮舉法、動態規劃法、回溯法、分治法、遞歸法和貪心法等。算法分析的根本任務是利用某一種方法，對每一個算法討論其各種復雜度，以探討各種算法的效率和適用性，為從解決同一個問題的多個不同的算法中做出選擇，或對原有算法進行改進使其性能更優提供依據。

算法的復雜度通常體現為時間復雜度和空間復雜度兩個指標，對于時間復雜度和空間復雜度的估算，本書采用漸近分析法。時間復雜度和空間復雜度都是問題規模的某個函數。

本章討論的都是一些基本概念，重點在于了解有關數據結構的各個名詞和術語的含義，掌握用于確定算法時間復雜度和空間復雜度的方法。