java2008_ch04数组字符串向量和哈希表.ppt

《java2008_ch04数组字符串向量和哈希表.ppt》由会员分享，可在线阅读，更多相关《java2008_ch04数组字符串向量和哈希表.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Java程序设计程序设计ProgramminginJava谷勇浩谷勇浩北京邮电大学北京邮电大学计算机学院计算机学院第第4章章数组、字符串、向量与哈希表数组、字符串、向量与哈希表本章内容概要本章内容概要当需要处理当需要处理大量数据大量数据时，可以考虑利用数组或向时，可以考虑利用数组或向量。量。数组数组元素的元素的个数个数在数组对象创建之后在数组对象创建之后不能改变不能改变向量向量元素的元素的个数个数可以动态发生可以动态发生变化变化，但需要一定时间，但需要一定时间利用利用HashHash表表可以可以提高提高访问或查找元素的访问或查找元素的效率效率，但，但是需要较大的是需要较大的空间代价空间代价。字

2、符串和字符串缓冲区都可以包含字符序列，但字符串和字符串缓冲区都可以包含字符序列，但都不是字符数组。都不是字符数组。任何一种类型的数据都可以转化成字符串，而且任何一种类型的数据都可以转化成字符串，而且字符字符串对象串对象一旦创建，其所包含的字符序列就一旦创建，其所包含的字符序列就不能发生变不能发生变化化。如果需要频繁如果需要频繁改变字符序列改变字符序列，可采用，可采用字符串缓冲区字符串缓冲区，从而提高字符序列的处理效率。从而提高字符序列的处理效率。本章总体纲要本章总体纲要数组数组字符串字符串字符串缓冲区字符串缓冲区向量向量哈希表哈希表数组数组数组类型是一种数组类型是一种引用数据类型引用数据类型，

3、它是由相，它是由相同类型的若干项同类型的若干项数据数据组成，同时包括成员组成，同时包括成员域域length（表示数组长度）。（表示数组长度）。例如例如:publicstaticvoidmain(Stringargs)其中其中args是是String类型的数组类型的数组占用连续的内存地址占用连续的内存地址数组的静态性数组的静态性一旦创建就不能修改数组的长度一旦创建就不能修改数组的长度一维数组声明一维数组声明一维数组变量的声明格式有如下两种一维数组变量的声明格式有如下两种:(1)数组元素的数据类型数组元素的数据类型变量名变量名;(2)数组元素的数据类型数组元素的数据类型变量名变量名;示例示例:in

4、tc;Stringnames;intc;Stringnames;一维数组创建对象一维数组创建对象数组对象的数组对象的两种创建形式：两种创建形式：new数组元素的数据类型数组元素的数据类型数组元素的个数数组元素的个数；charc=newchar5;数组元素的数据类型数组元素的数据类型变量名变量名数组元素数组元素1，数组元素，数组元素2，数组元素，数组元素n;charc=a,b,c,d,e;示例示例intc=newint12;c是数组名是数组名如何获得数组的长度如何获得数组的长度?c.length第一个数组元素的下标为第一个数组元素的下标为0使用数组可以通过数组名与下标使用数组可以通过数组名与下标

5、每个数组元素类似于普通的变量每个数组元素类似于普通的变量c0=3;c0+=5;-45-456 60 0727215431543-89-890 06262-3-31 16453645378781212c 1 c 1 c 2 c 2 c 4 c 4 c 3 c 3 c 5 c 5 c 6 c 6 c 7 c 7 c 8 c 8 c 9 c 9 c 10 c 10 c 11 c 11 c 0 c 0 c.length下标下标有时也称为索引有时也称为索引必须是整数或整数表达式必须是整数或整数表达式,例如例如:c11示例示例:含有运算符的下标表达式含有运算符的下标表达式:if(x=3)t=(c5-2=c

6、3)&(cx=c3);/t=true内存分配内存分配Java数组实际上也是数组实际上也是对象对象，所以可通过，所以可通过new关关键字来创建键字来创建示例示例:intc;/声明声明c=newint12;/创建对象，并分配内存创建对象，并分配内存声明时不必指定数组的大小声明时不必指定数组的大小上面的两个语句可以简化成一个语句上面的两个语句可以简化成一个语句intc=newint12;或者或者intc=45，6，0，72，1543，-89，0，62，-3，1，6453，78数组元素的默认值及初始化数组元素的默认值及初始化基本数据类型的元素默认值为基本数据类型的元素默认值为0或或false引用数据类

