Java基础知识--对象数组及二维数组.ppt

第2章 对象数组及二维数组,课程回顾： OO：属性+行为 特性：封装+继承+多态,第2章 对象数组及二维数组,Java基础知识 变量、数据类型、判定语句、循环语句,第2章 对象数组及二维数组,用数组存储对象 对数组元素进行排序 在已排序的数组中查找 二维数组,数组元素可以是任何类型（只要所有元素具有相同的类型） 数组元素可以是基本数据类型 数组元素也可以是类对象，称这样的数组为对象数组。在这种情况下，数组的每一个元素都是一个对象的引用。,用数组存储对象,例如， BankAccount accounts; 或 BankAccount accounts ; 定义了一个存储BankAccount类对象的数组。 与C、C+不同，Java在数组的定义中并不为数组元素分配内存，因此 中不需指明数组中元素的个数，即数组长度，而且对于如上定义的数组是不能引用的，必须经过初始化才可以引用。,用数组存储对象,对象数组的初始化 分为静态初始化和动态初始化 静态初始化：在定义数组的同时对数组元素进行初始化， 例如： BankAccount accounts = new BankAccount(“Zhang“, 100.00), new BankAccount(“Li“, 2380.00), new BankAccount(“Wang“, 500.00), new BankAccount(“Liu“, 175.56), new BankAccount(“Ma“, 924.02) ;,用数组存储对象,动态初始化：使用运算符new为数组分配空间，对于基本类型的数组，其格式如下： type arrayName =new typearraySize; type arrayName=new typearraySize; 对于对象数组，使用运算符new只是为数组本身分配空间，并没有对数组的元素进行初始化。即数组元素都为空，如图。,数组元素未初始化的对象数组,用数组存储对象,此时不能访问数组的任何元素，必须对数组元素进行初始化后，才能访问。因此，对于对象数组，需要经过两步空间分配。首先给数组分配空间： type arrayName =new typearraySize; 然后给每一个数组元素分配空间： arrayName0=new type(paramList); arrayNamearraySize-1=new type(paramList);,用数组存储对象,例如： /定义一个String类型的数组 String stringArrar; /给数组stringArray分配3个引用空间，每个引用值为null。 stringArray = new String3; /下面给数组元素分配空间 stringArray0=new String(“how”); stringArray1=new String(“are”); stringArray2=new String(“you”);,用数组存储对象,当给数组元素分配了内存空间后，就可以引用了。数组元素的引用方式为： arrayNameindex index为数组下标，下标从0开始，一直到数组长度减1。下标可以是整型常数或表达式。 Java对数组元素要进行越界检查以保证安全性。同时，对于每个数组都有一个属性length指明它的长度（这里即是数组元素的个数）。例如，stringArray.length指明数组stringArray的长度。,用数组存储对象,对象数组应用举例,使用数组对一个班的学生信息及考试成绩进行存储，学生信息包括学号、姓名、三门课（英语、数学、计算机）的成绩及总成绩。,用数组存储对象,首先定义学生类Student： 属性包括：学号（id），姓名（name），英语成绩（eng），数学成绩（math），计算机成绩（comp），总成绩（sum）。 方法包括：构造方法，get方法，set方法，toString方法，equals方法，compare方法（比较两个学生的总成绩, 结果分大于，小于，等于），sum方法（计算总成绩）。 为了能够将Student类对象直接存储，应使其加入串行化协议。代码如下：,用数组存储对象,/Student.java import java.io.*; public class Student implements Serializable private String id; /学号 private String name; /姓名 private int eng; /英语成绩 private int math; /数学成绩 private int comp; /计算机成绩 private int sum; /总成绩,用数组存储对象,/构造方法 public Student(String id,String name,int eng,int math,int comp) this.id=id; =name; this.eng=eng; this.math=math; p=comp; sum(); /计算总成绩 ,用数组存储对象,/构造方法 public Student(Student s) this.id=s.id; =new String(); this.eng=s.eng; this.math=s.math; p=p; sum(); /计算总成绩 ,用数组存储对象,/set方法 public void setId(String id) this.id=id; public void setName(String name) =name; public void setEng(int eng) this.eng=eng; sum(); /计算总成绩 ,用数组存储对象,/set方法 public void setMath(int math) this.math=math; sum(); /计算总成绩 public void setComp(int comp) p=comp; sum(); /计算总成绩 ,用数组存储对象,/get方法 public String getId() return id; public String getName() return name; public int getEng() return eng; public int getMath() return math; ,public int getComp() return comp; public int getSum() return sum; ,用数组存储对象,/计算总成绩 void sum() this.sum=eng+math+comp; /toString方法 public String toString() return getId() + “t“+getName() + “t“+getEng() + “t“+getMath() + “t“+getComp() + “t“+getSum(); ,用数组存储对象,/比较两个Student对象的值是否相等 public boolean equals(Object x) if (this.getClass() != x.getClass() return false; Student b = (Student) x; return (this.getId().equals(b.getId(); ,用数组存储对象,/比较成绩大小,当前对象成绩比参数对象成绩大时返回1, /相等时返回0,其它返回-1. public int compare(Student A) if(this.getSum()A.getSum() return 1; else if(this.getSum()=A.getSum() return 0; else return -1; ,用数组存储对象,下面定义班级类StudentClass： 属性包括：班级名称（name），容量（capacity），学生（students），实际人数（size）。 方法包括：构造方法，get方法，set方法， toString方法。,用数组存储对象,/StudentClass.java /定义学生班级类StudentClass public class StudentClass private String name; /班级名称 static int capacity = 40; /最大容量 private Student students; /学生 private int size; /实际人数,用数组存储对象,/构造方法 public StudentClass(String name, int size) = name; this.size = size; students = new Studentcapacity; ,用数组存储对象,/get方法 public String getName() return name; public int getCapacity() return capacity; public Student getStudents() return students; public int getSize() return size;,用数组存储对象,/set方法 public void setName(String name) = name; public void setCapacity(int capacity) this.capacity = capacity; public void setSize(int size) this.size = size; public void setStudents(Student students) for (int i = 0; isize; i+) this.studentsi = new Student(studentsi); ,用数组存储对象,/toString方法 public String toString() String s; s = “ 班级:“ + name +“t“ + “容量:“ + capacity + “t“ + “实际人数:“ + size +“nn“; s = s + “学号“+“t“ + “姓名“+“t“ + “英语“+“t“ + “数学“+“t“ + “计算机“+“t“ + “总成绩n“; for (int i=0; isize; i+) s = s + studentsi.getId()+“t“+studentsi.getName()+“t “ +studentsi.getEng()+“t“+studentsi.getMath()+“t“ +studentsi.getComp()+“t“+studentsi.getSum()+“n“; return s; ,用数组存储对象,定义测试类Tester1：为测试简单，仅生成具有5名学生的班级，5名学生的信息从键盘输入，为了避免以后再重复输入，可将输入的学生信息保存到文件中。,用数组存储对象,import java.io.*; public class Tester1 public static void main(String args) Student students; StudentClass aClass = new StudentClass(“软件06“,5); students=new Student5; for (int i=0; i5; i+) studentsi = new Student(getAStudent(i+1); aClass.setStudents(students); System.out.println(aClass);,用数组存储对象,/将学生信息保存到文件stu.ser中。 try FileOutputStream fo = new FileOutputStream(“stu.ser“); ObjectOutputStream so = new ObjectOutputStream(fo); for (int i=0; i5; i+) so.writeObject(studentsi); so.close(); catch(Exception e) System.out.println(e) ; ,用数组存储对象,/从键盘输入一个学生的信息 public static Student getAStudent(int i) Student studenti; System.out.println(“输入第“ + i + “个学生的信息:“); System.out.print(“学号:“); String id = Keyboard.getString(); System.out.print(“姓名:“); String name = Keyboard.getString(); System.out.print(“英语成绩:“); int eng = Keyboard.getInteger(); System.out.print(“数学成绩:“); int math = Keyboard.getInteger(); System.out.print(“计算机成绩:“); int comp = Keyboard.getInteger(); studenti = new Student(id,name,eng,math,comp); return studenti; ,用数组存储对象,运行结果如下： 输入第1个学生的信息: 学号:250201 姓名:李红 英语成绩:88 数学成绩:76 计算机成绩:60 输入第2个学生的信息: 班级:软件06 容量:40 实际人数:5 学号 姓名 英语 数学 计算机 总成绩 250201 李红 88 76 60 224 250202 张林 78 67 80 225 250203 董玉梅 86 80 75 241 250204 张力 70 68 75 213 250205 何为 80 90 78 248 Press any key to continue.,用数组存储对象,在班级类StudentClass中增加常用方法： 如查找某个学生是否存在（find），增加一个学生（add），删除一个学生（del）等。,用数组存储对象,(1) 查找 已知学生的学号，查找此学生是否存在。如果存在，返回其在数组中的下标位置；如果不存在，返回-1。 顺序查找方法的代码如下： /顺序查找 public int find(String id) for (int i = 0; i size; i+) if (studentsi.getId().equals(id) return i; return -1; ,用数组存储对象,(2) 增加 下面的方法是在数组的末尾增加一个学生对象。 /增加一个学生 public boolean add(Student aStudent) if (size = capacity) return false; /没有空间,不能增加 if (find(aStudent.getId()=0) return false; /此学号已存在,不能增加 /增加操作 this.studentssize = new Student( new String(aStudent.getId(), new String(aStudent.getName(), aStudent.getEng(),aStudent.getMath(),aStudent.getComp(); size+; return true; ,用数组存储对象,(3) 删除 已知一个Student对象，将此对象从数组中删除。 /删除一个学生 public boolean del(Student aStudent) int pos = find(aStudent.getId(); if (pos=-1) return false; /此学号不存在,不能删除 /将此学生从数组中删除. /将数组元素studentspos+1studentssize-1依次向前移动一个位置,且size的值减1. for (int i = pos+1; isize; i+) studentsi-1 = studentsi; size-; return true; ,用数组存储对象,/已知学号,删除一个学生 public boolean del(String id) int pos = find(id); if (pos=-1) return false; /此学号不存在,不能删除 /将此学生从数组中删除. /将数组元素studentspos+1studentssize-1依次向前移动一个位置,且size的值减1. for (int i = pos+1; isize; i+) studentsi-1 = studentsi; size-; return true; ,用数组存储对象,编写测试类Tester2：对新增加的查找、增加及删除方法进行测试。,用数组存储对象,/Tester2.java import java.io.*; public class Tester2 public static void main(String args) Student students=new Student5; /从文件stu.ser中读出学生信息。 try FileInputStream fi = new FileInputStream(“stu.ser“); ObjectInputStream si = new ObjectInputStream(fi); for (int i=0; i5; i+) studentsi = (Student)si.readObject(); si.close(); ,用数组存储对象,catch(Exception e) System.out.println(e); StudentClass aClass = new StudentClass(“软件04“,5); aClass.setStudents(students); System.out.println(aClass); / 查找,增加,删除测试 for (int i=0;i2; i+) System.out.print(“输入查找的学号“); String id = Keyboard.getString(); if (aClass.find(id)0) System.out.println(“不存在!“); else System.out.println(“存在!“); ,用数组存储对象,for (int i=0;i2; i+) Student aStudent = getAStudent(6+i); if (aClass.add(aStudent) System.out.println(“增加成功!“); else System.out.println(“不能增加!“); for (int i=0;i2; i+) System.out.print(“输入要删除的学号“); String id = Keyboard.getString(); if (aClass.del(id) System.out.println(“已删除!“); else System.out.println(“不存在!”); System.out.println(aClass); ,用数组存储对象,按照预先规定的准则（如升序或降序等），把数据有次序地排列起来的操作称为“排序”或“分类”（Sorting）。 目前已经设计出许多排序算法，常用的排序算法有选择排序、插入排序及交换排序等。,对数组元素进行排序,(1) 选择排序 选择排序的基本思想是先在未排序序列中选一个最小元素，作为已排序子序列，然后再重复地从未排序子序列中选取一个最小元素，把它加到已经排序的序列中，作为已排序子序列的最后一个元素，直到把未排序子序列中的元素处理完为止。,对数组元素进行排序,例 用选择排序方法将例1中生成的文件stu.ser中的班级学生按总成绩从高到低排序。 在前例中的StudentClass类中增加选择排序方法selectionSort： /用选择排序方法将总成绩按从高到低排序 public void selectionSort() Student temp; for (int i=0; i0) temp = studentsi; studentsi = studentsj; studentsj = temp; ,对数组元素进行排序,/SortTester.java 测试排序方法 import java.io.*; public class SortTester public static void main(String args) Student students=new Student5; /从文件stu.ser中读出学生信息。 try FileInputStream fi = new FileInputStream(“stu.ser“); ObjectInputStream si = new ObjectInputStream(fi); for (int i=0; i5; i+) studentsi = (Student)si.readObject(); si.close(); catch(Exception e) System.out.println(e); ,对数组元素进行排序,StudentClass aClass = new StudentClass(“软件06“,5); aClass.setStudents(students); System.out.println(aClass); / 选择排序 aClass.selectionSort(); System.out.println(“选择排序后的结果:n“); System.out.println(aClass); 运行结果如下：,对数组元素进行排序,班级:软件0201 容量:40 实际人数:5 学号 姓名 英语 数学 计算机 总成绩 250201 李红 88 76 60 224 250202 张林 78 67 80 225 250203 董玉梅 86 80 75 241 250204 张力 70 68 75 213 250205 何为 80 90 78 248 选择排序后的结果: 班级:软件0201 容量:40 实际人数:5 学号 姓名 英语 数学 计算机 总成绩 250205 何为 80 90 78 248 250203 董玉梅 86 80 75 241 250202 张林 78 67 80 225 250201 李红 88 76 60 224 250204 张力 70 68 75 213 Press any key to continue.,对数组元素进行排序,(2) 插入排序 先以未排序数列的第一个元素作为已排序子数列，然后从原来的第二个元素起，将各元素逐一插入到已排序子数列中合适的位置，直到把全部元素都插入为止。,对数组元素进行排序,(2) 插入排序 假设数组a中有n个元素a0、a1、an-1，则可以按照某种属性对其进行排序。 按照直接插入法，首先要把a0作为已排序子数列。然后逐一将a1、a2、an-1插入到已排序子数列中。每插入一个元素ai都要执行如下两步操作：,对数组元素进行排序,(2) 插入排序 第一步，在已排序子数列中找一个合适位置j，使ajai，并且aiaj+1。 第二步，将ai插入到aj之后。将aj+1、依次向后移一位（后移操作也可在第一步的查找过程中进行）。,对数组元素进行排序,例3 直接插入排序举例。 根据上面的算法，在StudentClass中增加直接插入排序方法insertSort，代码如下： /直接插入排序方法 public void insertSort() Student temp; for (int i=1; i-1 ,对数组元素进行排序,顺序查找的算法简单，但在大数据量中进行查找时效率较低。 在未排序的数组中进行查找，只能使用顺序查找方法。对于已排序的数组，也可以使用顺序查找方法，但可以对算法进行一定的改进，使其效率有所提高。,在已排序的数组中查找,例如，有一批Integer类型的数据已按升序排列好。 a1a2an 这批数据存储在数组a0、a1、an-1中，现在要对该数组进行查找，看给定的数据x是否在此数组中。 由于数组中的元素已按升序排列，因此，在查找时，x不需要与数组中的每个元素都进行比较。假如按从左向右的顺序查找，当x小于ai时就应该停止查找。改进的顺序查找方法如下：,在已排序的数组中查找,public int seqSearch(int x) for (int i = 0; (i = Value(); i+) if (Value() = x) return i; return -1; ,在已排序的数组中查找,对于已排序的数组，还可以使用效率更高的查找方法，比较典型的方法有二分查找。同样是上面的问题，可以用下面的方法： 在0到n-1中间选一个正整数k，用k把原来的有序数列分为三个有序子序列： I1: a0，a1，ak-1 I2: ak I3: ak+1，ak+2，an-1,在已排序的数组中查找,然后，用ak与x比较，若x等于ak，查找结束；若x小于ak，则用同样的方法把序列a0，a1，ak-1分成三个序列； 若xak，也用同样的方法把序列ak+1，ak+2，an-1分成三个序列， 这样每分一次，要查找的范围就缩小一半。这个过程进行下去，直到找到x，或查找的范围内已没有数据(这种情况说明x不存在)。 这是一种应用分治策略的解题思想。当k=1/2 时，称为二分查找法，或二分检索法。,在已排序的数组中查找,例 二分查找举例。 下面定义具有排序数组的类SortedIntArray。其中，search方法运用二分查找算法在给定的数组范围内查找某一元素，如果存在，返回元素所在的下标位置，如果不存在，则返回元素应该在的位置。 将此功能与插入功能相结合，又可实现对数组元素进行排序。,在已排序的数组中查找,public class SortedIntArray private int capacity; private Integer rep; private int size; / size 的缺省值为 0 /构造方法 public SortedIntArray(int n) capacity = n; rep = new Integercapacity; /无参的构造方法 public SortedIntArray( ) this(100); ,在已排序的数组中查找,/下面的方法运用二分查找算法在下标从lower到upper范围内的数组 /元素中查找第一个不小于新元素的数组元素的下标。 private int search(int i, int lower, int upper) int index = lower; if (upper = lower) int middle = (upper + lower) / 2; int current = Value( ); if (current = i) index = middle; else if (current i) index = search(i, middle + 1, upper); else index = search(i, lower, middle - 1); return index; ,在已排序的数组中查找,public int search(int i) return search(i, 0, size - 1); /在数组中插入一个元素。 public SortedIntArray insert(int i) int index = search(i); for(int j = size; j index; -j) repj = repj - 1; repindex = new Integer(i); +size; return this; ,在已排序的数组中查找,/在数组中删除一个元素。只删除查到的第一个元素。 public SortedIntArray remove(int i) int index = search(i); if (Value( ) = i) -size; for (int j = index; j size; +j) repj = repj + 1; return this; public String toString( ) String toReturn = “; for (int i = 0; i size; +i) toReturn += repi.toString( ) + “, “; return toReturn; ,在已排序的数组中查找,/ 主方法 static public void main(String args) SortedIntArray anArray = new SortedIntArray( ); anArray.insert(4).insert(9).insert(7).insert(1).insert(3).insert(2).insert(8).insert(7); System.out.println(anArray); anArray.remove(1).remove(8).remove(7).remove(3); System.out.println(anArray); 运行结果如下：,1, 2, 3, 4, 7, 7, 8, 9, 2, 4, 7, 9, Press any key to continue.,在已排序的数组中查找,数组元素的类型除了可以是基本数据类型、类对象外，还可以是数组。前面介绍的数组也称为一维数组，如果一维数组的元素又是一维数组，则称此数组为二维数组。二维数组常用来表示二维表，即以行(ro