Try   HackMD

PD-1 HW8 Pointer&Array

簡單釐清、理解Pointer的作用
不一定是對的，這是就我自己的理解，然後在用可能比較好懂的方法寫出來。
有問題可以再來Discord問我 夾帶私貨

底下的內容可能可以幫助你理解指標與避免Segmentation Fault

Before Start

1.單位

1byte = 8bits，資料在計算機中以0/1的形式儲存，其中的最小單位為bits，bits儲存的內容是0或1，每8bits可以組合成1byte，每一個byte可以表示0~255種組合。

簡單列出幾個常見型態的大小(同時也是使用sizeof會看見的大小):

Type Size
char 1byte
short 2bytes
int 4bytes
long long 8bytes

2.進位表示法

  • 0b 開頭代表以2進位表示這個數字，例如: 255 -> 0b11111111
  • 0o 開頭代表以8進位表示這個數字，例如: 4095 -> 0o7777
  • 0x 開頭代表以16進位表示這個數字，例如: 65535 -> 0xffff
  • 在0後面所帶的字元代表意義:
    字元 縮寫 全名 中文
    b BIN Binary 二進位
    o OCT Octal 八進位
    d DEC Decimal 十進位
    x HEX Hexadecimal 十六進位

I. About Pointer

指標，用以指向記憶體中的一個位置，長度常見為8bytes。

1.宣告變數的作用

宣告變數的目的，是為了向計算機索取一塊空間，而變數的型態則是告訴計算機你需要多大的空間，可以透過sizeof查看一個變數佔用了多少空間。

例如:

int a = 0;
print("%d", sizeof(a));
// 4

sizeof(a)輸出4代表a這個變數在記憶體中使用了4bytes的空間。

記憶體可以視為由很多個房間所組成，每個房間的大小為1byte，為了要讓計算機能夠取得房間中的資料，每個房間都會有一個專屬的地址，而這個地址就稱作指標。

在上面的範例中，宣告了一個型別為int的變數a，那在記憶體中就會有4個專屬的房間用來儲存a的內容:

Address Value
0x00 0b00000000
0x01 0b00000000
0x02 0b00000000
0x03 0b00000000

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
一般常見的64位元電腦，記憶體位址長度為64bits(8bytes)，以16碼16進制的數字表示，這邊為方便理解僅使用2碼。

從上面的表格中可以看到，編號0x00~0x03的房間中都裝了1個8bits的資料，而將這四個資料組合起來便是變數a裡面所的資料

為什麼記憶體(變數)要初始化?

  • 計算機的記憶體空間是有上限的，為了要節省空間，計算機會在程式運行結束之後對記憶體進行回收，當其他程式需要記憶體時，便有可能分配到回收回來的記憶體，這時的記憶體可能會殘留上一個程式運行時所儲存的資料，因此在宣告變數後需要先對其進行歸零(初始化)。

2.取得指標

如果要取得一個變數的指標，要在變數前方加上&，例如:

int a = 1234;
printf("%p", &a);
// ex. 00000000005FFE9C
// 這邊會因為電腦的分配所以可能會有不同的值

以上的程式碼會輸出一個長度為16的字串，代表a這個變數在記憶體中所在的位置。

Address Value
0x00000000005FFE9C 1234

在這邊你可能會感到疑惑，int的大小不是應該有4bytes嗎，為甚麼這裡只有一格，有這個想法非常正常，上表是為了方便理解所以簡化後的結果，實際上的資料是以下表儲存:

Address Value
0x00000000005FFE9C 0b11010010
0x00000000005FFE9D 0b00000100
0x00000000005FFE9E 0b00000000
0x00000000005FFE9F 0b00000000

從上表可以發現，剛剛所取得的指標其實是代表這個變數所分配到的第一個房間的編號，而變數的型態則決定了有多少房間。

3.儲存指標

