工具類及常用算法

1、.JAVA 第第7章章 工具類及常用算法工具類及常用算法.7.1 Java語(yǔ)言基礎(chǔ)類第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.1 Java基礎(chǔ)類庫(kù)njava.lang包是Java語(yǔ)言的核心類庫(kù)njava.io包是Java語(yǔ)言的標(biāo)準(zhǔn)輸入/輸出類庫(kù)njava.util包包括了Java語(yǔ)言中的一些低級(jí)的實(shí)用工具nava.awt包是Java語(yǔ)言用來(lái)構(gòu)建圖形用戶界面(GUI)的類庫(kù)njava.applet包是用來(lái)實(shí)現(xiàn)運(yùn)行于Internet瀏覽器中的Java Applet的工具類庫(kù)包是Java語(yǔ)言用來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)功能的類庫(kù)n其他包第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.JDK API文檔nJDK API文檔可以從網(wǎng)站下

2、載，安裝后，打開index.html即可 n網(wǎng)上可以找到chm格式的，甚至中文版第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.2 Object類nObject類是Java程序中所有類的直接或間接父類 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7. 類類jave.lang.Objectn類類java.lang.Object處于處于Java開發(fā)環(huán)境的類層次開發(fā)環(huán)境的類層次樹的根部，其他所有的類都直接或間接地為它的樹的根部，其他所有的類都直接或間接地為它的子類。該類定義了一些所有對(duì)象最基本的狀態(tài)和子類。該類定義了一些所有對(duì)象最基本的狀態(tài)和行為，包括與同類對(duì)象相比較，轉(zhuǎn)化為字符串等行為，包括與同類對(duì)象相比較，轉(zhuǎn)化為字

3、符串等等。下面我們分別進(jìn)行介紹等。下面我們分別進(jìn)行介紹(詳細(xì)用法大家可以查詳細(xì)用法大家可以查閱閱Java JDK的的API)。第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(1) equals( )n用來(lái)比較兩個(gè)對(duì)象是否相同，如果相同，則返回用來(lái)比較兩個(gè)對(duì)象是否相同，如果相同，則返回true，否則返回，否則返回false，它比較的是兩個(gè)對(duì)象狀態(tài)，它比較的是兩個(gè)對(duì)象狀態(tài)和功能上的相同，而不是引用上的相同。和功能上的相同，而不是引用上的相同。nInteger one = new Integer (1);nInteger anotherOne = new Integer (1);nif (one.equals (

4、anotherOne)nSystem.out.println (“objects are equal”);n例中，例中，equals( )方法返回方法返回true，因?yàn)閷?duì)象，因?yàn)閷?duì)象One和和anotherOne 包含相同的整數(shù)值包含相同的整數(shù)值1.第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(2) getClass ( )ngetClass ( )方法是方法是final方法，它不能被重載。方法，它不能被重載。它返回一個(gè)對(duì)象在運(yùn)行時(shí)所對(duì)應(yīng)的它返回一個(gè)對(duì)象在運(yùn)行時(shí)所對(duì)應(yīng)的類的表示，類的表示，從從而可以得到相應(yīng)的信息。下面的方法得到并顯示而可以得到相應(yīng)的信息。下面的方法得到并顯示對(duì)象的類名：對(duì)象的類名：nvo

5、id PrintClassName( Object obj )nn System.out.println(“ The objects class is “ + obj.getClass( ).getName( ) );n第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.n可以用可以用getClass創(chuàng)建一個(gè)類的實(shí)例，而不必在編譯時(shí)即知?jiǎng)?chuàng)建一個(gè)類的實(shí)例，而不必在編譯時(shí)即知道到底是哪個(gè)類。下例創(chuàng)建了一個(gè)與對(duì)象道到底是哪個(gè)類。下例創(chuàng)建了一個(gè)與對(duì)象obj具有相同類具有相同類型的一個(gè)新的實(shí)例，所創(chuàng)建的對(duì)象可以是任何類。型的一個(gè)新的實(shí)例，所創(chuàng)建的對(duì)象可以是任何類。nObject creatNewInstanceOf (ob

6、ject obj)nn return obj.getClass( ).newInstance( );n第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(3) toString( ) ntoString( )方法用來(lái)返回對(duì)象的字符串表示，可方法用來(lái)返回對(duì)象的字符串表示，可以用來(lái)顯示一個(gè)對(duì)象。例如：以用來(lái)顯示一個(gè)對(duì)象。例如：nSystem.out.println ( Thread.currentThread ( ).toString ( ) );n可以顯示當(dāng)前的線程?？梢燥@示當(dāng)前的線程。n通過(guò)重載通過(guò)重載toString ( )方法可以適當(dāng)?shù)仫@示對(duì)象的方法可以適當(dāng)?shù)仫@示對(duì)象的信息以進(jìn)行調(diào)試。信息以進(jìn)行調(diào)試。第3章

