pointer 實作一般陣列，以及 1-d dynamic array

--- GA: G-RZYLL0RZGV --- ###### tags: `大一程設-下` `東華大學` `東華大學資管系` `基本程式概念` `資管經驗分享` pointer 實作一般陣列，以及 1-d dynamic array === [TOC] ## 前言用指標實作陣列的好處是能夠更加地利用記憶體，可以利用零碎位置的記憶體，不用受到連續配置的條件影響，但變向的其實指標也會更需要記憶體資源，因為除了存指標變數之外，他指向的位址也需要記憶體來儲存，所以究竟要用指標還是要用一般的陣列還是老話一句 -> 全看需求而定! ## 觀念釐清! ### 陣列頭其實就是一種指標! > **我自己的理解，陣列頭是指標(pointer)，但不是指標變數(pointer variable)!** > [name=Orange] 還記得我們當初學陣列的時候告訴過大家，只打上陣列的名字的時候會印出陣列頭所在的記憶體位址，那不知道你有沒有覺得下面的例子跟指標很像。 ```cpp= int main(){ int *p; int a[10]; for(int i = 0; i < 10; i++){ a[i] = i; //會印出 0123456789 } p = a; for(int i = 0; i < 10; i++){ cout << p[i]; //會印出 0123456789 } } ``` 在第 7 行，我們把陣列頭的記憶體位址 assign 給指標變數 p。這邊你可能會納悶，明明指標變數是儲存指標(記憶體位址)，他又不是陣列，怎麼也可以像一般的陣列一樣使用中括號呢(第九行)? 原因是因為一般的陣列是**連續配置**的，在一般陣列裡面，使用**中括號[i]代表的是相對於陣列頭的位移量**，而我們知道整數陣列一格的記憶體位置大小為 4 bytes，所以 `a[0]` 就是相對於陣列頭 `0 * 4bytes` 的位移量，`a[1]` 就是 `1 * 4bytes` 的位移量。依此類推...，你可以從下圖理解一下。 > 雖然圖有點醜... > [name=Orange] ![](https://i.imgur.com/fyUrvi4.png) ### 小整理 * `a[0]` 代表的是說相對於 a 的陣列頭(記憶體位址)有 `0 * 4bytes` 的位移量。 * `p[0]` 代表的是相對於 p 這個指標變數所儲存的指標(記憶體位址)有 `0 * 4bytes` 的位移量。這樣你有懂為什麼可以用 `p[]` 了嗎? 因為指標變數 p 儲存指標(記憶體位址)，所以只要是**針對位址**表達位移量，都可以用 `[]`。 * `cout << a[0]` or `cout << p[0]` * 這樣是表示，印出相對應陣列頭 0 * 4bytes 位移量區塊內的數值 * `cout << &a[0]` or `cout << &p[0]` * 這樣是表示，印出相對應陣列頭 0 * 4bytes 位移量的記憶體位址 **希望這邊的基本觀念你一定要釐清，Orange 誠心建議哦!** ## 指標與一維陣列先看個例子。 ```cpp= int main(){ int a[10]; // 陣列是連續配置 int *p = a; for(int i = 0; i < 10; i++){ a[i] = i; cout << a[i] << " " << &a[i] << endl; } cout << endl; for(int i = 0; i < 10; i++){ cout << p[i] << " " << &p[i] << endl; } return 0; } ``` 上面例子的第 2 行，我們把陣列頭的記憶體位址也指派給了指標變數 p，透過剛剛上一段內容的講解，你應該可以理解 `[]` 的運作了，所以上方這段程式碼會印出甚麼呢? ![](https://i.imgur.com/riXyIyW.png) 居然位址跟數值都一模一樣，所以在第 3 行到底發生甚麼事呢，可以看下圖。 ![](https://i.imgur.com/3IGDLCP.png) 第 3 行把 a 的陣列頭位址 assign 給了指標變數 p(藍筆)，所以現在對於指標變數 p 而言，都能夠用 `[]` 去追相對應位移量位置的數值跟取址了，至於原因就是上面的觀念釐清摟! 所以 `&p[0]` 的記憶體位址會印出的是如圖中的 `0x123`。 ## 指標 with 1-d(dimension) dynamic array dynamic array，中文直翻就是動態陣列，而他也確實就是這樣的意思，主要就是讓我們自己去動態配置陣列出來，不囉嗦直接看語法吧! ```cpp= // 小括號中括號看清楚 // 宣告一個指標變數並配置一個整數給他所儲存的位址指向的記憶體空間 int *p1 = new int(5); // 宣告一個指標變數並配置一個大小為 5 陣列 int *p2 = new int[5]; ``` 雖然宣告陣列大小為 5，但是指標變數只能儲存一個指標(記憶體位址)，所以這邊的 5 代表的是允許的位移量，所以可以允許 0~4。也就是 p2[0]、p2[1]、p2[2]、p2[3]、p2[4]。 **而指標變數 p2 儲存的記憶體位址是陣列頭的記憶體位址!** 畫成圖就會像這樣。 ![](https://i.imgur.com/6yWQNGg.png) 來看個例子。 ```cpp= int main(){ int arr_size; cin >> arr_size; int *p = new int[arr_size]{0}; // 大括號這個就是為陣列的每一格設定初始值 for(int i = 0; i < arr_size; i++){ p[i] = i; cout << "value of p[" < 我相信眼尖的同學已經發現了 `&p+i` 這個怪東西了，這份筆記的最後會來談這個，還有 `*p+i`。 > [name=Orange] 上面例子的輸出我們來看一下~ ![](https://i.imgur.com/FZdnBwX.png) 在記憶體會怎麼展現呢? 希望你看懂這張圖，`&p+i` 可以先不懂沒關係。 > 圖沒有按照 stack 或 heap 來話，只是示意。 > 看不懂可以忽略上面這句話! > [name=Orange] ![](https://i.imgur.com/CiuvZef.png) ### 請養成 delete 的好習慣!! 在上方例子的第 11 行我們做了把這個動態一維陣列刪掉的動作，對於電腦來說，new 出來的記憶體是不會被自動回收的，要我們手動來回收。一維陣列記憶體回收語法如下: ```cpp= delete [] p; ``` p 是你配置的指標變數的名稱，而語法就是長這樣，沒有任何原因。中括號一定是放在中間。 ## 重要內容! 運算子的優先權! 這邊的內容相當重要，但我獨立成一篇筆記，請看這邊 -> [我是這邊](https://hackmd.io/@ndhu-programming-2021/HJAkAf8AF) 請記得回來看下面的指標運算喔! ## [補充，選擇性閱讀] 指標的運算 pointer arithmetic 相信上面的 `&p+i` 困擾著不少人。在指標的世界裡，當你對他做取址或取值的動作的時候，C++ 提供了指標的運算這個功能，讓你能夠透過語法去相對應的記憶體位移量的位址取址或取值。 ### 取址對於一個指標變數 p 而言，`&p` 是取得他所在的記憶體位址，`&p+i`，i 為0、1、2....的整數實數，則是跟上面 `［]` 一樣代表位移量的意思，在 C++ 裡一個記憶體位址需要 8 bytes 儲存，所以 `+i` 就是表示位移 i * 8bytes 個記憶體的意思。 `&p+1` 相對於 `&p` 的記憶體位址位移 1 * 8bytes `&p+2` 相對於 `&p` 的記憶體位址位移 2 * 8bytes，依此類推。 ### 取值那 `*(p+i)` 又是怎麼運作的呢? 還記得 `*p` 我們說過是取得指標變數 p 儲存的指標所指向的位址的值。而 `*(p+1)` 就是取得指標變數 p 所儲存的記憶體位址位移 1 * 4bytes 所儲存的值。而 `*(p+2)` 就是取得指標變數 p 所儲存的記憶體位址位移 2 * 4bytes 所儲存的值。，依此類推。 ```cpp= int main(){ int *p = new int[10]; for(int i = 0; i < 10; i++){ *(p+i) = i; } } ``` ## Reference 下面的參考資料都比我們的筆記更難，歡迎大家挑戰挑戰~ 你不一定能夠全部看懂，但我相信看懂部分是可以的，隨著時間越來越多，你會看懂更多。 [簡單搞懂指標(pointer)、指標陣列(pointers of array, int *foo[]) 與指向陣列的指標 (pointer to array, int (*bar)[])](http://hackgrass.blogspot.com/2018/03/c-pointerint-foo-int-bar.html)