數據結構--從概念到Java實現
王紅梅、黨源源、劉冰
相關主題
商品描述
數據結構是電腦及相關專業的核心課程，也是電腦及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹了數據結構、算法以及抽象數據類型的概念，講述了線性表、棧和隊列、字符串和多維數組、樹和二叉樹、圖等常用數據結構，討論了查找和排序技術。本書通過合理規劃教學內容，梳理了知識單元及其拓撲結構，並兼顧概念層和實現層，既強調數據結構的基本概念和原理及方法，又註重數據結構的程序實現和實際運用，在提煉基礎知識的同時，進行了適當的擴展和提高。 本書內容豐富，層次清晰，深入淺出且結合了實例，可作為電腦及相關專業數據結構課程的教材，也可供從事電腦軟件開發和應用的工程技術人員參考和閱讀。
目錄大綱
第1章緒論1
1.1問題求解與程序設計2
1.1.1程序設計的一般過程2
1.1.2數據結構在程序設計中的作用5
1.1.3算法在程序設計中的作用6
1.1.4本書討論的主要內容7
1.2數據結構的基本概念8
1.2.1數據結構8
1.2.2抽像數據類型11
1.3算法的基本概念13
1.3.1算法及算法的特性13
1.3.2算法的描述方法14
1.4算法分析16
1.4.1算法的時間複雜度16
1.4.2算法的空間複雜度18
1.4.3算法分析舉例18
1.5擴展與提高21
1.5.1從數據到大數據21
1.5.2算法分析的其他漸進符號22
思想火花——概率算法23
習題24
第2章線性表27
2.1引言28
2.2線性表的邏輯結構29
2.2.1線性表的定義29數據結構——從概念到Java實現目錄2.2.2線性表的抽象數據類型29
2.2.3線性表的Java接口定義31
2.3線性表的順序存儲結構及實現31
2.3.1順序表的存儲結構31
2.3.2順序表的實現32
2.3.3順序表的使用37
2.4線性表的鏈接存儲結構及實現38
2.4.1單鍊錶的存儲結構39
2.4.2單鍊錶的實現41
2.4.3單鍊錶的使用47
2.4.4雙鍊錶48
2.4.5循環鍊錶50
2.5順序表和鍊錶的比較51
2.6擴展與提高52
2.6.1線性表的靜態鍊錶存儲52
2.6.2順序表的動態分配方式54
2.7應用實例55
2.7.1約瑟夫環問題55
2.7.2一元多項式求和57
思想火花——好算法是反复努力和重新修正的結果61
習題62
實驗題65
第3章棧和隊列67
3.1引言68
3.2棧69
3.2.1棧的邏輯結構69
3.2.2棧的順序存儲結構及實現70
3.2.3棧的鏈接存儲結構及實現73
3.2.4順序棧和鏈棧的比較76
3.3隊列76
3.3.1隊列的邏輯結構76
3.3.2隊列的順序存儲結構及實現77
3.3.3隊列的鏈接存儲結構及實現82
3.3.4循環隊列與鏈隊列的比較85
3.4擴展與提高85
3.4.1兩棧共享空間85
3.4.2雙端隊列87
3.5應用舉例88
3.5.1括號匹配問題88
3.5.2表達式求值89
思想火花——好程序要能識別和處理各種輸入92
習題93
實驗題95
第4章字符串和多維數組97
4.1引言98
4.2字符串99
4.2.1字符串的邏輯結構99
4.2.2字符串的存儲結構101
4.2.3模式匹配101
4.3多維數組105
4.3.1數組的邏輯結構105
4.3.2數組的存儲結構與尋址106
4.4矩陣的壓縮存儲107
4.4.1特殊矩陣的壓縮存儲107
4.4.2稀疏矩陣的壓縮存儲110
4.5擴展與提高112
4.5.1稀疏矩陣的轉置運算112
4.5.2廣義表114
4.6應用實例118
4.6.1發紙牌118
4.6.2八皇后問題119
思想火花——用常識性的思維去思考問題121
習題121
實驗題123
第5章樹和二叉樹125
5.1引言126
5.2樹的邏輯結構127
5.2. 1樹的定義和基本術語127
5.2.2樹的抽像數據類型128
5.2.3樹的遍歷操作定義129
5.3樹的存儲結構130
5.3.1雙親表示法130
5.3.2孩子表示法131
5.3.3孩子兄弟表示法131
5.4二叉樹的邏輯結構133
5.4.1二叉樹的定義133
5.4.2二叉樹的基本性質134
5.4.3二叉樹的抽像數據類型定義136
5.4.4二叉樹的遍歷操作定義137
5.4.5二叉樹的Java接口定義139
5.5二叉樹的存儲結構及實現139
5.5.1順序存儲結構139
5.5.2二叉鍊錶140
5.5.3三叉鍊錶145
5.6森林146
5.6.1森林的邏輯結構146
5.6.2樹、森林與二叉樹的轉換147
5.7□優二叉樹149
5.7.1哈夫曼算法149
5.7 .2哈夫曼編碼152
5.8擴展與提高154
5.8.1二叉樹遍歷的非遞歸算法154
5.8.2線索二叉樹157
5.9應用實例161
5.9.1堆與優先隊列161
5.9.2並查集165
思想火花— —調試程序與魔術表演167
習題168
實驗題169
第6章圖171
6.1引言172
6.2圖的邏輯結構173
6.2.1圖的定義和基本術語173
6.2.2圖的抽像數據類型定義176
6.2.3圖的遍歷操作176
6.2.4圖的Java接口定義178
6.3圖的存儲結構及實現179
6.3.1鄰接矩陣179
6.3.2鄰接表183
6.3.3鄰接矩陣和鄰接表的比較188
6.4□小生成樹188
6.4.1Prim算法189
6.4.2Kruskal算法192
6.5□短路徑196
6.5. 1Dijkstra算法196
6.5.2Floyd算法199
6.6有向無環圖及其應用201
6.6.1AOV網與拓撲排序201
6.6.2AOE網與關鍵路徑204
6.7擴展與提高206
6.7.1圖的其他存儲方法206
6.7. 2圖的連通性208
6.8應用實例210
6.8.1七巧板塗色問題210
6.8.2醫院選址問題211
思想火花——直覺可能是錯誤的213
習題214
實驗題217
第7章查找技術219
7.1引言220
7.1.1查找的基本概念220
7.1.2查找算法的性能221
7.2線性表的查找技術221
7.2.1線性表查找結構的定義221
7.2.2順序查找222
7.2.3折半查找222
7.3樹表的查找技術225
7.3.1二叉排序樹225
7.3.2平衡二叉樹231
7.3.3B樹235
7.4散列表的查找技術239
7.4.1散列查找的基本思想239
7.4.2散列函數的設計240
7.4.3處理衝突的方法242
7.4.4散列查找的性能分析245
7.4.5開散列表與閉散列表的比較246
7.5各種查找方法的比較247
7.6擴展與提高247
7.6.1順序查找的改進——分塊查找247
7.6.2折半查找的改進——插值查找248
7.6.3B樹的改進——B+樹249
思想火花——把注意力集中於主要因素，不要糾纏於噪聲250
習題251
實驗題253
第8章排序技術255
8.1引言256
8.1.1排序的基本概念256
8.1.2排序算法的性能257
8.1.3排序類的定義257
8.2插入排序258
8.2.1直接插入排序258
8.2.2希爾排序260
8.3交換排序261
8.3.1起泡排序261
8.3.2快速排序263
8.4選擇排序266
8.4.1簡單選擇排序266
8.4.2堆排序268
8.5歸併排序273
8.5.1二路歸併排序的遞歸實現273
8.5.2二路歸併排序的非遞歸實現275
8.6各種排序技術的使用277
8.7各種排序方法的比較277
8.8擴展與提高279
8.8.1排序問題的時間下界279
8.8. 2基數排序280
思想火花——學會“盒子以外的思考”283
習題284
實驗題286
附錄A預備知識289
A.1數學術語289
A.2級數求和289
A.3集合290
A.4關係291
附錄BJava語言基本語法293
B.1程序文件結構293
B.2數據類型294
B.3Java編程規範295
B.4控制語句295
B.5函數296
B.6類與對象297
B.7接口298
B. 8異常處理299
附錄C中英文詞彙對照表301
參考文獻305
