Java程序設(shè)計大學(xué)教程第五章.ppt

第五章 算法與數(shù)據(jù)結(jié)構(gòu),程序是建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上使用計算機語言描述的算法，因此簡單地講，程序也可以表示成：算法數(shù)據(jù)結(jié)構(gòu)。 介紹算法的概念及常用算法。并通過數(shù)組、鏈表、棧、隊列等數(shù)據(jù)結(jié)構(gòu)以及Java對象容器，討論算法的應(yīng)用及算法的Java程序?qū)崿F(xiàn)。,5.1 算法,算法是為了求解某一問題在有限步驟內(nèi)、定義了具體操作序列的規(guī)則集合。一個算法應(yīng)該具有以下五個重要的特征 ： 確切性（No ambiguity） 算法的每一步驟必須有確切的定義。而不應(yīng)該有二義性，例如，在算法中不能出現(xiàn)諸如“賦值為100或1000”。 輸入（Input） 有0個或多個輸入，用于初始化運算對象。所謂0個輸入是指無需輸入條件，而算法本身定出了初始條件。 輸出（Output） 沒有輸出的算法是毫無意義的。一個算法應(yīng)該有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。 可行性（Feasibility） 算法原則上能夠精確地運行，而且對于算法中的每種運算，在原理上人們應(yīng)該能用筆和紙做有限次運算后完成。 有窮性（Finite） 算法必須保證執(zhí)行有限步之后結(jié)束。只具有前面四個特征的規(guī)則集合，稱不上算法。例如，盡管操作系統(tǒng)能完成很多任務(wù)，但是它的計算過程并不終止，而是無窮無盡的執(zhí)行、等待執(zhí)行，所以操作系統(tǒng)不是算法。,5.1.1 算法的描述,1、偽代碼描述 : 偽代碼（Pseudo-code）是一種算法描述語言。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言（如Pascal、C、Java等）實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰，代碼簡單，可讀性好，并且類似自然語言。,偽代碼描述的算法： 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代碼實現(xiàn)： 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;,5.1.1 算法的描述,2、圖形描述 : 程序設(shè)計中，能夠用來表示算法基本概念的圖主要有：PAD圖、NS盒圖、流程圖。,程序流程圖常用圖形符號及控制結(jié)構(gòu)圖例,5.1.2 常用算法,基本算法大都比較簡單，是其他算法的基礎(chǔ)。這類算法在程序中應(yīng)用非常普遍，如：累加求和、累乘求積、求最大和最小值等。,從10個數(shù)中求最大值算法 的例子,偽代碼描述算法： FindLargest Input: 10 positive integers 1. largest0 2. counter0 3. while(counter largest) then 3.2.1 largesttheInteger end if 3.3 countercounter+1 end while 4. Return largest End,Java語言實現(xiàn)： import java.io.*; public class Max public static void main(String args) throws IOException /初始化 BufferedReader input = new BufferedReader (new InputStreamReader(System.in); int largest=0; int counter=0; int theInteger=0; /循環(huán)比較 while(counter largest) largest=theInteger; / while System.out.println(“求出最大數(shù)是：“+largest); ,5.1.2 常用算法,排序算法根據(jù)數(shù)據(jù)的值對它們進(jìn)行排列。排序是為了把不規(guī)則的信息進(jìn)行整理，以提高查找效率。常用的排序方法包括：選擇排序、冒泡排序、插入排序、快速排序、合并排序、希爾排序、堆排序等。 查找是一種在列表中確定目標(biāo)所在位置的算法。基本的查找方法有順序查找和折半查找。 迭代和遞歸是用于編寫解決問題的算法的兩種途徑。迭代就是反復(fù)替換的意思，它通過使用一個中間變量保存中間結(jié)果，不斷反復(fù)計算求解最終值。遞歸是一個算法自我調(diào)用的過程，用遞歸調(diào)用的算法就是遞歸算法。,階乘迭代算法偽代碼 ： Factorial Input:Apositive integer num 1. FactN1 2. i1 3. While（i or = num） 3.1 FactNFactN 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 numFactorial(num-1) end if end,5.2 數(shù)組,數(shù)組用于表示相同類型的元素的有序集合，數(shù)組中每個元素都有一個唯一的索引。 根據(jù)數(shù)組的分配方式可將數(shù)組分為：一維數(shù)組和多維數(shù)組。Java中還可以定義不規(guī)則數(shù)組。我們可以把一維以上的數(shù)組看作是“數(shù)組的數(shù)組”。,5.2.1 數(shù)組的創(chuàng)建和使用,數(shù)組是一個被命名的連續(xù)存儲區(qū)域的集合，存放著相同類型的數(shù)據(jù)項。數(shù)組的每個元素通過它在數(shù)組里的位置索引來引用。數(shù)組索引必須是一個整數(shù)值或者一個整數(shù)表達(dá)式。 在Java里，大多數(shù)情況下數(shù)組被當(dāng)成對象來對待。它們是用new操作符來實例化的，有自己的實例變量（例如length，可返回數(shù)組中第一維的元素數(shù)量）。數(shù)組變量是引用類型的變量。 定義與創(chuàng)建一個數(shù)組的語法及例子。,定義與創(chuàng)建一個數(shù)組的語法： 數(shù)組類型名稱 數(shù)組變量名;/定義數(shù)組變量 (也可以寫成：數(shù)組類型名稱 數(shù)組變量名;/定義數(shù)組變量) 數(shù)組變量名 = new 數(shù)組類型名稱n;/創(chuàng)建長度為n的數(shù)組 以上兩步也可以合并寫為： 數(shù)組類型名稱 數(shù)組變量名= new 數(shù)組類型名稱n; 或者： 數(shù)組類型名稱 數(shù)組變量名= new 數(shù)組類型名稱n;,定義與創(chuàng)建一個數(shù)組的示例： Fruit fruits ; /定義Fruit類型的數(shù)組變量fruits fruits = new Fruit5; /新建有5個元素的數(shù)組fruits fruits0 = new Fruit(“香蕉“, 1000);/為數(shù)組元素賦值（引用對象） fruits1 = new Fruit(“葡萄“, 2000); fruits2 = new Fruit(“菠蘿“, 2000); fruits3 = new Fruit(“草莓“, 1000); fruits4 = new Fruit(“橘子“, 1000); int n = fruits.length; /測試數(shù)組長度,用不規(guī)則數(shù)組實現(xiàn) 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6,用2維數(shù)組實現(xiàn)每日股指顯示 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 多維數(shù)組和不規(guī)則數(shù)組,根據(jù)數(shù)組的分配方式可將數(shù)組分為：一維數(shù)組和多維數(shù)組。Java中還可以定義不規(guī)則數(shù)組。我們可以把一維以上的數(shù)組看作是“數(shù)組的數(shù)組”。,模擬每日股指的程序Stock public class Stock public Stock() for (int week=1;week=52;week+) stockValueweek0=week; for (int weekday=1;weekday=5;weekday+) stockValue0weekday=weekday; int stockIndex = (int)(Math.random()*1000+1000); stockValueweekweekday = stockIndex; public void printStock() for (int week=0;week=52;week+) for (int weekday=0;weekday=5;weekday+) System.out.print(stockValueweekweekday+“t“); System.out.println(); public static void main(String args) Stock s=new Stock(); s.printStock();/打印股指年表 int stockValue= new int536; ,不規(guī)則數(shù)組演示程序 ArrTest public class ArrTest public ArrTest() for (int n=1;nmyArr.length;n+) myArrn = new intn+1;/創(chuàng)建數(shù)組的數(shù)組，每個數(shù)組的長度不一樣。 for (int m=1; mmyArrn.length; m+) myArrnm=m; public void printArr() for (int n=1; nmyArr.length; n+) for (int m=1;mmyArrn.length;m+) System.out.print(myArrnm+“t“); System.out.println(); public static void main(String args) ArrTest arr=new ArrTest(); arr.printArr(); int myArr= new intMax+1;/定義不規(guī)則數(shù)組，先創(chuàng)建數(shù)組的第1維。 static int Max=6; ,5.2.3 排序,冒泡法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上??；較大的元素比較重，從而要往下沉。一個含有n個元素的列表，冒泡排序需要n-1次掃描來完成數(shù)據(jù)排序。 快速排序是對冒泡排序的一種改進(jìn)。它的基本思想是，通過一輪排序?qū)⒋判虻臄?shù)組元素分割成獨立的兩部分，其中一部分元素的關(guān)鍵字均比另一部分元素的關(guān)鍵字小，則分別可對這兩部分元素繼續(xù)進(jìn)行排序，以達(dá)到整個數(shù)組序列有序。,冒泡排序比較和交換的過程演示,5.2.4 查找,順序查找就是將要查找的數(shù)據(jù)的關(guān)鍵字按一定的順序挨個與列表中的數(shù)據(jù)進(jìn)行比較，相等時就找到了所要的數(shù)據(jù)。 對有序的列表可以使用更有效率的折半查找。折半查找是從一個列表的中間的元素來測試的，這將能夠判別出目標(biāo)在列表里的前半部還是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。換句話說，可以通過判斷排除一半的列表。重復(fù)這個過程直到找到目標(biāo)或是目標(biāo)不在這個列表里。,順序查找和折半查找示例程序： public class Search /順序查找 public int sequentialSearch(int arr, int key) for (int k = 0; k arr.length; k+) if (arrk = key) return k; / 成功,返回該數(shù)組元素的位置（即索引） 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 (arrmid = key) return mid; / 成功,返回該數(shù)組元素的位置（即索引） else if (arrmid key) low = mid + 1; / 定位查找上半段 else high = mid - 1; / 定位查找下半段 return -1; / 失敗,返回-1 ,5.3 對象容器,使用數(shù)組管理對象雖然有較高的計算效率，但是數(shù)組要求固定對象的數(shù)量，操作起來并不方便。特別當(dāng)對象數(shù)量不明確的情況下，我們需要更復(fù)雜的方法來管理對象。 Java類庫中提供了一些用于管理對象集的類，稱之為容器類（container classes）。它們可以在程序中用作對象的容器，持有和操作對象而不用擔(dān)心容量的變化。 Java容器的缺點是：一旦把對象放進(jìn)容器，便失去了該對象的類型信息。容器中對象集的元素都是最基本的Object類型，也就是說，無論是何種類型的對象，進(jìn)入容器后都向上轉(zhuǎn)型為Object。因此，當(dāng)我們從容器中取出對象時，可能無法知道它原來的類型。如果知道或者可以通過某種算法來判定出原來的類型，則可以將其轉(zhuǎn)型為最初的實際類型。,5.3.1 Java容器框架,列表（list） 按照一定次序排列的對象集，對象之間有次序關(guān)系。 集合（set） 無次序的對象集，但這些對象都是唯一的，不會重復(fù)。 映射（map） 一群成對的對象集，這些對象各自保持著“鍵-值”（key-value）對應(yīng)關(guān)系。其中，作為“鍵”的那些對象一定是一個set，即這些對象是唯一的，不會重復(fù)。,5.3.2 Collection與Iterator,Collection是Java容器框架中的高層接口，它聲明了所有容器類的核心方法，包括添加、清除、比較和持有對象（也稱為對象集的元素）的操作。此外，Collection接口還提供了一個方法用于返回Iterator。 迭代器是一個實現(xiàn)了Iterator或ListIterator接口的對象。它是一種“輕量級”的對象，消耗較小的資源，具有較高的效率，能夠滿足對象集的遍歷。,5.3.3 List及ListIterator,編程中最常用到的是List容器。List容器的重要屬性是對象按次序排列。List通常由ArrayList和LinkList來實現(xiàn)，它提供了列表的插入、刪除、定位、截取、遍歷等操作。 ArrayList 以可變數(shù)組實現(xiàn)完成的List容器。允許快速隨機訪問，但是當(dāng)元素的插入或移除發(fā)生于List中央位置時，效率便很差。對于ArrayList，建議使用ListIterator來進(jìn)行向后或向前遍歷，但而不宜用其來進(jìn)行元素的插入和刪除，因為所花代價遠(yuǎn)高于LinkedList。 LinkedList 以雙向鏈表（double-linked 1ist）實現(xiàn)完成的List容器