---
# System prepended metadata

title: C 練習(持續更新中)
tags: [linux, c]

---

# C 練習(持續更新中)


###### tags: `c` `linux`
---

**實作平台: [WSL (Windows Subsystem for Linux)](https://docs.microsoft.com/zh-tw/windows/wsl/install-win10)**

**C版本:C99**
**IDE:VS Code/vim**
**編譯器: gcc**

## 從tmp.c到tmp.exe

經過compiler(編譯器)產生object file(目地檔.o) -> 再用linker(連結器)產生exe(執行檔)

## Hello World
```
#include <stdio.h>   // <stdio.h>去/usr/include目錄尋找stdio.h
int main()
{
    
    char str1[]="Hello World";    // C語言在strings" "最後會加'\0'
    char *str2 ="Hello World";
    printf("str1:%s\tstr2:%s\n",str1,str2);
    printf("str1 add:%p\tstr2 add:%p\n",str1,str2);
    printf("str1[0]:%p\tstr2[0]:%p\n",&str1[0],&str2[0]);
    printf("str1[0]:%c\tstr2[0]:%c\n",str1[0],*str2);
    printf("str1+1:%p\tstr2+1:%p\n",str1+1,str2+1);
    printf("str1[0]:%c\tstr2[0]:%c\n",str1[1],*(str2+1));
    printf("sizeof(str1):%ld\tsizeof(str2):%ld\n",sizeof(str1),sizeof(str2));

    //return 0;    <-- C99已經不用加return 0
}
```
```
str1:Hello World            str2:Hello World
str1 add:0x7fffe7c41aec     str2 add:0x7f8a70e00868
str1[0]:0x7fffe7c41aec      str2[0]:0x7f8a70e00868
str1[0]:H                   str2[0]:H
str1+1:0x7fffe7c41aed       str2+1:0x7f8a70e00869
str1[0]:e                   str2[0]:e
sizeof(str1):12(11+1)       sizeof(str2):8(64位元os的指標大小)
```

---
## 超基礎排序

[C 語言排序演算法實作整理：泡沫排序、快速排序等](https://blog.gtwang.org/programming/c-sorting-algorithms-implementation/)

```
#include<stdio.h>
#include<stdlib.h>

static void swap(int *a, int *b){
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

static void bubble(int *data,int length){

        for(int i = 0 ; i<length ; i++){
                for(int n = 0 ; n < i ; n++){
                        if(data[n] > data[i]){
                                swap(&data[n],&data[i]);
                        }
                }
        }
}

int main(){
        int arr1[] = {5,4,7,6,9,1,2,3};
        int len  = sizeof(arr1)/sizeof(arr1[0]);

        bubble(arr1,len);

        for(int i=0 ; i<len ; i++){
                printf("%d ",arr1[i]);
        }

        return 0;
}

--------------------------------------------
1 2 3 4 5 6 7 9

```
```
#include<stdio.h>
#include<stdlib.h>

static void swap(int *a, int *b){
        int tmp = *a;
        *a = *b;
        *b = tmp;
}


static void insertion(int *data, int length){
        for(int i=1 ; i<length ; i++){
                int j = i;
                while(data[j]<data[j-1] && j>0){
                        swap(&data[j-1],&data[j]);
                        j--;
                }

        }
}

int main(){

        int arr1[] = {5,7,4,9,6,1,3};
        int len = sizeof(arr1) / sizeof(arr1[0]);

        insertion(arr1,len);

        for(int i=0 ; i <len ; i++){
                printf("%d ",arr1[i]);
        }

        return 0;
}
```


---
## Bitwise
[C語言的 Bitwise operator(位元運算子)介紹, 包含圖解及範例](https://www.youtube.com/watch?v=10sJkpoFpv0&ab_channel=Yu_PengNie)

[Practice with bit operations](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/)這裡練習

### 顯示binary & set0 set1 toggle

```
a = a | 15    // 最右側 4 位設為 1，其餘不變。
a = a & (~15) // 最右側 4 位設為 0，其餘不變。
a = a ^ 15    // 最右側 4 位執行 NOT operator，其餘不變。

```

```
#include<stdio.h>
#include<stdlib.h>

static void binary_print(int a){

        for(int i=31; i>=0 ;i--){
                printf("%d",a>>i & 1);
        }
        printf("\t -> %d\n",a);
}

int main(){

        int val = 45; //signed 00101101
        binary_print(val);
        binary_print(val>>1); //往右移 == /2
        binary_print(val<<1); //往左移 == *2

        int val2 = -45;
        binary_print(val2);
        binary_print(val2>>1);
        binary_print(val2/2);

        printf(" set the 5th bit from right to 1?\n");

        binary_print(val);
        int mask = 1<<4;
        val|=mask;
        binary_print(val);

        printf("set the 3th bit from right to 0?\n");

        mask = ~(1<<2);
        val&=mask;
        binary_print(val);

        printf("toggle the 3th bit from right\n");
        mask = 1<<2;
        val^=mask;
        binary_print(val);

        return 0;
}
```
```
00000000000000000000000000101101         -> 45
00000000000000000000000000010110         -> 22
00000000000000000000000001011010         -> 90
11111111111111111111111111010011         -> -45
11111111111111111111111111101001         -> -23
11111111111111111111111111101010         -> -22
 set the 5th bit from right to 1?
00000000000000000000000000101101         -> 45
00000000000000000000000000111101         -> 61
set the 3th bit from right to 0?
00000000000000000000000000111001         -> 57
toggle the 3th bit from right
00000000000000000000000000111101         -> 61
```
另一種顯示binary的寫法
```
#include<stdio.h>
#include<stdlib.h>

static void binary(int data){
        for(int i= 31; i>=0 ;i--){
                int b = data&(1<<i);
                printf("%d",b>0? 1:0);
        }
        printf("\t -> %d\n",data);
}

int main(){
        int a = 12;
        binary(a);

        return 0;
}

----------------------------------
00000000000000000000000000001100         -> 12
```

**兩種寫法不同在for迴圈裡的<< or >>**
[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
左移: x << y : x 左移 y 位元，左移出的位元會被丟棄，右側會補上 0
右移: x >> y : x 右移 y 位元，右移出的位元會被丟棄。
```
這裡為了方便以16位元表示  a為12

第一種: a>>i & 1               第二種: a & (1<<i)
0000 0000 0000 0110           0000 0000 0000 1100
0000 0000 0000 0001           0000 0000 0000 1000
----------------------       ---------------------
0000 0000 0000 0000           0000 0000 0000 1000 =>2^3=>8

0000 0000 0000 0011           0000 0000 0000 1100
0000 0000 0000 0001           0000 0000 0000 0100
----------------------       ----------------------
0000 0000 0000 0001 =>2^0=>1  0000 0000 0000 0100 =>2^2=>4

0000 0000 0000 0001
0000 0000 0000 0001 =>2^0=>1  
----------------------       
0000 0000 0000 0001

可以正確顯示                   因為會產生8與4，如果依序print
0000 0000 0000 1100           0000 0000 0000 8400 會產這樣的結果，
                              所以我加入 a>0? 1:0 產生1或0 

```
### 位元內有幾個1
```
#include<stdio.h>
#include<stdlib.h>

int numbers_one(int data); // 無號整數裡位元 == 1的個數

int main(void){

        int a = 0xff; //dec:255 bin:1111 1111
        int b = 0xc87; //dec:3201 bin:1100 1000 0111

        printf("%x\t位元1的個數:%d\n",a,numbers_one(a));
        printf("%x\t位元1的個數:%d\n",b,numbers_one(b));
        return 0;
}

int numbers_one(int data){
        int count = 0;
        for(int i =31 ; i>=0 ; i--){

                //i=31 是因為32位元  編號0~31有32個

                if(data&(1<<i)){
                count++;
                }

        }
        return count;
}

-----------------------------------------------
ff      位元1的個數:8
c87     位元1的個數:6
```
```
Leetcode 191. Number of 1 Bits

int hammingWeight(uint32_t n) {
    
    int count = 0;
    /* while(n>0){
       count += n&1;
        n=n>>1;
    } */
    
    for(int i=31 ; i>=0 ;i--){
        if(n & (UINT32_C(1)<<i)){
            count++;
        }
    }
    
    return count;
}
```

### 取出第n個bit的值

```
#include<stdio.h>
#include<stdlib.h>
#include<math.h> //pow(double , double)

static int n_bit(int data, int n);

int main(void){

        int a = 0xFA; // 1111 1010
        int b = 0xC87; //1100 1000 0111
        int n = 3;
        printf("%x\t位元的第%d個位元:%d\n",a,n,n_bit(a,n));
        n = 12;
        printf("%x\t位元的第%d個位元:%d\n",b,n,n_bit(b,n));
        return 0;
}

static int n_bit(int data, int n){

        int tmp = pow(2,n-1); // 2^n-1 
        return (data & tmp)>>(n-1);
}

-------------------------------
gcc -g -Wall test2.c -lm -o test2
fa      位元的第3個位元:0
c87     位元的第12個位元:1

```

```
a = 15   取第4個bit

0001 1001     => 跟2^(4-1) AND
0000 1000
----------
0000 1000     => 再>>(4-1)

0000 0001     => 第4個bit為1
```

---

## Struct的初始化宣告(C99)

```
#include<stdio.h>

typedef struct people{
    char *name;
    int age;
    char *job;
}PEOPLE;

int main(){

    PEOPLE Peter={"Peter",18,"Student"};
    printf("name:%s age:%d job:%s\n",Peter.name,Peter.age,Peter.job);

    PEOPLE Kevin={.age=8, .job="no job", .name="Kevin"}; //可以不按照順序
    printf("name:%s age:%d job:%s\n",Kevin.name,Kevin.age,Kevin.job);

    PEOPLE *Peter_ptr=&Peter;
    (*Peter_ptr).age=66;
    Peter_ptr->job="Teacher";
    printf("name:%s age:%d job:%s\n",Peter_ptr->name,Peter_ptr->age,Peter_ptr->job);
    printf("name:%s age:%d job:%s\n",Peter.name,Peter.age,Peter.job);   // 原本的資料已被更改
    
    PEOPLE human[2]={{"Joe",55,"Dead"},
                    {"Allen",77,"dead"}};
    printf("name:%s age:%d job:%s\n",human[1].name,human[1].age,human[1].job);
    PEOPLE *human_ptr=human;
    human_ptr[0].name="Amy";
    printf("name:%s age:%d job:%s\n",human_ptr[0].name,human_ptr[0].age,human_ptr[0].job);
    printf("name:%s age:%d job:%s\n",human_ptr->name,human_ptr->age,human_ptr->job);

}

```

```
name:Peter   age:18    job:Student
name:Kevin   age:8     job:no job
name:Peter   age:66    job:Teacher
name:Peter   age:66    job:Teacher
name:Allen   age:77    job:dead
name:Amy     age:55    job:Dead
name:Amy     age:55    job:Dead
```
---

[C语言内存操作-19.结构体字节对齐](https://www.youtube.com/watch?v=p5OXx_16K0o&ab_channel=it%E6%8A%80%E6%9C%AF%E5%AD%A6%E9%99%A2) 講得很清楚 。
[Is sizeof for a struct equal to the sum of sizeof of each member?](https://www.geeksforgeeks.org/is-sizeof-for-a-struct-equal-to-the-sum-of-sizeof-of-each-member/)

```
#include<stdio.h>
#include<stdlib.h>

typedef struct people1{
        char *name;
        int   age;
        char *profession;
}PEOPLE_1;

typedef struct people2{
        char name[5];
        int  age;
        char profession[5];
}PEOPLE_2;

typedef struct data1{
        int     a;
        char    b;
        short   c;
}DATA_1;

typedef struct data2{
        char    b;
        int     a;
        short   c;
}DATA_2;

int main(){

        printf("PEOPLE_1:%ld\n",sizeof(PEOPLE_1));
        printf("PEOPLE_2:%ld\n",sizeof(PEOPLE_2));

        printf("DATA_1:%ld\n",sizeof(DATA_1));
        printf("DATA_2:%ld\n",sizeof(DATA_2));


        return 0;
};0
```

```
PEOPLE_1:24
PEOPLE_2:20
DATA_1:8
DATA_2:12
```




## 指標

```
#include<stdio.h>

int main(void){

    int c[3][2][2]={ {{2,5},{7,9}},{{3,4},{6,1}},{{0,8},{11,13}} };
    
    printf("c:%p | *c:%p | c[0]:%p | &c[0][0]:%p \n",c,*c,c[0],&c[0][0]);
    printf("c:%p | *c:%p | c[1]:%p | &c[0][1]:%p \n",c,*c,c[1],&c[0][1]);
    printf("c:%p | *c:%p | c[2]:%p | &c[1][0]:%p \n",c,*c,c[2],&c[1][0]);
    printf("\n");

    printf("*(c[0][0]+1): %d | *(c[0][0]): %d \n",*(c[0][0]+1),*(c[0][0]));
    printf("*(c[0][1]+1): %d | *(c[0][1]): %d \n",*(c[0][1]+1),*(c[0][1]));
    printf("*(c[1][0]+1): %d | *(c[1][0]): %d \n",*(c[1][0]+1),*(c[1][0]));
    printf("*(c[1][1]+1): %d | *(c[1][1]): %d \n",*(c[1][1]+1),*(c[1][1]));
    printf("*(c[2][0]+1): %d | *(c[2][0]): %d \n",*(c[2][0]+1),*(c[2][0]));
    printf("*(c[2][1]+1): %d | *(c[2][1]): %d \n",*(c[2][1]+1),*(c[2][1]));
    
    printf("\n");
    printf("*(c[0]+1): %p\n",*(c[0]+1));

    return 0;
}
```
```
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[0]:0x7fffc6417680 | &c[0][0]:0x7fffc6417680 
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[1]:0x7fffc6417690 | &c[0][1]:0x7fffc6417688 
c:0x7fffc6417680 | *c:0x7fffc6417680 | c[2]:0x7fffc64176a0 | &c[1][0]:0x7fffc6417690 

*(c[0][0]+1): 5 | *(c[0][0]): 2 
*(c[0][1]+1): 9 | *(c[0][1]): 7 
*(c[1][0]+1): 4 | *(c[1][0]): 3 
*(c[1][1]+1): 1 | *(c[1][1]): 6 
*(c[2][0]+1): 8 | *(c[2][0]): 0 
*(c[2][1]+1): 13 | *(c[2][1]): 11 

*(c[0]+1): 0x7fffc6417688
```
---
```
#include<stdio.h>

int main(){
    int arr[]={1,2,3,4,5,6};
    int *p = arr;
    *(p++)+=100;    // p++ => 先取p再+1
    *(++p)+=100;    // ++p => 先+p再取值
    for(int i=0 ;i <6;i++){
        printf("%d ",arr[i]);
    }
}

output: 101 2 103 4 5 6
```

---



---
## 變數範圍

C語言有3種變數範圍 **須注意variable的lifetime**
1. Global variable(全域變數)
2. Local variable(區域變數)
3. Block variable(區塊變數)

static:
* **對其他.c檔隱藏變數/函式名稱，只能在宣告它的檔案中使用。(最重要的功能)**
* static變數內容的lifetime，不會因為離開區域變數而結束。
* static變數，如果沒設定預設值為0。

extern:
* 聲明變數會在其他的位置被定義，可能是在同一份檔案中，或是在其他檔案裡。

## 常用<string.h>的函式
**在Linux系統下，有關於標準函式庫的使用，都可以command `man xxx`，會出現該函式的資料。**
![](https://i.imgur.com/M8SttZ9.jpg)
或是這裡查詢[Linux man pages online](https://man7.org/linux/man-pages/index.html)。

---
* strlen - calculate the length of a string
    * size_t strlen(const char *s);
        * The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
        * The strlen() function returns the number of characters in the string pointed to by s.
---
* strcpy, strncpy - copy a string
    * char *strcpy(char *dest, const char *src);
        * 回傳值: *dest
        * strcpy是根據/0做為結束判斷的，如果dest空間不夠則會造成 buffer overflow。
        
    * char *str**n**cpy(char *dest, const char *src, **size_t n**); 
        * 回傳值: *dest
        * size_t n 指的是複製char的個數，且結尾不會自動加/0，需手動補上。
        * 如果dest的空間>src的空間，剩下的空間都會以/0補滿。
---
* memcpy - copy memory area    
    * void *memcpy(void *dest, const void *src, size_t n);
    
        * 回傳值: *dest    
        * **與strcpy不同，strcpy只能複製字串，而memcpy可以複製任何數據類型的對象，且不會遇到/0就停止，會完整複製n的位元組才結束。**
    *  void *memmove(void *dest, const void *src, size_t n);
        * 回傳值: *dest
        * 與memcpy不同的是。如果來源區域與目的地的某些區域重疊，這兩個函式可確保先複製重疊區域中的原始來源位元組，再進行覆寫。
---
* memset - fill memory with a constant byte
    *  void *memset(void *s, int c, size_t n);
        
        * 回傳值: *s   
        * The memset() function fills the first n bytes of the memory area pointed to by s with the constant byte c.  
        * 常用在記憶體空間的初始化。

---
```
#include <string.h>
#include <stdio.h>

int main(int argc, char **argv){
    char str1[]="Start stop";
    int str1_len = strlen(str1);
    char str2[str1_len];        //C99 允許宣告陣列用變數表示
    memset(str2,'\0',str1_len); // init str2's memory area
    strcpy(str2,str1);
    printf("str1: %s\n",str1);
    printf("str2: %s\n",str2);

    memcpy(str1,str1+2,3*sizeof(char)); //str1+2 = &str1[2] 
    memmove(str2,str2+2,3*sizeof(char));
    printf("str1: %s\n",str1);
    printf("str2: %s\n",str2);
}
```
```
str1: Start stop
str2: Start stop
str1: artrt stop
str2: artrt stop

"Start stop"                "Start stop"
[-]                          [-]      
  [-]                              [-]
有overlap的情況                無overlap的情況
```
此程式碼的memcpy 跟 memmove的結果雖然一樣，但那是因為編譯器可能會自動去處理overlap的問題，但根據編譯器的不同memcpy不能保證結果正確。範例是從[Difference between memmove and memcpy](https://www.youtube.com/watch?v=nFl1cNXk85s&ab_channel=CodeVault)修改而成的。


---
*  strcat, strncat - concatenate two strings
    *  char *strcat(char *dest, const char *src);
        * 回傳值: *dest
    *  char *strncat(char *dest, const char *src, size_t n);
        * 回傳值: *dest
        * n 決定複製幾個字元到dest尾端。
```
Source code:
char *strncat(char *dest, const char *src, size_t n)
{
    size_t dest_len = strlen(dest);
    size_t i;

    for (i = 0 ; i < n && src[i] != '\0' ; i++)
        dest[dest_len + i] = src[i];
    dest[dest_len + i] = '\0';
    return dest;
}
```
以上是str**n**cat的 soure code，從程式碼可以很清楚的看到strncat的處理過程，並在字串結尾會補上'\0'。

---
* strcmp, strncmp - compare two strings
    * int strcmp(const char *s1, const char *s2);
        * s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
        * 比較的依據是由[ASCII](https://zh.wikipedia.org/wiki/ASCII)碼去比較的。
        * 遇到字串結束符'\0'，會終止比較。 
    * int strncmp(const char *s1, const char *s2, size_t n);
        * s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
        * n是比較前n個字元。
        
strcmp系列的回傳值較複雜s1>s2的回傳值，根據編譯器的不同會產生1 or ASCII的差值。

* memcmp - compare memory areas
    * int memcmp(const void *s1, const void *s2, size_t n);
        *  s1 == s2 回傳 0，s1 > s2 回傳一個正數，s1 < s2 回傳一個負數。
        *  memcmp不會因為遇到'\0'，而結束函式。    
```
#include<stdio.h>
#include<string.h>

int main(void){
    char str1[]="He is teacher";
    char str2[]="He is student";

    printf("strcmp: %d\n",strcmp(str1,str2));
    printf("strcmp: %d\n",strncmp(str1,str2,5));
}
```
```
strcmp: 1  
strncmp: 0 // 前5個字元相等 "He is"，所以回傳值為0。

```
strcmp的回傳值為**1**代表str1大於str2，雖然"teacher"與"student"都是六個字母組成，但strcmp比較的是ASCII碼，第一個不同的字元分別為str1的't'與str2的's'，'t'的ASCII碼為116，則's'的ASCII碼為115，所以t大於s，回傳值為1。

strcmp、strncmp與memcmp的不同處，有網友在[What is the difference between memcmp, strcmp and strncmp in C?](https://stackoverflow.com/questions/13095513/what-is-the-difference-between-memcmp-strcmp-and-strncmp-in-c)解釋得非常清楚。
* strcmp: compares null-terminated C strings.
* strncmp: compares at most N characters of null-terminated C strings.
* memcmp: compares binary byte buffers of N bytes.
```
const char s1[] = "atoms\0\0\0\0";  // extra null bytes at end
const char s2[] = "atoms\0abc";     // embedded null byte
const char s3[] = "atomsaaa";
---------------------------------------------------------------------
strcmp(s1, s2) == 0      // strcmp stops at null terminator
strcmp(s1, s3) != 0      // Strings are different
strncmp(s1, s3, 5) == 0  // First 5 characters of strings are the same
memcmp(s1, s3, 5) == 0   // First 5 bytes are the same
strncmp(s1, s2, 8) == 0  // Strings are the same up through the null terminator
memcmp(s1, s2, 8) != 0   // First 8 bytes are different
```
---
## <stdio.h>
* ~~sprintf~~, snprintf - formatted output conversion
    * int snprintf(char *str, size_t size, const char *format, ...);
        * 限制字串的長度，避免overflow。
        * 比起用strncpy不會自動加\0，用snprintf會更好。

```
int buff[1024];
int num=10000;
sprintf(buff, "%d x %d = %d",num,num,num*num);

會產生 overflow
-----------------------------------------------
int buff[1024];
int num=10000;
sprintf(buff,sizeof(buff) ,"%d x %d = %d",num,num,num*num);

不會產生 overflow

```
---
## 錯誤處理

程式發生錯誤時通常會把錯誤代碼存入一個叫"errno"的全域變數，可以#include<errno.h>來顯示出對應的錯誤訊息。

* perror - print a system error message
    *  void perror(const char *s); 
    *  char *strerror(int errnum);
    
[Linux下perror errno出錯函數](https://tw511.com/a/01/8093.html)清楚展示如何使用。
```
#include <stdio.h> 		//perror
#include <string.h> 	//strerror
#include <errno.h> 		//errno

#if 0
void perror(const char *s);
功能：s + ':' + '空格' + '錯誤資訊' + '\n'

char *strerror(int errnum);
功能：將錯誤碼轉換成對應錯誤資訊

errno
功能：自動記錄最後一次的錯誤碼
#endif

int main(int argc, const char *argv[])
{
	FILE *fp = fopen(argv[1], "r");
	if(fp == NULL)
	{
		printf("fopen error\n");
		perror("fopen error");
		printf("strerror   : %s\n",strerror(errno));
		return -1;
	}
	printf("ok\n");
	
	return 0;
}

------------------------------------------
fopen error
fopen error: Bad address
strerror   : Bad address
```
* 節制的善用goto
    * 常使用在例外處理。
    * [Using goto for error handling in C](https://eli.thegreenplace.net/2009/04/27/using-goto-for-error-handling-in-c) 以下兩個範例，可以清楚地看到使用goto對程式碼精簡很多，更容易去閱讀及使用。

```
int c_example()
{
    int ret = 0; // return value 0 is success
    FILE *f = fopen("logfile.txt", "w+");

    if (!f)
        return -1;

    if (fputs("hello logfile!", f) == EOF)
    {
        ret = -2;
        goto out;
    }

    // continue using the file resource
    // ...

    // Releasing resources (in reverse order)
out:
    if (fclose(f) == EOF)
        ret = -3;

    return ret;
}
```

```
int c_example()
{
    int ret = 0; // return value 0 is success
    FILE *f = fopen("logfile.txt", "w+");

    if (!f)
        return -1;

    if (fputs("hello logfile!", f) != EOF)
    {
        // continue using the file resource
    }
    else
    {
        ret = -2;
    }

    if (fclose(f) == EOF)
        ret = -3;

    return ret;
}
```
---



---
## 好用的標準函式
* void qsort(void *base, size_t nmemb, size_t size,int (*compar)(const void , const void *));
    * qsort 並不一定是 quick sort，編譯器會根據陣列決定使用哪種演算法。
```
#include<stdio.h> 
#include<stdlib.h> //qsort

int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
void print_arr(int *arr,int n){
    for(int i=0; i<n ;i++){
        printf("%d ",*(arr+i));
    }
    printf("\n");
}
int main(){
    int arr[]={2,5,8,9,5,4,7,85,2,100};
    int n = sizeof(arr) / sizeof(int);
    print_arr(arr,n);
    qsort(arr,n,sizeof(int),cmp);
    print_arr(arr,n);
}

-------------------------------------------------
2 5 8 9 5 4 7 85 2 100 
2 2 4 5 5 7 8 9 85 100 
```
---
## Process
另一篇有簡略介紹[Process](https://hackmd.io/Zp7uUl5KTpSZSviYantg8w?view#%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1OS)。

* fork - create a child process (#include <unistd.h>)
    * pid_t fork(void);
    * Return Value:
        * -1: no child process is created, and errno is set appropriately.
        * 0 : 為child process
        * 大於0 : the  PID  of  the  child  process is returned in the parent

[[Linux C] fork 觀念由淺入深](https://wenyuangg.github.io/posts/linux/fork-use.html)

* 僵屍程序 (Zombie Process)：
    1.    僵屍程序是指一支存活在系統中, 但是他卻沒有做任何事, 只是佔著並耗用系統資源的程序
    2. 當使用 fork() 來建立子程序多工運行時, 如果子程序還沒運行結束就將父程序關閉的話, 就會有僵屍程序產生



---
## [Posix thread](https://zh.wikipedia.org/wiki/POSIX%E7%BA%BF%E7%A8%8B)
需要在程式開頭 #include<pthread.h>，在編譯時需加 -pthread參數。
[Difference between -pthread and -lpthread while compiling](https://stackoverflow.com/questions/23250863/difference-between-pthread-and-lpthread-while-compiling)

### 執行緒管理
pthread_xxxx的函式有許多種，以下僅列出較常使用的。
* pthread_self - obtain ID of the calling thread
    * pthread_t pthread_self(void);
        * 回傳 thread ID。

* pthread_create - create a new thread
    * int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                          void *(*start_routine) (void *), void *arg);
        * 創建成功回傳0，失敗回傳錯誤代碼。    
        * 第一個參數: pthread_t的變數，以pointer帶入。
        * 第二個參數: thread的屬性，沒指定就填入NULL，使用預設屬性。
        * 第三個參數: thread要執行的function，以pointer帶入。
        * 第四個參數: function要帶入的參數，不用參數就NULL。
```
pthread_t thread;
int ret;

ret = pthread_create(&thread, NULL, start_routine, NULL);
if(!ret){
    errno = ret;
    perror("pthread_create:");
    return -1;
}
```
* pthread_join - join with a terminated thread
    * int pthread_join(pthread_t thread, void **retval);
        * 成功回傳0，失敗回傳錯誤代碼。
        * 第一個參數: 等待的目標thread。
        * 第二個參數: 接收thread回傳的值。   
        
*  pthread_exit - terminate calling thread
    *  void pthread_exit(void *retval);
        * thread預計會傳回的值，可在主程式由 pthread_join接收此回傳值。

範例: [C 語言 pthread 多執行緒平行化程式設計入門教學與範例](https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/)   
```
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h> //sleep
#include<errno.h> //errno
#include<pthread.h>

void* child(void *data){            //子執行續
    char *str = (char*)data;
    for(int i=0 ;i<3;i++){
        printf("%s\n",str);
        sleep(1);
    }
    pthread_exit(NULL);
}

int main(){                        //主執行續

    pthread_t thread1;
    int th1= pthread_create(&thread1, NULL, child, "child");
    if(th1){
        errno =th1;
        perror("pthread_create:");
    }
    for(int i=0 ; i<3 ;i++){
        printf("Master\n");
        sleep(1);
    }
    pthread_join(thread1,NULL);
}
```

```
gcc -g -Wall pthread1.c -pthread -o pthread1

DESKTOP-T8T3932% ./pthread1 
Master
child
child
Master
Master
child
DESKTOP-T8T3932% ./pthread1
Master
child
Master
child
Master
child
```
可以發現輸出的結果並不一定是我們預期的輪流顯示，原因是我們不能控制thread的行動，需加上一些條件才能控制thread的行動(**EX:Condition Variable, Mutex等**)。

```
#include<stdio.h>
#include<stdlib.h>
#include<errno.h> 
#include<pthread.h>

void* child(void* arg){
    int *input = (int*) arg;
    int *result = malloc(sizeof(int)*1);
    result[0] = input[0]+input[1];
    pthread_exit((void*)result);
}

int main(){
    pthread_t thread1;
    int list[2]={1,2};
    void* ret; // 子執行續的回傳值
    int td1 = pthread_create(&thread1, NULL, child, list);
    if(td1){
        errno=td1;
        perror("pthread_create:");
    }
    pthread_join(thread1,&ret);

    int *result = (int*) ret;
    printf("%d + %d = %d\n",list[0],list[1],result[0]);
    free(result);
}
```
```
DESKTOP-T8T3932% gcc -g -Wall pthread2.c -pthread -o pthread2
DESKTOP-T8T3932% ./pthread2
1 + 2 = 3
這種動態配置記憶體的方法，在Thread比較不容易處理，容易寫錯造成 memory leak。
```
```
#include <stdio.h>
#include <pthread.h>
#include<errno.h> 

typedef struct my_data {
   int a;
   int b;
   int result;
} my_data;

void *child(void *arg) {
   my_data *data=(my_data *) arg; 
   int a = data->a;
   int b = data->b;
   int result = a + b; 
   data->result = result;
   pthread_exit(NULL);
}

int main() {
    pthread_t t;
    my_data data;
    data.a = 1;
    data.b = 2;
    int td1 = pthread_create(&t, NULL, child, (void*) &data);
    if(td1){
        errno = td1;
        perror("pthread_create:");
    }
    pthread_join(t, NULL);
    printf("%d + %d = %d\n", data.a, data.b, data.result);
}
```
```
1 + 2 = 3
統一由主thread來管理記憶體空間，較malloc安全許多。
```
### [互斥鎖(Mutex)](https://zh.wikipedia.org/wiki/%E4%BA%92%E6%96%A5%E9%94%81)

**Mutex的流程: 建立mutex → 初始化mutex → 操作mutex(lock,unlock等) → 銷毀mutex**

* mutex兩種初始化:

``` 
1. pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; //不需要destory mutex

2. pthread_mutex_t mutex; 
   pthread_mutex_init(&mutex,NULL); //第二個參數是 鎖的屬性
   pthread_mutex_destory(&mutex); 
```
* 操作mutex
```
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
```
在lock和unlock之間的程式碼，只允許一個thread執行，盡可能讓互斥鎖的程式碼少點，效率才更會好。

```
此範例"未加"互斥鎖(mutex)

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>

int count=0;            //同Process內的多個thread可以共同讀取全域變數

void *child(){
    for(int i=0; i<3 ;i++){
        int tmp = count;
        sleep(1);
        count=tmp+1;
        printf("count= %d \n",count);
    }
    pthread_exit(NULL);
}

int main(){
    pthread_t thread1,thread2;
    pthread_create(&thread1,NULL,child,NULL);
    pthread_create(&thread2,NULL,child,NULL);
    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);
}
```
```
count= 1 
count= 1 
count= 2 
count= 2 
count= 3 
count= 3 
```
---

```
此範例"加"互斥鎖(mutex)

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>

int count=0;
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER; 
void *child(){
    for(int i=0; i<3 ;i++){
        pthread_mutex_lock(&mutex1);
        int tmp = count;
        sleep(1);
        count=tmp+1;
        pthread_mutex_unlock(&mutex1);
        printf("count= %d \n",count);
    }
    pthread_exit(NULL);
}

int main(){
    pthread_t thread1,thread2;
    pthread_create(&thread1,NULL,child,NULL);
    pthread_create(&thread2,NULL,child,NULL);
    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);
}
```
```
count= 1 
count= 2 
count= 3 
count= 4 
count= 5 
count= 6 
```
### 條件變數(Condition Variable)
* Condition Variable 
通常都會與mutex搭配使用
```
pthread_cond_t cond_var = PTHREAD_COND_INITIALIZER; //初始化
int pthread_cond_broadcast(pthread_cond_t* cond); //喚醒條件變數等待的"所有"執行緒
int pthread_cond_signal(pthread_cond_t* cond); //喚醒條件變數上等待的"一個"執行緒
int pthread_cond_wait(pthread_cond_t* cond); //解鎖mutex並等待條件變數觸發
```



### [旗標（Semaphore)](https://zh.wikipedia.org/wiki/%E4%BF%A1%E5%8F%B7%E9%87%8F)
使用semaphore需載入#include<semaphore.h>，semaphore本身是一個計數器。

* int sem_init(sem_t *sem, int pshared, unsigned int value);
* int sem_wait(sem_t *sem);
    * sem_wait: 用來判斷是否有工作尚未完成，當工作數量大於0時，執行程序並把工作量-1，當工作量等於0時，停止此thread等待工作量大於0。
    
* int sem_post(sem_t *sem);
    * sem_post: 可以新增工作量+1。 

範例: [C 語言 pthread 多執行緒平行化程式設計入門教學與範例](https://blog.gtwang.org/programming/pthread-multithreading-programming-in-c-tutorial/)

```
#include<stdio.h>
#include<unistd.h>
#include<pthread.h>
#include<semaphore.h>

sem_t sem;
int counter = 0;

void* child(){
    for(int i=0; i< 5 ;i++){
        sem_wait(&sem);
        printf("counter = %d\n",counter++); //先取值，再++
        sleep(1);
    }
    pthread_exit(NULL);
}

int main(){

    sem_init(&sem,0,0);

    pthread_t thread;
    pthread_create(&thread,NULL,child,NULL);

    printf("post 2 jobs\n");
    sem_post(&sem);
    sem_post(&sem);
    sleep(3);

    printf("post 3 jobs\n");
    sem_post(&sem);
    sem_post(&sem);
    sem_post(&sem);
    
    pthread_join(thread,NULL);

}

```

```
DESKTOP-T8T3932% gcc -g -Wall semaphore_test1.c -pthread -o semaphore_test1
DESKTOP-T8T3932% ./semaphore_test1 
post 2 jobs
counter = 0
counter = 1
post 3 jobs
counter = 2
counter = 3
counter = 4
```

---
### Producer Consumer Models

* 最簡易的consumer producer範例(兩種寫法，不同於pthread_create最後有無參數)。
```
#include <stdio.h>
#include <stdlib.h>  
#include <pthread.h> 
#include <unistd.h> 
#include <string.h>

#define BUFFFSIZE 255
static void* producer(void* );
static void* consumer(void* );
int allnumber;                      // 總共有幾題
int isfound=1 ;                     // 還沒找到答案
char QA_buff[BUFFFSIZE] = {'\0'};   // producer 和 consumer 都要從這裡拿資料

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

typedef struct QA{
    char *Q;
    char *A;
    int number;
}QA;


int main(){
    srand(time(NULL));
    QA test[]={ {.Q = "James", .A = "Harden",   .number = 0},
                {.Q = "Kevin" , .A = "Love",    .number = 1},
                {.Q = "Ray"  , .A = "Allen",    .number = 2},
                {.Q = "Devin", .A = "book",     .number = 3}};
    allnumber = sizeof(test)/sizeof(test[0]);
    printf("allnumber:%d\n",allnumber);
   
    pthread_t prod,cons;
    if((pthread_create(&prod,NULL,consumer,&test)) != 0){
        perror("producer create:");
    }
     if((pthread_create(&cons,NULL,producer,&test)) != 0){
        perror("consumer create:");
    }

    pthread_join(prod,NULL);
    pthread_join(cons,NULL);
   
}

static void* producer(void *p){
    QA *qa_prod = (QA*) p;
    while(1){
        pthread_mutex_lock(&mutex);
        int i =rand() %allnumber;
        snprintf(QA_buff,BUFFFSIZE,"%s",qa_prod[i].Q);
        printf("Q: %s\n",QA_buff);
        while(isfound > 0){
            //printf("%s\n","wait");
            sleep(1);
            pthread_cond_wait(&cond,&mutex);
        }
        printf("A: %s\n",QA_buff);
        isfound=1;
        pthread_mutex_unlock(&mutex);
        sleep(1);
    }
    pthread_exit(NULL);
}

static void* consumer(void *p){
    QA *qa_cons = (QA*) p;
    while(1){
        pthread_mutex_lock(&mutex);
        for(int k=0; k< allnumber ;k++)
        {
            if( (strcmp(QA_buff,qa_cons[k].Q)) == 0){
                snprintf(QA_buff,BUFFFSIZE,"%s",qa_cons[k].A);
                isfound = -1;
                pthread_cond_signal (&cond);
                //printf("%s\n","signal");
                break;
            }
        }
        //printf("%s\n",QA_buff);
        pthread_mutex_unlock(&mutex);
        sleep(1);
    }
    pthread_exit(NULL);
}
```
---
```
#include <stdio.h>
#include <stdlib.h>  
#include <pthread.h> 
#include <unistd.h> 
#include <string.h>

#define BUFFFSIZE 255
static void* producer(void* );
static void* consumer(void* );
int isfound=1 ;                     // 還沒找到答案
char QA_buff[BUFFFSIZE] = {'\0'};   // producer 和 consumer 都要從這裡拿資料

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

typedef struct QA{
    char *Q;
    char *A;
    int number;
}QA;

QA test[]={ {.Q = "James", .A = "Harden",   .number = 0},
                {.Q = "Kevin" , .A = "Love",    .number = 1},
                {.Q = "Ray"  , .A = "Allen",    .number = 2},
                {.Q = "Devin", .A = "book",     .number = 3}};
int allnumber = sizeof(test)/sizeof(test[0]);

int main(){
    srand(time(NULL));
    
    printf("allnumber:%d\n",allnumber);
   
    pthread_t prod,cons;
    if((pthread_create(&prod,NULL,consumer,NULL)) != 0){
        perror("producer create:");
    }
     if((pthread_create(&cons,NULL,producer,NULL)) != 0){
        perror("consumer create:");
    }

    pthread_join(prod,NULL);
    pthread_join(cons,NULL);
   
}

static void* producer(void *p){
    
    while(1){
        pthread_mutex_lock(&mutex);
        int i =rand() %allnumber;
        snprintf(QA_buff,BUFFFSIZE,"%s",test[i].Q);
        printf("Q: %s\n",QA_buff);
        while(isfound > 0){
            //printf("%s\n","wait");
            sleep(1);
            pthread_cond_wait(&cond,&mutex);
        }
        printf("A: %s\n",QA_buff);
        isfound=1;
        pthread_mutex_unlock(&mutex);
        sleep(1);
    }
    pthread_exit(NULL);
}

static void* consumer(void *p){
    
    while(1){
        pthread_mutex_lock(&mutex);
        for(int k=0; k< allnumber ;k++)
        {
            if( (strcmp(QA_buff,test[k].Q)) == 0){
                snprintf(QA_buff,BUFFFSIZE,"%s",test[k].A);
                isfound = -1;
                pthread_cond_signal (&cond);
                //printf("%s\n","signal");
                break;
            }
        }
        //printf("%s\n",QA_buff);
        pthread_mutex_unlock(&mutex);
        sleep(1);
    }
    pthread_exit(NULL);
}
```
---
```
allnumber:4
Q: James
A: Harden
Q: Devin
A: book
Q: Kevin
A: Love
Q: Ray
A: Allen
....

兩種寫法得到的結果都一樣。
1. producer會把題目放入QA_buff後，進行wait掛起。
2. consumer讀取QA_buff的題目後，搜尋問題得到對應的答案，再把答案放回QA_buff，並signal 正在wait的producer。 
3. producer被喚醒重新上鎖後，顯示出QA_buff裡的答案。
```
![](https://i.imgur.com/tvXtkol.jpg)


---
```

```

```

```
---


---
## 簡易linked list練習
當初學習來源:[鏈結串列教學](https://medium.com/@racktar7743/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97%E6%95%99%E5%AD%B8-1-%E6%96%B0%E5%A2%9E%E8%88%87%E5%8D%B0%E5%87%BA-bb881da97796)
```
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int val;
    struct node* next;
}Node;

static void addnode(Node **node,int val);
static void insertnode(Node **node,int insert_after_val,int val);
static void deletenode(Node **node,int val);
static void printnode(Node *node);
static void freenode(Node *node);

int main(){
    Node* head = NULL;
    addnode(&head,10);
    addnode(&head,20);
    addnode(&head,30);
    insertnode(&head,20,25);
    insertnode(&head,30,35);
    printnode(head);
    deletenode(&head,10);
    deletenode(&head,20);
    deletenode(&head,30);
    printnode(head);
    freenode(head);

    return 0;
}

static void addnode(Node **node,int val){
    Node *newnode = malloc(sizeof(Node));
    newnode->val = val;
    newnode->next = NULL;

    if(*node == NULL){
        *node = newnode;
        return;
    }

    else{
        Node *current;
        current = *node;
        while(current->next != NULL){
            current = current->next;
        }
        current->next = newnode;
        return;
    }

}

static void insertnode(Node **node,int insert_after_val,int val){

    Node *current = *node;
    while(current != NULL){
        if(current->val == insert_after_val){
            Node *newnode = malloc(sizeof(Node));
            newnode->val = val;
            newnode->next = NULL;
            if(current->next == NULL){
                current->next = newnode;
                break;
            }

            else{
                newnode->next = current->next;
                current->next =newnode;
                break;
            }
        }
        current = current->next;
    }

}

static void deletenode(Node **node,int val){

    Node *tmp;
    Node *current = *node;
    if(current->val == val){
        *node = current->next;
        free(current);
        return;        
    }

    while(current != NULL){
        if(current->next->val == val){
            tmp = current->next;
            current->next = current->next->next;
            free(tmp);
            return;
        }
        current = current->next;
    }
}

static void printnode(Node *node){

    while(node != NULL){
        printf("%d ",node->val);
        node = node->next;
    }
    printf("\n");

}

static void freenode(Node *node){

    Node *tmp,*current;
    current = node;
    while(current != NULL){
        tmp = current;
        current = current->next;
        free(tmp);
    }

}
```
---
```
10 20 25 30 35 
25 35 
```
---

## 簡易Hash練習
當初學習來源待補:
```
#include<stdio.h>
#include<stdlib.h>

#define SIZE 20
typedef struct 
{
    int data;
    int key;
}HASH;

HASH *hashlist[SIZE]; 
HASH *item;
HASH *tmp;

int hash_code(int key){
    return key % SIZE;
}

void hash_insort(int key,int data){
    HASH *item = malloc(sizeof(HASH));
    item->data = data;
    item->key  = key;

    int hash_index = hash_code(key);

    while(hashlist[hash_index] != NULL && hashlist[hash_index]->key != -1){
        hash_index++;
        hash_index %=SIZE;
    }
    hashlist[hash_index] = item;

}
HASH *hash_delete(HASH *item){
    int key = item->key;
    int hash_index = hash_code(key);
    while(hashlist[hash_index] != NULL){
        if(hashlist[hash_index]->key == key){
            HASH *temp = hashlist[hash_index];
            hashlist[hash_index] = tmp;
            return temp;
        }
        hash_index++;
        hash_index %=SIZE;
    }
    return NULL;
}
HASH *hash_search(int key){
    int hash_index = hash_code(key);
    while(hashlist[hash_index] != NULL){
        if(hashlist[hash_index]->key == key){
            return hashlist[hash_index];
        }
        hash_index++;
        hash_index %=SIZE;

    }
    return NULL;
}

void hashlist_display(){
    for(int i=0 ;i<SIZE;i++){
        if(hashlist[i] != NULL){
            printf("(%d,%d)",hashlist[i]->key,hashlist[i]->data);
        }

        else{
            printf("~~");
        }
    }
    printf("\n");
}

int main(){
    tmp = malloc(sizeof(HASH));
    tmp->data=-1;
    tmp->key =-1;

    hash_insort(1,20);
    hash_insort(2,70);
    hash_insort(42,80);
    hash_insort(4,25);
    hash_insort(12,44);
    hash_insort(14,32);
    hash_insort(17,11);
    hash_insort(13,78);
    hash_insort(37,97);

    hashlist_display();

    item = hash_search(37);

    if(item != NULL){
        printf("element found:%d\n",item->data);
    }
    else{
        printf("element not found\n");
    }

    hash_delete(item);

    item = hash_search(37);

    if(item != NULL){
        printf("element found:%d\n",item->data);
    }
    else{
        printf("element not found\n");
    }

return 0;
}
```
---
```
~~(1,20)(2,70)(42,80)(4,25)~~~~~~~~~~~~~~(12,44)(13,78)(14,32)~~~~(17,11)(37,97)~~
element found:97
element not found
```
---



