5 陣列與預處理命令

課程內容#

陣列的定義與初始化#

定義：存儲一個固定大小的相同類型元素的順序集合
初始化
- int a[100] = {2, 3}; // a[0] = 2, a[1] = 3
- int a [100] = {0}; // 陣列的清空操作：陣列每一位都初始化為 0 值
  - 其實只是定義了第 0 位為 0，但會引發其他位自動初始化為 0
其他
- 從下標 0 開始
- 陣列空間大小：所有變量大小的總和
- 存儲空間連續
  - int a[3]

地址	0123	4567	89[10][11]
元素	a[0]	a[1]	a[2]

- 上述定義的陣列都屬於靜態陣列
  - 不建議的操作：int n; scanf ("% d", &n); int arr (n);
- 下標 - 值的映射
  - 已知索引，取值的時間效率是 O (1)

素數篩#

核心思想：用素數去枚舉掉所有合數

當作一個算法框架去學習，有很多演變
素數：只有 1 和它本身兩個因子
- 1 既不是素數也不是合數
- 2 是最小的素數
- 素數一定是奇數（除了 2），奇數不一定是素數
借助陣列結構。陣列可以表示三種信息：
- 下標
- 下標映射的值
- 值的正負
算法衡量標準及該算法性能
- 空間複雜度：O (N)，有 N 個數字就開辟大小為 N 的陣列
- 時間複雜度：O (N * logN)、O (N * loglogN)-- 優化版，趨近於 O (N)
  - 不是 O (N)，是因為有重複標記情況
  - log 以誰為底不重要，以 2 為底就已經很小了
  - 怎麼計算：均攤思想，根據時間複雜度與概率來算期望...
打標記：素數，0；合數，1
- 借助陣列的兩種狀態信息：下標→數字，值→標記
素數篩擴展
- 求一個範圍內所有數字的最小、最大素因子
- 比如 12：2、3

線性篩#

從歐拉第 7 題入手
- 求第 10001 個素數
- 可以使用枚舉法 O (N * sqrt (N))、素數篩
- 估算第 10001 位素數大小不會超過多少？
  - 規律：20 萬以內排名的素數，其範圍不會超過排名的 20 倍
來自素數篩的思考
- 6 被標記了幾次？2 次：2、3
- 30 被標記了幾次？3 次：2、3、5
- 如果一個數字 N 的素數分解式中，含有 m 種不同的素數，N 被標記幾次？m 次
- 那麼可不可以只被標記 1 次呢？👇
線性篩
- 空間、時間都是O(n)
- 用一個整數 M 去標記合數 N
- M、N 的關係符合四個性質
  1. N 的因子中最小的素數為 p
  2. N = p * M
  3. ❗ p 一定小於等於M 中最小的素因子
    - 類似七擒孟獲的道理，只在最後一次標記
  4. 利用 M * P' （所有不大於【M 的最小素數】的素數集合）標記 N1、N2、...

【i 和 iii 有點等價的意味】

代碼
- 核心思想：N = M（↑盡可能大） * p（↓盡可能小）
  - 枚舉 M，慢慢增大 p 值，直到 p 值滿足終止條件：性質 iii
  - 相比 M，p 更好控制！
- 避免重複的關鍵就是第 iii 條性質
- 注意：雖然有兩層 for 循環，但時間複雜度是 O (N)，因為第二層 for 循環裡的 break，整個陣列就遍歷一次
- 與素數篩初始條件優化為 i * i 的區別是？素數篩還是有重複標記的情況

二分查找法#

順序查找→折半查找：O (N)→O (logN)
關鍵前提：查找序列單調
代碼
- 主要演示三個部分：①在陣列中二分查找 ②在函數中二分查找 ③
- 對於函數的二分查找實現部分
  - 應該可以把 binary_search_f_i 和 binary_search_f_d 統一為一個函數
  - 關注後面的學習，可否辨識傳入的函數指針的返回類型
  - 但實現部分有差別，因此意義應該不大
- main 函數中被註釋的代碼，測試的是在陣列與函數中二分查找的結果，如下：
- - 利用函數做二分查找的範圍可以更靈活
- double 類型判等：用差值小於 EPSL 判斷
  - 記得 #undef EPSL
- 細節詳見註釋
  - 學習順序：binary_search 👉 binary_search_f_i 👉 binary_search_f_d