如果要將一個指標存入變數，可以在宣告時於名稱前方加上*以宣告一個指標變數，例如:

int a = 1234;
int *a_pointer = &a;

printf("%p %p", &a, a_pointer);
// ex. 00000000005FFE9C 00000000005FFE9C
// 前後的輸出結果應該會是一樣的

在前面有稍微提到過，一般常見的64位元電腦，指標為64bits(8bytes)，你可以嘗試將指標變數的大小印出來:

int a = 1234;
int *a_pointer = &a;

printf("%d", sizeof(a_pointer));
// 8

在這邊你會發現，一個指標變數所佔的空間是8bytes，一個long long變數所佔的空間也是8bytes，那能不能使用long long來儲存呢?

int a = 1234;
int *a_pointer = &a;
long long long_long_pointer = &a;

printf("%p %p %p", &a, a_pointer, long_long_pointer);
// ex. 00000000005FFE9C 00000000005FFE9C 00000000005FFE9C
// 三者的輸出結果應該會是一樣的

在這邊可能會有人感到不解，一個是指標變數，一個是long long，不一樣的變數型態，為甚麼都可以儲存指標?

還記得在最前面所說的嗎，計算機中資料的最小單位為bit，由0和1所組成，所以在計算機中的所有東西都可以轉換為一串由0和1所組成的列表，換個方法來說，所有東西都可以轉換為一個數字。

由此來看，指標也可以視為數字(其實它本質上就是數字)，以上面的00000000005FFE9C來舉例:

進位 值
HEX 00000000005FFE9C
DEC 6291100
OCT 27777234
BIN 01011111 11111110 10011100

既然都是一樣的東西，那只要空間足夠，便都可以存進去，在記憶體中是沒有型態區分的，指標變數也是變數，也會需要空間:

int a = 1234;
int *a_pointer = &a;

printf("%p", &a_pointer);
// ex. 0000000000FEAC20
// 這邊會因為電腦的分配所以可能會有不同的值

從輸出結果來看，指標變數自己也是會有一個專屬的房間存放資料(指標)的:

Address Value
0x0000000000FEAC20 0x00000000005FFE9C
  • 實際情形
    Address Value
    0x0000000000FEAC20 0b10011100
    0x0000000000FEAC21 0b11111110
    0x0000000000FEAC22 0b01011111
    0x0000000000FEAC23 0b00000000
    0x0000000000FEAC24 0b00000000
    0x0000000000FEAC25 0b00000000
    0x0000000000FEAC26 0b00000000
    0x0000000000FEAC27 0b00000000

如果都是數字的話，那自然也可以進行跟數字相同的操作，這裡可能有人會好奇，如果同為8bytes的數字，那為甚麼還需要指標變數，都用long long不就好了?

在解答之前，可以先試試對指標進行加減，例如:

int a = 1234;
int *a_pointer = &a;

// 注意這裡是以十進位(%d)進行輸出
prtinf("%d %d", a_pointer, a_pointer+1);
// 6291100 6291104
// 後面比前面多4

從輸出結果可以發現，前後數字差距為4，並不是1，這就是指標變數與long long不同的地方。

這裡稍微對指標變數做一下說明，會比較便於後面的理解:

  • int *a
    • 拆解為int、*、a
    • 代表a是一個指標變數(*)，指向的資料的型態是int
  • short **a
    • 拆解為short*、*、a
    • 代表a是一個指標變數(*)，指向的資料的型態是short*
  • char ***a
    • 拆解為char**、*、a
    • 代表a是一個指標變數(*)，指向的資料的型態是char**
  • 以此類推

只要是指標變數就是8bytes，不管他有幾層指標。

而指標偏移的距離就在於他所指向的資料的型態，如果記憶體的偏移單位是一個房間的話，那指標變數就是"將指向資料的型態的大小定義為一間屋子的大小"，每次偏移的單位是一間屋子，指標變數的值會是那間屋子的第一個房間，這個觀念在後面陣列的部分會用到。

