資料結構與演算法 第二章　陣列.

Presentation on theme: "資料結構與演算法 第二章　陣列."— Presentation transcript:

1 資料結構與演算法 第二章　陣列

2 目錄 2.1　陣列的宣告與使用 2.2　陣列的運算 2.3　陣列在記憶體中的位置

3 陣列的抽象定義是一組具有相同資料型態 (data type) 的元素，所組成的有序集合 (ordered set)，通常儲存在一塊連續的記憶體上。
陣列的應用技巧可開出善用陣列資料結構之門。

4 陣列在實體記憶空間中配置的關係可引領各位瞭解陣列資料結構如何存放在電腦中，以及程式語言、編譯器如何運作，方使陣列得以有效率地為吾人所用。

5 2.1 陣列的宣告與使用 任何資料結構的引用，皆需透過程式語言先行宣告，陣列的宣告必須包含三項要素： (1)陣列的名稱； (2)陣列的大小；
2.1　陣列的宣告與使用 任何資料結構的引用，皆需透過程式語言先行宣告，陣列的宣告必須包含三項要素： (1)陣列的名稱； (2)陣列的大小； (3)陣列中元素的資料型態。

6 程式2-1陣列內元素值的指定(assignment)
1 main() 2 { int list[5]; 3 int i; 4 for (i=0 ; i<5 ; i++) list[i]=i+1; 5 } //list為一整數陣列，共有5個元素。 陣列list 的邏輯圖示 list[0] 1 list[1] 2 list[2] 3 list[3] 4 list[4] 5

7 程式2-2陣列元素的指定與陣列對應元素相加 #define size=5 // 利用常數定義 main(){
// 宣告 陣列A 陣列B 陣列C int A[size],B[size],C[size]; int i; // 設定 陣列A 與 陣列B 的值 for (i=0; i<size; i++){ A[i]=i+1; B[size-i-1]= A[i]; } // 陣列C = 陣列A * 陣列B for (i=0; i<size; i++) C[i]= A[i]*B[i]; 陣列A, B和C 的邏輯圖示 A[0] 1 B[0] 5 C[0] 5 A[1] 2 B[1] 4 C[1] 8 A[2] 3 B[2] 3 C[2] 9 A[3] 4 B[3] 2 C[3] 8 A[4] 5 B[4] 1 C[4] 5 (a) (b) (c)

8 2.2 陣列的運算 2.2.1 挑選排序法 2.2.2 二元搜尋法 2.2.3 矩陣的運算 2.2.4 魔術方塊

9 2.2.1 挑選排序法 (Selection sort)
思考與探索： 欲將整數由小至大排序，可把數字小者放在左邊，數字大者放在右邊，… 若所有資料共計n個，則會執行n次挑出最小的運算，其第 i 次的運算，即為挑出未排序資料中最小者，其結果做為第i個資料。

10 2.2.1 挑選排序法 (Selection sort)
11, 7, 14, 1, 5, 9, 10 1, 7, 14, 11, 5, 9, 10 1, 5, 14, 11, 7, 9, 10 1, 5, 7, 11, 14, 9, 10 1, 5, 7, 9, 14, 11, 10 1, 5, 7, 9, 10, 11, 14 Input Output

11 2.2.1 挑選排序法 (Selection sort)演算法
輸入：data[0], data[1], data[2], …, data[n-1]，共 n 筆整數資料 輸出：data[0], data[1],…, data[n-1]；其中 若i<j，則data[i]data[j]，1i,jn 方法： (用虛擬碼Pseudo code表示) for (i=0; i<n; i++) { 挑出data[i]至data[n-1]中最小者：data[min] 將data[i] 和 data[min] 對調 }

