導(dǎo)讀
本書是關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法的經(jīng)典教材，主要論述了數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法設(shè)計以及算法評價，使讀者能夠深入了解線性表、棧、隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)以及排序和檢索等基礎(chǔ)算法，并掌握在不同的數(shù)據(jù)結(jié)構(gòu)上進行有關(guān)算法設(shè)計的思想和技巧。書中包含大量代碼實例和詳盡的解釋，非常適合作為計算機專業(yè)本科生的低年級入門教材。
全書由淺入深，分成了五部分。針對計算機專業(yè)的低年級本科生而言，可重點學(xué)習(xí)前面三部分的內(nèi)容，學(xué)有余力的讀者可以在此基礎(chǔ)上繼續(xù)研讀后面的內(nèi)容。下面為讀者介紹本書的重點內(nèi)容。
基礎(chǔ)知識
本書第1章介紹數(shù)據(jù)結(jié)構(gòu)的入門基礎(chǔ)知識。其中1.1節(jié)主要介紹數(shù)據(jù)結(jié)構(gòu)的定義、基本術(shù)語以及數(shù)據(jù)結(jié)構(gòu)的基本類型。讀者可通過該節(jié)的學(xué)習(xí)，重點理解數(shù)據(jù)結(jié)構(gòu)對抽象表達、程序建模的重要作用，了解在實際應(yīng)用過程中數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點分析方法。1.2節(jié)重點介紹基于抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)描述方法，這是整本書中各個數(shù)據(jù)結(jié)構(gòu)的基本描述方法。讀者可穿插翻閱后面第4章至第6章中各種數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型，加深對此概念的理解。此外，通過學(xué)習(xí)1.4節(jié)，讀者可進一步理解數(shù)據(jù)結(jié)構(gòu)、問題與算法的關(guān)系。
第2章介紹本課程涉及的一些基礎(chǔ)數(shù)學(xué)知識。這里介紹的絕大部分數(shù)學(xué)知識，讀者都在中學(xué)階段學(xué)過。讀者可簡單快速地瀏覽一下，用時再來回顧翻查。
第3章主要介紹算法復(fù)雜度的定義以及分析方法。通過學(xué)習(xí)這一章，讀者就能了解漸近算法復(fù)雜度分析方法，理解上界分析、下界分析以及確切界的具體定義和快速分析方法，并掌握針對任意給定程序片段的基本分析方法。
數(shù)據(jù)結(jié)構(gòu)
本書第II部分是整本教材的重點，主要討論了線性表(List)、二叉樹(Binary Tree)、普通樹(General Tree)和圖(Graph)的定義與實現(xiàn)方法。為了能對各類數(shù)據(jù)結(jié)構(gòu)融會貫通，建議讀者將第4章至第6章以及第11章放在一起來進行對比學(xué)習(xí)。
第4章主要介紹線性表的定義、存儲實現(xiàn)方法，以及插入、刪除和定位等基本運算；介紹了棧和隊列的基本定義、基本操作，以及靈活運用線性表解決現(xiàn)實工程問題的方法。本章的重點是分析線性表的數(shù)組和鏈表這兩種實現(xiàn)方法的優(yōu)缺點，實現(xiàn)線性表的插入、刪除和定位等基本運算的算法，掌握棧的入棧和出棧的操作以及隊列的入隊和出隊的操作。本章的難點是掌握單鏈表及循環(huán)鏈表的算法設(shè)計綜合應(yīng)用，掌握在循環(huán)隊列上進行入隊、出隊以及求隊列長度的操作。
第5章主要闡述二叉樹的基本定義和存儲實現(xiàn)方式，介紹二叉樹的遍歷和搜索等基本操作，并討論堆和哈夫曼樹的基本原理和實現(xiàn)方法。本章的重點是基于鏈接和數(shù)組兩種存儲結(jié)構(gòu)的二叉樹實現(xiàn)方法，基于遞歸的二叉樹遍歷算法，以及二叉檢索樹的搜索、刪除結(jié)點和添加結(jié)點等操作的實現(xiàn)。本章的難點是堆的構(gòu)建，插入刪除結(jié)點的算法實現(xiàn)，以及哈夫曼樹和哈夫曼編碼的原理。
第6章主要介紹普通樹的基本定義、遍歷算法，以及樹的基本存儲結(jié)構(gòu)的原理。本章的重點是左子結(jié)點/右兄弟結(jié)點的實現(xiàn)方法，以及普通樹和森林與二叉樹的相互轉(zhuǎn)換方法。本章的難點是普通樹的順序存儲方法。
第11章主要介紹圖的定義和實現(xiàn)方法，圖的遍歷算法、拓撲排序算法、最短路徑算法以及最小生成樹算法。本章的重點是圖的鄰接表和鄰接矩陣兩種實現(xiàn)方法的原理以及優(yōu)缺點對比，基于遞歸函數(shù)的圖的遍歷算法的實現(xiàn)，拓撲排序算法的實現(xiàn)方法以及應(yīng)用。本章的難點是Dijkstra最短路徑算法、Floyd最短路徑算法，以及最小支撐樹算法。
排序與檢索算法
第III部分主要介紹排序與檢索這兩類比較常見的算法，讀者在掌握了前面所學(xué)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，可以較為容易地掌握這些算法。
第7章和第8章主要介紹排序算法的定義、排序算法的穩(wěn)定性分析方法、排序算法的設(shè)計與實現(xiàn)、排序算法的復(fù)雜度對比分析，以及排序算法的應(yīng)用。這兩章的重點是快速排序算法、歸并排序算法以及堆排序算法的實現(xiàn)。這兩章的難點是希爾排序算法的原理和實現(xiàn)，以及快速排序算法的改進方法。
第9章主要介紹檢索的基本原理和二分法檢索，討論了哈希表的原理、構(gòu)建以及相關(guān)操作。本章的重點是哈希表的原理、哈希函數(shù)的設(shè)計方法，以及哈希表的插入和刪除算法的實現(xiàn)。本章的難點是哈希表的沖突解決策略。
第10章主要介紹線性索引、2-3樹索引、B/B+樹索引的構(gòu)建方法，以及算法復(fù)雜度分析方法。本章的重點是線性索引和2-3樹索引的插入、刪除和檢索算法，以及B樹和B+樹的定義。本章的難點是B樹和B+樹的插入、刪除和檢索算法。
至此，通過前三部分的學(xué)習(xí)，讀者已掌握了數(shù)據(jù)結(jié)構(gòu)的基本知識、理論和分析方法，為從事相關(guān)計算機程序分析和設(shè)計工作以及相關(guān)專業(yè)的后續(xù)課程學(xué)習(xí)打下了扎實的基礎(chǔ)。讀者在本書各章節(jié)的學(xué)習(xí)過程中，可動手實踐對應(yīng)的程序代碼，掌握各類數(shù)據(jù)結(jié)構(gòu)與算法的實現(xiàn)方法。華南理工大學(xué)計算機科學(xué)與工程學(xué)院的“數(shù)據(jù)結(jié)構(gòu)”課程采用了本書作為教材。我們授課團隊結(jié)合本書設(shè)計了相應(yīng)的在線教學(xué)視頻(https://next.xuetangx.com/course/SCUT08091000960/)，感興趣的讀者可參考學(xué)習(xí)，定能起到事半功倍的作用。采用本書作為教材的授課教師，也可登錄華信教育資源網(wǎng)(www.hxedu.com.cn)注冊后免費下載我們的教學(xué)用PPT等相關(guān)資料。
呂建明教授 博導(dǎo)
華南理工大學(xué)計算機科學(xué)與工程學(xué)院
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
新書資訊