將其套用在上面的範例:

  • int *a
    • 起始點為0x00
    • 一個屋子的大小為4個房間(int 4bytes)
    • 每次偏移會移動一個屋子(4bytes)
      • a+1 => 0x04
      • a+2 => 0x08
  • short **a
    • 起始點為0x00
    • 一個屋子的大小為8個房間(short* 8bytes)
    • 每次偏移會移動一個屋子(8bytes)
      • a+1 => 0x08 (8)
      • a+2 => 0x10 (16)
  • char ***a
    • 起始點為0x00
    • 一個屋子的大小為8個房間(char** 8bytes)
    • 每次偏移會移動一個屋子(8bytes)
      • a+1 => 0x08 (8)
      • a+2 => 0x10 (16)
  • 以此類推

4.讀取指標

透過在指標前方加上*來取得該指標儲存於記憶體的內容。

先試試以下程式碼:

int a = 1234;

printf("%d %d", a, *(&a));
// 1234 1234

你會發現前後兩者的輸出結果是一樣的，為甚麼呢?

假設這個a所的房間編號(指標)為0x01，那(&a)也就可以轉換成0x01，所以後半部所輸出的其實是*0x01的內容，而這個*0x01就是代表從編號為0x01的房間裡拿出數值(*的意思):

Address Value
0x01 1234

在先前的內容中有提到，int所占用的空間應該是4個房間，所以實際上的情形應該是這樣的:

Address Value(BIN) Value(DEC)
0x01 0b11010010 210
0x02 0b00000100 4
0x03 0b00000000 0
0x04 0b00000000 0

這邊多加了十進位的對應值，之後會稍微提到。

你可能會好奇，我只有給第一個房間的編號，那計算機是如何知道要將幾個房間的資料組合起來變成完整的資料呢，這個就是變數型態的功用，不同變數型態會有不同的大小，也有不同的解析方法，也就是在前面所提到屋子的概念，在上面的範例中，a使用的是int的變數型態，因此&a的型態會是int *，將其進行拆解:

  • int *
    • 拆解為int、*
    • 是一個指標(*)，指向的型態是int 所以計算機就會知道他要將連續4bytes(int 的大小)的資料組合成一筆完整的資料。

哪如果強行改變屋子的大小會發生什麼事呢?

  • 可以試試下面的程式碼 
    ​​​​int a = 1234;
​​​​
​​​​printf("%d %d", a, *((unsigned char*)(&a)));
​​​​// 1234 210

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    這邊使用unsigned char的原因是為了避免第一bit如果為1的話，輸出會被解析為負數，比較不直觀，但下方的說明仍是以char作為說明。

    你會發現後面的輸出變成210了，這是因為透過轉型將原本int *轉換為char *，原本應該是要將4bytes(int 的大小)組合成完整的資料，然而現在只有將1byte(char 的大小)組合為資料，因此就會出現資料不一樣的現象。

    • 原本計算機會連續讀取四個房間的資料:

      Address Value(BIN) Value(DEC)
      0x01 0b11010010 210
      0x02 0b00000100 4
      0x03 0b00000000 0
      0x04 0b00000000 0

      組合成為00000000 00000000 00000100 11010010，轉換為十進位之後就是我們所設定的1234。

    • 轉型之後計算機只會讀取一個房間(char 1byte)的資料:

      Address Value(BIN) Value(DEC)
      0x01 0b11010010 210

      組合成為11010010，轉換為十進位之後就是210

5.寫入指標

與讀取大致上差不多，只是變成在賦值的時候加上*。

對著哪一個指標使用*做修改，資料就會直接在那個記憶體上做更改:

int a = 1234;
int *a_pointer = &a;

printf("%d\n", a);
// 1234

*a_pointer = 5678
printf("%d\n", a);
// 5678

