信息學(xué)競賽寶典數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

定　價：￥89.90

作　者：	張新華梁靖韻劉樹明
出版社：	人民郵電出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購買這本書可以去

當(dāng)當(dāng)網(wǎng) (￥85.40)

ISBN：	9787115635020	出版時間：	2024-06-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字?jǐn)?shù)：

內(nèi)容簡介

　　數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式，往往同高效的檢索算法和索引技術(shù)有關(guān)。學(xué)習(xí)和掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，使我們能夠更好地運(yùn)用計算機(jī)來解決實(shí)際問題。為了提高讀者的學(xué)習(xí)效率，本書直接從各類競賽真題入手，以精練而準(zhǔn)確的語言、全面細(xì)致地介紹了信息學(xué)競賽中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)類型，包括鏈表、堆棧、隊(duì)列、樹、圖等。本書精挑細(xì)選、由淺入深地安排了相關(guān)習(xí)題。考慮讀者接受水平的差異，一般在引入新知識點(diǎn)的題目時，本書會提供該題目的完整參考代碼，但隨著讀者對此知識點(diǎn)的理解逐步加深，后續(xù)的同類型題目將逐步向僅提供算法思路、提供偽代碼和無任何提示的方式轉(zhuǎn)變。此外，對于一些思維跨度較大的題目，本書會酌情給予讀者一定的提示。本書可以與《信息學(xué)競賽寶典　基礎(chǔ)算法》同步學(xué)習(xí)，也可以作為有一定編程基礎(chǔ)的讀者學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法的獨(dú)立用書。

作者簡介

　　張新華中學(xué)高級教師，信息學(xué)競賽教練。取得浙江大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)士學(xué)位、廈門大學(xué)軟件工程碩士學(xué)位，獲得 2009年普通高中信息技術(shù)現(xiàn)場優(yōu)質(zhì)課比賽全國一等獎。培養(yǎng)的學(xué)生多次獲得全國青少年信息學(xué)奧賽國家一等獎及亞洲與太平洋地區(qū)信息學(xué)奧賽獎牌。著有“信息學(xué)競賽寶典”系列書。開發(fā)了三維圖形化 C 編程工具 Dev-C 智能開發(fā)平臺和 Python 可視化界面設(shè)計軟件 Visual Python。梁靖韻中學(xué)高級教師，高級程序員，取得華南師范大學(xué)碩士學(xué)位，入選廣州市“百千萬人才培養(yǎng)工程”第二批名教師培養(yǎng)對象。長期從事信息學(xué)競賽、計算機(jī)作品比賽與科技創(chuàng)新競賽輔導(dǎo)工作。劉樹明深圳市第二實(shí)驗(yàn)學(xué)校信息技術(shù)教師，二十一世紀(jì)教育網(wǎng)創(chuàng)始人。精通 C 、C#、Python、PHP 語言編程，有大量大型軟件系統(tǒng)的研發(fā)經(jīng)驗(yàn)，獨(dú)立或者與他人一起研發(fā)的排課系統(tǒng)、閱卷系統(tǒng)等教育教學(xué)軟件在國內(nèi)享有良好口碑。

圖書目錄

第 1章鏈表
1.1　何謂鏈表　/　1
1.2　簡單靜態(tài)鏈表　/　2
1.3　動態(tài)鏈表　/　3
1.3.1　鏈表的建立　/　3
1.3.2　鏈表的顯示　/　4
1.3.3　查找節(jié)點(diǎn)元素x的位置　/　4
1.3.4　返回鏈表的長度　/　4
1.3.5　獲得節(jié)點(diǎn)元素值　/　5
1.3.6　節(jié)點(diǎn)的插入　/　5
1.3.7 節(jié)點(diǎn)的刪除　/　6
1.3.8　釋放鏈表　/　7
1.4　數(shù)組與鏈表的比較　/　7
1.5　課后練習(xí)　/　8

第 2章堆棧
2.1　堆棧的定義　/　9
2.2　數(shù)組仿真堆?！?　9
2.3　單調(diào)?！?　12
2.4　后序表達(dá)式　/　16
2.5　課后練習(xí)　/　19

第3章隊(duì)列
3.1　隊(duì)列的定義　/　21
3.2　數(shù)組仿真隊(duì)列　/　21
3.3　數(shù)組循環(huán)隊(duì)列　/　23
3.4　單調(diào)隊(duì)列　/　29
3.5　課后練習(xí)　/　31

