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 object’s 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。

（2）提供了valueOf(String)，toString()，用于从字符串转换及或转换成字符串。 这几个类有以下共同特点。 （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的几种方法 s = "" + d； s = Double.toString( d )； s = new Double(d).toString()； s = String.valueOf( d )； // String转成double的几种方法 s = "3.14159"； try{ d = 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 日期类 例 CalendarDate.java Date 7.1.5 日期类 getTime() getTime() Calendar Date long Calendar 得到一个实例 Calendar.getInstance() //Locale.ZH .get(DAY_OF_MONTH) .getDisplayName(DAY_OF_WEEK) .set .add(HOUR,1) .roll(MONTH, 5), .setTime(date), .getTime() Date new Date(), new Date(System.currentTimeMillis()) .setTime(long), .getTime() SimpleDateFormat(“yyyy-MM-dd HH:mm:ss”) .format, .parse 例 CalendarDate.java

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.java Jdk1.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包含下述接口 Set: (Collection的子接口) 不记录元素的保存顺序，且不允许有重复元素 List: (Collection的子接口)记录元素的保存顺序，且允许有重复元素 另外，还有一类键、值对的集合(Map)

<<interface>> Collection 接口 <<interface>> Collection +add(element : Object) : boolean +remove(element : Object) : boolean +size() : int +isEmpty() : boolean +contains(element : Object) : boolean +iterator() : Iterator

Collection 层次结构(简化) Iterator Iterable Collection Set List Queue <<interface>> Iterator <<interface>> Iterable <<interface>> Collection <<interface>> Set <<interface>> List <<interface>> Queue HashSet TreeSet Vector ArrayList LinkedList PrirotyQueue Stack ArrayDeque

Map层次结构(简化) Map Dictionary HashMap TreeMap Properties <<interface>> Map <<interface>> Dictionary AbstractMap HashMap TreeMap Hashtable Properties

Iterator接口 Iterator接口定义了对Collection类型对象中所含元素的遍历等增强处理功能 可以通过Collection接口中定义的iterator()方法获得一个对应的Iterator(实现类)对象 Set (实现类)对象对应的Iterator仍然是无序的 List(实现类)对象对应的ListIterator对象可以实现对所含元素的双向遍历: 使用next()方法和previous()方法

Iterator接口层次 Iterator +hasNext() : boolean +next() : boolean +remove() <<interface>> Iterator +hasNext() : boolean +next() : boolean +remove() <<interface>> ListIterator +hasPrevious() : boolean +previous() : Object +add(element : Object) +set(element : Object)

几个早期的类或接口 Vector， 现多用 ArrayList Stack， 现多用 LinkedList 相当于动态数组(比JDK1.0中的 ArrayList好), elementAt, Stack， 现多用 LinkedList Stack是Vector的子类, push, pop, peek Hashtable， 现多用 HashMap Hashtable实现Map接口, 参见Properties类 Enumeration， 现多用Iterator 用另一种方式实现Iterator的功能

7.3.2 Set接口及HashSet类 Set中对象不重复 所谓不重复是指： 例： TestHashSet.java 注： hashCode()不等 如果hashCode()相等，再看equals是否为false 例： TestHashSet.java 注： String 对象的哈希码根据以下公式计算： s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 使用 int 算法，这里 s[i] 是字符串的第 i 个字符，n 是字符串的长度，^ 表示求幂。（空字符串的哈希值为 0。）

7.3.3 List接口及ArrayList，Vector类 public interface List<E> extends Collection<E> { 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> e = v.elements(); while(e.hasMoreElements()) doSomething(e.nextElement()) 在JDK1.5以后，增强的for语句 for( Element e : list ) doSomething(e);

7.3.5 Map接口及HashMap类 Map是键、值对的集合 例：TestHashMap.java 其中可以取到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 要么提供一个java.lang. Comparator 实现方法 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 7.5.4 排序的实现 冒泡排序 BubbleSort.java 选择排序 SelectSort.java 快速排序 QuickSortTest.java

7.6 遍试、迭代、递归及回溯 本节介绍在程序设计中常用的几种算法，包括遍试、迭代、递归和回溯，这些算法属于“通用算法”，它们在解决许多问题中都有应用。

7.6.1 遍试 在有限的范围内，可以对所有的值都进行试验和判断，从而找到满足条件的值 遍试算法基本的模式 7.6.1 遍试 在有限的范围内，可以对所有的值都进行试验和判断，从而找到满足条件的值 All_153.java求三位的水仙花数 All_628.java求9999以内的完全数 All_220.java 求9999以内的“相亲数” 遍试算法基本的模式 for(;;){ if(); }

7.6.2 迭代 是多次利用同一公式进行计算，每次将计算的结果再代入公式进行计算，从而逐步逼近精确解 迭代的基本模式 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<String> v = new Vector<String> (); 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( )