实用数据结构辅导知识点Word文档格式.docx
- 文档编号:8595519
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:35
- 大小:357.62KB
实用数据结构辅导知识点Word文档格式.docx
《实用数据结构辅导知识点Word文档格式.docx》由会员分享,可在线阅读,更多相关《实用数据结构辅导知识点Word文档格式.docx(35页珍藏版)》请在冰点文库上搜索。
减半查找范围,确定待查元素是否存在于数组中。
1、获取中间元素的位置,拿带查元素与中间位置元素比较;
2、比中间元素大,在后半部分找;
3、比中间元素小,在前半部分找。
注意问题:
✓sort()的使用
✓binarySearch()的使用
✓数组与Arrays类的区别
练习:
请参见读程序写结果中——程序1、程序2、程序3
2List、ArrayList
1.掌握ArrayList的具体使用2.掌握List接口的实现
ArrayList是一种线性表,在内存中是连续存储的,适合于元素的随机存取。
添加和删除操作是需要依据添加的位置来定,如果在ArrayList最后元素后面添加和删除元素,在性能方面还算好,但是如果是在ArrayList中间添加和删除元素的话,代价就会很大。
1.ArrayList结构特点:
数组大小固定,ArrayList可以自动增加空间
ArrayList常用方法:
size()返回此列表中的元素数。
get()返回此列表中指定位置上的元素。
set()用指定的元素替代此列表中指定位置上的元素。
add()将指定的元素添加到此列表的尾部;
将指定的元素插入此列表中的指定位置。
contains()如果此列表中包含指定的元素,则返回true。
remove()移除此列表中指定位置上的元素。
Object[]toArray()按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组。
3.遍历方法
①for循环语句:
for(inti=0;
i<
…;
i++)
②迭代器:
Iteratorit=list.iterator();
while(it.hasNext())
{Ee=it.next();
…}
③forEach结构:
for(Ee:
list){…}
4.了解ArrayList与Vector的区别
5.List接口的实现
6.继承关系如下图:
1.List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。
2.List接口与其常用实现类的继承实现关系:
3.对比List接口的两个常用实现类
简述
实现
操作特性
成员要求
List
提供基于索引的对成员的随机访问
ArrayList
提供快速的基于索引的成员访问,对尾部成员的增加和删除支持较好
成员可为任意
Object子类的对象
LinkedList
对列表中任何位置的成员的增加和删除支持较好,但对基于索引的成员访问支持性能较差
1、上机实现下面程序
publicstaticvoidmain(String[]args)
{
Listlist=newArrayList();
for(inti=0;
5;
i++){
list.add("
编程词典"
+i);
}
ListIteratorli=list.listIterator();
while(li.hasNext()){
System.out.println(li.next());
1、练习:
请参见读程序写结果中——程序4、程序5
2、创建一个类Cat:
包含属性name,在构造方法中进行初始化;
添加一个方法show(),用以打印name属性的值
创建一个类CatTest:
添加main方法,实现创建一个ArrayList,向其中添加几个Cat对象遍历该集合,并且对每个Cat对象调用show()方法
参考代码:
classCat{
privateStringname;
publicCat(Stringname){
this.name=name;
publicvoidshow(){
System.out.println(name);
}
publicclassCatTest{
publicstaticvoidmain(String[]args){//创建一个ArrayList,向其中添加几个Cat对象;
ArrayListlist=newArrayList();
list.add(newCat("
mimi"
));
list.add(newCat("
qiqi"
ding"
//遍历该集合,并且对每个Cat对象调用show()方法。
for(inti=0;
list.size();
Catc=(Cat)list.get(i);
c.show();
}}}
3LinkedList
1.掌握LinkedList类的使用方法2.掌握栈和队列的概念
1.结点、链表的概念以及链式存储的思想
2.LinkedList类的常用方法(对比ArrayList)的掌握
3.与ArrayList类比较,各自特点,如何应用、选择
LinkedList的常用方法:
add()向链表末尾添加一个新的节点
remove()删除指定位置上的节点;
删除首次出现含有数据elemen的节点。
get()得到链表中指定位置处节点中的对象。
set()将当前链表index位置结点中的对象替换为参数element指定的对象,并返回被替换的对象。
4.用LinkList类实现栈和队列栈中常用方法:
pop()从此列表所表示的堆栈处弹出一个元素。
push()将元素推入此列表所表示的堆栈。
新增以下新方法:
构造方法LinkedList()
getFirst()和getLast()
removeFirst()和removeLast()
addFirst()和addLast()
5、类继承关系如图:
List接口实现:
1.LinkedList是采用双向循环链表实现的。
2.利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-endedqueue)
采用链表的方法来实现栈:
用方法addFirst(Objectelement)实现进栈操作。
用方法removeFirst()实现出栈。
用方法getFirst()实现栈顶数据查询。
用方法isEmpty()实现栈是否为空。
请参见读程序写结果中——程序6、程序7、程序7
上机操作:
创建一个类Stack,代表堆栈(其特点为:
后进先出),添加方法add(Objectobj)、以及delete(),添加main方法进行验证,要求:
☐使用LinkedList实现堆栈
☐在向LinkedList中添加时,使用addLast()方法
☐在从LinkedList中取出时,使用removeLast()方法
4Collections与Collection
1.会使用Collections类2.掌握Collection接口
1.了解Collection接口
2.掌握Collection接口常用方法
3.掌握Collections类中常用方法
Collection接口中常用方法:
toArray()
返回包含此collection中所有元素的数组。
add()
确保此collection包含指定的元素。
equals()
比较此collection与指定对象是否相等。
hashCode()
返回此collection的哈希码值。
size()
返回此collection中的元素数。
iterator()返回调用类集的迭代程序
remove()从调用类集中删除obj的一个实例。
如果这个元素被删除了,则返回true;
否则返回false
4.Comparable与Comparator
的区别联系
5、Collections类的继承关系:
Collections类中常用方法:
binarySearch()使用二分搜索法搜索指定列表,以获得指定对象。
sort()
根据元素的自然顺序对指定列表按升序进行排序。
synchronizedMap()
返回由指定映射支持的同步(线程安全的)映射。
synchronizedSet()
返回指定set支持的同步(线程安全的)set。
sort()、reverse()、max()、min()、fill()等方法
6、Collection接口的继承关系:
1.Collections中的大多数方法都与List或collection有关。
1.Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。
一些Collection允许相同的元素而另一些不行。
一些能排序而另一些不行。
JavaSDK不提供直接继承自Collection的类,JavaSDK提供的类都是继承自Collection的“子接口”如List和Set。
2.Collections类完全由在collection上进行操作或返回collection的静态方法组成。
它包含在collection上操作的多态算法,即“包装器”,包装器返回由指定collection支持的新collection,以及少数其他内容。
2、Collection的遍历:
Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代器,使用该迭代器即可逐一访问Collection中每一个元素。
借助Iterator接口实现。
Iterator接口结构:
模板代码:
Iteratorit=collection.iterator();
//获得一个迭代器
while(it.hasNext()){
Objectobj=it.next();
//得到下一个元素
}
利用Collection接口的iterator()获得一个实现了Iterator接口的迭代器,然后利用其完成Collection接口对象的遍历操作。
模板代码如右所示:
对象排序方法:
1、Comparable接口
所有可以”排序“的类都实现了java.lang.Comparable接口
Comparable接口中只有一个方法:
publicintcompareTo(Objectobj);
2、Comparator接口
Comparator通常在对于自然排序不能满足需要时使用。
Comparator接口定义了两个方法:
compare(
)和equals(
)。
publicinterfaceComparator<
T>
intcompare(To1,To2);
booleanequals(Objectobj);
请参见读程序写结果中——程序9(Collections)
请参见读程序写结果中——程序10(Collections、Iterator接口)
请参见读程序写结果中——程序11(Comparator接口)
5Set与HashSet
1.掌握Set接口常用方法2.掌握HashSet的特点及学会使用HashSet类3.了解其它的Set接口实现类
1、Set接口:
扩展了Collection接口,Set接口是Collection接口的子接口,不包含重复元素。
它采用所有原始方法,并且未引入任何新方法。
继承关系如下图:
Set接口定义:
publicinterfaceSet<
E>
extendsCollection<
……//接口定义请参照API帮助文档
Set接口中的常用方法:
2、Set接口提供了两种通用实现:
HashSet和TreeSet
HashSet,采用散列函数对元素进行排序,这是专门为快速查询而设计的;
来存储不重复的集合。
TreeSet,当需要以一种排序的方式从集合中提取元素的时候使用。
为了正确运行,添加到TreeSet中的元素必须是可排序的。
采用二叉树的数据结构进行排序元素。
3、HashSet类定义:
是Set接口最常用的实现之一,存入HashSet的对象必须定义hashCode(),其元素在其中存储不保证任何顺序。
实际上,HashSet存储对象引用时是按照哈希策略来实现的。
publicclassHashSet<
extendsAbstractSet<
implementsSet<
Cloneable,java.io.Serializable{
……//具体方法实现参考API帮助文档
HashSet类常用方法:
HashSet类继承关系:
HashSet类的几个构造器:
publicHashSet():
该构造器将构造一个空的HashSet对象。
该对象的初始容量为16。
publicHashSet(intinitalCapacity):
参数initalCapacity表示指定的初始容量,该构造器将构造一个具有指定容量的空HashSet对象。
publicHashSet(Collectionc):
参数c为包含指定元素的Collection。
该构造器将构造一个以c中的元素为初始内容的HashSet对象。
4、TreeSet类定义:
实现了SortedSet接口,此类保证排序后的Set按照升序排列元素,底层为树结构。
使用它可以从Set中提取有序的序列。
publicclassTreeSet<
implementsNavigableSet<
Cloneable,java.io.Serializable
{……}
TreeSet类继承关系:
TreeSet类中常用方法见右图:
1.Set中的几个重要方法:
equals()、contains()、hashCode()
2.Set接口中元素具有唯一性,改写equals()方法。
Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。
3.HashSet散列(hash),特点:
查找的高效率(例如两个集合相交),改写hashCode()方法
分析:
HashSet要求放入的对象必须实现hashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的String对象,hashcode是一样,所以放入的内容不能重复。
但是同一个类的对象可以放入不同的实例。
4.了解其它的Set相关类:
LinkedHashSet
随堂练习:
1、分析程序,写出结果
importjava.util.Collection;
importjava.util.HashSet;
importjava.util.Iterator;
publicclassSetTest2{
publicstaticvoidmain(String[]args){
Collectionc;
c=newHashSet();
c.add("
1"
);
3"
2"
Iteratorit=c.iterator();
while(it.hasNext()){
System.out.println(it.next());
//返回集合元素
2、分析程序,写出结果
importjava.util.*;
publicclassHashSetTest{
publicstaticvoidmain(String[]args){
HashSetset=newHashSet();
set.add("
1st"
2nd"
3rd"
set.add(newString("
Four"
set.add(newInteger(6));
set.add(“2nd”);
//重复的元素没有被加入
System.out.println(set);
//元素的顺序与加入的顺序没有关系
请参见读程序写结果中——程序12(Arrays和HashSet)
请参见读程序写结果中——程序13(TreeSet和SortedSet)
6Map与HashMap
1.掌握Map接口的使用2.掌握HashMap类的应用
1、Map接口:
将键映射到值的对象。
一个映射不能包含重复的键;
每个键最多只能映射到一个值。
Map看起来比较像由映射组成的Set。
Map接口不是Collection接口的继承。
定义:
publicinterfaceMap<
K,V>
{
……//具体方法请查看API帮助文档
继承关系:
Map接口中常见方法:
其中重要方法:
get()、put()、equals()、hashCode()、keySet()、values()、containsKey()、containsValue()
2、Map接口的可用实现类主要有:
HashMap,TreeMap,Hashtable,Properties
其中:
Hashtable,Properties是JDK1.0/1.1中的。
①HashMap对key进行散列。
HashMap通过哈希码对其内部的映射关系进行快速查找。
②TreeMap按照key进行排序。
TreeMap中的映射关系存在一定的顺序,如果希望在遍历集合时是有序的,则应该使用由TreeMap类实现的Map集合,否则建议使用由HashMap类实现的Map集合,因为由HashMap类实现的Map集合对于添加和删除映射关系更高效。
3、Map接口提供三种collection视图
允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。
允许以三种方法将映射视作集合。
如下表:
keySet是映射中包含的键集
Setkeys=map.keySet();
values是映射中的值的集合
Collectionsvalues=map.values();
entrySet是包含在映射中的键-值对的集
Setkvs=map.entrySet();
4、HashMap类定义:
HashMap类实现了Map接口
publicclassHashMap<
extendsAbstractMap<
implementsMap<
Cloneable,Serializable{
HashMap类常见方法见右图:
其中重要的方法有:
HashMap的常用方法:
5、HashMap类说明:
①由HashMap类实现的Map集合,允许以null作为键对象,但是因为键对象不可以重复,所以这样的键对象只能有一个。
如果经常需要添加、删除和定位映射关系,建议利用HashMap类实现Map集合,不过在遍历集合时,得到的映射关系是无序的。
②在使用由HashMap类实现的Map集合时,需要重写作为主键对象类的hashCode()方法
重写hashCode()方法时,有以下两条基本原则:
(1)不唯一原则:
不必为每个对象生成一个唯一的哈希码,只要通过hashCode方法生成的哈希码能够利用get()方法得到利用put()方法添加的映射关系就可以。
(2)分散原则:
生成哈希码的算法应尽量使哈希码的值分散一些,不要很多哈希码值都集中在一个范围内,这样有利于提高由HashMap类实现的Map集合的性能。
6、遍历HashMap的方法:
//遍历方法1
for(Iteratoriter=map.keySet().iterator();
iter.hasNext();
)
System.out.println(iter.next());
//遍历方法2
Iteratoriter=map.keySet().iterator();
while(iter.hasNext()){
System.out.println(iter.next());
7、TreeMap类定义:
TreeMap类不仅实现了Map接口,还实现了Map接口的子接口java.util.SortedMap。
支持对键有序地遍历,使用时建议先用HashMap增加和删除成员,最后从HashMap生成TreeMap。
publicclassTreeMap<
K,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实用 数据结构 辅导 知识点
![提示](https://static.bingdoc.com/images/bang_tan.gif)