導讀
本書是關於數據結構與算法的經典教材，主要論述了數據的邏輯結構、存儲結構、算法設計以及算法評價，使讀者能夠深入了解線性表、棧、隊列、樹、圖等數據結構以及排序和檢索等基礎算法，並掌握在不同的數據結構上進行有關算法設計的思想和技巧。書中包含大量代碼實例和詳盡的解釋，非常適合作為計算機專業本科生的低年級入門教材。
全書由淺入深，分成了五部分。針對計算機專業的低年級本科生而言，可重點學習前面三部分的內容，學有餘力的讀者可以在此基礎上繼續研讀後面的內容。下面為讀者介紹本書的重點內容。
基礎知識
本書第1章介紹數據結構的入門基礎知識。其中1.1節主要介紹數據結構的定義、基本術語以及數據結構的基本類型。讀者可通過該節的學習，重點理解數據結構對抽像表達、程序建模的重要作用，了解在實際應用過程中數據結構的優缺點分析方法。1.2節重點介紹基於抽像數據類型的數據結構描述方法，這是整本書中各個數據結構的基本描述方法。讀者可穿插翻閱後面第4章至第6章中各種數據結構的抽像數據類型，加深對此概念的理解。此外，通過學習1.4節，讀者可進一步理解數據結構、問題與算法的關繫。
第2章介紹本課程涉及的一些基礎數學知識。這裡介紹的絕大部分數學知識，讀者都在中學階段學過。讀者可簡單快速地瀏覽一下，用時再來回顧翻查。
第3章主要介紹算法復雜度的定義以及分析方法。通過學習這一章，讀者就能了解漸近算法復雜度分析方法，理解上界分析、下界分析以及確切界的具體定義和快速分析方法，並掌握針對任意給定程序片段的基本分析方法。
數據結構
本書第II部分是整本教材的重點，主要討論了線性表(List)、二叉樹(Binary Tree)、普通樹(General Tree)和圖(Graph)的定義與實現方法。為了能對各類數據結構融會貫通，建議讀者將第4章至第6章以及第11章放在一起來進行對比學習。
第4章主要介紹線性表的定義、存儲實現方法，以及插入、刪除和定位等基本運算；介紹了棧和隊列的基本定義、基本操作，以及靈活運用線性表解決現實工程問題的方法。本章的重點是分析線性表的數組和鏈表這兩種實現方法的優缺點，實現線性表的插入、刪除和定位等基本運算的算法，掌握棧的入棧和出棧的操作以及隊列的入隊和出隊的操作。本章的難點是掌握單鏈表及循環鏈表的算法設計綜合應用，掌握在循環隊列上進行入隊、出隊以及求隊列長度的操作。
第5章主要闡述二叉樹的基本定義和存儲實現方式，介紹二叉樹的遍歷和搜索等基本操作，並討論堆和哈夫曼樹的基本原理和實現方法。本章的重點是基於鏈接和數組兩種存儲結構的二叉樹實現方法，基於遞歸的二叉樹遍歷算法，以及二叉檢索樹的搜索、刪除結點和添加結點等操作的實現。本章的難點是堆的構建，插入刪除結點的算法實現，以及哈夫曼樹和哈夫曼編碼的原理。
第6章主要介紹普通樹的基本定義、遍歷算法，以及樹的基本存儲結構的原理。本章的重點是左子結點/右兄弟結點的實現方法，以及普通樹和森林與二叉樹的相互轉換方法。本章的難點是普通樹的順序存儲方法。
第11章主要介紹圖的定義和實現方法，圖的遍歷算法、拓撲排序算法、最短路徑算法以及最小生成樹算法。本章的重點是圖的鄰接表和鄰接矩陣兩種實現方法的原理以及優缺點對比，基於遞歸函數的圖的遍歷算法的實現，拓撲排序算法的實現方法以及應用。本章的難點是Dijkstra最短路徑算法、Floyd最短路徑算法，以及最小支撐樹算法。
排序與檢索算法
第III部分主要介紹排序與檢索這兩類比較常見的算法，讀者在掌握了前面所學數據結構的基礎上，可以較為容易地掌握這些算法。
第7章和第8章主要介紹排序算法的定義、排序算法的穩定性分析方法、排序算法的設計與實現、排序算法的復雜度對比分析，以及排序算法的應用。這兩章的重點是快速排序算法、歸並排序算法以及堆排序算法的實現。這兩章的難點是希爾排序算法的原理和實現，以及快速排序算法的改進方法。
第9章主要介紹檢索的基本原理和二分法檢索，討論了哈希表的原理、構建以及相關操作。本章的重點是哈希表的原理、哈希函數的設計方法，以及哈希表的插入和刪除算法的實現。本章的難點是哈希表的衝突解決策略。
第10章主要介紹線性索引、2-3樹索引、B/B+樹索引的構建方法，以及算法復雜度分析方法。本章的重點是線性索引和2-3樹索引的插入、刪除和檢索算法，以及B樹和B+樹的定義。本章的難點是B樹和B+樹的插入、刪除和檢索算法。
至此，通過前三部分的學習，讀者已掌握了數據結構的基本知識、理論和分析方法，為從事相關計算機程序分析和設計工作以及相關專業的後續課程學習打下了扎實的基礎。讀者在本書各章節的學習過程中，可動手實踐對應的程序代碼，掌握各類數據結構與算法的實現方法。華南理工大學計算機科學與工程學院的“數據結構”課程采用了本書作為教材。我們授課團隊結合本書設計了相應的在線教學視頻(https://next.xuetangx.com/course/SCUT08091000960/)，感興趣的讀者可參考學習，定能起到事半功倍的作用。采用本書作為教材的授課教師，也可登錄華信教育資源網(www.hxedu.com.cn)注冊後免費下載我們的教學用PPT等相關資料。
呂建明教授 博導
華南理工大學計算機科學與工程學院
Preface
We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we attempt more complex tasks.
The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with “programming tricks” but rather is based on good organization of information and good algorithms. A programmer who has not mastered the basic principles of clear design is not likely to write efficient programs. Conversely, concerns related to development costs and maintainability should not be used as an excuse to justify inefficient performance. Generality in design can and should be achieved without sacrificing performance, but this can only be done if the designer understands how to measure performance and does so as an integral part of the design and implementation process. Most computer science curricula recognize that good programming skills begin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and implementation, the next step is to study the effects of data organization and algorithms on program efficiency.
Approach: This book describes many techniques for representing data. These techniques are presented within the context of the following principles:
1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation f
