體驗Java的功能。
8-1-0 基本觀念
用電腦來解決問題,是人類的一大進步,可是問題要交給電腦解決,就一定要有方法;而把問題資料化,亦即設計一套資料的組合與操作法則來表示原始問題與各種可能的處理結果,是其中的關鍵!
8-1-1 從資料到資料結構
描述現實問題的結構: 在描述平常生活中遇到的事物時,會用到的多半不只單一資料型態,甚至經常是幾種資料型態的特定組合,這樣的組合就形成了所謂的『結構 (structures)』。 結構一樣會給個名稱,屬於同一種結構的實體資料會有固定大小的儲存空間以及相同的型態組合。 結構可以更貼切地描述現實問題。
由基本資料型態發展到資料結構的過程
8-1-2 定義資料結構
資料的定義與組織: 資料的定義包含了各資料項目的名稱與其型態。
和資料有關的操作: 資料結構除了要含有各種必要的資料項目,更重要的是它還必須好利用。
實作由概念而來
8-1-3 抽象資料型態
抽象資料型態(ADT)的由來: 用電腦來解決問題,必須將現實世界的事物或觀念轉化成資料結構來表示,所以才會把實體的資料依照資料型態來分類,然後將資料型態組織成資料結構。 完整的資料結構定義可能過於複雜,在分析問題時反而成為理解上的障礙,因此就有了所謂的抽 象資料型態 (ADT, abstract data types)。
抽象資料型態(ADT)的特性: 抽象資料型態在設計上希望做到隱藏內部細節、展現平易外觀的目的,也就是讓使用者能善用資料結構,卻不必了解其內部的運作細節。 理論上常把ADT定義為將資料規格 (specification) 與實作(implementation)分開的資料型態。 Java語言中有一種介面(interface)定義,只含有程序的宣告,沒有實作的程式,算是ADT概念的實現。
抽象資料型態的實例
8-1-4 從實作觀點看資料結構的分類
ex. IP位址的分級, 通常在實作時, 我們會把資料結構當成一種資料型態(data type)
-2-1 資料結構與演算法的關聯
用演算法表示問題的解決方法: 了解問題、描述問題、表示出問題的解決方法、執行並解決問題
偏向programmer的觀點: algorithms + data structures = programs 的觀念。 資料結構是要用來配合演算法寫程式解決問題的。 經過多年理論性的探討與發展,已經發展出一些好用的資料結構與演算法,只要能了解其原理,就能用來解決很多不同的問題。
演算法的基本特性: 演算法algorithm代表一系列為達成某種目標而進行的工作,通常這些工作都是針對資料所做的處理。電腦科學中所談的演算法是比較嚴謹的,所以我們要求一個演算法具備一些必要的特性。
8-2-3 資料結構、演算法與程式語言
基本觀念: 資料結構用來表示問題與最後的解答,而演算法則描述解決問題的方法。 資料結構跟演算法都還是以人類的方式來思考的,因此必須再用某種程式語言來完成資料宣告、並將 演算法的程序寫成程式,才能交由電腦來執行。 要用哪一種程式語言,並沒有特別規定,任何一種程式語言都應該有能力把觀念具體化。
資料結構、演算法與程式語言的關聯: 電腦的主要功能是對輸入的資料進行運算 (computation)。 資料放入與輸出的形式由資料結構來決定,運算過程按照演算法來執行。 執行的動作要靠程式語言來驅動才能實現。
簡單的比喻
8-3-1 認識矩陣 (matrix)
基本觀念: 矩陣是數學裡頭定義的一種結構,由數值所組成。 矩陣中的數值排起來像矩形,橫向的為列、縱向的是行。 橫列的數目與縱行的數目不一定要一樣,但是每一行的元素數目等於橫列的數目、而每一列的元素數目等於縱行的數目。
8-3-2 矩陣的資料結構設計
資料結構設計: 矩陣可以直接用二維陣列來表示。 矩陣的列(row)與行(column)對應到二維陣列的兩個索引,矩陣的行對應到二維陣列的行索引,矩陣的列則對應到二維陣列的列索引。
8-3-3 矩陣的操作與處理方法
常見的矩陣運算: 轉置 (transpose)。 相加。 相乘。
8-3-4 矩陣的程式實作
matrix.java
public interface matrix {
myMatrix transpose(myMatrix A);
myMatrix add(myMatrix A, myMatrix B);
myMatrix multiply(myMatrix A, myMatrix B);
public void printMatrix();
}
矩陣的Java 實作：myMatrix.java
public class myMatrix implements matrix{
int column, row;
double element[ ][ ]; // 矩陣資料的型態為一般的實數
myMatrix(int d_row, int d_column, double d_element[ ][ ])
{ // 建構子(constructor)
column=d_column; row = d_row;
element = new double [row][column];
element=d_element;
}
public myMatrix transpose(myMatrix A) //矩陣轉置的運算
{
double r_element[ ][ ]=new double [A.column][A.row];
myMatrix result = new myMatrix(A.column, A.row, r_element);
for (int i=0; i<A.row; i++)
for (int j=0; j<A.column; j++)
result.element[j][i]=A.element[i][j]; // 將行與列的元素資料交換
return result;
}
public myMatrix add(myMatrix A, myMatrix B) //矩陣加法的運算
{
double r_element[ ][ ]=new double [A.row][A.column];
myMatrix result = new myMatrix(A.row, A.column, r_element);
for (int i=0; i<A.row; i++)
for (int j=0; j<A.column; j++)
result.element[i][j]=A.element[i][j]+B.element[i][j];
return result;
}
public myMatrix multiply(myMatrix A, myMatrix B) //矩陣乘法的運算
{
double r_element[ ][ ]=new double [A.row][B.column];
myMatrix result = new myMatrix(A.row, B.column, r_element);
double sum;
for (int i=0;i<A.row;i++)
for (int j=0; j<B.column; j++)
{ sum=0;
for (int k=0;k<B.row;k++)
sum=sum+A.element[i][k]*B.element[k][j];
result.element[i][j]=sum;
};
return result;
}
public void printMatrix()
{
for (int i=0; i<this.row; i++)
{
for (int j=0; j<this.column; j++)
System.out.print(this.element[i][j]+ " ");
System.out.println();
}
}
}
8-4-1 認識多項式
多項式也可以用陣列來表示,有了這種表示法,我們就能以 Java程式來表示多項式的運算。一 般在數學裡頭,一個次數為n的多項式可以用下面的方式來表示：
f(x)= cₙxⁿ+ cₙ₋₁xⁿ⁻¹+ ……+ c₁x+ c₀, nN, cᵢR
8-4-2 多項式資料結構的設計
用陣列依序儲存各次項的係數: 一個次數 (或稱冪次 )為n的多項式可以用一個含有「n+2」個元素的一維陣列來表示,以多項式一般式來說,就可以陣列來表示：
f(x)= cₙxⁿ+ cₙ₋₁xⁿ⁻¹+ ……+ c₁x+ c₀, nN, cᵢR ……….多項式一般式
陣列F, 內含的元素依序為: n, cₙ, cₙ₋₁, ……, c₁, c₀……陣列表示法
用陣列依序儲存係數不為0的次項的係數: 只儲存係數非0的項次。 同樣使用一維陣列來表示多項式。 必須記錄多項式的項次數目,以及各次項與對應的係數。
多項式表示方式的實例
8-4-3 多項式的操作與處理方法
多項式的產生: 產生一個多項式時必須記載多項式總共有幾項,以及各項次的係數。 係數為 0的次項對於多項式的操作沒有影響,所以不需要記載。
多項式的加法
多項式的乘法: 兩個多項式相乘會將兩個多項式的各次項兩兩相乘,也就是把係數相乘、次數相加,乘完以後,同樣要把次數相同的次項的係數相加變成單一的次項。 由於已經有加法的運算,所以在乘法中,我們可以將其中一個多項式逐項乘以第2個多項式,然後呼叫加法加到結果多項式中。
8-4-4 多項式的程式實作
多項式的ADT, polynomial.java
public interface Polynomial {
public MyPolynomial add(MyPolynomial poly1, MyPolynomial poly2);
public MyPolynomial multiply(MyPolynomial poly1, MyPolynomial poly2);
public void printPolynomial();
}
myPolynomial.java
public class MyPolynomial implements Polynomial{
int numOfTerms;
double [ ] coeff;
int [ ] order;
public MyPolynomial(int num, double [ ] coeff_in, int [ ] order_in)
{ // 多項式的建構子
numOfTerms=num;
coeff=coeff_in;
order=order_in;
}
public MyPolynomial add(MyPolynomial poly1, MyPolynomial poly2)
{
int num_result=poly1.numOfTerms+poly2.numOfTerms;
// 結果多項式最大可能出現的項數
double coeff_result[]=new double[num_result];
int order_result[]=new int[num_result];
MyPolynomial result=new MyPolynomial(num_result,coeff_result,order_result);
int p1=0, p2=0, p3=0; // p3決定結果多項式的項數
while (p1 != poly1.numOfTerms || p2 != poly2.numOfTerms)
// p1與p2追蹤各多項式處理到那一項
{ if (p1 == poly1.numOfTerms) // p1追蹤的多項式處理完畢
while (p2 != poly2.numOfTerms)
{ result.order[p3]=poly2.order[p2];
result.coeff[p3]=poly2.coeff[p2];
p2++;
if (result.coeff[p3]!=0) p3++;
};
if (p2 == poly2.numOfTerms) // p2追蹤的多項式處理完畢
while (p1 != poly1.numOfTerms)
{ result.order[p3]=poly1.order[p1];
result.coeff[p3]=poly1.coeff[p1];
p1++;
if (result.coeff[p3]!=0) p3++;
};
if (p1 != poly1.numOfTerms && p2 != poly2.numOfTerms && poly1.order[p1] > poly2.order[p2])
{ result.order[p3]=poly1.order[p1];
result.coeff[p3]=poly1.coeff[p1];
p1++;
if (result.coeff[p3]!=0) p3++;
}
else
if (p1 != poly1.numOfTerms && p2 != poly2.numOfTerms && poly1.order[p1] == poly2.order[p2])
{ result.order[p3]=poly1.order[p1];
result.coeff[p3]=poly1.coeff[p1]+poly2.coeff[p2];
// 冪次相等則係數相加
p1++; p2++;
if (result.coeff[p3]!=0) p3++;
}
else
if (p1 != poly1.numOfTerms && p2 != poly2.numOfTerms && poly1.order[p1] < poly2.order[p2])
{ result.order[p3]=poly2.order[p2];
result.coeff[p3]=poly2.coeff[p2];
p2++;
if (result.coeff[p3]!=0) p3++;
};
};
result.numOfTerms = p3;
return result;
}
public MyPolynomial multiply(MyPolynomial poly1, MyPolynomial poly2)
{
int num_result=poly1.numOfTerms*poly2.numOfTerms;
double coeff_result[ ]=new double[num_result];
int order_result[ ]=new int[num_result];
MyPolynomial result=new MyPolynomial(num_result,coeff_result,order_result);
double coeff_tmp[ ]=new double[num_result];
int order_tmp[ ]= new int[num_result];
MyPolynomial tmp=new MyPolynomial(num_result,coeff_tmp, order_tmp);
int p1=0;
for (int i=0; i<poly1.numOfTerms; i++)
{ p1=0;
for (int j=0; j<poly2.numOfTerms; j++)
{
tmp.coeff[p1]=poly1.coeff[i]*poly2.coeff[j];
tmp.order[p1]=poly1.order[i]+poly2.order[j];
p1++;
};
if (i==0) result.numOfTerms=p1;
tmp.numOfTerms=p1;
result.numOfTerms=Math.max(p1, result.numOfTerms);
result=result.add(result,tmp);
};
return result;
}
public void printPolynomial( )
{
for (int i=0; i<this.numOfTerms; i++)
{
if (this.coeff[i]!=0) // 只列印係數不為0的項次
System.out.print("("+this.coeff[i]+"x^"+this.order[i]+")");
if (i < (this.numOfTerms-1) && (this.coeff[i]!=0) && (this.order[i]!=0))
System.out.print("+");// 最後一項之後不必印+號
}
System.out.println( );
}
}
多項式的Java 實作：add
public class myMatrix implements matrix{
int column, row;
double element[ ][ ]; // 矩陣資料的型態為一般的實數
myMatrix(int d_row, int d_column, double d_element[ ][ ])
{ // 建構子(constructor)
column=d_column; row = d_row;
element = new double [row][column];
element=d_element;
}
public myMatrix transpose(myMatrix A) //矩陣轉置的運算
{
double r_element[ ][ ]=new double [A.column][A.row];
myMatrix result = new myMatrix(A.column, A.row, r_element);
for (int i=0; i<A.row; i++)
for (int j=0; j<A.column; j++)
result.element[j][i]=A.element[i][j]; // 將行與列的元素資料交換
return result;
}
public myMatrix add(myMatrix A, myMatrix B) //矩陣加法的運算
{
double r_element[ ][ ]=new double [A.row][A.column];
myMatrix result = new myMatrix(A.row, A.column, r_element);
for (int i=0; i<A.row; i++)
for (int j=0; j<A.column; j++)
result.element[i][j]=A.element[i][j]+B.element[i][j];
return result;
}
public myMatrix multiply(myMatrix A, myMatrix B) //矩陣乘法的運算
{
double r_element[ ][ ]=new double [A.row][B.column];
myMatrix result = new myMatrix(A.row, B.column, r_element);
double sum;
for (int i=0;i<A.row;i++)
for (int j=0; j<B.column; j++)
{ sum=0;
for (int k=0;k<B.row;k++)
sum=sum+A.element[i][k]*B.element[k][j];
result.element[i][j]=sum;
};
return result;
}
public void printMatrix()
{
for (int i=0; i<this.row; i++)
{
for (int j=0; j<this.column; j++)
System.out.print(this.element[i][j]+ " ");
System.out.println();
}
}
}
8-5-1 遞迴程式的設計
遞迴是演算法中常用的技巧,當我們發現某個問題具有遞迴問題的特性時,可以試著思考一下如何運用遞迴的方法求解。使用遞迴的關鍵在於先找到問題本身的基礎問題,而整個問題的解決可以反覆應用基礎問題的解法來求解。
紙上作業: 先找幾個典型的可由遞迴方式求解的問題,例如「n階乘」的問題,試著用演算法的各種表示法來描述求解的步驟,一般人最先想到的大概是以控制迴路的方式,要用遞迴的話一定得寫副程式,所以先把問題分成主程式和副程式兩部分。
撰寫和測試遞迴的程式: 在遞迴呼叫的過程中,盡量利用變數值的輸出來觀察呼叫call和回傳return的順序,以及程式執行的中間結果。
應用遞迴演算法來解決問題: 有了經驗之後,才會慢慢地熟悉遞迴思考的模式,接下來就可以實際地應用遞迴演算法來解決問題;雖然迴演算法有一些效率上的問題,但是在表達上十分簡潔,習慣以後對於程式的設計有很大的幫助。
8-5-2
8-5-3 河內塔問題
套環數目為1: 套環數目只有1個是最單純的狀況,可以直接將套環從A塔移至C塔就完成了,所以完成的步驟為1。
套環數目為2: 我們只能移動A塔上的第1個套環,若是移到C塔,則第2個套環不能移到第1個套環之上,所以只能先將第1個套環移到B塔,接著將第2個套環移到C塔,然後再將第1個套環移到第2個套環之上,所需要的步驟為3。
套環數目為3: 由於塔位只有3個,第3個套環又需要上面2個套環先移走才能動,所以下面的做法是先將第1個套環與第2個套環移到B塔,這需要3個步驟,方法跟前一個例子相似。
8-5-4 用Java程式解決河內塔問題
解決河內塔問題: 將上頭的 (n-1)個套環從第1個塔柱移到第2個塔柱。 將最底下的套環從第 1個塔柱移到第3個塔柱。 將第2個塔柱的套環移到第3個塔柱。
Move 方法
public class TowerOfHanoi {
static int numOfSteps=0; // 移動套環的步驟總數
public static void move(int n, int peg1, int peg2, int peg3)
// 將n個套環從塔柱peg1移到peg3, 以peg2為暫放處
{
if (n>0)
{ move(n-1,peg1,peg3,peg2); // (n-1)個套環從peg1移到peg2
numOfSteps++;
System.out.println("步驟"+numOfSteps+":將套環"+n+"從塔柱"+peg1+"移到塔柱"+peg3);
move(n-1,peg2,peg1,peg3); // 再把(n-1)個套環從peg2移到peg3
}
}
public static void main(String args[]){
int numOfRings=0; // numOfRings代表套環數目
if( args.length == 0 )
{
System.out.println( "在執行程式行上請提供套環數目!" );
System.exit(0); // 未提供套環數目! 程式跳離!
}
try
{ numOfRings = Integer.parseInt(args[0]); }
catch( Exception excep )
{
System.out.println( excep );
System.exit(0);
}
System.out.println("套環數目為:" + numOfRings);
move(numOfRings,1,2,3);
System.out.println("移動"+numOfRings+
"個套環需要進行的步驟總數為:" + numOfSteps);
}
}
8-6-1 計數排序 (Count Sort)
認識計數排序 (Count Sort) : 假設A代表要排序的陣列。 Rank 是輸出,代表各陣列元素所在的順序,由大到小。 這是排序並且列次序的方式。
public class testCountSort {
void sort(int[] a) {
int n = a.length;
int[] count = new int[n];
for (int i = 0; i < n; i++)
count[a[i]]=count[a[i]]+1;
//此階段count記錄與a[i]等值的元素個數
for (int k = 1; k < n; k++)
count[k]=count[k]+count[k-1];
//此階段count記錄小於等於a[i]的元素個數
int[] sorted = new int[n]; // sorted是完成排序輸出的陣列
for (int i = n-1; i >= 0; i--)
{
count[a[i]]=count[a[i]]-1;
sorted[count[a[i]]]=a[i];
}
System.arraycopy(sorted, 0, a, 0, n);
}
public static void main(String[] args) {
testCountSort CSort = new testCountSort();
int[] a = MyArrays.randomInts(10,10);
System.out.print("輸入的陣列: ");
MyArrays.print(a);
System.out.println("是否已排序: " + MyArrays.isSorted(a));
CSort.sort(a);
System.out.print("排序後的輸出: ");
MyArrays.print(a);
System.out.println("是否已排序: " + MyArrays.isSorted(a));
}
}
8-6-2 二分搜尋法 (binary search)
認識「二分搜尋」(Binary search): 假如資料本身是經過排序的,在搜尋時可以利用二分的方法,每次都把陣列分成兩半。 然後從其中的一半繼續搜尋。 這種方法叫做「二分搜尋」(Binary search)。
二分搜尋的例子/二分搜尋的實例
二分搜尋法的實作
public class BinarySearch
{// 利用遞迴的方法來進行二分搜尋(binary search)
public static int binSearch(int [] a, int DataToSearch)
{
return binSearch(a, DataToSearch, 0, a.length -1);
}
private static int binSearch(int [] ArrayToSearch, int DataToSearch, int low, int high)
{
if (low > high)
return -1;
int mid = (low + high) / 2;
if(ArrayToSearch[mid]<DataToSearch)
return binSearch(ArrayToSearch, DataToSearch, mid + 1, high);
else if( ArrayToSearch[mid]>DataToSearch)
return binSearch( ArrayToSearch, DataToSearch, low, mid - 1);
else
return mid;
}
public void insertionSort( int[ ] a ) {
int i, j, tmp;
for( i = 1; i < a.length; i++ ) {
tmp = a[ i ];
for( j = i; j > 0 && (a[ j - 1 ] >= tmp); j-- ) {
a[ j ] = a[ j - 1 ];
}
a[j] = tmp;
}
}
public static void main(String [] args)
{
// 建立搜尋的陣列資料
int[] a = MyArrays.randomInts(10,20);
System.out.println("搜尋的陣列:");
MyArrays.print(a);
BinarySearch s=new BinarySearch();
s.insertionSort(a); // 搜尋前先進行排序
System.out.println("排序以後的陣列:");
MyArrays.print(a);
int r=s.binSearch(a,7);
if (r==-1)
System.out.println("搜尋失敗!"+r);
else
System.out.println("在陣列中搜尋到7!索引位置為:"+r);
}
}
字體：小 中 大
