Microsoft PowerPoint - CH07 Arrays and Vectors [相容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - CH07 Arrays and Vectors [相容模式]"

洛繁胡
5 years ago
Views:

1 CH7 陣列與向量 Array and Vectors 課程名稱 : 資管一程式設計任課教師 : 謝明哲單位職稱 : 台東大學資管系副教授電子郵件 :hmz@nttu.edu.tw hmz@nttu.edu.tw

2 Outline 什麼是陣列? 陣列的運用排序方式多維陣列

3 什麼是陣列?

4 陣列 (array) 是一群具有相同型態的元素集合起來的特殊型態, 每一個元素都有一個索引值 (index) 作為存取的依據宣告時, 在陣列名稱後加上中括號 [ ], 中括號內可以寫上此陣列的大小宣告方式 : 資料型別陣列名稱 [ 長度 ]; 或資料型別陣列名稱 [ 長度 ]={ 初始值 0, 初始值 1,, 初始值 n-1}; 可略 hmz@nttu.edu.tw

5 ex. int a[10]; // 宣告陣列 a 為 10 個整數空間 float f[20]; // 宣告陣列 f 為 20 個浮點數空間 char str[40]; // 宣告陣列 str 為 40 個字元空間注意 : 因為陣列是連續的儲存單元, 所以每個單元都是相同的型態!! hmz@nttu.edu.tw

6 陣列的運用

7 字元陣列的宣告及應用 : 輸入 6 個字元, 以相反順序列印出來 char str[6]; cout<< input 6 characters string: ; for(int i=0;i<6;i++) cin>>str[i]; cout<<endl; for(int i=5;i>=0;i--) cout<<str[i]; hmz@nttu.edu.tw

8 整數陣列的宣告初值設定及使用 : 求出 5 人中的最高與最低成績 int score[5] = {87,88,91,76,99}; int max,min; max=min=score[0]; for(int i=1;i<5;i++){ if (score[i]>max) max=score[i]; if (score[i]<min) min=score[i]; } hmz@nttu.edu.tw

9 模擬丟骰子 6000 次並統計各點出現次數 int freq[7]={0}; for(int i=0;i<6000;i++) { int die = rand( )%6+1; freq[die]++; } for (int i=1;i<=6;i++) cout<<i<< : <<freq[i]<<endl; [0] [1] [2] [3] [4] [5] [6] 如果擲出骰子的骰子數為 1, 則 freq[1]+1 其它可依此類推 hmz@nttu.edu.tw

10 排序方式

11 兩種常用的排序演算法 : 1. 選擇排序 Selection sort 2. 泡沫排序 Bubble sort hmz@nttu.edu.tw

12 Selection sort 步驟 1: 一開始整個數列歸類為未排序步驟 2: 從未排序的數列中, 挑選出最小的數, 並與第一個元素的位置互換, 並將此最小的數, 歸類為已排序數列步驟 3: 重複步驟 2, 直到所有的數都歸到已排列數列中

13 N = 5 Run 1: hmz@nttu.edu.tw

14 Run 2: Run 3: Run 4: hmz@nttu.edu.tw

15 for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) if (A[i]>A[j]) swap(a[i], A[j]); } hmz@nttu.edu.tw

16 Bubble sort 步驟 1: 一開始整個數列歸類為未排序步驟 2: 從未排序的數列中的第一個數開始看, 如果前面的數比後面的數, 就往後推在這過程中, 最大的數會被推到未排列數列中的最後一個位置, 將該最大的數歸類到已排序的數列中步驟 3: 重複步驟 2, 直到沒有往後推的動作為止

17 N = 5 Run 1: hmz@nttu.edu.tw

18 Run 2: Run 3: Run 4: hmz@nttu.edu.tw

19 void bubblesort (int x[ ], int n) { for (int i=0;i<n-1;i++) for (int j=0;j<n-1-i;j++) if (x[j+1] < x[j]) swap(x[j], x[j+1]); } hmz@nttu.edu.tw

20 多維陣列

21 語法 : 型別陣列名 [n][m]; 或型別陣列名 [n][m]={{ },{ },,{ }}; 範例 : // 宣告一個 2x4 整數二維陣列 int a[2][4]; // 宣告一個 2x4 整數二維陣列, 並設定初始值 int a[2][4] = { {0,1,2,3}, {4,5,6,7} }; hmz@nttu.edu.tw

22 a[2][4] = a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] hmz@nttu.edu.tw

23 轉換矩陣 void transporse(int A[][2], int n) { for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) swap(a[i][j], A[j][i]) } void main() { int x[][2] = { {1, 2}, {3, 4}}; transpose(x, 2); } hmz@nttu.edu.tw

24 使用指標傳遞矩陣 ( 傳址呼叫法 ) void transporse(int *ptra, int n) { for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) swap(*(ptra+i*n+j), *(ptra+j*n+i)); } void main() { int X[][3] = { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11} }; int *ptrx = &X[0][0]; transpose(prtx, 3); } 記憶體位址 X[][3] 內容 prta+0 0 ptra+1 1 ptra+2 2 ptra+3 3 ptra+4 4 ptra+5 5 ptra+6 6 ptra+7 7 ptra+8 8 ptra+9 9 ptra ptra hmz@nttu.edu.tw

