資料結構 Data Structure.

Presentation on theme: "資料結構 Data Structure."— Presentation transcript:

1 資料結構 Data Structure

2 第2章 陣列與結構 （Arrays and Structures）
2-2 陣列表示法 2-3 C語言的結構 2-4 陣列的應用 - 稀疏矩陣表示法

3 2-1 C語言的陣列 2-1-1 一維陣列 2-1-2 一維陣列的存取與走訪 2-1-3 二維陣列 2-1-4 二維陣列的存取與走訪

4 2-1 C語言的陣列 陣列(Array)是C語言延伸資料型態提供的資料結構，屬於一種循序性的資料結構。
日常生活最常見的範例是一排信箱，郵差依信箱號碼投遞郵件，住戶依信箱號碼取出郵件，信箱儲存的信件就是儲存在陣列的元素值，信箱號碼是陣列索引值（Index），我們可以隨機存取每一個元素，這是陣列的特性。

5 2-1-1 一維陣列-宣告 「一維陣列」（One-dimensional Array） 在C語言陣列變數的宣告語法，如下所示：
如同前述單排信箱的資料結構，只是將相同資料型態的變數集合起來，然後使用一個變數名稱來代表，以索引值存取指定陣列元素的值。 在C語言陣列變數的宣告語法，如下所示： 資料型態 變數名稱[長度]; 上述陣列宣告的資料型態可以是基本資料型態：整數、浮點數和字元，也可以是延伸資料型態的結構。

6 2-1-1 一維陣列-範例 例如：宣告整數int的一維陣列scores[]，如下所示： int scores[5];
上述程式碼宣告大小為5的一維陣列，資料型態是int整數，陣列名稱是scores，C語言的陣列索引值是從0開始。

7 2-1-1 一維陣列-記憶體圖例 陣列scores[]的記憶體圖例，
m表示陣列第1個元素的記憶體位址scores[0]，這是一塊連續的記憶體空間，如下圖所示：

8 2-1-2 一維陣列的存取與走訪-存取 一維陣列可以隨機存取元素值，只需花費固定時間就可以存取指定索引的元素值。
例如：大小10的整數陣列scores[]儲存學生的成績資料，陣列索引值是學生學號，我們可以很容易查詢學生成績或更改學生的成績資料，如下圖所示：

9 2-1-2 一維陣列的存取與走訪-走訪 陣列走訪是以循序方式移動陣列索引值，然後處理每一個元素，也就是以地毯方式依序存取陣列全部的元素，
在C語言通常是使用迴圈來走訪陣列，如下所示： for ( i = 0; i < 10; i++ ) printf("%d:%d ", i, scores[i]); 上述for迴圈可以走訪整個scores[]陣列的元素。

10 2-1-3 二維陣列-說明 「二維陣列」（Two-dimensional Array）屬於一維陣列的擴充，
如果將一維陣列視為一度空間，二維陣列就是一個二度空間的平面。 在日常生活的二維陣列非常常見，只要屬於平面的表格，大都可以轉換成二維陣列來儲存資料。

11 2-1-3 二維陣列-圖例1

12 2-1-3 二維陣列-圖例2

13 2-1-3 二維陣列-宣告 宣告一個整數int的二維陣列courses[][]儲存功課表，其大小是6 X 5，6列和5欄（或稱行）如下所示：
上述二維陣列的元素值是整數的課程代碼，如果這節沒課，其值為0。

14 2-1-3 二維陣列-記憶體圖例

15 2-1-3 二維陣列-索引 二維陣列各元素的陣列索引值，如下圖所示：

16 2-1-4 二維陣列的存取與走訪 二維陣列如同一維陣列一般，只需知道存取元素的欄（或稱行）與列值，就可以在固定時間存取其元素值。
同樣的，二維陣列的走訪也一樣可以使用二層巢狀迴圈來完成，如下所示： for ( i = 0; i < 6; i++ ) 先決定列 for ( j = 0; j < 5; j++ ) 再決定欄 if ( courses[i][j] != 0 ) sum++; 上述程式碼使用二層for迴圈來走訪二維陣列courses[][]。

17 2-2 陣列表示法 2-2-1 以列為主的表示方法 2-2-2 以欄為主的表示方法 2-2-3 指標陣列表示法

