C++ 鍊氣期之數組探幽

2022 年 6 月 24 日
筆記
C++, C++編程之美

1. 數組概念

變量是內存中的一個存儲塊，大小由聲明時的數據類型決定。

數組可以認為是變量的集合，在內存中表現為一片連續的存儲區域，其特點為：

同類型多個變量的集合。
每一個變量沒有自己的名字。
數組會為每一個變量分配一個位置編號。
可以通過變量在數組中的位置編號（下標）使用變量。

C++中稱數組為複合類型，複合類型指除了基本類型之外或通過基本類型組合而成的新類型。如類、結構體、枚舉……

數組是一種數據結構，與棧、隊列、樹、圖……這類數結構不同，數組是實體數據結構，有自己的物理內存描述。棧、隊列、樹……是抽象數據結構，或者說是一種數據存儲思想，沒有對應的物理存儲方案，需開發者自行設計邏輯存儲方案。

什麼時候使用數組？

在需要保存大量同類型數據的應用場景下可以考慮選擇數組。因數組中的變量是相鄰的，如同一條藤上的瓜（順藤摸瓜），訪問起來非常方便快捷。

大部分抽象數據結構的底層都可藉助數組來實現。

連續存儲的優點一眼可知，但是連續也會帶來新的問題，程序運行過程中，會產生內存碎片，當數組需要的空間較大時，底層邏輯可能無法騰出一大片連續空間來。

當需要考慮充分利用空間時，鏈表當是首選。

下面，通過數組的使用流程，讓我們全方面了解數組。

2. 創建數組

根據數組在內存中的存儲位置，有 2 種創建方式：

靜態創建。
動態創建。

2.1 靜態創建

2.1.1 語法

創建數組時需要指定 3 方面信息：

數組名：數組名就是變量名，只是這個名稱指的是一片連續區域。
數據類型：數組用來保存什麼樣類型的數據。
數組長度：編譯器需要根據數組大小開闢空間。

int num[10];

如上語法，創建了可以存儲 10 個整型數據的數組。

創建數組後，怎麼訪問數組中的變量？

編譯器會為數組中的 10 個 int 存儲塊從 0開始編號。編號從 0開始，到數組長度-1結束，編號也稱為下標。如果需要訪問數組中的第一個變量中的數據，則如下代碼可實現：

int num[10]; 
cout<<num[0]<<endl;

正因為數組的下標屬性，數組通常藉助循環語法結構進行整體遍歷。

創建數組後是否存在數據？

遍歷一次數組，便可以看到數組中所有的數據信息。

int num[10]; 
for(int i=0;i<10;i++){
	cout<<num[i]<<endl;
}

輸出結果可能會讓你摸不着頭。這是啥意思？

創建數組後，數組中會有數據信息，是內存中相應位置曾經存儲過的或由編譯器隨機生成的數據。對於創建數組初衷（保存自己的數據）的你而言，這都是垃圾數據。

隨機數據：每一次運行上述代碼，結果可能都不一樣。

所以，必須對數組進行初始化，這樣數組中的數據才會有意義。

2.1.2 初始化

初始化指創建數組後為數組中的變量指定初始值。

初始化語法：

創建後通過循環語法結構賦值。

int num[10];
for(int i=0; i<10; i++) {
	num[i]=i*10;
}

單個變量賦值。

int num[10];
num[0]=10;

邊創建邊賦值，{}符號可以用來表示數組字面常量。

//正確
int num[10]={1,3,4,9};

在賦值時，實際指定的值可以少於數組的長度。如果反過來，如下代碼則行不通。

//錯誤
int num[3]={1,3,4,9};

上述賦值代碼，實際值超過數組創建時的長度約束，語法上不能通過。如果邊創建、邊賦值分成 2 行，也是不行的。如下代碼是錯誤的。

int num[3];
//錯誤
num=={1,3,4,9};

如下代碼，省略數組長度也是可以的，編譯器會根據給定的值判斷出數組長度。

int num[]={1,3,4,9};

全部初始化為 0。如下代碼，初始化時只指定一個值且為 0 時，這裡的語義不是指給數組中的第一個變量賦值，而是為數組中的所有變量指定初始值為 0。

int num[5]={0}; 
//輸出數組所有值
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

輸出結果：

如果用下面的代碼進行初始化，語義是：數組的第一個變量賦值為 1，其餘變量賦值都為 0。

