第2章 陣列結構 資料結構設計與C++程式應用

Presentation on theme: "第2章 陣列結構 資料結構設計與C++程式應用"— Presentation transcript:

1 第2章 陣列結構 資料結構設計與C++程式應用
Fundamentals of Data Structures and Their Applications Using C++ 第2章 陣列結構 資料結構設計與C++程式應用 版權所有 禁止重製

2 陣列的宣告 資料型態 陣列名稱[陣列大小][陣列大小]… [陣列大小];
資料型態 陣列名稱[陣列大小][陣列大小]… [陣列大小] = {初值}; int X[10] = {73, 65, 52, 24, 83, 17, 35, 96, 41, 9};

3 陣列的宣告 int Y[2][3] = { {1,2,3}, // 設定第0列初值 {4,5,6}, // 設定第1列初值 };

4 陣列的表示法 一維陣列 A[1]，A[2]，…，A[n] = α+(i-1)S 。 α為陣列A的起始位置，而S為陣列元素所佔之空間大小。
LOC(ai ) = A的起始位址 + ai的索引位移 = α+(i-1)S 。 α為陣列A的起始位置，而S為陣列元素所佔之空間大小。 [周清江註：n 個元素的一維陣列 應該是 A[0], A[1], … A[n-1] = α+(i)S 重點在了解記憶體的排列，以下 2 維, 3 維, … 請大家 自己調整]

5 陣列的表示法 二維陣列 B[m][n] 【以列為主 (Row Major) 】
LOC(bij) = α + (i-1)nS + (j-1)S。 【以行為主 (Column Major) 】 LOC(bij) = α + (j-1)mS + (i-1)S。 α為陣列B的起始位置，而S為陣列元素所佔之空間大小。

6 陣列的表示法 三維陣列 C[m][n][o] 【以列為主 (Row Major) 】
LOC(cijk) = α + (i-1)noS + n(j-1)oS + (k-1)S。 【以行為主 (Column Major) 】 LOC(cijk) = α + (k-1)mnS + (j-1)mS + (i-1)S。

7 陣列的表示法 N維陣列 K[u1][u2]...[un] 【以列為主 (Row Major) 】
LOC( ) = α + (i1-1)u2u3…un S + (i2-1)u3u4…un S + (i3-1)u4u5…un S + … + (in-1-1)un S + (in-1) S 【以行為主 (Column Major) 】 LOC( ) = α + (in -1)un-1un-2…u1 S + (in-1-1)un-2un-3…u1 S + (in-2-1)un-3 un-4 …u1 S + (i2 -1)u1 S + (i1 -1)S

8 一維陣列的應用 排序 挑選式排序法

9 一維陣列的應用 排序 氣泡浮昇排序法

10 一維陣列的應用 排序 氣泡浮昇排序法

11 一維陣列的應用 搜尋 循序搜尋法 以循序搜尋法搜尋鍵值309之過程

12 一維陣列的應用 搜尋 二元搜尋法

13 一維陣列的應用 標記(Marking) 計數(Counting) 暫存(Temporary Store) 取代(Substitution)
索引(Indexing)

14 二維陣列的應用 矩陣乘積

15 二維陣列的應用 矩陣乘積

16 二維陣列的應用 矩陣轉置 B[j][i]=A[i][j] 矩陣A及其轉置矩陣B

17 二維陣列的應用 反射矩陣 矩陣A及其反射矩陣B

18 二維陣列的應用 稀疏矩陣(Sparse Matrix) 原矩陣為 8*8，共有 9 個非 0 元素