# PD-1 HW8 Pointer&Array
> 簡單釐清、理解Pointer的作用<br/>
> 不一定是對的，這是就我自己的理解，然後在用可能比較好懂的方法寫出來。<br/>
> 有問題可以再來Discord問我 ~~[夾帶私貨](https://chih-hao.xyz)~~
底下的內容可能可以幫助你理解指標與避免Segmentation Fault
[TOC]
## 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`查看一個變數佔用了多少空間。
例如:
```cpp
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 |
:::warning
:warning: 一般常見的64位元電腦，記憶體位址長度為64bits(8bytes)，以16碼16進制的數字表示，這邊為方便理解僅使用2碼。
:::
從上面的表格中可以看到，編號`0x00`~`0x03`的房間中都裝了1個8bits的資料，而將這四個資料組合起來便是變數`a`裡面所的資料
#### 為什麼記憶體(變數)要初始化?
- 計算機的記憶體空間是有上限的，為了要節省空間，計算機會在程式運行結束之後對記憶體進行回收，當其他程式需要記憶體時，便有可能分配到回收回來的記憶體，這時的記憶體可能會殘留上一個程式運行時所儲存的資料，因此在宣告變數後需要先對其進行歸零(初始化)。
### 2.取得指標
如果要取得一個變數的指標，要在變數前方加上`&`，例如:
```cpp
int a = 1234;
printf("%p", &a);
// ex. 00000000005FFE9C
// 這邊會因為電腦的分配所以可能會有不同的值
```
以上的程式碼會輸出一個長度為16的字串，代表`a`這個變數在記憶體中所在的位置。
| Address | Value |
| :----------------: | :---: |
| 0x00000000005FFE9C | 1234 |
:::info
在這邊你可能會感到疑惑，`int`的大小不是應該有4bytes嗎，為甚麼這裡只有一格，有這個想法非常正常，上表是為了方便理解所以簡化後的結果，實際上的資料是以下表儲存:
| Address | Value |
| :----------------: | :--------: |
| 0x00000000005FFE9C | 0b11010010 |
| 0x00000000005FFE9D | 0b00000100 |
| 0x00000000005FFE9E | 0b00000000 |
| 0x00000000005FFE9F | 0b00000000 |
從上表可以發現，剛剛所取得的指標其實是代表這個變數所分配到的第一個房間的編號，而變數的型態則決定了有多少房間。
:::
### 3.儲存指標
如果要將一個指標存入變數，可以在宣告時於名稱前方加上`*`以宣告一個指標變數，例如:
```cpp
int a = 1234;
int *a_pointer = &a;
printf("%p %p", &a, a_pointer);
// ex. 00000000005FFE9C 00000000005FFE9C
// 前後的輸出結果應該會是一樣的
```
在前面有稍微提到過，一般常見的64位元電腦，指標為64bits(8bytes)，你可以嘗試將指標變數的大小印出來:
```cpp
int a = 1234;
int *a_pointer = &a;
printf("%d", sizeof(a_pointer));
// 8
```
在這邊你會發現，一個指標變數所佔的空間是8bytes，一個`long long`變數所佔的空間也是8bytes，那能不能使用`long long`來儲存呢?
```cpp
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 |
既然都是一樣的東西，那只要空間足夠，便都可以存進去，**在記憶體中是沒有型態區分的**，指標變數也是變數，也會需要空間:
```cpp
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`不就好了?
在解答之前，可以先試試對指標進行加減，例如:
```cpp
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**`
- 以此類推
:::info
只要是指標變數就是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.讀取指標
透過在指標前方加上`*`來取得該指標儲存於記憶體的內容。
先試試以下程式碼:
```cpp
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 |
:::info
這邊多加了十進位的對應值，之後會稍微提到。
:::
你可能會好奇，我只有給第一個房間的編號，那計算機是如何知道要將幾個房間的資料組合起來變成完整的資料呢，這個就是變數型態的功用，不同變數型態會有不同的大小，也有不同的解析方法，也就是在前面所提到屋子的概念，在上面的範例中，`a`使用的是`int`的變數型態，因此`&a`的型態會是`int *`，將其進行拆解:
- `int *`
- 拆解為`int`、`*`
- 是一個指標(`*`)，指向的型態是`int`
所以計算機就會知道他要將連續4bytes(`int` 的大小)的資料組合成一筆完整的資料。
#### 哪如果強行改變屋子的大小會發生什麼事呢?
- 可以試試下面的程式碼
```cpp
int a = 1234;
printf("%d %d", a, *((unsigned char*)(&a)));
// 1234 210
```
:::warning
:warning: 這邊使用`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.寫入指標
與讀取大致上差不多，只是變成在賦值的時候加上`*`。
對著哪一個指標使用`*`做修改，資料就會直接在那個記憶體上做更改:
```cpp
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。
與讀取的時候相同，變數的型態會決定要將資料拆分成幾份，並分別放進幾個房間，這部分就不展開說明了，如果有興趣的話，可以試試下面這段程式碼，然後去分析為甚麼:
```cpp
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`陣列的程式碼作為範例:
```cpp
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 |
:::spoiler 實際情形
| 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 |
:::
:::info
關於為甚麼編號一次會增加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.多維陣列
這邊是很多人最難理解的地方，但大多數原因是因為把陣列與指標想得太複雜了。
:::info
以下的指標都進行了簡化，所以只有三碼
:::
以一個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
我也不知道要寫甚麼結語，如果要學好指標與陣列的話，"以底層的方式"進行思考是很重要的，去了解每個部分的操作分別是在做甚麼，電腦的底層是如何執行的，這個部分沒有複雜的數學(頂多進制轉換可能要按個計算機)、沒有花俏的資料結構，相比起來應該是簡單許多的。
Sign in with Wallet
Connect another wallet