Presentation is loading. Please wait.

Presentation is loading. Please wait.

資料結構 Data Structure.

Similar presentations


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


Download ppt "資料結構 Data Structure."

Similar presentations


Ads by Google