遞歸版代碼
- 函數的參數與迭代方式有所不同，需確定查找邊界

牛頓迭代法#

目的：求解 f (x) = 0 時 x 的值
條件：函數可導；收斂
迭代一次公式：x2 = x1 - f(x1) / f'(x1)
核心思想：每迭代一次，x2 會比 x1 更接近要求的 x 的值，直到 f (x) 的絕對值比 EPSL 小即可
代碼
- ⭐循環終止條件記得取絕對值！
- x = n / 2.0 這個初始值是固定的嗎？
  - 不是
  - 這個值是設想的 x 最近的解，在解的左右兩側都沒問題
  - 不過不能取 0 哈，因為導數為 0，會導致除數為 0
- 對 NewTon 函數做一個包裝，得到 my_sqrt 函數
- 不是二分查找！二分需要單調～

預處理命令#

#開頭的命令
- #include <stdio.h> →在預處理時，將 stdio.h 文件原封不動地拷貝到當前位置
宏定義

定義符號常量：常量→符號。

#define PI 3.1415926
#define MAX_N 1000

便於批量修改值

傻瓜表達式

#define MAX(a, b) (a) > (b) ? (a) : (b)
#define S(a, b) a * b

傻 eg. #define S (a, b) a * b
- S (2 + 3, 4 + 5) → 簡單替換 → 2 + 3 * 4 + 5 等價於 2 + (3 * 4) + 5
- 在替換過程中不做任何運算！

定義代碼段（高級）

#define P(a) { \
    printf("%d\n", a); \
}

宏只能接受一行定義，換行需要使用反斜杠 '' （連接符）
預定義的宏（系統封裝好的）
- 宏的兩端是兩個下劃線
- DATA、TIME：預編譯時的日期、時間，不預處理就不會改變
  - 可以實現類似指紋識別的功能？預存儲的關係？
- 非標準宏：有的環境可能未定義，不同環境的標準可能不同，所以可移植性不好
  - 怎麼處理呢？可以使用條件式編譯👇
條件式編譯
- #ifdef DEBUG
  - 說明：是否定義了 DEBUG 宏
  - 注意：DEBUG 一定是一個宏，而不是變量！
    - 宏在預編譯後生效，變量在編譯後生效
- #ifndef DEBUG 是否沒定義
- #if MAX_N == 5 宏 MAX_N 是否等於 5
  - 可在遊戲中判斷用戶手機版本
- #elif MAX_N == 4
- #else
- 一定要以 #endif結束！！！
  - 【編碼規範】
  - 如同 va_start、va_end
簡易編譯過程
- C 源碼 .c
👇預處理階段 (預編譯) (gcc -E)：包含頭文件、宏替換等預處理命令，替換所有的 #命令
- 編譯源碼 .c
👇語法檢查、編譯 (gcc –S)
- 匯編源碼 .s、.asm
👇匯編 (gcc -c)
- 對象文件 .o（linux 下）或 .obj（windows 下）
👇鏈接 (gcc)
- 可執行程序 a.out（linux 下）或 a.exe（windows 下）（二進制文件）
PS：最後還有一個裝載過程，主要是建立可執行文件、虛擬地址、物理地址三者的映射關係

字符串#

字符數組
- 定義：char str [size];
- 初始化

char str[] = "hello world";
char str[size] = {'h', 'e', 'l', 'l', 'o'};

Line1
- [] 裡可不指明大小，系統會自動算
- 系統會自動加終止符 '\0'，字符數組大小：11+1
Line2
- size 至少為 6，考慮終止符 '\0' 占一位
  - 多餘的位都補 '\0'
- 如果不加 size，就要在數組最後加字符 '\0'，系統不會自動加
'\0'
- 一個終止標記位
- 底層對應 0 值：false
- '\0' 可作為終止條件，如：for 循環讀入字符串
字符後面會有 '\0' 嗎？沒有，是字符串的特性
相關操作
- 頭文件：<string.h>
- strlen(str)
  - 返回字符 '\0' 的下標，長度不含 '\0'
  - PS：sizeof () 會考慮變量實實在在占用的內存，會考慮 '\0'，單位為字節
- strcmp(str1, str2);
  - 按字典序比較 ASCII 碼大小
    - 從第一位開始
  - 返回值為差值（相等即為 0）
