陣列
2012/10/26 謝碧景(c)編製更新
學習目標
摘要
資料結構(Data Structure)：含陣列(Array)、堆疊(Stack)：後進先出LIFO(Last In First Out)、佇列(Queue)：FIFO(First In First Out)、鏈結串列(Linked List)、樹(Tree)、圖(Graph)等。
堆疊(Stack)：是一種先進後出 FILO(First In, Last Out，等同於後進先出LIFO[Last In, First Out]) 的資料結構，例如：Array Stack Visualization。
演算法(Algorithm)：將解決問題的方法以系列的步驟與流程表達出，則為演算法。
可運用流程圖表示，參閱： fChart 程式設計工具。
一、一維數值陣列
(一)陣列 (Array)
陣列是一群相同型態的變數集合(基本的資料結構之一)，屬循序性的資料結構。
陣列宣告及存取以『索引』值(index)為主，且索引值必須是整數常數或整數運算式。
陣列內的每個資料稱為元素(element)，元素在電腦記憶體中佔有連續的記憶體空間。
透過索引可存取陣列個別的元素，且索引不可超過宣告陣列的範圍。
一個索引，如 a[3] 為一維陣列；二個索引，如 a[3,5] 為二维陣列；多個索引即為多維陣列。
(二)宣告格式
資料型別 陣列名稱[n]={值1,...,值n}
n：陣列大小，即元素個數。
索引：為 0 至 n-1
＊註：陣列名稱是指向陣列之記憶體起始位址。
//a[0]=90 , a[1]=80 , a[2]=87
(三)陣列初始化
陣列需初始化，若未初始化，編譯時不會產生錯誤，但執行後結果會錯誤。陣列初始化是將大括號{ }內的資料可以在陣列宣告時指定給陣列元素。
例：以迴圈指定陣列元素的初始值皆為0。
for(i=0;i<5;i++)
a[i]={0};
//相同於 int a[5]={ };
//相同於 int a[5]={0,0,0,0,0};
例：給予全部元素初始值。
int a[3]={90,80,87};
例：指定值給陣列元素。
int a[3];
a[0]=90; a[1]=80; a[2]=87;
(四)一維陣列與重複結構
例1：陣列宣告與輸入。班上依座號序發放口罩，並依座號序輸出口罩數。
例2：求最大值：呈上例，班上同學領最多口罩為多少？
方法1：for迴圈
方法2：while迴圈
例3：陣列相加：陣列大小需相同，且需以陣列元素相加。
(五)一維陣列空間大小：
sizeof 運算子可取得整個陣列所佔記憶體空間大小，亦可取得每個陣列元素記憶體空間大小；若把陣列總記憶體空間大小除以每個陣列元素記憶體空間大小，即可得到陣列元素的個數。【參閱：資料型態】。
◆範例１：計算成績：以一維陣列，存放班上五位同學之成績，並合計五個成績之總分及平均。
二、陣列的應用：排序 (Sort)
氣泡排序法：第8-18、23行【參閱：流程圖】。
◆範例２：輸入n個數值，並將該數列由小至大排序後顯示。
(三) sort 排序函數
陣列排序可利用內建函數sort，由小至大排序，更為簡便，如下。使用 sort函數，需先引入#include <algorithm> 標頭檔。
＊註：
sort 函數：由小至大排序，sort(array,array+n); //array 陣列名稱是位址，n 為元素個數 (注意：由索引0開始算起)。
即 sort(陣列名稱+開始索引,陣列名稱+欲排序數量)欲將指定的陣列順序『反轉』(注意：非排序)，可利用函數 reverse(array,array+n);
例：呈上題：連續輸入陣列元素，請輸出排序後之陣列元素及反轉陣列元素。
三、陣列的應用：搜尋 (Search)
資料搜尋是陣列常應用的功能，其搜尋方式有循序搜尋及二分搜尋，循序搜尋是依序逐一搜尋，方法簡單但較沒效率，而二分搜尋可提升速度，但搜尋前資料必須先由小至大排序好。
(一)循序搜尋法（Sequential search）
循序搜尋法：從數列的頭走到尾，逐一檢查每個元素，直到找到目標數值或檢查完所有數值(目標數值不在數列中)為止。
缺點：較沒有效率。
＊註：
break 指令可強制跳離迴圈，且用於迴圈中。
程式碼效率：第16到24行要掃描data陣列的每一個元素，所以程式碼效率為O(n)。
(二)二分搜尋法 (Binary Search)
搜尋前資料必須先排序好。
將陣列分為兩半，即較小部分及較大部分，以正中央陣列元素和欲搜尋之資料相比較，若相等則表示找到資料，若正中央陣列元素大於欲搜尋之資料，代表欲搜尋之資料落在較小的那半部，則可去掉較大的那半部，接著再於較小的那半部分為兩半，同上法再搜尋，直到找到欲搜尋之資料。
1.先將num陣列由小至大排序
2.二分搜尋法
執行結果
3.延伸思考：先依num陣列由小至大排序好後(注意：name陣列也需一起交換)，再以二分搜尋法比對中獎編號。
若陣列元素有n個，二分搜尋最多需x次能搜尋到，即 2x>=n 次。如上範例：元素有10個，最多需4次，即 24=16>=10，故最多4次可搜尋到。
N個數的數列中搜尋，最壞的情況下，循序搜尋法會從頭到尾逐項搜尋，共搜尋N次。二分搜尋法每次會將搜尋範圍減半，第1次搜尋後約剩N/2個，第2次搜尋後約剩N/22個，以此類推，當只剩1個數時，約需 log2N 次。
程式碼效率：第38到51行為二分搜尋，每次根據數值的大小可排除一半可能性，所以程式碼效率為O(log(n))可找到，二分搜尋較循序搜尋效率要好，但二分搜尋需事先排序。
四、 一維字元陣列
C語言以字元陣列或指標來呈現字串，而C++在內建的標準函式庫中有個 string類別(class)，如同資料型態 (int、char等)，可定義變數【參閱：string 類別應用】。下述先簡介字元陣列。
(一)字元陣列
char 型態的陣列稱為字元陣列，通常用來儲存字元字串， 字元陣列是由一串字元，最後需加上一個字串的結束字元 '\0' 組成，故字元陣列宣告後可利用字串初始化，即會自動在陣列結尾加上 '\0' 字元，每一個字元大小是1個byte，功能與字串雷同。字串與字元陣列仍有些許不同，字串必定是以一個隱藏的空字元'\0'為最後一個字元，為結束，故字串的最大長度是『陣列大小-1』可使用。(字元以單引號 ' 括起文字，字串以雙引號 " 括起文字)。
宣告格式：
char 字串名稱[長度]; // 例 char str[8]; 宣告一個長度為8個字元的字串 str
例如：char str[]={'D','e','v','-','C','+','+'};
亦可利用『字串常數』來初始化。
2.字串初始化：
char 字串名稱[長度]={'字元1','字元2','字元3','字元4','字元5',…};
char 字串名稱[長度]="字串常數";
陣列內的長度是可以省略的，若省略，必須同時指定初始化，否則編譯器不知需配置多大的記憶空間。如下：
char str[8]="Dev-C++"; //以字串常數初始化，系統會自動加入'\0' 字元於陣列結尾
或 char str[]="Dev-C++"; //省略陣列長度，則長度由系統自動分配
◆ 範例５：輸入一串字元(<10)，並輸出每個陣列元素之值。
＊註：cin 指令在接受使用者輸入資料後按下【Enter鍵】時，會自動以空白(Space)鍵或Tab鍵作為資料的結束字元，故輸入之資料不可含空白(Space)鍵或Tab鍵，否則空白(Space)鍵或Tab鍵之後的資料會被移除。若輸入資料需包含空白，則可使用gets函式。
(二) gets、puts 函式
gets(字元陣列);
puts(字元陣列);
gets() 函式可取得字串資料(含空白字元)，其參數必須是字元陣列。
puts() 函式可顯示字元陣列，但只能顯示字串資料，顯示後會自動換行。
◆範例６：以 gets() 及 puts() 函式，存取字元陣列。
執行結果
五、 二維陣列
(一)宣告格式
資料型別 陣列名稱[列索引1][行索引2]
// 元素個數 = 列(左方) x 行(上方)
例 int sc[300][10];
// 宣告陣列 sc 儲存 300*10=3000個元素
(二)對應關係：
1.如下表：左方為列，上方為行，即 sc[列][行]，一列接一列存放至記憶體中，sc[0][0]…sc[0][9]→sc[1][0]…sc[1][9]…。
2.初始值設定：例如：2x3 的二維陣列，初始值設定如下:
int sc[2][3]={{80,83,73},{66,77,88}};
→對應關係如右表：元素個數為6個(2x3=6)
3.二維陣列初始化，可省略列或行的大小，但不可同時省略列及行，因編譯器會無法確認陣列的形式。
例如：陣列元素6個，可能為1x6、6x1、2x3、3x2等。
int sc[2][]={80,83,73,66,77,88};
int sc[][3]={80,83,73,66,77,88};
(三)陣列之元素個數為各索引之乘積：
元素個數 = 列索引 x 行索引
(四)二維陣列與重複結構的應用
◆範例7：輸入兩位學生各三科成績後，顯示每位學生之總分及平均。
＊註：外迴圈控制列索引，內迴圈控制行索引。
六、指標
(一)指標變數宣告：
指標變數就是存放記憶體位址的變數，每個記憶體位址如同住家的門牌號碼，其宣告方式，在變數名稱加上【*】，例如：*p為指標變數p。
資料型態 *指標變數;
(二)格式：
一般可利用一個變數型別相同的指標來儲存其他變數的位址，格式如下:
資料型別 變數名稱=值;
資料型別 *指標變數=&變數名稱;
int n=10;
int *p=&n; //宣告指標變數儲存變數 n 的位址
cout<<"p="<<p<<endl; //p=0x28ff44，指標 p 指向變數 n 的位址
cout<<"*p="<<*p<<endl; //顯示*p=10
＊註：
【&】為取址運算子，可取得變數的儲存位址。
【*】有兩個用途：可宣告指標變數，此外另一個用途為使用【*記憶體位址】可取得該記憶體的內容，故【*】又稱為取值運算子。
(三)一維陣列與指標：
1.一維陣列與指標存取陣列元素：
存取陣列元素：
陣列名稱[索引]；
指標存取值：
*(陣列名稱+索引);
int array[3]={1,2,3};
cout<<array[0]<<"\t"<<*array<<endl; //顯示 1 1
cout<<array[1]<<"\t"<<*(array+1)<<"\n"; // 2 2
cout<<array[2]<<"\t"<<*(array+2)<<endl; // 3 3
2.一維陣列與指標存取陣列元素位址：
存取陣列元素位址：
&陣列名稱[索引]；
指標存取位址：
陣列名稱+索引;
int array={1,2,3};
cout<<&array[0]<<"\t"<<array<<endl; //0x28ff30 0x28ff30
cout<<&array[1]<<"\t"<<array+1<<"\n"; //0x28ff34 0x28ff34
cout<<&array[2]<<"\t"<<array+2<<"\n"; //0x28ff38 0x28ff38
◆範例8：dim_ex.cpp
◆範例9：輸入一字串，並請倒著輸出此字串。
方法Ⅰ
＊註：cin 指令在接受使用者輸入資料後按下【Enter鍵】時，會自動以空白(Space)鍵或Tab鍵作為資料的結束字元，故輸入之資料不可含空白(Space)鍵或Tab鍵，否則空白(Space)鍵或Tab鍵之後的資料會被移除。若輸入資料需包含空白，則可使用gets函式，如下範例。
方法Ⅱ
七、補充
解題策略：暴力法、貪婪演算法、分治法等。
(一)貪婪演算法(Greedy Algorithm)
又稱貪心演算法，選當下最有利方式，再決定下一步驟，缺點：有時候並無法達成全局最佳解。【參閱：貪婪演算法-維基百科】。
◆ 範例10：銀行提款以最少紙鈔、硬幣組成此現金，輸入n元，請以最少的紙鈔、硬幣兌換。
【提示：常用的紙鈔有2000、1000、500、100，硬幣有50、10、5、1元等，可指定給陣列[0]-陣列[7]，兌換參閱：if 題11】
執行結果
§實作練習
◆數值陣列
題1：一維陣列，輸入一串數字(以空白鍵隔開，至多26個，0為結束)，請由小至大排列，並求出算數平均數。
題2：輸入一個十進位整數，請轉換為二進位輸出。【參閱：十進位轉二,八,十六進位，摘自 YouTube】
題3：求費氏數列（Fibonacci）﹦0,1,1,2,3,5,8,13,… 即 f[n]=f[n-1]+f[n-2] 且 n>2，請列出Fibonacci數列的前10項。【提示：費氏數列-維基百科】
題4：二維陣列：成績計算
輸入三位學生各三科成績後顯示每位學生之總分及平均成績。
題5：二維陣列：顯示轉置矩陣。
題6：以亂數模擬擲骰子連續n次，請統計各點數出現的次數。【參閱：亂數函數】
◆字元陣列
題1：輸入一串字元(<50)，將大寫字母轉成小寫字母，小寫字母轉成大寫字母，非字母的字元用減號代替 。【參閱 ASCII符號表 ，提示：ASCII 碼值→A：65、Ｂ：66、…Z：90、、a：97、b：98、…z：122、】
題2：輸入10個字元，輸出共有多少個A,B,C,…Z。(大小寫視為相同) 例：輸入ADAaEVSzaZ 輸出 A:4, D:1, E:1, S:1, V:1, Z:2【提示：方法二→將字母轉為大寫 toupper() 函數定義在 #include <ctype.h> 標頭檔】
題3：輸入三個句子計算總共輸入了多少個字元（包含空白字元）。【提示：參閱 gets(字元陣列)】