第4章樹
4.1　樹的介紹　/　32
4.1.1　樹的概念及表示　/　32
4.1.2　樹的相關(guān)術(shù)語　/　33
4.2　二叉樹　/　34
4.2.1　二叉樹的概念　/　34
4.2.2 二叉樹的性質(zhì)　/　35
4.3　二叉樹的表示　/　42
4.3.1　二叉樹數(shù)組表示法　/　42
4.3.2　二叉樹結(jié)構(gòu)體數(shù)組表示法　/　45
4.3.3 二叉樹鏈表表示法　/　48
4.4　二叉樹的遍歷　/　50
4.4.1　二叉樹的前序遍歷　/　50
4.4.2　二叉樹的中序遍歷　/　53
4.4.3　二叉樹的后序遍歷　/　54
4.4.4　二叉樹的圖形化顯示　/　55
4.4.5　已知前序、中序遍歷序列求后序遍歷序列　/　61
4.4.6 已知后序、中序遍歷序列求前序遍歷序列　/　62
4.4.7　已知前序、后序遍歷序列求中序遍歷序列　/　63
4.4.8 表達(dá)式處理　/　66
4.5　最優(yōu)二叉樹及應(yīng)用　/　71
4.5.1　最優(yōu)二叉樹　/　71
4.5.2　哈夫曼編碼　/　72
4.6　一般樹轉(zhuǎn)換成二叉樹　/　74
4.7　堆排序的實(shí)現(xiàn)　/　76
4.8　優(yōu)先隊(duì)列的實(shí)現(xiàn)　/　80
4.9　樹的一些應(yīng)用　/　86
4.9.1　樹的最小支配集　/　86
4.9.2　樹的最小點(diǎn)覆蓋　/　91
4.9.3 樹的最大獨(dú)立集　/　93
4.9.4　樹的直徑　/　95
4.9.5　樹的重心　/　100
4.10　二叉查找樹　/　102

第5章圖
5.1　圖的介紹　/　109
5.1.1　圖的基本概念　/　109
5.1.2　鄰接數(shù)組表示法　/　111
5.1.3　加權(quán)邊的圖　/　113
5.2　前向星　/　113
5.2.1　前向星表示法　/　113
5.2.2　前向星的DFS　/　117
5.2.3　前向星的BFS　/　120
5.3　生成樹問題　/　122
5.3.1　Kruskal算法　/　123
5.3.2　Prim算法　/　126
5.4　最短路問題　/　128
5.4.1　Dijkstra算法　/　128
5.4.2　Dijkstra算法的堆優(yōu)化　/　132
5.4.3 Floyd算法　/　133
5.4.4 最小環(huán)問題　/　135
5.4.5　Bellman-Ford算法　/　137
5.4.6　SPFA及優(yōu)化　/　140
5.5　拓?fù)渑判颉?　147
5.5.1　拓?fù)渑判蚪榻B　/　147
5.5.2　關(guān)鍵路徑　/　152
5.6　DAG最長路　/　157
5.7　邊和頂點(diǎn)的可行遍性　/　159
5.7.1　歐拉圖　/　159
5.7.2　哈密爾頓環(huán)　/　164
5.8　無向圖的一些應(yīng)用　/　171
5.8.1　最大團(tuán)問題　/　171
5.8.2　無向圖的割點(diǎn)和橋　/　175
5.8.3　無向圖的雙連通分量　/　185
5.9 Kosaraju算法　/　191
5.10　樹的一些應(yīng)用　/　194
5.10.1　次小生成樹算法　/　194
5.10.2　基環(huán)樹　/　200
5.10.3　度限制生成樹　/　206
5.10.4　最小樹形圖　/　208

第6章哈希
6.1　哈?！?　215
6.2　字符串哈?！?　223
6.3　哈希樹　/　228

第7章樹狀數(shù)組
7.1　樹狀數(shù)組介紹　/　230
7.2　樹狀數(shù)組的簡單應(yīng)用　/　232
7.3　樹狀數(shù)組的區(qū)間更新　/　236
7.4　樹狀數(shù)組維護(hù)區(qū)間最值　/　239
7.5　樹狀數(shù)組求逆序?qū)Α?　244
7.6　樹狀數(shù)組的應(yīng)用　/　246
7.7　二維樹狀數(shù)組　/　249
7.8　課后練習(xí)　/　253

第8章并查集
8.1　基礎(chǔ)并查集　/　254
8.2　帶權(quán)并查集　/　259
8.3　種類并查集　/　261
8.4　課后練習(xí)　/　266

第9章線段樹
9.1　線段樹的基本操作　/　267
9.2　懶惰標(biāo)記的使用　/　282
9.3 線段樹區(qū)間乘與加　/　284
9.4　課后練習(xí)　/　287

第 10章二分圖
10.1　二分圖的概念及判定　/　288
10.2　二分圖最大匹配問題　/　291
10.3　最小點(diǎn)覆蓋問題　/　297
10.4　最小邊覆蓋問題　/　299
10.5　最小路徑覆蓋問題　/　303
10.6　最佳匹配問題　/　309
10.7　課后練習(xí)　/　314