第四章Java常用数据结构.ppt

第四章Java常用数据结构.ppt

《第四章Java常用数据结构.ppt》由会员分享，可在线阅读，更多相关《第四章Java常用数据结构.ppt（128页珍藏版）》请在冰点文库上搜索。

第四章算法与数据结构（数组、向量及字符处理）,1、数组（Array）2、向量（Vector）3、字符处理（String）4、算法：

递归、排序、查找5、复杂数据结构,程序算法数据结构,软件：

刻画现实世界，解决现实世界中的问题语言：

实现的工具算法：

问题的解的描述数据结构：

现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。

瑞士科学家沃思（NiklausWirth，1984年图灵奖得主）在1976年出版了著名的程序算法数据结构一书。

不了解施加于数据上的算法就无法决定如何构造数据，反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。

简而言之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。

1、数组一维数组：

定义,一维数组的定义方式为：

typearrayName；,其中类型（type）可以为Java中任意的数据类型，包括基本类型和类类型，数组名arrayName为一个合法的标识符，指明该变量是一个数组类型变量。

例如：

intintArray；声明了一个整型数组，数组中的每个元素为整型数据。

我们还可以定义一个类类型的数组，例如：

DatedateArray；声明了一个容纳复合数据类型Date的数组。

1、数组一维数组：

定义,与C、C+不同，Java在数组的定义中并不为数组元素分配内存，因此中不用指出数组中元素的个数，即数组长度，而且对于如上定义的一个数组是不能访问它的任何元素的。

必须经过初始化后，才能应用数组的元素。

除了这种定义数组的方式之外，java语言还提供了其他的定义形式，如下所示：

typearrayName；,1、数组一维数组：

定义,对于以上举出的例子，我们也可以这样定义：

intintArray；DatedateArray;,一维数组定义之后，必须经过初始化才可以引用。

数组的初始化分为静态初始化和动态初始化两种：

1、数组一维数组：

初始化,静态初始化：

在定义数组的同时对数组元素进行初始化，例如：

intintArray=1,2,3,4;/定义了一个含有4个/元素的int型数组。

动态初始化：

使用运算符new为数组分配空间，对于简单类型的数组，其格式如下：

typearrayName=newtypearraySize;typearrayName=newtypearraySize;,1、数组一维数组：

初始化,对于复合类型的数组，需要经过两步空间分配。

首先：

typearrayName=newtypearraySize;然后：

arrayName0=newtype（paramList）;arrayNamearraySize-1=newtype（paramList）;,例如：

StringstringArrar;/定义一个String类型的数组stringArray=newString3;/给数组stringArray分配3个应用空间，初始化每个引用值为nullstringArray0=newString（“how”）;stringArray1=newString（“are”）;stringArray2=newString（“you”）;,初始化各数组元素,1、数组一维数组：

初始化,当定义了一个数组，并用运算符new为它分配了内存空间后，就可以引用数组中的每一个元素了。

元素的引用方式为：

arrayNameindex,1、数组一维数组：

引用,index为数组下标，可以是整型常数或表达式，如：

arrayName1,arrayNamei,arrayName6*i等。

下标是0序的，即从0开始，一直到数组长度减1。

另外，与C、C+中不同，Java对数组元素要进行越界检查以保证安全性。

同时，对于每个数组都有一个属性length指明它的长度，例如：

intArray.length指明数组intArray的长度例:

模拟抽彩游戏,1、数组一维数组：

边界检查,PublicclassLotteryDrawing/模拟抽彩游戏publicstaticvoidmain（Stringargs）Stringinput=JOptionPane.showInputDialog（Howmanynumbersdoyouneedtodraw?

）;intk=Integer.parseInt（input）;input=JOptionPane.showInputDialog（Whatisthehighestnumberyoucandraw?

）;intn=Integer.parseInt（input）;/numbers用来存放123.nintnumbers=newintn;for（inti=0;inumbers.length;i+）numbersi=i+1;/result用不存放选取出的数intresult=newintk;for（inti=0;iresult.length;i+）/在0-N-1之间产生选取出的数intr=（int）（Math.random（）*n）;,/将选出的数放入resultresulti=numbersr;/movethelastelementintotherandomlocationnumbersr=numbersn-1;n-;/将result排序输出Arrays.sort（result）;System.out.println（Betthefollowingcombination.Itllmakeyourich!

）;for（inti=0;iresult.length;i+）System.out.println（resulti）;System.exit（0）;,在任何语言中，多维数组都被看作数组的数组。

比如二维数组是一个特殊的一维数组，其每一个元素又是一个一维数组。

我们主要以二维数组为例来说明，高维数组与此类似。

1、数组多维数组,二维数组的定义方式typearrayName；例如：

