資料結構 第2章　陣列.

Presentation on theme: "資料結構 第2章　陣列."— Presentation transcript:

1 資料結構 第2章　陣列

2 2-1　認識陣列 2-1-1　一維陣列 int A[3] = {10, 20, 30};

3 2-1-2　二維陣列

4 2-1-3　三維陣列

5 2-2 陣列的運算 一維陣列常見的運算 建立 (create) 讀取 (retrieve) 寫入 (store) 插入 (insert)
2-2　陣列的運算 一維陣列常見的運算 建立 (create) 讀取 (retrieve) 寫入 (store) 插入 (insert) 刪除 (delete) 複製 (copy) 搜尋 (search) 走訪 (traverse)

6 範例2.1：撰寫一個函數實作一維陣列的 [走訪] 運算並分析其時間複雜度。
array_traverse(int A[], int n) { int i; for(i = 0; i < n; i++) printf("%d\n", A[i]); } main() int A[5] = {10, 20, 30, 40, 50}; array_traverse(A, 5);

7 二維陣列常見的運算 矩陣轉置 (matrix transposition) A = B = At = 例如：

8 矩陣相加 (matrix addition)

9 矩陣相乘 (matrix multiplication)

10 範例2.4： [矩陣走訪] 撰寫一個函數印出矩陣的所有元素並分析其時間複雜度。
範例2.4： [矩陣走訪] 撰寫一個函數印出矩陣的所有元素並分析其時間複雜度。 matrix_traverse(int m, int n, int A[m][n]) { int i, j; for(i = 0; i < m; i++){ for(j = 0; j < n; j++) printf("%d ", A[i][j]); printf("\n"); } main() int A[2][3] = {{11, 12, 13}, {21, 22, 23}}; matrix_traverse(2, 3, A);

11 2-3　陣列的定址方式 一維陣列的定址方式 我們根據以列為主來討論一維陣列A[upper0] 的定址方式，假設第一個元素A[0] 的位址為α，則元素A[i] 的位址為α + i x length。

12 二維陣列的定址方式 我們根據以列為主來討論二維陣列A[upper0][upper1] 的定址方式，假設第一個元素A[0][0] 的位址為α，則元素A[i][0] 的位址為α + i x upper1 ，元素A[i][j] 的位址為α + i x upper1 + j 。

13 範例2.7：假設以C語言宣告一個浮點數陣列float A[7][8]; (已知sizeof(float) 等於4)，若元素A[3][4] 在記憶體空間的位址為100，則元素A[5][6] 的位址為何？而元素A[2][3] 的位址又為何？ 解答： A[5][6] 的位址 = A[3][4] 的位址 + 位移量 = ((5 x 8 + 6) - (3 x 8 + 4)) x = 172 A[2][3] 的位址 = A[3][4] 的位址 + 位移量 = ((2 x 8 + 3) - (3 x 8 + 4)) x = 64

14 三維陣列的定址方式 我們根據以列為主來討論三維陣列A[upper0][upper1][upper2] 的定址方式，假設第一個元素A[0][0][0] 的位址為α，則元素A[i][0][0] 的位址為α + i x upper1 x upper2，元素A[i][j][0] 的位址為α + i x upper1 x upper2 + j x upper2，元素A[i][j][k] 的位址為α + i x upper1 x upper2 + j x upper2 + k 。

15 範例2.10：假設以C語言宣告一個浮點數陣列float A[6][7][8]; (已知sizeof(float) 等於4)，若元素A[3][4][5] 在記憶體空間的位址為1000，則元素A[1][2][3] 的位址為何？ 解答： ((1 x 7 x x 8 + 3) - (3 x 7 x x 8 + 5)) x 4 = 480

16 n維陣列的定址方式 我們根據以列為主來討論n維陣列A[upper0][upper1] …[uppern-1] 的定址方式，假設第一個元素A[0][0]…[0] 的位址為α，則元素A[i0][0]…[0] 的位址為： α + i0 x upper1 x upper2 x … x uppern-1 元素A[i0][i1][0]…[0] 的位址為： + i1 x upper2 x upper3 x … x uppern-1 元素A[i0][i1][i2]…[in-1] 的位址為：

17 2-4 陣列的應用 2-4-1 多項式 陣列可以用來存放多項式 ，方式如下：
2-4　陣列的應用 2-4-1　多項式 陣列可以用來存放多項式 ，方式如下： 使用陣列Polynomial存放多項式cnXn + cn-1Xn-1 +… + c1X1 + c0X0，Polynomial[] = {n, cn, cn-1, …, c1, c0}，以8X4 - 6X2 + 3X5 + 5為例，Polynomial[] = {5, 3, 8, 0, -6, 0, 5} 使用陣列Polynomial存放多項式cm-1Xem-1 + … + c1Xe1 + c0Xe0，Polynomial[] = {m, cm-1, em-1, …, c1, e1, c0, e0}，以8X4 - 6X2 + 3X5 + 5為例，Polynomial[] = {4, 3, 5, 8, 4, -6, 2, 5, 0}

18 定義如下的NonZeroTerm結構表示非零項，然後定義如下的Polynomial結構表示多項式：
typedef struct{ int coef; int exp; }NonZeroTerm; #define MAX_SIZE 100 int count; NonZeroTerm terms[MAX_SIZE]; }Polynomial;

19 以8X4 - 6X2 + 3X5 + 5為例，存放結果如下： count 4 terms [0] [1] [2] [3] coef exp
-6 2

20 2-4-2　稀疏矩陣 除了多項式之外，陣列也經常用來存放稀疏矩陣 (sparse matrix)，也就是非零元素相對較少的矩陣，例如：

21 我們可以定義如下結構存放稀疏矩陣的非零項：
#define MAX_SIZE 100 typedef struct{ int row; int col; int value; }SparseTerm; 宣告一個陣列變數A代表前面的稀疏矩陣： SparseTerm A[MAX_SIZE];

22 A = A   [0] [1] [2] [3] [4] [5] [6] row 4 1 2 3 col 5 value 6

23 範例2.13：[稀疏矩陣轉置] 使用第2-4-2節定義的SparseTerm結構存放稀疏矩陣的非零項，然後撰寫一個函數實作稀疏矩陣轉置運算並分析其時間複雜度，下面是一個例子。

24 範例2.14：[下三角矩陣] 假設以一維陣列B來存放n×n的下三角矩陣A，即A[0][0] 存放在B[0]、A[1][0] 存放在B[1]、A[1][1] 存放在B[2]…餘此類推，試問，陣列B的長度為何？又A[i][j] 是存放在陣列B的哪個位置？

25 2-5 字串 對C語言來說，字串 (string) 是以空字元 ‘\0’ 結尾的一串字元，因此是以字元陣列的形式來表示字串，例如：
2-5　字串 對C語言來說，字串 (string) 是以空字元 ‘\0’ 結尾的一串字元，因此是以字元陣列的形式來表示字串，例如： char name1[] = "Jean Chen"; char name2[10] = "Mary"; char name3[5] = {'J', 'o', 'e', '\0'};

26 字串常見的運算 字串複製：例如strcpy(str, "Happy New Year");
字串比較 ：例如printf("%d", strcmp(str1, str2)); 字串轉換 ：例如strupr("new");、strlwr(“NEW") ; 字串搜尋 ：例如strstr(char *str1, char *str2) 函數會傳回一個指標，指向str2字串第一次出現在str1字串內的位置，若str1字串不包含str2字串，則傳回NULL 。

27 範例2.15：[字串長度] 撰寫一個函數模擬C語言的strlen()，以計算字串包含幾個字元。
解答： int StrLength(char str[]) { int i = 0; while(str[i] != '\0') i++; return i; }

28 範例2.17：[模式比對] 撰寫一個函數在str字串內比對另一個pat字串，若pat字串在str字串內，就傳回其起始位置，否則傳回 -1。
我們可以使用str[] = "yxyxxxyyxxx" 和pat[] = "yyx" 來模擬比對的過程：

29 2-6 結構 巢狀結構，例如： typedef struct{ int year; int month; 配置記憶體給結構：
2-6　結構 巢狀結構，例如： typedef struct{ int year; int month; int day; }DATE; char name[50]; DATE birthday; }PERSON; 配置記憶體給結構： PERSON employee; 存取結構的成員： employee.name = "Mary Wang"; employee.birthday.year = 1995; employee.birthday.month = 2; employee.birthday.day = 14;