數(shù)據結構與抽象：Java語言版

第1章  Java類 11.1  對象與類 11.2  在Java類中使用方法 31.2.1  引用與別名 41.2.2  實參與形參 51.3  定義Java類 61.3.1  方法定義 71.3.2  傳遞實參 91.3.3  Name類的定義 121.3.4  構造函數(shù) 131.3.5  toString方法 151.3.6  靜態(tài)的域與方法 161.4  包 17
第2章  從已有類創(chuàng)建新類 232.1  合成 232.2  繼承 272.2.1  在構造函數(shù)中調用構造函數(shù) 302.2.2  基類的私有域與私有方法 312.2.3  方法的覆蓋與重載 322.2.4  保護訪問 352.2.5  多重繼承 362.3  類型兼容性與基類 362.3.1  Object類 372.3.2  抽象類與抽象方法 392.4  多態(tài)性 40
第3章  類的設計 503.1  封裝 503.2  方法的說明 523.3  Java接口 553.3.1  編寫接口 553.3.2  實現(xiàn)接口 573.3.3  作為數(shù)據類型的接口 583.3.4  接口實現(xiàn)中的類型轉換 583.3.5  擴展接口 593.3.6  接口中的符號常量 603.3.7  接口與抽象類的比較 613.4  類的選擇 633.4.1  類的確定 643.4.2  CRC卡片 643.5  類的復用 66
第4章  線性表 704.1  ADT線性表說明 704.2  使用ADT線性表 784.3  Java類庫：List接口 824.4  使用線性表如同使用自動售貨機 82
第5章  用數(shù)組實現(xiàn)線性表 875.1  使用定長數(shù)組實現(xiàn)ADT線性表 875.1.1  類比 875.1.2  Java實現(xiàn) 895.2  使用動態(tài)擴展數(shù)組實現(xiàn)ADT線性表 965.2.1  擴展數(shù)組 975.2.2  線性表新的實現(xiàn) 985.3  使用向量實現(xiàn)ADT線性表 1005.4  用數(shù)組實現(xiàn)ADT線性表的優(yōu)缺點 1045.5  Java類庫 1045.5.1  ArrayList類 1045.5.2  Serializable接口 105
第6章  用鏈表實現(xiàn)線性表 1086.1  鏈表 1086.1.1  創(chuàng)建一個鏈表 1096.1.2  創(chuàng)建另一個鏈表 1116.1.3  仍創(chuàng)建一個鏈表 1136.2  Node類 1166.3  使用鏈表實現(xiàn)ADT線性表 1186.3.1  在線性表的末端插入元素 1196.3.2  在線性表的指定位置插入元素 1226.3.3  私有方法getNodeAt 1256.3.4  方法remove 1266.3.5  方法replace 1286.3.6  方法getEntry 1296.3.7  方法contains 1306.3.8  其余方法 1306.3.9  使用具有設置與獲取方法的Node類 1316.4  表尾引用 1316.5  用鏈表實現(xiàn)ADT線性表的優(yōu)缺點 1366.6  Java類庫：LinkedList類 136
第7章  迭代器 1397.1  迭代器是什么 1397.1.1  基本迭代器 1407.1.2  對ADT進行修改的迭代器方法 1437.2  內部迭代器的實現(xiàn) 1457.3  將迭代器本身實現(xiàn)為一個類 1507.3.1  外部迭代器 1537.3.2  內部類迭代器 154
第8章  Java的迭代器接口 1608.1  Iterator接口 1608.2  實現(xiàn)Iterator接口 1638.2.1  基于鏈表實現(xiàn) 1638.2.2  基于數(shù)組實現(xiàn) 1658.3  ListIterator接口 1688.4  基于數(shù)組實現(xiàn)ListIterator接口 1748.5  Java類庫：重溫ArrayList和LinkedList 181
第9章  算法的效率 1849.1  動機 1849.2  度量算法的效率 1869.3  形式化 1929.4  效率的圖形表示 1949.5  ADT線性表不同實現(xiàn)的效率 1989.5.1  基于數(shù)組實現(xiàn) 1989.5.2  基于鏈表實現(xiàn) 1999.5.3  比較上述實現(xiàn) 201第10章  遞歸 20610.1  何謂遞歸 20610.2  跟蹤遞歸方法 21110.3  有返回值的遞歸方法 21310.4  遞歸處理數(shù)組 21610.5  遞歸處理鏈表 21810.6  遞歸方法的時間效率 22010.6.1  countDown的時間效率 22010.6.2  計算xn的時間效率 22210.7  困難問題的簡單解法 22310.8  簡單問題的拙劣解法 22810.9  尾遞歸 23010.10  協(xié)同遞歸 232
第11章  排序入門 23811.1  選擇排序 23911.1.1  迭代選擇排序 24011.1.2  遞歸選擇排序 24211.1.3  選擇排序的效率 24311.2  插入排序 24311.2.1  迭代插入排序 24411.2.2  遞歸插入排序 24611.2.3  插入排序的效率 24811.2.4  鏈表的插入排序 24811.3  希爾排序 25111.3.1  Java代碼 25311.3.2  希爾排序的效率 25411.4  算法比較 255
第12章  更快的排序算法 25912.1  歸并排序 25912.1.1  數(shù)組的歸并 25912.1.2  遞歸歸并排序 26012.1.3  歸并排序的效率 26212.1.4  迭代歸并排序 26412.1.5  Java類庫中的歸并排序 26412.2  快速排序 26512.2.1  快速排序的效率 26512.2.2  創(chuàng)建劃分 26612.2.3  快速排序的Java代碼 26812.2.4  Java類庫中的快速排序 27212.3  基數(shù)排序 27212.3.1  基數(shù)排序的偽代碼 27412.3.2  基數(shù)排序的效率 27412.4  算法比較 275
第13章  有序表 28013.1  ADT有序表的說明 28013.2  鏈表實現(xiàn) 28413.2.1  add方法 28513.2.2  鏈表實現(xiàn)的效率 29113.3  使用ADT線性表的實現(xiàn) 292
第14章  繼承與線性表 29914.1  使用繼承實現(xiàn)有序表 29914.2  基類的設計 30214.3  有序表的一種高效實現(xiàn) 306
第15章  可變對象、不可變對象及可克隆對象 31015.1  可變對象與不可變對象 31015.1.1  同伴類 31315.1.2  使用繼承構建同伴類 31515.2  可克隆對象 31715.3  克隆體的有序表 32315.4  克隆數(shù)組 32515.5  克隆鏈表 327
第16章  查找 33416.1  問題描述 33416.2  查找無序數(shù)組 33516.2.1  迭代順序查找無序數(shù)組 33516.2.2  遞歸順序查找無序數(shù)組 33616.2.3  順序查找數(shù)組的效率 33816.3  查找有序數(shù)組 33816.3.1  順序查找有序數(shù)組 33816.3.2  折半查找有序數(shù)組 33916.3.3  Java類庫：方法binarySearch 34316.3.4  折半查找數(shù)組的效率 34316.4  查找無序鏈表 34516.4.1  迭代順序查找無序鏈表 34516.4.2  遞歸順序查找無序鏈表 34616.4.3  順序查找鏈表的效率 34716.5  查找有序鏈表 34716.5.1  順序查找有序鏈表 34716.5.2  折半查找有序鏈表 34816.6  查找方法的選擇 348
第17章  詞典 35217.1  ADT詞典的說明 35217.1.1  Java接口 35517.1.2  迭代器 35617.2  使用ADT詞典 35717.2.1  電話號碼簿 35717.2.2  詞頻 36117.2.3  詞的索引 36317.3  Java類庫：Map接口 365
第18章  詞典的實現(xiàn) 36818.1  基于數(shù)組的實現(xiàn) 36818.1.1  元素 36918.1.2  基于數(shù)組的無序詞典 37018.1.3  基于數(shù)組的有序詞典 37118.2  基于向量的實現(xiàn) 37518.3  基于鏈表的實現(xiàn) 37718.3.1  元素 37718.3.2  基于鏈表的無序詞典 37818.3.3  基于鏈表的有序詞典 379
第19章  用散列實現(xiàn)詞典 38519.1  什么是散列 38619.2  散列函數(shù) 38819.2.1  計算散列碼 38819.2.2  將散列碼壓縮為散列表的索引 39119.3  處理沖突 39219.3.1  線性探測開放定址 39219.3.2  二次探測開放定址 39619.3.3  雙散列開放定址 39719.3.4  開放定址的潛在問題 39819.3.5  鏈地址 39819.4  效率 40119.4.1  裝填因子 40119.4.2  開放定址的開銷 40219.4.3  鏈地址的開銷 40319.5  再散列 40419.6  處理沖突的各方案比較 40519.7  使用散列的詞典實現(xiàn) 40619.7.1  散列表中的元素 40619.7.2  數(shù)據域與構造函數(shù) 40719.7.3  方法getValue、remove及add 40819.7.4  迭代器 41519.8  Java類庫：類HashMap 416
第20章  棧 42120.1  ADT棧的說明 42120.2  利用棧處理代數(shù)表達式 42520.2.1  檢查中綴代數(shù)表達式中括號是否平衡 42520.2.2  將中綴表達式轉化為后綴表達式 43020.2.3  后綴表達式求值 43720.2.4  中綴表達式求值 43920.3  程序棧 44120.4  使用棧代替遞歸 44320.5  Java類庫：類Stack 445
第21章  棧的實現(xiàn) 44921.1  基于鏈表的實現(xiàn) 44921.2  基于數(shù)組的實現(xiàn) 45221.3  基于向量的實現(xiàn) 456
第22章  隊列、雙端隊列及優(yōu)先隊列 46022.1  ADT隊列的說明 46022.2  使用隊列模擬排隊 46422.3  使用隊列計算股份銷售的資本收益 47022.4  ADT雙端隊列的說明 47322.5  使用雙端隊列計算股份銷售的資本收益 47522.6  ADT優(yōu)先隊列的說明 47622.7  使用優(yōu)先隊列計算股份銷售的資本收益 477
第23章  隊列、雙端隊列及優(yōu)先隊列的實現(xiàn) 48123.1  基于鏈表實現(xiàn)隊列 48123.2  基于數(shù)組實現(xiàn)隊列 48523.2.1  循環(huán)數(shù)組 48523.2.2  含有一個不用位置的循環(huán)數(shù)組 48823.3  基于向量實現(xiàn)隊列 49323.4  基于循環(huán)鏈表實現(xiàn)隊列 49523.5  基于雙向鏈表實現(xiàn)雙端隊列 50023.6  實現(xiàn)優(yōu)先隊列可用方法 504
第24章  樹 50724.1  樹的概念 50724.1.1  層次化的組織 50724.1.2  樹的術語 50924.2  樹的遍歷 51324.2.1  二叉樹的遍歷 51324.2.2  樹的遍歷 51524.3  樹的Java接口 51624.3.1  所有樹的接口 51624.3.2  二叉樹接口 51724.4  二叉樹舉例 51924.4.1  表達式樹 51924.4.2  決策樹 52124.4.3  二叉查找樹 52424.4.4  堆 52624.5  樹舉例 52824.5.1  語法分析樹 52824.5.2  博弈樹 530
第25章  樹的實現(xiàn) 53425.1  二叉樹的節(jié)點 53425.1.1  節(jié)點的接口 53525.1.2  BinaryNode的實現(xiàn) 53625.2  ADT二叉樹的實現(xiàn) 53725.2.1  創(chuàng)建基本二叉樹 53725.2.2  方法privateSetTree 53925.2.3  訪問者與修改者方法 54225.2.4  計算高度與統(tǒng)計節(jié)點 54325.2.5  遍歷 54425.3  表達式二叉樹的實現(xiàn) 54925.4  樹 55025.4.1  樹的節(jié)點 55025.4.2  用二叉樹表示樹 551
第26章  二叉查找樹的實現(xiàn) 55526.1  預備知識 55526.1.1  二叉查找樹接口 55626.1.2  相同的元素 55826.1.3  開始類定義 55926.2  查找與提取 56026.3  遍歷 56126.4  插入元素 56126.4.1  迭代實現(xiàn) 56226.4.2  遞歸實現(xiàn) 56426.5  刪除元素 56926.5.1  刪除葉子節(jié)點中的元素 56926.5.2  刪除有一個孩子的節(jié)點中的元素 57026.5.3  刪除有兩個孩子的節(jié)點中的元素 57026.5.4  刪除根節(jié)點中的元素 57326.5.5  迭代實現(xiàn) 57426.5.6  遞歸實現(xiàn) 57926.6  操作的效率 58226.6.1  平衡的重要性 58326.6.2  插入節(jié)點的順序 58426.7  ADT詞典的實現(xiàn) 585
第27章  堆的實現(xiàn) 59127.1  再論ADT堆 59127.2  用數(shù)組表示堆 59227.3  插入元素 594