資料結構筆記(二)：陣列、字串與指標

Noob Tsai -

第二章就從陣列、字串和指標開始講好了。覺得把記憶體位址拿來一起講應該會比較好理解一點，畢竟在底層都是差不多的東西。

陣列

還記得陣列是什麼嗎？也許下面這段程式碼可以幫助你回憶一下：

int arr[5] = {3,8,7,6,3};
for(i=0;i<5;i++){
    printf("%d", arr[i]);
}

想起來了嗎？

陣列有點像是一格一格連續的格子，裡面儲存不同的東西。畫成圖的話：

好像沒有那麼難，對吧？

仔細看這個陣列是由 陣列名稱[陣列索引] 所組成的，也就是說，陣列是一組序對，<index, value>，其中每一個 索引（index） 都對應（或稱映射）到一個相關的 值（value）。

當然還有所謂的二維陣列，像是：

int arr[3][4] = {
    {1,2,3,5},
    {4,5,6,2},
    {4,5,7,0}
}

但說實在的不要去把他理解成二維陣列的每一個元素都是一個一維陣列什麼的，個人覺得很複雜。你只要把陣列想成一種物件，然後陣列裡面可以放陣列就好了，放幾個都不是問題。不然人類只能理解到三維空間，要是你遇到四維陣列你就會想撞牆了。

記憶體位址

來看看陣列在記憶體裡面是怎麼運作的。當你宣告一個 8 格的整數陣列時，其實程式向作業系統要求了 32 bytes 的連續空間（通常一個 int 佔 4 bytes，八個就佔 32 bytes）。

（圖中一格為 1 byte，記憶體位址以 10 進位表示。）

還記得指標中，& 可以用來取得記憶體位址、* 可以用來取值嗎？

如果想要取得 arr[0] 的記憶體位址，可以用 &arr[0] 來取得。如圖中的範例，會得到 1000。以此類推，&arr[1] 會得到 1004、&arr[2] 會得到 1008。

同理，如果能夠理解陣列是透過這種方式取得記憶體位址的話，就知道陣列的底層其實是用指標來實作，那麼就可以透過 *(arr) 來取得陣列的第一格、*(arr+1) 來取得陣列的第二格。

難得來附個例題好了：

在C語言中，宣告 int a[3] = {2, 1, 6}，若 &a[0] 的值是 $1000$ 且整數之大小為 $4$ 位元組，請問 *(a+2) 的值為何？（假設記憶體位址以 10 進位表示。）

這題其實根本不用管記憶體位址是多少。由於 * 是用來取值的，所以 *(a+2) 可以看成 a[2]，也就是 a 的第三格，答案為 $6$。

再來看一題需要考慮記憶體位址的：

假設 a 為一大小 $m \times n$ 之二維陣列，其中 a[2][2] 之位址為 $121$，a[5][4] 之位址為 $194$，已知每一元素之大小為 $1$ 位元組，則 a[3][5] 之位址為合？（假設陣列索引值由 $0$ 開始、記憶體位址以 $10$ 進位表示）

這題就比較複雜一點，把它想成一個 $m \times n$ 之表格，其中透過一個整數為 4 bytes 的觀念，可推得：

  • a[2][2] 的記憶體位址為 121 → 可推得 a[2][0] 的記憶體位址為 119
  • a[5][4] 的記憶體位址為 194 → 可推得 a[5][0] 的記憶體位址為 190

假設 a[0][0] 的記憶體為 $k$，則可以列出：

  • $k+2n = 119$
  • $k+5n = 190$

解出來發現 k 和 n 沒有正整數解。

由於陣列有可能以列為主，也有可能以行為主，我們只好轉過來推得：

  • a[2][2] 的記憶體位址為 121 → 可推得 a[0][2] 的記憶體位址為 119
  • a[5][4] 的記憶體位址為 194 → 可推得 a[0][4] 的記憶體位址為 189

假設 a[0][0] 的記憶體位址為 $k$ ，則可以列出：

  • $k+2n = 119$
  • $k+4n = 189$
  • 解出得 $k+5n+3 = 227$

註：原本記憶體算錯了，感謝網友蕭于傑協助更正。

這邊就是陣列和記憶體的概念了。

字串

最後來講一下字串。

C 語言裡面沒有字串，字串其實是由字元陣列組成的。還記得 C 裡面有個東西叫 char 嗎？

char name[] = "NoobTW";

C 語言允許你用字元陣列搭配雙引號來宣告一個字串，看起來沒有什麼大問題，概念和剛剛的整數陣列差不多。可是一旦你執行了這段程式碼：

#include <stdio.h>

int main(){
    char name[] = "NoobTW";
    printf("%d", sizeof(name));
    return 0;
}

你會發現，奇怪，NoobTW 不是總共六個字嗎？為什麼輸出會是 7？

那是因為字串需要一個 \0 符號做結尾，來判斷這個字串已經結束了。也就是說，name 在記憶體中其實長這樣：

延伸閱讀

資料結構筆記 目錄