Java06标准类库与常用算法.ppt

第6章标准类库与常用算法 陆雪松生物医学工程学院 2020 3 14 第6章标准类库与常用算法 2of48 主要内容 数据结构核心语言包 java lang 工具包 java util 递归算法排序算法 2020 3 14 第6章标准类库与常用算法 3of48 数据结构 使用计算机求解现实世界问题的步骤 首先需要对问题进行数学抽象 使用数学语言对现实问题加以描述称为数学建模 得到数学模型然后将数学模型化为计算机算法和数据结构最后使用计算机语言进行程序设计 得出问题的答案 2020 3 14 第6章标准类库与常用算法 4of48 数据结构 各种数据组织形式及其相关操作方式的集合 包括线性结构和非线性结构线性结构的元素之间存在确定的物理顺序关系而非线性结构的元素之间不一定存在确定的物理顺序 2020 3 14 第6章标准类库与常用算法 5of48 数据结构 2 数据的逻辑结构描述的是元素之间的逻辑关系数据的逻辑结构在计算机存储空间中的实现称为数据的物理结构 常见的数据结构又可以细分为 顺序表 链表 栈 队列 哈希表 树和图等 2020 3 14 第6章标准类库与常用算法 6of48 算法 算法是解决特定问题的步骤 即 计算与法则 具有以下5个特性 输入 包含输入数据 输出 包含输出数据 有穷 由有限条指令组成 确定 每条指令有确切的含义 对于相同的输入数据得到相同的输出结果 可行 在有限步内实现输出 描述算法可以使用自然语言 框图 伪代码或程序设计语言等使用时间复杂度和空间复杂度来度量算法的效率 2020 3 14 第6章标准类库与常用算法 7of48 误差 由算法得出计算结果的过程中步步都可能存在误差计算结果只是现实世界模型的近似值 在建立数学模型时可能由于抽象方法不很科学 会出现第一种误差 称为模型误差 数学模型中用到的一些参数大多数情况下是由观测得来的 所以也会出现误差 称为观测误差 由电脑计算出来的结果与模型的准确值之间也存在误差 称为截断误差 当计算当中对数值位数进行舍入时也存在误差 称为舍入误差 2020 3 14 第6章标准类库与常用算法 8of48 衡量算法的误差幅度 绝对误差 即准确值与近似值之差相对误差 即准确值与近似值的差值除以准确值 例5 1 5 2说明了算法与误差的关系 2020 3 14 第6章标准类库与常用算法 9of48 核心语言包 java lang ObjectClassSystemMath基本数据类型类StringBuilder 2020 3 14 第6章标准类库与常用算法 10of48 Object类 在Java中 object类是所有类的祖先 即不管是Java系统所提供的标准类 还是用户自行编写的类 它们都是从object类直接或间接继承而来 当编程者在定义一个类时若没有使用关键字extends指明它的父类 则编译器认为该类从object类继承而来 2020 3 14 第6章标准类库与常用算法 11of48 Object类 其中的几个重要方法 1 equals 方法publicbooleanequals Objectobj 该方法是把当前对象 即调用该方法的对象 与参数对象obj进行比较 判断这两个对象所封装的信息是否完全一样 2 toString 方法publicStringtoString 该方法是返回表示Object类一个对象的字符串 该字符串由对象所属类的全限定名 java lang object 字符 和一个用十六进制表示的散列码组成 2020 3 14 第6章标准类库与常用算法 12of48 3 finalize 方法protectedvoidfinalize throwsThrowable该方法可以观察垃圾回收的过程 4 clone 方法protectedobjectclone 该方法被声明为保护型 只有继承链上的类才可以调用来克隆对象 例5 8 Object类的使用方法 Object类 2020 3 14 第6章标准类库与常用算法 13of48 Class类 Class类的实例表示正在运行的Java应用程序中的类和接口 包括数组基本的Java类型 boolean byte char short int long float和double 和关键字void等都可以表示为Class对象 Class类主要用于解析各种类 2020 3 14 第6章标准类库与常用算法 14of48 System类 System类提供标准输入 标准输出和错误输出等三个属性 以及访问外部系统属性和环境变量 加载文件和库的方法以及数组复制等方法 例5 9 System类的使用方法示例 2020 3 14 第6章标准类库与常用算法 15of48 Math类 Math类是Object类的直接子类 定义 publicfinalclassMathextendsObject它是一个最终类 包含有实现基本数值运算 如取绝对值abs 最大值max 最小值min 随机数random 四舍五入round 向下舍入floor 自然指数exp 对数log 平方根sqrt 三角和反三角函数等一系列方法函数 2020 3 14 第6章标准类库与常用算法 16of48 Number类 Number类是抽象类 它是JAVA平台中所有数字类的父类 包括Byte Short Integer Long Float Double BigDecimal和BigInteger等 这些子类提供将数值转换为相应数据类型的方法 2020 3 14 第6章标准类库与常用算法 17of48 BigDecimal类不可变的 任意精度的有符号的十进制数字 Number类 2020 3 14 第6章标准类库与常用算法 18of48 BigInteger类不可变的 任意精度的整型数字 Number类 2020 3 14 第6章标准类库与常用算法 19of48 java util程序包提供了一系列描述数据结构的实用化类和接口 其核心是向量 Vector 二进制位集合 BitSet 堆栈 Stack 和散列表 Hashtable 等能包容一种各类对象的类型 同时它还提供了若干个十分有用的类 如日期类 阳历类 日历类 随机数发生器类和字符串分解器类等 java util程序包 2020 3 14 第6章标准类库与常用算法 20of48 java util程序包 日期类DateCalendarGregorianCalendar 例5 11 随机数类Random 例5 12 2020 3 14 第6章标准类库与常用算法 21of48 集合 集合是能包容一组各类对象的数据类型 Java在java util程序包中定义了几种类型的集合 Vector类 BitSet类 ArrayList类 LinkedList类 Stack类和HashTable类等 2020 3 14 第6章标准类库与常用算法 22of48 Vector类 Vector类是集合类型中应用最广泛的一种 它类似于一维数组 但又是可扩充的对象数组 其内的元素可以用一组整数访问 但访问元素的格式却不像数组元素那么简单 是调用Vector类提供的elementAt 方法 即 向量对象名 elementAt 索引 2020 3 14 第6章标准类库与常用算法 23of48 举例 1 importjava util Vector 2 importjavafoundation ch03 UDate 3 publicclassSwapDateextendsVector 4 privatevoidSwap intx inty 5 6 Objecttemp elementAt x 7 setElementAt elementAt y x 8 setElementAt temp y 9 10 publicstaticvoidmain String args 11 2020 3 14 第6章标准类库与常用算法 24of48 举例 12 SwapDatev newSwapDate 13 v addElement newUDate 2001 3 8 14 v addElement newUDate 2001 10 1 15 UDatea UDate v elementAt 0 16 UDateb UDate v elementAt 1 17 System out println 调用Swap 方法之前的v 0 18 a getDate a getMonth a getYear 19 System out println 调用Swap 方法之前的v 1 20 b getDate b getMonth b getYear 22 v Swap 0 1 2020 3 14 第6章标准类库与常用算法 25of48 举例 23 a UDate v elementAt 0 24 b UDate v elementAt 1 25 System out println 调用Swap 方法之后的v 0 26 a getDate a getMonth a getYear 27 System out println 调用Swap 方法之后的v 1 28 b getDate b getMonth b getYear 输出结果为 调用Swap 方法之前的v 0 8 3 2001调用Swap 方法之前的v 1 1 10 2001调用Swap 方法之后的v 0 1 10 2001调用Swap 方法之后的v 1 8 3 2001 2020 3 14 第6章标准类库与常用算法 26of48 线性表类 线性表是一种最简单的线性结构 所具有的特点是 其数据元素按照逻辑顺序依次存放在一组连续的物理存储单元之中 可以使用ArrayList类来定义 保存各种Java对象的值 并进行增删改操作 还可以完成查询 例5 3 2020 3 14 第6章标准类库与常用算法 27of48 链表类 链表结构中的每个元素一般占用两个单元 一个是当前元素数据 另一个是指向下一元素地址的指针 对于一个链表 还需增加一个额外的链头 其后跟随其它元素 在最后元素中标明一个空地址 表示链表结束 表 5 3 例 5 4 2020 3 14 第6章标准类库与常用算法 28of48 堆栈类 堆栈类一般是线性结构 其特点是 其数据元素按照逻辑顺序依次存放在一组连续的物理存储单元之中 并遵守先进后出的原则 例 5 5 2020 3 14 第6章标准类库与常用算法 29of48 递归算法 在介绍递归算法之前 首先熟悉下递推 递推一般指 在已知第一步结果和第n 1步结果的情况下 通过公式可以递推出第n步的结果 对于a1 1 an 1 n 1 3 可以推出an n3 对于阶乘 求积分和级数求和等问题都可以使用递推解决 即通过循环语句执行若干次就可以得出所需要的某一步或者前几步的结果 2020 3 14 第6章标准类库与常用算法 30of48 例5 6 计算两个正整数的最大公约数算法描述 采用 辗转相除法 假定两个数为p和q 首先判断p与q的大小关系 如果p q则交换它们 计算p与q的余数r p q 如果r为0 则q即为所求 程序结束 否则继续 令p q q r 并转到 继续进行 递归算法 2020 3 14 第6章标准类库与常用算法 31of48 程序代码 1 Scannersc newScanner System in 2 intp sc nextInt 3 intq sc nextInt 4 System out print p 与 q 的最大公约数 5 intr Math max p q 6 q Math min p q 7 p r 8 while r p q 0 9 10 p q 11 q r 12 13 System out println q 递归算法 2020 3 14 第6章标准类库与常用算法 32of48 递归算法 递归是方法调用其自身直到执行完成为止 它是一种重要的编程技术 例如 求n的阶乘的公式可以写成递归的形式 当n 0时 将f n 的计算转化为f n 1 的计算 f n 1 的计算转化为f n 2 的计算 依此类推 此时递归继续 当n 0时 f n 1 此时递归结束 2020 3 14 第6章标准类库与常用算法 33of48 递归算法一般用于解决三类问题 问题的数据定义形式是按递归定义的 问题解法按递归算法实现 例如回溯等 问题的数据结构形式是按递归定义的 如树的遍历 图的搜索等 递归算法 裴波那契数列阿克曼函数梵塔问题 2020 3 14 第6章标准类库与常用算法 34of48 例5 7 从键盘输入整数n 然后使用递归算法计算裴波那契数列的第n项算法描述 f 0 0 f 1 1 f n f n 1 f n 2 递归方式定义 1 longf intn 2 3 if n 0 4 return0 5 elseif n 1 6 return1 7 else8 returnf n 1 f n 2 9 递归算法 2020 3 14 第6章标准类库与常用算法 35of48 主方法体代码 1 Scannersc newScanner System in 2 intn sc nextInt 3 Fibonaccifibonacci newFibonacci 4 longresult fibonacci f n 5 System out println 裴波那契数列第 n 项 6 result 递归算法 运行结果 输入 7结果 裴波那契数列第7项 13 2020 3 14 第6章标准类库与常用算法 36of48 排序算法 排序是计算机程序设计中的一种重要操作 它的功能是将一组杂乱无章的数据元素按照关键字给出的次序重新排列起来 在确保排序数据元素安全性的前提下 减少时间开销提高执行速度是设计排序程序必须遵循的最重要原则 排序算法有插入排序 选择排序 冒泡排序 双冒泡排序和快速排序等 2020 3 14 第6章标准类库与常用算法 37of48 双冒泡排序算法 冒泡排序的基本思想 对于具有n个元素的一组数据 从它最开头两个元素开始 比较相邻两数的大小 将小的调换到前面 重复此过程直到比较完所有元素 称之为 一趟冒泡 过程 其结果是最大数已 沉底 即已移到它排序的最终位置 所以可把它从这组数据中剔除掉 同时 其它元素移动的总趋势也都向排序的最终位置靠拢 接着 对剩下的n 1个元素再进行 一趟冒泡 过程将次大数 沉底 重复上述冒泡过程 直到整个 一趟冒泡 过程中不再发生数据交换为止 2020 3 14 第6章标准类库与常用算法 38of48 双冒泡排序算法只不过在 一趟冒泡 过程中再增加一次冒泡过程 分别称为 前冒泡过程 和 后冒泡过程 前者与上述的办法完全一样 后者从删除掉 沉底 元素后剩下的一组数据中取最后相邻两元素开始比较两元素的大小 也是将小的调换到前面 然后 再选取前移一个位置的相邻两元素进行比较 重复上述过程 直到把此时的一组数据比较完为止 才完成后冒泡过程 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 39of48 双冒泡排序算法的测试 1 publicclassSortTool 2 publicstaticvoidswapItem intdata inti intj 3 4 try5 6 inttemp data i 7 data i data j 8 data j temp 9 10 catch ArrayIndexOutOfBoundsExceptionaIndexOutEx 11 System out println 执行线程中的数组下标越界 12 13 publicstaticvoidprtElement intdata 14 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 40of48 15 for intk 0 k data length k 16 System out print data k 17 System out println 18 19 1 publicclassBidirectionalBubbleSortextendsSortTool 2 publicintexchNum 3 publicvoidbiDirSort inta 4 5 intj k 1 6 intlimit a length 7 intst 1 8 while st limit 9 10 st 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 41of48 11 System out println n 第 st 1 趟冒泡过程 12 limit 13 booleanswapped false 14 for j st ja j 1 16 17 swapItem a j j 1 18 exchNum 19 swapped true 20 System out println k j j exchNum exchNum swapped swapped 21 prtElement a 22 23 if swapped return 24 elseswapped false 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 42of48 25 for j limit j st 26 if a j a j 1 27 28 swapItem a j j 1 29 exchNum 30 swapped true 31 System out println k j j exchNum exchNum swapped swapped 32 prtElement a 33 34 if swapped return 35 36 37 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 43of48 1 publicclassBiDirSortTest 2 publicstaticvoidmain String args 3 4 intdata 40 2 1 43 3 65 0 1 58 3 42 4 5 BidirectionalBubbleSortbiDirBubble newBidirectionalBubbleSort 6 System out println 排序前的数组data 7 biDirBubble prtElement data 8 biDirBubble biDirSort data 9 System out println 10 System out println 排序后的数组data 11 biDirBubble prtElement data 12 13 双冒泡排序算法 2020 3 14 第6章标准类库与常用算法 44of48 4021433650 1583424第1趟冒泡过程2401433