25 標準樣版函式庫 STL Standard Template Library

26 STL vector 物件 (template 類別 ) #include <vector> using std::vector; 使用 vector 類別宣告一維陣列 (vector 物件 ) vector<int> x(5); // 5 個整數未設定初始值 vector<int> y(8,0); // 8 個整數初始值為 0 vector<int> z(y); // 以 y 初始 z,z 為 y 的複製 hmz@nttu.edu.tw

27 vector 物件的運算設定 x = y; 相等 if (x==y) cout<< x ==y ; 長度 for(int i=0;i<x.size( );i++) cin>>x[i]; 加入元素 x.push_back(0); // 在 x 末尾添加元素 0 hmz@nttu.edu.tw

28 讀取末尾元素 cout<<x.back(); // 列印 x 末尾元素讀取指定元素 cout<<x.at(0); // 列印 x 第 0 個元素 cout<<x[0]; // 列印 x 第 0 個元素刪除末尾元素 x.pop_back(); // 刪除 x 末尾元素清除所有元素 x.clear(); // 將 x 清空 hmz@nttu.edu.tw

29 bubblesort() 的 vector 版 void bubblesort (vector<int>& x) { for (int i=0; i<n-1; i++) for (int j=0; j<x.size()-1-i; j++) if (x[j+1]<x[j]) swap(x[j], x[j+1]); } hmz@nttu.edu.tw

30 STL 的 sort() 排序演算法 #include <algorithm> 宣告 Vector 物件 vector<grade> grade; 自行定義 < 的 operator 函式給 sort() 函式使用 bool operator<(const Grade &x, const Grade &y) { if (x.average < y.average) return true; else return false; } 使用 sort() 函式由小到大進行排序 sort(&grade[0], &grade[n]); //N=grade.size() hmz@nttu.edu.tw

31 STL map 物件 (template 類別 ) #include <map> using std::map; 使用 map 類別宣告 < 座號, 姓名 > 映射物件 map<int, string> student; 加入 < 座號, 姓名 > 映射值 1. student.insert(pair<int, string>(1, 李誠 )); 2. student.insert( map<int, string>::value_type (1, 李誠 )); 3. student[1] = 李誠 ; hmz@nttu.edu.tw

32 取得 map 的大小 cout<<student.size(); 由 key 尋找映射值 map<int, string>::iterator iter; iter = student.find(1); if (iter!= student.end()) cout << iter->first <<, << iter->second; else cout<< not find ; 刪除映射值 student.erase(iter); 清除所有映射值 student.clear(); hmz@nttu.edu.tw

33 STL set 物件 (template 類別 ) #include <set> using std::set; 使用 set 類別宣告集合物件 set<int> s; 加入集合元素, 不可重複 for (int i=0;i<n;i++) s.insert(i); 列印所有集合元素 set<int>::iterator iter; for (iter=s.begin();iter!=s.end();iter++) cout<<*iter<<" "; hmz@nttu.edu.tw

34 加入集合元素, 但不可重複 s.insert(3); 尋找集合元素 3 iter=s.find(3); if (iter!=s.end()) cout<<*iter; 刪除集合元素 3 s.erase(3); 判斷是否為空集合 if (s.empty()) cout<< 空集合 ; hmz@nttu.edu.tw

35 樂活時間為何哈佛飲食金字塔建議每天適量食用健康油脂, 避免不健康油脂? 為何哈佛飲食金字塔建議少吃紅肉 & 奶油?

36 不健康油脂, 包括存在於紅肉中的飽和脂肪酸和人造奶油烘焙食品及油炸食品中的反式不飽和脂肪酸, 會增加 LDL 及三酸甘油酯健康油脂, 主要是單元不飽和脂肪酸和多元不飽和脂肪酸 (polyunsaturated fat) 多存在於植物油與魚類中 ), 包括橄欖油麻油葵花籽油葡萄籽油油菜籽油玉米油大豆油花生油及其他良好植物油, 可以提高 HDL, 保護肝臟及心血管功能的正常

37 習題

38 Ch7. Exercises 7.8 (6%) 7.9 (14%) 7.11(6%) 7.13(8%) 7.14(8%) 7.16(6%) 7.17(6%) 7.18(6%) 7.21 (6%) 7.31 (6%) 7.35 (6%) 7.36 (6%) 7.37 (6%)

Microsoft PowerPoint - C_Structure.ppt

Microsoft PowerPoint - C_Structure.ppt 結構與其他資料型態 Janet Huang 5-1 結構的宣告 struct 結構名稱 struct 結構名稱變數 1, 變數 2,, 變數 m; struct 結構名稱變數 1, 變數 2,, 變數 m; student; student; 5-2 1 結構變數初值的設定 struct 結構名稱 struct 結構名稱變數 = 初值 1, 初值 2,, 初值 n student="janet","1350901",100,95