intintArray；,1、数组二维数组：

定义,也可以采用另一种定义方式：

typearrayName;与一维数组一样，这时对数组元素也没有分配内存空间，同样要使用运算符new来分配内存，然后才可以访问每个元素。

二维数组的初始化也分为静态和动态两种。

静态初始化：

在定义数组的同时为数组分配空间。

intintArray=1,2,2,3,3,4;不必指出数组每一维的大小，系统会根据初始化时给出的初始值的个数自动算出数组每一维的大小。

1、数组二维数组：

初始化,动态初始化：

对高维数组来说，分配内存空间有下面两种方法：

1.直接为每一维分配空间，如：

typearrayName=newtypearraylength1arraylength2例如：

inta=newint23；,1、数组二维数组：

初始化,2.从最高维开始（而且必须从最高维开始），分别为每一维分配空间，如：

Strings=newString2;s0=newString2;s1=newString3;s00=newString（“Good”）;s01=newString（“Luck”）;s10=newString（“to”）;s11=newString（“you”）;s12=newString（“!

”）;,1、数组二维数组：

初始化,二维数组的引用对二维数组中每个元素，引用方式为：

arrayNameindex1index2其中index1和index2为数组下标，为整型常数和表达式，都是0序的。

1、数组二维数组：

引用及示例,数组是用来表达一组同类型数据的数据结构,1、数组java.util.Arrays,在Java中数组是定长的，数组的大小不会动态变化,数组变量的值是数组对象实例的引用,在java.util包中的Arrays类提供了一些操作数组的方法,在java.util包中的Vector提供了动态变长数组的功能，Vector的容量可以随着需要变化,intbinarySearch（typea,typekey）数组a必须已经排序，否则返回值无意义当数组a中有重复的值时，该方法返回的值不确定如果key存在，则返回它在数组a中的位置如果不存在，则返回它的“-（插入位置-1）”voidfill（typea,typeval）voidfill（typea,intfromIndx,inttoIndex,typeval）包括afromIndx，但不包括atoIndexfromIndx=toIndex时，范围是一个空的范围,1、数组java.util.Arrays,booleanequals（typea,typea2）两个数组大小相同，并且每一个元素相等两个null数组是相等的,1、数组java.util.Arrays,voidsort（typea）voidsort（typea,intfromIndx,inttoIndex）voidsort（typea,Comparatorc）voidsort（typea,intfromIndx,inttoIndex,Comparatorc）包括afromIndx，但不包括atoIndexfromIndx=toIndex时，范围是一个空的范围排序算法都具有n*log（n）的计算复杂性，效率高排序算法都保证稳定，即排序算法不会改变相等元素的顺序对不同类型的数组，算法的实现并不完全相同可以用自己的Comparator对象声明自定义的顺序,1、数组java.util.Arrays,java.lang.Systemvoidarraycopy（Objectsrc,intsrc_position,Objectdst,intdst_position,intlength）范围不能越界可对任何同类型的数组进行复制数组复制过程中做严格的类型检查更详细的内容参见JDK文档,1、数组数组的复制,向量（Vector）是java.util类包提供的一个工具类。

它对应于类似数组的顺序存储的数据结构，但是具有比数组更强大的功能。

它是允许不同类型元素共存的变长数组。

每个Vector类的对象可以表达一个完整的数据序列。

Vector类的对象不但可以保存顺序的一列数据，而且还提供了许多有用的方法来操作和处理这些数据。

另外，Vector类对象所表达的序列中元素的个数是可变的，即Vector实现了变长数组。

2、向量,Java中的数组只能保存固定数目的元素，且必须把所有需要的内存单元一次性的申请出来，而不能先创建数组再追加数组元素数量，为了解决这个问题Java中引入了向量类Vector。

Vector也是一组对象的集合，但相对于数组，Vector可以追加对象元素数量，可以方便的修改和维护序列中的对象。

2、向量,向量比较适合在如下情况下使用：

1.需要处理的对象数目不定，序列中的元素都是对象或可以表示为对象。

2.需要将不同类的对象组合成一个数据序列。

3.需要做频繁的对象序列中元素的插入和删除。

4.经常需要定位序列中的对象和其他查找操作。

5.在不同的类之间传递大量的数据。

Vector类的方法相对于数组要多一些，但是使用这个类也有一定的局限性，例如其中的对象不能是简单数据类型等。

2、向量,Vector类有三个构造函数：

Vector（）：

构造一个空的向量Vector（intcapacity）：

以指定的存储容量构造一个空的向量Vector（intcapacity,intcapacityIncrement）：

以指定的存储容量和容量增量构造一个空的Vector。

例如：