7、型的元素默认值为引用数据类型的元素默认值为null可以采用循环结构初始化数组可以采用循环结构初始化数组示例示例:doublesquares;squares=newdouble100;for(inti=0;isquares.length;i+)squaresi=i*i;通过初始化语句创建数组通过初始化语句创建数组Java语言允许通过数组的初始化语句创语言允许通过数组的初始化语句创建数组建数组示例示例:intn=10,20,30,40,50;上面语句创建了一个含有五个元素的数组上面语句创建了一个含有五个元素的数组下标值分别为下标值分别为0,1,2,3,4这时不需要运算符这时不需要运算符new注意事

8、项注意事项当通过循环遍历数组时当通过循环遍历数组时下标永远不要低于下标永远不要低于0下标永远要比数组元素个数小下标永远要比数组元素个数小当数组下标出错，当数组下标出错，Java产生产生ArrayIndexOutOfBoundsExceptionJava抛出异常抛出异常在第在第6章讲解章讲解多维数组多维数组最常用的多维数组是二维数组最常用的多维数组是二维数组inta=newint34;二维数组可以理解成如下图示的表格二维数组可以理解成如下图示的表格a 0 0 a 0 0 a 1 0 a 1 0 a 2 0 a 2 0 a 0 1 a 0 1 a 1 1 a 1 1 a 2 1 a 2 1 a 0

9、 2 a 0 2 a 1 2 a 1 2 a 2 2 a 2 2 a 0 3 a 0 3 a 1 3 a 1 3 a 2 3 a 2 3 行的下标值行的下标值列的下标值列的下标值示例示例1类似于一维数组进行二维数组的声明、创建类似于一维数组进行二维数组的声明、创建(内存分配内存分配)与初始化与初始化示例示例:classJ_FillArraypublicstaticvoidmain(Stringargs)intmatrix=newint45;for(introw=0;row4;row+)for(intcol=0;col5;col+)matrixrowcol=row+col;/内部内部for循环结

10、束循环结束/外部外部for循环结束循环结束/方法方法main结束结束/类类J_FillArray结束结束示例示例2通过初始化语句创建数组通过初始化语句创建数组示例示例:doublec=1.0,2.0,3.0,4.0,0.0,1.0,0.0,0.0,0.0,0.0,1.0,0.0;注意事项注意事项JavaJava的多维数组实际上是的多维数组实际上是数组的数组数组的数组即创建以数组为元素的数组即创建以数组为元素的数组意味着意味着:二维数组的每一行可以具有不同的二维数组的每一行可以具有不同的列数列数示例示例:intint a ;a ;a=a=new intnew int 3 ;3 ;/allocat

11、e rows/allocate rowsa 0 =a 0 =new intnew int 3;3;/allocate row 0/allocate row 0a 1 =a 1 =new intnew int 2;2;/allocate row 1/allocate row 1a 2 =a 2 =new intnew int 3;3;/allocate row 2/allocate row 2a.length a.length 行数行数a i.length a i.length 第第i i行列数行列数三维数组三维数组思维的扩展思维的扩展:一维数组一维数组二维数组二维数组三维数组三维数组示例示例:

12、class J_Fill3DArray public static void main(String args)int M=new int453;for(int row=0;row 4;row+)for(int col=0;col 5;col+)for(int ver=0;ver=0;c-)dest.append(source.charAt(c);returndest.toString();insert和和delete方法方法9种种insert方法方法允许将各种数据插到允许将各种数据插到StringBuffer对象的指对象的指定位置定位置方法方法delete(intstart,intend)和

13、和deleteCharAt(intindex)允许删除允许删除StringBuffer对象中的指定字符对象中的指定字符字符串例程字符串例程String和和StringBuffer是两种不同的类是两种不同的类不能用字符串不能用字符串(String)的实例对象调用类的实例对象调用类(StringBuffer)的成员方法的成员方法反之亦然反之亦然StringStringBuffer采用采用StringBuffer构造方法构造方法newStringBuffer(StringmyString);StringBufferString采用采用String构造方法构造方法newString(StringBuf

14、ferbuffer)采用采用StringBuffer的成员方法的成员方法toString()String和和StringBufferJ_StringBuffer.javaExample4_1.javaExample4_2.javaExample4_3.java本章总体纲要本章总体纲要数组数组字符串字符串字符串缓冲区字符串缓冲区向量向量哈希表哈希表向量向量向量向量在功能上与在功能上与数组数组类似，只是数组对象的长类似，只是数组对象的长度在数组对象创建之后不能改变，而向量元度在数组对象创建之后不能改变，而向量元素的个数可以素的个数可以改变改变，同时，同时向量元素向量元素的数据类的数据类型必须是型必

15、须是引用类型引用类型。向量向量的的基本原理基本原理：预先给向量对象分配一定的：预先给向量对象分配一定的存储空间，然后给向量对象添加元素或设置存储空间，然后给向量对象添加元素或设置元素值。元素值。向量对象的向量对象的容量容量：向量对象存储空间的大小：向量对象存储空间的大小（单位：元素个数），容量可根据向量长度（单位：元素个数），容量可根据向量长度的变化动态变化。的变化动态变化。(新容量计算方法新容量计算方法p147)p147)向量对象的向量对象的长度长度：向量对象中实际元素的个数。：向量对象中实际元素的个数。向量向量向量所对应的类是类向量所对应的类是类java.util.Vectorjava.u

