4[1].1Java数组.doc

4.1 Java数组一、 一维数组1.基本概念：（1）数组：数组是有序数据的集合。（2）数组元素：数组名和下标来唯一地确定数组中的元素。（数组元素的下标从0开始）（3）数组长度：数组对象所包含的元素个数。2一维数组的声明在Java中，一维数组的定义形式为：数组元素类型 数组名 ；或 数组元素类型 数组名；例如 char c;Char c;也可以在一条语句中声明多个数组变量：（一般不提倡使用）Char a,b,c;Char a,b,c;但 char a,b,c;中a是数组变量，而b和c不是。3. Java中数组对象的创建（两种形式）（1）使用关键字new创建数组对象，格式为：数组名 = new 数组元素的类型 数组元素的个数；例如：publicclassTestNew publicstaticvoidmain(Stringargs) int s; inti; s=newint5; for(i=0;i=0;i-) System.out.println( +si); （2）数组的初始化语句创建数组对象数组元素的数据类型 变量名=数组元素1，数组元素2，,数组元素n;或：数组元素的数据类型 变量名 =数组元素1，数组元素2，,数组元素n;例如：char c=a，b，c，d，e初始化：1）静态初始化：在定义数组的同时就为数组元素分配空间并赋值； 2）动态初始化：数组定义与为数组分配空间和赋值的操作分开进行；3）默认初始化：数组是引用类型，它的元素相当于类的成员变量，因此数组分配空间后，每个元素也被按照成员变量的规则被隐式初始化。数组元素的数据类型是引用型（即类、接口或数组类型）时，数组名下标的值是引用。在没有给它赋值前，其默认的值为null。因此还需要通过new运算符及赋值语句给它们分别赋值。例如：String s=new String3;S0=new String(“abc”);S1=new String(“def”);S2=new String(“gh”);上面的四条语句还可以简化成一个数组的初始化语句：String s=new String(“abc”), new String(“def”), new String(“gh”);/变量s是一个数组对象的引用，执行初始化以后，该数组的三个元素分别指向三个不同的字符串对象。程序举例：public class TestDpublic static void main(String args) int a ; a = new int3 ; a0 = 0 ; a1 = 1 ; a2 = 2 ; for(int i=0;i3;i+) System.out.print( +ai); System.out.println(); Date days ; days = new Date3 ; days0 = new Date(2008,4,5) ; days1 = new Date(2008,2,31) ; days2 = new Date(2008,4,4) ; for(int i=0;i3;i+) System.out.print(daysi.year); System.out.print(.+daysi.month); System.out.print(.+daysi.day); System.out.println(); class Date int year,month,day ; Date(int year ,int month ,int day) this.year = year ; this.month = month ; this.day = day ; 程序输出：0 1 22008.4.52008.2.312008.4.4静态初始化举例：publicclassTestS publicstaticvoidmain(Stringargs) inta=0,1,2; Timetimes=newTime(19,42,42),newTime(1,23,54),newTime(5,3,2); classTime inthour,min,sec; Time(inthour,intmin,intsec) this.hour=hour; this.min=min; this.sec=sec; 4一维数组元素的引用 只有完成了对所有数组元素的创建和初始化工作之后，才可以在程序中引用数组元素、修改其属性和调用其方法。 Java中数组元素的引用是通过数组下标来实现的，其引用方式为： 数组名数组下标 其中数组下标可以为整型常数或表达式，下标从0开始，到数组元素个数值减1为止。每个数组都有一个属性length来指明它的长度，即数组元素的个数。例：/一维数组定义与输出class shuzupublic static void main(String args) int stu=new int1,2,3;/方法一/int stu=1,2,3; 方法二/int stu=new int1,2,3; 方法三/int stu=1,2,3; 方法四for(int i=0;istu.length;i+)System.out.println(stui);例2：数组排序输出public class BubbleSortpublic static void main(String args)int a=27,6,4,8,10,12,89,68,45,37;System.out.println(排序前的数据序列：);printArray(a);System.out.println(排序的各趟结果：);sortBubble(a);printArray(a);/数组排序的方法public static void sortBubble(int a) int hold;for(int pass=1;passa.length;pass+) for(int i=0;iai+1) hold=ai; ai=ai+1; ai+1=hold; printArray(a); /打印数组的方法 public static void printArray(int b)for(int i=0;ib.length;i+)System.out.print( +bi);System.out.println();AVA中运用数组的几种排序算法JAVA中在运用数组进行排序功能时，一般有四种方法：快速排序法、冒泡法、选择排序法、插入排序法。排序算法即解决以下问题的算法： 输入：n个数的序列。 输出：原序列的一个重排；使得a1*=a2*=a3*=.=an*。1.选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 基本思想n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 初始状态：无序区为R1.n，有序区为空。 第1趟排序 在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R(i.n）。该趟排序从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第1个记录R交换，使R1.i和Ri+1.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。例如：初始关键字 49 38 65 97 76 13 27 49 第一趟排序后 13 38 65 97 76 49 27 49 第二趟排序后 13 27 65 97 76 49 38 49 第三趟排序后 13 27 38 97 76 49 65 49 第四趟排序后 13 27 38 49 76 97 65 49 第五趟排序后 13 27 38 49 49 97 65 76 第六趟排序后 13 27 38 49 49 65 97 76 第七趟排序后 13 27 38 49 49 65 76 97 最后排序结果 13 27 38 49 49 65 76 97public class selectsort public static void main(String args) int arr=2,345,111,1,34,5; int temp=0; int min=0; for(int i=0;iarr.length;i+) min=i; for(int j=i+1;jarrj) min=j; temp=arrmin; arrmin=arri; arri=temp; System.out.println(排序后的数组为:); for (int i=0;iarr.length;i+) System.out.print(arri+ ); 2. 冒泡排序（BubbleSort）基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。用二重循环实现，外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，.，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和aj+1标识，i的值依次为1,2,.,9，对于每一个i,j的值依次为1,2,.10-i。程序：public class maopaosort public static void main(String args) int arr=2,345,111,1,34,5; int temp=0; for(int i=0;iarr.length-1;i+) for(int j=0;jarrj+1) temp=arrj; arrj=arrj+1; arrj+1=temp; System.out.println(排序后的数组为:); for (int k=0;karr.length;k+) System.out.print(arrk+ );3. 插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。基本思想:将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例： a1，a2，a3，a4，an a1，a2，a3，a4 ，an a1(n-1），a2(n-1) ，,an(n-1) 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到下一位置中 重复步骤2public class InsertSort public static int a=5,8,11,6,77,33,13,99,24,37; public static void main(String args) int i; / 循环计数变量 int Index = a.length;/ 数据索引变量 System.out.print(排序前: ); for (i = 0; i Index ; i+) System.out.print( + ai + ); System.out.println(); InsertSort(a); / 选择排序 / 排序后结果 System.out.print(排序后: ); for (i = 0; i Index ; i+) System.out.print( + ai + ); System.out.println(); public static void InsertSort(int b) int i, j, k; / 循环计数变量 int InsertNode; / 欲插入数据变量 for (i = 1; i = 0 & InsertNode aj) aj + 1 = aj; j-; aj + 1 = InsertNode; / 将数值插入 / 打印目前排序结果 System.out.print(排序中: ); for (k = 0; k a.length; k+) System.out.print( + ak + ); System.out.println(); 4.快速排序基本思想： 设当前待排序的无序区为Rlow.high，利用分治法可将快速排序的基本思想描述为：分解： 在Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.pivotpos-1)和Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。 注意： 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=Rpivotpos)： Rlow.pivotpos-1.keysRpivotpos.keyRpivotpos+1.high.keys其中lowpivotposhigh。求解： 通过递归调用快速排序对左、右子区间Rlow.pivotpos-1和Rpivotpos+1.high快速排序。组合： 因为当求解步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，组合步骤无须做什么，可看作是空操作。快速排序算法QuickSortvoid QuickSort(SeqList R，int low，int high) /对Rlow.high快速排序 int pivotpos； /划分后的基准记录的位置 if(lowhigh)/仅当区间长度大于1时才须排序 pivotpos=Partition(R，low，high)； /对Rlow.high做划分 QuickSort(R，low，pivotpos-1)； /对左区间递归排序 QuickSort(R，pivotpos+1，high)； /对右区间递归排序 /QuickSortJava快速排序代码：public class Qsort public static void main(String args) / TODO 自动生成方法存根 quicksort qs = new quicksort(); int data = 44,22,2,32,54,22,88,77,99,11; qs.data = data; qs.sort(0, qs.data.length-1); qs.display(); class quicksort public int data; private int partition(int sortArray,int low,int hight)/找出分界点 int key = sortArraylow; while(lowhight) while(low=key) hight-; sortArraylow = sortArrayhight; while(lowhight & sortArraylow=key) low+; sortArrayhight = sortArraylow; sortArraylow = key; return low; public void sort(int low,int hight) if(lowhight) int result = partition(data,low,hight); sort(low,result-1); sort(result+1,hight); public void display() for(int i=0;idata.length;i+) System.out.print(datai); System.out.print( ); 二、二维数组1二维数组的定义在Java中，二维数组的定义形式为： 数组元素类型 数组名 ； 数组元素类型 数组名；2二维数组的初始化 静态初始化： Java语言中，由于把二维数组看作是数组的数组，数组空间不是连续分配的，所以不要求二维数组每一维的大小相同。例如： int intArray =1,2,2,3,3,4,5;3二维数组元素的引用 与一维数组相同，二维数组元素可以通过指定数组元素下标的方式进行引用。 对二维数组中的每个元素，引用方式为：数组名index1index2。 需要注意的是：在数组的每一维中，数组元素的编号均从0开始，到该维的数组元素个数减1结束。/二维数组定义与输出class erwshzupublic static void main(String args)/int num=new int1,2,3,4,5,6; 方法一int num=1,2,3,4,5,6;/方法二for (int i=0;inum.length ;i+ )for (int j=0;jnumi.length ;j+ )System.out.print(numij+ );System.out.println();三、多维数组（难点）1.多维数组变量的声明格式（1）数组元素数据类型 变量名；（2）数组元素数据类型 变量名 ；“”的个数均为数组的维数。2创建数组对象的三种形式：（1）直接创建多维数组New 数组元素的数据类型 第n维元素个数第(n-1)维元素个数第1维元素个数; 例如 int matrix;Matrix=new int 22；/数组matrix的元素是2，并且数组matrix的每一个元素都是包含2个元素的一维数组。（2）从高维开始逐维创建数组对象例如 int matrix3d;Matrix3d=new int 3;Matrix3d0=new int 2;Matrix3d1=new int 3;Matrix3d2=new int 2;Matrix3d00=new int 2;Matrix3d01=new int 3;Matrix3d10=new int 4;Matrix3d11=new int 5;Matrix3d12=new int 7;Matrix3d20=new int 2;Matrix3d21=new int 3;int matrix;Matrix=new int 22；上面的等价创建：Matrix=new2;Matrix0=new2;Matrix1=new2;(3)采用数组初始化语句创建数组对象数组元素的数据类型 变量名=数组元素1，数组元素2，.数组元素n;或 数组元素的数据类型变量名 =数组元素1，数组元素2，.数组元素n;例如：Int matrix=1,2,3,4;String matrixstring=new String(“abcd”), new String(“efg”), new String(“hi”), new String(“j”);3.多维数组的访问格式：数组名第n维元素下标 第（n-1）维元素下标第1维元素下标；综合举例：“和为15的棋盘游戏“（”1-9“数字不重复地填入3*3的方格，使行、列、两对角线的和均为15，得出游戏的所有解）（p129）public class grid15 int array=new int33; int count = 1; public void showgrid() int i,j; for(i=0;iarray.length;i+) for(j=0;jarrayi.length;j+) System.out.print(arrayij+ ); System.out.println(); System.out.println(); private boolean datacheck() if(array00+array01+array02!=15) return false; if(array10+array11+array12!=15) return false; if(array20+array21+array22!=15) return false; if(array00+array10+array20!=15) return false; if(array01+array11+array21!=15) return false; if(array02+array12+array22!=15) return false; if(array00+array11+array22!=15) return false; if(array02+array11+array20!=15) return false; return true; public void arrange() int sum=1; for(int i=1;i=9;i+) for(int j=1;j=9;j+) if(j=i)continue; for(int k=1;k=9;k+) if(k=i|k=j)continue; for(int l=1;l=9;l+) if(l=i|l=j|l=k)continue; for(int m=1;m=9;m+) if(m=i|m=j|m=k|m=l)continue; for(int n=1;n=9;n+) if(n=i|n=j|n=k|n=l|n=m)continue; for(int o=1;o=9;o+) if(o=i|o=j|o=k|o=l|o=m|o=n)continue; for(int p=1;p=9;p+) if(p=i|p=j|p=k|p=l|p=m|p=n|p=o)continue; for(int q=1;q=9;q+) if(q=i|q=j|q=k|q=l|q=m|q=n|q=o|q=p)continue; array00=i; array01=j; array02=k; array10=l; array11=m; array12=n; array20=o; array21=p; array22=q; if(datacheck() System.out.println(=+sum+=); sum+; showgrid(); public static void main(String args) grid15 t=new grid15(); t.arrange(); 数组小结： 1简单类型的数组2复合类型的数组例如：class s public static void main(String args) String stringArray = new String3;/*为数组中每个元素开辟引用空间(32位) */stringArray0= new String(How);/为第一个数组元素开辟空间stringArray1= new String(are);/为第二个数组元素开辟空间stringArray2= new String(you);/ 为第三个数组元素开辟空间 for(int i=0;istringArray.length;i+) System.out.println(stringArrayi); 3二维数组举例：【例】两个矩阵相乘publicclassMatrixMultiply publicstaticvoidmain(Stringargs) inti,j,k; inta=newint23;/动态初始化一个二维数组 intb=1,5,2,8,5,9,10,-3,2,7,-5,-18;/静态初始化 一个二维数组 intc=newint24;/动态初始化一个二维数组 for(i=0;i2;i+) for(j=0;j3;j+) aj=(i+1)*(j+2); for(i=0;i2;i+) for(j=0;j4;j+) cj=0; for(k=0;k3;k+) cj+=ak*bkj; System.out.println(*MatrixC*);/打印MatrixC标记 for(i=0;i2;i+) for(j=0;j2,6,5,1,3如:int arr = 3, 1, 5, 6, 2 ;for (int