數據結構與抽象（Java語言版）

《數據結構與抽象（Java語言版）》是2014年清華大學出版社出版的圖書，作者是嚴蔚敏。

基本介紹

• 書名：數據結構與抽象（Java語言版）
• 作者：FrankCarrano、Walter Savitch
• 譯者：嚴蔚敏
• ISBN：9787302093756
• 定價：89.00
• 出版社：清華大學出版社
• 出版時間：2014-11-1
• 裝幀：平裝

內容簡介

本書是為數據結構入門課程（通常課號是CS-2）而編寫的教材。作者FrankCarrano和Walter Savitch在編寫過程自始至終特別考慮到了Java與對象，為教師和學生提供了一種精心設計並經過教學實驗的方式藉助Java講授ADT和對象。本書獨特的設計將內容組織為相對較短的章。這種方式使學習更容易，並留出了教學的機動性。本書教給學生如何使用線性表、詞典、棧、佇列等等來組織數據。利用這些數據組織方式，學生們將學到算法設計的相關技術。書中的“編程提示”給讀者額外的編程建議；大量的插圖使講解更形象生動；自測題貫穿各章，書末還給出了答案。本書適合作為數據結構的教學用書。

目錄

第1章Java類 1

1.1對象與類 1

1.2在Java類中使用方法 3

1.2.1引用與別名 4

1.2.2實參與形參 5

1.3定義Java類 6

1.3.1方法定義 7

1.3.2傳遞實參 9

1.3.3Name類的定義 12

1.3.4構造函式 13

1.3.5toString方法 15

1.3.6靜態的域與方法 16

1.4包 17

第2章從已有類創建新類 23

2.1合成 23

2.2繼承 27

2.2.1在構造函式中調用構造函式 30

2.2.2基類的私有域與私有方法 31

2.2.3方法的覆蓋與重載 32

2.2.4保護訪問 35

2.2.5多重繼承 36

2.3類型兼容性與基類 36

2.3.1Object類 37

2.3.2抽象類與抽象方法 39

2.4多態性 40

第3章類的設計 50

3.1封裝 50

3.2方法的說明 52

3.3Java接口 55

3.3.1編寫接口 55

3.3.2實現接口 57

3.3.3作為數據類型的接口 58

3.3.4接口實現中的類型轉換 58

3.3.5擴展接口 59

3.3.6接口中的符號常量 60

3.3.7接口與抽象類的比較 61

3.4類的選擇 63

3.4.1類的確定 64

3.4.2CRC卡片 64

3.5類的復用 66

第4章線性表 70

4.1ADT線性表說明 70

4.2使用ADT線性表 78

4.3Java類庫：List接口 82

4.4使用線性表如同使用自動售貨機 82

第5章用數組實現線性表 87

5.1使用定長數組實現ADT線性表 87

5.1.1類比 87

5.1.2Java實現 89

5.2使用動態擴展數組實現ADT線性表 96

5.2.1擴展數組 97

5.2.2線性表新的實現 98

5.3使用向量實現ADT線性表 100

5.4用數組實現ADT線性表的優缺點 104

5.5Java類庫 104

5.5.1ArrayList類 104

5.5.2Serializable接口 105

第6章用鍊表實現線性表 108

6.1鍊表 108

6.1.1創建一個鍊表 109

6.1.2創建另一個鍊表 111

6.1.3仍創建一個鍊表 113

6.2Node類 116

6.3使用鍊表實現ADT線性表 118

6.3.1線上性表的末端插入元素 119

6.3.2線上性表的指定位置插入元素 122

6.3.3私有方法getNodeAt 125

6.3.4方法remove 126

6.3.5方法replace 128

6.3.6方法getEntry 129

6.3.7方法contains 130

6.3.8其餘方法 130

6.3.9使用具有設定與獲取方法的Node類 131

6.4表尾引用 131

6.5用鍊表實現ADT線性表的優缺點 136

6.6Java類庫：LinkedList類 136

第7章疊代器 139

7.1疊代器是什麼 139

7.1.1基本疊代器 140

7.1.2對ADT進行修改的疊代器方法 143

7.2內部疊代器的實現 145

7.3將疊代器本身實現為一個類 150

7.3.1外部疊代器 153

7.3.2內部類疊代器 154

第8章Java的疊代器接口 160

8.1Iterator接口 160

8.2實現Iterator接口 163

8.2.1基於鍊表實現 163

8.2.2基於數組實現 165

8.3ListIterator接口 168

8.4基於數組實現ListIterator接口 174

8.5Java類庫：重溫ArrayList和LinkedList 181

第9章算法的效率 184

9.1動機 184

9.2度量算法的效率 186

9.3形式化 192

9.4效率的圖形表示 194

9.5ADT線性表不同實現的效率 198

9.5.1基於數組實現 198

9.5.2基於鍊表實現 199