12 2.2.1 挑選排序法 (Selection sort)程式
void SelectionSort(int data[], int n) { int i, j; int min, temp; for (i=0; i<n; i++) { // 挑出data[i]至data[n-1]中最小者：data[min] min = i; for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; // 將data[i] 和 data[min] 對調 temp = data[i]; data[i] = data[min]; data[min] = temp; } swap(&data[i], &data[min]);

13 2.2.1 挑選排序法 (程式 2-3) 函數與參數傳遞 void swap(int *x, int *y) { int temp;
2.2.1　挑選排序法 (程式 2-3) 函數與參數傳遞 void swap(int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } void SelectionSort(int data[], int n) { int i, j; int min; for (i=0; i<n-1; i++){ // 挑出data[i]至data[n-1]中最小者：data[min] min = i; for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; // 將data[i] 和 data[min] 對調 swap(&data[i], &data[min]);

14 參數傳遞的說明 (a) 傳位法 以*x, *y記載傳入參數data[i], data[min]的位址
void swap(int *x, int *y) swap(&data[i], &data[min]); 將data[i], data[min]的位址傳入程序swap中 宣告 呼叫 (b) 傳位與傳值法 以data[]記載傳入參數陣列data的位址、n記載傳入參數n值 void SelectionSort(int data[],int n) SelectionSort(data, n); 將陣列data的位址，n的值傳入程序SelectionSort中 宣告 呼叫 在這個例子中，n用傳位法傳遞、甚至data和n都用全域變數(global variable)，也不致出錯；但用傳值法可增加程式的可讀性，對程序的可再使用也較明確。

15 2.2.2 二元搜尋法 搜尋資料 資料沒有結構 11, 7, 14, 1, 5, 9, 10, 2, 8, 3, 6, 23, 16, 12, 4 搜尋 data=6 資料有由小到大的順序結構 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 23 1, 2, 3, 4, 5, 6, 7 5, 6, 7

16 演算法2-1 線性搜尋法 線性搜尋法 (linear seach)
這個方法是從第一筆資料開始，依序一一比對，直到找到所要的資料，或找不到為止。 自i=0起，核對data[i]是否與x相等，若相等，則演算法傳出位置i後停止；若不相等，則換下一筆，繼續比對；若陣列所有資料皆無x，則傳回-1，知會呼叫程序：x不在陣列data中。

17 演算法2-1線性搜尋法： Input: data[0].data[1]....data[n-1]
Output:資料x所在的位置；或0(x不在陣列data中) //逐一比對，直到找到所要的資料，或找不到為止。 for (i=0; i<n; i++) if (x==data[i]) return(i); retrun(-1);

18 二元搜尋法 但若資料已經過排序（由小到大），則可以用二元搜尋法 (binary search)，來提高搜尋的速率 其基本想法如下：
檢查數列中間之資料是否為所求？ 若是即找到了 否則再看 若中間資料大於x，對前半部數列進行二元搜尋 若中間資料小於x，對後半部數列進行二元搜尋

19 演算法2-2 二元搜尋法 Input:已由小至大排序的陣列data及欲搜尋的資料x，最小位置(lower)，最大位置(upper)
Output:若x在data陣列中，則輸出x所在位置之註標，否則輸出-1 重覆下列步驟至沒有資料為止： 1. 計算中間位置 mid 2. 檢查data[mid]與x是否相等，若二者相等， 則表示在位置mid中已找到x了，遂傳回mid； 3.若 data[mid] < x， x只可能在data[mid+1]~data[upper]之間 否則 data[mid] > x x只可能在data[lower]~data[mid-1]之間

20 演算法2-2 二元搜尋法 (迴圈程式) int Bi_Search(int data[], int x, int lower, int upper) { int mid; // 重覆下列步驟至沒有資料為止： while (lower<=upper){ // 1. 計算中間位置 mid mid = (lower+upper)/2; // 2. 檢查data[mid]與x是否相等，若二者相等， // 則表示在位置mid中已找到x了，遂傳回mid； if (data[mid] == x) return(mid); else //3. 若 data[mid]< x，x只可能在data[mid+1]~data[upper] if(data[mid] < x) lower = mid+1; // 否則 data[mid]> x，x只可能在data[lower]~data[mid-1]之間 upper = mid-1; } return -1; // 若沒有資料

21 程式2-4 二元搜尋法—遞迴呼叫 int BinarySearch(int data[], int x, int lower, int upper) { int mid; // 若有資料： if (lower <= upper){ // 1. 計算中間位置 mid mid = (lower+upper)/2; // 2. 檢查data[mid]與x是否相等，若二者相等， // 則表示在位置mid中已找到x了，遂傳回mid； if (data[mid] == x) return(mid); //3. 若 data[mid]< x，x只可能在data[mid+1]~data[upper]之間 if (data[mid] < x) return BinarySearch(data,x,mid+1,upper); // 否則 data[mid]> x，x只可能在data[lower]~data[mid-1]之間 else return BinarySearch(data,x,lower,mid-1); } return –1; // 若沒有資料

22 2.2.3 矩陣的運算 矩陣 (或行列式) 是一種數學上的重要結構，恰可用二維陣列表示之。
若矩陣A是一個34的整數矩陣，我們可以C語言宣告矩陣A int A[3][4]; 此二維整數陣列A共有3列4行，而A[i][j]即對應了矩陣A之元素Aij。

23 二維陣列內元素值的指定

24 轉置矩陣AT

25 矩陣轉置 演算法的時間複雜度為O(mn)。 演算法2-3矩陣轉置 輸入：mn矩陣A 輸出：矩陣B，B=AT
1 將二維矩陣A的元素載入二維陣列A中：A[i][j]= aij 2 for (i=0; i<m; i++) 3 for (j=0; j<n; j++) 4 B[i][j]=A[j][i]; 演算法的時間複雜度為O(mn)。

26 矩陣相加

27 矩陣相加 演算法2-4矩陣相加 演算法的時間複雜度為O(mn)。 輸入：mn矩陣A 輸出：矩陣C，C=A+B
1 將二維矩陣A,B的元素載入二維陣列A,B中：A[i][j]=aij；B[i][j]=bij 2 for (i=0; i<m; i++) 3 for (j=0; j<n; j++) 4 C[i][j]=A[i][j]+B[i][j]; 演算法的時間複雜度為O(mn)。

28 矩陣相乘

29 演算法2-5矩陣相乘 演算法的時間複雜度為O(mnp) 輸入：mn矩陣A，np矩陣B 輸出：矩陣C，C=AB
1 將二維矩陣A,B的元素載入二維陣列A,B中：A[i][j]=aij;B[i][j]=bij; 2 for (i=0; i<m; i++) 3 for (j=0; j<p; j++) 4 { C[i][j] = 0; 5 for (k=0; k<n; k++) 6 C[i][j] += A[i][k]*B[k][j]; 7 } 演算法的時間複雜度為O(mnp)

30 2.2.4 魔術方塊 魔術方塊：是在一nn的矩陣中，每一格內放入一個1~n2的整數，使每一行、每一列及對角線的和都相等。 15 8 1
2.2.4　魔術方塊 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 6 1 8 7 5 3 2 9 4 魔術方塊：是在一nn的矩陣中，每一格內放入一個1~n2的整數，使每一行、每一列及對角線的和都相等。

31 2.2.4　魔術方塊 15 8 1 24 17 16 14 7 5 23 6 1 8 22 20 13 6 4 7 5 3 3 21 19 12 10 9 4 2 9 2 25 18 11 當n是奇數時，H. Coxeter觀察到了產生魔術方塊的規則： 填在第1列中間； 將方塊想成上下、左右、對角相接的圓球，往左上角填入下一個數字；若左上角已遭其它數字佔用，則填在目前方格的下方。

32 魔術方塊 演算法 輸入： 二維矩陣, 魔術方陣之大小n 輸出： 魔術方陣 步驟： 1. 檢查 n 是否太大 2. 檢查 n 是否為奇數
3. 設定方陣之初始值為0 4. 設定第一列的中間格為1 5. 從 i= 2 到 n*n 為止 若左上方格內沒有資料則將 i 放入左上方格內 否則將i放入下方格內

33 程式2-5 魔術方塊 #define MaxSize 21
void MagicSquare(int square[MaxSize][MaxSize], int n) { int i, j, k, l, data; // 1. 檢查 n 是否太大 　　if ((n>MaxSize)||(n<1)) 　　{ cerr<<”輸入方塊過大，不予處理。”<<endl; return; } // 2. 檢查 n 是否為奇數 else if ((n%2)==0) 　 { cerr<<”輸入方塊邊長為偶數，不予處理。”<<endl; return; } // 3. 設定方陣之初始值為0 　　for (i=0; i<n; i++) for (j=0; j<n;j++) square[i][j] = 0; // 4. 設定第一列的中間格為1 i = 0; j = (n-1)/2; square[i][j] = 1;

34 程式2-5魔術方塊 (續) // 5. 從 data= 2 到 n*n 為止 data = 2;
while (data <= n*n){ k = (i-1<0) ? n-1 : i-1; // 檢查上列的邊界 l = (j-1<0) ? n-1 : j-1; // 檢查左行的邊界 // 若左上方格內沒有資料則將 data 放入左上方格內 if (square[k][l] <= 0) {i = k; j = l;} // 否則將data放入下方格內 else { i =(i+1)%n; } square[i][j] = data++ ; }

35 魔術方塊 測試程式 // 魔術方塊 // 輸出結果 #define MaxSize 21 main() {
魔術方塊 測試程式 #define MaxSize 21 main() { int m[MaxSize][MaxSize]; int n,i,j; n=5; // 魔術方塊 MagicSquare(m, n); // 輸出結果 cout<<n<<””<<n<<”的魔術方塊”<<endl; for (i=0; i<n; i++){ for (j=0; j<n; j++) cout<<m[i][j]<<” ”; cout<<endl; }

36 2.3 陣列在記憶體中的位置 2.3.1 一維陣列 2.3.2 二維陣列 2.3.3 三維陣列與高維陣列

37 2.3.1 一維陣列 A[i]在記憶體中的位址為+il
若一維陣列A在記憶體中的起點為，而且任一元素佔用l位元組，若有n個元素，則陣列A在記憶體中的配置位置，可描繪如圖2-7。其中A[i]在記憶體中的位址為+il： A[i]在記憶體中的位址為+il 陣列的存取時間與元素存放的位置無關，亦即編譯器可在相同的時間內，決定任何位置陣列元素的位址，其存入（或取出）的時間皆為一樣。

38 現今大多的程式語言皆依以列為優先的原則設計。
2.3.2 二維陣列 當二維陣列空間轉為一維記憶體空間時，可採以列為優先 (row major) 或採以行為優先 (column major) 的配置方式。 以列為優先的次序，指的是先依列由小到大的順序，再依行由小到大的順序存放資料，即第0列所有資料依行序存妥後，再將第1列所有資料依行序存妥…，依此類推。 行為優先的次序，則先依行由小到大的順序，再依列由小到大的順序存放陣列的資料。 　 現今大多的程式語言皆依以列為優先的原則設計。

39 二維陣列 以列為優先 以行為優先

40 二維陣列的實際記憶體配置

41 2.3.3 三維陣列與高維陣列 在電腦的內部運作中，編譯器可先行找出陣列宣告的上下限值：u1, u2, … , un，然後利用n-2個乘法，求出上式的w1, w2, … , wn-1 (wn=1，不必求之)，先行存下。而計算A[i1][i2]…[in]的位址時，即可利用上式，以n個乘法和n+1個加法求得其位址值。 也因而陣列是一個隨機(random access)存取的結構，其元素的存取與存放的位置無關。

42 三維陣列中元素的定址關係

43 作 業 習題 2-3 2-10 2-11