VectorMyVector=newVector（100,50）；这个语句创建的MyVector向量序列初始有100个元素的空间，以后一旦使用殆尽则以50为单位递增，使序列中元素的个数变化成150，200，。

在创建Vector序列时，不需要指明序列中元素的类型，可以在使用时确定。

2、向量创建向量类的对象,有两种添加元素的方法：

addElement（Objectobj）：

将新元素添加到序列尾部。

insertElementAt（Objectobj,intindex）：

将新元素插入到指定位置。

2、向量向向量序列中添加元素,下面是使用这两种方法的例子：

VectorMyVector=newVector（）；for（inti=1;i=10;i+）MyVector.addElement（newRandom（）;MyVector.insertElementAt（middle,5）;,2、向量向向量序列中添加元素,使用以下方法修改或删除向量序列中的元素：

1.setElementAt（Objectobj,intindex）将向量序列index位置处的对象元素设置成为obj，如果这个位置原来有元素则被覆盖。

2.removeElement（Objectobj）删除向量序列中第一个与指定的obj对象相同的元素，同时将后面的元素前提，补上空位。

这个方法返回的是布尔值。

3.removeElementAt（intindex）删除index指定位置处的元素，同时将后面的元素前提。

2、向量修改或删除向量序列中的元素,4.removeAllElements（）清除向量序列中的所有元素。

下例中先创建了一个Vector，再删除掉其中的所有字符串对象“to”。

VectorMyVector=newVector（100）;for（inti=0;i10;i+）MyVector.addElement（“welcome”）;MyVector.addElement（“to”）;MyVector.addElement（“beijing”）;while（MyVector.removeElement（“to”）;,2、向量修改或删除向量序列中的元素,常用于查找向量序列中某元素的方法如下：

1.ObjectelementAt（intindex）返回指定位置处的元素。

一个要注意的问题：

由于返回的是Object类型的对象，在使用之前通常需要进行强制类型转换，将返回的对象引用转换成Object类的某个具体子类的对象。

例如：

Stringstr=（String）MyVector.elementAt（0）;2.booleancontains（Objectobj）检查向量序列中是否包含指定的对象元素obj。

2、向量查找向量序列中的元素,3.intindexOf（Objectobj,intstart_index）从指定的start_index位置开始向后搜索，返回所找到的第一个与指定对象obj相同的元素的下标位置。

若指定的对象不存在，则返回1。

4.intlastIndexOf（Objectobj,intstart_index）从指定的start_index位置开始向前搜索，返回所找到的第一个与指定对象obj相同的元素的下标位置。

若指定的对象不存在，则返回1。

例如：

inti=0;While（i=MyVector.indexOf（“welcome”,i）!

=-1）System.out.println（i）;,2、向量查找向量序列中的元素,capacity（）：

返回Vector的容量clone（）：

建立Vector的备份copyInto（Object）：

把Vector中的元素拷贝到一个数组中firstElement（）：

返回第一个元素lastElement（）：

返回最后一个元素isEmpty（）：

判断是否为空setSize（intsize）：

设置Vector的大小size（）：

返回Vector中元素的数量trimToSize（）：

将Vector的容量下调至最小值,2、向量Vector中的其他方法,2、向量,使用Vector时，一个需要特别注意的问题就是要先创建后使用。

如果不先使用new算法利用构造函数创建Vector类的对象，而直接使用Vector的方法，如：

addElement（）等方法，则可能造成堆栈溢出或使用null指针等异常，妨碍程序的正常运行。

数组列表,一、定义ArrayList对象newArrayList（）;例：

ArrayListstaffnewArrayList（）;API：

java.util.ArrayListArrayList（）构造一个空数组列表ArrayList（intc）构造一个具有指定容量的空数组列表,二、添加新元素API：

booleanadd（Objectobj）把元素obj追加到数组列表的结尾例：

staff.add（newemployee（）;三、统计个数API：

intsize（）返回数组列表中当前元素个数例：

staff.size（）;,数组列表,四、调整大小把数组列表的存贮空间调整到当前大小API：

voidtrimtosize（）五、访问API：

voidset（intindex,Objectobj）将obj放入数组列表index位置Objectget（intindex）获得指定位置index的元素值,数组列表,六、增加与删除booleanadd（intn,Objectobj）在第n个位置插入objObjectremove（n）;将第n个位置存放的对象删除例：

staff.add（5,harry）;e=（Employee）staff.remove（5）;,数组列表,3、字符串,字符串是字符的序列，它是组织字符的基本数据结构，从某种程度上来说有些类似于字符的数组。

在Java中，字符串被当作对象来处理。

程序中需要用到的字符串可以分为两大类，一类是创建之后不会再做修改和变动的字符串常量；另一类是创建之后允许再做更改和变化的字符串变量。

