陣列

• 陣列是一群具有相同名稱或資料型態的變數集合。

• 由於整個陣列中的變數均具有相同的名稱，因此若要存取陣列中的變數，我們只需要透過陣列的 index 來指定就可以了。

• 陣列與變數的功能都是用來儲存資料，但有所不同的是每一個變數只能儲存一項資料，而陣列則是由一連串的主記憶體空間組合而成，所以可以同時連續儲放多項資料，亦即一次可以宣告多個變數，而不用一個一個宣告。因此，可以少寫許多行程式，並且增加程式的可讀性。

• 陣列定義：

  1. 陣列裡的每一個元素都必須是同一種資料型態。
  2. 陣列大小須為常數（constant value）。
  3. 佔用了連續（contiguous）的記憶體位址。
  4. 如果我們不會分配任何初始值給陣列，最好在宣告的時候將陣列初始化為零或 null。
  5. 插入或刪除元素時較麻煩，因為需挪移其他元素。
  6. 用來表示有序串列之一種方式。

陣列的應用

讓電腦隨機給定四十人的分數，並在螢幕顯示出來。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(){
    int i;
    int score[40];
    
    srand( time(NULL) );
    
    for(i = 0; i < 40; i++){
        score[i] = rand(() % 41) + 60; // 把分數設定在 100~60 之間
    }
    
    printf("座號\t分數\n");
    for(i = 0; i < 40; i++){
        printf("%d\t%d\n", (i+1), score[i]);
    }
}

陣列格式

• 根據陣列結構不同，我們可以把陣列分為
  1. 一維陣列
  2. 二維陣列
  3. 多維陣列
• 而表示方法如下：

dataType arrayName[arraySize];
dataType arrayName[arraySize] [arraySize];

int score[40]; // 沒有宣告初值的陣列
int arr[5] = {3, 4, 5, 6, 7}; // 也可以一併宣告初值
int arr[] = {3, 4, 5, 6, 7}; // 或是用這種方式讓電腦自動決定陣列長度
int arr[5] = {0}; // 初始化陣列，所有元素都設為0

但是要切記，陣列的長度要在編譯期間就決定好，也就是陣列長度須為常數。如果想要在執行期間，動態生成陣列，要用動態配置記憶體的方式，這邊我們等到指標的單元會再提。

int arr[5] = {3, 4, 5, 6, 7};

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(){
    int arr[5] = {0, 10, 100, 1000, 5000};
    
    printf("arr[3] = %d\n\n", arr[3]); // arr[3] = 1000
}

陣列的空間分配方式

無論是幾維的陣列，C語言都會分配一塊連續的記憶體空間來處理。（這個概念到未來的指標單元會用到）

int x[10];
分配 10*sizeof(int) 個 bytes

int x[5][10];
分配 5*10*sizeof(int) 個 bytes

但如果是呼叫函式傳遞參數時，如：

void fun(int x[]){

}

這裡的陣列 x 就沒有分配空間，這樣相當於 int *x。
這是因為 C語言在呼叫函式傳遞參數時，無法傳遞整個陣列，因為陣列可能大的不得了，所以我們傳遞的是陣列的開頭地址，也就是指標。
因此，在參數宣告時，指標和沒有宣告大小的陣列可以混用。

範例一 整數陣列

1. 定義一個陣列空間為 10 的整數一維陣列，以亂數填入介於 a、b （a < b）之間的整數元素。
   a、b 為使用者輸入的整數。
   請列出該陣列的所有元素。
2. 承上題，計算該整數陣列之平均值（means）。

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void main(){

    int arr[10] = {0};
    int a, b;

    srand(time(NULL));

    printf("Please enter two number a and b (a < b):\n");
    scanf("%d %d", &a, &b);

    for(int i = 0; i < 10; i++){
        arr[i] =  rand() % (b - a + 1) + a;
    }

    for(int i = 0; i < 10; i++){
        printf("arr[%d] = %d\n", i, arr[i]);
    }

    /* 第二小題 */
    int sum = 0;
    float ave = 0;
    
    for(int i = 0; i < 10; i++){
        sum += arr[i];
    }
    
    ave = sum / 10.0;
    print("\nmean of the array: %f", ave);
}

Please enter two number a and b (a < b):
3 25
arr[0] = 25
arr[1] = 6
arr[2] = 4
arr[3] = 12
arr[4] = 18
arr[5] = 5
arr[6] = 3
arr[7] = 9
arr[8] = 11
arr[9] = 21

