Java语言程序设计基础教程课件(第12章).ppt
- 文档编号:18878192
- 上传时间:2024-02-07
- 格式:PPT
- 页数:56
- 大小:228.50KB
Java语言程序设计基础教程课件(第12章).ppt
《Java语言程序设计基础教程课件(第12章).ppt》由会员分享,可在线阅读,更多相关《Java语言程序设计基础教程课件(第12章).ppt(56页珍藏版)》请在冰点文库上搜索。
第第12章章常见数据结构的常见数据结构的Java实现实现链表的基本操作链表的基本操作栈栈树集树集树映射树映射散列表散列表散列集散列集向量向量容器类容器类数组数组的的优缺点优缺点java用于存储数据的集合类用于存储数据的集合类存储存储单个单个对象对象的集合的集合存储存储键值对键值对对象的集合对象的集合集合遍历工具:
集合遍历工具:
迭代器迭代器顺序表顺序表链表链表Tree:
排排序树序树Hash:
哈希值确哈希值确定存储地址定存储地址集合工具:
静集合工具:
静态方法态方法比较器比较器比较器接口比较器接口List接口(索引读取,可重复)接口(索引读取,可重复)ListList关心的是索引关心的是索引关心的是索引关心的是索引与其他集合相比,与其他集合相比,与其他集合相比,与其他集合相比,ListList特有的就是和索引相关特有的就是和索引相关特有的就是和索引相关特有的就是和索引相关的一些方法:
的一些方法:
的一些方法:
的一些方法:
get(intindex)get(intindex)、add(intadd(intindex,Objecto)index,Objecto)、indexOf(Objecto)indexOf(Objecto)。
ArrayListArrayList:
可增长的数组,它提供快速迭代和:
可增长的数组,它提供快速迭代和:
可增长的数组,它提供快速迭代和:
可增长的数组,它提供快速迭代和快速随机访问的能力,增删元素慢。
快速随机访问的能力,增删元素慢。
快速随机访问的能力,增删元素慢。
快速随机访问的能力,增删元素慢。
LinkedListLinkedList:
双向链表,增删元素快。
:
双向链表,增删元素快。
:
双向链表,增删元素快。
:
双向链表,增删元素快。
Set接口(元素唯一)接口(元素唯一)SetSet关心元素唯一性,它不允许重复,且无序关心元素唯一性,它不允许重复,且无序关心元素唯一性,它不允许重复,且无序关心元素唯一性,它不允许重复,且无序HashSetHashSet:
不关心元素之间的顺序且无重复值:
不关心元素之间的顺序且无重复值:
不关心元素之间的顺序且无重复值:
不关心元素之间的顺序且无重复值时使用时使用时使用时使用LinkedHashsetLinkedHashset:
希望按照元素的插入顺序:
希望按照元素的插入顺序:
希望按照元素的插入顺序:
希望按照元素的插入顺序进行迭代遍历,且不希望集合中有重复值时采进行迭代遍历,且不希望集合中有重复值时采进行迭代遍历,且不希望集合中有重复值时采进行迭代遍历,且不希望集合中有重复值时采用此类。
用此类。
用此类。
用此类。
TreeSetTreeSet希望按照元素的按大小顺序排列,且希望按照元素的按大小顺序排列,且希望按照元素的按大小顺序排列,且希望按照元素的按大小顺序排列,且不希望集合中有重复值时使用不希望集合中有重复值时使用不希望集合中有重复值时使用不希望集合中有重复值时使用Map接口(键值对映射)接口(键值对映射)MapMap关心的是唯一的键,可映射到某个元素关心的是唯一的键,可映射到某个元素关心的是唯一的键,可映射到某个元素关心的是唯一的键,可映射到某个元素HashMapHashMap当需要键值对表示,又不关心顺序当需要键值对表示,又不关心顺序当需要键值对表示,又不关心顺序当需要键值对表示,又不关心顺序时可采用时可采用时可采用时可采用HashMapHashMapHashtableHashtable注意注意注意注意HashtableHashtable中的中的中的中的tt是小写的,它是小写的,它是小写的,它是小写的,它是是是是HashMapHashMap的线程安全版本,已较少使用的线程安全版本,已较少使用的线程安全版本,已较少使用的线程安全版本,已较少使用LinkedHashMapLinkedHashMap当需要键值对,并且关心插当需要键值对,并且关心插当需要键值对,并且关心插当需要键值对,并且关心插入顺序时可采用它入顺序时可采用它入顺序时可采用它入顺序时可采用它TreeMapTreeMap当需要键值对,并希望元素按大小排当需要键值对,并希望元素按大小排当需要键值对,并希望元素按大小排当需要键值对,并希望元素按大小排序时可采用它。
序时可采用它。
序时可采用它。
序时可采用它。
List常用方法:
常用方法:
add(Objecte)将指定对象添加到集合中将指定对象添加到集合中remove(Objecto)将指定的对象从集合中移除,移除成功返回将指定的对象从集合中移除,移除成功返回true,不成功不成功返回返回falsecontains(Objecto)查看该集合中是否包含指定的对象,包含返回查看该集合中是否包含指定的对象,包含返回true,不包不包含返回含返回flasesize()返回集合中存放的对象的个数。
返回值为返回集合中存放的对象的个数。
返回值为intclear()移除该集合中的所有对象,清空该集合。
移除该集合中的所有对象,清空该集合。
iterator()返回一个包含所有对象的返回一个包含所有对象的iterator对象,用来循环遍历对象,用来循环遍历toArray()返回一个包含所有对象的数组返回一个包含所有对象的数组,类型是类型是ObjectLinkedList的常用方法的常用方法publicpublicbooleanbooleanadd(Objectadd(Objectelement)element)publicvoidpublicvoidadd(intadd(intindex,Objectelement)index,Objectelement)publicvoidpublicvoidaddFirst(ObjectaddFirst(Objectelement)element)publicvoidpublicvoidaddLast(ObjectaddLast(Objectelement)element)publicObjectpublicObjectremoveFirstremoveFirst()()publicObjectpublicObjectremoveLastremoveLast()()publicObjectremove(publicObjectremove(intintindex)index)publicObjectget(publicObjectget(intintindex)index)publicObjectpublicObjectgetFirstgetFirst()()publicObjectpublicObjectgetLastgetLast()()intintindexOf(ObjectindexOf(Objectelement)element)publicpublicintintlastIndexOf(ObjectlastIndexOf(Objectelement)element)publicObjectpublicObjectset(intset(intindex,Objectindex,Objectelement)element)publicpublicintintsize()size()publicpublicbooleanbooleancontains(Objectcontains(Objectelement)element)ObjecttoArray()ObjecttoArray()迭代器的使用迭代器的使用Stringsa=one,two,three,four;Stringsa=one,two,three,four;Listlist=Listlist=Arrays.asList(sa)Arrays.asList(sa);Iteratorit=Iteratorit=list.iterator()list.iterator();/;/转换成转换成转换成转换成IteratorIteratorwhile(while(it.hasNext()it.hasNext()/)/遍历遍历遍历遍历System.out.println(System.out.println(it.next()it.next(););12.3.3TreeSet常用方法常用方法publicbooleanadd(Objecto)publicvoidclear()publicbooleancontains(Objecto)publicObjectfirst()/最小元素最小元素publicObjectlast()/最大元素最大元素PublicbooleanisEmpty()publicbooleanremove(Objecto)publicintsize()ObjecttoArray()Set集合中如何实现元素的比较集合中如何实现元素的比较方法一:
方法一:
元素对象实现元素对象实现Comparable接口接口实现方法实现方法实现方法实现方法publicvoidcompareTo(Objecto)publicvoidcompareTo(Objecto)方法二:
方法二:
定义定义TreeSet时指定比较器时指定比较器Comparator重载重载重载重载publicintcompare(Objecta,Objectb)publicintcompare(Objecta,Objectb)Map接口的常用方法接口的常用方法put(Kkey,Vvalue)向集合中添加指定的键值对向集合中添加指定的键值对putAll(Mapt)把一把一Map中的所有键值对添加到该集合中的所有键值对添加到该集合containsKey(Objectkey)如果包含该键,则返回如果包含该键,则返回truecontainsValue(Objectval)如果包含该值,则返回如果包含该值,则返回trueget(Objectkey)根据键根据键,返回相应的值对象返回相应的值对象SetkeySet()将该集合中的所有键将该集合中的所有键Collectionvalues()将该集合中所有的值将该集合中所有的值remove(Objectkey)如存在指定的键,移除该键值对,返回键如存在指定的键,移除该键值对,返回键所对应的值,不存在则返回所对应的值,不存在则返回nullclear()清空集合清空集合isEmpty()查看查看Map中是否为空中是否为空size()集合中包含键值对的个数集合中包含键值对的个数12.4树映射树映射TreeMap树集树集树集树集TreeSetTreeSet适合用于数据的排序,适合用于数据的排序,适合用于数据的排序,适合用于数据的排序,TreeMapTreeMap类树类树类树类树映射的结点存储映射的结点存储映射的结点存储映射的结点存储“关键字关键字关键字关键字/值值值值”对,实现对,实现对,实现对,实现MapMap接口接口接口接口树映射各结点树映射各结点树映射各结点树映射各结点按照关键字升序排列按照关键字升序排列按照关键字升序排列按照关键字升序排列使用使用使用使用put(Kput(Kkey,Vkey,Vvalue)value)方法添加结点方法添加结点方法添加结点方法添加结点,该结点不,该结点不,该结点不,该结点不仅存储数据仅存储数据仅存储数据仅存储数据valuevalue,而且也存储和其关联的关键字,而且也存储和其关联的关键字,而且也存储和其关联的关键字,而且也存储和其关联的关键字keykey。
HashSet常用方法常用方法booleanadd(Ee)booleanadd(Ee)voidclear()voidclear()Objectclone()Objectclone()booleancontains(Objecto)booleancontains(Objecto)booleanisEmpty()booleanisEmpty()iteratoriterator()iteratoriterator()booleanremove(Objecto)booleanremove(Objecto)intsize()intsize()12.5.1Hashtable类常用方法类常用方法publicpublicHashtableHashtable()()publicpublicHashtable(intHashtable(intitialCapacityitialCapacity)publicpublicHashtable(intHashtable(intinitialCapacity,floatinitialCapacity,floatloadFactorloadFactor)publicvoidclear()publicvoidclear()publicpublicbooleanbooleancontains(Objectcontains(Objecto)o)publicObjectpublicObjectget(Objectget(Objectkey)key)publicpublicbooleanbooleanisEmptyisEmpty()()publicObjectpublicObjectput(Objectput(Objectkey,Objectkey,Objectvalue)value)publicObjectpublicObjectremove(Objectremove(Objectkey)key)publicpublicintintsize()size()publicpublicEnumerationEnumerationelements()elements()HashMap和和Hashtable的区别的区别HashMap:
不允许不允许不允许不允许nullkeynullkey和和和和nullvaluenullvalue方法不同步方法不同步方法不同步方法不同步Collection.synchronizedMap(hashmap)Collection.synchronizedMap(hashmap)Hashtable允许允许允许允许nullkeynullkey和和和和nullvaluenullvalue方法同步方法同步方法同步方法同步类型安全的集合类型安全的集合在在在在Java5Java5版本之前我们使用:
版本之前我们使用:
版本之前我们使用:
版本之前我们使用:
Listlist=newArrayList()Listlist=newArrayList()在在在在Java5Java5版本之后,我们使用带泛型的写法:
版本之后,我们使用带泛型的写法:
版本之后,我们使用带泛型的写法:
版本之后,我们使用带泛型的写法:
Listlist=newArrayList();Listlist=newArrayList();上面的代码定义了一个只允许保存字符串的列表,上面的代码定义了一个只允许保存字符串的列表,上面的代码定义了一个只允许保存字符串的列表,上面的代码定义了一个只允许保存字符串的列表,尖括号括住的类型就是参数类型,也称泛型。
带泛尖括号括住的类型就是参数类型,也称泛型。
带泛尖括号括住的类型就是参数类型,也称泛型。
带泛尖括号括住的类型就是参数类型,也称泛型。
带泛型的写法给了我们一个类型安全的集合。
型的写法给了我们一个类型安全的集合。
型的写法给了我们一个类型安全的集合。
型的写法给了我们一个类型安全的集合。
集合中存放的是对象,而不能是基本数据集合中存放的是对象,而不能是基本数据类型,在类型,在Java5之后可以使用自动装箱功之后可以使用自动装箱功能,更方便的导入基本数据类型。
能,更方便的导入基本数据类型。
Listlist=newArrayList();Listlist=newArrayList();list.add(newInteger(42);list.add(newInteger(42);list.add(43);list.add(43);ArrayList的排序:
的排序:
ArrayList本身不具备排序能力,但是我们本身不具备排序能力,但是我们可以使用可以使用Collections类的类的sort方法使其排方法使其排序。
序。
System.out.println(System.out.println(排序前:
排序前:
排序前:
排序前:
+list);+list);Collections.sort(list);Collections.sort(list);System.out.println(System.out.println(排序后:
排序后:
排序后:
排序后:
+list);+list);在在for-each出现之后,遍历变得简单一些:
出现之后,遍历变得简单一些:
Listlist=Arrays.asList(one,Listlist=Arrays.asList(one,two,three,four);two,three,four);for(Strings:
list)for(Strings:
list)System.out.println(s);System.out.println(s);作业:
作业:
使用堆栈实现加减乘除的四则运算使用堆栈实现加减乘除的四则运算如:
如:
34+5*6-(23-8)/7设计学生成绩单的输入、查找和输出。
设计学生成绩单的输入、查找和输出。
P263【例12-2】LinkedList常用方法使用使用Iterator类遍历链表类遍历链表迭代器(迭代器(迭代器(迭代器(IteratorIterator),又叫做游标(),又叫做游标(),又叫做游标(),又叫做游标(CursorCursor)。
)。
)。
)。
它提供了遍历访问容器对象中各个元素的方法它提供了遍历访问容器对象中各个元素的方法它提供了遍历访问容器对象中各个元素的方法它提供了遍历访问容器对象中各个元素的方法由容器产生一个对应的迭代器由容器产生一个对应的迭代器由容器产生一个对应的迭代器由容器产生一个对应的迭代器:
IteratorIterator容器对象名容器对象名容器对象名容器对象名.iteratoriterator()()迭代器遍历元素的方法:
迭代器遍历元素的方法:
迭代器遍历元素的方法:
迭代器遍历元素的方法:
BooleanBooleanhasNexthasNext()():
是否仍有元素可以迭代:
是否仍有元素可以迭代:
是否仍有元素可以迭代:
是否仍有元素可以迭代Objectnext()Objectnext():
返回迭代的下一个元素。
返回迭代的下一个元素。
返回迭代的下一个元素。
返回迭代的下一个元素。
voidremove()voidremove():
移除容器中的最后一个元素。
:
移除容器中的最后一个元素。
:
移除容器中的最后一个元素。
:
移除容器中的最后一个元素。
P265P265【例例例例12-312-3】把学生的成绩存放在一个链表中,把学生的成绩存放在一个链表中,把学生的成绩存放在一个链表中,把学生的成绩存放在一个链表中,并遍历链表。
并遍历链表。
并遍历链表。
并遍历链表。
程序运行后的效果如下所示:
程序运行后的效果如下所示:
importimportjava.utiljava.util.*;.*;classclassStackOneStackOnepublicstaticvoidpublicstaticvoidmain(Stringmain(Stringargsargs)StackStackmystackmystack=newStack();=newStack();mystack.push(newmystack.push(newInteger
(1);Integer
(1);mystack.push(newmystack.push(newInteger
(2);Integer
(2);mystack.push(newmystack.push(newInteger(3);Integer(3);mystack.push(newmystack.push(newInteger(4);Integer(4);mystack.push(newmystack.push(newInteger(5);Integer(5);mystack.push(newmystack.push(newInteger(6);Integer(6);while(!
(while(!
(mystack.emptymystack.empty()()Integertemp=(Integer)Integertemp=(Integer)mystack.popmystack.pop();();System.out.printSystem.out.print(+(+temp.toStringtemp.toString();();【例例例例12-512-512-512-5】将数字,将数字,将数字,将数字,6666压入堆栈压入堆栈压入堆栈压入堆栈12.2栈栈Stack栈栈栈栈(StackStack)是是是是一一一一种种种种仅仅仅仅限限限限定定定定在在在在表表表表尾尾尾尾进进进进行行行行插插插插入入入入和和和和删删删删除除除除运运运运算算算算的的的的线线线线性性性性表表表表,是是是是一一一一种种种种后后后后进进进进先先先先出出出出(LIFOLIFO)的的的的数据结构。
数据结构。
数据结构。
数据结构。
只能在一端进行输入或输出数据的操作只能在一端进行输入或输出数据的操作只能在一端进行输入或输出数据的操作只能在一端进行输入或输出数据的操作表表表表尾尾尾尾称称称称为为为为栈栈栈栈顶顶顶顶toptop,表表表表头头头头称称称称为为为为栈栈栈栈底底底底bottombottom。
向向向向堆堆堆堆栈栈栈栈中中中中输输输输入入入入数数数数据据据据的的的的操操操操作作作作称称称称为为为为“压压压压栈栈栈栈”,从从从从栈栈栈栈中中中中输输输输出出出出数据的操作称为数据的操作称为数据的操作称为数据的操作称为“弹栈弹栈弹栈弹栈”。
栈栈栈栈的的的的物物物物理理理理存存存存储储储储可可可可以以以以用用用用顺顺顺顺序序序序存存存存储储储储结结结结构构构构,也也也也可可可可以以以以用用用用链链链链式存储结构。
式存储结构。
式存储结构。
式存储结构。
12.2.1栈的常用方法栈的常用方法使用使用使用使用java.utiljava.util包中的包中的包中的包中的StackStack类创建一个堆栈对象类创建一个堆栈对象类创建一个堆栈对象类创建一个堆栈对象StackStackmyStackmyStack=newStack();=newStack();publicObjectpublicObjectpush(Objectpush(Objectdata)data)publicObjectpop()publicObjectpop()publicpublicbooleanbooleanempty()empty()publicobjectpeek()publicobjectpeek()publicpublicintintsearch(Objectsearch(Objectdata)data)递归是一种很消耗内存的算法,我们可以递归是一种很消耗内存的算法,我们可以借助堆栈消除大部分递归,达到和递归算借助堆栈消除大部分递归,达到和递归算法同样的目的。
法同样的目的。
P271P271例例例例12-612-6使用使用使用使用stackstack输出输出输出输出FibonaciiFibonacii整数序列整数序列整数序列整数序列12.3树集
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Java 语言程序设计 基础教程 课件 12