第5章 数据结构及常用算法Word文档格式.docx

1、（3） public void insertElement （Object o ,int index） : 将新对象o插入到向量的指定索引位置.（4） public void addElement （Object o ,int index） : 将新对象o添加到向量指定索引位置.2. 修改和删除向量元素（1） public void set（Object o ,int index） : 将指定索引位置的对象设置为o,覆盖原来的对象.（2） public void setElement （Object o ,int index） : 将指定索引位置的对象设置为o,覆盖原来的对象元素.（3） pu

2、blic boolean removeElement （Object o） : 将向量序列中第一次出现的对象o删除, 同时将后面元素移补上前删除空位.（4） public void removeALLElement （ ） : 将向量序列中所有对象删除.（5） public Object remove （int index ） : 将向量序列中指定索引位置的对象元素删除,并返回该对象.（6） public Object ElementAt （int index ） : 获取向量序列中指定索引位置的对象.（7） public Object get （int index ） :（8） public

3、 Object firstElement （ ） : 获取向量序列中的第一个对象.（9） public Object lastElement （ ） : 获取向量序列中在的最后一个对象.（10） public Enumeration Element（ ） : 获取向量序列中的一个枚举对象.（11） public index indexOf （Object o） : 获取对象o在向量序列中首次出现的位置.（12） public index lastIndexOf （Object o） : 获取对象o在向量序列中最后出现的位置.（13） public index lastIndexOf （Obje

4、ct o, int index） : 获取向量序列中在向量位置之前出现的最后位置.（3） public boolean contains （Object o） :判断对象o是否是向量成员.例5-1 TestVector1.java - 使用向量import java.util.*;public class TestVector1public static void main（String args） String names = Merry,MartinBobDavid; int namesLen = names.length; /获取数组长度 Vector stu = new Vector（

5、）; /创建向量对象实例 for（int i=0;i0） int index=（int）（Math.random（）*vector.size（）; /产生16个随机整数索引 int number=（Integer）vector.get（index）.intValue（）; /取得索引对应值 ak=number; /存入数组 k+; vector.removeElementAt（index）; /删除向量中对应索引的元素随机排列之后的数组: /输出经随机排列的数组元素 System.out.println（）; 5.1.3枚举（Enumeration） Vector类也可以用枚举器来列举和存放许

6、多元素。Vector类的Enumeration（）方法可返回一个Enumeration接口，该接口有两个常用方法:（1）hasMoreElements（） /判断是否还有元素（2）nextElement（） /下一个元素使用方法如下:例5-3 TestEnumerationpublic class TestEnumeration public static void main（String args） String names = dogcatfishbird /创建字符串数组对象并初始化数组 int namesLen = names.length; /取得数组长度 Vector animal

7、 = new Vector（）; for（int i=0;i+） / for循环将数组元素依次添加（存）到向量对象中 animal.addElement（namesi）; Enumeration enum1 = animal.elements（）; /用向量对象的elements（）方法获取一个枚举对象 String name = null;/ while循环枚举对象中判断是否还有元素,如果有取出枚举中的元素并输出 while（enum1.hasMoreElements（） name = （String）enum1.nextElement（）; /下一个元素 System.out.printl

8、n（name）; /输出枚举对象中的元素5.2 散列表（Hashtable-哈希表）数组,向量提供了集合内容的顺序访问, 哈希表可以对集合内容进行随机访问。哈希表是使用关键字查找被存储的数据项的一种数据结构,可以通过键（名）-值对应集合内容进行随机访问,是Map接口的主要实现类.5.2.1 创建哈希表对象 用java.util包中Hashtable类的构造函数来创建,其Hashtable类的构造函数如下:（1） public Hashtable （ ）; 创建具有默认容量和装载因子为0.75的散列表（2） public Hashtable （ int intialCapacity）; 创建具有

9、指定容量和装载因子为0.75的散列表.（3） public Hashtable （ int intialCapacity , float loadFactor）; 创建具有指定容量和指定装载因子的散列表.如:Hashtable table1 = new Hashtable （ ）;5.2.2 哈希表主要方法如下:（1） public void put （Object key, Object value）- 加进对象（键/值）关键字/数值对.（2） public Object get （Object key）取得一个关键字的值.（3） public Object remove （Object k

10、ey）-删除一个元素（4） public int size（）-取得哈希表中关键字的数目（5） public Boolean empty（）-判断哈希表是否为空（6） public Enumeration keys（）-取得所有关键字设置（7） public Enumeration elements（）-取得所有数值的设置,两者都返回Enumeration.例5-4 TestHarsh.javapublic class TestHarsh String subject = 语文数学英语政治 /创建字符串科目数组代表键（名） String score = 88999692 /创建字符串分数数组代