從執行結果來看，會發現透過a_pointer更改資料，a的內容也一起被更改了，假設a的房間編號為0x00000000005FFE9C，那在這個房間中的值就會是1234，也就是我們所設定給a的值:

Address Value
0x00000000005FFE9C 1234

而在每次使用a的時候都會從編號為0x00000000005FFE9C的房間把資料取出來，因此會得到1234的結果。

那現在透過*a_pointer = 5678去進行修改，就相當於*0x00000000005FFE9C = 5678，其所代表的意義便是將編號為0x00000000005FFE9C的房間裡面所存放的值修改為5678，那這時候在記憶體中的內容就會變成這樣:

Address Value
0x00000000005FFE9C 5678

而當我們再次去使用a的時候，他一樣會從編號為0x00000000005FFE9C的房間取出數值，便會得到剛剛所修改的數值，也就是5678。

與讀取的時候相同，變數的型態會決定要將資料拆分成幾份，並分別放進幾個房間，這部分就不展開說明了，如果有興趣的話，可以試試下面這段程式碼，然後去分析為甚麼:

int a = 1234;
int *a_pointer = &a;

printf("%d\n", a);
// 1234

*((unsigned char*)a_pointer) = 123;

printf("%d\n", a);
// 1147

II. Array

就是陣列，用來儲存一連串的資料。

1.宣告陣列的目的

有時候會有很多的資料需要儲存，會需要宣告很多個變數，這時候就可以使用陣列來進行儲存。

宣告一個陣列同樣是需要與計算機索取空間的，用以下宣告一個長度為20的int陣列的程式碼作為範例:

int *arr = malloc(20 * sizeof(int));

printf("%p", arr);
// ex. 00000000007B6B60
// 這邊會因為電腦的分配所以可能會有不同的值

在宣告陣列時所回傳的結果為一個指向陣列開頭的指標，以上的程式碼宣告了一個長度為20 * 4 = 80的陣列，而arr是這個陣列開頭的指標，代表了陣列開始的位置，在記憶體中看起來如下:

Address Value
0x00000000007B6B60 0b00000000
0x00000000007B6B61 0b00000000
… …
0x00000000007B6BAF 0b00000000

在這裡你可能會疑惑，明明是長度為20的陣列，為甚麼填進malloc的數值不是20而是80，這是因為malloc所接收的數字代表要在記憶體中索取多少bytes的空間，而一個int的大小是4bytes，要放20個int就需要4 * 20的空間，這就是一般看到宣告陣列時都會填入長度 * sizeof(型態)的原因。

2.陣列操作

如果一個變數是由多個房間所組合而成的房子的話，那陣列就代表由多間房子所組成的社區，而每個房子在社區中都會有一個專屬的編號，從0~n。

一般常見讀取陣列的方法是arr[index]，其實這個寫法所代表的是*(arr + index)，假設今天有一個長度為3的陣列，裡面放的內容是{1, 2, 3}，那在記憶體中看起來會像這樣:

Address Value Index
0x00 1 0
0x04 2 1
0x08 3 2
實際情形
Address Value
0x00 0b00000001
0x01 0b00000000
0x02 0b00000000
0x03 0b00000000
0x04 0b00000010
0x05 0b00000000
0x06 0b00000000
0x07 0b00000000
0x08 0b00000011
0x09 0b00000000
0x0A 0b00000000
0x0B 0b00000000

關於為甚麼編號一次會增加4可以回去看看前面的內容。

上面寫到宣告陣列時所回傳的其實是一個指向陣列開頭的指標，放在這個例子中的話，arr儲存的內容便是0x00。

那arr[index]又是如何轉換為*(arr + index)的呢?

還記得前面所說，指標每次偏移的距離是其所指向的資料型態大小，以這個範例來看，arr的型態會是int *:

  • int *arr
    • 拆解為int、*、arr
    • 代表arr是一個指標變數(*)，指向的資料的型態是int
    • 起始點為0x00
    • 一個屋子的大小為4個房間(int 4bytes)
    • 每次偏移會移動一個屋子(4bytes)
      • a+0 => 0x00
      • a+1 => 0x04
      • a+2 => 0x08

