Java05-工具类与算法.pptx

《Java05-工具类与算法.pptx》由会员分享，可在线阅读，更多相关《Java05-工具类与算法.pptx（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5讲讲工具类与算法工具类与算法JavaJava类库类库语言基础类语言基础类数据结构类数据结构类查找与排序查找与排序Copyright 2011Keerqin All Rights Reserved.Java类库类库Java类库是系统提供的已实现的标准类的集合类库是系统提供的已实现的标准类的集合Java编程的编程的API（ApplicationProgramInterface）系统系统定义好的类根据实现的功能定义好的类根据实现的功能不同划分不同划分成不同的集合，每成不同的集合，每个集合是一个包，合称为类库。个集合是一个包，合称为类库。基础类库（基础类库（JFC）SUNAPI应用程序编程接

2、口应用程序编程接口面向过程语言面向过程语言函数库（子程序包）函数库（子程序包）面向对象语言面向对象语言类库类库Copyright 2011Keerqin All Rights Reserved.Java类库结构类库结构java.langSystem、Math、Thread、基本数据类型类、基本数据类型类.java.util向量、栈、日期向量、栈、日期java.io（用于输入输出）（用于输入输出）（用于网络编程）（用于网络编程）java.applet（编写（编写applet小程序）小程序）java.awt（编写图形用户界面）（编写图形用户界面）Copyright 2011Keerqin All

3、Rights Reserved.Object类类类层次的根，每一个类都是它的子类。类层次的根，每一个类都是它的子类。构造方法：构造方法：Object()一般方法：一般方法：Objectclone()生成当前对象的一个拷贝。生成当前对象的一个拷贝。booleanequals(Objectobj)比较两个对象是比较两个对象是否相同。否相同。ClassgetClass()获取当前对象所属的类信息获取当前对象所属的类信息StringtoString()用来返回当前对象本身的有关用来返回当前对象本身的有关信息信息Copyright 2011Keerqin All Rights Reserved.数学运算

4、的数学运算的Math类类属性属性publicfinalstaticdoubleE;/数学常量数学常量epublicfinalstaticdoublePI;/圆周率常量圆周率常量方法（均为静态方法）方法（均为静态方法）publicstaticintabs(inti);求绝对值求绝对值publicstaticdoublesin(doublea);/sin函数函数publicstaticdoublelog(doublea);/log函数函数publicstaticdoublemax(doublea,doubleb);publicstaticdoublepow(doublea,doubleb);pub

5、licstaticdoublerandom();/产生产生01之间随机数之间随机数Copyright 2011Keerqin All Rights Reserved.数学运算的数学运算的Math类类publicstaticdoubleexp(doublea);publicstaticintround(floata);publicstaticdoublesqrt(doublea);Copyright 2011Keerqin All Rights Reserved.Math类例类例publicclassTestpublicstaticvoidmain(Stringargs)System.out.p

