《C語言》 —— 數(shù)組詳解

書籍使我變成了一個(gè)幸福的人，使我的生活變成輕松而舒適的詩?！郀柣?/p>

本文已經(jīng)收錄至我的GitHub,歡迎大家踴躍star 和 issues。
https://github.com/midou-tech/articles

前言

 我本來準(zhǔn)備C語言章節(jié)就寫個(gè)指針就ok了，在我看來C語言的精華部分就是指針了。但是有很多同學(xué)就開始在群里各種拉扯C語言的其他問題，沒辦法，我是龍叔嘛，想想還是整理一下，把一些重要的C語言知識點(diǎn)都一一更新了吧。C語言指針的內(nèi)容請點(diǎn)擊 指針（上） 和 指針（下），記得點(diǎn)關(guān)注，不迷路

數(shù)組的基本概念

 我們把一組數(shù)據(jù)的集合稱為數(shù)組（Array），它所包含的每一個(gè)數(shù)據(jù)叫做數(shù)組元素（Element），所包含的數(shù)據(jù)的個(gè)數(shù)稱為數(shù)組長度（Length），數(shù)組中的每個(gè)元素都有一個(gè)序號，這個(gè)序號從0開始，而不是從我們熟悉的1開始，稱為下標(biāo)（Index），所包含數(shù)組的里面元素的類型叫做數(shù)組類型（Type）。

 一句話就說清楚了數(shù)組的基本概念，就是這么簡單，^_^。

數(shù)組底層結(jié)構(gòu)探析

int array[5];

內(nèi)存布局圖

 不要看這個(gè)圖簡單，底層就是這樣的。數(shù)組是一個(gè)整體，它的內(nèi)存是連續(xù)的；也就是說，數(shù)組元素之間是相互挨著的，彼此之間沒有一點(diǎn)點(diǎn)縫隙。

 這一點(diǎn)很重要,連續(xù)的內(nèi)存為指針操作（通過指針來訪問數(shù)組元素）和內(nèi)存處理（整塊內(nèi)存的復(fù)制、寫入等）提供了便利，這使得數(shù)組可以作為緩存使用。

 有同學(xué)估計(jì)要說什么叫做指針操作，聽龍叔絮叨下。

int arr[5] = {1,2,3,4,5};
printf("%d\n",arr[3]);

 看上面的代碼，學(xué)過數(shù)組都知道arr[3]是取第三個(gè)元素的值，那我就要問你了，怎么取到值的呢？？？

 不要慌，龍叔告訴你其實(shí)就是指針操作。當(dāng)我們聲明并定義數(shù)組int arr[5] = {1,2,3,4,5}，此時(shí)數(shù)組被分配了5個(gè)int大小的空間在棧上，并初始化了數(shù)組元素。我們都知道數(shù)組名代表數(shù)組的首元素的首地址，那么很明顯就可以得到arr[3] = arr + 3。指針的加減操作詳情請看龍叔公號，微信搜索 龍躍十二 即可訂閱喔。

數(shù)組的運(yùn)算

int a[] = {1,2,3,4};
printf("%d\n",sizeof(a));
printf("%d\n",sizeof(a+0));
printf("%d\n",sizeof(*a));
printf("%d\n",sizeof(a+1));
printf("%d\n",sizeof(a[1]));
printf("%d\n",sizeof(&a));
printf("%d\n",sizeof(&a+1));
printf("%d\n",sizeof(&a[0]));
printf("%d\n",sizeof(&a[0]+1));
//字符數(shù)組
char arr[] = {'a','b','c','d','e','f'};
printf("%d\n", sizeof(arr));
printf("%d\n", sizeof(arr+0));
printf("%d\n", sizeof(*arr));
printf("%d\n", sizeof(arr[1]));
printf("%d\n", sizeof(&arr));
printf("%d\n", sizeof(&arr+1));
printf("%d\n", sizeof(&arr[0]+1));
printf("%d\n", strlen(arr));
printf("%d\n", strlen(arr+0));
printf("%d\n", strlen(*arr));
printf("%d\n", strlen(arr[1]));
printf("%d\n", strlen(&arr));
printf("%d\n", strlen(&arr+1));
printf("%d\n", strlen(&arr[0]+1));
char *p = "abcdef";printf("%d\n", sizeof(p));
printf("%d\n", sizeof(p+1));
printf("%d\n", sizeof(*p));
printf("%d\n", sizeof(p[0]));
printf("%d\n", sizeof(&p));
printf("%d\n", sizeof(&p+1));
printf("%d\n", sizeof(&p[0]+1));
printf("%d\n", strlen(p));
printf("%d\n", strlen(p+1));
printf("%d\n", strlen(*p));
printf("%d\n", strlen(p[0]));
printf("%d\n", strlen(&p));
printf("%d\n", strlen(&p+1));
printf("%d\n", strlen(&p[0]+1));
//二維數(shù)組
int a[3][4] = {0};
printf("%d\n",sizeof(a));
printf("%d\n",sizeof(a[0][0]));
printf("%d\n",sizeof(a[0]));
printf("%d\n",sizeof(a[0]+1));
printf("%d\n",sizeof(a+1));
printf("%d\n",sizeof(&a[0]+1));
printf("%d\n",sizeof(*a));
printf("%d\n",sizeof(a[3]));

