陣列

2012/11/11 謝碧景(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

、一維數值陣列

(一)陣列 (Array)
  1. 陣列是一群相同型態變數集合(基本的資料結構之一),屬循序性的資料結構。
  2. 陣列宣告及存取以『索引』值(index)為主,且索引值必須是整數常數或整數運算式
  3. 陣列內的每個資料稱為元素(element),元素在電腦記憶體中佔有連續的記憶體空間。
  4. 透過索引可存取陣列個別的元素,且索引不可超過宣告陣列的範圍。
  5. 一個索引,如 a[3] 為一維陣列;二個索引如 a[3,5] 為二维陣列多個索引即為多維陣列。

(二)宣告格式

 資料型別 陣列名稱[n]={值1,...,值n}

   n:陣列大小,即元素個數。

  索引:為 0 至 n-1

 例  int a[3]={90,80,87};

    /* 宣告陣列a 中 a[0]=90 , a[1]=80 , a[2]=87

            索引:0,1,2            元素;90,80,87      */


*註:陣列名稱是指向陣列之記憶體起始位址


 索引 0 1 2
元素  90  80  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;



(四)一維陣列與重複結構

例:陣列相加:陣列大小需相同,且需以陣列元素相加。



(五)一維陣列空間大小

sizeof 運算子可取得整個陣列所佔記憶體空間大小,亦可取得每個陣列元素記憶體空間大小;若把陣列總記憶體空間大小除以每個陣列元素記憶體空間大小,即可得到陣列元素的個數。

 範例1:計算成績:以一維陣列,存放班上五位同學之成績,並合計五個成績之總分及平均。

執行結果


二、陣列的應用:排序 (Sort)

(一)氣泡排序 (Bubble Sort)
  • 將一序列的數值由小至大或由大至小排列,稱為排序,排序的方式很多,其原理為逐一比較相鄰的兩個陣列元素資料,若前者大於後者,則交換此兩個資料,同法反覆比較,直到最大者被移到最後,而較小者則會慢慢往陣列前端移動
  • 若要排序n個數字,只需n-1次,因第n次只剩一個最小的數,不需排序。
  • 例如: 10、7、12、5 由小至大排序,如下:
陣列比較  比較前  交換後  說明:n=4,a[n]

第1次逐一比較n-1次,即兩兩相比,若前者大於後者,則互相交換,否則不變。

a[0]>a[1]  107、12、5  710、12、5 10 和  7 比較,交換
a[1]>a[2]   7、1012、5  7、1012、5 10 和 12 比較,不變
a[2]>a[3]   7、10、125  7、10、512 12 和  5 比較,交換

第2逐一比較n-2次。

a[0]>a[1]   710、5、12  710、 5、12  7 和 10 比較,不變
a[1]>a[2]   7、10512  7、 51012 10 和  5 比較交換

第3次即最後1次需比較1次,依此類推,總比較次數為 (n-1)+(n-2)+…+2+1=n(n-1)/2

a[0]>a[1]   7 51012   5 71012  5 和  7 比較交換

  • 氣泡排序法:第8-18、23行【參閱:流程圖
執行結果:


 範例2:輸入n個數值,並將該數列由小至大排序後顯示

執行結果


(二)選擇排序法(Selection Sort)

  • 若由小至大排序,則每一回合都選出剩下的數字中最小的一個,將它排在對應的位置(最小排在最前面,第二小的排在第二個,以此類推)。【參閱:選擇排序法-維基百科
  • 選擇排序法:第8-18、23行【參閱:流程圖】。
執行結果


(三) sort 排序函數

陣列排序可利用內建函數sort,由小至大排序,更為簡便,如下。使用 sort函數,需先引入#include <algorithm> 標頭檔

*註:
  • sort 函數:由小至大排序,sort(array,array+n); //array 陣列名稱是位址,n 為元素個數。
  • 欲將指定的陣列順序『反轉』(注意:非排序),可利用函數 reverse(array,array+n);

  •  例:呈上題:連續輸入陣列元素,請輸出排序後之陣列元素及反轉陣列元素。


三、陣列的應用:搜尋 (Search)

  • 常用的搜尋方式有循序搜尋及二分搜尋,循序搜尋是依序逐一搜尋,方法簡單但較沒效率,而二分搜尋可提升速度,但搜尋前資料必須先由小至大排序好

(一)循序搜尋法Sequential search

  • 循序搜尋法:從數列的頭走到尾,逐一檢查每個元素,直到找到目標數值或檢查完所有數值(目標數值不在數列中)為止。
  • 缺點:較沒有效率。

 範例3:在10個數值資料中尋找一數,並顯示其在資料中第幾個找到,若無則顯示“查無此數"。【參閱:流程圖

執行結果


*註:
  • break 指令可強制跳離迴圈,且用於迴圈中
  • 程式碼效率:第16到24行要掃描data陣列的每一個元素,所以程式碼效率為O(n)。

(二)二分搜尋法 (Binary Search)

  • 搜尋前資料必須先排序好
  • 將陣列分為兩半,即較小部分及較大部分,以正中央陣列元素和欲搜尋之資料相比較,若相等則表示找到資料,若正中央陣列元素大於欲搜尋之資料,代表欲搜尋之資料落在較小的那半部,則可去掉較大的那半部,接著再於較小的那半部分為兩半,同上法再搜尋,直到找到欲搜尋之資料。

 範例4:園遊會中獎者姓名查詢【參閱:流程圖

(1)先依num陣列由小至大排序

(2)二分搜尋法

執行結果


*註:(思考)先依num陣列由小至大排序好(注意:name陣列也需一起交換),再以二分搜尋法比對中獎編號。
  1. 若陣列元素有n個,二分搜尋最多需x次能搜尋到,即 2x>=n 次。如上範例:元素有10個,最多需4次,即 24=16>=10,故最多4次可搜尋到。
  2. N個數的數列中搜尋,最壞的情況下,循序搜尋法會從頭到尾逐項搜尋,共搜尋N次。二分搜尋法每次會將搜尋範圍減半,第1次搜尋後約剩N/2個,第2次搜尋後約剩N/22個,以此類推,當只剩1個數時,約需 log2N 次。
  3. 程式碼效率:第39到52行為二分搜尋,每次根據數值的大小可排除一半可能性,所以程式碼效率為O(log(n))可找到,二分搜尋較循序搜尋效率要好,但二分搜尋需事先排序。

四、 一維字元陣列

        C語言以字元陣列或指標來呈現字串,而C++在內建的標準函式庫中有個string類別(class),如同資料型別(int、char等),可定義變數【參閱:string 類別應用。下述先簡介字元陣列。

(一)字元陣列

char 型態的陣列稱為字元陣列,通常用來儲存字元字串, 字元陣列是由一串字元,最後需加上一個字串的結束字元'\0'組成,故字元陣列宣告後可利用字串初始化,即會自動在陣列結尾加上'\0'字元,每一個字元大小是1個byte,功能與字串雷同。字串與字元陣列仍有些許不同,字串必定是以一個隱藏的空字元'\0'為最後一個字元,為結束,故字串的最大長度是陣列大小-1,可使用。(字元以單引號'括起文字,字串以雙引號"括起文字)。
    1. 宣告格式:

       char 字串名稱[長度];    // 例 char str[8];  宣告一個長度為8個字元的字串 str

      例如:char str[]={'D','e','v','-','C','+','+'}; 

       str[0]  str[1]  str[2] str[3]  str[4]  str[5]  str[6]   str[7] 
       D  \0
      亦可利用『字串常數來初始化。

    2. 字串初始化:
 char 字串名稱[長度]={'字元1','字元2','字元3','字元4','字元5',…};
 char 字串名稱[長度]="字串常數";   

陣列內的長度是可以省略的,若省略,必須同時指定初始化,否則編譯器不知需配置多大的記憶空間。如下:

    char str[8]="Dev-C++";             //以字串常數初始化,系統會自動加入'\0' 字元於陣列結尾
 
或 
char str[]="Dev-C++";               //省略陣列長度,則長度由系統自動分配

 範例5:輸入一串字元(<10),並輸出每個陣列元素之值。

執行結果


*註:cin 指令在接受使用者輸入資料後按下【Enter鍵】時,會自動以空白(Space)鍵Tab鍵作為資料的結束字元,故輸入之資料不可含空白(Space)鍵或Tab鍵,否則空白(Space)鍵或Tab鍵之後的資料會被移除。若輸入資料需包含空白,則可使用gets函式。
  

(二)gets、puts 函式

 gets(字元陣列);

 puts(字元陣列);

 gets() 函式可取得字串資料(含空白字元),其參數必須是字元陣列。

 puts() 函式可顯示字元陣列,但只能顯示字串資料,顯示後會自動換行


 範例6:以 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]…。

 sc[0][0]  sc[0][1]  sc[0][2]  ……  sc[0][9]
 sc[1][0]  sc[1][1]  sc[1][2]  ……  sc[1][9]
 ……  ……  ……  ……  ……
 sc[299][0]  sc[299][1]  sc[299][2]   ……  sc[299][9]

2.初始值設定:例如:2x3 的二維陣列,初值設定如下:

 int sc[2][3]={{80,83,73},{66,77,88}};


→對應關係如下表:
元素個數為6個(2x3=6)

 sc[0][0]=80  sc[0][1]=83  sc[0][2]=73
 sc[1][0]=66  sc[1][1]=77  sc[1][2]=88


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:輸入兩位學生各三科成績後,顯示每位學生之總分及平均。

執行結果


*註:外迴圈控制陣列的列索引,內迴圈
控制陣列的行索引。

 sc[0][0]=85  sc[0][1]=72  sc[0][2]=69
 sc[1][0]=80  sc[1][1]=83  sc[1][2]=88


六、指標

(一)指標變數宣告

指標變數就是存放記憶體位址的變數,每個記憶體位址如同住家的門牌號碼,其宣告方式,在變數名稱加上【*】,例如:*p為指標變數p。

 資料型態 *指標變數;


(二)格式

一般可利用一個變數型別相同的指標來儲存其他變數的位址,格式如下:

 資料型別 變數名稱=值;
 資料型別 *指標變數=&變數名稱;
例:    int n=10; 
          int *p=&n;                       //宣告指標變數儲存變數 n 的位址
          cout<<"p="<<p<<endl;       //顯示p=0x28ff44,指標 p 指向變數 n 的位址
          cout<<"*p="<<*p<<endl;   //顯示*p=10

*註:
1.【&】為取址運算子,可取得變數的儲存位址。
2.【*】有兩個用途:可宣告指標變數,此外另一個用途為使用【*記憶體位址】可取得該記憶體的內容,故【*】又稱為取值運算子。

(三)一維陣列與指標

1.一維陣列與指標存取陣列元素:

 存取陣列元素:

 陣列元素[索引];
 指標存取:

*(陣列名稱+索引);
 int array={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<<endl;  //顯示 0x28ff34  0x28ff34
 cout<<&array[2]<<"\t"<<array+2<<endl;  //顯示 0x28ff38  0x28ff38

 範例8:dim_ex.cpp


 範例9:輸入一字串,並請倒著輸出此字串。

    • 方法Ⅰ

執行結果


*註:cin 指令在接受使用者輸入資料後按下【Enter鍵】時,會自動以空白(Space)鍵Tab鍵作為資料的結束字元,故輸入之資料不可含空白(Space)鍵或Tab鍵,否則空白(Space)鍵或Tab鍵之後的資料會被移除。若輸入資料需包含空白,則可使用gets函式,如下範例。

    • 方法Ⅱ

執行結果



七、補充

  • 解題策略:暴力法、貪婪演算法、分治法等。

又稱貪心演算法,選當下最有利方式,再決定下一步驟,缺點:有時候並無法達成全局最佳解。【參閱:貪婪演算法-維基百科

 範例10:銀行提款以最少紙鈔、硬幣組成此現金,輸入n元,請以最少的紙鈔、硬幣兌換。
【提示:常用的紙鈔有2000、1000、500、100,硬幣有50、10、5、1元等,可指定給陣列[0]-陣列[7],兌換參閱:if 題11


執行結果


* 延伸題:Scarecrow。【想法:由左往右看田地,一發現有好地沒被保護到,就放一個稻草人在此好地的右邊一格,該稻草人除了保護此地,還有機會保護到右邊一格和右邊兩格的好地。摘自:Lucky貓






 範例練習

 數值陣列

 array-1  題1:一維陣列,輸入一串數字(以空白鍵隔開,至多26個,0為結束),請由小至大排列,並求出算數平均數。

執行結果


array-2


題2:輸入一個十進位整數,請轉換為二進位輸出【參閱:十進位轉二,八,十六進位,摘自 YouTube

執行結果

 array-3
  

 題3:求費氏數列(Fibonacci)﹦0,1,1,2,3,5,8,13,… 即 f[n]=f[n-1]+f[n-2] 且 n>2,請列出Fibonacci數列的前10項。【提示:費氏數列-維基百科

執行結果


 array-4   題4:二維陣列:成績計算

   輸入位學生各科成績後顯示每位學生之總分及平均成績。

執行結果


 array-5
   
 題5:二維陣列:顯示轉置矩陣。

執行結果


 array-6  題6:以亂數模擬擲骰子連續n次,請統計各點數出現的次數。【參閱:亂數函數

執行結果

 字元陣列

 char-1
  
 題1:輸入一串字元(<50),將大寫字母轉成小寫字母,小寫字母轉成大寫字母,非字母的字元用減號代替 。參閱 ASCII符號表

【提示:ASCII 碼值→A:65、B:66、…Z:90、、a:97、b:98、…z:122、】

執行結果


 char-2-1
 char-2-2
  
 題2:輸入10個字元,輸出共有多少個A,B,C,…Z。(大小寫視為相同) 例:輸入ADAaEVSzaZ    輸出 A:4, D:1, E:1, S:1, V:1, Z:2

【提示:方法二→將字母轉為大寫 toupper() 函數定義在 #include <ctype.h>  標頭檔】

執行結果


 char-3

 題3:輸入三個句子計算總共輸入了多少個字元(包含空白字元)。【提示:參閱 gets(字元陣列)

執行結果