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

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

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

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

3 陣列的抽象定義是一組具有相同資料型態 (data type) 的元素，所組成的有序集合 (ordered set)，通常儲存在一塊連續的記憶體上 。
陣列的應用技巧可開出善用陣列資料結構之門。 陣列在實體記憶空間中配置的關係可引領各位瞭解陣列資料結構如何存放在電腦中，以及程式語言、編譯器如何運作，方使陣列得以有效率地為吾人所用。

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

5 程式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

6 程式2-2陣列元素的指定與陣列對應元素相加 1 #define size=5 2 main()
3 { int A[size],B[size],C[size]; 4 int i; 5 for (i=0; i<size; i++) 6 { A[i]=i+1; 7 B[size-i-1]= A[i]; 8 } 9 for (i=0; i<size; i++) C[i]= A[i]*B[i]; 11 } 利用常數定義 陣列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) 註標是可以先行計算的

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

8 2.2.1 挑選排序法 程序swap的宣告則在第1~6行。一樣的道理，所以在第14行欲執行挑選排序，可呼叫 程式2-3挑選排序法
2.2.1　挑選排序法 程式2-3挑選排序法 1 void swap(int *x, int *y) 2 { int temp; 3 temp = *x; 4 *x = *y; 5 *y = temp; 6 } 7 void SelectionSort(int data[], int n) 8 { int i, j; int min, temp; for (i=0; i<n-1; i++) { min = i; 12 for (j=i+1; j<n; j++) if (data[j]<data[min]) min = j; 14 swap(&data[i], &data[min]); } 16 } 程序swap的宣告則在第1~6行。一樣的道理，所以在第14行欲執行挑選排序，可呼叫 SelectionSort(data, n);

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

10 ：當時最小元素的位置 x ：x 為已排序完成的資料
挑選排序法的執行過程 欲對下列6筆資料：9、8、4、7、2、3，進行挑選排序，結果如下：  每次挑出排序資料中最小者 原資料 i=0 i=1 i=2 i=3 i=4 排序結果 Data[0]   Data[1] Data[2]  Data[3]  Data[4] Data[5] 3   ：當時最小元素的位置 x ：x 為已排序完成的資料 藉著迴圈和陣列，適當更動迴圈控制變數做為陣列的註標，即可透過比較資料大小、調換資料所在位置，完成排序的目的。

11 2.2.2 二元搜尋法 直覺的線性搜尋法 (linear seach) — 這個方法是從第一筆資料開始，依序一一比對，直到找到所要的資料，或找不到為止。 但若資料已經過排序（由小到大），則可以用二元搜尋法 (binary search)，來提高搜尋的速率，其基本想法如下： ．檢查數列中間之資料是否為所求？若是即找到了， 否則再看 　 ．若中間資料大於x，對前半部數列進行二元搜尋 ．若中間資料小於x，對後半部數列進行二元搜尋

12 演算法2-1線性搜尋法： Input: data[0].data[1]....data[n-1]
Output:資料x所在的位置(註標)或0(x不在陣列data中) 1 for (i=0; i<n; i++) 2 if (x==data[i]) return(i); 3 retrun(-1); 自i=0起，核對data[i]是否與x相等，若相等，則演算法傳出位置i後停止；若不相等，則換下一筆，繼續比對；若陣列所有資料皆無x，則傳回-1，知會呼叫程序：x不在陣列data中。

13 若data[mid+1]~data[upper]之間，遂把lower調至mid+1 ；
演算法2-2二元搜尋法： Input:已由小至大排序的陣列data及欲搜尋的資料x Output:若x在data陣列中，則輸出x所在位置之註標，否則輸出-1 1 lower=0; upper=n-1; 2 while (lower<=upper) 3 { mid = (left+right)/2; 4 if (data[mid] == x) 5 return(mid); 6 else 7 if(data[mid] < x) left = mid+1; 9 else upper = mid-1; 11 } 12 return -1; 檢查data[mid]與x是否相等，若二者相等，則表示在位置mid中已找到x了，遂傳回mid； 若data[mid+1]~data[upper]之間，遂把lower調至mid+1 ； // data[mid]>x) // data[mid]x) 執行時表示data[mid]大於x，即x只可能在data[lower]~data[mid-1]之間，於是把upper調成mid-1。

14 程式2-4二元搜尋法—遞迴呼叫 1 int BinarySearch(int data[], int x, int left, int right) 2 { int middle; 3 if (left <= right) 4 { mid = (left+right)/2; 5 if (data[mid] == x) return(mid); if (data[mid] < x) BinarySearch(data[],x,mid+1,right); else BinarySearch(data[], x, mid+1, right); 11 } 12 return –1; 13 }

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

16 矩陣轉置及相加 演算法的時間複雜度為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)。

17 矩陣轉置及相加(續) 演算法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[j][i]; 演算法的時間複雜度為O(mn)。

18 演算法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)

19 2.2.4 魔術方塊 當n是奇數時，H. Coxeter觀察到了產生魔術方塊的規則： 15 8 1 24 17
2.2.4　魔術方塊   (a)3＊ (b)5＊5 當n是奇數時，H. Coxeter觀察到了產生魔術方塊的規則： 填在第1列中間； 將方塊想成上下、左右、對角相接的圓球，往左上角填入下一個數字；若左上角已遭其它數字佔用，則填在目前方格的下方。

20 程式2-5魔術方塊 1 #define MaxSize = 21; 2 int square[MaxSize][MaxSize];
3 void MagicSquare(int n) 4 { int i, j, k, l, data; 5 　　if ((n>MaxSize)||(n<1)) 6 　　{ cerr<<”輸入方塊過大，不予處理。”<<endl; return; } 7 　　else if ((n%2)==0) 8 　　{ cerr<<”輸入方塊邊長為偶數，不予處理。”<<endl; return; } 9 　　for (i=j=0; i<n, j<n; i++, j++) square[o][j] = 0; 10 i = 0; j = (n-1)/2; 11 square[i][j] = 1; 12 data = 2;

21 程式2-5魔術方塊 (續) 13 while (data < n*n)
14 { k = (i-1<0) ? n-1 : i-1; l = (j-1<0) ? n-1 : j-1; if (square[k][l] > 0) i = (i+1)%n; else { i = k; j = l; } square[i][j] = data++; 19 } 20 cout<<n<<””<<n<<”的魔術方塊”<<endl; 21 for (i=0; i<n; i++) 22 { for (j=0; j<n; j++) 23 out<<squarepi][j]<<” ”; 24 cout<<endl; 25 } 26 }

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

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

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

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

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

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