对于字符串常量，由于程序中经常需要对它做比较，搜索之类的操作，所以通常把它放在一个具有一定名称的对象之中，由程序对该对象完成上述操作。

在Java中，存放字符串常量的对象用String类，对于字符串变量，由于程序中经常需要对它做添加，插入，修改等操作，一般存放在StringBuffer类的对象中。

3、字符串String,字符串常量使用双引号括住的一串字符，比如：

Helloworld!

Java编译器自动为每一个字符串常量生成一个String类的实例，因此可以用字符串常量直接初始化一个String对象，如：

Strings=Helloworld!

;,要创建类String的一个对象并进行初始化，需要调用类String的构造方法。

类String中提供了下面的一些构造方法：

String（）：

无参数的缺省的构造方法用来创建一个空串。

Strings=newString（）;String（Stringvalue）：

利用已经存在的字符串常量创建一个新的String对象，该对象的内容与给出的字符串常量一致。

Strings=newString（“hello”）;String（charvalue）：

通过给构造方法传递一个字符数组可以创建一个非空串。

charchars=a,b,c;Strings=newString（chars）;,3、字符串String：

创建,String（char,intstartIndex,intnumChars）：

这种方法用来创建一个非空串，并且指明所创建的字符串在字符数组中的起始地址以及所包含的字符个数。

charchars=a,b,c,d,e,f;Strings=newString（chars,2,3）;该方法生成的串s为“cde”。

（注意数组的下标从0开始）,3、字符串String：

创建,1.lengthpublicintlength（）此方法返回字符串的字符个数，如：

Strings=abc;System.out.println（s.length（）;则将显示字符个数为3。

3、字符串String：

基本方法,2.charAtpubliccharcharAt（intindex）该方法返回字符串中index位置上的字符，其中index值的范围是0length-1。

3.getChars如果要从字符串中提取一个以上的字符，则可以用此方法：

publicvoidgetchars（intsrcbegin,intend,charbuf,intdstbegin）其中，srcbegin为要提取的第一个字符在源串中的位置，end为要提取的最后一个字符在源串中的位置，字符数组buf存放目的字符串，dstbegin为提取的字符串在目的串中的起始位置。

3、字符串String：

基本方法,4.getbytespublicvoidgetbytes（intsrcbegin,intend,bytebyt,intdstbegin）类似于上一个方法，只是串中的字符均用8位表示，参数及用法同上。

5.indexOf和lastIndexOf为了在给定的字符串中检索特定的字符或子串，类String提供了上面两种方法，并通过方法重写更方便的处理这类问题。

这两种方法中，如果查找成功，则返回匹配成功的字符的位置，如果没有查找到，则都返回-1。

intindexOf（intch）intlastIndexOf（intch）返回字符ch在字符串中出现的第一个和最后一个位置。

3、字符串String：

基本方法,intindexOf（Stringstr）intlastindexOf（Stringstr）返回子串str中第一个字符在字符串中出现的始末位置。

intindexOf（intch,intfromIndex）intlastIndexOf（intch,intfromIndex）返回字符ch在字符串中位置fromIndex以后出现的始末位置。

intindexOf（Stringstr，intfromIndex）intlastIndexOf（Stringstr,intfromIndex）返回子串str中的第一个字符在字符串中位置fromIndex以后出现的始末位置。

3、字符串String：

基本方法,6.在Java中，运算符“”可以用来实现字符串的连接，如：

Strings=“Heis”+age+“yearsold.”假设整数型变量age的值为15，那么，s的值为“Heis15yearsOld”。

pareTopublicintcompareTo（Stringstr）该方法按字典次序比较两个字符串的大小，如果源串较小，则返回一个小于0的值，如相等则返回0，否则返回一个大于0的值。

3、字符串String：

基本方法,8.regionMatchesbooleanregionMatches（inttoffset,Stringother,intooffset,intlen）booleanregionMatches（booleanignoreCase,inttoffset,Stringother,intooffset,intlen）上述两个方法都是用来进行模式匹配的，匹配成功则返回true，否则返回false.其中,toffset和ooffset分别指明当前字符串和参数字符串中所要比较的子串的起始索引位置，len指明比较的长度，而ignoreCase指明比较时是否区分大小写。

对于第一种方法，比较是区分大小写的。

Ex：

regionMatches（2,abcdef,2,3）,此时“cde”为模式，与indexOf相似。

3、字符串String：

基本方法,9.equals和equalsIgnoreCasepublicbooleanequals（objectstr）publicbooleanequalsIgnoreCase（objectstr）判断两个字符串是否相等，则可以用此方法。

相等则返回true，不等则返回false，两种方法的区别在于equalsIgnoreCase不