第5章 数据结构及常用算法Word文档格式.docx
《第5章 数据结构及常用算法Word文档格式.docx》由会员分享，可在线阅读，更多相关《第5章 数据结构及常用算法Word文档格式.docx（25页珍藏版）》请在冰点文库上搜索。
（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;
i<
namesLen;
i++）{
stu.addElement（names[i]）;
//将数组元素值添加到向量对象末尾.
}
intstuLen1=stu.size（）;
//获取向量对象长度（元素大小）
stuLen1;
System.out.println（stu.elementAt（i））;
//输出向量对象元素
}
例5-2TestVector2.java-使用向量依次存储不同数据类型
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（））;
向量的第1个元素：
+vector.firstElement（））;
//输出向量中元素对象
向量的第2个元素：
+vector.elementAt
（1））;
向量的第3个元素：
+vector.get
（2））;
向量的第4个元素：
+vector.get（3））;
向量的第5个元素：
+vector.lastElement（））;
if（vector.contains（date））//如果向量中包含日期对象
{vector.addElement（newString（"
verygood!
"
））;
//添加字符串对象到向量对象末尾
向量的最后一个元素：
}
【例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};
随机排列之前的数组:
）;
a.length;
i++）
{System.out.print（"
+a[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（）;
}
5.1.3枚举（Enumeration）–Vector类也可以用枚举器来列举和存放许多元素。
Vector类的Enumeration（）方法可返回一个Enumeration接口，该接口有两个常用方法:
（1）hasMoreElements（）//判断是否还有元素
（2）nextElement（）//下一个元素
使用方法如下:
例5-3TestEnumeration
publicclassTestEnumeration
publicstaticvoidmain（Stringargs[]）
Stringnames[]={"
dog"
cat"
fish"
bird"
//创建字符串数组对象并初始化数组
intnamesLen=names.length;
//取得数组长度
Vectoranimal=newVector（）;
for（inti=0;
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.java
publicclassTestHarsh
Stringsubject[]={"
语文"
数学"
英语"
政治"
//创建字符串科目数组代表键（名）
Stringscore[]={"
88"
99"
96"
92"
//创建字符串分数数组代表键（名）对应值
Hashtablehash=newHashtable（）;
//创建哈希表对象
subject.length;
i++）{//获得科目数组长度
hash.put（subject[i],score[i]）;
//将科目数组和分数数组加进hash对象中（键/值）对
//取得hash表中所有关键字并赋给枚举对象元素（返回枚举类型Enumeration.）
Enumerationenum1=hash.keys（）;
Objectobj;
//声明引用对象变量
//判断枚举对象是否还有元素,如果有while循环输出键值对
while（enum1.hasMoreElements（））{
//枚举对象的nextElement（）方法取得下一个枚举元素值（键/值）
obj=enum1.nextElement（）;
System.out.println（obj+"
:
+hash.get（obj））;
//输出取得的关键字和枚举元素值（键/值）
5.3数据结构中的接口
Java2数据结构提供了4种重要接口:
Collection﹑List﹑Set﹑Iterator接口,用于描述不同类型的数据结构.
5.3.1Collection接口
Collection接口是任何对象组的集合,对象的存放没有一定的顺序,并且允许重复,可以存放几个相同的对象.Collection接口的常用方法如下:
（1）publicbooleanadd（objecto）–向集合添加对象.
（2）publicbooleanremove（objecto）–从集合删除对象.
（3）publicbooleancontains（objecto）–判断是否包含对象.
（4）publicbooleanequals（objecto）–比教两个对象是否相同
例5-5TestCollection.java–使用Collection接口
publicclassTestCollection{
publicstaticvoidmain（Stringargs[]）{
StringstrNumber[]={"
one"
two"
three"
four"
five"
six"
seven"
eight"
intstrlen=strNumber.length;
//获得数组长度
CollectionNumbers=newVector（）;
//创建向量对象使用Collection接口的变量引用
strlen;
Numbers.add（strNumber[i]）;
//添加数组元素值到Collection接口集合对象中
}
Objects[]=Numbers.toArray（）;
//将集合对象转换为数组
s.length;
i++）{//取得数组长度for循环输出数组中个元素
System.out.println（s[i].toString（））;
//
5.3.2Set接口
集合是由不重复元素组成的.Set集合接口中的元素不重复,且至多包含一个null元素.
例5-6TestSet.java使用Set接口（对象无序存放）
classTestSet{
publicstaticvoidmain（String[]args）{
HashSeth=newHashSet（）;
//创建哈希Set集合接口对象
h.add（"
1st"
//向集合添加对象
2nd"
h.add（newInteger（3））;
h.add（newDouble（4.0））;
//重复元素,未被加入
m1（h）;
//调用m1（h）方法输出集合
publicstaticvoidm1（Sets）{//m1方法形式参数为Set无序集合接口
System.out.println（s）;
//输出集合
5.3.3List接口
List接口是一种可含有重复元素的,有序的数据集合,也称序列.用户可以控制向序列中插入元素的位置,并可按元素的位序（加入顺序）来进行访问,位序从0开设.
5-7TestList.java使用List接口（可存储重复元素）
classTestList{
ArrayListh=newArrayList（）;
//创建List接口对象
//在List接口对象中添加不同类型的对象元素
h.add（newInteger（111））;
h.add（newDouble（2.22））;
//加入重复元素
publicstaticvoidm1（Lists）{//m1方法参数为List有序集合接口
//输出List接口对象中的对象元素
5.3.4Iterator接口
可以通过任何Collection接口中定义的iterator（）方法获得一个Iterator对象.List接口中声明了三种方法hasNext（）,next（）,remove（）.Set对象对应的Iterator仍然是无序的.
例5-8TestIterator.java使用Iterator接口
classTestIterator{
//在List接口对象中添加不同类型的对象元素
Iteratorit=h.iterator（）;
//用List接口对象集合的方法iterator（）获得一个Iterator接口对象
while（it.hasNext（））{//判断Iterator接口对象中是否有对象元素
System.out.println（it.next（））;
//输出对象元素
5.4堆栈
堆栈（Stack）是一种遵循:
”后进先出”原则的重要线性数据结构,只允许在一端输入和输出线性的顺序表.堆栈把一个输入的数据放在最底下,把后面放入的数据放在已有数据的顶上,最后输入的数据在堆栈的最上面.这样堆栈就有一个固定的栈底和一个浮动的栈顶.允许输入和输出的一端称为栈顶（top）,另一端称为栈底（bottom）.
向堆栈中压入数据的操作称为”压栈”;
从堆栈中输出数据的操作称为”弹栈”.由于堆栈总是在栈顶进行数据的输入输出操作,所以弹栈总是先输出最后压入堆栈中的数据,这就是后进先出的原理.
在Java中,使用jsva.util包中的Stack类来创建堆栈对象.如:
Stackperson=newstack（）;
//Stack（）是Stack类唯一的构造函数
Stack类是向量Vector类的子类,所以Stack类不但具有Vector类的所以方法,同时还有自己操作堆栈对象的方法,主要方法如下.
PublicObjectpush（Objecto）--将对象压入（输入）堆栈的操作.
Pubilcobjectpop（Objecto）--将栈顶对象弹出（输出）堆栈的操作.
PublicBooleanempty（）--判断堆栈是否还有数据,若有数据,返回false;
否则返回true.
PublicObjectpeek（）:
--查看并返回堆栈顶端数据,但不删除.
Publicintsearch（Objecto）;
查看数据在堆栈中的位置,最顶端的位置1,向下依次增加,如果堆栈不含该数,则返回-1.
例5-9TestStack.java-堆栈类的使用
classTestStack
{publicstaticvoidmain（Stringargs
升级会员 