16、til.Vector向量变量的声明格式向量变量的声明格式Vector变量名变量名;示例示例Vectorvs;“向量元素的数据类型向量元素的数据类型”必须指定，否则编译告警。必须指定，否则编译告警。创建向量实例对象创建向量实例对象/创建元素类型为字符串的向量对象创建元素类型为字符串的向量对象Vectorvs=newVector();/创建元素类型为创建元素类型为Object类型的向量对象类型的向量对象Vectorvo=newVector();上述两种情况的初始容量和容量增量的默认值分别为上述两种情况的初始容量和容量增量的默认值分别为10和和0。/创建向量对象，初始容量为创建向量对象，初始容量为i

17、nitialCapacity，容量增量为，容量增量为capacityIncrementpublicVector(intinitialCapacity)publicVector(intinitialCapacity,intcapacityIncrement)向量对象的操作向量对象的操作增加元素增加元素成员方法：成员方法：add/addElement/insertElementAt修改元素修改元素成员方法：成员方法：set/setElementAt删除元素删除元素成员方法：成员方法：clear/remove/removeElement/removeElementAt/.信息查询信息查询成员方法：成

18、员方法：contains/equals/indexOf/elementAt增加元素增加元素/将指定元素添加到向量对象的末尾，长度加将指定元素添加到向量对象的末尾，长度加1(其中，其中，E为一种为一种引用数据类型引用数据类型)publicbooleanadd(Eo)publicvoidaddElement(Eobj)/在向量对象的下标索引在向量对象的下标索引index处插入新元素处插入新元素element或或objpublicvoidadd(intindex,Eelement)publicvoidinsertElementAt(Eobj,intindex)示例示例vs.add(Tom);vs.i

19、nsertElementAt(“Tom”,4)修改元素修改元素/将下标为将下标为index的元素替换为元素的元素替换为元素element或或objpublicEset(intindex,Eelement)publicvoidsetElementAt(Eobj,intindex)删除元素删除元素/清空向量对象的所有元素清空向量对象的所有元素publicvoidclear()publicvoidremoveAllElements()/删除下标为删除下标为index的元素的元素publicEremove(intindex)publicvoidremoveElementAt(intindex)信息查询

20、信息查询查询向量是否包含某个指定的元素、查询指定元查询向量是否包含某个指定的元素、查询指定元素的下标、通过下标获取元素以及查询向量对象素的下标、通过下标获取元素以及查询向量对象的容量和长度等。的容量和长度等。/判断指定对象是否是向量对象的一个元素判断指定对象是否是向量对象的一个元素publicbooleancontains(Objectelem)/返回向量对象的容量返回向量对象的容量publicintcapacity()/返回向量对象的长度返回向量对象的长度publicintsize()importjava.util.Vector;publicclassCollectionOneCollect

21、ionOne()Vectorvec=newVector();/jdk1.5以前不支持泛型以前不支持泛型/Vectorvec=newVector();vec.add(“zero”);vec.add(“one”);vec.add(“two”);vec.add(“three”);Stringstr=(String)vec.get(2);/返回向量中指定位置元素返回向量中指定位置元素System.out.println(Theindexof2:+str);publicstaticvoidmain(Stringarg)newCollectionOne();通过迭代器通过迭代器(iterator)获取向量

22、对象的各个元素获取向量对象的各个元素*迭代器迭代器遍历并选择序列中的对象遍历并选择序列中的对象类类java.util.Vector的成员方法的成员方法publicIteratoriterator()/返回当前向量对应的迭代器返回当前向量对应的迭代器(指指向第一个元素的前一个位置向第一个元素的前一个位置)接口接口java.util.Iterator的成员方法的成员方法(实现该接口的一个类：实现该接口的一个类：Scanner)booleanhasNext()/判断迭代器的下一个位置上是否还有元素，判断迭代器的下一个位置上是否还有元素，返回值是返回值是boolean型型接口接口java.util.I