int num[5]={1,0}; 
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

輸出結果：

理解上述語法的語義後，以此類推，對於下面的代碼，想必很容易猜到輸出結果：

int num[5]={1,2,0}; 
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

C++11中提供更清晰、簡潔、安全的初始化語法。如下語法，是不是很簡潔、驚艷。數組和{}之間可以不用等於號，太體貼了，生怕你多敲一個字母，會手痛。且為數組中的每一個變量賦值 0。沒有多餘的廢話。

int num[5] {};
for(int i=0; i<5; i++) {
	cout<<num[i]<<endl;
}

當然，你一定要加一個等於號讓代碼符合你曾經的認知也是可以的。

int num[5]= {};

除此之外，對數組初始化時，禁止類型宿窄轉換。如下代碼，會有編譯警告提示，2.5是浮點類型，存儲存到 int類型數組中，是類型縮窄。C++11是禁止的。

int num[5] ={3,2.5};

2.1.3 越界問題

C++中使用數組，沒有訪問越界一說。所謂訪問越界，指下標超過數組創建時指定的大小範圍。

越界在Java語言中認定是語法錯誤。

int num[5];
//理論是越界的
num[6]=20;
for(int i=0; i<7; i++) {
    //輸出了 7 個數據
	cout<<num[i]<<endl;
}

上述代碼，創建數組時，確定了數組長度為 5，其有效下標應該是0~4。但 num[6]=20能正確執行且循環輸出時居然能得到 20。

C++並不會阻止你的訪問超過數組邊界，但是，開發者需要從源頭上切斷這種行為。類似於相鄰兩家，關係很好，相互之間不設阻隔牆，但不意味着你能隨意出入對方家裡。

2.2.4 數組與指針

數組在內存中的存儲結構有 2 個部分：

存儲數組數據的內存區域。
存儲數組首地址的內存變量。

數組名本質是指針變量，保存着數組的首地址，也是第一個存儲位置。

int num[5]={4,1,8,2,6};
cout<<"數組的地址："<<num<<endl;
//輸出結果：
//數組的地址：0x70fe00 16進制描述的內存地址

如果要得到數組第一個位置的數據，則需要使用*運算符。

int num[5]={4,1,8,2,6};
cout<<"數組中的第一個位置的數據："<<*num<<endl;
//數組中的第一個位置的數據：4

除了使用*運算符，還可以使用[下標]語法。兩者語法上有差異，但是語義是一樣的。可以認為[下標]訪問語法是指針訪問語法的簡化版。

int num[5]={4,1,8,2,6};
cout<<"數組中的第一個位置的數據："<<num[0]<<endl;
//數組中的第一個位置的數據：4

如果要訪問其它位置的數據，可以通過移動指針實現。

Tip： num+1可以讓指針移到數組的下一個變量位置。這裡的1具體移動多少，由創建數組時指定的數據類型決定，如本文數組是 int類型，1便是移動 4 位元組。

int num[5]={4,1,8,2,6};
cout<<"數組中第二個位置的數據："<<*(num+1)<<endl;
//數組中第二個位置的數據：1

當然，完全可以使用[下標]替代。

int num[5]={4,1,8,2,6};
cout<<"數組中第二個位置的數據："<<num[1]<<endl;

指針是C++語言的一大特色，能夠讓開發者直接操作內存地址（屬於直接硬件操作），正因為此原因，編譯器無法干涉，所以指針移動的範圍只受限於物理內存大小的影響。如下代碼能正常運行。

int num[5]={4,1,8,2,6};
//完全超界，但人家就是能運行 ，指針的手能伸到天涯海角
for(int i=0;i<1000000;i++){
	cout<<*(num+i)<<endl;
}

了解指針的特性後，也就不會奇怪為什麼訪問數組時能夠越界。使用指針時務必謹慎，需要靠個人行為對之約束。

2.2.5 小結

通過靜態創建語法創建的數組，稱為靜態數組，其特點如下：

在編譯時，就需要為數組指定大小，或說數組大小在編碼時就必須給定。
靜態創建數組時不能使用 auto關鍵字。

//錯誤語法
auto  num[5];

數組名中保存有數組大小的信息。如下代碼可以獲取到數組長度。

int num[10];
//sizeof得到num實際佔用的內存空間，以位元組為單位
int len=sizeof(num)/4;
cout<<len;
//輸出：10