7、 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(4) finalize( )n用于在垃圾收集前清除對(duì)象，前面已經(jīng)講述。用于在垃圾收集前清除對(duì)象，前面已經(jīng)講述。第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.3 基本數(shù)據(jù)類型的包裝類nJava的基本數(shù)據(jù)類型用于定義簡(jiǎn)單的變量和屬性將十分方便，但為了與面向?qū)ο蟮沫h(huán)境一致，Java中提供了基本數(shù)據(jù)類型的包裝類（wrapper），它們是這些基本類型的面向?qū)ο蟮拇?。與8種基本數(shù)據(jù)類型相對(duì)應(yīng)，基本數(shù)據(jù)類型的包裝類也有8種，分別是：Character，Byte，Short，Integer，Long，F(xiàn)loat，Double，Boolean。n這幾個(gè)類有以下共同特點(diǎn)。n（1）這些類都提

8、供了一些常數(shù)，以方便使用，如Integer.MAX_VALUE（整數(shù)最大值）， Double.NaN(非數(shù)字)，Double. POSITIVE_INFINITY（正無(wú)窮）等。n（2）提供了valueOf(String)，toString()，用于從字符串轉(zhuǎn)換及或轉(zhuǎn)換成字符串。n（3）通過(guò)xxxxValue()方法可以得到所包裝的值，Integer對(duì)象的intValue()方法。n（4）對(duì)象中所包裝的值是不可改變的（immutable）。要改變對(duì)象中的值只有重新生成新的對(duì)象。n（5）toString(), equals()等方法進(jìn)行了覆蓋。n除了以上特點(diǎn)外，有的類還提供了一些實(shí)用的方法以方便操

9、作。例如，Double類就提供了更多的方法來(lái)與字符串進(jìn)行轉(zhuǎn)換。第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.n/double轉(zhuǎn)成string的幾種方法nd=3.14159；ns = + d；ns = Double.toString( d )；ns = new Double(d).toString()；ns = String.valueOf( d )；n/ String轉(zhuǎn)成double的幾種方法ns = 3.14159；ntrynd = Double.parseDouble( s )；nd = new Double(s).doubleValue()；nd = Double.valueOf( s ).doubl

10、eValue()；nncatch(NumberFormatException e )nne.printStackTrace()；n第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.4 Math類nMath類用來(lái)完成一些常用的數(shù)學(xué)運(yùn)算 npublic final static double E；/ 數(shù)學(xué)常量en public final static double PI；/ 圓周率常量npublic static double abs(double a)；/ 絕對(duì)值npublic static double exp(double a)；/ 參數(shù)次冪nublic static double floor(do

11、uble a)；/ 不大于參數(shù)的最大整數(shù)n public static double IEEE remainder(double f1，double f2)；/ 求余n public static double log(double a)；/ 自然對(duì)數(shù)n public static double max(double a，double b)；/ 最大值n public static float min(float a，float b)；/ 最小值npublic static double pow(double a，double b)；/ 乘方n public static double ran

12、dom()；/ 產(chǎn)生0和1(不含1)之間的偽隨機(jī)數(shù)n public static double rint(double a)；/ 四舍五入n public static double sqrt(double a)；/ 平方根n public static double sin(double a)；/ 正弦n public static double cos(double a)；/ 余弦n public static double tan(double a)；/ 正切n public static double asin(double a)；/ 反正弦n public static double