發現了嗎? arr + index的結果都剛好會是資料儲存的位置，也就是&(arr[index])的數值，在外面套上一層取值便能得到其中的內容，也就是陣列運作的原理。

3.多維陣列

這邊是很多人最難理解的地方，但大多數原因是因為把陣列與指標想得太複雜了。

以下的指標都進行了簡化，所以只有三碼

以一個3 * 4 * 5的陣列來說，他的型態會是像這樣子:int ***。

許多人看到三層指標就亂了，這時候其實只要像上面一樣將他拆開處理就可以了。

以第一層來看:

  • int ***
    • 拆解為int**、*
    • 代表這是一個指標(*)，指向的資料型態是int**
    • 起始點為0x000(假設)
    • 一個屋子的大小為8個房間(int** 8bytes) (只要是指標就都是8bytes)
    • 每次偏移會移動一個屋子(8bytes)
      • a+0 => 0x000
      • a+1 => 0x008
      • a+2 => 0x010

那在記憶體中看起來會是這個樣子:

Address Value Index
0x000 0x01C 0
0x008 0x03C 1
0x010 0x05C 2

這樣子來看可以把他當作一個一維陣列處理，第一層就像是一張大地圖，告訴你哪座城市在哪個位置，而城市的位置所代表的就是第二層的位置。

接下來，取得arr[0](0x01C)，這個就是第二層的位置，將這個第二層也進行拆解:

  • int **
    • 拆解為int*、*
    • 代表這是一個指標(*)，指向的資料型態是int*
    • 起始點為0x01C(假設)
    • 一個屋子的大小為8個房間(int* 8bytes) (只要是指標就都是8bytes)
    • 每次偏移會移動一個屋子(8bytes)
      • a+0 => 0x01C
      • a+1 => 0x024
      • a+2 => 0x02C
      • a+3 => 0x034

同樣從記憶體的角度來看: 那在記憶體中看起來會是這個樣子

Address Value Index
0x01C 0x07C 0
0x024 0x090 1
0x02C 0x0A4 2
0x034 0x0B8 3

同樣把它當成一為陣列來看，這就像是比較小的地圖，上面告訴你每個社區各別是坐落在哪一條街上，找到社區之後，就又回到熟悉的一維陣列了。

以第4項進行舉例，也就是arr[0][3]的值(0x0B8)，這個值所代表的就是社區的位置，同樣對其進行拆解:

  • int *
    • 拆解為int、*
    • 代表這是一個指標，指向的資料的型態是int
    • 起始點為0x0B8
    • 一個屋子的大小為4個房間(int 4bytes)
    • 每次偏移會移動一個屋子(4bytes)
      • a+0 => 0x0B8
      • a+1 => 0x0BC
      • a+2 => 0x0C0
      • a+3 => 0x0C4
      • a+4 => 0x0C8

在這裡就回到了真正的一維陣列:

Address Value Index
0x0B8 123 0
0x0BC 456 1
0x0C0 789 2
0x0C8 876 3
0x0D0 543 4

取第2項就是arr[0][3][1]，得到的就是裡面的值了。

所以多維陣列其實就是一張一張地圖，依序告訴你下一步要走去哪裡，一層一層對應，到最終就可以取道需要的資料了。

III. Conclusion

我也不知道要寫甚麼結語，如果要學好指標與陣列的話，"以底層的方式"進行思考是很重要的，去了解每個部分的操作分別是在做甚麼，電腦的底層是如何執行的，這個部分沒有複雜的數學(頂多進制轉換可能要按個計算機)、沒有花俏的資料結構，相比起來應該是簡單許多的。

Last changed by 
 
zhi_hao
0
1
746
Published on HackMD