前言

用計算機求解實際問題時，必然涉及數據組織及數據處理，這些正是“數據結構”課程的主要學習內容。“數據結構”課程在計算機科學中是一門綜合性的專業基礎課。在計算機科學中，數據結構內容不僅作為一般程序設計的必備知識，而且是設計編譯程序、操作系統、數據庫系統及其他系統程序和大型應用程序的重要基礎。

“數據結構”課程主要的學習內容有：數據的邏輯結構描述，即表示求解問題中的數據和數據元素之間的邏輯關系；數據的存儲結構設計，即將數據邏輯結構在計算機內存中表示出來；運算算法設計，即實現求解問題的功能，如設計插入、刪除、修改、查詢和排序算法等。

很多學習“數據結構”課程的學生都感覺數據結構比較抽象，算法理解比較困難，這很大程度上是由于沒有領會數據結構的特點。首先，一個學習計算機專業的學生必須具有某種計算機語言編程能力，能夠將求解問題的思路轉換成計算機可以執行的程序代碼，會編寫基本的程序就像一個小學生識字和掌握基本的詞匯一樣重要；其次，必須掌握用計算機求解問題的三個層次，即提取求解問題中數據的邏輯結構、設計相應的存儲結構和在存儲結構上實現求解問題的算法。在設計一個算法時，先要充分理解相關的存儲結構，試想一下，一個圖的鄰接表存儲結構還沒有弄清楚，如何設計一個圖的遍歷算法呢？所以在寫算法時腦海里要準確地呈現數據的存儲結構，這樣才會下筆有“神”，流暢地寫出正確的代碼，如同小學生在掌握相當量的詞匯和寫作技巧后才會寫出高質量的作文。

本書是作者針對數據結構課程的特點，在總結自己長期教學經驗的基礎上編寫的。本書的“簡明”性主要體現在以下兩個方面。

一是內容上的簡明性。本書的內容基本涵蓋了最新全國計算機專業聯考大綱（2018年）數據結構部分的知識點，講授上省去了一些難度較大的應用和擴展內容，如表達式求值和迷宮問題、串的KMP算法和廣義表等。

二是寫作上的簡明性。作者在寫作時遵循“簡潔如iPhone”的風格，主要體現為知識點、知識結構和算法表述簡明清晰。

本書的主要特色如下。

·力求實現從C/C++語言程序設計到數據結構算法設計的無縫對接，對算法設計中用到的一些C/C++語言難點如指針、引用類型等，結合算法設計的特點予以充分的講述。實際上，算法描述中除了引用類型屬于C++，其他均采用C語言的基本語法。

·通過通俗易懂的示例簡單明了地講解數據結構解決問題的一般性思路，如一些綜合性示例統一從問題描述、設計存儲結構、設計基本運算算法、設計主程序和程序運行結果幾方面來講解，突出數據結構求解問題的三個層次。

·采用大量圖示描述算法設計的思路，如求最小生成樹的Prim算法、求圖中最短路徑的Dijkstra算法和各種內排序算法中都通過直觀的圖示，不僅描述這些算法的設計思路，而且講解這些算法為什么這樣設計的精髓。

·注重算法設計的簡潔和易懂特性，同一種算法可以有多種設計方法，本書中盡可能采用簡單的設計方法，如二叉排序樹查找、刪除等都用非遞歸算法來實現。

·力求歸納數據結構算法設計的通用性方法，如單鏈表算法設計、遞歸算法設計、二叉樹的算法設計和圖算法設計等，都相應地總結出通用求解的方法，讀者只要靈活運用這些通用方法，便可以舉一反三自己設計求解較復雜問題的算法。

·書中提供了大量的練習題和上機實驗題，各類練習題401道，各類上機實驗題118道，便于讀者練習和實訓。

·書中所有算法都用C/C++語言編寫并上機調試，并配套有較完整的教學資源（含教學PPT和所有算法和示例源程序），讀者可以從清華大學出版社網站http://www.tup.edu.cn免費下載。對于學習計算機專業的學生，直接閱讀程序代碼可能比看“偽碼”更簡明。

·本書配套有《數據結構簡明教程學習與上機實驗指導》（李春葆等，清華大學出版社，2018），涵蓋所有練習題和上機實驗題的參考答案。

·本書配套有全部知識點的教學視頻，視頻采用微課碎片化形式組織（含141個小視頻，累計25小時），讀者通過掃描二維碼即可觀看相關視頻講解。

全書分為9章，第1章為概論，介紹數據結構的基本概念，特別強調了基本算法設計和分析的方法；第2章為線性表，介紹線性表的概念、兩種存儲結構即順序表和鏈表，線性表基本運算的實現算法以及線性表的應用；第3章為棧和隊列，介紹這兩種特殊線性表的概念、存儲結構和相關應用；第4章為串，介紹串的概念、串的兩種存儲結構和應用；第5章為數組和稀疏矩陣，介紹數組的概念、幾種特殊矩陣的壓縮方法、稀疏矩陣的定義和壓縮存儲結構；第6章為樹和二叉樹，介紹樹的概念和性質，二叉樹的概念，二叉樹的兩種主要存儲結構，二叉樹各種運算算法設計，哈夫曼樹和哈夫曼編碼，特別突出了二叉樹遞歸算法設計方法；第7章為圖，介紹圖的概念、圖的兩種主要的存儲結構、圖遍歷算法以及圖的各類應用；第8章為查找，介紹各種查找算法的實現過程；第9章為排序，介紹各種主要的內排序算法設計方法和基本的外排序過程。附錄A給出了書中部分算法清單，附錄B給出了全國計算機專業數據結構2017年研究生聯考大綱。

本書適合作為計算機及相關專業本、專科生“數據結構”課程的教材，也適合于各類計算機考試人員參考。

本書的編寫得到湖北省教改項目“計算機科學與技術專業課程體系改革”的資助，清華大學出版社給予了大力支持，許多授課教師和同學提出建設性意見，編者在此一并表示衷心感謝。

由于水平所限，盡管編者不遺余力，書中仍可能存在疏漏和不足之處，歡迎讀者聯系并批評指正。

編者

2018年10月