13、 acon(double a)；/ 反余弦n public static double atan(double a)；/ 反正切第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.5 System類在Java中，系統(tǒng)屬性起到替代環(huán)境變量的作用(環(huán)境變量是平臺(tái)相關(guān)的)可使用System.getProperties()方法獲得一個(gè) Properties類的對(duì)象，其中包含了所有可用的系統(tǒng)屬性信息可使用System.getProperty(String name)方法獲得特定系統(tǒng)屬性的屬性值在命令行運(yùn)行Java程序時(shí)可使用-D選項(xiàng)添加新的系統(tǒng)屬性第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7. 2 字符串n程序中需要用到的字

14、符串可以分為兩大類，一類是創(chuàng)建之后不會(huì)再做修改和變動(dòng)的字符串常量；另一類是創(chuàng)建之后允許再做更改和變化的字符串。前者是String類，后者是StringBuffer類。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.2.1 String類nString 類對(duì)象保存不可修改(immutable)的Unicode字符序列 nString類的下述方法能創(chuàng)建并返回一個(gè)新的String對(duì)象: concat, replace, substring, toLowerCase, toUpperCase, trim,toString.n提供查找功能的有關(guān)方法: endsWith, startsWith, indexOf,，

15、lastIndexOf.n提供比較功能的方法: equals, equalsIgnoreCase, n其它方法: charAt ，length.第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.2.2 StringBuffer類StringBuffer類對(duì)象保存可修改的Unicode字符序列構(gòu)造方法 nStringBuffer() nStringBuffer(int capacity) nStringBuffer(String initialString)實(shí)現(xiàn)修改操作的方法: nappend, insert, reverse, setCharAt, setLength.第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.2

16、.3 StringTokenizer類njava.util.StringToken類提供了對(duì)字符串進(jìn)行解析和分割的功能。比如，要對(duì)一條語(yǔ)句進(jìn)行單詞的區(qū)分，就可以用到該類。nStringTokenizer的構(gòu)造方法有：nStringTokenizer(String str); nStringTokenizer(String str, String delim); nStringTokenizer(String str, String delim, boolean returnDelims);n其中，str是要解析的字符串，delim是含有分隔符的字符串，returnDelims表示是否將分隔符也

17、作為一個(gè)分割串。n該類的重要方法有：n public int countTokens()；/ 分割串的個(gè)數(shù)n public boolean hasMoreTokens()；/ 是否還有分割串n public String nextToken()；/ 得到下一分割串.7.3 集合類第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.3.1 集合與Collection APICollection API提供“集合”的功能Collection API包含下述接口nCollection: 將一組對(duì)象以集合元素的形式組織到一起，在其子接口中分別實(shí)現(xiàn)不同的組織方式nSet: (Collection的子接口) 不記錄元素的

18、保存順序，且不允許有重復(fù)元素nList: (Collection的子接口)記錄元素的保存順序，且允許有重復(fù)元素第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.Collection+add(element : Object) : boolean+remove(element : Object) : boolean+size() : int+isEmpty() : boolean+contains(element : Object) : boolean+iterator() : IteratorSetHashSetListArrayListVector第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.Iterator接口定義了對(duì)C

19、ollection類型對(duì)象中所含元素的遍歷等增強(qiáng)處理功能n可以通過(guò)Collection接口中定義的iterator()方法獲得一個(gè)對(duì)應(yīng)的Iterator(實(shí)現(xiàn)類)對(duì)象nSet (實(shí)現(xiàn)類)對(duì)象對(duì)應(yīng)的Iterator仍然是無(wú)序的nList(實(shí)現(xiàn)類)對(duì)象對(duì)應(yīng)的ListIterator對(duì)象可以實(shí)現(xiàn)對(duì)所含元素的雙向遍歷: 使用next()方法和previous()方法第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.Iterator+hasNext() : boolean+next() : boolean+remove() ListIterator+hasPrevious() : boolean+previous() :

20、 Object+add(element : Object)+set(element : Object) 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.nVectorn相當(dāng)于動(dòng)態(tài)數(shù)組(比JDK1.0中的 ArrayList好), elementAt, nStacknVector的子類, push, pop, peeknHashtablen實(shí)現(xiàn)Map接口, 參見Properties類nEnumeratoionn用另一種方式實(shí)現(xiàn)Iterator的功能第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.3.2 Set接口及HashSet類第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.3.3 List接口及ArrayList，Vector類第

