# 2018q3 Homework1
contributed by < `littlepee` >

:::danger
你的提問呢？回顧你過去開發的程式，難道沒想到概念上有衝突或者激發出更多想法嗎？
:notes: jserv
:::

## 為什麼要深入學習 C 語言？
* 第一個 C 語言編譯器如何編寫的?
* 可能是用 B 語言或是混合 B 語言與 PDP 組合語言編寫的
* 先編寫一個C語言的子集的編譯器，在通過這個子及去慢慢完成完整的C語言編譯器
* 先創造出最基本子集 C0，再利用 C~0~ 去創造出 C~1~，再從 C~1~ 創造出 C~2~，設計漸漸複雜，一直開發到足夠強大的 C~N~，便可開發出 C語言編譯器
:::info
關於「可能是用 B 語言或是混合 B 語言與 PDP 組合語言編寫的」，可參閱 Bell Labs 過往的材料，有提及 ancient C compilers 的緣由 (和這猜想有出入)
:notes: jserv
:::

## 指標篇

* " & " 不要都念成 "and"，在指標操作的時候，要念成 “address of”
* 沒有「雙指標」只有「指標的指標」
* C 語言中只有 call-by-value
* 「指標的指標」英文是 "a pointer of a pointer"
* Pointers vs. Arrays
* in declaration
* extern, 如 `extern char x[];` => 不能變更為 pointer 的形式
* definition/statement, 如 `char x[10]` => 不能變更為 pointer 的形式
* (如果10拿掉，就可以換成 pointer。但因為有10，所以是有明確空間，連續10個 bytes 的記憶體空間， pointer 是一個 word 長度記錄了記憶體位址，所以不能互換)
* parameter of function, 如 `func(char x[])` => 可變更為 pointer 的形式 => `func(char *x)`
* in expression
* array 與 pointer 可以互換

int main() {
    int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%d %d %d %d\n", x[4], *(x + 4), *(4 + x), 4[x]);
}

## 函式呼叫篇
* C 語言中不允許 "nested function"
* Process 和 C 程式的關聯
* instructions : 從 object file (ELF) map 到 process 的 program code
* static data : 靜態初始化的變數
* BSS : 未初始化的變數或資料
* 可用 `size` 指令來觀察
* Heap 或 data segment : 執行時期才動態配置的空間
* sbrk 系統呼叫 (sbrk = set break) 
* malloc/free 實際的實做透過 sbrk 系統呼叫
* 藏在 Heap 裡的細節
* free() 釋放的是 pointer 指向位於 heap 的連續記憶體，而非 pointer 本身佔有的記憶體 (*ptr)。

舉例來說：

#include <stdlib.h>
int main() {
    int *p = (int *) malloc(1024);
    free(p);
    free(p);
    return 0;
}

編譯不會有錯誤，但運作時會失敗：

*** Error in './free': double free or corruption (top):
0x000000000067a010 ***

倘若改為以下：

#include <stdlib.h>
int main() {
    int *p = (int *) malloc(1024);
    free(p);
    p = NULL;
    free(p);
    return 0;
}

則會編譯和執行都成功。

因此，為了防止對同一個 pointer 作 free() 兩次的操作，而導致程式失敗，free() 後應該設定為 NULL。

## 遞迴呼叫篇
* 遞迴程式設計
* 遞迴法 (Recursive)
* 非遞迴法 (Iterative)
* 可縮減原先使用遞迴法的函式呼叫造成之執行時期開銷
* Tail recursion
* 可加速原先之遞迴，可減少一半的資料回傳，而概念上是運用從第一次 call function 後即開始計算值，不像之前的遞迴需 call function 至中止條件後才開始計算值，再依序傳回到最上層，因此可大幅降低時間，減少 stack 使用量。

## 前置處理器應用篇

* `#`: [Stringification/Stringizing(字串化)](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html)
* `##`: [concatenation(連結，接續)](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html)

#define DECLARE_OBJECT(name) \
	struct __##name##_node; \
	typedef struct __##name##_node *name##_node; \
	struct __##name##_node { \
	name element; \
	name##_node next; \
	}; \
	void append_##name(const name *X, name##_node *list); \
	void delete_##name##_list(name##_node *list);

DECLARE_OBJECT(light)
DECLARE_OBJECT(rectangular)
DECLARE_OBJECT(sphere)

light 在 `DECLARE_OBJECT(light)` 中會取代 name，因此會產生以下程式碼：

struct __light_node;
typedef struct __light_node *light_node;
struct __light_node { light element; light_node next; };
void append_light(const light *X, light_node *list);
void delete_light_list(light_node *list);

## linked list 和非連續記憶體操作
* circular linked list
* [龜兔賽跑](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4)
* 一、尋找循環長度的倍數：
* 龜兔從起點同時出發，龜走一步、兔就走兩步。由於兔比龜快，當龜兔皆進入循環之中，兔必然領先數圈、從後方追上龜。
* 當龜兔相遇，龜兔的行走距離差，即是循環長度的倍數。龜一倍速、兔兩倍速，龜兔的行走距離差，剛好是龜的行進距離。龜的行進距離即是循環長度的倍數。
* 二、尋找循環起點：
* 龜退回起點，兔原地待命，龜兔同時出發，龜走一步、兔走一步。龜兔相遇之處即是循環起點。
* 三、尋找循環長度：
* 從循環之中任意一處出發，一次走一步，繞一圈回到原處，即得循環長度。
* 時間複雜度：
* 令 μ 是出發起點到循環起點的距離， λ 是循環長度。龜最多走 μ + λ 步，兔最多走 2μ + 2λ 步，時間複雜度為 3μ + 3λ = O(μ + λ) 。