第1章 Java数据结构及集合框架

java

第一章Java数据结构及集合框架

java

目标 掌握简单的Java数据结构 Java的数组(Array) 向量(Vector) 字符处理(String, StringBuffer ) 集合框架 Java集合框架概述 Collection接口 Set 接口 List 接口 Map 接口 集合框架中常用类比较

复杂数据结构及其Java实现 线性表 堆栈(Stack) 队列(Queue)

列表(List) 链表(Linked List) 集合(Set) 树(Tree) 图(Graph)-2-

java

Java的数组(Array)

一维数组 声明 初始化 引用及示例 顺序表及查找算法 数组间相互赋值 向成员方法传递数组元素 向成员方法传递数组 同类型不同长度的数组引用 同一个成员方法

二维数组 声明

初始化 引用及示例 java.util.Arrays类

数组元素排序 对象数组-3-

java

数组——一维数组：声明 数组在其他语言是相同数据类型的元素的集 合；而Java中，数组是独立的对象，有自身 的方法，不是变量的集合 数组的声明： 类型标识符 数组名[ ];或 类型标识符[ ] 数组名； int intArray [ ]; --([ ]不是指长度可变) int[ ] intArray; int abc[ ]; double[ ] example2; 数组的长度不是在声明时指定，而是在创建 时由所开辟的内存单元数目确定-4-

java

数组——一维数组：声明 数组的创建(3步) – 数组的声明 – 创建数组空间 – 当数组元素为对象时，使用之前必须对数组元素进 行创建和初始化。 创建方法： – 先声明后创建 int intArray [ ] ; intArray = new int [10] ; – 在声明的同时创建 int intArray [ ] = new int [10] ; – 直接赋值 int intArray[ ] = { 1, 2, 3, 4, 5 } ;-5-

java

数组——一维数组：声明我们还可以定义一个复合类型的数组(对象数 组),例如： Date dateArray[ ];

声明了一个容纳复合数据类型Date的数组。与C、C++不同，Java在数组的定义中并不为数 组元素分配内存，因此[ ]中不用指出数组中元素 的个数，即数组长度，而且对于如上定义的一个 数组是不能访问它的任何元素的。必须经过初始

化后，才能应用数组的元素。-6-

java

数组——一维数组：声明

除了这种定义数组的方式之外，java语言还提 供了其他的定义形式，如下所示： type[ ] arrayName; 对于以上举出的例子，我们也可以这样定义：

int[ ] intArray;Date[ ] dateArray;

-7-

java

数组——一维数组：初始化 声明数组仅为数组指定数组名和数组元素的类型，并没

有为元素分配实际的存储空间。 因为Java的数组声明中并未指出数组元素的个数，在Java中指明元素个数放在初 始化进行。初始化后，其长度(即可存放的元素个数)就不 可再改变。 数组的初始化分为静态初始

化和动态初始化两种：

静态初始化：在定义数组的同时对数组元素进行初始化，例如： int intArray[ ]={1,2,3,4};//定义了一个含有4个

// 元素的int型数组。-8-

java

数组——一维数组：初始化动态初始化：使用运算符new为数组分配空间，对于简单类型的数组，其格式如下：

type arrayName[ ]=new type[arraySize];type[ ] arrayName=new type[arraySize]; 对于复合类型的数组，需要经过两步空间分配。 首先： type arrayName[ ]=new type[arraySize]; 然后：arrayName[0]=new type(paramList); … arrayName[arraySize-1]=new type(paramList);

-9-

java

数组——一维数组：初始化例如： String stringArrar[]; //定义一个String类型的数组

stringArray = new String[3]; //给数组stringArray 分配3个应用 //空间，初始化每个引用值为null stringArray[0]=new String(“how”); 初始化各数组元素 stringArray[1]=new String(“are”); stringArray[2]=new String(“you”);-10-

java

数组——一维数组：引用当定义了一个数组，并用运算符new为它分配 了内存空间后，就可以引用数组中的每一个元 素了。元素的引用方式为： arrayName[index] index为数组下标，可以是整型常数或表达 式，如：arrayName[1], arrayName[i], arrayName[6*i]等。下标是0序的，即从0开始， 一直到数组长度减1。-11-

java

数组——一维数组：边界检查

另外，与C、C++中不同，Java对数组元素要进 行越界检查以保证安全性。同时，对于每个数组 都有一个属性length指明它的长度，例如： intArray.length指明数组intArray的长度。

-12-

java

数组——一维数组：示例 例Li1_1.java 对数组中的每个元素赋值，然后按逆序输出。

例Li1_2.java 用数组求解Fibonacci数列的前20项，即使用数组 下标表达式求解数学上的迭代问题。

-13-

java

顺序表及查找算法 以数组的形式组织和存放数据的数据结构被称为 顺序表。 对于顺序表的查找，人们已经发明了许多种算法， 典型的有顺序查找和二分(折半、对分)查找。 顺序查找是将待查值与顺序表(数组)中的每个元 素逐一比较，直至查找成功或到达数组的最后一 个元素还未找到。这种查找的效率相对较低。

-14-

java

顺序表及查找算法 二分查找是在一个有序表(数据是按其值由小到大或由大到

小依次存放的，这里我们以值由小到大排列为例)中，每次都与中间的那个元素比较，若相等则查找成功；否则，调整

查找范围，若中间那个元素的值小于待查值，则在表的后一半中查找；若中间那个元素的值大于待查值，则在表的前一 半中查找；如此循环，每次只与一半中的一个元素比较，可 使查找效率大大提高。 例：设数组中的数值是由小到大存放的，编写二分查找算法 程序查找指定元素

的位置(数组下标)。 FindSearch.java Li1_3.java-15-

java

运行结果：

二分查找的比较与下标调整过程

-16-