21、3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.3.4 Iterator及Enumeration第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.3.5 Map接口及Hashtable類.7.4 向量、堆棧、隊(duì)列第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.4.1 Vector向量n它對(duì)應(yīng)于類似數(shù)組的順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，但是具有比數(shù)組更強(qiáng)大的功能。n它是允許不同類型元素共存的變長(zhǎng)數(shù)組。npublic Vector(int initCapacity，int capacityIncrement)；naddElement(Object obj)；ninsertElement(Object obj，int index)；nvoid rem

22、oveElementAt(int index)； nObject elementAt(int index) n int indexOf(Object obj，int start_index) 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.4.2 Stack堆棧n是遵循“后進(jìn)先出”(Last In First Out, LIFO)原則的重要線性數(shù)據(jù)結(jié)構(gòu) n（1）構(gòu)造函數(shù)。npublic Stack()：是棧類惟一的構(gòu)造函數(shù)，創(chuàng)建堆棧時(shí)可以直接調(diào)用它。n（2）壓棧與彈棧操作。npublic Object push(Object item)：將指定對(duì)象壓入棧中。nPublic Object pop()：將堆棧

23、最上面的元素從棧中取出，并返回這個(gè)對(duì)象。n（3）檢查堆棧是否為空npublic boolean empty()：若堆棧中沒(méi)有對(duì)象元素，則此方法返回true，否則返回false。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.4.3 LinkedList及隊(duì)列n隊(duì)列(Queue)，也是重要的線性數(shù)據(jù)結(jié)構(gòu)。隊(duì)列遵循“先進(jìn)先出”(First In First Out，F(xiàn)IFO)的原則，固定在一端輸入數(shù)據(jù)(稱為加隊(duì))，另一端輸出數(shù)據(jù)(稱為減隊(duì))。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5 排序與查找第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.1 Arrays類nArrays類是用于對(duì)數(shù)組進(jìn)行排序和搜索的類。Array

24、s類為所有基本數(shù)據(jù)類型的數(shù)組提供了sort()和binarySearch() n執(zhí)行binarySearch()之前應(yīng)調(diào)用sort() npublic static void sort(List list);npublic static void sort(List list, Comparator c);npublic static int binarySearch(List list, Object key);npublic static int binarySearch(List list, Object key, Comparator c);第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.2

25、Collections類第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.3 冒泡排序n BubbleSort.java 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.4 選擇排序nSelectSort.java 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.5 快速排序nQuickSortTest.java 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6 遍試、迭代、遞歸及回溯n本節(jié)介紹在程序設(shè)計(jì)中常用的幾種算法，包括遍試、迭代、遞歸和回溯，這些算法屬于“通用算法”，它們?cè)诮鉀Q許多問(wèn)題中都有應(yīng)用。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6.1 遍試n在有限的范圍內(nèi)，可以對(duì)所有的值都進(jìn)行試驗(yàn)和判斷，從而找到滿足條件的值 nA

26、ll_153.java求三位的水仙花數(shù) nAll_628.java求9999以內(nèi)的完全數(shù) nAll_220.java 求9999以內(nèi)的“相親數(shù)” n遍試算法基本的模式nfor(;) if(); 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6.2 迭代n是多次利用同一公式進(jìn)行計(jì)算，每次將計(jì)算的結(jié)果再代入公式進(jìn)行計(jì)算，從而逐步逼近精確解nSqrt.java自編一個(gè)函數(shù)求平方根 nJulia.java 利用迭代公式求Julia集n迭代的基本模式 nfor(;) x = f(x); 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6.3 遞歸n遞歸(recursive)就是一個(gè)過(guò)程調(diào)用過(guò)程本身。在遞歸調(diào)用中，一個(gè)過(guò)程執(zhí)行的某一步要用到它自身的上一步(或上幾步)的結(jié)果。 nFac.java用遞歸方法求階乘 nVonKoch.java畫畫Von_Koch曲線曲線 nCayleyTree.java 用計(jì)算機(jī)生成Cayley樹 n遞歸算法的基本模式nf(n) f(n-1); 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.