mean of the array: 11.4

多維陣列

一維陣列使用陣列名稱與一個 index 來指定存取的陣列元素。
二維陣列使用陣列名稱與兩個 indices 來指定存取的陣列元素，宣告方式與一維陣列類似。

範例二－泡沫排序法 Bubble Sort

我們先來講解排序演算法（sorting algorithm），但在這之前，我們又要先來再講講何謂演算法？

何謂演算法？

• Wiki的定義：
  為任何良定義的具體計算步驟的一個序列，常用於計算、資料處理和自動推理。精確而言，演算法是一個表示爲有限長列表的有效方法。演算法應包含清晰定義的指令用於計算函式。
  

• 簡單講成一句話：可以解決某些問題的有效方法之有限集合。
• 那麼，在程式的領域，我們再把它縮成一個公式：
  $$
  程式設計 = 資料結構 + 演算法 \
  \text{Programming} = \text{Data Structures} + \text{Algorithm}
  $$
• 說穿了，演算法就是一種 解決問題的邏輯思維！

排序演算法

所謂排序法，就是將一堆沒有排序過的數字由小到大（或大到小）排列好的演算法。
視覺化15種排序法

其中一種程式入門者最常使用的排序演算法－泡沫演算法 Bubble sort

泡沫演算法 Bubble Sort

首先比較最前面兩個數字
如果要排序由小到大，那麼將較大的往後排
反之，將較小的數字往後排

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

字串 String

• C語言其實並沒有「string」這種類型的資料型態，但我們通常不會只用「一個字元」啊，一般來說都會使用「字串」。
• 這種時候我們就只能透過字元陣列 char[] 來模擬字串。
• 要注意：字串一定是 char[] 字元陣列；但是 char[] 字元陣列不一定就是字串。
• 在 C 談到字串的話，一個意義是指字元組成的陣列，最後加上一個空（null）字元 '\0'，例如底下這個 “hello” 字串：char text[] = {‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
• 之後可以直接使用以下 function 顯示在螢幕上：printf(“%s”, text);
• 也可以使用 " " 來包含文字，例如：char text[] = “hello”;
• 雖然在這個例子沒有指定空字元 '\0'，但是此語法下會自動加上空字元。

範例

我們改成使用 gets() 來讀取字串。

所以這裡我們可以發現，已經解決剛剛的問題了。
gets() 只有 Enter 鍵（回車符）才會結束，在 Enter 鍵以前都會當成字元（包含空白鍵）。

gets() vs. scanf()

• gets(str) 允許輸入的字符含有空格。
• scanf("%s", str) 不允許輸入字符串含有空格。

注意：
當你編譯包含 gets 的程式時，可能會出現 warning 説 gets 是不安全的，原因是 gets( ) 及 scanf( ) 都無法知道字串 s 大小，必須遇到換行符或讀到文件結尾為止才接收輸入，因此容易導致字元陣列 overflow 的情況。
意思就是說，當你輸入的字串數量超過接收字串的陣列大小，就很容易發生 overflow。

函式 Function

• 到目前為止都只使用一個函式（Function），也就是 main() 主函式，若某些程式碼經常使用，我們就可以抽出來讓它成為一個新函式好讓我們重覆呼叫。這也就是所謂的模組化。
• 什麼叫模組化？簡單來說，就是把特定功能分出來當成一個模組，需要的時候只要呼叫這個模組就好；而需要修正的時候也只要修正模組即可。
• 函式用來將程式組織為一個小的、獨立的運行單元，一個函式可以接受資料（傳入參數），並執行其中的算法，最後將結果傳回去。

函式的優點

1. 減少撰寫重覆的程式碼。
2. 將程式碼以有意義的方式組織起來。
3. 在相同的流程下，可藉由參數調整程式的行為。
4. 藉由函式庫可組織和分享程式碼。
5. 做為資料結構 (data structures) 和物件 (objects) 的基礎。

我們就舉幾個例子來簡單示範如何宣告並且使用函數。

範例

沒有輸入參數，也沒有回傳值。

主程式

副程式內容

範例

有輸入參數，也有回傳值。

主程式 簡化了前一頁的程式方便講解

副程式內容

通常我們的副函式會寫在整個 program 的最前面（main function 前面），不過也可以寫在 main function 的後面，但是一開始要先宣告副函式。