數(shù)據(jù)結(jié)構(gòu)是研究計(jì)算機(jī)科學(xué)和工程的基礎(chǔ)，數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)及相關(guān)專業(yè)的核心課程之一，學(xué)好該課程不僅對(duì)后續(xù)課程的學(xué)習(xí)有很大幫助，而且對(duì)開發(fā)有效利用計(jì)算機(jī)資源的程序極為有益。
計(jì)算機(jī)是進(jìn)行數(shù)據(jù)處理的工具，數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的各種組織形式以及建立在這些結(jié)構(gòu)上的各種運(yùn)算算法的實(shí)現(xiàn)，它不僅為用計(jì)算機(jī)語言進(jìn)行程序設(shè)計(jì)提供了方法性的理論指導(dǎo)，還在更高的層次上總結(jié)了程序設(shè)計(jì)的常用方法和常用技巧。
本書是編者針對(duì)數(shù)據(jù)結(jié)構(gòu)課程概念多、算法靈活和抽象性強(qiáng)等特點(diǎn)，在總結(jié)長期教學(xué)經(jīng)驗(yàn)的基礎(chǔ)上編寫的。全書分為12章和5個(gè)附錄，第1章為緒論，介紹數(shù)據(jù)結(jié)構(gòu)的基本概念，特別強(qiáng)調(diào)算法分析的方法； 第2章為線性表，介紹線性表的兩種存儲(chǔ)結(jié)構(gòu)順序表和鏈表，以及基本運(yùn)算算法的實(shí)現(xiàn)過程； 第3章為棧和隊(duì)列，介紹這兩種特殊的線性結(jié)構(gòu)的概念與應(yīng)用； 第4章為串，介紹串的概念與模式匹配算法； 第5章為遞歸，討論計(jì)算機(jī)學(xué)科中遞歸算法的設(shè)計(jì)方法； 第6章為數(shù)組和廣義表，介紹數(shù)組、稀疏矩陣和廣義表的概念與相關(guān)運(yùn)算算法的實(shí)現(xiàn)過程； 第7章為樹和二叉樹，介紹樹和二叉樹的概念與各種運(yùn)算算法的實(shí)現(xiàn)過程，其中特別介紹二叉樹的各種遞歸算法方法； 第8章為圖，介紹圖的概念和圖的各種運(yùn)算算法的實(shí)現(xiàn)過程； 第9章為查找，介紹各種查找算法的實(shí)現(xiàn)過程； 第10章為內(nèi)排序，介紹各種內(nèi)排序算法的實(shí)現(xiàn)過程； 第11章為外排序，介紹各種外排序算法的實(shí)現(xiàn)過程； 第12章為采用面向?qū)ο蟮姆椒枋鏊惴ǎ榻B面向?qū)ο蟮母拍詈筒捎肅 語言描述數(shù)據(jù)結(jié)構(gòu)算法的方法。
附錄A給出了實(shí)驗(yàn)報(bào)告格式； 附錄B是引用型參數(shù)和指針引用型參數(shù)的說明； 附錄C給出了書中全部算法的索引； 附錄D給出了書中相關(guān)名詞的索引； 附錄E為教育頒布的2022年全國計(jì)算機(jī)專業(yè)碩士研究生入學(xué)考試專業(yè)課中的數(shù)據(jù)結(jié)構(gòu)部分考試大綱。標(biāo)注*的知識(shí)點(diǎn)作為選學(xué)內(nèi)容。
數(shù)據(jù)結(jié)構(gòu)是一門應(yīng)用實(shí)踐性非常強(qiáng)的課程，學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)（特別是存儲(chǔ)結(jié)構(gòu)）的基礎(chǔ)上一定要盡可能多地上機(jī)實(shí)習(xí)，通過較多的實(shí)驗(yàn)把難以理解的抽象概念轉(zhuǎn)化為實(shí)實(shí)在在的能夠在計(jì)算機(jī)上執(zhí)行的程序，這樣才能將所學(xué)知識(shí)和實(shí)際應(yīng)用結(jié)合起來，吸取算法的設(shè)計(jì)思想和精髓，提高運(yùn)用這些知識(shí)解決實(shí)際問題的能力。因此，本書突出上機(jī)實(shí)習(xí)內(nèi)容，書中給出了大量的上機(jī)實(shí)驗(yàn)題(分為驗(yàn)證性實(shí)驗(yàn)、設(shè)計(jì)性實(shí)驗(yàn)和綜合性實(shí)驗(yàn))，同時(shí)按各章知識(shí)點(diǎn)精選了若干LeetCode網(wǎng)站(http://leetcodecn.com)的在線編程題（題目的難度用1~3星表示，分別對(duì)應(yīng)簡單、中等和困難三個(gè)級(jí)別）供教師和學(xué)生選用。
為了便于學(xué)生學(xué)習(xí)和上機(jī)實(shí)驗(yàn)，編者還編寫了與本書配套的《數(shù)據(jù)結(jié)構(gòu)教程(第6版)學(xué)習(xí)指導(dǎo)》《數(shù)據(jù)結(jié)構(gòu)教程(第6版)上機(jī)實(shí)驗(yàn)指導(dǎo)》和《數(shù)據(jù)結(jié)構(gòu)LeetCode在線編程實(shí)訓(xùn)(C/C 語言)全程視頻講解版》三本書，構(gòu)成一個(gè)完整的教學(xué)系列。本系列教程中的所有程序均在Dev C 5和Visual C 6．0環(huán)境（程序文件為*.cpp）下調(diào)試通過。
為了方便教師教學(xué)和學(xué)生學(xué)習(xí)，本書提供了全面而豐富的教學(xué)資源，配套教學(xué)資源包的內(nèi)容如下。
（1） 教學(xué)課件（PPT）： 提供全部教學(xué)內(nèi)容的精美PPT，供任課教師教學(xué)中使用。
（2） 思政教學(xué)課件（PPT）： 提供包含思政教學(xué)內(nèi)容的精美PPT，供任課教師教學(xué)中使用。
（3） 教學(xué)大綱和電子教案： 包含數(shù)據(jù)結(jié)構(gòu)課程支撐的各個(gè)畢業(yè)要求指標(biāo)點(diǎn)，課程介紹、教學(xué)目的、課程內(nèi)容和學(xué)時(shí)分配（72學(xué)時(shí)），每個(gè)課時(shí)的教學(xué)內(nèi)容安排。
（4） 實(shí)驗(yàn)教學(xué)大綱： 包含課程教學(xué)介紹、教學(xué)目的、實(shí)驗(yàn)基本要求與方式、實(shí)驗(yàn)報(bào)告、課程內(nèi)容與學(xué)時(shí)（36學(xué)時(shí)）分配。
（5） 程序源碼： 所有源代碼按章組織，例如第3章文件夾存放第3章的全部源代碼，其中第3章＼algorithm37.cpp為例3.7的源代碼。
（6） 微課視頻： 書中配套有絕大部分知識(shí)點(diǎn)的教學(xué)視頻，視頻采用微課碎片化形式組織（總時(shí)長超過50小時(shí)）。
（7） 在線作業(yè)： 包括選擇題、判斷題、填空題、簡答題和編程題。
（8） 附錄E除了2022年全國計(jì)算機(jī)聯(lián)考數(shù)據(jù)結(jié)構(gòu)部分大綱外，還包含20182021年全國計(jì)算機(jī)專業(yè)研究生入學(xué)聯(lián)考數(shù)據(jù)結(jié)構(gòu)部分試題的講解視頻。
資源下載提示
課件等資源： 掃描封底的課件下載二維碼，在公眾號(hào)書圈下載。
素材（源碼）等資源： 掃描目錄上方的二維碼下載。
在線作業(yè)： 掃描封底的作業(yè)系統(tǒng)二維碼，登錄網(wǎng)站在線做題及查看答案。
視頻等資源： 掃描封底的文泉云盤防盜碼，再掃描書中相應(yīng)章節(jié)中的二維碼，可以在線學(xué)習(xí)。
本書和配套的上機(jī)實(shí)驗(yàn)指導(dǎo)、學(xué)習(xí)指導(dǎo)的編寫得到了武漢大學(xué)弘毅學(xué)堂數(shù)據(jù)結(jié)構(gòu)榮譽(yù)課程教學(xué)項(xiàng)目和湖北省計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)課程體系
改革項(xiàng)目的資助，聚集了課程組許多教師多年來在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)研究和教學(xué)改革中的經(jīng)驗(yàn)與成果。本書在編寫過程中得到了王麗娜、黃傳河和吳黎兵等多位教授、博導(dǎo)的大力支持，陳國良院士提供了富有建設(shè)性的指導(dǎo)，很多使用本書的老師和同學(xué)給予了熱心幫助，并與清華大學(xué)出版社的魏江江分社長和王冰飛編輯進(jìn)行了愉快的合作，除了署名作者外，課程組的汪鼎文、安楊、李蓉蓉、文衛(wèi)東、李小紅、何璐璐、夏啟明等老師也參與了大量的課程探討和教學(xué)實(shí)踐工作。編者在此一并表示衷心的感謝。
由于編者水平所限，盡管不遺余力，書中仍存在不足之處，敬請(qǐng)讀者批評(píng)指正。
編者
2022年5月
源碼下載
數(shù)據(jù)結(jié)構(gòu)課程思政視頻
第1章緒論/
1.1什么是數(shù)據(jù)結(jié)構(gòu)/
1.1.1數(shù)據(jù)結(jié)構(gòu)的定義/
1.1.2邏輯結(jié)構(gòu)/
1.1.3存儲(chǔ)結(jié)構(gòu)/
1.1.4數(shù)據(jù)運(yùn)算/
1.1.5數(shù)據(jù)類型和抽象數(shù)據(jù)類型/
1.2算法及其描述/
1.2.1算法的定義/
1.2.2算法設(shè)計(jì)的目標(biāo)/
1.2.3算法的描述/
1.3算法分析/
1.3.1算法分析概述/
1.3.2算法的時(shí)間性能分析/
1.3.3算法的空間性能分析/
1.4數(shù)據(jù)結(jié)構(gòu) 算法=程序/
1.4.1程序和數(shù)據(jù)結(jié)構(gòu)/
1.4.2算法和程序/
1.4.3算法和數(shù)據(jù)結(jié)構(gòu)/
1.4.4數(shù)據(jù)結(jié)構(gòu)的發(fā)展/
本章小結(jié)/
練習(xí)題1/
上機(jī)實(shí)驗(yàn)題1/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
LeetCode在線編程題1/
第2章線性表/
2.1線性表及其邏輯結(jié)構(gòu)/
2.1.1線性表的定義/
2.1.2線性表的抽象數(shù)據(jù)類型描述/
2.2線性表的順序存儲(chǔ)結(jié)構(gòu)/
2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)順序表/
2.2.2順序表基本運(yùn)算的實(shí)現(xiàn)/
2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)/
2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表/
2.3.2單鏈表/
2.3.3雙鏈表/
2.3.4循環(huán)鏈表/
2.4線性表的應(yīng)用/
2.5有序表/
2.5.1有序表的抽象數(shù)據(jù)類型描述/
2.5.2有序表的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法/
2.5.3有序表的歸并算法/
2.5.4有序表的應(yīng)用/
本章小結(jié)/
練習(xí)題2/
上機(jī)實(shí)驗(yàn)題2/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題2/
第3章棧和隊(duì)列/
3.1棧/
3.1.1棧的定義/
3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)/
3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)/
3.1.4棧的應(yīng)用/
3.2隊(duì)列/
3.2.1隊(duì)列的定義/
3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)/
3.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)/
3.2.4隊(duì)列的應(yīng)用舉例/
3.2.5雙端隊(duì)列/
本章小結(jié)/
練習(xí)題3/
上機(jī)實(shí)驗(yàn)題3/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題3/
第4章串/
4.1串的基本概念/
4.2串的存儲(chǔ)結(jié)構(gòu)/
4.2.1串的順序存儲(chǔ)結(jié)構(gòu)順序串/
4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈串/
4.3串的模式匹配/
4.3.1BruteForce算法/
4.3.2KMP算法/
本章小結(jié)/
練習(xí)題4/
上機(jī)實(shí)驗(yàn)題4/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題4/
第5章遞歸/
5.1什么是遞歸/
5.1.1遞歸的定義/
5.1.2何時(shí)使用遞歸/
5.1.3遞歸模型/
5.1.4遞歸與數(shù)學(xué)歸納法/
5.2棧和遞歸/
5.2.1函數(shù)調(diào)用棧/
5.2.2遞歸調(diào)用的實(shí)現(xiàn)/
5.2.3遞歸算法的時(shí)空性能分析/
5.2.4遞歸到非遞歸的轉(zhuǎn)換*/
5.3遞歸算法的設(shè)計(jì)/
5.3.1遞歸算法的設(shè)計(jì)步驟/
5.3.2基于遞歸數(shù)據(jù)結(jié)構(gòu)的遞歸算法設(shè)計(jì)/
5.3.3基于遞歸求解方法的遞歸算法設(shè)計(jì)/
本章小結(jié)/
練習(xí)題5/
上機(jī)實(shí)驗(yàn)題5/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題5/
第6章數(shù)組和廣義表/
6.1數(shù)組/
6.1.1數(shù)組的基本概念/
6.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)/
6.1.3特殊矩陣的壓縮存儲(chǔ)/
6.2稀疏矩陣/
6.2.1稀疏矩陣的三元組表示/
6.2.2稀疏矩陣的十字鏈表表示/
6.3廣義表/
6.3.1廣義表的定義/
6.3.2廣義表的存儲(chǔ)結(jié)構(gòu)/
6.3.3廣義表的運(yùn)算*/
本章小結(jié)/
練習(xí)題6/
上機(jī)實(shí)驗(yàn)題6/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題6/
第7章樹和二叉樹/
7.1樹的基本概念/
7.1.1樹的定義/
7.1.2樹的邏輯表示方法/
7.1.3樹的基本術(shù)語/
7.1.4樹的性質(zhì)/
7.1.5樹的基本運(yùn)算/
7.1.6樹的存儲(chǔ)結(jié)構(gòu)/
7.2二叉樹的概念和性質(zhì)/
7.2.1二叉樹的定義/
7.2.2二叉樹的性質(zhì)/
7.2.3二叉樹與樹、森林之間的轉(zhuǎn)換/
7.3二叉樹的存儲(chǔ)結(jié)構(gòu)/
7.3.1二叉樹的順序存儲(chǔ)結(jié)構(gòu)/
7.3.2二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)/
7.4二叉樹的基本運(yùn)算及其實(shí)現(xiàn)/
7.4.1二叉樹的基本運(yùn)算的概述/
7.4.2二叉樹的基本運(yùn)算算法的實(shí)現(xiàn)/
7.5二叉樹的遍歷/
7.5.1二叉樹遍歷的概念/
7.5.2先序、中序和后序遍歷遞歸算法/
7.5.3先序、中序和后序遍歷非遞歸算法*/
7.5.4層次遍歷算法/
7.6二叉樹的構(gòu)造/
7.7線索二叉樹/
7.7.1線索二叉樹的概念/
7.7.2線索化二叉樹/
7.7.3遍歷線索化二叉樹/
7.8哈夫曼樹/
7.8.1哈夫曼樹概述/
7.8.2哈夫曼樹的構(gòu)造算法/
7.8.3哈夫曼編碼/
7.9用并查集求解等價(jià)問題/
7.9.1并查集的定義/
7.9.2并查集的算法實(shí)現(xiàn)/
本章小結(jié)/
練習(xí)題7/
上機(jī)實(shí)驗(yàn)題7/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題7/
第8章圖/
8.1圖的基本概念/
8.1.1圖的定義/
8.1.2圖的基本術(shù)語/
8.2圖的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算算法/
8.2.1鄰接矩陣存儲(chǔ)方法/
8.2.2鄰接表存儲(chǔ)方法/
8.2.3圖的基本運(yùn)算算法設(shè)計(jì)/
8.2.4其他存儲(chǔ)方法/
8.3圖的遍歷/
8.3.1圖的遍歷的概念/
8.3.2深度優(yōu)先遍歷/
8.3.3廣度優(yōu)先遍歷/
8.3.4非連通圖的遍歷/
8.3.5圖遍歷算法的應(yīng)用/
8.4生成樹和最小生成樹/
8.4.1生成樹的概念/
8.4.2非連通圖和生成樹/
8.4.3普里姆算法/
8.4.4克魯斯卡爾算法/
8.5最短路徑/
8.5.1路徑的概念/
8.5.2從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑/
8.5.3每對(duì)頂點(diǎn)之間的最短路徑/
8.6拓?fù)渑判?
8.7AOE網(wǎng)與關(guān)鍵路徑/
8.7.1相關(guān)概念/
8.7.2求AOE網(wǎng)的關(guān)鍵活動(dòng)/
本章小結(jié)/
練習(xí)題8/
上機(jī)實(shí)驗(yàn)題8/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題8/
第9章查找/
9.1查找的基本概念/
9.2線性表的查找/
9.2.1順序查找/
9.2.2折半查找/
9.2.3索引存儲(chǔ)結(jié)構(gòu)和分塊查找/
9.3樹表的查找/
9.3.1二叉排序樹/
9.3.2平衡二叉樹/
9.3.3紅黑樹/
9.3.4B樹/
9.3.5B 樹/
9.4哈希表的查找/
9.4.1哈希表的基本概念/
9.4.2哈希函數(shù)的構(gòu)造方法/
9.4.3哈希沖突的解決方法/
9.4.4哈希表的運(yùn)算算法/
本章小結(jié)/
練習(xí)題9/
上機(jī)實(shí)驗(yàn)題9/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題9/
第10章內(nèi)排序/
10.1排序的基本概念/
10.2插入排序/
10.2.1直接插入排序/
10.2.2折半插入排序/
10.2.3希爾排序/
10.3交換排序/
10.3.1冒泡排序/
10.3.2快速排序/
10.4選擇排序/
10.4.1簡單選擇排序/
10.4.2堆排序/
10.5歸并排序/
10.6基數(shù)排序/
10.7各種內(nèi)排序方法的比較和選擇/
本章小結(jié)/
練習(xí)題10/
上機(jī)實(shí)驗(yàn)題10/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
綜合性實(shí)驗(yàn)/
LeetCode在線編程題10/
第11章外排序/
11.1外排序的概述/
11.2磁盤排序/
11.2.1磁盤排序概述/
11.2.2生成初始?xì)w并段/
11.2.3多路平衡歸并/
11.2.4最佳歸并樹/
本章小結(jié)/
練習(xí)題11/
上機(jī)實(shí)驗(yàn)題11/
驗(yàn)證性實(shí)驗(yàn)/
設(shè)計(jì)性實(shí)驗(yàn)/
第12章采用面向?qū)ο蟮姆椒枋鏊惴?
12.1面向?qū)ο蟮母拍?
12.2用C 描述面向?qū)ο蟮某绦?
12.2.1類/
12.2.2類對(duì)象/
12.2.3構(gòu)造函數(shù)和析構(gòu)函數(shù)/
12.2.4模板類/
12.3用C 描述數(shù)據(jù)結(jié)構(gòu)算法/
12.3.1順序表類模板/
12.3.2鏈棧類模板/
12.4使用STL設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)算法/
附錄A實(shí)驗(yàn)報(bào)告格式/
附錄B引用型參數(shù)和指針引用型參數(shù)的說明/
附錄C算法索引/
附錄D名詞索引/
附錄E全國計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)2022年
聯(lián)考大綱/
參考文獻(xiàn)/
書單推薦