靜態數組的數據保存在棧中，在編譯期間進行空間分配，在生命周期結束後自動回收。

2.2 動態創建

動態創建：指數組的大小可以在運行時動態指定，除此之外，和靜態創建的底層區別在於存儲位置的不同，動態創建的數組的數據存儲在堆中。

堆的特點：

開發者可以根據自己的需要提出空間使用申請。
當空間不再需要時，開發者需要手動釋放空間。

先看一下創建語法：

int *num=new int[10];

代碼解釋：

num是指針變量，用來保存數組的首地址。
new是運算符，其作用是在堆中開闢空間，並把空間的首地址返回。
int[10]，指開闢空間的大小，以及保存什麼類型的數據。

num是首地址，也是數組中第一個位置的地址。

int *num=new int[10];
//初始化第一個位置的數據
*num=10;
cout<<"第一個位置的數據:"<<*num<<endl;

如下通過對整個數組進行初始化：

int *num=new int[10];
for(int i=0; i<10; i++) {
	*(num+i)=i*10;
}
for(int i=0; i<10; i++) {
	cout<<*(num+i)<<endl;
}

輸出結果：

同樣可以使用[下標]語法結構，對訪問數組。

int *num=new int[10];
for(int i=0; i<10; i++) {
	num[i]=i*10;
}
for(int i=0; i<10; i++) {
	cout<<num[i]<<endl;
}

動態數組可以在運行時改變數組的大小。靜態創建方式是一錘定音的買賣，一旦確定後，就不能再改變。如下代碼是正確的。

int *num=new int[10];
num=new int[20];

正因為動態數組的動態性，無法通過代碼獲得它的長度。

int *num=new int[10];
cout<<sizeof(num)/4<<endl; 
//輸出結果：2，並不是數組的長度。

當動態數組的使命結束後，開發者需要使用 delete運算符手動釋放數組所佔用的空間。

int *num=new int[10];
//delete num;語法上可行，會產生不確定行為
delete [] num;

這裡要注意，如果不加[]，語法上是沒有問題的，但是，會有不確定的因素存在，所以！請務必加[]。

3. 數組性能分析

得益於數組內存結構的連續性，只要知道數據的位置，便能快速訪問到。查詢時間度複雜度可以達到O（1）。在查詢類的應用場景下，數組存儲方案應該成為首選。

當在數組中插入數據時，需要把數據向後移動為插入的數據挪出位置，且需要在創建數組時預留足夠多的空間，否則會有數據丟失的風險。

//最後一位為預留位置
int num[10]= {1,2,3,4,5,6,7,8,9,0};
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}
cout<<endl;
int newNum=0;
int pos=0;
cout<<"請輸入要插入的數據："<<endl;
cin>>newNum;
cout<<"請輸入要插入的位置："<<endl;
cin>>pos;
//從插入位置的數據向後移動
for(int i=9; i>pos-1; i--) {
	num[i]=num[i-1];
}
num[pos-1]=newNum;
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}

運行結果：

1       2       3       4       5       6       7       8       9       0
請輸入要插入的數據：
13
請輸入要插入的位置：
5
1       2       3       4       13      5       6       7       8       9

刪除數據時，需要把數據刪除位置之後的數據向刪除位置移動（向前）。

int num[10]= {1,2,3,4,5,6,7,8,9,10};
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}
cout<<endl;
int pos=0;
cout<<"請輸入要刪除的位置："<<endl;
cin>>pos;
//從插入位置的數據向前移動
for(int i=pos-1; pos<8; i++) {
	num[i]=num[i+1];
}
 //最後一位補 0
num[9]=0;
for(int i=0; i<10; i++) {
	cout<<num[i]<<"\t";
}

運行結果：

1       2       3       4       5       6       7       8       9       10
請輸入要刪除的位置：
4
1       2       3       5       6       7       8       9       10      0

在數組中插入、刪除數據的時間複雜度為O（n）。

在頻繁需要插入、刪除的應用場景下，可以選擇比數組性能更好的鏈表。

4. 總結

本文介紹了數組的 2 種創建方式，並對數組的操作性能做了簡單的分析。數組遍歷時是通過底層的指針移動來實現的。指針是C系列語言的一大特點，是一把雙刃劍，用的好能禦敵千里之外，用的不好！bug滿天飛。

Tags: C++ C++編程之美