6、rintln(Math.E);/2.7182818System.out.println(Math.PI);/3.14159265System.out.println(Math.sqrt(9.08);/3.0133038System.out.println(Math.pow(2,3);/8.0System.out.println(Math.round(99.6);/100System.out.println(Math.abs(-8.09);/8.09System.out.println(Math.random();/0.14System.out.println(Math.random();/0.

7、69随机数Copyright 2011Keerqin All Rights Reserved.System类类实现了用户访问系统资源时的系统无关编程接口实现了用户访问系统资源时的系统无关编程接口属性标准输入输出属性标准输入输出publicstaticInputStreaminpublicstaticPrintStreamoutpublicstaticPrintStreamerr方法获取系统时间信息方法获取系统时间信息publicstaticlongcurrentTimeMillis();获取自获取自1970年年1月月1日零时至当前系统时刻的微秒数日零时至当前系统时刻的微秒数方法强制方法强制Ja

8、va虚拟机退出运行状态，并把状态信息虚拟机退出运行状态，并把状态信息status返回给运行返回给运行虚拟机的操作系统虚拟机的操作系统publicstaticvoidexit(intstatus);例：例：System.exit(0)；Copyright 2011Keerqin All Rights Reserved.System类类方法取系统属性方法取系统属性staticStringgetProperty(Stringkey)例例:显示显示classpathpublicclassTestpublicstaticvoidmain(Stringargs)System.out.println(Sys

9、tem.getProperty(java.class.path);Copyright 2011Keerqin All Rights Reserved.向量类向量类-Vectorjava.util.Vector实现链式存储结构实现链式存储结构适合于如下的情况适合于如下的情况需要处理的对象数目不定需要处理的对象数目不定序列中元素都是对象，而不是基本数据类型的量序列中元素都是对象，而不是基本数据类型的量需要做频繁的元素插入和删除需要做频繁的元素插入和删除需要定位序列中的对象或其他查找操作需要定位序列中的对象或其他查找操作 对象对象对象对象 0 1 2 3Copyright 2011Keerqin A

10、ll Rights Reserved.创建向量类对象创建向量类对象创建向量类的对象创建向量类的对象VectormyVector=newVector();创建空的向量对象（初始容量为创建空的向量对象（初始容量为10）优化存储管理优化存储管理VectormyVector=newVector(100);创建空的向量对象（初始容量为创建空的向量对象（初始容量为100）VectormyVector=newVector(100,50);创建空的向量对象（初始容量为创建空的向量对象（初始容量为100，增量为，增量为50）Copyright 2011Keerqin All Rights Reserved.向量

11、元素操作向量元素操作追加元素追加元素add(Objectelement)插入元素插入元素add(intindex,Objectelement)修改向量中的元素修改向量中的元素set(intindex,Objectelement)删除向量中的指定元素删除向量中的指定元素Objectremove(intindex)(返回被删元素）返回被删元素）Booleanremove(Objectelement)removeRange(inti,intj)(包括包括i但不包括但不包括j)Copyright 2011Keerqin All Rights Reserved.向量元素操作向量元素操作取出向量中的指定元

12、素取出向量中的指定元素Objectget(intindex)测试对象在向量中是否存在测试对象在向量中是否存在booleancontains(Objectelement)查找指定元素的位置查找指定元素的位置intindexOf(Objectelement)intindexOf(Objectelement,intfromIndex)返回一个包含向量中所有元素的对象数组返回一个包含向量中所有元素的对象数组ObjecttoArray()Copyright 2011Keerqin All Rights Reserved.获取向量信息获取向量信息清空向量清空向量(删除所有元素）删除所有元素）clear()

13、测试向量是否为空测试向量是否为空booleanisEmpty()当前向量元素数量当前向量元素数量intsize()向量当前容量向量当前容量intcapacity()Copyright 2011Keerqin All Rights Reserved.向量例向量例importjava.util.*;publicclassTestpublicstaticvoidmain(Stringargs)Vectorv1=newVector();for(inti=0;i15;i+)v1.add(newString(Integer.toString(i);System.out.println(v1.get(2);

14、/输出：输出：2System.out.println(v1.contains(3);/输出：输出：trueSystem.out.println(v1.indexOf(4);/输出：输出：4v1.set(2,newString(wang);System.out.println(v1.get(2);/输出：输出：wangSystem.out.println(v1.size();/输出：输出：15System.out.println(v1.capacity();/输出：输出：20System.out.println(v1.isEmpty();/输出：输出：falsev1.clear();System

15、.out.println(v1.isEmpty();/输出：输出：trueCopyright 2011Keerqin All Rights Reserved.日期类日期类Calendar抽象类，在抽象类，在Date对象和一组整数域之间进行转换：对象和一组整数域之间进行转换：YEAR,MONTH,DAY,HOUR,Calendarc=Calendar.getInstance();intc.get(Calendar.YEAR)intc.get(Calendar.MONTH)（1月为月为0）intc.get(Calendar.DATE)intc.get(Calendar.HOUR)intc.get(

16、Calendar.MINUTE)intc.get(Calendar.SECOND)c.set(Calendar.YEAR,2000)c.set(Calendar.MONTH,10)(11月月)c.set(Calendar.DATE,7)c.set(2000,10,7)Copyright 2011Keerqin All Rights Reserved.日期类日期类Calendar例例importjava.util.*;publicclassTestpublicstaticvoidmain(Stringargs)Calendarc=Calendar.getInstance();System.out

17、.println(c.get(Calendar.YEAR)+年年+(c.get(Calendar.MONTH)+1)+月月+c.get(Calendar.DATE)+日日);System.out.println(c.get(Calendar.HOUR)+时时+c.get(Calendar.MINUTE)+分分+c.get(Calendar.SECOND)+秒秒);c.set(2008,7,8);/2008年年8月月8日日System.out.println(c.get(Calendar.YEAR)+年年+(c.get(Calendar.MONTH)+1)+月月+c.get(Calendar.D

18、ATE)+日日);Copyright 2011Keerqin All Rights Reserved.堆栈堆栈Stack是是Vector的子类的子类构造函数构造函数Stack()建立一个新的栈建立一个新的栈方法方法booleanempty()测试栈是否空测试栈是否空Objectpeek()查看栈顶元素查看栈顶元素Objectpop()弹栈（出栈）弹栈（出栈）Objectpush(Objectitem)压栈（进栈）压栈（进栈）intsearch(Objectitem)查找栈中元素，返回距栈顶位置查找栈中元素，返回距栈顶位置（栈顶位置为（栈顶位置为1）栈底栈顶弹栈压栈堆栈例堆栈例-表达式计算表达式

19、计算#2*(3+5 8 16-4 122*（3+）5-4#操作数栈 s1 操作符栈 s2Copyright 2011Keerqin All Rights Reserved.排序算法排序算法冒泡排序算法冒泡排序算法基本思路：把当前数据序列中的各相邻数据两两比较，发现任何一基本思路：把当前数据序列中的各相邻数据两两比较，发现任何一对数据间不符合要求的升序或降序关系则立即调换它们的顺序，从对数据间不符合要求的升序或降序关系则立即调换它们的顺序，从而保证相邻数据间符合升序或降序的关系。而保证相邻数据间符合升序或降序的关系。选择排序选择排序插入排序插入排序利用系统类实现排序利用系统类实现排序Arrays

20、类提供了多种操作数组的方法，包括查找和排序类提供了多种操作数组的方法，包括查找和排序publicstaticvoidsort(inta)/对整型数组排序对整型数组排序publicstaticvoidsort(floata)/对浮点数数组排序对浮点数数组排序publicstaticvoidsort(chara)/对字符数组进行排序对字符数组进行排序Copyright 2011Keerqin All Rights Reserved.排序例排序例importjava.util.Arrays;publicclassTestSysSortpublicstaticvoidmain(Stringargs)i

21、ntarray_int=4,-5,23,7,0,66,37,365,-22,4;/整型数组整型数组Arrays.sort(array_int);/调用调用Arrays类的整型数组排序方法类的整型数组排序方法for(inti=0;iarray_int.length;i+)System.out.print(array_inti+);System.out.println();chararray_char=T,s,i,n,g,h,u,a;/字符数组字符数组Arrays.sort(array_char,2,5);/对字符组排序，只排第对字符组排序，只排第24个元素个元素for(inti=0;iarray

22、_char.length;i+)System.out.print(array_chari+);System.out.println();/字符串数组字符串数组Stringarray_str=grape,banana,pear,apple,orange;Arrays.sort(array_str);/调用调用sort(Object)方方法对字符串数组排序法对字符串数组排序for(inti=0;iarray_str.length;i+)System.out.print(array_stri+);Copyright 2011Keerqin All Rights Reserved.查找算法查找算法顺序

23、查找顺序查找对半查找对半查找利用系统类实现查找利用系统类实现查找Arrays类几个查找方法的定义：类几个查找方法的定义：publicstaticintbinarySearch(inta,intkey)publicstaticintbinarySearch(floata,floatkey)publicstaticintbinarySearch(Objecta,Objectkey)Copyright 2011Keerqin All Rights Reserved.查找例查找例importjava.util.Arrays;publicclassTestSysSearchpublicstaticvoi

24、dmain(Stringargs)inti;intarray_int=4,-5,23,7,0,66,37,365,-22,4;Arrays.sort(array_int);/调用调用Arrays类排序方法排序类排序方法排序i=Arrays.binarySearch(array_int,0);/调用调用Arrays类查找方法类查找方法System.out.println(0是整型数组下标为是整型数组下标为+i+的元素的元素);Stringarray_str=grape,banana,pear,apple,orange;Arrays.sort(array_str);/调用调用Arrays类排序方法

25、排序类排序方法排序i=Arrays.binarySearch(array_str,apple);/Arrays类查找方法类查找方法System.out.println(apple是字符串数组下标为是字符串数组下标为+i+的元素的元素);Copyright 2011Keerqin All Rights Reserved.查找例查找例System.out.println(-下面程序用于测试查找方法返回值的含义下面程序用于测试查找方法返回值的含义-);chararray_char=i,j,k,p,q,r,s;/已排序已排序i=Arrays.binarySearch(array_char,a);Sys

26、tem.out.println(查找对象比最小元素还小，方法返回值是：查找对象比最小元素还小，方法返回值是：+i);i=Arrays.binarySearch(array_char,j);System.out.println(查找对象找到，查找对象找到，j是数组下标为是数组下标为+i+的元素的元素);i=Arrays.binarySearch(array_char,m);System.out.println(查找对象不存在，但位于两个元素之间，方法返回值是：查找对象不存在，但位于两个元素之间，方法返回值是：+i);i=Arrays.binarySearch(array_char,x);Syst

27、em.out.println(查找对象比最大元素还大，方法返回值是：查找对象比最大元素还大，方法返回值是：+i);表驱动法表驱动法Table-DrivenMethodsCopyright 2011Keerqin All Rights Reserved.实例：判断字符的种类实例：判断字符的种类Copyright 2011Keerqin All Rights Reserved.解释和评论解释和评论上例是使用复杂逻辑对字符分类，把字符划上例是使用复杂逻辑对字符分类，把字符划分为字母、标点符号和数字。使用的语言是分为字母、标点符号和数字。使用的语言是JAVA可以看出，这种比较可以看出，这种比较“直观直

28、观”的编程方法的的编程方法的逻辑判断非常的复杂。逻辑判断非常的复杂。如果功能要求做一个简单的改动，那么，就如果功能要求做一个简单的改动，那么，就需要对代码进行改动需要对代码进行改动,Copyright 2011Keerqin All Rights Reserved.换一种思路解决：表驱动法换一种思路解决：表驱动法如果用一个查询表（如果用一个查询表（lookuptable），就可以），就可以把每个字符的类型保存在一个用字符编码的数把每个字符的类型保存在一个用字符编码的数组里。那么上述复杂的逻辑就可以替换为：组里。那么上述复杂的逻辑就可以替换为：charTypecharTypeTableinput

29、Char;前提条件是已经建立好了前提条件是已经建立好了charTypeTable数组数组Copyright 2011Keerqin All Rights Reserved.优势很明显，优势很明显，适当的使用表驱动法，生成的代码会比复杂适当的使用表驱动法，生成的代码会比复杂的逻辑代码更简单、更容易修改，而且效率的逻辑代码更简单、更容易修改，而且效率会更高。会更高。Copyright 2011Keerqin All Rights Reserved.表驱动法是什么表驱动法是什么?是一种编程模式（是一种编程模式（scheme）从表里面查找信息而不使用逻辑语句（从表里面查找信息而不使用逻辑语句（if和和

30、else）凡是可以通过逻辑语句来选择的事物，都可以通凡是可以通过逻辑语句来选择的事物，都可以通过查表来选择过查表来选择对于简单的情况，使用逻辑语句更为容易和直白，对于简单的情况，使用逻辑语句更为容易和直白，对于复杂的逻辑链，查表法有其不可替代的优势对于复杂的逻辑链，查表法有其不可替代的优势Copyright 2011Keerqin All Rights Reserved.使用表驱动法的两个重要问题使用表驱动法的两个重要问题1、怎样从表中查询条目？、怎样从表中查询条目？直接访问（直接访问（Directaccess）索引访问（索引访问（Indexedaccess）阶梯访问（阶梯访问（Stair-s

31、tepaccess）2、在表里应该存些什么？、在表里应该存些什么？数据（数据（data）动作（动作（action）实现该动作的子程序的引用（例如函数指针）实现该动作的子程序的引用（例如函数指针）其他其他Copyright 2011Keerqin All Rights Reserved.直接访问表（直接访问表（Directaccess）通过查询表，直接找到目标数据通过查询表，直接找到目标数据IfthenElseifElseifElseifElseifElseifCopyright 2011Keerqin All Rights Reserved.如何根据月份的不同，确定每个月的天数？如何根据月份的

32、不同，确定每个月的天数？大多数程序员的第一反应是如大多数程序员的第一反应是如下代码下代码(幸亏一年只有幸亏一年只有12个月个月)：if(month=1)thendays=31elseif(month)=2thendays=28elseif(month)=3thendays=31elseif(month)=4thendays=30elseif(month)=5thendays=31elseif(month)=6thendays=30elseif(month)=7thendays=31elseif(month)=8thendays=31elseif(month)=9thendays=30elsei

33、f(month)=10thendays=31elseif(month)=11thendays=30elseif(month)=12thendays=31EndIfCopyright 2011Keerqin All Rights Reserved.直接访问表（直接访问表（DirectAceessTables）实现同样功能的一种更简单、更容易修改的方法实现同样功能的一种更简单、更容易修改的方法是把这些数据到一张表里。是把这些数据到一张表里。intdaysPerMonth=31,28,31,30,31,30,31,31,30,31,30,31;daysdaysPerMonthmonth-1;现在你无

34、需再写那条长长的现在你无需再写那条长长的if语句了，只需一条简语句了，只需一条简单的数组访问即可。如果考虑闰年怎么办？单的数组访问即可。如果考虑闰年怎么办？daysdaysPerMonth(month-1,LeapYearIndex();LeapYearIndex()的取值要么为的取值要么为0，要么为，要么为1这种查询表就是直接访问表这种查询表就是直接访问表Copyright 2011Keerqin All Rights Reserved.索引访问表索引访问表（Indexedaccess）先用一个基本类型的数据从一张索引表中查先用一个基本类型的数据从一张索引表中查处一个键值，再用这一键值查出目

35、标数据处一个键值，再用这一键值查出目标数据优点优点如果查询表中每条记录都很大，如果查询表中每条记录都很大，索引数组所用的空间索引数组所用的空间 主查询表所用的空间主查询表所用的空间即使所使用的内存空间相同，操作索引记录也即使所使用的内存空间相同，操作索引记录也会更快捷会更快捷Copyright 2011Keerqin All Rights Reserved.索引访问表索引访问表查询表索引（基本为空）查询表本身（基本为满）Copyright 2011Keerqin All Rights Reserved.阶梯访问表阶梯访问表（Stair-stepaccess）表中的记录对于不同的数据范围有效，而

36、不表中的记录对于不同的数据范围有效，而不是对不同的数据点有效是对不同的数据点有效Copyright 2011Keerqin All Rights Reserved.总结：表驱动法的实质总结：表驱动法的实质实际上，表驱动法就是状态机理论在程序设计领实际上，表驱动法就是状态机理论在程序设计领域的一个实际应用，用于处理需要复杂域的一个实际应用，用于处理需要复杂if/else，switch等逻辑判断的时候等逻辑判断的时候.表提供了一种复杂的逻辑和继承结构的替换方案。表提供了一种复杂的逻辑和继承结构的替换方案。如果某个应用程序的逻辑或者继承树关系非常复如果某个应用程序的逻辑或者继承树关系非常复杂，那么可以试试通过查询表来加以简化。杂，那么可以试试通过查询表来加以简化。总的来说，表驱动法是利用表来存储解决问题的总的来说，表驱动法是利用表来存储解决问题的逻辑，用空间换时间。逻辑，用空间换时间。Copyright 2011Keerqin All Rights Reserved.啰嗦几句啰嗦几句看一些算法是很有益处的看一些算法是很有益处的CodeComplete是一本好书是一本好书