9.5.3比較上述實現 201

第10章遞歸 206

10.1何謂遞歸 206

10.2跟蹤遞歸方法 211

10.3有返回值的遞歸方法 213

10.4遞歸處理數組 216

10.5遞歸處理鍊表 218

10.6遞歸方法的時間效率 220

10.6.1countDown的時間效率 220

10.6.2計算xn的時間效率 222

10.7困難問題的簡單解法 223

10.8簡單問題的拙劣解法 228

10.9尾遞歸 230

10.10協同遞歸 232

第11章排序入門 238

11.1選擇排序 239

11.1.1疊代選擇排序 240

11.1.2遞歸選擇排序 242

11.1.3選擇排序的效率 243

11.2插入排序 243

11.2.1疊代插入排序 244

11.2.2遞歸插入排序 246

11.2.3插入排序的效率 248

11.2.4鍊表的插入排序 248

11.3希爾排序 251

11.3.1Java代碼 253

11.3.2希爾排序的效率 254

11.4算法比較 255

第12章更快的排序算法 259

12.1歸併排序 259

12.1.1數組的歸併 259

12.1.2遞歸歸併排序 260

12.1.3歸併排序的效率 262

12.1.4疊代歸併排序 264

12.1.5Java類庫中的歸併排序 264

12.2快速排序 265

12.2.1快速排序的效率 265

12.2.2創建劃分 266

12.2.3快速排序的Java代碼 268

12.2.4Java類庫中的快速排序 272

12.3基數排序 272

12.3.1基數排序的偽代碼 274

12.3.2基數排序的效率 274

12.4算法比較 275

第13章有序表 280

13.1ADT有序表的說明 280

13.2鍊表實現 284

13.2.1add方法 285

13.2.2鍊表實現的效率 291

13.3使用ADT線性表的實現 292

第14章繼承與線性表 299

14.1使用繼承實現有序表 299

14.2基類的設計 302

14.3有序表的一種高效實現 306

第15章可變對象、不可變對象及可克隆對象 310

15.1可變對象與不可變對象 310

15.1.1同伴類 313

15.1.2使用繼承構建同伴類 315

15.2可克隆對象 317

15.3克隆體的有序表 323

15.4克隆數組 325

15.5克隆鍊表 327

第16章查找 334

16.1問題描述 334

16.2查找無序數組 335

16.2.1疊代順序查找無序數組 335

16.2.2遞歸順序查找無序數組 336

16.2.3順序查找數組的效率 338

16.3查找有序數組 338

16.3.1順序查找有序數組 338

16.3.2折半查找有序數組 339

16.3.3Java類庫：方法binarySearch 343

16.3.4折半查找數組的效率 343

16.4查找無序鍊表 345

16.4.1疊代順序查找無序鍊表 345

16.4.2遞歸順序查找無序鍊表 346

16.4.3順序查找鍊表的效率 347

16.5查找有序鍊表 347

16.5.1順序查找有序鍊表 347

16.5.2折半查找有序鍊表 348

16.6查找方法的選擇 348

第17章詞典 352

17.1ADT詞典的說明 352

17.1.1Java接口 355

17.1.2疊代器 356

17.2使用ADT詞典 357

17.2.1電話號碼簿 357

17.2.2詞頻 361

17.2.3詞的索引 363

17.3Java類庫：Map接口 365

第18章詞典的實現 368

18.1基於數組的實現 368

18.1.1元素 369

18.1.2基於數組的無序詞典 370

18.1.3基於數組的有序詞典 371

18.2基於向量的實現 375

18.3基於鍊表的實現 377

18.3.1元素 377

18.3.2基於鍊表的無序詞典 378

18.3.3基於鍊表的有序詞典 379

第19章用散列實現詞典 385

19.1什麼是散列 386

19.2散列函式 388

19.2.1計算散列碼 388

19.2.2將散列碼壓縮為散列表的索引 391

19.3處理衝突 392

19.3.1線性探測開放定址 392

19.3.2二次探測開放定址 396

19.3.3雙散列開放定址 397

19.3.4開放定址的潛在問題 398

19.3.5鏈地址 398

19.4效率 401

19.4.1裝填因子 401

19.4.2開放定址的開銷 402

19.4.3鏈地址的開銷 403

19.5再散列 404

19.6處理衝突的各方案比較 405

19.7使用散列的詞典實現 406

19.7.1散列表中的元素 406

19.7.2數據域與構造函式 407

19.7.3方法getValue、remove及add 408

19.7.4疊代器 415

19.8Java類庫：類HashMap 416

第20章棧 421

20.1ADT棧的說明 421

20.2利用棧處理代數表達式 425

20.2.1檢查中綴代數表達式中括弧是否平衡 425

20.2.2將中綴表達式轉化為後綴表達式 430

20.2.3後綴表達式求值 437

20.2.4中綴表達式求值 439