11、表键（名）对应值 Hashtable hash = new Hashtable（）; /创建哈希表对象 subject.length;i+） /获得科目数组长度 hash.put（subject i, score i）; /将科目数组和分数数组加进hash对象中（键/值）对/取得hash表中所有关键字并赋给枚举对象元素（返回枚举类型Enumeration.） Enumeration enum1 = hash.keys（）; Object obj; /声明引用对象变量/判断枚举对象是否还有元素,如果有while循环输出键值对 while（enum1.hasMoreElements（） /枚举对象

12、的nextElement（）方法取得下一个枚举元素值（键/值） obj = enum1.nextElement（）; System.out.println（obj + : +hash.get（obj）; /输出取得的关键字和枚举元素值（键/值）5.3 数据结构中的接口Java2数据结构提供了4种重要接口: CollectionListSetIterator接口,用于描述不同类型的数据结构.5.3.1 Collection接口Collection接口是任何对象组的集合,对象的存放没有一定的顺序,并且允许重复,可以存放几个相同的对象. Collection接口的常用方法如下:（1） public

13、boolean add （object o） 向集合添加对象.（2） public boolean remove （object o） 从集合删除对象.（3） public boolean contains （object o） 判断是否包含对象.（4） public boolean equals （object o） 比教两个对象是否相同例5-5 TestCollection.java 使用Collection接口public class TestCollection public static void main（String args） String strNumber=onetwoth

14、reefourfivesixseveneight int strlen=strNumber.length; /获得数组长度 Collection Numbers=new Vector（）; /创建向量对象使用Collection接口的变量引用strlen; Numbers.add（strNumberi）; /添加数组元素值到Collection接口集合对象中 Object s=Numbers.toArray（）; /将集合对象转换为数组s.length;i+） /取得数组长度for循环输出数组中个元素 System.out.println（si.toString（）; /5.3.2 Set接口

15、集合是由不重复元素组成的. Set集合接口中的元素不重复,且至多包含一个null元素.例5-6 TestSet.java使用Set接口（对象无序存放）class TestSet public static void main（String args） HashSet h = new HashSet（）; /创建哈希Set集合接口对象 h.add（1st /向集合添加对象2nd h.add（new Integer（3）; h.add（new Double（4.0）; / 重复元素, 未被加入 m1（h）; /调用m1（h）方法输出集合 public static void m1（Set s） /

16、m1方法形式参数为Set无序集合接口 System.out.println（s）; /输出集合5.3.3 List接口List接口是一种可含有重复元素的,有序的数据集合,也称序列.用户可以控制向序列中插入元素的位置,并可按元素的位序（加入顺序）来进行访问, 位序从0开设.5-7 TestList.java使用List接口（可存储重复元素）class TestList ArrayList h = new ArrayList（）; /创建List接口对象 /在List接口对象中添加不同类型的对象元素 h.add（new Integer（111）; h.add（new Double（2.22）; /

17、加入重复元素 public static void m1（List s） /m1方法参数为List有序集合接口 /输出List接口对象中的对象元素5.3.4 Iterator接口可以通过任何Collection接口中定义的iterator（）方法获得一个Iterator对象. List接口中声明了三种方法hasNext（）,next（）,remove（）. Set对象对应的Iterator仍然是无序的.例5-8 TestIterator.java使用Iterator接口class TestIterator /在List接口对象中添加不同类型的对象元素 Iterator it = h.itera

18、tor（）; /用List接口对象集合的方法iterator（）获得一个Iterator接口对象 while （ it.hasNext（） ） /判断Iterator接口对象中是否有对象元素 System.out.println（it.next（）; /输出对象元素5.4 堆栈堆栈（Stack）是一种遵循:”后进先出”原则的重要线性数据结构,只允许在一端输入和输出线性的顺序表.堆栈把一个输入的数据放在最底下,把后面放入的数据放在已有数据的顶上,最后输入的数据在堆栈的最上面.这样堆栈就有一个固定的栈底和一个浮动的栈顶.允许输入和输出的一端称为栈顶（top）,另一端称为栈底（bottom）.向堆栈

19、中压入数据的操作称为”压栈”;从堆栈中输出数据的操作称为”弹栈”.由于堆栈总是在栈顶进行数据的输入输出操作,所以弹栈总是先输出最后压入堆栈中的数据,这就是后进先出的原理.在Java中,使用jsva.util包中的Stack类来创建堆栈对象.如:Stack person = new stack（）; / Stack（）是Stack类唯一的构造函数Stack类是向量Vector类的子类,所以Stack类不但具有Vector类的所以方法,同时还有自己操作堆栈对象的方法,主要方法如下.Public Object push（Object o）- 将对象压入（输入）堆栈的操作.Pubilc object pop （Object o）-将栈顶对象弹出（输出）堆栈的操作. Public Boolean empty （）- 判断堆栈是否还有数据,若有数据,返回false; 否则返回true.Public Object peek （）: - 查看并返回堆栈顶端数据,但不删除.Public int search （Object o）; 查看数据在堆栈中的位置,最顶端的位置1,向下依次增加,如果堆栈不含该数,则返回-1.例5-9 TestStack.java -堆栈类的使用class TestStack public static void main（String args