23、terator的成员方法的成员方法Enext()/返回迭代器下一个位置上的元素，并将迭代器的当返回迭代器下一个位置上的元素，并将迭代器的当前位置移到下一个位置前位置移到下一个位置本章总体纲要本章总体纲要数组数组字符串字符串字符串缓冲区字符串缓冲区向量向量哈希表哈希表哈希表哈希表数组：数组：按顺序存储，通过元素的下标可以非按顺序存储，通过元素的下标可以非常方便地获得该元素。常方便地获得该元素。另一种另一种需求需求：通过元素查找元素的存储位置。：通过元素查找元素的存储位置。一般认为一般认为最快最快的查找方式是采用的查找方式是采用哈希表哈希表，即，即散列表。散列表。哈希函数或散列函数哈希函数或散列函

24、数哈希表的基本原理哈希表的基本原理：在哈希表的元素的关键：在哈希表的元素的关键字与该元素的存储位置之间建立起一种映射字与该元素的存储位置之间建立起一种映射关系，即关系，即哈希函数哈希函数或散列函数。哈希函数种或散列函数。哈希函数种类很多，下面是一个示例。类很多，下面是一个示例。示例示例h1(s)=s031(n-1)+s131(n-2)+.+sn-1其中，其中，si表示字符串表示字符串s的下标为的下标为i的字符，的字符，n是字是字符串的长度。如果符串的长度。如果s为空字符串，则为空字符串，则h1(s)=0。哈希码哈希码(hashcode)或散列索引或散列索引由哈希函数计算出来的数值由哈希函数计算

25、出来的数值哈希表的空间利用率哈希表的空间利用率为节省存储空间，引入哈希表容量为节省存储空间，引入哈希表容量(capacity)(capacity)概念概念哈希表的存储空间大小哈希表的存储空间大小h h2 2(s)=|h(s)=|h1 1(s)|%m(s)|%m，作为字符串的另一个哈希函数（，作为字符串的另一个哈希函数（m m表示容表示容量）量）哈希表填写过程哈希表填写过程：计算哈希码，将元素存放在哈希码对：计算哈希码，将元素存放在哈希码对应的位置上。应的位置上。如果不同元素对应同一个哈希码，产生如果不同元素对应同一个哈希码，产生冲突冲突。解决冲突解决冲突的方法的方法如下：如下：对于产生冲突的元

26、素，第一个元素添加到相应位置，后面的对于产生冲突的元素，第一个元素添加到相应位置，后面的元素通过新的哈希函数或采用增量形式（如哈希码自增元素通过新的哈希函数或采用增量形式（如哈希码自增1 1）重）重新计算哈希码直到不冲突。新计算哈希码直到不冲突。通过定义新类或接口，改变哈希表存储结构通过定义新类或接口，改变哈希表存储结构(如，链表如，链表)，使，使得哈希表的每个位置上能够存放多个具有该哈希码的元素。得哈希表的每个位置上能够存放多个具有该哈希码的元素。哈希表的空间利用率哈希表的空间利用率减少冲突的方法减少冲突的方法在构造哈希函数时尽量使得元素在哈希表中均匀在构造哈希函数时尽量使得元素在哈希表中均

27、匀分布分布增加哈希表的容量，但是会降低哈希表的空间利增加哈希表的容量，但是会降低哈希表的空间利用率。用率。哈希表的哈希表的空间利用率空间利用率以哈希表的装填因子来以哈希表的装填因子来衡量。衡量。装填因子装填因子（建议：（建议：0.75）计算公式：）计算公式：哈希表类哈希表类java.util.Hashtable实例对象的元素由实例对象的元素由关键字关键字与与值值两两部分组成，其中关键字与值的类型可以是任意的部分组成，其中关键字与值的类型可以是任意的引用引用数据类型数据类型（不允许为（不允许为nullnull）。）。哈希表通过关键字可以与元素的存储位置建立映射关哈希表通过关键字可以与元素的存储位

28、置建立映射关系，所以可以直接通过关键字获取该元素的值。系，所以可以直接通过关键字获取该元素的值。Hashtable的构造方法的构造方法publicHashtable()/创建对象的容量为默认值创建对象的容量为默认值11，装填因子默认值为，装填因子默认值为0.75fpublicHashtable(intinitialCapacity,floatloadFactor)/创建对象的容量为创建对象的容量为initialCapacity，装填因子为，装填因子为loadFactorK(ey)和和V(alue)分别用来指定哈希表分别用来指定哈希表元素的关键字元素的关键字及其及其值的值的类型类型。哈希表类哈希