18 2-2 陣列表示法-種類 陣列表示法是電腦內部記憶體儲存陣列元素的方式， 常見的方法有三種，如下所示：
一維陣列是一塊連續的記憶體空間，二維以上的陣列因為擁有多列和多欄，所以這塊記憶體的儲存方式就有不同的順序，稱為陣列表示法， 常見的方法有三種，如下所示： 以列為主的表示方法。 以欄為主的表示方法。 指標陣列表示法。

19 2-2 陣列表示法-範例 二維陣列的圖例，如下圖所示：

20 2-2-1 以列為主的表示方法-說明 二維陣列一共有6 X 5 = 30個元素，可以宣告一個大小為30的一維陣列來儲存二維陣列的所有元素，
一維陣列classes[]的宣告，如下所示： int classes[30]; 二維陣列a的大小是rows X columns，二維陣列的元素a(row_num,column_num)使用以列為主的一維陣列表示法，其索引值公式如下所示： row_num * columns + column_num

21 2-2-1 以列為主的表示方法-範例 rows = 6，columns = 5，陣列元素(1, 0)對應的索引值，如下所示：
(1, 0) = 1 * = 5 二維陣列的每一列大小是5，即columns。 row_num是陣列的第row_num + 1列，column_num是第column_num + 1欄。 所以對應一維陣列的索引值就是所在列前的總列數乘以大小columns，即((row_num+1)-1)*columns = row_num*columns再加上(column_num+1)-1欄。

22 2-2-1 以列為主的表示方法-圖例

23 2-2-2 以欄為主的表示方法-說明 二維陣列一共有6 X 5 = 30個元素，所以可以宣告一個長度為30的一維陣列來儲存二維陣列的元素，
一維陣列classes[]的宣告，如下所示： int classes[30]; 二維陣列a的大小是rows X columns，二維陣列的元素a(row_num,column_num)使用以欄為主的一維陣列表示法，其索引值公式如下所示： column_num * rows + row_num

24 2-2-2 以欄為主的表示方法-範例 rows = 6，columns = 5，陣列元素(0, 1)對應的索引值，如下所示：
(0, 1) = 1 * = 6 上述公式計算出索引值是6，也就是classes[6]。

25 2-2-2 以欄為主的表示方法-圖例

26 2-2-3 指標陣列表示法-說明 指標陣列是另一種使用一維陣列來儲存二維陣列元素的方法。
指標陣列的元素是指向另一個一維陣列data[]的索引值，data[]陣列儲存二維陣列內的每一列。 二維陣列a的尺寸是rows X columns，元素a(row_num,column_num)在指標陣列表示法的索引值公式，如下所示： pointer(row_num) + column_num 上述pointer(row_num)內容是每一列的起始座標，column_num是陣列這一列的位移值。

27 2-2-3 指標陣列表示法-圖例

28 2-3 C語言的結構 2-3-1 結構的基礎 2-3-2 宣告結構型態 2-3-3 結構陣列 2-3-4 巢狀結構
2-3-5 建立新型態typedef

29 2-3-1 結構的基礎 「結構」（Structures）是C語言的延伸資料型態，這是一種自定資料型態（User-Defined Types），可以讓程式設計者自行在程式碼定義新的資料型態。 結構是由一或多個不同資料型態（當然可以是相同資料型態）所組成的集合，然後使用一個新名稱來代表，新名稱是一個新的資料型態，可以用來宣告結構變數。 struct Point { int x; int y; };

30 2-3-2 宣告結構型態-結構宣告 在C程式宣告結構是使用struct關鍵字來定義新型態，其語法如下所示： struct 結構名稱 {
資料型態 變數1; 資料型態 變數2; …… }; 上述語法定義名為【結構名稱】的新資料型態，程式設計者可以自行替結構命名，在結構中宣告的變數稱為該結構的「成員」（Members）。 範例: struct Point { int x; int y; };

31 2-3-2 宣告結構型態-結構範例 例如：學生資料的結構student，如下所示： struct student { int id;
char name[20]; int math; int english; int computer; }; 上述結構是由學號id、學生姓名name、數學成績math、英文成績english和電腦成績computer的成員變數所組成。

