工具類及常用算法

1、.JAVA 第第7章章 工具類及常用算法工具類及常用算法.7.1 Java語言基礎(chǔ)類第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.1.1 Java基礎(chǔ)類庫njava.lang包是Java語言的核心類庫njava.io包是Java語言的標(biāo)準(zhǔn)輸入/輸出類庫njava.util包包括了Java語言中的一些低級的實用工具nava.awt包是Java語言用來構(gòu)建圖形用戶界面(GUI)的類庫njava.applet包是用來實現(xiàn)運(yùn)行于Internet瀏覽器中的Java Applet的工具類庫包是Java語言用來實現(xiàn)網(wǎng)絡(luò)功能的類庫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)境的類層次樹的根部，其他所有的類都直接或間接地為它的樹的根部，其他所有的類都直接或間接地為它的子類。該類定義了一些所有對象最基本的狀態(tài)和子類。該類定義了一些所有對象最基本的狀態(tài)和行為，包括與同類對象相比較，轉(zhuǎn)化為字符串等行為，包括與同類對象相比較，轉(zhuǎn)化為字

3、符串等等。下面我們分別進(jìn)行介紹等。下面我們分別進(jìn)行介紹(詳細(xì)用法大家可以查詳細(xì)用法大家可以查閱閱Java JDK的的API)。第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(1) equals( )n用來比較兩個對象是否相同，如果相同，則返回用來比較兩個對象是否相同，如果相同，則返回true，否則返回，否則返回false，它比較的是兩個對象狀態(tài)，它比較的是兩個對象狀態(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，因為對象，因為對象One和和anotherOne 包含相同的整數(shù)值包含相同的整數(shù)值1.第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.(2) getClass ( )ngetClass ( )方法是方法是final方法，它不能被重載。方法，它不能被重載。它返回一個對象在運(yùn)行時所對應(yīng)的它返回一個對象在運(yùn)行時所對應(yīng)的類的表示，類的表示，從從而可以得到相應(yīng)的信息。下面的方法得到并顯示而可以得到相應(yīng)的信息。下面的方法得到并顯示對象的類名：對象的類名：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)建一個類的實例，而不必在編譯時即知創(chuàng)建一個類的實例，而不必在編譯時即知道到底是哪個類。下例創(chuàng)建了一個與對象道到底是哪個類。下例創(chuàng)建了一個與對象obj具有相同類具有相同類型的一個新的實例，所創(chuàng)建的對象可以是任何類。型的一個新的實例，所創(chuàng)建的對象可以是任何類。nObject creatNewInstanceOf (ob

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

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

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

9、作。例如，Double類就提供了更多的方法來與字符串進(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類用來完成一些常用的數(shù)學(xué)運(yùn)算 npublic final static double E；/ 數(shù)學(xué)常量en public final static double PI；/ 圓周率常量npublic static double abs(double a)；/ 絕對值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)；/ 自然對數(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)境變量是平臺相關(guān)的)可使用System.getProperties()方法獲得一個 Properties類的對象，其中包含了所有可用的系統(tǒng)屬性信息可使用System.getProperty(String name)方法獲得特定系統(tǒng)屬性的屬性值在命令行運(yùn)行Java程序時可使用-D選項添加新的系統(tǒng)屬性第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7. 2 字符串n程序中需要用到的字

14、符串可以分為兩大類，一類是創(chuàng)建之后不會再做修改和變動的字符串常量；另一類是創(chuàng)建之后允許再做更改和變化的字符串。前者是String類，后者是StringBuffer類。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.2.1 String類nString 類對象保存不可修改(immutable)的Unicode字符序列 nString類的下述方法能創(chuàng)建并返回一個新的String對象: 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類對象保存可修改的Unicode字符序列構(gòu)造方法 nStringBuffer() nStringBuffer(int capacity) nStringBuffer(String initialString)實現(xiàn)修改操作的方法: nappend, insert, reverse, setCharAt, setLength.第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.2

16、.3 StringTokenizer類njava.util.StringToken類提供了對字符串進(jìn)行解析和分割的功能。比如，要對一條語句進(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、作為一個分割串。n該類的重要方法有：n public int countTokens()；/ 分割串的個數(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: 將一組對象以集合元素的形式組織到一起，在其子接口中分別實現(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接口定義了對C

19、ollection類型對象中所含元素的遍歷等增強(qiáng)處理功能n可以通過Collection接口中定義的iterator()方法獲得一個對應(yīng)的Iterator(實現(xiàn)類)對象nSet (實現(xiàn)類)對象對應(yīng)的Iterator仍然是無序的nList(實現(xiàn)類)對象對應(yīng)的ListIterator對象可以實現(xiàn)對所含元素的雙向遍歷: 使用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)于動態(tài)數(shù)組(比JDK1.0中的 ArrayList好), elementAt, nStacknVector的子類, push, pop, peeknHashtablen實現(xiàn)Map接口, 參見Properties類nEnumeratoionn用另一種方式實現(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 向量、堆棧、隊列第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.4.1 Vector向量n它對應(yīng)于類似數(shù)組的順序存儲的數(shù)據(jù)結(jié)構(gòu)，但是具有比數(shù)組更強(qiáng)大的功能。n它是允許不同類型元素共存的變長數(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)建堆棧時可以直接調(diào)用它。n（2）壓棧與彈棧操作。npublic Object push(Object item)：將指定對象壓入棧中。nPublic Object pop()：將堆棧

23、最上面的元素從棧中取出，并返回這個對象。n（3）檢查堆棧是否為空npublic boolean empty()：若堆棧中沒有對象元素，則此方法返回true，否則返回false。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.4.3 LinkedList及隊列n隊列(Queue)，也是重要的線性數(shù)據(jù)結(jié)構(gòu)。隊列遵循“先進(jìn)先出”(First In First Out，F(xiàn)IFO)的原則，固定在一端輸入數(shù)據(jù)(稱為加隊)，另一端輸出數(shù)據(jù)(稱為減隊)。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5 排序與查找第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.5.1 Arrays類nArrays類是用于對數(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è)計中常用的幾種算法，包括遍試、迭代、遞歸和回溯，這些算法屬于“通用算法”，它們在解決許多問題中都有應(yīng)用。 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6.1 遍試n在有限的范圍內(nèi)，可以對所有的值都進(jì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)行計算，每次將計算的結(jié)果再代入公式進(jìn)行計算，從而逐步逼近精確解nSqrt.java自編一個函數(shù)求平方根 nJulia.java 利用迭代公式求Julia集n迭代的基本模式 nfor(;) x = f(x); 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.6.3 遞歸n遞歸(recursive)就是一個過程調(diào)用過程本身。在遞歸調(diào)用中，一個過程執(zhí)行的某一步要用到它自身的上一步(或上幾步)的結(jié)果。 nFac.java用遞歸方法求階乘 nVonKoch.java畫畫Von_Koch曲線曲線 nCayleyTree.java 用計算機(jī)生成Cayley樹 n遞歸算法的基本模式nf(n) f(n-1); 第3章 數(shù)據(jù)運(yùn)算、流控制和數(shù)組.7.