第7章 工具类及常用算法.ppt

JAVA 程序设计,第7章 工具类及常用算法,7.1 Java语言基础类,7.1.1 Java基础类库,java.lang包是Java语言的核心类库java.util包包括了Java语言中的一些低级的实用工具java.io包是Java语言的标准输入/输出类库java.awt包是Java语言用来构建图形用户界面(GUI)的类库java.applet包是用来实现运行于Internet浏览器中的Java Applet的工具类库java.net包是Java语言用来实现网络功能的类库其他包,JDK API文档,JDK API文档可以从java.sun.com网站下载，安装后，打开index.html即可 网上有chm格式的，有中文版,7.1.2 Object类,Object类是Java程序中所有类的直接或间接父类,7. 类jave.lang.Object,类java.lang.Object处于Java开发环境的类层次树的根部，其他所有的类都直接或间接地为它的子类。该类定义了一些所有对象最基本的状态和行为，包括与同类对象相比较，转化为字符串等等。下面我们分别进行介绍(详细用法大家可以查阅Java JDK的API)。,(1) equals( ),用来比较两个对象是否相同，如果相同，则返回true，否则返回false，它比较的是两个对象状态和功能上的相同，而不是引用上的相同。Integer one = new Integer (1);Integer anotherOne = new Integer (1);if (one.equals (anotherOne)System.out.println (“objects are equal”);例中，equals( )方法返回true，因为对象One和anotherOne 包含相同的整数值1.上次我们讲到了“=”与equals的区别,(2) getClass ( ),getClass ( )方法是final方法，它不能被重载。它返回一个对象在运行时所对应的类的表示，从而可以得到相应的信息。下面的方法得到并显示对象的类名：void PrintClassName( Object obj ) System.out.println(“ The objects class is “ + obj.getClass( ).getName( ) );,可以用getClass创建一个类的实例，而不必在编译时即知道到底是哪个类。下例创建了一个与对象obj具有相同类型的一个新的实例，所创建的对象可以是任何类。Object creatNewInstanceOf (object obj) return obj.getClass( ).newInstance( );,(3) toString( ),toString( )方法用来返回对象的字符串表示，可以用来显示一个对象。例如：System.out.println ( Thread.currentThread ( ).toString ( ) );可以显示当前的线程。通过重载toString ( )方法可以适当地显示对象的信息以进行调试。,(4) finalize( ),用于在垃圾收集前清除对象，前面已经讲述。,7.1.3 基本数据类型的包装类,Java的基本数据类型用于定义简单的变量和属性将十分方便，但为了与面向对象的环境一致，Java中提供了基本数据类型的包装类（wrapper），它们是这些基本类型的面向对象的代表。与8种基本数据类型相对应，基本数据类型的包装类也有8种，分别是：Character，Byte，Short，Integer，Long，Float，Double，Boolean。,这几个类有以下共同特点。,（1）这些类都提供了一些常数，以方便使用，如Integer.MAX_VALUE（整数最大值）， Double.NaN(非数字)，Double. POSITIVE_INFINITY（正无穷）等。（2）提供了valueOf(String)，toString()，用于从字符串转换及或转换成字符串。（3）通过xxxxValue()方法可以得到所包装的值，Integer对象的intValue()方法。（4）对象中所包装的值是不可改变的（immutable）。要改变对象中的值只有重新生成新的对象。（5）toString(), equals()等方法进行了覆盖。除了以上特点外，有的类还提供了一些实用的方法以方便操作。例如，Double类就提供了更多的方法来与字符串进行转换。,/double转成string的几种方法d=3.14159；s = "" + d；s = Double.toString( d )；s = new Double(d).toString()；s = String.valueOf( d )；/ String转成double的几种方法s = "3.14159"；tryd = Double.parseDouble( s )；d = new Double(s).doubleValue()；d = Double.valueOf( s ).doubleValue()；catch(NumberFormatException e )e.printStackTrace()；例 DoubleAndString.java在jdk1.5 以上提供了boxing/unboxing，更方便操作,7.1.4 Math类,Math类用来完成一些常用的数学运算 public final static double E；/ 数学常量e public final static double PI；/ 圆周率常量public static double abs(double a)；/ 绝对值public static double exp(double a)；/ 参数次幂ublic static double floor(double a)；/ 不大于参数的最大整数 public static double IEEE remainder(double f1，double f2)；/ 求余 public static double log(double a)；/ 自然对数 public static double max(double a，double b)；/ 最大值 public static float min(float a，float b)；/ 最小值例： TestMath.java,public static double pow(double a，double b)；/ 乘方 public static double random()；/ 产生0和1(不含1)之间的伪随机数 public static double rint(double a)；/ 四舍五入 public static double sqrt(double a)；/ 平方根 public static double sin(double a)；/ 正弦 public static double cos(double a)；/ 余弦 public static double tan(double a)；/ 正切 public static double asin(double a)；/ 反正弦 public static double acon(double a)；/ 反余弦 public static double atan(double a)；/ 反正切,7.1.5 日期类,Calendar得到一个实例 Calendar.getInstance() /Locale.ZH.get(DAY_OF_MONTH) .getDisplayName(DAY_OF_WEEK).set .add(HOUR,1) .roll(MONTH, 5), .setTime(date), .getTime()Datenew Date(), new Date(System.currentTimeMillis().setTime(long), .getTime()SimpleDateFormat(“yyyy-MM-dd HH:mm:ss”).format, .parse例 CalendarDate.java,getTime(),getTime(),7.1.6 System类,在Java中，系统属性起到替代环境变量的作用(环境变量是平台相关的)可使用System.getProperties()方法获得一个 Properties类的对象，其中包含了所有可用的系统属性信息可使用System.getProperty(String name)方法获得特定系统属性的属性值在命令行运行Java程序时可使用-D选项添加新的系统属性,7. 2 字符串,程序中需要用到的字符串可以分为两大类，一类是创建之后不会再做修改和变动的字符串常量；另一类是创建之后允许再做更改和变化的字符串。前者是String类，后者是StringBuffer类。 除了immutable特点外，还要注意String是否interned,7.2.1 String类,String 类对象保存不可修改(immutable)的Unicode字符序列 String类的下述方法能创建并返回一个新的String对象实例: concat, replace, replaceAll, substring, toLowerCase, toUpperCase, trim,toString.提供查找功能的有关方法: endsWith, startsWith, indexOf,，lastIndexOf.提供比较功能的方法: equals, equalsIgnoreCase, 其它方法: charAt ，length.例： TestStringMethod.javaJdk1.5 增加了format函数 StringFormat.java%1$,8.5f %序号$ 标识 宽度及精度 转换方式,7.2.2 StringBuffer类,StringBuffer类对象保存可修改的Unicode字符序列: 特别是在循环中不使用+=构造方法 StringBuffer() StringBuffer(int capacity) StringBuffer(String initialString)实现修改操作的方法: append, insert, reverse, setCharAt, setLength.例：Sring与StringBuffer的转化 StringAssign.java,7.2.3 StringTokenizer类,java.util.StringToken类提供了对字符串进行解析和分割的功能。比如，要对一条语句进行单词的区分，就可以用到该类。StringTokenizer的构造方法有：StringTokenizer(String str); StringTokenizer(String str, String delim); StringTokenizer(String str, String delim, boolean returnDelims);其中，str是要解析的字符串，delim是含有分隔符的字符串，returnDelims表示是否将分隔符也作为一个分割串。该类的重要方法有： public int countTokens()；/ 分割串的个数 public boolean hasMoreTokens()；/ 是否还有分割串 public String nextToken()；/ 得到下一分割串例：TestStringTokenizer.java另String类的 matches, replaceAll, split可以使用正则表达式例：StringSplit.java,7.3 集合类,7.3.1 集合与Collection API,Collection API提供“集合”的功能Collection API包含下述接口Collection: 将一组对象以集合元素的形式组织到一起，在其子接口中分别实现不同的组织方式Set: (Collection的子接口) 不记录元素的保存顺序，且不允许有重复元素List: (Collection的子接口)记录元素的保存顺序，且允许有重复元素另外，还有一类键、值对的集合(Map),Collection 接口,Collection 层次结构(简化),Map层次结构(简化),Iterator接口,Iterator接口定义了对Collection类型对象中所含元素的遍历等增强处理功能可以通过Collection接口中定义的iterator()方法获得一个对应的Iterator(实现类)对象Set (实现类)对象对应的Iterator仍然是无序的List(实现类)对象对应的ListIterator对象可以实现对所含元素的双向遍历: 使用next()方法和previous()方法,Iterator接口层次,几个早期的类或接口,Vector， 现多用 ArrayList相当于动态数组(比JDK1.0中的 ArrayList好), elementAt, Stack， 现多用 LinkedListStack是Vector的子类, push, pop, peekHashtable， 现多用 HashMapHashtable实现Map接口, 参见Properties类Enumeration， 现多用Iterator用另一种方式实现Iterator的功能,7.3.2 Set接口及HashSet类,Set中对象不重复所谓不重复是指：hashCode()不等如果hashCode()相等，再看equals是否为false例： TestHashSet.java注：String 对象的哈希码根据以下公式计算： s0*31(n-1) + s1*31(n-2) + . + sn-1 使用 int 算法，这里 si 是字符串的第 i 个字符，n 是字符串的长度， 表示求幂。（空字符串的哈希值为 0。）,7.3.3 List接口及ArrayList，Vector类,List接口public interface List extends Collection E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); int indexOf(Object o); .例：TestArrayList.java,7.3.4 Iterator及Enumeration,Iterator (所有的Collection都能产生）Iterator iterator = iterable.iterator();while( iterator.hasNext() doSomething( iterator.next();Enumeration(JDK早期的类实现，如Vector, 有点过时了）Enumeration e = v.elements(); while(e.hasMoreElements() doSomething(e.nextElement()在JDK1.5以后，增强的for语句for( Element e : list ) doSomething(e);,7.3.5 Map接口及HashMap类,Map是键、值对的集合其中可以取到entrySet()、keySet()、values()、Map.Entry是一个嵌套接口例：TestHashMap.java又例：早期的TestHashtable.java,7.4 向量、堆栈、队列,7.4.1 Vector向量,它对应于类似数组的顺序存储的数据结构，但是具有比数组更强大的功能。它是允许不同类型元素共存的变长数组。public Vector(int initCapacity，int capacityIncrement)；addElement(Object obj)；insertElement(Object obj，int index)；void removeElementAt(int index)； Object elementAt(int index) int indexOf(Object obj，int start_index),7.4.2 Stack堆栈,是遵循“后进先出”(Last In First Out, LIFO)原则的重要线性数据结构 （1）构造函数。public Stack()：是栈类惟一的构造函数，创建堆栈时可以直接调用它。（2）压栈与弹栈操作。public Object push(Object item)：将指定对象压入栈中。Public Object pop()：将堆栈最上面的元素从栈中取出，并返回这个对象。（3）检查堆栈是否为空public boolean empty()：若堆栈中没有对象元素，则此方法返回true，否则返回false。,7.4.3 LinkedList及队列,队列(Queue)，也是重要的线性数据结构。队列遵循“先进先出”(First In First Out，FIFO)的原则，固定在一端输入数据(称为加队)，另一端输出数据(称为减队)。,7.5 排序与查找,7.5.1 Arrays类,Arrays类是用于对数组进行排序和搜索的类。Arrays类为所有基本数据类型的数组提供了sort()和binarySearch() 执行binarySearch()之前应调用sort() public static void sort(List list);public static void sort(List list, Comparator c);public static int binarySearch(List list, Object key);public static int binarySearch(List list, Object key, Comparator c);Arrays.asList( 10, 7, 6, 5, 9) 方法例：TestArraysSort.java,关于比较,要么对象是java.lang.Comparable实现方法 public int compareTo(Object obj)return this.price (Book)obj).price;要么提供一个java.lang. Comparator实现方法 public int compare(T o1, T o2) 这些方法的含义要与equals不冲突,7.5.2 Collections类,此类完全由在 collection 上进行操作或返回 collection 的静态方法组成.如sort, binarySearch, reverse等例 TestCollectionsSort.java,7.5.3 TreeMap及TreeSet,分别实现了SortedMap及SortedSet,7.5.4 排序的实现,冒泡排序 BubbleSort.java选择排序 SelectSort.java快速排序 QuickSortTest.java,7.6 遍试、迭代、递归及回溯,本节介绍在程序设计中常用的几种算法，包括遍试、迭代、递归和回溯，这些算法属于“通用算法”，它们在解决许多问题中都有应用。,7.6.1 遍试,在有限的范围内，可以对所有的值都进行试验和判断，从而找到满足条件的值 All_153.java求三位的水仙花数 All_628.java求9999以内的完全数 All_220.java 求9999以内的“相亲数” 遍试算法基本的模式for(;) if(); ,7.6.2 迭代,是多次利用同一公式进行计算，每次将计算的结果再代入公式进行计算，从而逐步逼近精确解Sqrt.java自编一个函数求平方根 Julia.java 利用迭代公式求Julia集迭代的基本模式 for(;) x = f(x); ,7.6.3 递归,递归(recursive)就是一个过程调用过程本身。在递归调用中，一个过程执行的某一步要用到它自身的上一步(或上几步)的结果。 Fac.java用递归方法求阶乘 VonKoch.java画Von_Koch曲线 CayleyTree.java 用计算机生成Cayley树 递归算法的基本模式f(n) f(n-1); ,7.6.4 回溯,回溯法也叫试探回溯法，利用回溯算法解决问题的思路是：先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都一一试探，如果不符合条件就返回纠正，反复进行这种试探再返回纠正，直到得出全部符合条件的答案或是问题无解为止。 Queen8.java 八皇后问题,7.7 与集合类相关的Java新特性,在JDK1.5（即JDK5.0）中，Java语言增加了许多新的特性，其中有几项与集合的使用密切相关（虽然它们也可以用于其他场合），在这里专门介绍一下,7.7.1 泛型,泛型（Generic）是JDK5.0增加的最重要的Java语言特性。使用泛型可以解决这种问题：程序可以针对不同的类有相同的处理办法，但这些类之间不一定有继承关系。 Vector v = new Vector ();v.addElement( “one” );String s = v.elementAt(0);,7.7.2 增强的for语句,for (Photo photo : album)System.out.println( photo.toString() );,7.7.3 装包与拆包,在JDK1.5以上的版本中则可以自动地进行装包和拆包：自动装包是指基本类型自动转为包装类(如int转为Integer)；自动拆包是指包装类自动转为基本类型 (如Integer转为int) int a = 3;ArrayList ary = new ArrayList();ary.add(a); /装包：int自动转换成Integer对象作为add方法的参数int c = (Integer)ary.get(0); / 拆包：Integer自动转换成int赋值给变量c,(5) notify( )、 notifyAll( )、 wait( ),