第5章数据结构及常用算法

第五章数据结构及常用算法本章内容:常用集合元素有:向量(Vector),枚举(Enumeration),散列表(哈希表)(Hashtable)和属性(Properties)﹑数据结构中的接口﹑堆栈﹑链表﹑数据排序算法﹑数据查找算法.教学目标:学生通过本章学习应掌握Java常用集合元素﹑堆栈﹑链表﹑数据排序算法﹑数据查找算法的应用一、重点与难点:Java语法基础及Java面向对象特性,掌握常用的集合元素及常用的结合接口,熟练使用常用集合元素,数据排序算法﹑数据查找算法。二、教具:可进行广播的教学或多媒体计算机局域网,投影仪及相关的软硬件.三、教学方法:理论与实训相结合。四、教学时数:第8-9周6小时五、作业及上机练习:P.139--1.3.4.6.7.8.5.1向量(Vector)向量(Vector)是常见的数据结构,向量对象由java.util包中的Vector类来创建.它类似数组结构,但不要求每个元素的类型相同,向量中可以混合多种数据类型.向量元素可动态增加.Vector类中的对象不但可以顺序存储数据,还封装了一些方法来处理和操作向量中的数据,使用非常方便.5.1.1创建向量对象:(1)Vectorstu=newVector();//使用无参数构造函数创建向量对象，不给出向量大小(2)带参数的构造函数PublicVector(intCapacity,intIncreament);//形参intCapacity–容量(初始化向量元素多少);intIncreament–追加元素个数,如:Vectorstu=newVector(40,5);//容量为40个元素,一次可添加5个元素.5.1.2向量对象的常用方法:1.添加元素方法(1)publicvoidadd(Objecto):将新对象o添加到向量末尾.(2)publicvoidadd(intindex,Objecto):将新对象o添加到向量的指定索引位置.(3)publicvoidinsertElement(Objecto,intindex):将新对象o插入到向量的指定索引位置.(4)publicvoidaddElement(Objecto,intindex):将新对象o添加到向量指定索引位置.2.修改和删除向量元素(1)publicvoidset(Objecto,intindex):将指定索引位置的对象设置为o,覆盖原来的对象.(2)publicvoidsetElement(Objecto,intindex):将指定索引位置的对象设置为o,覆盖原来的对象元素.(3)publicbooleanremoveElement(Objecto):将向量序列中第一次出现的对象o删除,同时将后面元素移补上前删除空位.(4)publicvoidremoveALLElement():将向量序列中所有对象删除.(5)publicObjectremove(intindex):将向量序列中指定索引位置的对象元素删除,并返回该对象.(6)publicObjectElementAt(intindex):获取向量序列中指定索引位置的对象.(7)publicObjectget(intindex):获取向量序列中指定索引位置的对象.(8)publicObjectfirstElement():获取向量序列中的第一个对象.(9)publicObjectlastElement():获取向量序列中在的最后一个对象.(10)publicEnumerationElement():获取向量序列中的一个枚举对象.(11)publicindexindexOf(Objecto):获取对象o在向量序列中首次出现的位置.(12)publicindexlastIndexOf(Objecto):获取对象o在向量序列中最后出现的位置.(13)publicindexlastIndexOf(Objecto,intindex):获取向量序列中在向量位置之前出现的最后位置.(3)publicbooleancontains(Objecto):判断对象o是否是向量成员.例5-1TestVector1.java-使用向量importjava.util.*;publicclassTestVector1{publicstaticvoidmain(Stringargs[]){Stringnames[]={Merry,Martin,Bob,David};intnamesLen=names.length;//获取数组长度Vectorstu=newVector();//创建向量对象实例for(inti=0;inamesLen;i++){stu.addElement(names[i]);//将数组元素值添加到向量对象末尾.}intstuLen1=stu.size();//获取向量对象长度（元素大小）for(inti=0;istuLen1;i++){System.out.println(stu.elementAt(i));//输出向量对象元素}}}例5-2TestVector2.java-使用向量依次存储不同数据类型importjava.util.*;classTestVector2{publicstaticvoidmain(Stringargs[]){Vectorvector=newVector();Datedate=newDate();vector.add(newInteger(18));//依次添加整数对象18到向量对象末尾，以下依次类推.vector.add(newFloat(99.9f));vector.add(newDouble(100.08));vector.add(newBoolean(true));vector.add(date);System.out.println(向量的总长度：+vector.size());System.out.println(向量的第1个元素：+vector.firstElement());//输出向量中元素对象System.out.println(向量的第2个元素：+vector.elementAt(1));System.out.println(向量的第3个元素：+vector.get(2));System.out.println(向量的第4个元素：+vector.get(3));System.out.println(向量的第5个元素：+vector.lastElement());if(vector.contains(date))//如果向量中包含日期对象{vector.addElement(newString(verygood!));//添加字符串对象到向量对象末尾System.out.println(向量的最后一个元素：+vector.lastElement());}}}【例13.12】向量随机排列importjava.util.Vector;publicclassExample13_12{publicstaticvoidmain(Stringargs[]){Vectorvector=newVector();//创建向量对象inta[]={1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4};System.out.println(随机排列之前的数组:);for(inti=0;ia.length;i++){System.out.print(+a[i]);//输出数组元素}System.out.println();for(inti=0;ia.length;i++){vector.add(newInteger(a[i]));//将数组对象元素添加到向量对象中}intk=0;while(vector.size()0){intindex=(int)(Math.random()*vector.size());//产生16个随机整数索引intnumber=((Integer)vector.get(index)).intValue();//取得索引对应值a[k]=number;//存入数组k++;vector.removeElementAt(index);//删除向量中对应索引的元素}System.out.println(随机排列之后的数组:);for(inti=0;ia.length;i++){System.out.print(+a[i]);//输出经随机排列的数组元素}System.out.println();}}5.1.3枚举(Enumeration)–Vector类也可以用枚举器来列举和存放许多元素。Vector类的Enumeration（）方法可返回一个Enumeration接口，该接口有两个常用方法:（1）hasMoreElements()//判断是否还有元素（2）nextElement()//下一个元素使用方法如下:例5-3TestEnumerationimportjava.util.*;publicclassTestEnumeration{publicstaticvoidmain(Stringargs[]){Stringnames[]={dog,cat,fish,bird};//创建字符串数组对象并初始化数组intnamesLen=names.length;//取得数组长度Vectoranimal=newVector();//创建向量对象for(inti=0;inamesLen;i++){//for循环将数组元素依次添加(存)到向量对象中animal.addElement(names[i]);}Enumerationenum1=animal.elements();//用向量对象的elements()方法获取一个枚举对象Stringname=null;//while循环枚举对象中判断是否还有元素,如果有取出枚举中的元素并输出while(enum1.hasMoreElements()){name=(String)enum1.nextElement();//下一个元素System.out.println(name);//输出枚举对象中的元素}}}5.2散列表(Hashtable-哈希表)数组,向量提供了集合内容的顺序访问,哈希表可以对集合内容进行随机访问。哈希表是使用关键字查找被存储的数据项的一种数据结构,可以通过键（名）-值对应集合内容进行随机访问,是Map接口的主要实现类.5.2.1创建哈希表对象–用java.util包中Hashtable类的构造函数来创建,其Hashtable类的构造函数如下:(1)publicHashtable();创建具有默认容量和装载因子为0.75的散列表(2)publicHashtable(intintialCapacity);创建具有指定容量和装载因子为0.75的散列表.(3)publicHashtable(intintialCapacity,floatloadFactor);创建具有指定容量和指定装载因子的散列表.如:Hashtabletable1=newHashtable();5.2.2哈希表主要方法如下:(1)publicvoidput(Objectkey,Objectvalue)--加进对象(键/值)关键字/数值对.(2)publicObjectget(Objectkey)—取得一个关键字的值.(3)publicObjectremove(Objectkey)---删除一个元素(4)publicintsize()---取得哈希表中关键字的数目(5)publicBooleanempty()---判断哈希表是否为空(6)publicEnumerationkeys()---取得所有关键字设置(7)publicEnumerationelements()---取得所有数值的设置,两者都返回Enumeration.例5-4TestHarsh.javaimportjava.util.*;publicclassTestHarsh{publicstaticvoi