風月春秋的程式筆記

Appearance

指標的應用 ​

雖然說了不少指標的基礎，但是很多時候，真正困難的是各種指標的使用。

動態記憶體管理 (Dynamic Memory Allocation) ​

在 C 語言中，手動管理記憶體是通往高階開發者的必經之路。如果說之前的指標是「找到現有的房子」，那麼動態記憶體管理就是「根據需求臨時蓋一棟房子」。

進階: 記憶體的位置差異

動態請求記憶體的位置是在 heap，使用 first fit 找合適的位置，類似於拼拼圖時，找到合適的一塊就直接放下去，記憶體是找到一塊長度足夠的就劃分。

而一般的變數宣告記憶體是存在 stack，大致上就是看成是一行一行執行，到哪裡就在當前的 stack 頂端多疊一塊。

優缺點 ​

手動管理記憶體雖然增加了心智負擔，但帶來了巨大的好處：

  1. 更大的空間: 想比一般陣列宣告 106 的極限，動態宣告的極限是 107
  2. 合適的大小: 如果使用傳統做法，對於從 10 個到 1e5 個的內容，只能選擇宣告一個大的陣列(1e5)，時常浪費空間；動態做法則能夠根據需求劃分剛好的空間

權力越大，責任越大。不當的指標操作是資安漏洞的主要來源：

  1. 懸空指標 (dangling pointer): 指標指向一個已經被釋放的變數的位址，可以理解為住戶搬走了，但登記的各種資料還在
  2. 記憶體洩漏 (memory leak): 指標被更改了，但是指向的變數沒有被釋放，可以理解為買了一個包裹，但忘了領，堆在物流中心
  3. 請求失敗: 要了一塊記憶體，但失敗了，卻直接開始使用
  4. 可讀性: 過多的 malloc/free 夾雜在邏輯中，會讓程式碼變得像迷宮一樣難以追蹤。

核心函數工具箱 (<stdlib.h>) ​

函數功能備註
malloc請求一塊連續空間不保證內容，裡面是殘留的垃圾值
calloc請求一塊空間，並自動歸零格式為 (個數, 大小)
realloc調整已申請空間的大小可能會把資料搬到全新的地址
free釋放記憶體歸還給系統釋放後應立即將指標設為 NULL(也就是 0)

記憶體請求有可能失敗，因此在使用前應使用 if 檢查。

實戰示範 ​

c
// sizeof: int 的 byte 數
int *p1 = malloc(4*sizeof(int)); // 4 int 的陣列
free(p1);
p1 = NULL; // 防止程式誤用已釋放的記憶體
int *p2 = calloc(3, sizeof(int));// {0, 0, 0}
if (p2) p2[1] = 1;
int *tmp = realloc(p2, 4*sizeof(int)); // 擴充成四個
if (tmp) { // 分配成功
    p2 = tmp; // 更新地址
    // 此時內容為 {0, 1, 0, 未定義}
}
else { // 分配失敗
    // tmp = NULL
    // p2 沒有釋放
    free(p2);
    p2 = NULL;
}

指標的指標示範 ​

3x3 array example

c
int **ptr = NULL;
ptr = malloc(3 * sizeof(int*));
if (ptr)
    for (int i = 0; i < 3; i++) 
        ptr[i] = malloc(3 * sizeof(int));

多層指標需要多層 free，否則會有懸空指標

指標與函數 ​

前面在 陣列 部分有說過，因為陣列名是指標，因此作為參數傳遞會讓 function 可以更改其中的數值，解決函數回傳只能有一個數值的痛點與傳遞參數過大的問題，降低性能消耗與記憶體使用(尤其在遞迴情境)。

遞迴範例 ​

我寫過比較難的功課: 算 fibonacci 數

題幹:
給 k: [1, 93]，求第 k 個費波那契數
formula:

fib(2k) = fib(k) * [2 * fib(k + 1) - fib(k)]
fib(2k + 1) = fib(k) * fib(k) + fib(k + 1) * fib(k + 1)

測試程式:

c
#include <stdio.h>

typedef unsigned long long uint64_t;
void fib_fast_doubling(unsigned k, uint64_t *f2k, uint64_t *f2k1);

int main()
{
    unsigned k;
    scanf("%u", &k);
    uint64_t f2k, f2k1;
    fib_fast_doubling(k / 2, &f2k, &f2k1);
    printf("%llu", (k & 0x1) ? f2k1 : f2k);
    return 0;
}

實作 fib_fast_doubling 函數，並在 1s 與 5000KB 內完成。

code
c
void fib_fast_doubling(unsigned k, uint64_t *f2k, uint64_t *f2k1)
{
    if(k == 0)
    {
        *f2k1 = 1;
        *f2k = 1;
        return;
    }
    else if(k == 1)
    {
        *f2k1 = 2;
        *f2k = 1;
        return;
    }
    uint64_t ori,ori1;
    if(k%2)
    {
        fib_fast_doubling(k/2,f2k,f2k1);
        ori1 = *f2k1;
        fib_fast_doubling(k/2+1,f2k,f2k1);
        ori = *f2k;
        *f2k = ori1 * (2 * ori - ori1);
        *f2k1 = ori1 * ori1 + ori * ori;
    }
    else
    {
        fib_fast_doubling(k/2,f2k,f2k1);
        ori1 = *f2k * *f2k + *f2k1 * *f2k1;
        ori = *f2k * (2 * *f2k1 - *f2k);
        *f2k = ori;
        *f2k1 = ori1;
    }
}