就這幾個(gè)運(yùn)算，估計(jì)會(huì)難倒很多同學(xué)的，不信你可以把答案寫出來之后在去跑一遍，全對找我拿紅包。

sizeof(數(shù)組名)，代表整個(gè)數(shù)組的字節(jié)數(shù)；&數(shù)組名，代表取得整個(gè)數(shù)組的地址。

數(shù)組的一些特性

1. 嚴(yán)格上說數(shù)組只有一維數(shù)組。n維數(shù)組是在一維數(shù)組里面存放一個(gè)(n-1)維數(shù)組，掌握以為數(shù)組即可。
2. 數(shù)組的長度指的是數(shù)組的元素個(gè)數(shù)不是數(shù)組空間長度。sizeof()關(guān)鍵字即可獲取數(shù)組總的字節(jié)數(shù)，在除以元素類型的字節(jié)數(shù)即可得到數(shù)組長度。
3. C語言并不會(huì)判斷數(shù)組訪問越界，需要程序員判斷越界訪問。eg: int arr[5] = {1,2,3,4,5}; int b = arr[10];，這樣訪問也是可以拿到元素的，天知道你訪問的是誰的數(shù)據(jù)。
4. 數(shù)組底層內(nèi)存結(jié)構(gòu)是連續(xù)的。正是由于數(shù)組結(jié)構(gòu)的連續(xù)性便誕生了內(nèi)存的友好性，數(shù)組分配內(nèi)存是整塊分配的，堆內(nèi)存很友好；連續(xù)的內(nèi)存是的訪問內(nèi)存效率高。
5. 數(shù)組大小是固定不變的。需要改變大小就需要新開一塊大內(nèi)存的數(shù)組，把之前的元素拷貝過來，釋放之前的內(nèi)存。
6. 數(shù)據(jù)根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為 O(1)
7. 數(shù)據(jù)的插入和刪除很低效：
   • 如果刪除數(shù)組末尾的數(shù)據(jù)，最好情況時(shí)間復(fù)雜度為 O(1)
   • 如果刪除開頭的數(shù)據(jù)，則最壞情況時(shí)間復(fù)雜度為 O(n)
   • 平均情況時(shí)間復(fù)雜度也為 O(n)。

數(shù)組常見問題

數(shù)組長度是一個(gè)非常量。

int b;
scanf("%d",&b);
int arr[3*b];

 不知道你曾經(jīng)有沒有寫過這樣的代碼，反正我寫過。數(shù)組的長度和內(nèi)存是在程序編譯時(shí)就已經(jīng)確定了的。b的值是在運(yùn)行時(shí)才確定的。有兩個(gè)新名詞，程序編譯時(shí)&程序運(yùn)行時(shí)。

數(shù)組越界訪問

int arr[5] = {1,2,3,4,5};
printf("%d\n",arr[-1]);
printf("%d\n",arr[1]);
printf("%d\n",arr[4]);
printf("%d\n",arr[5]);
printf("%d\n",arr[6]);

肉眼可見的錯(cuò)誤，編譯器竟然沒報(bào)錯(cuò)。

數(shù)組相關(guān)筆試題目

1. 給你一個(gè)數(shù)組，求一個(gè)k值，使得前k個(gè)數(shù)的方差 + 后面n-k個(gè)數(shù)的方差最小 ，時(shí)間復(fù)雜度可以到O(n)。
2. 給定一個(gè)n個(gè)整型元素的數(shù)組a，其中有一個(gè)元素出現(xiàn)次數(shù)超過n / 2，求這個(gè)元素。
3. 給定一個(gè)含有n個(gè)元素的數(shù)組，找出數(shù)組中的兩個(gè)元素X和Y使得abs（x-y）最小。
4. 在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
5. 在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。
6. 給定一個(gè)數(shù)組A[0,1,...,n-1],請構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。（注意：規(guī)定B[0] = A[1] A[2] ... A[n-1]，B[n-1] = A[0] A[1] ... A[n-2];）

利用數(shù)組可以出很多筆試題目，當(dāng)然這些題目很多并不是考驗(yàn)數(shù)組本身特性大多是考算法基礎(chǔ)的。本節(jié)就到這里了，有什么不清楚的問題歡迎留言喔，也可私信或mail。

<h5 style="color:blue;text-align:center">「轉(zhuǎn)發(fā)」是明目張膽的喜歡，「在看」是偷偷摸摸的愛。</h5>

往期精彩回顧：