- strcpy(dest, src);
- 比較和拷貝的結束標誌：找字符 '\0'，如果 '\0' 丟了呢？所以有
- 更安全的比較與拷貝：strncmp、strncpy
  - 針對 '\0' 不小心丟了的情況
  - 最多比較、拷貝 n 個字節
- 內存相關
  - memset(str, c, n)
  - 不局限於字符串操作，str 對應一個地址即可
    - 這裡舉例對數組的操作
    - memset(arr, 0, sizeof(arr))
      - 初始化，清空為 0
    - memset(arr, 1, sizeof(arr))
      - 這裡不是把每位置為 1，因為操作的是每個字節，而 int 占 4 個字節
      - 0000...01000...001000....0001...
    - memset(arr, -1, sizeof(arr))
      - 確實是 - 1，因為 - 1 在 1 個字節裡就是 11111111
頭文件：<stdio.h>
兩者結合可以做格式拼接：一個讀入，一個輸出
scanf 裡的 str1 類比於終端的輸入，它被換成了字符串輸入

隨堂練習#

實現沒有 BUG 的 MAX 宏#

思路：①手算正確輸出👉②先寫最簡單的有 BUG 的實現，並有友好的輸出顯示👉③針對錯誤輸出依次找問題，解決
①正確輸出如圖
②先寫有 BUG 的，並實現友好的輸出顯示

#define MAX(a, b) a > b ? a : b
#define P(func) { \
    printf("%s = %d\n", #func, func); \
}

Line2-4：友好輸出顯示
- #func 直接輸出其字符串表示
- 不加 #就是調用其值
③針對錯誤輸出依次找問題，解決
- （解決 BUG 的順序也很重要，不過這裡 BUG 的順序很好）
- 這個時候看下錯誤情況
- 因為宏導致的錯誤，可以看預處理後的文件
  - gcc -E *.c 輸出預處理替換掉宏之後的代碼
- 第一次糾錯
  - 解決：可以將紅框處用括號提高優先級

#define MAX(a, b) (a > b ? a : b)

- 第二次糾錯
  - 第四個結果為 2，思路如上圖
  - 注意條件運算符 '?:'
    - 優先級很低：比 '>' 低
    - 有多個 '?:' 存在時，其結合方向是右到左
  - 解決：對於每個變量再用括號提高優先級

#define MAX(a, b) ((a) > (b) ? (a) : (b))

- 第三次糾錯
  - a++ 運行了兩次
    - 實際應該先拿 a 作比較，再進行 a+1
  - 解決：把 ++ 運算前的值先賦給一個變量；定義成一個代碼段生成的表達式

#define MAX(a, b) ({\
    __typeof(a) _a = (a);\
    __typeof(b) _b = (b);\
    _a > _b ? _a : _b;\
})

__typeof (a++) 裡的 a++ 執行嗎？
- 用於表達式的時候不執行，只是取出其類型
({}) 表達式
- 值為小括號內最後一個表達式的值，數據類型為最後一個表達式的數據類型
- 參考C 語言的小括號和花括號結合使用 && 複合語句-CSDN
- 去掉 {} 或者 () 都不行！
  - () 裡只能放逗號表達式
    - 逗號表達式取最後一個式子的值
  - {} 是代碼段，沒有返回值
    - 若直接定義成宏函數
    - 直接 printf 輸出，就失去了 MAX 返回最大值的本質
    - ❓用 return 返回值
      - 需要聲明
      - 但直接用表達式代表返回值更聰明
最終版代碼

結果全部正確！

實現打印 LOG 宏#

代碼
- 交付工作時，免去 log 信息，可以使用條件式編譯
  - 編譯時使用 "gcc -DDEBUG" 可以傳入 DEBUG 宏定義
  - #else 後面定義一個空的宏替換
- 變參宏
  - 變參 '...' 取一個名字即可。eg. args...
- 宏中 "#"、"##" 使用
  - "#"：取字符串
  - "##"：連接
    - 解決 log 宏傳入是空字符的情況：如果是空，frm 後面的 "," 會自動去除，可參考預編譯結果👇
    - 參考替換文本宏-cppreference
    - ab 和 a##b 的區別
      - ab 不會將 a、b 代入再連接
      - 需 ## 連接的 a、b 對應的傳入參數可以不定義
        
        預處理就會將這些未定義的變量名連接起來，連接後的變量名定義過即可

亮點筆記#

