Java语言版数据结构与抽象 _生活百科

文章插图
数据结构与抽象（Java语言版）【Java语言版数据结构与抽象】《数据结构与抽象（Java语言版）》是2014年清华大学出版社出版的图书，作者是严蔚敏。
基本介绍书名：数据结构与抽象（Java语言版）
作者：FrankCarrano、Walter Savitch
译者：严蔚敏
ISBN：9787302093756
定价：89.00
出版社：清华大学出版社
出版时间：2014-11-1
装帧：平装
内容简介本书是为数据结构入门课程（通常课号是CS-2）而编写的教材。作者FrankCarrano和Walter Savitch在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式藉助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、伫列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。书中的“编程提示”给读者额外的编程建议；大量的插图使讲解更形象生动；自测题贯穿各章，书末还给出了答案。本书适合作为数据结构的教学用书。目录第1章Java类 11.1对象与类 11.2在Java类中使用方法 31.2.1引用与别名 41.2.2实参与形参 51.3定义Java类 61.3.1方法定义 71.3.2传递实参 91.3.3Name类的定义 121.3.4构造函式 131.3.5toString方法 151.3.6静态的域与方法 161.4包 17第2章从已有类创建新类 232.1合成 232.2继承 272.2.1在构造函式中调用构造函式 302.2.2基类的私有域与私有方法 312.2.3方法的覆盖与重载 322.2.4保护访问 352.2.5多重继承 362.3类型兼容性与基类 362.3.1Object类 372.3.2抽象类与抽象方法 392.4多态性 40第3章类的设计 503.1封装 503.2方法的说明 523.3Java接口 553.3.1编写接口 553.3.2实现接口 573.3.3作为数据类型的接口 583.3.4接口实现中的类型转换 583.3.5扩展接口 593.3.6接口中的符号常量 603.3.7接口与抽象类的比较 613.4类的选择 633.4.1类的确定 643.4.2CRC卡片 643.5类的复用 66第4章线性表 704.1ADT线性表说明 704.2使用ADT线性表 784.3Java类库：List接口 824.4使用线性表如同使用自动售货机 82第5章用数组实现线性表 875.1使用定长数组实现ADT线性表 875.1.1类比 875.1.2Java实现 895.2使用动态扩展数组实现ADT线性表 965.2.1扩展数组 975.2.2线性表新的实现 985.3使用向量实现ADT线性表 1005.4用数组实现ADT线性表的优缺点 1045.5Java类库 1045.5.1ArrayList类 1045.5.2Serializable接口 105第6章用鍊表实现线性表 1086.1鍊表 1086.1.1创建一个鍊表 1096.1.2创建另一个鍊表 1116.1.3仍创建一个鍊表 1136.2Node类 1166.3使用鍊表实现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用鍊表实现ADT线性表的优缺点 1366.6Java类库：LinkedList类 136第7章叠代器 1397.1叠代器是什幺 1397.1.1基本叠代器 1407.1.2对ADT进行修改的叠代器方法 1437.2内部叠代器的实现 1457.3将叠代器本身实现为一个类 1507.3.1外部叠代器 1537.3.2内部类叠代器 154第8章Java的叠代器接口 1608.1Iterator接口 1608.2实现Iterator接口 1638.2.1基于鍊表实现 1638.2.2基于数组实现 1658.3ListIterator接口 1688.4基于数组实现ListIterator接口 1748.5Java类库：重温ArrayList和LinkedList 181第9章算法的效率 1849.1动机 1849.2度量算法的效率 1869.3形式化 1929.4效率的图形表示 1949.5ADT线性表不同实现的效率 1989.5.1基于数组实现 1989.5.2基于鍊表实现 1999.5.3比较上述实现 201第10章递归 20610.1何谓递归 20610.2跟蹤递归方法 21110.3有返回值的递归方法 21310.4递归处理数组 21610.5递归处理鍊表 21810.6递归方法的时间效率 22010.6.1countDown的时间效率 22010.6.2计算xn的时间效率 22210.7困难问题的简单解法 22310.8简单问题的拙劣解法 228 10.9尾递归 23010.10协同递归 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.1Java代码 25311.3.2希尔排序的效率 25411.4算法比较 255第12章更快的排序算法 25912.1归併排序 25912.1.1数组的归併 25912.1.2递归归併排序 26012.1.3归併排序的效率 26212.1.4叠代归併排序 26412.1.5Java类库中的归併排序 26412.2快速排序 26512.2.1快速排序的效率 26512.2.2创建划分 26612.2.3快速排序的Java代码 26812.2.4Java类库中的快速排序 27212.3基数排序 27212.3.1基数排序的伪代码 27412.3.2基数排序的效率 27412.4算法比较 275第13章有序表 28013.1ADT有序表的说明 28013.2鍊表实现 28413.2.1add方法 28513.2.2鍊表实现的效率 29113.3使用ADT线性表的实现 292第14章继承与线性表 29914.1使用继承实现有序表 29914.2基类的设计 30214.3有序表的一种高效实现 306第15章可变对象、不可变对象及可克隆对象 31015.1可变对象与不可变对象 31015.1.1同伴类 31315.1.2使用继承构建同伴类 31515.2可克隆对象 31715.3克隆体的有序表 32315.4克隆数组 32515.5克隆鍊表 327第16章查找 33416.1问题描述 33416.2查找无序数组 33516.2.1叠代顺序查找无序数组 33516.2.2递归顺序查找无序数组 33616.2.3顺序查找数组的效率 33816.3查找有序数组 33816.3.1顺序查找有序数组 33816.3.2折半查找有序数组 33916.3.3Java类库：方法binarySearch 34316.3.4折半查找数组的效率 34316.4查找无序鍊表 34516.4.1叠代顺序查找无序鍊表 34516.4.2递归顺序查找无序鍊表 34616.4.3顺序查找鍊表的效率 34716.5查找有序鍊表 347 16.5.1顺序查找有序鍊表 34716.5.2折半查找有序鍊表 34816.6查找方法的选择 348第17章词典 35217.1ADT词典的说明 35217.1.1Java接口 35517.1.2叠代器 35617.2使用ADT词典 35717.2.1电话号码簿 35717.2.2词频 36117.2.3词的索引 36317.3Java类库：Map接口 365第18章词典的实现 36818.1基于数组的实现 36818.1.1元素 36918.1.2基于数组的无序词典 37018.1.3基于数组的有序词典 37118.2基于向量的实现 37518.3基于鍊表的实现 37718.3.1元素 37718.3.2基于鍊表的无序词典 37818.3.3基于鍊表的有序词典 379第19章用散列实现词典 38519.1什幺是散列 38619.2散列函式 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使用散列的词典实现 40619.7.1散列表中的元素 40619.7.2数据域与构造函式 40719.7.3方法getValue、remove及add 40819.7.4叠代器 41519.8Java类库：类HashMap 416第20章栈 42120.1ADT栈的说明 42120.2利用栈处理代数表达式 42520.2.1检查中缀代数表达式中括弧是否平衡 42520.2.2将中缀表达式转化为后缀表达式 43020.2.3后缀表达式求值 43720.2.4中缀表达式求值 43920.3程式栈 44120.4使用栈代替递归 44320.5Java类库：类Stack 445第21章栈的实现 44921.1基于鍊表的实现 44921.2基于数组的实现 45221.3基于向量的实现 456第22章伫列、双端伫列及优先伫列 46022.1ADT伫列的说明 46022.2使用伫列模拟排队 46422.3使用伫列计算股份销售的资本收益 47022.4ADT双端伫列的说明 47322.5使用双端伫列计算股份销售的资本收益 475 22.6ADT优先伫列的说明 47622.7使用优先伫列计算股份销售的资本收益 477第23章伫列、双端伫列及优先伫列的实现 48123.1基于鍊表实现伫列 48123.2基于数组实现伫列 48523.2.1循环数组 48523.2.2含有一个不用位置的循环数组 48823.3基于向量实现伫列 49323.4基于循环鍊表实现伫列 49523.5基于双向鍊表实现双端伫列 50023.6实现优先伫列可用方法 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章树的实现 53425.1二叉树的节点 53425.1.1节点的接口 53525.1.2BinaryNode的实现 53625.2ADT二叉树的实现 53725.2.1创建基本二叉树 53725.2.2方法privateSetTree 53925.2.3访问者与修改者方法 54225.2.4计算高度与统计节点 54325.2.5遍历 54425.3表达式二叉树的实现 54925.4树 55025.4.1树的节点 55025.4.2用二叉树表示树 551第26章二叉查找树的实现 55526.1预备知识 55526.1.1二叉查找树接口 55626.1.2相同的元素 55826.1.3开始类定义 55926.2查找与提取 56026.3遍历 56126.4插入元素 56126.4.1叠代实现 56226.4.2递归实现 56426.5删除元素 56926.5.1删除叶子节点中的元素 56926.5.2删除有一个孩子的节点中的元素 57026.5.3删除有两个孩子的节点中的元素 57026.5.4删除根节点中的元素 57326.5.5叠代实现 57426.5.6递归实现 57926.6操作的效率 58226.6.1平衡的重要性 58326.6.2插入节点的顺序 58426.7ADT词典的实现 585第27章堆的实现 59127.1再论ADT堆 59127.2用数组表示堆 59227.3插入元素 594 27.4删除根 59727.5创建堆 60027.6堆排序 602第28章平衡查找树 60628.1AVL树 60628.1.1单旋转 60728.1.2双旋转 60828.1.3实现细节 61228.22-3树 61528.2.12-3树的查找 61628.2.2向2-3树插入元素 61728.2.3插入期间分裂节点 61928.32-4树 62028.3.1向2-4树插入元素 62028.3.2比较AVL树、2-3树及2-4树 62228.4红黑树 62328.4.1红黑树的特性 62428.4.2向红黑树插入元素 62528.4.3Java类库：类TreeMap 62928.5B树 629第29章图 63329.1一些例子与术语 63329.1.1公路地图 63329.1.2航线 63629.1.3迷宫 63629.1.4先修课程 63729.1.5树 63729.2遍历 63829.2.1广度优先遍历 63929.2.2深度优先遍历 63929.3拓扑顺序 64229.4路径 64429.4.1寻找路径 64429.4.2无权图中的最短路径 64429.4.3带权图中的最短路径 64729.5ADT图的Java接口 650第30章图的实现 65730.1两种实现的概述 65730.1.1邻接矩阵 65730.1.2邻接表 65830.2顶点与边 65930.2.1说明类Vertex 65930.2.2类Edge 66130.2.3实现类Vertex 66330.3ADT图的实现 66430.3.1基本操作 66530.3.2图的算法 668附录AJava基础 673附录B异常处理 723附录C档案输入与输出 732附录D文档与程式设计风格 748附录E自测题答案 754

Java语言版 数据结构与抽象

Java语言版数据结构与抽象