20.3程式棧 441

20.4使用棧代替遞歸 443

20.5Java類庫：類Stack 445

第21章棧的實現 449

21.1基於鍊表的實現 449

21.2基於數組的實現 452

21.3基於向量的實現 456

第22章佇列、雙端佇列及優先佇列 460

22.1ADT佇列的說明 460

22.2使用佇列模擬排隊 464

22.3使用佇列計算股份銷售的資本收益 470

22.4ADT雙端佇列的說明 473

22.5使用雙端佇列計算股份銷售的資本收益 475

22.6ADT優先佇列的說明 476

22.7使用優先佇列計算股份銷售的資本收益 477

第23章佇列、雙端佇列及優先佇列的實現 481

23.1基於鍊表實現佇列 481

23.2基於數組實現佇列 485

23.2.1循環數組 485

23.2.2含有一個不用位置的循環數組 488

23.3基於向量實現佇列 493

23.4基於循環鍊表實現佇列 495

23.5基於雙向鍊表實現雙端佇列 500

23.6實現優先佇列可用方法 504

第24章樹 507

24.1樹的概念 507

24.1.1層次化的組織 507

24.1.2樹的術語 509

24.2樹的遍歷 513

24.2.1二叉樹的遍歷 513

24.2.2樹的遍歷 515

24.3樹的Java接口 516

24.3.1所有樹的接口 516

24.3.2二叉樹接口 517

24.4二叉樹舉例 519

24.4.1表達式樹 519

24.4.2決策樹 521

24.4.3二叉查找樹 524

24.4.4堆 526

24.5樹舉例 528

24.5.1語法分析樹 528

24.5.2博弈樹 530

第25章樹的實現 534

25.1二叉樹的節點 534

25.1.1節點的接口 535

25.1.2BinaryNode的實現 536

25.2ADT二叉樹的實現 537

25.2.1創建基本二叉樹 537

25.2.2方法privateSetTree 539

25.2.3訪問者與修改者方法 542

25.2.4計算高度與統計節點 543

25.2.5遍歷 544

25.3表達式二叉樹的實現 549

25.4樹 550

25.4.1樹的節點 550

25.4.2用二叉樹表示樹 551

第26章二叉查找樹的實現 555

26.1預備知識 555

26.1.1二叉查找樹接口 556

26.1.2相同的元素 558

26.1.3開始類定義 559

26.2查找與提取 560

26.3遍歷 561

26.4插入元素 561

26.4.1疊代實現 562

26.4.2遞歸實現 564

26.5刪除元素 569

26.5.1刪除葉子節點中的元素 569

26.5.2刪除有一個孩子的節點中的元素 570

26.5.3刪除有兩個孩子的節點中的元素 570

26.5.4刪除根節點中的元素 573

26.5.5疊代實現 574

26.5.6遞歸實現 579

26.6操作的效率 582

26.6.1平衡的重要性 583

26.6.2插入節點的順序 584

26.7ADT詞典的實現 585

第27章堆的實現 591

27.1再論ADT堆 591

27.2用數組表示堆 592

27.3插入元素 594

27.4刪除根 597

27.5創建堆 600

27.6堆排序 602

第28章平衡查找樹 606

28.1AVL樹 606

28.1.1單旋轉 607

28.1.2雙旋轉 608

28.1.3實現細節 612

28.22-3樹 615

28.2.12-3樹的查找 616

28.2.2向2-3樹插入元素 617

28.2.3插入期間分裂節點 619

28.32-4樹 620

28.3.1向2-4樹插入元素 620

28.3.2比較AVL樹、2-3樹及2-4樹 622

28.4紅黑樹 623

28.4.1紅黑樹的特性 624

28.4.2向紅黑樹插入元素 625

28.4.3Java類庫：類TreeMap 629

28.5B樹 629

第29章圖 633

29.1一些例子與術語 633

29.1.1公路地圖 633

29.1.2航線 636

29.1.3迷宮 636

29.1.4先修課程 637

29.1.5樹 637

29.2遍歷 638

29.2.1廣度優先遍歷 639

29.2.2深度優先遍歷 639

29.3拓撲順序 642

29.4路徑 644

29.4.1尋找路徑 644

29.4.2無權圖中的最短路徑 644

29.4.3帶權圖中的最短路徑 647

29.5ADT圖的Java接口 650

第30章圖的實現 657

30.1兩種實現的概述 657

30.1.1鄰接矩陣 657

30.1.2鄰接表 658

30.2頂點與邊 659

30.2.1說明類Vertex 659

30.2.2類Edge 661

30.2.3實現類Vertex 663

30.3ADT圖的實現 664

30.3.1基本操作 665

30.3.2圖的算法 668

附錄AJava基礎 673

附錄B異常處理 723

附錄C檔案輸入與輸出 732

附錄D文檔與程式設計風格 748

附錄E自測題答案 754