Java程序設(shè)計(jì) 課件 【ch04】數(shù)組

數(shù)組Java程序設(shè)計(jì)第四章01一維數(shù)組一維數(shù)組必須先聲明后使用。聲明數(shù)組時(shí)，需要指明數(shù)組名稱和數(shù)組元素的數(shù)據(jù)類型。一維數(shù)組聲明的語法格式有以下兩種，建議使用第一種方式。方式一：數(shù)組元素類型[]數(shù)組名;例如：int[]a; double[]b;方式二：數(shù)組元素類型數(shù)組名[];例如：inta[]; doubleb[];1．一維數(shù)組的聲明4.1一維數(shù)組4.1.1一維數(shù)組的聲明與訪問4.1一維數(shù)組2．一維數(shù)組的創(chuàng)建聲明數(shù)組僅僅給出了數(shù)組的名稱和其中可存放數(shù)據(jù)的類型，而要真正使用數(shù)組來保存數(shù)據(jù)，還必須為該數(shù)組分配內(nèi)存空間，即創(chuàng)建數(shù)組。在創(chuàng)建數(shù)組時(shí)，必須指明數(shù)組的長度，即數(shù)組中可存儲的數(shù)據(jù)個(gè)數(shù)。Java語言中創(chuàng)建數(shù)組的語法格式為：數(shù)組名=new數(shù)組元素類型[數(shù)組長度]；例如，對于前面聲明的數(shù)組a和b，可以進(jìn)一步來創(chuàng)建：a=newint[20];b=newdouble[10];也可以將數(shù)組的定義和創(chuàng)建合二為一，例如：Int[]a=newint[20];Double[]b=newdouble[10];4.1一維數(shù)組3．一維數(shù)組的初始化在定義數(shù)組的同時(shí)，可以對數(shù)組進(jìn)行初始化，也就是為數(shù)組元素設(shè)置指定的初始值。例如：int[]a={9,12,-1,3,6};或者Int[]a=new[]{9,12,-1,3,6}聲明了一個(gè)int類型的數(shù)組a，并且用花括號中的數(shù)據(jù)對這個(gè)數(shù)組進(jìn)行了初始化，各個(gè)數(shù)據(jù)之間用“,”分隔開。此時(shí)數(shù)組的大小由花括號中的用于初始化數(shù)組的元素個(gè)數(shù)決定，注意不要在數(shù)組聲明中指定數(shù)組的大小，否則將會引起錯誤。例如：Inta[20]={9,12,-1,3,6};//編譯出錯4.1一維數(shù)組4．一維數(shù)組元素的訪問聲明并創(chuàng)建數(shù)組以后，就可以訪問它了。需要注意的是，數(shù)組的訪問以元素為單位，不能直接訪問數(shù)組整體。數(shù)組元素可通過下標(biāo)訪問，一般形式為：數(shù)組名[下標(biāo)]例如：a[0]=3;s=s+a[i];下標(biāo)可以是整型表達(dá)式。Java中數(shù)組元素的下標(biāo)從0開始，因此，若數(shù)組長度為n，則下標(biāo)從0開始，最大為n?1。程序中可以使用如下形式的表達(dá)式來獲得數(shù)組的長度值，也就是數(shù)組的元素個(gè)數(shù)。數(shù)組名.lenght4.1一維數(shù)組【例4-1】輸入一個(gè)班10名學(xué)生的數(shù)學(xué)成績，求這10名學(xué)生的平均數(shù)學(xué)成績?！境绦颉俊具\(yùn)行結(jié)果】輸入內(nèi)容為：輸出內(nèi)容為：【程序說明】一旦數(shù)組被建立，數(shù)組就具有固定大小。因此，數(shù)組引用使用的下標(biāo)必須指向有效的數(shù)組元素，即下標(biāo)范圍必須是0～n?1（n為數(shù)組長度）。4.1一維數(shù)組【例4-2】用foreach實(shí)現(xiàn)例4-1?！境绦颉俊具\(yùn)行結(jié)果】輸入內(nèi)容為：輸出內(nèi)容為：【程序說明】foreach語句是for語句的特殊簡化版本，但是foreach語句并不能完全取代for語句。如果要引用數(shù)組或者集合的索引，foreach語句無法做到，foreach僅能老老實(shí)實(shí)地遍歷數(shù)組或者集合一遍。4.1一維數(shù)組4.1.2順序查找一維數(shù)組的一個(gè)典型應(yīng)用就是解決查找問題。查找是指在一批數(shù)據(jù)中查找某個(gè)指定的數(shù)據(jù)。例如，在10個(gè)數(shù)（92，23，40，90，82，34，12，98，35，5）中查找90這個(gè)數(shù)，或者在這10個(gè)數(shù)中查找100這個(gè)數(shù)，前者可以找到90，而后者找不到100。順序查找法是最簡單、最直觀的查找方法。要查找的指定數(shù)據(jù)通常稱為關(guān)鍵字，順序查找的基本思路是，從表中的第一個(gè)元素開始，依次與關(guān)鍵字比較，若某個(gè)元素與關(guān)鍵字相等，則查找成功；若查找到最后一個(gè)元素，仍然沒有數(shù)組元素與關(guān)鍵字相等，則查找失敗。順序查找的優(yōu)點(diǎn)是數(shù)組中的數(shù)據(jù)無須按大小順序排列，缺點(diǎn)是時(shí)間復(fù)雜度較大，數(shù)據(jù)規(guī)模較大時(shí)，效率較低。4.1一維數(shù)組【例4-3】順序查找。【程序】【程序說明】index用于存放與關(guān)鍵字相等的數(shù)組元素的下標(biāo)，初始值設(shè)置為?1。for循環(huán)語句實(shí)現(xiàn)數(shù)組元素與關(guān)鍵字的依次比較，如果相等，則記錄下標(biāo)，并用break語句終止循環(huán)；否則繼續(xù)比較。循環(huán)結(jié)束以后，如果index的值為?1，表明index一直沒有被重新賦值，也就是沒有數(shù)組元素值與關(guān)鍵字相等，否則index的值即為與關(guān)鍵字相等的數(shù)組元素的下標(biāo)。4.1一維數(shù)組4.1.3二分查找對于元素已排序的數(shù)組數(shù)據(jù)，常利用二分查找法。假設(shè)數(shù)組元素已按升序排列，二分查找法的核心思想如下。（1）首先，將數(shù)組中間位置元素與關(guān)鍵字比較，如果兩者相等，則查找結(jié)束；否則進(jìn)行下一步操作。（2）利用中間位置元素將數(shù)組分成前、后兩段，如果中間位置元素大于查找數(shù)據(jù)，則進(jìn)一步查找前半段，否則進(jìn)一步查找后半段，這樣查找范圍將縮小一半。（3）重復(fù)以上過程，直到找到和查找數(shù)據(jù)匹配的元素，則查找成功，若查找區(qū)間為空，則表示找不到要查找的數(shù)據(jù)。二分查找的效率顯著高于順序查找，但前提是數(shù)組元素必須是有序的。4.1一維數(shù)組【例4-4】二分查找。【程序】【程序說明】程序中用while循環(huán)結(jié)構(gòu)實(shí)現(xiàn)二分查找，每循環(huán)一次，查找區(qū)間縮小一半。如果找到要查找的數(shù)據(jù)，記錄數(shù)組下標(biāo)，并用break語句終止循環(huán)。4.1一維數(shù)組4.1.4選擇排序排序是指將一組無序的數(shù)據(jù)，重新排列成一個(gè)有序（升序或降序）序列的過程。n個(gè)數(shù)據(jù)選擇排序（升序）的思想如下：第1步：在未排序的n個(gè)數(shù)（a[0]～a[n?1]）中找到最小數(shù)，將其與a[0]交換；第2步：在剩下未排序的n?1個(gè)數(shù)（a[1]～a[n?1]）中找到最小數(shù)，將其與a[1]交換；第3步：在剩下未排序的n?2個(gè)數(shù)（a[2]～a[n?1]）中找到最小數(shù)，將其與a[2]交換；……第n?1步：在剩下未排序的2個(gè)數(shù)（a[n?2]～a[n?1]）中找到最小數(shù)，將其與a[n?2]交換；n個(gè)數(shù)據(jù)選擇排序的算法如下：4.1一維數(shù)組【例4-5】創(chuàng)建長度為10的整型一維數(shù)組，元素初始值為隨機(jī)正整數(shù)，用選擇法排序輸出。【程序】【程序說明】程序中，在查找最小值的過程中，記錄下標(biāo)值minIndex，然后進(jìn)行比較和交換。4.1一維數(shù)組4.1.5冒泡排序冒泡排序同樣是一種經(jīng)典的排序方法。其基本思想是，從數(shù)組的第1個(gè)元素開始，數(shù)組前后兩個(gè)元素兩兩比較，如果兩個(gè)元素的順序不滿足要求，則相互交換位置。這樣，經(jīng)過第1輪比較，數(shù)組中最大的元素到達(dá)數(shù)組末尾，經(jīng)過第2輪比較，數(shù)組中次大的元素到達(dá)數(shù)組倒數(shù)第二的位置。重復(fù)以上步驟，數(shù)組中所有元素即完成了從小到大的排序。由于該排序類似于氣泡小的上升、大的沉底，故名冒泡法。冒泡排序的算法過程如下（以n個(gè)數(shù)從小到大排序?yàn)槔海?）第1輪冒泡排序：對n個(gè)數(shù)的每相鄰兩數(shù)進(jìn)行比較，如果不是從小到大的順序，則交換兩數(shù)。結(jié)果為最大的數(shù)被安置在最后一個(gè)位置上；（2）第2輪冒泡排序：對前面的n?1個(gè)數(shù)進(jìn)行冒泡，結(jié)果為次大的數(shù)被安置在最后第二的位置上；……（3）重復(fù)上述過程，共經(jīng)過n?1輪冒泡排序后，排序結(jié)束。4.1一維數(shù)組【例4-6】創(chuàng)建長度為10的整型一維數(shù)組，元素初始值為隨機(jī)正整數(shù)，用冒泡法排序輸出?！境绦颉俊境绦蛘f明】外層循環(huán)的含義：需要遍歷a.length?1次數(shù)組，才能將數(shù)組排好序。內(nèi)層循環(huán)的含義：待排序區(qū)域的起始和結(jié)尾位置。02二維數(shù)組4.2二維數(shù)組4.2.1二維數(shù)組的聲明、創(chuàng)建與初始化1．二維數(shù)組的聲明同一維數(shù)組類似，二維數(shù)組的聲明方式也有以下兩種。方式一：數(shù)據(jù)類型[][]數(shù)組名稱例如：Double[][]b;方式二：數(shù)據(jù)類型數(shù)組名稱[][];例如：doubleb[][];4.2二維數(shù)組2．二維數(shù)組的創(chuàng)建同一維數(shù)組類似，通過new運(yùn)算符可進(jìn)行二維數(shù)組的創(chuàng)建。創(chuàng)建每行列數(shù)都相同的二維數(shù)組的語法格式如下：數(shù)組名稱=new數(shù)據(jù)類型[數(shù)組行數(shù)][數(shù)組列數(shù)]例如，對于前面聲明，可以用以下語句創(chuàng)建3行4列的二維數(shù)組b：b=newdouble[3][4];與一維數(shù)組類似，也可以將聲明和創(chuàng)建合二為一：double[][]b=newdouble[3][4]Java語言不要求二維數(shù)組中每行的元素個(gè)數(shù)相同，例如：a數(shù)組中元素的分布如圖4-1所示。4.2二維數(shù)組3．二維數(shù)組的初始化同一維數(shù)組一樣，二維數(shù)組創(chuàng)建之后，系統(tǒng)為每個(gè)數(shù)組元素分配一個(gè)默認(rèn)值，如int型數(shù)據(jù)的值為0，double型數(shù)據(jù)的值為0.0。在聲明數(shù)組的同時(shí)，也可以為數(shù)組中的元素賦值，例如：intscore[][]={{85,90,65},{70,93,88}};//數(shù)組行數(shù)為2，列數(shù)為3doubleweight[][]={{61.5,70.3},{91.4,89.5}}//2行2列的數(shù)組需要注意的是，在聲明二維數(shù)組的同時(shí)為數(shù)組中的元素賦值時(shí)，必須用花括號{}將數(shù)組中的行元素括起來，不同的行元素之間用逗號分隔開。對于每行元素個(gè)數(shù)不一樣的二維數(shù)組，可以采用如下方式初始化：intscore[][]={{60},{85,90},{70,93,88}}則數(shù)組score第1行有1個(gè)元素，第2行2個(gè)元素，第3行3個(gè)元素。4.2二維數(shù)組4．二維數(shù)組元素的引用可以通過行下標(biāo)和列下標(biāo)來引用二維數(shù)組中的某個(gè)數(shù)組元素，其中，數(shù)組行下標(biāo)和列下標(biāo)均從0開始。因此，對一個(gè)2行3列的數(shù)組，其行下標(biāo)為0和1，列下標(biāo)為0,1,2。否則，程序?qū)l(fā)生數(shù)組下標(biāo)越界異常。和一維數(shù)組不同的是，二維數(shù)組的length屬性指明了數(shù)組的行數(shù)。通過“數(shù)組名稱.length”可以得到數(shù)組的行數(shù)，通過“數(shù)組名稱[i].length”可以得到數(shù)組第i行的列數(shù)。4.2二維數(shù)組【例4-7】輸入10名學(xué)生4門課的成績，計(jì)算輸出每名學(xué)生的總成績。【程序】【程序說明】外層循環(huán)變量i控制矩陣的行數(shù)，內(nèi)層循環(huán)變量j控制矩陣的列數(shù)。4.2二維數(shù)組4.2.2用二維數(shù)組表示矩陣矩陣是由m*n個(gè)數(shù)排成的m行n列的數(shù)組，記為：矩陣是高等數(shù)學(xué)中的常見工具，也常用于統(tǒng)計(jì)分析等應(yīng)用數(shù)學(xué)學(xué)科中。在物理學(xué)中，矩陣在電路學(xué)、力學(xué)、光學(xué)和量子物理中都有應(yīng)用。在計(jì)算機(jī)科學(xué)中，三維動畫制作也需要用到矩陣。矩陣的運(yùn)算是數(shù)值分析領(lǐng)域的重要問題，二維數(shù)組是矩陣的常用表示方式。需要注意的是，在數(shù)學(xué)上，矩陣的下標(biāo)從1開始，而Java中數(shù)組的行下標(biāo)和列下標(biāo)都從0開始。4.2二維數(shù)組【例4-8】矩陣的乘法運(yùn)算。設(shè)A為m*p的矩陣，B為p*n的矩陣，那么稱m*n的矩陣C為矩陣A與B的乘積。其中，矩陣C中的第i行第j列的元素可以表示為【程序】【程序說明】二維數(shù)組A的長度是2，B的長度是3，三重循環(huán)中，最內(nèi)層循環(huán)k的值為從0到2。03范例4.3范例【例4-9】輸入一個(gè)班10名學(xué)生的數(shù)學(xué)成績，求數(shù)組中大于平均值的元素并顯示?！境绦颉俊痉治觥壳蠼鈹?shù)組的題目一般分為幾個(gè)步驟：數(shù)組的聲明與輸入；數(shù)組的相關(guān)操作；結(jié)果的輸出。本題中使用foreach語句，簡化了for循環(huán)的編寫。4.3范例【例4-10】輸入一個(gè)班10名學(xué)生的數(shù)學(xué)成績，將數(shù)學(xué)最高分顯示輸出?！境绦颉俊痉治觥吭O(shè)最大值變量為max，由于變量存放為數(shù)學(xué)成績，故不會出現(xiàn)負(fù)值，所以max可以設(shè)置為0，然后與數(shù)組中的元素分別進(jìn)行比較，得出最大值。4.3范例【例4-11】使用Java隨機(jī)生成30個(gè)0～9之間的數(shù)字，分別統(tǒng)計(jì)0～9這10個(gè)數(shù)字分別出現(xiàn)了多少次?！境绦颉俊痉治觥渴紫壬?0個(gè)0～9之間的數(shù)字，定義數(shù)組b來存放每個(gè)數(shù)字出現(xiàn)的次數(shù)，a的值恰好是數(shù)組b的下標(biāo)。4.3范例【例4-12】篩選法求質(zhì)數(shù)：輸入一個(gè)整數(shù)n，求小于這個(gè)整數(shù)的所有質(zhì)數(shù)。【程序】【分析】定義一個(gè)長度為n的boolean型數(shù)組，true表示是質(zhì)數(shù)，false表示不是質(zhì)數(shù)，初始值均為true，之后從2開始循環(huán)。（1）找到第一個(gè)值為true的下標(biāo)i。（2）把所有下標(biāo)為i的倍數(shù)的值置為false。直到掃描完數(shù)組中的所有數(shù)值，最后遍歷數(shù)組，如果下標(biāo)i的值為true，則說明i為質(zhì)數(shù)。范例【例4-13】假設(shè)有10位候選人參加學(xué)生會主席選舉，實(shí)現(xiàn)選票的統(tǒng)計(jì)工作，輸出最終獲勝者的編號?！境绦颉俊痉治觥棵课缓蜻x人的編號為1～10，如果希望為某位候選人投票，就從鍵盤上輸入這位候選人的編號。每位候選人的選票數(shù)存放在一個(gè)數(shù)組a中，a[i]的值就表示編號為i的候選人的選票數(shù)。程序中，先用do-while循環(huán)輸入選票并統(tǒng)計(jì)各候選人的選票數(shù)，然后從數(shù)組中找出最大值的下標(biāo)。4.3范例【例4-14】明明想在學(xué)校中請同學(xué)一起做一項(xiàng)問卷調(diào)查，為了調(diào)查的客觀性，他先用計(jì)算機(jī)生成了n個(gè)1到1000之間的隨機(jī)整數(shù)（1≤n≤100），對于其中重復(fù)的數(shù)字，只保留一個(gè)，不同的數(shù)對應(yīng)不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作。【分析】這里的n個(gè)整數(shù)都是1到1000之間的整數(shù)，可以定義長度為1001（下標(biāo)為0～1000）的數(shù)組a。數(shù)組元素a[i]的值為0，表示i不存在。4.3范例【程序】4.3范例【例4-15】輸入一個(gè)日期，輸出該天是這一年中的第幾天。【分析】閏年的二月份是29天，非閏年的二月份是28天，可以將每個(gè)月的天數(shù)存放在一個(gè)2行12列的二維數(shù)組中，第1行存放非閏年的每月天數(shù)，第2行存放閏年的每月天數(shù)。將所輸入日期之前的所有完整月的天數(shù)相加，再加上本月到該日期為止的天數(shù)，就是該日期在這一年中的第幾天。例如，如果輸入的天數(shù)是2016年9月