Class 3：陣列.

Presentation on theme: "Class 3：陣列."— Presentation transcript:

1 Class 3：陣列

2 複習 int i=1; while(i<=5){ //Do Something i++; }
for(i=1;i<=5;i++){ //Do Something } int i=1; do{ //Do Something i++; }while(i<=5); 這3種寫法做出來都是一樣的

3 複習 int i=1; while(i<=5){ if(i==3){ break; } //Do Somthing i++;
continue; } //Do Somthing //Do Something 的部份只會執行到2次 ( i==1 和 i==2 兩次) //Do Something 的部份只會執行到4次 (少了i==3 的一次)

4 想一想… 如果要撰寫一個程式，程式要求要輸入全班5位同 學的期中考數學科成績，則這個程式會長什麼樣 子？
上面是只有5位同學的程式，若全班有50位同學， 則num變數和scanf()敘述都需要50個！

5 解決方法 改用陣列來寫這樣的程式： 是不是變得簡潔多了？

6 陣列 一群由相同資料型態的元素所集合而成的特殊型 別 電腦中一塊連續的記憶體 這塊記憶體被分成許多相同大小的小空間
每個小空間會依照順序從0開始給予一個編號 可以用編號來存取該小空間的資料

7 一維陣列 宣告出陣列名稱為a，有5個整數元素的陣列 語法 陣列a 指定初始值的語法 編譯程式會根據初始值的個數自動判斷陣列的大小
資料型別 陣列名稱[陣列大小]; 如: int a[5]; 宣告出陣列名稱為a，有5個整數元素的陣列 陣列a 指定初始值的語法 資料型別 陣列名稱[陣列大小]={資料1,資料2,資料3,…資料N}; 編譯程式會根據初始值的個數自動判斷陣列的大小 宣告大小為N時，取用的索引值範圍為0,1,2,…, N-1 a[0] a[1] a[2] a[3] a[4]

8 範例練習 利用for迴圈與陣列資 料型態 使用者輸入5個數字後， 印出此5個數字值及總 和

9 課堂練習 練習1 練習2 請修改上面的程式，輸出增加最大值與5個數字的平 均值 使用陣列儲存字串 請讓使用者輸入自己的名字後，和使用者打招呼
int max=0; for(i=1;i<5;i++){ if(num[max]<num[i])max=i; } 課堂練習 練習1 請修改上面的程式，輸出增加最大值與5個數字的平 均值 提示：加入if敘述 練習2 使用陣列儲存字串 請讓使用者輸入自己的名字後，和使用者打招呼 char name[32]; scanf(“%s”,name);

10 二維陣列 需要2個索引值的陣列 宣告int grade[2][3]; 指定起始值的語法
資料型別 陣列名稱[列數][行數]={{第0列的資料},{第1列的資料},...}; 假設我們有像這樣的資料 則語法為 int grade[3][4]={{10001,95,97,83},{10002,51,98,69},{10003,67,99,90}}; 陣列grade grade[0][0] grade[0][1] grade[0][2] grade[1][0] grade[1][1] grade[1][2] 10001 95 97 83 10002 51 98 69 10003 67 99 90 二年甲班成績

11 範例練習 讓使用者依序輸入3個 學生的數學成績、英 文成績和國文成績的 資料，並計算平均並 輸出

12 課堂練習 請改寫上面的程式： 調整學生人數為4人，科目增加社會 增加一項在不及格分數前面加上*號的功能 結果應如下圖所示：

13 氣泡排序法 排序時，最大的元素會如同氣泡一樣移至右端 利用比較相鄰元素的方法，將大的元素交換至右 端 口訣：小在前，大在後！

14 ↓ 10 7 13 5 1 比較10> 7 ,10和7對掉 ↓ 7 10 13 5 1 比較10<= 13 ,不做認何事 ↓ 7 10 13 5 1 比較13>5 , 13和5對掉

15 7 10 5 13 1 7 10 5 1 13 比較13> 1 ,13和1對掉 ↓ 最後結果: 最大的數跑到最右邊了
最後結果: 最大的數跑到最右邊了 剩下4個數還未排序,重複剛才的動做,這次讓10跑到右邊 ↓ 7 10 5 1 13 比較7<=10 , 不做任何事

16 操作範例 10,7,13,5,1 由小到大排列 Step1.1 10>7，於是兩者交換，陣列變成7,10,13,5,1
到此為止，我們已經把最大的元素13移至最右端了，下一次只需檢查到陣 列倒數第二個元素即可。 Step2.1 7<10，於是沒有動作 Step2.2 10>5，於是兩者交換，陣列變成7,5,10,1,13 Step2.3 10>1，於是兩者交換，陣列變成7,5,1,10,13 第二大的元素10也就定位了。 Step3.1 7>5，於是兩者交換，陣列變成5,7,1,10,13 Step3.2 7>1，於是兩者交換，陣列變成5,1,7,10,13 第三大的元素7也就定位了。 Step4.1 5>1，於是兩者交換，陣列變成1,5,7,10,13 完成。

17 HW4_sort.cpp 請利用氣泡排序法程 式片段，撰寫一個程 式可以讓使用者任意 輸入5個數字，程式 會輸出排序結果

18 二元搜尋法 在已排序的資料數列中尋找某一筆資料 在執行二元搜尋時的比較，可以分成三種情況， 如下所示： 搜尋鍵值小於陣列的中間元素
鍵值在資料陣列的前半部 搜尋鍵值大於陣列的中間元素 鍵值在資料陣列的後半部 搜尋鍵值等於陣列的中間元素 找到搜尋的鍵值

19 1 5 9 12 16 Low ↓ Middle ↓ Up ↓ Num Num[0] Num[1] Num[2] Num[3] Num[4]
int SearchKey=7; //數字7在陣列裡的哪個位置 (0~4) int Low=0,Up=4; int Middle=(Up+Low)/2; // (0+4)/2 = 2

20 1 5 9 12 16 Low ↓ Up ↓ Middle ↓ Num Num[0] Num[1] Num[2] Num[3] Num[4]
//因為: 7 不在Num[middle], 且7<9 //所以: 我們知道7如果在陣列裡的話,應該會在middle 的左邊 // => 把up移到middle-1的位置 Up=Middle-1; //把Up移到新的位置後,計算新的middle middle=(Up+Low)/2; // middle = (0+1)/2 =0

21 1 5 9 12 16 Middle ↓ Low ↓ Up ↓ Num Num[0] Num[1] Num[2] Num[3] Num[4]
//因為: 7 不在Num[middle], 且7>1 //所以: 我們知道7如果在陣列裡的話,應該會在middle 的右邊 // => 把Low移到middle+1的位置 Low=Middle+1; //把Low移到新的位置後,計算新的middle middle=(Up+Low)/2; // middle = (1+1)/2 =1

22 1 5 9 12 16 Middle ↓ Up ↓ Low ↓ Num Num[0] Num[1] Num[2] Num[3] Num[4]
//因為: 7 不在Num[middle], 且7>5 //所以: 我們知道7如果在陣列裡的話,應該會在middle 的右邊 // => 把Low移到middle+1的位置 Low=Middle+1; //把Low移到新的位置後,發現Low > Up //告知使用者7不在陣列裡

23 程式範例 // bool done; // bool 這個資料型態只能有兩個值 true, false // !false==true

24 課堂練習 請利用上面的二元搜尋法程式片段，撰寫一個程 式可以讓使用者任意輸入5個數字並指定一個任意 的搜尋數字，程式會輸出搜尋結果

25 作業四 請利用剛教過的二元搜尋法與氣泡排序法程式片 段，撰寫一個程式可以讓使用者任意輸入8個數字 並指定一個任意的搜尋數字
使用者可以決定想要由大到小或由小到大排序 程式會輸出排序結果和搜尋結果（HW4.cpp）