---
tags: C
---
# C Supplements
## bitwise shift operator
https://docs.microsoft.com/zh-tw/cpp/c-language/bitwise-shift-operators?view=vs-2019
* 重點（？）
## sort ref. (考試會附)
> qsort() is in <stdlib.h>
>
> Prototype:
>
> `void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));`
>
> the last parameter is a function pointer that return int type.
* sort struct by qsort()
* 這篇裡面有講 qsort() 和 sort() 兩個函式的使用
* sort() 是 C++ 才有的函式，可以看 qsort() 的使用就好。 https://www.twblogs.net/a/5b7cf76c2b71770a43dd564a
* sort struct by bubble sort
* 不想用 stdlib.h 提供的 qsort() 也可以自己手刻，下面附上 bubble sort 的例子。
* http://www.cprogrammingnotes.com/question/sorting-structure-array.html
---
## linked list
:::warning
### [👉測驗](https://hackmd.io/@jserv/SyK-WApKM?type=view)
> 如果你點進去覺得這些題目太簡單，下面的東西就不用看了。
>
> 來自 Jserv 2018 [系統軟體系列課程](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
* [參考解答](https://hackmd.io/@LinYunWen/HyELy5bTz)
* 勘誤：參考解答沒有錯，助教眼殘
:::
### Basic linked list
* Leetcode ，辦個帳號就可以使用他的 online judge 了
* 建議可以多寫幾題看看，來熟悉實作一個 linked list 需要包含哪些函式：https://leetcode.com/tag/linked-list/
* 至少應該寫完這兩題 <b><span style="color:red">(小考會考)</span></b>
* [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
* [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)
* [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)
* [直播錄影 1:14:26 - 1:18:50](https://youtu.be/0B0GNPv02zg?t=6264)
* 建議看完 circular linked list 的段落，和上面兩題 cycle finding 有關 <b><span style="color:red">(小考會考)</span></b>，
其他的難度偏高，建議修完作業系統再看。
* [Cycle Finding: Floyd's Algorithm](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4) <b><span style="color:red">(小考會考)</span></b>
### Advanced Topics
* [使用 linked list 實作 bubble sort](https://hackmd.io/s/BklGm1MhZ)
* 這太難ㄌ不會考，可以在家練。
### Reference
> 可以參考別人寫好的 linked list
* [singly linked list](https://github.com/FremdSprach/csinglylist/blob/master/src/list.c)
* doubly linked list
* [隨便進去點一個翻翻看吧，太多了](https://github.com/search?l=C&q=doubly+linked+list&type=Repositories)
* [dlist: Type-safe single file linked list](https://github.com/laserswald/dlist)
---
---
---
---
---
## Ch17. Dynamic memory allocation
::: success
### Dynamic memory allocation
:::
* [GNU manual](https://linux.die.net/man/3/malloc)
* prototype
```c
void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
```
* 我們已知 `malloc()` 會回傳一塊沒有歸零過的記憶體， `calloc()` 會回傳一塊有做歸零的記憶體。
* 為什麼還需要存在兩個差不多的函式？
* 理想上，malloc() 是比 calloc() 快的 (但實務上常常不是)
* 如果 `calloc()` 沒有被作業系統加速 (e.g. 如果是在資源缺乏的小型嵌入式系統)，則使用 `malloc()` 還是比較有效率。
* 留下 `malloc()` 給予編譯器和 C programmer 一些彈性，可以以此做最佳化。
* `calloc()` 是否等於 `malloc() + memset(0)`？
* 不是
* `malloc()` 會有 overflow 問題，`calloc()` 有做防呆處理
* `calloc()` 實際上沒有去呼叫 `memset(0)`，而是去跟作業系統要早就歸零好的記憶體。
### why calloc exist?
* https://vorpus.org/blog/why-does-calloc-exist/
---
---
---
---
---
## Ch 16. struct, union, enum
> 以下皆假設在 64 位元的電腦上。編譯器為 gcc 至少 7.3 版
### Apply `sizeof` operator on basic types
* [下載連結](https://people.cs.nctu.edu.tw/~ysl/2019C/basic_size.c)
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main(void){
printf("-----------------------------------------------------------\n"
"-- Print size of basic types -----------------------------\n"
"-----------------------------------------------------------\n");
printf("sizeof char: %lu\n"
"sizeof unsigned char: %lu\n"
"sizeof short: %lu\n"
"sizeof unsigned short: %lu\n"
"sizeof int: %lu\n"
"sizeof long: %lu\n"
"sizeof unsigned int: %lu\n"
"sizeof float: %lu\n"
"sizeof long long: %lu\n"
"sizeof unsigned long long: %lu\n"
"sizeof double: %lu\n",
sizeof(char),
sizeof(unsigned char),
sizeof(short),
sizeof(unsigned short),
sizeof(int),
sizeof(long),
sizeof(unsigned int),
sizeof(float),
sizeof(long long),
sizeof(unsigned long long),
sizeof(double));
printf("-----------------------------------------------------------\n"
"-- sizeof pointer is constant (8bytes in 64-bit machine) --\n"
"-----------------------------------------------------------\n");
printf("sizeof char* %lu\n"
"sizeof int* %lu\n"
"sizeof float* %lu\n", sizeof(char*),
sizeof(int*),
sizeof(float*));
printf("-----------------------------------------------------------\n"
"-- Using exact-width integer types in <stdint.h> --------\n"
"-----------------------------------------------------------\n");
printf("sizeof int8_t: %lu\n"
"sizeof uint8_t: %lu\n"
"sizeof int16_t: %lu\n"
"sizeof uint16_t: %lu\n"
"sizeof int32_t: %lu\n"
"sizeof uint32_t: %lu\n"
"sizeof int64_t: %lu\n"
"sizeof uint64_t: %lu\n",
sizeof(int8_t),
sizeof(uint8_t),
sizeof(int16_t),
sizeof(uint16_t),
sizeof(int32_t),
sizeof(uint32_t),
sizeof(int64_t),
sizeof(uint64_t));
return 0;
}
```
* Output
---
:::success
### structure & union
:::
### alignment & padding in C structure
* <b><span style="color:red">(下次小考會考這個)</span></b>
struct 內的 member variable，宣告的順序不同會影響 struct 的大小
http://katecpp.github.io/struct-members-order/
* 連結中每個 chunk 只畫四格是因為他考慮 32 位元 (4 byte) 的電腦
* 若位於 64 位元 (8 byte) 的電腦，alignment 的單位應為一個 chunk 8 格
* https://kezeodsnx.pixnet.net/blog/post/27585076
* https://blog.csdn.net/tianshuai1111/article/details/7576279
### packed structure
可以使 struct size 強制收緊，放棄 alignment/padding
> 課本 P.410, Ch16, Exercise 11, 12 就是直接考慮被 pack 過的 struct
* `#pragma pack(1)`
* Ref: https://bluelove1968.pixnet.net/blog/post/222282988
* `__attribute__((packed))`
* 加在 struct 宣告後面可以強制把 struct size pack 起來
* 1. 原始的 struct A
```c=
struct A{
uint8_t m_byte1;
uint64_t m_long;
uint8_t m_byte2;
uint32_t m_int;
uint8_t m_byte3;
};
```
* 2. 對 `struct A` 增加 `__attribute__((packed))`
```c=
struct A{
uint8_t m_byte1;
uint64_t m_long;
uint8_t m_byte2;
uint32_t m_int;
uint8_t m_byte3;
}__attribute__((packed));
* 範例
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// --- modify this struct --- //
struct A{
uint8_t m_byte1;
uint64_t m_long;
uint8_t m_byte2;
uint32_t m_int;
uint8_t m_byte3;
}__attribute__((packed));
// -------------------------- //
struct A2{
uint8_t *m_byte1;
uint8_t m_byte3;
};
struct B{
struct A* ptr_a;
char c;
};
struct B2{
struct A a_instance;
float fff;
};
union U{
struct A a_instance;
struct A2 a2_instance;
struct B b_instance;
struct B2 b2_instance;
};
int main(void){
printf("%lu %ld "
"%ld %ld %ld\n", sizeof(struct A), sizeof(struct A2),
sizeof(struct B), sizeof(struct B2), sizeof(union U));
return 0;
}
```
*
| | 1. `struct A` | 2. `struct A` 加上 `__attribute__((packed))`|
| --- | -------------- | -------------- |
| 輸出 |`32 16 16 40 40`| `15 16 16 20 24`
---
### Forward Declaration
* 有時候我們可能會頻繁的增減一個 struct 內的變數，但我們不希望一直每次做小更動都要重新編譯整個程式。
* 舉個例子：
* 一開始宣吿一個 struct A，裡面裝一個 unsigned short 變數
```c
struct A{
uint8_t m_byte1;
};
```
* 後來發現一個 unsigned short 不夠用，於是改成這樣：
```c
struct A{
uint8_t m_byte1;
uint8_t m_byte2;
uint8_t m_byte3;
};
```
* 可以把這個 `struct A` 丟進標頭檔，主程式則宣告一個 pointer to struct 指向 `struct A`。
* 主程式(`main.c`) 就不用管它指到的 struct 內部長什麼樣子、有增減哪些變數，
對 main.c 來說， `struct ptr_to_A` 的 size 是固定的，
因 pointer 的 size 固定為 8 bytes (on 64-bit machine)。
* "struct_a.h"
```hpp
#ifndef STRUCT_A_H
#define STRUCT_A_H
struct A
{
uint8_t m_byte1;
uint8_t m_byte2;
uint8_t m_byte3;
};
#endif
```
* "main.c"
```c=
#include "struct_a.h"
//...
struct ptr_to_A{
struct A *ptr;
};
int main(void){
//...
return 0;
}
```
### Example
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
struct SRandomOrder{
uint8_t m_byte1;
uint64_t m_long;
uint8_t m_byte2;
uint32_t m_int;
uint8_t m_byte3;
};
struct SNiceOrder{
uint8_t m_byte1;
uint8_t m_byte2;
uint8_t m_byte3;
uint32_t m_int;
uint64_t m_long;
};
struct SRandomOrderPacked{
uint8_t m_byte1;
uint64_t m_long;
uint8_t m_byte2;
uint32_t m_int;
uint8_t m_byte3;
} __attribute__((packed));
struct SForwardDeclare{
struct SRandomOrder *ptr1;
struct SNiceOrder *ptr2;
struct SRandomOrderPacked *ptr3;
};
int main(void){
printf("%lu %lu %lu %lu\n", sizeof(struct SRandomOrder),
sizeof(struct SNiceOrder),
sizeof(struct SRandomOrderPacked),
sizeof(struct SForwardDeclare));
struct SRandomOrder A;
struct SNiceOrder B;
struct SRandomOrderPacked C;
struct SForwardDeclare F;
// sizeof is a unary operator instead of a function
printf("%lu %lu %lu %lu\n", sizeof A,
sizeof B,
sizeof C,
sizeof F);
return 0;
}
```
* output
:::danger
修正結果：最後一個輸出是三個 pointer 的 size，在 32/64 位元的編譯結果會有差。
:::
* 64-bit machine 結果，pointer 為 8 byte
* 32-bit machine 結果，pointer 為 4 byte
### union
* union 內的變數會共用記憶體。
* downcasting(向下轉型) using union
https://stackoverflow.com/questions/740577/sizeof-a-union-in-c-c
* `float` 是 4 bytes, `unsigned short` 是 2 bytes
* 可以用 union 共享變數 f 和 s 的記憶體，取 s[1] 即向下轉型取 f 的較低 2 bytes
```
union float_cast { unsigned short s[2]; float f; };
```
### combination of struct & union
* Ref: https://blog.csdn.net/selinahuiling/article/details/9046403
* 此篇範例為 32-bit 結果 (long 為 4 byte)，我將 64-bit (long 為 8 byte) 的結果貼在下面。
* e.g. 1
```c
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef union{
long i;
int k[5];
char c;
} DATE;
struct data{
char cc;
int cat;
DATE cow;
char a[6];
};
int main(void){
printf("%lu %lu\n", sizeof(DATE), sizeof(struct data));
return 0;
}
```
* 輸出
`24 40`
* e.g. 2
* 將 long 換為 int32_t
* 其餘換成對應的 stdint type (`char` --> `int8_t`, `int` --> `int32_t`)
```c
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef union{
int32_t i;
int32_t k[5];
int8_t c;
} DATE;
struct data{
int8_t cc;
int32_t cat;
DATE cow;
int8_t a[6];
};
int main(void){
printf("%lu %lu\n", sizeof(DATE), sizeof(struct data));
return 0;
}
```
* 輸出
`20 36`
* e.g. 3
* struct data 內的變數順序並沒調整好，依照 size 升冪排序後
```c
struct data{
int8_t cc;
int8_t a[6];
int32_t cat;
DATE cow;
};
```
* 跟這個是等價的
```c
struct data{
char cc;
char a[6];
int cat;
DATE cow;
};
```
* 其他跟 e.g. 2 一樣，可以看到 sizeof(struct data) 從 36 降成 32
```c
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef union{
int32_t i;
int32_t k[5];
int8_t c;
} DATE;
struct data{
int8_t cc;
int8_t a[6];
int32_t cat;
DATE cow;
};
int main(void){
printf("%lu %lu\n", sizeof(DATE), sizeof(struct data));
return 0;
}
```
* 輸出
`20 32`
---
---
---
---
---
## Others
::: success
## 修完 C 之後...
* 你可以試著開始學 C++，或是
* [你所不知道的 C 語言 系列講座](https://hackmd.io/@sysprog/c-programming?type=view)
* [學一下 GDB，開發 C/C++ 更有效率](https://jasonblog.github.io/note/gdb/tongguo_gdb_xue_xi_c_yu_yan.html)
:::
* 推薦的 C/C++ 開發環境(IDE)：
* 微軟：Visual Studio (Community)
* 學校有提供 Visual Studio (Professional) 授權軟體
* https://ca.nctu.edu.tw/
* 
* 微軟：VS Code
* JetBrains：[CLion](https://www.jetbrains.com/clion/)
* 須用學校信箱申請教育版，系計中電腦有安裝
* vim (這只是文字編輯器，不是開發環境)
* ~~vim 只是比較潮，上面的用起來比較簡單~~
### [你所不知道的 C 語言 (點擊)](https://hackmd.io/@sysprog/c-programming?type=view)
> 其實難度蠻高ㄉ，可能大二大三必修修過再看比較好
* 由成大資工的黃敬群老師 (Jserv) 發起的一系列講座
* [Jserv 與他快樂的小夥伴 粉絲團](https://www.facebook.com/JservFans/)
* 這系列講座對於資工本科的學習高度相關，也因此會牽扯到很多科目
* e.g. 物件導向程式設計、計算機架構、作業系統、編譯器
* 對於理解計算機或數值系統的底層相當有幫助，
理解數值系統，才能把程式寫得更好。
### [通過 GDB 學習 C 語言](https://jasonblog.github.io/note/gdb/tongguo_gdb_xue_xi_c_yu_yan.html)
---
### C/C++ 面試相關
> 很多硬體廠、EDA、嵌入式系統的職缺，面試都會問 C/C++ 相關的題目，有空可以做看看。
* https://hackmd.io/@a110605/By6DscbVM?type=view
* https://mropengate.blogspot.com/2017/08/cc-c.html
* https://ykhorzon.github.io/tw/2018/12/%E6%8C%81%E7%BA%8C%E6%9B%B4%E6%96%B0-c-c-%E5%B8%B8%E8%A6%8B%E9%9D%A2%E8%A9%A6%E5%95%8F%E9%A1%8C%E7%B5%B1%E6%95%B4/
* http://paicc.github.io/2018/09/29/%E9%9D%A2%E8%A9%A6%E5%BF%83%E5%BE%97%E5%88%86%E4%BA%AB/
##### [Win10 使用 Command Line Interface 編譯 C 程式](https://hackmd.io/B-RBze5XSv-IIGxI5r5hug?view)
---
:::success
## For Python Beginner
:::
* [30 天使用Python進行資料分析](https://ithelp.ithome.com.tw/users/20107514/ironman/1399)
* 建議初學可以安裝 Anaconda 作為 Python 的開發環境：[Day01](https://ithelp.ithome.com.tw/articles/10192460)
* [用 Python 刷 LeetCode](https://medium.com/@desolution)
* 這只是提供初學 Python 的人一些語法的範例，
這位寫的 code 有點太高階了，有些演算法的實作細節可能都是靠 Python 解決掉的，沒有真的練習到演算法。
* [莫凡 Python](https://morvanzhou.github.io/)
* 有 Python 基礎語法、爬蟲、機器學習等等教學。
---
:::success
## 喜歡俊龍ㄉ這邊請
* [點我](https://csdrive.cs.nctu.edu.tw/release/003dd3ac-4c28-4d20-b0c2-18cb4c937b15)
* [或點我](http://140.113.216.123:5050/final/project.pdf)
* [或點我](https://www.youtube.com/watch?v=az3VV56AMZ4)
* ~~這是俊榮~~
:::
Sign in with Wallet
Connect another wallet