Java语言描述数据结构与算法分析（第2版） _生活百科

文章插图
数据结构与算法分析（Java语言描述）（第2版）【Java语言描述数据结构与算法分析（第2版）】《数据结构与算法分析（Java语言描述）（第2版）》是2007年出版的图书，作者是Frank Carrano 。
基本介绍书名：数据结构与算法分析（Java语言描述）（第2版）
ISBN：9787302162698
定价：98元
出版时间：2012.09.10
装帧：平装
印次：1-2
图书简介本书是为数据结构入门课程（通常课号是CS-2）而编写的教材。作者Frank Carrano在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式藉助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、伫列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。书中的“编程提示”给读者额外的编程建议；大量的插图使讲解更形象生动；自测题贯穿各章，书末还给出了答案。本书适合作为数据结构的教学用书。“数据结构”是计算机专业的基础与核心课程之一，也是从事软体开发必不可少的入门和常用知识。程式编写得好不好，很大程度上取决于编程者对数据结构是否熟练地掌握和恰当地运用。由于它不仅重要，而且易学难精，“数据结构”一直都被列入相关专业的研究生入学考试和相关行业的公司招聘考试的重点考查範围。由于“数据结构”这门课程本身的特点，它必须依託于一种程式设计语言才能讲授，否则就成了空中楼阁、纸上谈兵。因此，儘管从抽象和逻辑的角度看来都大同小异，按照所依託的程式设计语言可以把“数据结构”的教材分为不同的版本--诸如Pascal版、C版、C++版以及Java版。除了由于程式设计语言的不同特性而导致的程式实现上的差异，不同版本的“数据结构”教材所讲述的主要内容并无本质区别。因此，初学者可以根据自己已经掌握的或者将作为主要使用的程式设计语言选择相应版本的“数据结构”教材来学习。将来如果换用另一种程式设计语言，也不需要重新学习另一个版本的“数据结构”教材，只需将其作为参考，查阅同样的数据结构是如何用另一种语言实现的即可。这也是为什幺不同版本的“数据结构”教材都有其存在的意义。图书目录引言1第1章 Java类21.1 对象与类21.2 在Java类中使用方法51.3 定义Java类71.3.1 方法定义81.3.2 实参与形参101.3.3 传递实参111.3.4 Name类的定义141.3.5 构造函式161.3.6 toString方法181.3.7 调用其他方法的方法 …181.3.8 返回所属类实例的方法201.3.9 静态域与静态方法201.3.10 方法的重载221.4 枚举类231.5 包26本章小结27练习28项目设计31第2章从已有类创建新类352.1 合成352.1.1 通用类型382.1.2 适配器412.2 继承422.2.1 从构造函式中调用构造函式452.2.2 基类的私有域与私有方法462.2.3 受保护的访问472.2.4 方法的覆盖与重载472.2.5 多重继承522.3 类型兼容性与基类532.3.1 Object类542.3.2 抽象类与抽象方法562.4 多态性58本章小结63练习64项目设计68第3章类的设计703.1 封装703.2 方法的说明723.3 接口763.3.1 编写接口763.3.2 实现接口783.3.3 作为数据类型的接口793.3.4 接口的通用类型803.3.5 Comparable接口803.3.6 扩展接口823.3.7 接口与抽象类833.3.8 符号常量853.4 类的选择863.4.1 类的确定873.4.2 CRC卡片883.5 类的复用91本章小结91练习92项目设计93第4章线性表964.1 ADT线性表说明964.2 使用ADT线性表1034.3 像使用自动售货机一样使用线性表1074.4 Java类库：List接口109本章小结109练习110项目设计112第5章用数组实现线性表1145.1 使用定长数组实现ADT线性表1145.1.1 类比1145.1.2 Java实现1165.2 使用动态扩展数组实现ADT线性表1245.2.1 扩展数组1255.2.2 线性表的新实现1275.3 Java类库：ArrayList与Vector类128 5.4 用数组实现ADT线性表的优缺点132本章小结133练习134项目设计135目录数据结构与算法分析（Java语言描述）（第2版）第6章用鍊表实现线性表1366.1 鍊表1366.1.1 在表头添加来创建鍊表1376.1.2 在表末添加来创建鍊表1386.1.3 在不同位置添加来创建鍊表 …1406.2 使用鍊表实现ADT线性表1426.2.1 私有类Node1426.2.2 数据域与构造函式1446.2.3 选择要实现的核心方法组1456.2.4 线上性表的末端插入元素1466.2.5 线上性表的指定位置插入元素148 6.2.6 私有方法getNodeAt1526.2.7 断言与isEmpty方法1536.2.8 display方法1546.3 测试不完整的实现155本章小结157练习158项目设计159第7章完成线性表的鍊表实现1607.1 从鍊表中删除一个元素1607.2 完成ADT线性表的鍊表实现1627.2.1 方法remove1627.2.2 方法replace1657.2.3 方法getEntry1657.2.4 方法contains1667.2.5 其他方法1667.3 使用具有设定与获取方法的Node类1677.4 表尾引用1707.5 用鍊表实现ADT线性表的优缺点1757.6 Java类库：LinkedList类175本章小结176练习176项目设计177第8章叠代器1798.1 什幺是叠代器1798.2 Iterator接口1808.3 独立类叠代器1868.4 内部类叠代器1898.4.1 基于鍊表实现1908.4.2 基于数组实现1948.5 叠代器方法为何在自己的类中1978.6 ListIterator接口1988.7 基于数组实现ListIterator接口2048.8 Java类库：Iterable接口2118.8.1 Iterable与for-each循环2128.8.2 重温List接口212本章小结213练习213项目设计216第9章算法的效率2189.1 动机2189.2 度量算法的效率2209.3 形式化2269.4 效率的图形表示2299.5 ADT线性表不同实现的效率2329.5.1 基于数组实现2329.5.2 基于鍊表实现2349.5.3 比较上述实现237本章小结238练习238项目设计240第10章递归24310.1 何谓递归24310.2 跟蹤递归方法24810.3 有返回值的递归方法25010.4 递归处理数组25310.5 递归处理鍊表25510.6 递归方法的时间效率25710.6.1 countDown的时间效率25710.6.2 计算xn的时间效率25810.7 困难问题的简单解法25910.8 简单问题的拙劣解法26410.9 尾递归26610.10 协同递归268本章小结268 练习270项目设计271第11章排序入门27511.1 组织用于数组排序的Java方法27611.2 选择排序27711.2.1 叠代选择排序27811.2.2 递归选择排序28011.2.3 选择排序的效率28111.3 插入排序28211.3.1 叠代插入排序28311.3.2 递归插入排序28411.3.3 插入排序的效率28611.3.4 鍊表的插入排序28611.4 希尔排序28911.4.1 Java代码29111.4.2 希尔排序的效率29211.5 算法比较293本章小结293练习293项目设计296第12章快速排序算法29812.1 归併排序29812.1.1 数组的归併29812.1.2 递归归併排序29912.1.3 归併排序的效率30212.1.4 叠代归併排序30312.1.5 Java类库中的归併排序30412.2 快速排序30412.2.1 快速排序的效率30512.2.2 创建划分30512.2.3 快速排序的Java代码30812.2.4 Java类库中的快速排序31112.3 基数排序31112.3.1 基数排序的伪代码31312.3.2 基数排序的效率31312.4 算法比较314本章小结314练习315项目设计316第13章有序表31913.1 ADT有序表的说明31913.2 鍊表实现32313.2.1 add方法32413.2.2 鍊表实现的效率33113.3 使用ADT线性表的实现331本章小结336练习336项目设计337第14章继承与线性表33914.1 使用继承实现有序表33914.2 设计一个基类34214.3 有序表的一种高效实现348本章小结349练习350项目设计350第15章可变对象、不可变对象与可克隆对象35215.1 可变对象与不可变对象35215.1.1 创建唯读类35515.1.2 同伴类35615.2 可克隆对象35815.2.1 克隆数组36415.2.2 克隆鍊表36615.2.3 克隆体的有序表370本章小结373练习373项目设计376第16章查找37716.1 问题描述37716.2 查找无序数组37816.2.1 叠代顺序查找无序数组37816.2.2 递归顺序查找无序数组379 16.2.3 顺序查找数组的效率38116.3 查找有序数组38116.3.1 顺序查找有序数组38116.3.2 折半查找有序数组38216.3.3 Java类库： binarySearch方法38616.3.4 折半查找数组的效率38716.4 查找无序鍊表38816.4.1 叠代顺序查找无序鍊表38816.4.2 递归顺序查找无序鍊表38916.4.3 顺序查找鍊表的效率39016.5 查找有序鍊表39016.5.1 顺序查找有序鍊表39016.5.2 折半查找有序鍊表39116.6 查找方法的选择391本章小结392练习392项目设计394第17章词典39617.1 ADT词典的说明39617.1.1 Java接口39917.1.2 叠代器40017.2 使用ADT词典40217.2.1 电话号码簿40217.2.2 词频40717.2.3 词的索引41117.3 Java类库：Map接口414本章小结415练习415项目设计416第18章词典的实现41818.1 基于数组的实现41818.1.1 基于数组的无序词典41918.1.2 基于数组的有序词典42418.2 基于向量的实现42818.3 基于鍊表的实现43318.3.1 基于鍊表的无序词典43418.3.2 基于鍊表的有序词典434本章小结438练习438项目设计439第19章散列概述44019.1 什幺是散列44019.2 散列函式44219.2.1 计算散列码44319.2.2 将散列码压缩为散列表的索引44519.3 处理冲突44619.3.1 线性探测开放定址44619.3.2 二次探测开放定址45119.3.3 双散列开放定址45119.3.4 开放定址的潜在问题45319.3.5 链地址453本章小结456练习457项目设计458第20章用散列实现词典45920.1 效率45920.1.1 装填因子46020.1.2 开放定址的开销46020.1.3 链地址的开销46220.2 再散列46320.3 处理冲突的各方案比较46420.4 使用散列的词典实现46520.4.1 散列表中的元素46520.4.2 数据域与构造函式46620.4.3 方法getValue、remove 和add46720.4.4 叠代器47320.5 Java类库：类HashMap475本章小结475练习476项目设计476第21章栈47821.1 ADT栈的说明47821.2 利用栈处理代数表达式48121.2.1 检查中缀代数表达式的括弧是否平衡48221.2.2 将中缀表达式转化为后缀表达式48721.2.3 后缀表达式求值49321.2.4 中缀表达式求值49521.3 程式栈49721.4 使用栈代替递归49821.5 Java类库：类Stack501本章小结502练习502项目设计504第22章栈的实现50622.1 基于鍊表的实现50622.2 基于数组的实现50922.3 基于向量的实现513本章小结515练习515项目设计516第23章伫列、双端伫列与优先伫列51723.1 ADT伫列的描述51723.2 使用伫列模拟排队52123.3 使用伫列计算股份销售的资本收益52723.4 Java类库：Queue接口53023.5 ADT双端伫列的描述53023.6 使用双端伫列计算股份销售的资本收益53223.7 ADT优先伫列的描述53423.8 使用优先伫列跟蹤委派任务535本章小结537练习537项目设计539第24章伫列、双端伫列与优先伫列的实现54124.1 基于鍊表的伫列实现54124.2 基于数组的伫列实现54524.2.1 循环数组54624.2.2 含有一个未用位置的循环数组54724.3 基于向量的伫列实现55224.4 基于循环鍊表的伫列实现55424.5 Java类库：AbstractQueue类56024.6 基于双向鍊表的双端伫列实现56024.7 实现优先伫列的可用方法56424.8 Java类库：PriorityQueue类564本章小结565练习566项目设计567第25章树56925.1 树的概念56925.1.1 层次化的组织56925.1.2 树的术语57125.2 树的遍历57425.2.1 二叉树的遍历57525.2.2 树的遍历57625.3 树的Java接口57725.3.1 所有树的接口57725.3.2 二叉树的接口578 25.4 二叉树举例57925.4.1 表达式树58025.4.2 决策树58125.4.3 二叉查找树58525.4.4 堆58725.5 树举例58925.5.1 语法分析树58925.5.2 博弈树590本章小结590练习591项目设计593第26章树的实现59526.1 二叉树的结点59526.1.1 结点的接口59626.1.2 BinaryNode的实现59726.2 ADT二叉树的实现59926.2.1 创建基本二叉树59926.2.2 方法privateSetTree60026.2.3 访问者与修改者方法60326.2.4 计算高度与统计结点60426.2.5 遍历60526.3 表达式二叉树的实现61026.4 树61226.4.1 树的结点61226.4.2 用二叉树表示树613本章小结614练习614项目设计616第27章二叉查找树的实现61727.1 预备知识61727.1.1 二叉查找树接口61827.1.2 重複元素62027.1.3 开始类定义62127.2 查找与检索62227.3 遍历62427.4 插入元素62427.4.1 递归实现62527.4.2 叠代实现62827.5 删除元素63127.5.1 删除叶子结点中的元素63127.5.2 删除有一个孩子的结点中的元素63127.5.3 删除有两个孩子的结点中的元素63127.5.4 删除根结点中的元素63527.5.5 递归实现63527.5.6 叠代实现63927.6 操作的效率64327.6.1 平衡的重要性64427.6.2 插入结点的顺序64427.7 ADT词典的实现645本章小结648练习649项目设计651第28章堆的实现65328.1 再论ADT堆65328.2 用数组表示堆65428.3 插入元素65628.4 删除根65928.5 创建堆66228.6 堆排序664本章小结667练习668项目设计669第29章平衡查找树67029.1 AVL树67029.1.1 单旋转67129.1.2 双旋转67329.1.3 实现细节67629.2 2-3树68129.2.1 2-3树的查找68129.2.2 往2-3树插入元素682 29.2.3 插入期间分裂结点68329.3 2-4树68529.3.1 往2-4树插入元素68529.3.2 比较AVL树、2-3树和2-4树 68629.4 红黑树68729.4.1 红黑树的特性68829.4.2 往红黑树插入元素68929.4.3 Java类库：类TreeMap69329.5 B树693本章小结694练习695项目设计696第30章图69730.1 一些例子与术语69730.1.1 公路地图69730.1.2 航线70030.1.3 迷宫70030.1.4 先修课程70130.1.5 树70130.2 遍历70130.2.1 广度优先遍历70230.2.2 深度优先遍历70430.3 拓扑顺序70530.4 路径70730.4.1 寻找路径70830.4.2 无权图的最短路径70830.4.3 加权图的最短路径71030.5 ADT图的Java接口714本章小结717练习718项目设计720第31章图的实现72231.1 两种实现的概述72231.1.1 邻接矩阵72231.1.2 邻接表72331.2 顶点与边72431.2.1 说明类Vertex72431.2.2 内部类Edge72631.2.3 实现Vertex类72731.3 ADT图的实现73131.3.1 基本操作73131.3.2 图的算法735本章小结737练习738项目设计739附录A Java基础741A.1 引言741A.1.1 应用程式和小程式741A.1.2 对象和类741A.1.3 第一个Java应用程式741A.2 Java基础744A.2.1 标识符744A.2.2 保留字744A.2.3 变数745A.2.4 基本类型745A.2.5 常量746A.2.6 赋值语句746A.2.7 赋值兼容性747A.2.8 类型转换748A.2.9 算术运算符和表达式749A.2.10 括弧和优先规则750A.2.11 自增和自减运算符751A.2.12 特殊赋值运算符752A.2.13 符号常量752A.2.14 Math类753A.3 用键盘和萤幕进行简单的输入和输出754A.3.1 萤幕输出754A.3.2 用Scanner类进行键盘输入755A.4 if-else语句757A.4.1 布尔表达式758 A.4.2 嵌套语句761A.4.3 多重if-else语句763A.4.4 条件运算符（可选）764A.5 switch语句764A.6 枚举766A.7 作用域768A.8 循环769A.8.1 while语句769A.8.2 for语句770A.8.3 do-while语句772A.8.4 关于循环的其他信息773A.9 String类774A.9.1 字元串中的字元775A.9.2 字元串的联接776A.9.3 String方法777A.10 StringBuilder类779A.11 使用Scanner抽取字元串的一部分780A.12 数组783A.12.1 数组形参和返回值785A.12.2 初始化数组786A.12.3 数组索引出界786A.12.4 对数组使用=与==786A.12.5 数组与for-each循环788A.12.6 多维数组788A.12 封装类790附录B 异常处理796B.1 基本的异常处理796B.2 Java类库的异常类799B.3 定义自己的异常类800B.4 複合catch代码块802B.5 finally代码块803B.6 抛出但不捕获异常的方法804B.7 不需要捕获的异常805附录C 档案输入与输出807C.1 概述807C.1.1 数据流807C.1.2 档案的优点807C.1.3 档案的类型808C.1.4 档案名称809C.1.5 包java.io809C.2 使用PrintWriter写文本档案809C.3 读取文本档案812C.3.1 使用Scanner读取文本档案812C.3.2 使用BufferedReader读取文本档案814C.3.3 定义打开数据流的方法816C.4 二进制档案的I/O817C.4.1 使用DataOutputStream写二进制档案817C.4.2 使用DataInputStream读取二进制档案821C.5 File类823C.6 对象串列化824附录D 文档与程式设计风格828D.1 命名变数与类828D.2 缩排828D.3 注释829D.3.1 单行注释829D.3.2 注释块830D.3.3 何时写注释830D.3.4 Java文档注释830D.3.5 运行javadoc832附录E 自测题答案833第1章 Java类第2章从已有类创建新类第3章类的设计第4章线性表第5章用数组实现线性表第6章用鍊表实现线性表第7章完成线性表的鍊表实现第8章叠代器第9章算法的效率第10章递归第11章排序入门第12章快速排序算法第13章有序表第14章继承与线性表第15章可变对象、不可变对象与可克隆对象第16章查找第17章词典第18章词典的实现第19章散列概述第20章用散列实现词典第21章栈第22章栈的实现第23章伫列、双端伫列与优先伫列第24章伫列、双端伫列与优先伫列的实现第25章树第26章树的实现第27章二叉查找树的实现第28章堆的实现第29章平衡查找树第30章图第31章图的实现

Java语言描述 数据结构与算法分析（第2版）

Java语言描述数据结构与算法分析（第2版）