數(shù)組的基本概念

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

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

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

1int array[5];

內(nèi)存布局圖

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

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

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

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

看上面的代碼，學(xué)過(guò)數(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)算

1int a[]={1,2,3,4};

2printf("%d\n",sizeof(a));

3printf("%d\n",sizeof(a+0));

4printf("%d\n",sizeof(*a));

5printf("%d\n",sizeof(a+1));

6printf("%d\n",sizeof(a[1]));

7printf("%d\n",sizeof(&a));

8printf("%d\n",sizeof(&a+1));

9printf("%d\n",sizeof(&a[0]));

10printf("%d\n",sizeof(&a[0]+1));

11//字符數(shù)組

12char arr[] = {'a','b','c','d','e','f'};

13printf("%d\n", sizeof(arr));

14printf("%d\n", sizeof(arr+0));

15printf("%d\n", sizeof(*arr));

16printf("%d\n", sizeof(arr[1]));

17printf("%d\n", sizeof(&arr));

18printf("%d\n", sizeof(&arr+1));

19printf("%d\n", sizeof(&arr[0]+1));

20printf("%d\n", strlen(arr));

21printf("%d\n", strlen(arr+0));

22printf("%d\n", strlen(*arr));

23printf("%d\n", strlen(arr[1]));

24printf("%d\n", strlen(&arr));

25printf("%d\n", strlen(&arr+1));

26printf("%d\n", strlen(&arr[0]+1));

27char *p = "abcdef";printf("%d\n", sizeof(p));

28printf("%d\n", sizeof(p+1));

29printf("%d\n", sizeof(*p));

30printf("%d\n", sizeof(p[0]));

31printf("%d\n", sizeof(&p));

32printf("%d\n", sizeof(&p+1));

33printf("%d\n", sizeof(&p[0]+1));

34printf("%d\n", strlen(p));

35printf("%d\n", strlen(p+1));

36printf("%d\n", strlen(*p));

37printf("%d\n", strlen(p[0]));

38printf("%d\n", strlen(&p));

39printf("%d\n", strlen(&p+1));

40printf("%d\n", strlen(&p[0]+1));

41//二維數(shù)組

42int a[3][4] = {0};

43printf("%d\n",sizeof(a));

44printf("%d\n",sizeof(a[0][0]));

45printf("%d\n",sizeof(a[0]));

46printf("%d\n",sizeof(a[0]+1));

47printf("%d\n",sizeof(a+1));

48printf("%d\n",sizeof(&a[0]+1));

49printf("%d\n",sizeof(*a));

50printf("%d\n",sizeof(a[3]));

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

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

數(shù)組的一些特性

1、嚴(yán)格上說(shuō)數(shù)組只有一維數(shù)組。n維數(shù)組是在一維數(shù)組里面存放一個(gè)(n-1)維數(shù)組，掌握以為數(shù)組即可。

2、數(shù)組的長(zhǎng)度指的是數(shù)組的元素個(gè)數(shù)不是數(shù)組空間長(zhǎng)度。sizeof()關(guān)鍵字即可獲取數(shù)組總的字節(jié)數(shù)，在除以元素類型的字節(jié)數(shù)即可得到數(shù)組長(zhǎng)度。

3、C語(yǔ)言并不會(huì)判斷數(shù)組訪問越界，需要程序員判斷越界訪問。eg:?int arr[5] = {1,2,3,4,5}; int b = arr[10];，這樣訪問也是可以拿到元素的，天知道你訪問的是誰(shuí)的數(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ù)組，把之前的元素拷貝過(guò)來(lái)，釋放之前的內(nèi)存。

6、數(shù)據(jù)根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為 O(1)

7、數(shù)據(jù)的插入和刪除很低效：

（1）如果刪除數(shù)組末尾的數(shù)據(jù)，最好情況時(shí)間復(fù)雜度為 O(1)

（2）如果刪除開頭的數(shù)據(jù)，則最壞情況時(shí)間復(fù)雜度為 O(n)

（3）平均情況時(shí)間復(fù)雜度也為 O(n)。

數(shù)組常見問題

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

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

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

數(shù)組越界訪問

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

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

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

給你一個(gè)數(shù)組，求一個(gè)k值，使得前k個(gè)數(shù)的方差 + 后面n-k個(gè)數(shù)的方差最小 ，時(shí)間復(fù)雜度可以到O(n)。

給定一個(gè)n個(gè)整型元素的數(shù)組a，其中有一個(gè)元素出現(xiàn)次數(shù)超過(guò)n / 2，求這個(gè)元素。

給定一個(gè)含有n個(gè)元素的數(shù)組，找出數(shù)組中的兩個(gè)元素X和Y使得abs（x-y）最小。

在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。

給定一個(gè)數(shù)組A[0,1,…,n-1],請(qǐng)構(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é)就到這里了！

作者：龍躍十二鏈接：https://www.imooc.com/article/300814 ，微信公眾號(hào)：龍躍十二

學(xué)習(xí)C/C++編程知識(shí)，了解C語(yǔ)言更多小知識(shí)，歡迎關(guān)注UP，更多小知識(shí)持續(xù)分享~