Java05算法与数据结构.ppt

1、Java技术与应用,Java系统类 (第5章),西安交大 卫颜俊 2009年4月 电子信箱：Mr.J QQ: 610568018 网站: 7/java,主要内容,算法、数据结构 核心语言包(java.lang) 工具包(java.util) 数学包(java.math),1.算法、数据结构,使用计算机求解现实世界问题的步骤： 首先需要对问题进行数学抽象，使用数学语言对现实问题加以描述称为数学建模，得到数学模型 然后将数学模型化为计算机算法和数据结构 最后使用计算机语言进行程序设计，得出问题的答案。,数据结构,各种数据组织形式及其相关操作方式的集合。 包括线性

2、结构和非线性结构 线性结构的元素之间存在确定的物理顺序关系 而非线性结构的元素之间不一定存在确定的物理顺序。,数据结构(2),数据的逻辑结构描述的是元素之间的逻辑关系 数据的逻辑结构在计算机存储空间中的实现称为数据的物理结构。 常见的数据结构又可以细分为：顺序表、链表、栈、队列、哈希表、树和图等。,算法,算法是解决特定问题的步骤，即“计算与法则”，具有以下5个特性： 输入：包含输入数据； 输出：包含输出数据； 有穷：由有限条指令组成； 确定：每条指令有确切的含义，对于相同的输入数据得到相同的输出结果； 可行：在有限步内实现输出。 描述算法可以使用自然语言、框图、伪代码或程序设计语言等 使用时间

3、复杂度和空间复杂度来度量算法的效率。,误差,由算法得出计算结果的过程中步步都可能存在误差 计算结果只是现实世界模型的近似值，在建立数学模型时可能由于抽象方法不很科学，会出现第一种误差，称为模型误差； 数学模型中用到的一些参数大多数情况下是由观测得来的，所以也会出现误差，称为观测误差； 由电脑计算出来的结果与模型的准确值之间也存在误差，称为截断误差； 当计算当中对数值位数进行舍入时也存在误差，称为舍入误差。,衡量算法的误差幅度,绝对误差，即准确值与近似值之差 相对误差，即准确值与近似值的差值除以准确值。 例5-1,5-2说明了算法与误差的关系。,【例8-1】计算定积分,两种迭代公式 (A) (B

4、),2.核心语言包(java.lang),Object Class System 【例5-9】 Math 基本数据类型类 【例5-10】 StringBuilder,3.工具包(java.util),日期类 Date Calendar GregorianCalendar 【例5-11】 随机数类Random 集合（Collection）和映射（Map）,数据结构类,Collection为所有集合层次的根，代表一组元素； Set为不包含重复元素的集合； SortedSet 为Set的一种，自动维持升序排列； List为有序集合（序列），可以包含重复元素； Queue为队列。 Map为键-值对（key-value），不能包含重复键，每个键最多对应一个值； SortedMap为Map的一种，自动维持升序排列。,数据结构类举例,【例5-3】ArrayList类演示 【例5-5】Stack类演示,4.数学包(java.math),BigDecimal类,BigInteger类,综合举例,【例5-