29、表类构造构造Hashtable的实例对象的实例对象Hashtable ht=new Hashtable ht=new Hashtable();Hashtable();其中，其中，StringString和和IntegerInteger用来指明哈希表中元素关用来指明哈希表中元素关键字键字(key)(key)类型和取值类型和取值(value)(value)类型。类型。Hashtable ht=new Hashtable();Hashtable ht=new Hashtable();编译警告编译警告（原因：无法给哈希表添加元素时判断元素关（原因：无法给哈希表添加元素时判断元素关键字及元素值的数据类型

30、的合法性和安全性）键字及元素值的数据类型的合法性和安全性）Hashtable成员方法成员方法Hashtable的成员方法的成员方法put/往哈希表中的指定位置（往哈希表中的指定位置（value）添加元素（）添加元素（key）publicVput(Kkey,Vvalue)成员方法成员方法get/获取由参数获取由参数key指定的关键字所对应的元素值，即存储位置指定的关键字所对应的元素值，即存储位置publicVget(Objectkey)成员方法成员方法clear/清空整个哈希表清空整个哈希表publicvoidclear()成员方法成员方法size/返回哈希表元素个数返回哈希表元素个数publi

31、cintsize()Hashtable成员方法成员方法判断在哈希表中是否已经存在指定的关键字判断在哈希表中是否已经存在指定的关键字publicbooleancontainsKey(Objectkey)判断在哈希表中是否已经存在指定的元素值判断在哈希表中是否已经存在指定的元素值publicbooleancontains(Objectvalue)publicbooleancontainsValue(Objectvalue)从哈希表中删除指定关键字所对应的元素从哈希表中删除指定关键字所对应的元素publicVremove(Objectkey)示例示例/J_Hashtable.java/通过哈希表形成

32、数组下标与值之间的双向映射。通过哈希表形成数组下标与值之间的双向映射。J_Hashtable.java本章小结本章小结数组数组：处理大量数据时使用，数组对象可以记录：处理大量数据时使用，数组对象可以记录各个元素和元素个数（各个元素和元素个数（lengthlength）字符串字符串：StringString对象创建后不能改变包含的字符对象创建后不能改变包含的字符序列，所有类型的数据都可以转化成字符串数据。序列，所有类型的数据都可以转化成字符串数据。字符串缓冲区字符串缓冲区：如果需要改变字符序列的组成和：如果需要改变字符序列的组成和长度应当采用长度应当采用StringBufferStringBuf

33、fer类，类，StringBufferStringBuffer的的对象具有缓冲区容量和字符序列长度两个指标。对象具有缓冲区容量和字符序列长度两个指标。向量向量：如果需要频繁改变元素个数，可以使用：如果需要频繁改变元素个数，可以使用VectorVector类。类。哈希表哈希表：HashtableHashtable类提供了提高查找元素效率的类提供了提高查找元素效率的方法。方法。请编写程序，输入一个字符串，然后由程序统请编写程序，输入一个字符串，然后由程序统计并输出在该字符串中每个字符出现的次数。计并输出在该字符串中每个字符出现的次数。请编写程序实现两种日期格式（如：请编写程序实现两种日期格式（如：

34、“1981.07.301981.07.30”和和“July 30,1981July 30,1981”）之间）之间相互转换。要求其中一种格式的日期通过程序相互转换。要求其中一种格式的日期通过程序的参数输入，程序通过识别判断其格式，然后的参数输入，程序通过识别判断其格式，然后输出另一个格式表示的日期。输出另一个格式表示的日期。作业作业(按照编程规范按照编程规范)举例说明生成字符串对象的几种方法举例说明生成字符串对象的几种方法举例说明字符串和字符串缓冲区的区别举例说明字符串和字符串缓冲区的区别4.14.14.24.2作业作业(按照编程规范按照编程规范)打印输出打印输出n行杨晖三角形行杨晖三角形(n可通过键盘输入可通过键盘输入)1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1完成下面的表达式，要求，星号分别表示完成下面的表达式，要求，星号分别表示0-0-9 9的一位数字，而且不允许重复，使得下面的一位数字，而且不允许重复，使得下面的加法表达式成立。的加法表达式成立。(输出所有结果输出所有结果)*+20085-*