32 2-3-2 宣告結構型態-結構變數 當宣告student結構後，因為它是一種自訂資料型態，所以在程式碼可以使用這個新型態來宣告變數，其語法如下所示： struct 結構名稱 變數名稱; 上述宣告使用struct關鍵字開頭加上結構名稱來宣告結構變數，以本節程式範例為例，結構變數的宣告，如下所示： struct student std1; struct student std2 = {2, "江小魚", 45, 78, 66}; 不給初始值 給初始值

33 2-3-2 宣告結構型態-結構運算 在建立好結構變數後，就可以存取結構各成員變數的值，如下所示：
std1.id = 1; strcpy(std1.name, “陳會安”); //字串拷貝 std1.math = 78; std1.english = 65; std1.computer = 90; ANSI-C語言支援結構變數的指定敘述，如下所示： struct student std3; std3 = std2;

34 2-3-3 結構陣列 「結構陣列」（Arrays of Structures）是結構資料型態的陣列。例如：test結構如下所示：
struct test { int math; int english; int computer; }; 上述結構擁有3個成員變數，因為test是一種新型態，所以可以使用此型態建立陣列，如下所示： #define NUM_STUDENTS struct test students[NUM]; //結構陣列

35 2-3-4 巢狀結構 「巢狀結構」（Nested Structures）是在宣告的結構中擁有其它結構，
例如：在student結構可以使用test結構儲存測驗成績，如下所示： struct test { int math; int english; int computer; }; struct student { int id; char name[20]; struct test score;

36 2-3-5 建立新型態typedef 在宣告結構型態後，為了方便宣告，我們可以使用一個別名來取代新的資料型態，這個別名是新增的識別字，可以用來定義全新的資料型態，其語法如下所示： typedef 資料型態 識別字; 上述識別字代表資料型態，所以可以直接使用此識別字宣告變數。 例如：程式範例的test結構可以使用typedef指令定義新識別字的型態和宣告變數，如下所示： typedef struct test score; score joe;

37 2-4 陣列的應用 - 稀疏矩陣表示法(矩陣) 「矩陣」（Matrices）類似二維陣列，一個m X n矩陣表示這個矩陣擁有m列（Rows）和n欄（Columns），或稱為列和行，4 X 3矩陣的m和n是矩陣的「維度」（Dimensions）。

38 2-4 陣列的應用 - 稀疏矩陣表示法(稀疏矩陣說明)
「稀疏矩陣」（Sparse Matrices）屬於矩陣一種非常特殊的情況，因為矩陣元素大部份元素都沒有使用，元素稀稀落落，所以稱為稀疏矩陣。 例如：50個元素的稀疏矩陣，真正使用的元素只有5個，如下圖所示：

39 2-4 陣列的應用 - 稀疏矩陣表示法(稀疏矩陣表示法)
稀疏矩陣實際儲存資料的項目很少，如果使用二維陣列來儲存稀疏矩陣，表示大部分記憶體空間都是閒置的， 為了增加記憶體的使用效率，可以採用壓縮方式儲存稀疏矩陣中只擁有值的項目，如下圖所示：

40 2-4 陣列的應用 - 稀疏矩陣表示法(標頭檔) 01: /* 程式範例: Ch2-4.h */
02: #define MAX_TERMS /* 稀疏矩陣的最大元素數 */ 03: struct Term { /* 稀疏矩陣的元素結構 */ 04: int row; /* 元素的列數 */ 05: int col; /* 元素的欄數 */ 06: int value; /* 元素的值 */ 07: }; 08: struct sMatrix { /* 稀疏矩陣的結構 */ 09: int rows; /* 矩陣的列數 */ 10: int cols; /* 矩陣的欄數 */ 11: int numOfTerms; /* 矩陣的元素數 */ 12: struct Term smArr[MAX_TERMS]; /* 壓縮陣列的宣告 */ 13: }; 14: typedef struct sMatrix Matrix; /* 建立稀疏矩陣的新型態 */ 15: Matrix m; /* 建立稀疏矩陣 */ 16: /* 抽象資料型態的操作函數宣告 */ 17: extern void createMatrix(int r,int c,int *arr); 18: extern void printMatrix();

41 矩正轉置

42