实用数据结构辅导知识点.doc

常璐璐，赵玉霞编

常璐璐，赵玉霞编

学习目标：

1.掌握关于数组概念2.掌握Arrays类以及常用方法

回忆数组概念、定义及使用；

掌握Arrays类常用方法

继承关系：Arrays类是Object类直接子类。如下图所示：

Arrays类常用方法:

sort()对指定的类型数组按数字升序进行排序。binarySearch()使用二分搜索法来搜索指定的类型数组，以获得指定的值。

equals()用于比较两个数组是否相等。

fill()用以某个值填充整个数组。

asList()接受任意的数组为参数，将其转变为List容器。

Java的二分查找算法:

privatestaticintbinarySearch0(Object[]a,intfromIndex,inttoIndex,Objectkey){

intlow=fromIndex;

inthigh=toIndex-1;

while(low=high){

intmid=(low+high)/2;

ComparablemidVal=(Comparable)a[mid];

intcmp=midVpareTo(key);

if(cmp0)

low=mid+1;

elseif(cmp0)

high=mid-1;

else

returnmid;//keyfound

}

return-(low+1);//keynotfound.

}

算法思想描述：

查找的数组必须是按关键字值排好序；减半查找范围，确定待查元素是否存在于数组中。

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.继承关系如下图：

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。

List接口与其常用实现类的继承实现关系：

对比List接口的两个常用实现类

简述

实现

操作特性

成员要求

List

提供基于索引的对成员的随机访问

ArrayList

提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好

成员可为任意

Object子类的对象

LinkedList

对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差

成员可为任意

Object子类的对象

1、上机实现下面程序

publicstaticvoidmain(String[]args)

{

Listlist=newArrayList();

for(inti=0;i5;i++){

list.add(编程词典+i);

}

ListIteratorli=list.listIterator();

while(li.hasNext()){

System.