數據結構 數據結構（Data Structure）是信息的一種組織方式，它用來反映一個數據的內部構成，即一個數據由哪些成分數據構成，以什么方式構成，呈什么結構。其目的是為了提高算法的效率，它通常與一組算法的集合相對應，通過這組算法集合可以以數據結構中的數據進行某種操作。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的數據結構反映數據在計算機內部的存儲安排。

1．1 數據結構的概念數據結構是計算機科學與技術專業的專業基礎課，是十分重要的核心課程。所有的計算機系統軟件和應用軟件都要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付眾多復雜的課題的。要想有效地使用計算機、充分發揮計算機的性能，還必須學習和掌握好數據結構的有關知識。打好“數據結構”這門課程的扎實基礎，對于學習計算機專業的其他課程，如操作系統、編譯原理、數據庫管理系統、軟件工程、人工智能等都是十分有益的。1.1.1 為什么要學習數據結構在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出一個適當的數學模型，然后設計或選擇一個解此數學模型的算法，最后編出程序進行調試、測試，直至得到最終的解答。例如，求解梁架結構中應力的數學模型的線性方程組，該方程組可以使用迭代算法來求解。由于當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，所以程序設計者的主要精力是集中于程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟、硬件的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題占用了90%以上的機器時間。這類問題涉及到的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，才能有效地解決問題。下面所列舉的就是屬于這一類的具體問題。[例1] 學生信息檢索系統。當我們需要查找某個學生的有關情況的時候；或者想查詢某個專業或年級的學生的有關情況的時候，只要我們建立了相關的數據結構，按照某種算法編寫了相關程序，就可以實現計算機自動檢索。由此，可以在學生信息檢索系統中建立一張按學號順序排列的學生信息表和分別按姓名、專業、年級順序排列的索引表，如圖1.1所示。由這四張表構成的文件便是學生信息檢索的數學模型，計算機的主要操作便是按照某個特定要求（如給定姓名）對學生信息文件進行查詢。諸如此類的還有電話自動查號系統、考試查分系統、倉庫庫存管理系統等。在這類文檔管理的數學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關系，這類數學模型可稱為線性的數據結構。[例2] 八皇后問題。在八皇后問題中，處理過程不是根據某種確定的計算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步形成一個新的狀態，整個試探過程形成了一棵隱含的狀態樹。如圖1.2所示（為了描述方便，將八皇后問題簡化為四皇后問題）。回溯法求解過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。[例3] 教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規定的先后次序進行，有些則沒有次序要求。即有些課程之間有先修和后續的關系，有些課程可以任意安排次序。這種各個課程之間的次序關系可用一個稱作圖的數據結構來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進行。由以上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如表、樹、圖之類的數據結構。因此，可以說數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。