代碼演示#

素數篩#

代碼

對偶邏輯，控制縮進
- if continue
prime 數組前部分可以同時計數和存儲（整體用來打標記）
- 一開始 prime [0]、prime [1] 並沒有用，空閒著
- 不會出現超車的問題：偶數肯定是合數，素數至少隔一個才出現
第二個 for 循環的初始條件可以優化
- 初始條件：i * 2 → i * i
- 時間效率：O (Nlogn)→O (Nlognlogn)
- 因為比 i * i 小的合數肯定已經被比 i 小的數標記過了
  - 這樣減少了前面一部分重複標記的次數，但不是完全
  - 完全避免重複標記要使用線性篩
- 危險點：i * i 指數增長，更可能溢出int 能存儲的最大值
  - 是否可以提前加一個判斷？不過可能帶來更大的耗時
  - 換一個上限更高的存儲 i * i 的數據類型

陣列#

代碼

輸出
- 細節👇

聲明、初始化#

編程技巧：多開 5 位，避免溢出，可以降低 bug 率

#define max_n 100
int arr[max_n + 5];

在函數內的變量空間都定義在棧區
- 棧區可以用羽毛球筒去理解，後進先出
- 棧區大小 (默認)：8MB≈800 萬 Byte (字節)
在函數內聲明的陣列可能是不乾淨的，需手動初始化
- = {0};
- scanf 讀入

for (int i = 0; i < max_n; i++) {
scanf("%d",arr + i);
}

- arr + i 等價於 &arr [i]& 不能少！
在函數外聲明的陣列
- 系統會自動將其清空為 0，類似於 = {0} 操作
- 可開辟大小受電腦內存限制，基本無限制
malloc、calloc、realloc 定義的陣列在堆區，即使在函數內部定義

占用空間、地址#

sizeof () 對應的控制字符是 % lu，無符號長整型
陣列名 arr 代表的就是陣列的首地址，即 & arr [0]

printf ("% p % p\n", arr, &arr [0]); // 地址值一樣

地址 + 1 偏移多少字節取決於地址表示的元素字節數

傳參#

條件：外部和函數裡參數表現形式一致
- 一維陣列：int arr [100];
  - void func(int *num)
- 二維陣列：int arr2[100][100];
  - void func2 (int **num) 報警告
    - num + 1 和 arr + 1 的表現形式不一致
    - num 是指向 int 指針的指針
    - num 和 num +1 的地址相差一個【指針】的大小，64 位操作系統裡是 8 個字節
    - arr 和 arr + 1 的地址相差一個【一維陣列】的大小，4 * 100 字節
  - void func2(int (*num)[100]) 可以
- 三維陣列：int arr3 [100][100][32]
  - void func3(int (*num)[100][32]) 可以
  - (*num)[100][32] 可以寫成 num [][100][32]
    - (*num) 和 num [] 表現形式一樣，但本質其實不一樣
❓q 指向的是 nil？就是 0x0

附加知識點#

陣列可以表示三種信息
int arr [100]; //arr 作為參數傳到函數，是作為陣列首元素的地址的
1 取反是 - 2？推導一下
- 1： 0000...001
- 取反：1111...110
- 符號位不變，取反加一得：1000...010
- 即 - 2
- 結論：所有正整數的按位取反是其本身 + 1 的負數
包含 <math.h> 的源文件，在編譯時添加 - lm，使用 gcc *.c -lm
編碼習慣，一行不超過 80 個字符
控制字符 "%X"：大寫的十六進制

思考點#

函數與宏誰更厲害？
- 宏能生成函數，宏可不是函數的爸爸？

Tips#

vim 自動補齊頭文件的格式修改：加空格
- 進入～/.vimrc 文件，修改 SetTitle () 裡對應的格式即可
宏的展開、嵌套，自己去摸索
參考工具書第 8 章 8.1、8.4 以及第 15 章

Bo2SS

5 陣列與預處理命令

課程內容#

陣列的定義與初始化#

素數篩#

線性篩#

二分查找法#

牛頓迭代法#

預處理命令#

字符串#

隨堂練習#

實現沒有 BUG 的 MAX 宏#

實現打印 LOG 宏#

亮點筆記#

代碼演示#

素數篩#

陣列#

聲明、初始化#

占用空間、地址#

傳參#

附加知識點#

思考點#

Tips#

課程速記#