CH7 陣列與向量 Array and Vectors 課程名稱 : 資管一程式設計任課教師 : 謝明哲單位職稱 : 台東大學資管系副教授電子郵件 :hmz@nttu.edu.tw hmz@nttu.edu.tw 2016 1
Outline 什麼是陣列? 陣列的運用 排序方式 多維陣列 hmz@nttu.edu.tw 2016 2
什麼是陣列? hmz@nttu.edu.tw 2016 3
陣列 (array) 是一群具有相同型態的元素集合起來的特殊型態, 每一個元素都有一個索引值 (index) 作為存取的依據 宣告時, 在陣列名稱後加上中括號 [ ], 中括號內可以寫上此陣列的大小 宣告方式 : 資料型別陣列名稱 [ 長度 ]; 或資料型別陣列名稱 [ 長度 ]={ 初始值 0, 初始值 1,, 初始值 n-1}; 可略 hmz@nttu.edu.tw 2016 4
ex. int a[10]; // 宣告陣列 a 為 10 個整數空間 float f[20]; // 宣告陣列 f 為 20 個浮點數空間 char str[40]; // 宣告陣列 str 為 40 個字元空間 注意 : 因為陣列是連續的儲存單元, 所以每個單元都是相同的型態!! hmz@nttu.edu.tw 2016 5
陣列的運用 hmz@nttu.edu.tw 2016 6
字元陣列的宣告及應用 : 輸入 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 2016 7
整數陣列的宣告初值設定及使用 : 求出 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 2016 8
模擬丟骰子 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 2016 9
排序方式 hmz@nttu.edu.tw 2016 10
兩種常用的排序演算法 : 1. 選擇排序 Selection sort 2. 泡沫排序 Bubble sort hmz@nttu.edu.tw 2016 11
Selection sort 步驟 1: 一開始整個數列歸類為未排序 步驟 2: 從未排序的數列中, 挑選出最小的數, 並與第一個元素的位置互換, 並將此最小的數, 歸類為已排序數列 步驟 3: 重複步驟 2, 直到所有的數都歸到已排列數列中 hmz@nttu.edu.tw 2016 12
N = 5 Run 1: 19 7 35 40 19 7 13 0 1 2 3 4 hmz@nttu.edu.tw 2016 13
Run 2: 7 35 40 19 13 Run 3: 7 13 40 35 19 Run 4: 7 13 19 40 35 7 13 19 35 40 hmz@nttu.edu.tw 2016 14
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 2016 15
Bubble sort 步驟 1: 一開始整個數列歸類為未排序 步驟 2: 從未排序的數列中的第一個數開始看, 如果前面的數比後面的數, 就往後推 在這過程中, 最大的數會被推到未排列數列中的最後一個位置, 將該最大的數歸類到已排序的數列中 步驟 3: 重複步驟 2, 直到沒有往後推的動作為止 hmz@nttu.edu.tw 2016 16
N = 5 Run 1: 7 39 39 6 92 6 92 hmz@nttu.edu.tw 2016 17
Run 2: 7 3 6 2 9 Run 3: 3 6 2 7 9 Run 4: 3 2 6 7 9 2 3 6 7 9 hmz@nttu.edu.tw 2016 18
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 2016 19
多維陣列 hmz@nttu.edu.tw 2016 20
語法 : 型別陣列名 [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 2016 21
0 1 2 3 a[2][4] = a[0][0] a[0][1] a[0][2] a[0][3] 4 5 6 7 a[1][0] a[1][1] a[1][2] a[1][3] hmz@nttu.edu.tw 2016 22
轉換矩陣 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); } 1 2 3 3 4 2 hmz@nttu.edu.tw 2016 23
使用指標傳遞矩陣 ( 傳址呼叫法 ) 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+10 10 ptra+11 11 hmz@nttu.edu.tw 2016 24
標準樣版函式庫 STL Standard Template Library hmz@nttu.edu.tw 2016 25
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 2016 26
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 2016 27
讀取末尾元素 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 2016 28
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 2016 29
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 2016 30
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 2016 31
取得 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 2016 32
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 2016 33
加入集合元素, 但不可重複 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 2016 34
樂活時間 為何哈佛飲食金字塔建議每天適量食用 健康油脂, 避免 不健康油脂? 為何哈佛飲食金字塔建議少吃紅肉 & 奶油? hmz@nttu.edu.tw 2016 35
不健康油脂, 包括存在於紅肉中的飽和脂肪酸和人造奶油 烘焙食品及油炸食品中的反式不飽和脂肪酸, 會增加 LDL 及三酸甘油酯 健康油脂, 主要是單元不飽和脂肪酸和多元不飽和脂肪酸 (polyunsaturated fat) 多存在於植物油與魚類中 ), 包括橄欖油 麻油 葵花籽油 葡萄籽油 油菜籽油 玉米油 大豆油 花生油及其他良好植物油, 可以提高 HDL, 保護肝臟及心血管功能的正常 hmz@nttu.edu.tw 2016 36
習題 hmz@nttu.edu.tw 2016 37
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%) hmz@nttu.edu.tw 2016 38