Java程序设计大学教程第五章 算法与数据结构程序是建立在数据结构基础上使用计算机语言描述的算法，因此简单地讲，程序也可以表示成：算法＋数据结构。
介绍算法的概念及常用算法。并通过数组、
链表、栈、队列等数据结构以及 Java对象容器，讨论算法的应用及算法的 Java程序实现。
Java程序设计大学教程
5.1 算法算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征,
确切性（ No ambiguity） 算法的每一步骤必须有确切的定义。而不应该有二义性，例如，在算法中不能出现诸如,赋值为
100或 1000”。
输入（ Input） 有 0个或多个输入，用于初始化运算对象。所谓 0个输入是指无需输入条件，而算法本身定出了初始条件。
输出（ Output） 没有输出的算法是毫无意义的。一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。
可行性（ Feasibility） 算法原则上能够精确地运行，而且对于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运算后完成。
有穷性（ Finite） 算法必须保证执行有限步之后结束。只具有前面四个特征的规则集合，称不上算法。例如，尽管操作系统能完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执行、等待执行，所以操作系统不是算法。
Java程序设计大学教程
5.1.1 算法的描述
1、伪代码描述,
伪代码（ Pseudo-code）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（如
Pascal,C,Java等）实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。
伪代码描述的算法：
1,x ← 0
2,y ← 0
3,z ← 0
4,while x < 100
4.1 do x ← x + 1
4.2 y ← x + y
4.3 for t ← 0 to 10
4.3.1 do z ← ( z + x * y ) / 100
4.3.2 repeat
4.3.2.1 y ← y + 1
4.3.2.2 z ← z - y
4.3.3,until z < 0
4.4,z ← x * y
5,y ← y / 2
Java代码实现：
int x = 0;
int y = 0;
int z = 0;
while ( x < 100 ) {
x = x + 1;
y = x + y;
for ( int t = 0,t <= 10,t++ ) {
z = ( z + x * y ) / 100;
do {
y = y + 1;
z = z - y;
} while (z < 0);
};
z = x * y;
}
y = y / 2;
Java程序设计大学教程
5.1.1 算法的描述
2、图形描述,
程序设计中，能够用来表示算法基本概念的图主要有,PAD图,N\S盒图、流程图。
处理 1
处理 2
处理 1 处理 2 处理 条件否,
是条件处理是条件否,
端点符 处理 判断 预定义处理连接符顺序结构 选择结构
(while-do) (repeat-until)
循环结构程序流程图常用图形符号及控制结构图例
Java程序设计大学教程
5.1.2 常用算法
基本算法大都比较简单，
是其他算法的基础。这类算法在程序中应用非常普遍，如：
累加求和、
累乘求积、
求最大和最小值等。
从 10个数中求最大值算法 的例子开始初始化,将 largest和 counter设为 0
计数器判断
counter <10?
否,
是
while-do
循环
largest← theInteger
大值比较
theInteger>larges?
否,
是返回 largest
结束输入被比较的数 theInteger
计数,counter←counter+1
伪代码描述算法：
FindLargest
Input,10 positive integers
1,largest← 0
2,counter← 0
3,while(counter < 10)
3.1 Input theInteger
3.2 if (theInteger > largest)
then
3.2.1 largest← theInteger
end if
3.3 counter← counter+1
end while
4,Return largest
End
1,Java语言实现：
2,import java.io.*;
3,public class Max {
4,public static void main(String[] args) throws IOException {
5,//初始化
6,BufferedReader input = new BufferedReader
7,(new InputStreamReader(System.in));
8,int largest=0;
9,int counter=0;
10,int theInteger=0;
11,//循环比较
12,while(counter < 10) {
13,//输入被比较的数
14,counter++;//计数
15,System.out.println("请输入第 "+counter+"个被比较的数,");
16,String inputString = input.readLine();
17,theInteger = Integer.parseI t(inputString);
18,//大值比较
19,if (theInteger > largest) largest=theInteger;
20,}// while
21,System.out.println("求出最大数是,"+largest);
22,}
23.
24.}
Java程序设计大学教程
5.1.2 常用算法
排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找效率。常用的排序方法包括：选择排序、冒泡排序、插入排序、快速排序、合并排序、希尔排序、堆排序等。
查找是一种在列表中确定目标所在位置的算法。基本的查找方法有顺序查找和折半查找。
迭代和递归是用于编写解决问题的算法的两种途径。
迭代就是反复替换的意思，它通过使用一个中间变量保存中间结果，不断反复计算求解最终值。递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。
阶乘迭代算法伪代码,
Factorial
Input:Apositive integer num
1,FactN← 1
2,i← 1
3,While（ i < or = num）
3.1 FactN← FactN × i
3.2 Increment i
end while
Return FactN
end
阶乘递归算法伪代码,
Factorial
Input:A positive integer num
1,if（ num = 0）
then
1.1 Return 1
else
1.2 return num× Factorial(num-1)
end if
end
Java程序设计大学教程
5.2 数组
数组用于表示相同类型的元素的有序集合，
数组中每个元素都有一个唯一的索引。
根据数组的分配方式可将数组分为：一维数组和多维数组。 Java中还可以定义不规则数组。我们可以把一维以上的数组看作是,数组的数组,。
Java程序设计大学教程
5.2.1 数组的创建和使用
数组是一个被命名的连续存储区域的集合，存放着相同类型的数据项。数组的每个元素通过它在数组里的位置索引来引用。数组索引必须是一个整数值或者一个整数表达式。
在 Java里，大多数情况下数组被当成对象来对待。它们是用 new操作符来实例化的，有自己的实例变量（例如 length，可返回数组中第一维的元素数量）。数组变量是引用类型的变量。
定义与创建一个数组的语法及例子。
定义与创建一个数组的语法：
数组类型名称 [] 数组变量名 ;//定义数组变量
(也可以写成：数组类型名称 数组变量名 [];//定义数组变量 )
数组变量名 = new 数组类型名称 [n];//创建长度为 n
的数组以上两步也可以合并写为：
数组类型名称 数组变量名 []= new 数组类型名称 [n];
或者：
数组类型名称 [] 数组变量名 = new 数组类型名称 [n];
定义与创建一个数组的示例：
Fruit[] fruits ; //定义 Fruit类型的数组变量 fruits
fruits = new Fruit[5]; //新建有 5个元素的数组 fruits
fruits[0] = new Fruit("香蕉 ",1000);//为数组元素赋值（引用对象）
fruits[1] = new Fruit("葡萄 ",2000);
fruits[2] = new Fruit("菠萝 ",2000);
fruits[3] = new Fruit("草莓 ",1000);
fruits[4] = new Fruit("橘子 ",1000);
int n = fruits.length; //测试数组长度
Java程序设计大学教程用不规则数组实现
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
用 2维数组实现 每日股指显示
0 1 2 3 4 5
1 1133 1995 1500 1655 1033
2 1605 1981 1143 1226 1265
3 1226 1015 1648 1411 1007
4 1754 1472 1680 1793 1065
5 1469 1707 1745 1477 1742
...,..
52 1578 1550 1309 1139 1357
5.2.1 多维数组和不规则数组
根据数组的分配方式可将数组分为：一维数组和多维数组。 Java中还可以定义不规则数组。
我们可以把一维以上的数组看作是,数组的数组,。
模拟每日股指的程序 Stock
1,public class Stock {
2,public Stock() {
3,for (int week=1;week<=52;week++){
4,stockValue[week][0]=week;
5,for (int weekday=1;weekday<=5;weekday++){
6,stockValue[0][weekday]=weekday;
7,int stockIndex = (int)(Math.random()*1000+1000);
8,stockValue[week][weekday] = stockIndex;
9,}
10,}
11,}
12.
13,public void printStock(){
14,for (int week=0;week<=52;week++){
15,for (int weekday=0;weekday<=5;weekday++){
16,System.out.print(stockValue[week][weekday]+"\t");
17,}
18,System.out.println();
19,}
20,}
21.
22,public static void main(String[] args) {
23,Stock s=new Stock();
24,s.printStock();//打印股指年表
25,}
26.
27,int stockValue[][]= new int[53][6];
28.}
不规则数组演示程序 ArrTest
public cla s ArrTest {
public ArrTest() {
for (int n=1;n<myArr.length;n++){
myArr[n] = new int[n+1];//创建数组的数组，每个数组的长度不一样。
for (int m=1; m<myArr[n].length; m++){
myArr[n][m]=m;
}
}
}
public void printArr(){
for (int n=1; n<myArr.length; n++){
for (int m 1 m<myArr[n].length;m++){
System.out.print(myArr[n][m]+"\t");
}
System.out.println();
}
}
public static void main(String[] args) {
ArrTes arr=new ArrTest();
arr.printArr();
}
int myArr[][]= new int[Max+1][];//定义不规则数组，先创建数组的第 1维。
static int Max=6;
}
Java程序设计大学教程
5.2.3 排序
冒泡法的基本思想是，将待排序的元素看作是竖着排列的,气泡,,较小的元素比较轻，从而要往上浮；较大的元素比较重，从而要往下沉。一个含有 n个元素的列表，冒泡排序需要 n-1次扫描来完成数据排序。
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一轮排序将待排序的数组元素分割成独立的两部分，其中一部分元素的关键字均比另一部分元素的关键字小，则分别可对这两部分元素继续进行排序，以达到整个数组序列有序。
冒泡排序比较和交换的过程演示
2 3 5 8 7 6 9 10 49 25
2 5 3 8 7 6 9 10 49 25
492 3 5 7 6 8 9 10 25
第 2次比较第 3次比较第一轮的最后一次比较比较交换比较比较交换
......
2 5 3 8 7 6 9 10 49 25第 1次比较比较不交换不交换
Java程序设计大学教程
5.2.4 查找
顺序查找就是将要查找的数据的关键字按一定的顺序挨个与列表中的数据进行比较，相等时就找到了所要的数据。
对有序的列表可以使用更有效率的折半查找。折半查找是从一个列表的中间的元素来测试的，这将能够判别出目标在列表里的前半部还是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。换句话说，
可以通过判断排除一半的列表。重复这个过程直到找到目标或是目标不在这个列表里。
顺序查找和折半查找示例程序：
public class Search {
//顺序查找
public int sequentialSearch(int arr[],int key) {
for (int k = 0; k < arr.length; k++)
if (arr[k] == key)
return k; // 成功,返回该数组元素的位置（即索引）
return -1; // 失败,返回 -1
}
//折半查找
public int binarySearch(int arr[],int key) {
int low = 0; // 初始化
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2; // 取折半值
if (arr[mid] == key)
return mid; // 成功,返回该数组元素的位置（即索引）
else if (arr[mid] < key)
low = mid + 1; // 定位查找上半段
else
high = mid - 1; // 定位查找下半段
}
return -1; // 失败,返回 -1
}
}
Java程序设计大学教程
5.3 对象容器
使用数组管理对象虽然有较高的计算效率，但是数组要求固定对象的数量，操作起来并不方便。特别当对象数量不明确的情况下，我们需要更复杂的方法来管理对象。
Java类库中提供了一些用于管理对象集的类，称之为容器类（ container classes）。它们可以在程序中用作对象的容器，持有和操作对象而不用担心容量的变化。
Java容器的缺点是：一旦把对象放进容器，便失去了该对象的类型信息。容器中对象集的元素都是最基本的 Object
类型，也就是说，无论是何种类型的对象，进入容器后都向上转型为 Object。因此，当我们从容器中取出对象时，
可能无法知道它原来的类型。如果知道或者可以通过某种算法来判定出原来的类型，则可以将其转型为最初的实际类型。
Java程序设计大学教程
5.3.1 Java容器框架
列表（ list） 按照一定次序排列的对象集，对象之间有次序关系。
集合（ set） 无次序的对象集，但这些对象都是唯一的，不会重复。
映射（ map） 一群成对的对象集，这些对象各自保持着,键 -值,（ key-
value）对应关系。其中，作为,键,的那些对象一定是一个 set，即这些对象是唯一的，不会重复。
a d a c
a
b
c
d
e
a
b
c
v23
b
0 1 2 … n4
v41
v23
v17
d
list
map
set
Java程序设计大学教程
5.3.2 Collection与 Iterator
Collection是 Java容器框架中的高层接口，它声明了所有容器类的核心方法，包括添加、清除、比较和持有对象
（也称为对象集的元素）的操作。此外,Collection接口还提供了一个方法用于返回 Iterator。
迭代器是一个实现了 Iterator或 ListIterator接口的对象。
它是一种,轻量级,的对象，消耗较小的资源，具有较高的效率，能够满足对象集的遍历。
Java程序设计大学教程
5.3.3 List及 ListIterator
编程中最常用到的是 List容器。 List容器的重要属性是对象按次序排列。 List通常由 ArrayList和 LinkList来实现，它提供了列表的插入、删除、定位、截取、遍历等操作。
ArrayList 以可变数组实现完成的 List容器。允许快速随机访问，
但是当元素的插入或移除发生于 List中央位置时，效率便很差。
对于 ArrayList，建议使用 ListIterator来进行向后或向前遍历，
但而不宜用其来进行元素的插入和删除，因为所花代价远高于
LinkedList。
LinkedList 以双向链表（ double-linked 1ist）实现完成的
List容器。最佳适合遍历，但不适合快速随机访问。插入和删除元素效率较高。它还提供 addFirst,addLast,getFirst、
getLast,removeFirst,removeLast等丰富的方法，可用于实现栈和队列的操作。
Java程序设计大学教程
5.4 抽象数据类型
抽象数据类型（ ADT）是把与对该数据类型有意义的操作封装在一起的数据声明。它将数据和操作封装起来，
用户可通过操作接口对数据进行操作。
常用的抽象数据类型有链表、栈、对列等。
Java程序设计大学教程
5.4.1 链表
链表是一组互相链接的元素序列，分为：单链表、循环链表、双向链表等。若在这个序列中每个元素总是与它前面的元素相链接
（除第一个元素外），则形成单链表。单链表关系的实现可以通过指针来描述。
在 Java类库中,LinkedList可以当作链表使用，它能实现链表常用的操作，包括：增加、删除、定位、遍历等，这足够解决一切关于有序列表的问题。使用 LinkedList链表还能实现栈和队列。
1000 A
1200
B
1312
C
1423
head 1000 1200 1312
D
1423
空指针指针节点
h r
非空循环链表
rh
空表链表示意图
Java程序设计大学教程
5.4.2 栈
栈是限定仅在一端进行插入或删除操作的线性表。栈又称为后进先出（ LIFO）线性表，其主要操作为进栈（ push）和出栈
（ pop）。栈的应用非常广泛，如：倒转数据、回溯等。
栈栈顶栈栈顶数据栈栈顶栈栈顶数据入栈操作出栈操作
Java程序设计大学教程
5.4.3队列
队列是线性列表的一种特殊情况，其所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。队列的结构特点是先进队列的元素先出队列。队列又称为先进先出（ FIFO）
线性表，其主要操作为入列（ enqueue）和出列（ dequeue）。
对列主要应用于排队处理用户请求、任务和指令。在计算机系统中，需要用队列来完成对作业或对系统设备如打印池的处理。
a1 a2 a3 an
队尾队头入列出列
介绍算法的概念及常用算法。并通过数组、
链表、栈、队列等数据结构以及 Java对象容器，讨论算法的应用及算法的 Java程序实现。
Java程序设计大学教程
5.1 算法算法是为了求解某一问题在有限步骤内、定义了具体操作序列的规则集合。一个算法应该具有以下五个重要的特征,
确切性（ No ambiguity） 算法的每一步骤必须有确切的定义。而不应该有二义性，例如，在算法中不能出现诸如,赋值为
100或 1000”。
输入（ Input） 有 0个或多个输入，用于初始化运算对象。所谓 0个输入是指无需输入条件，而算法本身定出了初始条件。
输出（ Output） 没有输出的算法是毫无意义的。一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。
可行性（ Feasibility） 算法原则上能够精确地运行，而且对于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运算后完成。
有穷性（ Finite） 算法必须保证执行有限步之后结束。只具有前面四个特征的规则集合，称不上算法。例如，尽管操作系统能完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执行、等待执行，所以操作系统不是算法。
Java程序设计大学教程
5.1.1 算法的描述
1、伪代码描述,
伪代码（ Pseudo-code）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（如
Pascal,C,Java等）实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。
伪代码描述的算法：
1,x ← 0
2,y ← 0
3,z ← 0
4,while x < 100
4.1 do x ← x + 1
4.2 y ← x + y
4.3 for t ← 0 to 10
4.3.1 do z ← ( z + x * y ) / 100
4.3.2 repeat
4.3.2.1 y ← y + 1
4.3.2.2 z ← z - y
4.3.3,until z < 0
4.4,z ← x * y
5,y ← y / 2
Java代码实现：
int x = 0;
int y = 0;
int z = 0;
while ( x < 100 ) {
x = x + 1;
y = x + y;
for ( int t = 0,t <= 10,t++ ) {
z = ( z + x * y ) / 100;
do {
y = y + 1;
z = z - y;
} while (z < 0);
};
z = x * y;
}
y = y / 2;
Java程序设计大学教程
5.1.1 算法的描述
2、图形描述,
程序设计中，能够用来表示算法基本概念的图主要有,PAD图,N\S盒图、流程图。
处理 1
处理 2
处理 1 处理 2 处理 条件否,
是条件处理是条件否,
端点符 处理 判断 预定义处理连接符顺序结构 选择结构
(while-do) (repeat-until)
循环结构程序流程图常用图形符号及控制结构图例
Java程序设计大学教程
5.1.2 常用算法
基本算法大都比较简单，
是其他算法的基础。这类算法在程序中应用非常普遍，如：
累加求和、
累乘求积、
求最大和最小值等。
从 10个数中求最大值算法 的例子开始初始化,将 largest和 counter设为 0
计数器判断
counter <10?
否,
是
while-do
循环
largest← theInteger
大值比较
theInteger>larges?
否,
是返回 largest
结束输入被比较的数 theInteger
计数,counter←counter+1
伪代码描述算法：
FindLargest
Input,10 positive integers
1,largest← 0
2,counter← 0
3,while(counter < 10)
3.1 Input theInteger
3.2 if (theInteger > largest)
then
3.2.1 largest← theInteger
end if
3.3 counter← counter+1
end while
4,Return largest
End
1,Java语言实现：
2,import java.io.*;
3,public class Max {
4,public static void main(String[] args) throws IOException {
5,//初始化
6,BufferedReader input = new BufferedReader
7,(new InputStreamReader(System.in));
8,int largest=0;
9,int counter=0;
10,int theInteger=0;
11,//循环比较
12,while(counter < 10) {
13,//输入被比较的数
14,counter++;//计数
15,System.out.println("请输入第 "+counter+"个被比较的数,");
16,String inputString = input.readLine();
17,theInteger = Integer.parseI t(inputString);
18,//大值比较
19,if (theInteger > largest) largest=theInteger;
20,}// while
21,System.out.println("求出最大数是,"+largest);
22,}
23.
24.}
Java程序设计大学教程
5.1.2 常用算法
排序算法根据数据的值对它们进行排列。排序是为了把不规则的信息进行整理，以提高查找效率。常用的排序方法包括：选择排序、冒泡排序、插入排序、快速排序、合并排序、希尔排序、堆排序等。
查找是一种在列表中确定目标所在位置的算法。基本的查找方法有顺序查找和折半查找。
迭代和递归是用于编写解决问题的算法的两种途径。
迭代就是反复替换的意思，它通过使用一个中间变量保存中间结果，不断反复计算求解最终值。递归是一个算法自我调用的过程，用递归调用的算法就是递归算法。
阶乘迭代算法伪代码,
Factorial
Input:Apositive integer num
1,FactN← 1
2,i← 1
3,While（ i < or = num）
3.1 FactN← FactN × i
3.2 Increment i
end while
Return FactN
end
阶乘递归算法伪代码,
Factorial
Input:A positive integer num
1,if（ num = 0）
then
1.1 Return 1
else
1.2 return num× Factorial(num-1)
end if
end
Java程序设计大学教程
5.2 数组
数组用于表示相同类型的元素的有序集合，
数组中每个元素都有一个唯一的索引。
根据数组的分配方式可将数组分为：一维数组和多维数组。 Java中还可以定义不规则数组。我们可以把一维以上的数组看作是,数组的数组,。
Java程序设计大学教程
5.2.1 数组的创建和使用
数组是一个被命名的连续存储区域的集合，存放着相同类型的数据项。数组的每个元素通过它在数组里的位置索引来引用。数组索引必须是一个整数值或者一个整数表达式。
在 Java里，大多数情况下数组被当成对象来对待。它们是用 new操作符来实例化的，有自己的实例变量（例如 length，可返回数组中第一维的元素数量）。数组变量是引用类型的变量。
定义与创建一个数组的语法及例子。
定义与创建一个数组的语法：
数组类型名称 [] 数组变量名 ;//定义数组变量
(也可以写成：数组类型名称 数组变量名 [];//定义数组变量 )
数组变量名 = new 数组类型名称 [n];//创建长度为 n
的数组以上两步也可以合并写为：
数组类型名称 数组变量名 []= new 数组类型名称 [n];
或者：
数组类型名称 [] 数组变量名 = new 数组类型名称 [n];
定义与创建一个数组的示例：
Fruit[] fruits ; //定义 Fruit类型的数组变量 fruits
fruits = new Fruit[5]; //新建有 5个元素的数组 fruits
fruits[0] = new Fruit("香蕉 ",1000);//为数组元素赋值（引用对象）
fruits[1] = new Fruit("葡萄 ",2000);
fruits[2] = new Fruit("菠萝 ",2000);
fruits[3] = new Fruit("草莓 ",1000);
fruits[4] = new Fruit("橘子 ",1000);
int n = fruits.length; //测试数组长度
Java程序设计大学教程用不规则数组实现
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
用 2维数组实现 每日股指显示
0 1 2 3 4 5
1 1133 1995 1500 1655 1033
2 1605 1981 1143 1226 1265
3 1226 1015 1648 1411 1007
4 1754 1472 1680 1793 1065
5 1469 1707 1745 1477 1742
...,..
52 1578 1550 1309 1139 1357
5.2.1 多维数组和不规则数组
根据数组的分配方式可将数组分为：一维数组和多维数组。 Java中还可以定义不规则数组。
我们可以把一维以上的数组看作是,数组的数组,。
模拟每日股指的程序 Stock
1,public class Stock {
2,public Stock() {
3,for (int week=1;week<=52;week++){
4,stockValue[week][0]=week;
5,for (int weekday=1;weekday<=5;weekday++){
6,stockValue[0][weekday]=weekday;
7,int stockIndex = (int)(Math.random()*1000+1000);
8,stockValue[week][weekday] = stockIndex;
9,}
10,}
11,}
12.
13,public void printStock(){
14,for (int week=0;week<=52;week++){
15,for (int weekday=0;weekday<=5;weekday++){
16,System.out.print(stockValue[week][weekday]+"\t");
17,}
18,System.out.println();
19,}
20,}
21.
22,public static void main(String[] args) {
23,Stock s=new Stock();
24,s.printStock();//打印股指年表
25,}
26.
27,int stockValue[][]= new int[53][6];
28.}
不规则数组演示程序 ArrTest
public cla s ArrTest {
public ArrTest() {
for (int n=1;n<myArr.length;n++){
myArr[n] = new int[n+1];//创建数组的数组，每个数组的长度不一样。
for (int m=1; m<myArr[n].length; m++){
myArr[n][m]=m;
}
}
}
public void printArr(){
for (int n=1; n<myArr.length; n++){
for (int m 1 m<myArr[n].length;m++){
System.out.print(myArr[n][m]+"\t");
}
System.out.println();
}
}
public static void main(String[] args) {
ArrTes arr=new ArrTest();
arr.printArr();
}
int myArr[][]= new int[Max+1][];//定义不规则数组，先创建数组的第 1维。
static int Max=6;
}
Java程序设计大学教程
5.2.3 排序
冒泡法的基本思想是，将待排序的元素看作是竖着排列的,气泡,,较小的元素比较轻，从而要往上浮；较大的元素比较重，从而要往下沉。一个含有 n个元素的列表，冒泡排序需要 n-1次扫描来完成数据排序。
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一轮排序将待排序的数组元素分割成独立的两部分，其中一部分元素的关键字均比另一部分元素的关键字小，则分别可对这两部分元素继续进行排序，以达到整个数组序列有序。
冒泡排序比较和交换的过程演示
2 3 5 8 7 6 9 10 49 25
2 5 3 8 7 6 9 10 49 25
492 3 5 7 6 8 9 10 25
第 2次比较第 3次比较第一轮的最后一次比较比较交换比较比较交换
......
2 5 3 8 7 6 9 10 49 25第 1次比较比较不交换不交换
Java程序设计大学教程
5.2.4 查找
顺序查找就是将要查找的数据的关键字按一定的顺序挨个与列表中的数据进行比较，相等时就找到了所要的数据。
对有序的列表可以使用更有效率的折半查找。折半查找是从一个列表的中间的元素来测试的，这将能够判别出目标在列表里的前半部还是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。换句话说，
可以通过判断排除一半的列表。重复这个过程直到找到目标或是目标不在这个列表里。
顺序查找和折半查找示例程序：
public class Search {
//顺序查找
public int sequentialSearch(int arr[],int key) {
for (int k = 0; k < arr.length; k++)
if (arr[k] == key)
return k; // 成功,返回该数组元素的位置（即索引）
return -1; // 失败,返回 -1
}
//折半查找
public int binarySearch(int arr[],int key) {
int low = 0; // 初始化
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2; // 取折半值
if (arr[mid] == key)
return mid; // 成功,返回该数组元素的位置（即索引）
else if (arr[mid] < key)
low = mid + 1; // 定位查找上半段
else
high = mid - 1; // 定位查找下半段
}
return -1; // 失败,返回 -1
}
}
Java程序设计大学教程
5.3 对象容器
使用数组管理对象虽然有较高的计算效率，但是数组要求固定对象的数量，操作起来并不方便。特别当对象数量不明确的情况下，我们需要更复杂的方法来管理对象。
Java类库中提供了一些用于管理对象集的类，称之为容器类（ container classes）。它们可以在程序中用作对象的容器，持有和操作对象而不用担心容量的变化。
Java容器的缺点是：一旦把对象放进容器，便失去了该对象的类型信息。容器中对象集的元素都是最基本的 Object
类型，也就是说，无论是何种类型的对象，进入容器后都向上转型为 Object。因此，当我们从容器中取出对象时，
可能无法知道它原来的类型。如果知道或者可以通过某种算法来判定出原来的类型，则可以将其转型为最初的实际类型。
Java程序设计大学教程
5.3.1 Java容器框架
列表（ list） 按照一定次序排列的对象集，对象之间有次序关系。
集合（ set） 无次序的对象集，但这些对象都是唯一的，不会重复。
映射（ map） 一群成对的对象集，这些对象各自保持着,键 -值,（ key-
value）对应关系。其中，作为,键,的那些对象一定是一个 set，即这些对象是唯一的，不会重复。
a d a c
a
b
c
d
e
a
b
c
v23
b
0 1 2 … n4
v41
v23
v17
d
list
map
set
Java程序设计大学教程
5.3.2 Collection与 Iterator
Collection是 Java容器框架中的高层接口，它声明了所有容器类的核心方法，包括添加、清除、比较和持有对象
（也称为对象集的元素）的操作。此外,Collection接口还提供了一个方法用于返回 Iterator。
迭代器是一个实现了 Iterator或 ListIterator接口的对象。
它是一种,轻量级,的对象，消耗较小的资源，具有较高的效率，能够满足对象集的遍历。
Java程序设计大学教程
5.3.3 List及 ListIterator
编程中最常用到的是 List容器。 List容器的重要属性是对象按次序排列。 List通常由 ArrayList和 LinkList来实现，它提供了列表的插入、删除、定位、截取、遍历等操作。
ArrayList 以可变数组实现完成的 List容器。允许快速随机访问，
但是当元素的插入或移除发生于 List中央位置时，效率便很差。
对于 ArrayList，建议使用 ListIterator来进行向后或向前遍历，
但而不宜用其来进行元素的插入和删除，因为所花代价远高于
LinkedList。
LinkedList 以双向链表（ double-linked 1ist）实现完成的
List容器。最佳适合遍历，但不适合快速随机访问。插入和删除元素效率较高。它还提供 addFirst,addLast,getFirst、
getLast,removeFirst,removeLast等丰富的方法，可用于实现栈和队列的操作。
Java程序设计大学教程
5.4 抽象数据类型
抽象数据类型（ ADT）是把与对该数据类型有意义的操作封装在一起的数据声明。它将数据和操作封装起来，
用户可通过操作接口对数据进行操作。
常用的抽象数据类型有链表、栈、对列等。
Java程序设计大学教程
5.4.1 链表
链表是一组互相链接的元素序列，分为：单链表、循环链表、双向链表等。若在这个序列中每个元素总是与它前面的元素相链接
（除第一个元素外），则形成单链表。单链表关系的实现可以通过指针来描述。
在 Java类库中,LinkedList可以当作链表使用，它能实现链表常用的操作，包括：增加、删除、定位、遍历等，这足够解决一切关于有序列表的问题。使用 LinkedList链表还能实现栈和队列。
1000 A
1200
B
1312
C
1423
head 1000 1200 1312
D
1423
空指针指针节点
h r
非空循环链表
rh
空表链表示意图
Java程序设计大学教程
5.4.2 栈
栈是限定仅在一端进行插入或删除操作的线性表。栈又称为后进先出（ LIFO）线性表，其主要操作为进栈（ push）和出栈
（ pop）。栈的应用非常广泛，如：倒转数据、回溯等。
栈栈顶栈栈顶数据栈栈顶栈栈顶数据入栈操作出栈操作
Java程序设计大学教程
5.4.3队列
队列是线性列表的一种特殊情况，其所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。队列的结构特点是先进队列的元素先出队列。队列又称为先进先出（ FIFO）
线性表，其主要操作为入列（ enqueue）和出列（ dequeue）。
对列主要应用于排队处理用户请求、任务和指令。在计算机系统中，需要用队列来完成对作业或对系统设备如打印池的处理。
a1 a2 a3 an
队尾队头入列出列
