C/C++‎ > ‎

陣列

2012/11/11 謝碧景(c)編製更新 

一、一維數值陣列


(一)陣列 (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:計算成績:以一維陣列,存放班上五位同學之成績,並合計五個成績之總分及平均。

執行結果


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

將一序列的數值由小至大或由大至小排列,稱為排序,排序的方式很多,而氣泡排序法最為基本,其原理為逐一比較相鄰的兩個陣列元素資料,若前者大於後者,則交換此兩個資料,同法反覆比較,直到最大者被移到最後,而較小者則會慢慢往陣列前端移動,如同氣泡由底部逐漸浮出,而稱為氣泡排序法。例如: 10、7、12、5 由小至大排序,如下:
陣列比較 比較前 交換後 說明:n=4,a[n]

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

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

第2逐一比較n-2次。

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

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

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

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

執行結果


*註:排序方式很多,下述是不同之設計方式,請自行思考其排序過程及比較次數,參考用。

執行結果


三、陣列的應用:搜尋

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

(一)循序搜尋Sequential search

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

執行結果


*註:break 指令可強制跳離迴圈,且用於迴圈中

(二)二分搜尋Binary search

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

 範例4:園遊會中獎者姓名查詢

執行結果


*註:若陣列元素有n個,二分搜尋最多需x次能搜尋到,即 2x>=n 次。如上範例:元素有10個,最多需4次,即 24=16>=10,故最多4次可搜尋到。


四、一維字元陣列

(一)字元陣列

char 型態的陣列稱為字元陣列,通常用來儲存字元字串, 字元陣列是由一串字元,最後需加上一個字串的結束字元'\0'組成,故字元陣列宣告後可利用字串初始化,即會自動在陣列結尾加上'\0'字元,每一個字元大小是1個byte,功能與字串雷同。字串與字元陣列仍有些許不同,字串必定是以'\0'字元為最後一個字元,即系統自動加入此字串結束字元 。

例如:char str[]={'D','e','v','-','C','+','+'}; 亦可利用字串初始化,如下:

    char str[7]="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() 函式,存取字元陣列。

執行結果


(三)strcpy、strlen函式 

  • 使用字元陣列儲存字串,只能在初始化時使用(採"字串內容"方式),之後不可使用指定運算子“=”來改變字元陣列內容,若需要改變字元陣列內容必須使用 strcpy 函式。
  • 若欲取得字串實際儲存字元長度可使用 strlen 函式

 strcpy(字元陣列,"字串內容");

 strlen(字元陣列);

可改變字元陣列內容。

取得字串內字元之長度。


 範例7:strcpy 及 strlen 函式之應用。

執行結果



 範例8:統計字數:每輸入一行英文句子,即顯示每行之字數,並於輸入完後,統計總字數。

執行結果


二維陣列

(一)宣告語法

 資料型別 陣列名稱[索引1][索引2]

 例  int sc[300][10];

    // 宣告陣列 sc 儲存 300*10=3000個元素

(二)對應關係如下表:

 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]

*註:初始值設定:例如: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

(三)陣列之元素個數為各索引之乘積:

  元素個數=(索引1)x(索引2)
 

 範例9:輸入兩位學生各三科成績後,顯示每位學生之總分及平均。

執行結果



六、指標

(一)指標變數宣告:指標變數就是存放記憶體位址的變數,每個記憶體位址如同住家的門牌號碼,其宣告方式,在變數名稱加上【*】,例如:*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

程式:dim_ex.cpp

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

  • 方法Ⅰ

執行結果


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

  • 方法Ⅱ

執行結果




 範例練習

 數值陣列

 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:輸入一串字元(<50),將大寫字母轉成小寫字母,小寫字母轉成大寫字母,非字母的字元用減號代替 。參閱 ASCII符號表

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

執行結果


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

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

執行結果


 array-8

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

執行結果