第2章 陣列與結構 (Arrays and Structures)

Slides:



Advertisements
Similar presentations
第一單元 建立java 程式.
Advertisements

陣列與清單控制項 [學生成績管理][井字遊戲]
08 CSS 基本語法 8-1 CSS 的演進 8-2 CSS 樣式規則與選擇器 8-3 連結HTML 文件與CSS 樣式表
陣列 Array chapter 3 德明科技大學資訊科技系.
陣列與字串 Java陣列特性 一維陣列 多維陣列 字串 字串的相關函數 字串緩衝器類別.
陳維魁 博士 儒林圖書公司 第九章 資料抽象化 陳維魁 博士 儒林圖書公司.
C/C++基礎程式設計班 陣列 (Array)
C 語言簡介 - 1.
第8章 字串與陣列 8-1 一維陣列的處理 8-2 二維和多維陣列 8-3 字串處理 8-4 動態陣列、不規則陣列與參數傳遞
Chapter 3.0 C語言的結構與指標 資料結構導論 - C語言實作.
資料結構 Data Structure.
資料結構 第2章 陣列.
第6章 佇列(Queues) 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列.
結構(struct).
第十一章 結構.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置 4-2 鏈結串列的基礎 4-3 單向鏈結串列 4-4 環狀鏈結串列
Chapter 2 陣列結構 資料結構導論 - C語言實作.
第8章 字串與陣列.
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
第10章 陣列與清單控制項.
列舉(enum).
第八章 利用SELECT查詢資料.
保留字與識別字.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
第9章 自訂資料型態 – 結構 9-1 結構資料型態 9-2 結構陣列 9-3 指標與結構 9-4 動態記憶體配置 9-5 聯合資料型態
C語言簡介 日期 : 2018/12/2.
類別(class) 類別class與物件object.
SQL Stored Procedure SQL 預存程序.
第二章 鏈結串列 2-1 線性串列 2-2 認識陣列 2-3 矩陣的簡介與運算 2-4 陣列與多項式.
Methods 靜宜大學資工系 蔡奇偉副教授 ©2011.
第3章 指標與字串 (Pointers and Strings)
Java 程式設計 講師:FrankLin.
JAVA 程式設計與資料結構 第四章 陣列、字串與數學物件.
Chap3 Linked List 鏈結串列.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
|12 結構與列舉型態.
第一單元 建立java 程式.
陣列(Array).
第7章 陣列與指標 7-1 陣列的基礎 7-2 一維陣列的處理 7-3 二維與多維陣列的處理 7-4 陣列的函數參數
第一章 直角坐標系 1-3 函數圖形.
第 19 章 XML記憶體執行模式.
陣列
OOP6 結構Struct 黃兆武.
CH1 我的第一個App與變數宣告.
程式設計 博碩文化出版發行.
第7章 指標 7-1 指標的基礎 7-2 指標變數的使用 7-3 指標運算 7-4 指標與陣列 7-5 指向函數的指標.
挑戰C++程式語言 ──第8章 進一步談字元與字串
向量 (vector) 就是典型的一維陣列,而更高維的矩陣,例如矩陣 (matrix) 和張量 (tensor) 則分別是二維和三維的陣列。
Class & Object 靜宜大學資工系 蔡奇偉副教授 ©2011.
C qsort.
MiRanda Java Interface v1.0的使用方法
第14章 結構與其他資料形式.
陣列與結構.
第 4 章 認識 SQL 語言與資料型別.
第 三 章 陣 列 課程名稱:資料結構 授課老師:________ 2019/5/15.
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
資料表示方法 資料儲存單位.
第四章 陣列、指標與參考 4-1 物件陣列 4-2 使用物件指標 4-3 this指標 4-4 new 與 delete
Introduction to the C Programming Language
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
Array(陣列) Anny
SQLite資料庫 靜宜大學資管系 楊子青.
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
C語言程式設計 老師:謝孟諺 助教:楊斯竣.
Introduction to the C Programming Language
台大資訊工程學系 資訊系統訓練班 第119期 吳晉賢
C 程式設計— 結構 台大資訊工程學系 資訊系統訓練班.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
InputStreamReader Console Scanner
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2-2 陣列表示法-範例 二維陣列的圖例,如下圖所示:

2-2-1 以列為主的表示方法-說明 二維陣列一共有6 X 5 = 30個元素,可以宣告一個大小為30的一維陣列來儲存二維陣列的所有元素,如下所示: int classes[30]; 二維陣列的索引値如何對應到一維陣列的索引値? 例如: 二維陣列a的大小是rows X columns,二維陣列的元素 a(row_num,column_num)使用以列為主的一維陣列表示法,其索引值公式如下所示: row_num * columns + column_num (第幾列) (多少欄) (第幾欄)

2-2-1 以列為主的表示方法-範例 6 列 (rows = 6) 5欄(columns = 5)的二維陣列,陣列元素(1, 0)以列為主時對應於一維陣列的索引值,如下所示: (1, 0)索引值 => 1 * 5 + 0 = 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欄。

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

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

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

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

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

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

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

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

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

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

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

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;

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

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;

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

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

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

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

2-4 陣列的應用 - 稀疏矩陣表示法(標頭檔) 01: /* 程式範例: Ch2-4.h */ 02: #define MAX_TERMS 10 /* 稀疏矩陣的最大元素數 */ 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();