嵌入式和Linux知識總結

嵌入式和Linux基礎知識

- 1. C語言基礎
- - 1.1 資料類型
  - - 1.1.1 static和extern
    - 1.1.2 volatile
    - 1.1.3 typedef
    - 1.1.4 union
    - 1.1.5 inline内聯函數
  - 1.2 資料與指針
  - 1.3 printf函數和i++
- 2. Linux基礎
- - 2.1 記憶體管理
  - - 2.1.1 Linux虛拟位址空間
    - 2.1.2 記憶體存儲空間
    - 2.1.3 記憶體配置設定方式
    - 2.1.4 段錯誤以及調試方法
  - 2.2 程序與多程序
  - - 2.2.1 多程序
    - 2.2.2 Linux程序的三态
    - 2.2.3 程序建立（程序的實作）
    - 2.2.4 僵屍程序
  - 2.3 程序間的通信方式
  - - 2.3.1 管道（Pipe）和有名管道（Named Pipe或FIFO）
    - 2.3.2 信号（Signal）
    - 2.3.3 消息隊列（Message Queue）
    - 2.3.4 信号量（燈）（Semaphore）
    - 2.3.5 共享記憶體（Shared Memory）
    - 2.3.6 套接字（Socket）
  - 2.4 線程與多線程
  - - 2.4.1 多線程
    - 2.4.2 多線程的實作
    - 2.4.3 線程同步機制
    - 2.4.4 鎖機制
- 3. 硬體接口和協定
- - 3.1 ARM架構
  - 3.2 RAM和ROM的差別
  - 3.3 硬體接口
  - - 3.3.1 UART
    - 3.3.2 SPI
    - 3.3.3 I2C
    - 3.3.4 USB
    - 3.3.5 CAN
    - 3.3.6 CANFD
    - 3.3.7 RS485
  - 3.4 無線通信方式和協定
  - - 3.4.1 WiFi協定
    - 3.4.2 BLE協定
    - 3.4.3 ZigBee協定
    - 3.4.4 LoRa協定
    - 3.4.5 NB-IoT
  - 3.5 網絡通信協定
  - - 3.5.1 TCP
    - 3.5.1 IP
    - 3.5.3 UDP
    - 3.5.4 HTTP
    - 3.5.5 HTTPS
    - 3.5.6 CoAP
    - 3.5.7 MQTT
    - 3.5.8 MQTT和TCP的差別
    - 3.5.9 OpenSSL加密
    - 3.5.9 RTSP
- 4. 資料結構
- - 4.1 線性表
  - - 4.1.1 線性表的順序結構
    - 4.1.2 線性表的鍊式結構
  - 4.2 棧（stack）
  - - 4.2.1 棧的順序結構
    - 4.2.2 兩棧共享空間
    - 4.2.3 棧的鍊式結構
  - 4.3 隊列（queue）
  - - 4.3.1 順序隊列
    - 4.3.2 鍊式隊列
  - 4.4 字元串（string）
  - - 4.4.1 KMP模式比對算法
  - 4.5 樹（tree）
- 5. 算法
- - 5.1 冒泡排序和選擇排序
  - 5.2 查找特定資料
  - 5.3 牛客網題目
  - - 5.3.1 資料結構
  - 5.4 C語言的經典問題
  - - 5.4.1 漢諾塔問題

說明：本文的目的是為了簡單總結嵌入式和Linux常見知識點，在本文中你可以快速将不同的知識點串起來，形成一個更加清晰的知識網絡。

1. C語言基礎

1.1 資料類型

1.1.1 static和extern

1.static修飾變量

（1）修飾局部變量

局部變量：存儲在棧區，生命周期在該語句塊執行結束時便結束。

static局部變量：存儲在靜态資料區，生命周期一直持續到整個程式執行結束為止。作用域沒有改變，仍然是一個局部變量。

（2）修飾全局變量

static全局變量的作用域由原來的整個工程可見變為本源檔案可見。

（3）修飾函數

與修飾全局變量大同小異。

2.extern

extern可以修改變量或函數，表示該變量或函數不是在本源檔案内聲明的。多個源檔案中隻能有一處對其進行初始化。

1.1.2 volatile

volatile修飾的變量表示該變量的值很容易由于外部因素發生變化。不管它的值有沒有變化，每次對其值進行通路時，都會從記憶體裡、寄存器裡讀取，進而保證資料的一緻。

線上程間通信時由于多個線程可能更改全局變量，是以全局變量最好聲明為volatile。

1.1.3 typedef

舉例：

typedef struct tag_node {
	char *p_item;
	struct tag_node *p_next;
} *p_node;

#define和typedef的差別：

（1）#define 隻是簡單的字元串替換。

（2）typedef 是為一個類型起新名字。

struct和typedef struct的差別：

（1）在C中定義一個結構體類型，

第一種：

struct Student {
	int a;
};
struct Student stu1;

第二種：

typedef struct Student {
	int a;
} Stu;
Stu stu1; 或：struct Student stu1;

第三種：

typedef struct {
	int a;
} Stu;
Stu stu1;

（2）在C++中定義一個結構體類型，

第一種：

struct Student {
	int a;
};
(struct )Student stu1;		// struct可省略

第二種：

struct Student {
	int a;
} stu1;

第三種：

typedef struct Student {
	int a;
} Stu;
Stu stu1;

1.1.4 union

union聯合體：在聯合體中各成員共享一段記憶體空間，一個聯合變量的長度等于各成員中最長的長度

小端模式和大段模式：x86系列CPU都是Little endian的位元組序，PowerPC通常是Big endian。

舉例：

int CheckCPUType() {
	union w {
		int a;
		char b;
	} c;

	c.a = 1;
	return (c.b == 1);		/* 若等于1，則為Little endian */
}

1.1.5 inline内聯函數

一個函數被調用時，會有函數入棧（即函數棧），會造成棧空間或棧記憶體的消耗。

inline修飾的函數為内聯函數，在調用該函數時會直接複制函數體内容，減少函數棧的開銷。

void Foo(int x, int y);
inline void Foo(int x, int y)
{
}

1.2 資料與指針

xxxxxx

1.3 printf函數和i++

C語言中函數參數的執行順序 – 從右到左；

C語言中逗号運算符的執行順序 – 從左到右。

i++為先指派再遞增，++i為遞增後再指派。

參考：https://blog.csdn.net/gongluck93/article/details/68069194

例子1：

#include <stdio.h>

void main(void)
{
	int i = 3;

	printf("i=%d, ++i=%d, i++=%d\n", i, ++i, i++);	// 輸出為：i=5, ++i=5, i++=3
}

例子2：

#include <stdio.h>

void main(void)
{
	int a, x = 2, y = 5;
	a = (x + 3, y++, x++);
	printf("%d, %d, %d\n", a, x, y);		// 輸出為：2， 3， 6
}

2. Linux基礎

C語言程式的過程：編輯 -> 預處理 -> 編譯 -> 彙編 -> 連結 -> 執行。

2.1 記憶體管理

2.1.1 Linux虛拟位址空間

采用虛拟位址空間的好處：

（1）擴大位址空間（4G）；

（2）每個程序獨立占用空間；

（3）公用庫隻需儲存一份在實體記憶體，程序拷貝到虛拟位址記憶體中使用；

（4）程序通信時可以采用虛拟記憶體共享的方式；

（5）等等。

2.1.2 記憶體存儲空間

（1）未初始化的全局變量（.bss段）

（2）初始化過的全局變量（.data段）

（3）常量資料（.rodata段）

（4）代碼（.text段）

（5）棧（stack） - 函數調用和函數内的局部變量

（6）堆（heap） - 由使用者動态配置設定

2.1.3 記憶體配置設定方式

（1）從靜态存儲區配置設定。如全局變量、static變量等。

（2）在棧上建立。函數調用和函數局部變量等。

（3）從堆上配置設定。動态配置設定。

2.1.4 段錯誤以及調試方法

（1）gdb

（2）core檔案

（3）backtrace和objdump進行分析

2.2 程序與多程序

2.2.1 多程序

fork()：由fork函數建立的新程序被稱為子程序。fork函數被調用一次，但是傳回兩次。父程序傳回的值是新程序的程序ID，而子程序傳回的值是0。建立新程序成功後，系統中出現兩個基本完全相同的程序，這兩個程序執行沒有固定的先後順序，哪個程序先執行要看系統的程序排程政策

getpid()：擷取目前程序ID。

getppid()：擷取父程序ID。

例子：建立3個子程序：

嵌入式和Linux知識總結

2.2.2 Linux程序的三态

。。。。。

2.2.3 程序建立（程序的實作）

（1）pid_t fork();

（2）pid_t vfork();

fork()調用執行一次傳回2個值，對于父程序，fork()傳回子程序的程序号，而對于子程序，fork()則傳回0。

在fork()之後，子程序和父程序都會執行fork()調用之後的指令。

fork()和vfork()的差別：

fork()建立的子程序會複制父程序的資料和堆棧空間等資源，不包含task_struct和PID；而vfork()建立的子程序與父程序共享位址空間，隻有當其中一程序試圖修改欲複制的空間時才會做真正的複制動作，另外，vfork()的子程序先運作，運作完後并推出後父程序才運作。

2.2.4 僵屍程序

僵屍程序：已經結束但還沒有從程序表中删除的程序。僵屍程序太多會導緻程序表的條目滿了，進而導緻系統崩潰，倒是不占用系統資源。

産生原因：fork()建立一個新程序後，核心程序會在程序表中給它配置設定一個進入點（Entry），然後将相關資訊存儲在該進入點所對應的程序表中，這些資訊中有一項時其父程序的識别碼。子程序結束後，原來程序表中的資料會被取代為退出碼、執行時間等資料，子程序已經結束但父程序尚未讀取這些資料之前，子程序就會變成僵屍程序。

如何避免：

（1）處理子程序結束

父程序通過wait()和waitpit()等待子程序結束，但這會導緻父程序挂起。

如果父程序很忙，可以使用signal函數為SIGCHLD安裝handler處理函數，當子程序結束後就在handler中調用wait()進行回收。

（2）讓系統接管

設定signal(SIGCHLD, SIG_IGN)忽略子程序的結束，由核心進行回收。

fork()兩次，子程序退出後，孫程序被init接管，其中子程序的回收需要自己處理。

2.3 程序間的通信方式

2.3.1 管道（Pipe）和有名管道（Named Pipe或FIFO）

pipe管道是一種最基本的IPC機制，作用于有血緣關系的程序之間，完成資料傳遞。管道隻能承載無格式位元組流。

管道的原理: 管道實為核心使用環形隊列機制，借助核心緩沖區(4k)實作。其本質是一個僞檔案（實為核心緩沖區）。

例程：其中fd[0]為讀端，fd[1]為寫端。

嵌入式和Linux知識總結

2.3.2 信号（Signal）

信号：用于通知程序有某種事件發生。如果一個信号被設定為阻塞，則該信号的傳遞被延遲，直到其阻塞被取消時才傳遞給程序。

信号值小于32（SIGRTMIN）的為不可靠信号/非實時信号，例如SIGINT、SIGQUIT、SIGKILL、SIGSTOP，程序對這些信号的響應設定為預設動作。

信号值在32（SIGRTMIN）和63（SIGRTMAX）之間的為可靠信号/實時信号，支援排隊，信号不會丢失。

信号的安裝（處理）函數：signal() 和 sigaction()

signal()函數主要用于前32種非實時信号的安裝；而

sigaction()函數有3個參數，支援信号帶有參數傳遞資訊。

2.3.3 消息隊列（Message Queue）

消息隊列：消息的連結表。消息隊列連結清單由系統核心維護，每個消息隊列用消息隊列描述符來區分。

可以使用 ipcs -q 檢視系統目前使用的消息隊列。

（1）消息隊列API

1.建立：msgget

int msgget(key_t key, int msgflg);

2.發送：msgsnd

int msgsnd(int msqid, const void *msgp, size_t msgsz, int msgflg);

3.接收：msgrcv

ssize_t msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg);

msgtyp = 0: 讀取隊列中的第一條消息。

msgtyp > 0: 讀取隊列中類型為msgtyp的第一條消息，除非在msgflg中指定了MSG_EXCEPT，否則将讀取類型不等于msgtyp的隊列中的第一條消息。

msgtyp < 0: 讀取隊列中最小類型小于或等于msgtyp絕對值的第一條資訊。

4.删除及控制：msgctl

int msgctl(int msqid, int cmd, struct msqid_ds *buf);

執行個體參考：https://www.jianshu.com/p/7598e5ed5200

2.3.4 信号量（燈）（Semaphore）

信号量主要提供對程序間共享資源通路控制機制，作為程序間以及同一程序不同線程之間的同步手段。信号燈有兩種類型：二值信号燈和計算信号燈。

信号可以類比于單線鐵路上火車通過的信号，用于同步通過該軌道的火車。火車在進入單一軌道之前必須等待信号燈變為允許通行的狀态。火車進入軌道後，會改變信号狀态（信号燈值-1，P()或sem_wait()，表示占用資源），防止其他火車進入軌道；火車離開這段軌道時，必須再次改變信号的狀态（信号燈值+1，V()或sem_post()，表示釋放資源），以便允許其他火車進入軌道。

詳細閱讀：https://docs.oracle.com/cd/E19253-01/819-7051/sync-95982/index.html

（1）信号燈API

1.檔案名到健值

key_t ftok(char *pathname, char proj); 傳回與路徑pathname相對應的一個鍵值。

2.Linux特有的ipc()調用

int ipc(unsigned int call, int second, int third, void *ptr, long fifth);

參數call為SEMOP、SEMGET、SEMCTL時對應信号燈的三個系統調用：

int semop(int semid, struct sembuf *sops, unsigned nsops);

int semget(key_t key, int nsems, int semflg);

int semctl(int semid, int semnum, int cmd, union semum arg);

3.系統V信号燈API

int semget(key_t key, int nsems, int semflg); 建立和初始化信号燈，傳回信号燈集描述字。

int semop(int semid, struct sembuf *sops, unsigned nsops); 完成對信号燈的P操作或V操作。

int semctl(int semid, int semnum, int cmd, union semum arg); 實作對信号燈的各種控制操作。

（2）競争問題

競争狀态：當第一個建立信号燈的程序在初始化信号燈時，第二個程序又調用semget，并且發現信号燈已經存在，此時，第二個程序必須具有判斷是否有程序正在對信号燈進行初始化的能力。

解決方法：當semget建立一個新的信号燈時，信号燈結構semid_ds的sem_otime成員初始化後的值為0。是以，第二個程序在成功調用semget後，可再次以IPC_STAT指令調用semctl，等待sem_otime變為非0值，此時可判斷該信号燈已經初始化完畢。（這種解決方法時基于一個假定：第一個建立信号燈的程序必須在初始化完信号燈後調用semop，這樣sem_otime才能變為非0值。）

嵌入式和Linux知識總結

執行個體參考：

https://www.iteye.com/blog/kenby-1165042

https://www.ibm.com/developerworks/cn/linux/l-ipc/part4/index.html

– 以上主要指的是System V信号量。

（3）差別System V信号量和POSIX信号量

信号量有2種實作：傳統的System V信号量和新的POSIX信号量。主要差別有：

① 對于所有System V信号量函數，在它們的名字裡面沒有下劃線，而POSIX信号量函數都有一個下劃線。

② 對于POSIX信号量，可以有命名的信号量（有名信号量），例如，信号量有一個檔案關聯它們。

System V信号量，常用于程序的同步。POSIX信号量來源于POSIX技術規範的實時擴充方案（POSIX Realtime Extension），常用于線程。

System V信号量	POSIX信号量
頭檔案	#include <sys/sem.h>	#include <semaphore.h>
API函數	semget(), semctl(), semop()	sem_getvalue(), sem_post(), semtimewait(), sem_trywait(), sem_wait()
sem_init(), sem_destroy()
sem_open(), sem_close(), sem_unlink()

使用差別：

1.System V的信号量一般用于程序同步，且是核心持續，函數為：

semget(), semctl(), semop()

2.POSIX的有名信号量一般用于程序同步，有名信号量是核心持續的，函數為：

sem_open(), sem_close(), sem_unlink()

3.POSIX的無名信号量一般用于線程同步，無名信号量是程序持續的，函數為：

sem_init(), sem_destroy()

舉例：

（1）System V 二值信号量 + 共享記憶體：

/*
 * Description: semaphore to control share resources
 * (1) 使用信号燈(二值信号燈)來同步共享記憶體的操作
 * (2) 程式建立一塊共享記憶體，然後父子程序采用信号燈共同修改共享記憶體
 * Date: 2019-08-31
 */
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/wait.h>

#define SHM_KEY 0x33
#define SEM_KEY 0x44

union semun {
    int val;
    struct semid_ds *buf;
    unsigned short *array;
};

/*
 * Verhogen，增加（信号值+1），相當于釋放資源
 */
int V(int semid)
{
    struct sembuf sb;

    sb.sem_num = 0;
    sb.sem_op = 1;
    sb.sem_flg = SEM_UNDO;

    if(semop(semid, &sb, 1) == -1) {
        perror("semop error!");
        return -1;
    }

    return 0;
}

/*
 * Proberen，減小（信号值-1），相當于占用資源
 */
int P(int semid)
{
    struct sembuf sb;

    sb.sem_num = 0;
    sb.sem_op = -1;
    sb.sem_flg = SEM_UNDO;

    if(semop(semid, &sb, 1) == -1) {
        perror("semop error!");
        return -1;
    }

    return 0;
}


int main(void)
{
    pid_t pid;
    int shmid, semid;
    union semun semopts;
    int i;
    int *ptr;
    int status;

    /* 建立一塊共享記憶體，存一個int變量 */
    shmid = shmget(SHM_KEY, sizeof(int), IPC_CREAT | 0600);
    if(shmid == -1) {
        perror("shmget error!");
    }
    /* 将共享記憶體映射到程序，fork後子程序可以繼續映射 */
    ptr = (int *)shmat(shmid, NULL, 0);
    if(ptr == (void *)-1) {
        perror("shmat error!");
    }
    *ptr = 100;
    printf("initial int value: %d\n", *ptr);

    /* 建立一個信号量用來同步共享記憶體的操作 */
    semid = semget(SEM_KEY, 1, IPC_CREAT | 0600);     // 信号集中隻有一個信号燈
    if(semid == -1) {
        perror("semget error!");
    }
    /* 初始化信号量 */
    semopts.val = 1;
    if(semctl(semid, 0, SETVAL, semopts) == -1) {
        perror("semctl setval error!");
    }

    /* 父子程序修改共享記憶體的資源 */
    pid = fork();
    if(pid < 0) {
        perror("fork error");
    }
    else if(pid == 0) {     // 子程序
        /* 子程序對共享記憶體的資料加1 */
        for(i=0; i<5; i++) {
            P(semid);       // 子程序占用資源
            (*ptr)++;
            V(semid);       // 子程序釋放資源
            printf("(child)讀取共享記憶體資料中的值: %d\n", *ptr);
        }
    }
    else {                  // 父程序
        /* 父程序對共享記憶體的資料減1 */
        for(i=0; i<5; i++) {
            P(semid);
            (*ptr)--;
            V(semid);
            printf("(father)讀取共享記憶體資料中的值: %d\n", *ptr);
        }

        if(waitpid(pid, &status, 0) != pid) {
            printf("child process failed!\n");
        }
        else {
            printf("child process returned value = %d\n", status);
        }

        printf("finally int value: %d\n", *ptr);
        printf("father process return.\n");
    }

    return 0;
}

（2）posix信号量 + 共享記憶體：

/*
 * Description: semaphore to control share resources
 * (1) 使用信号燈(POSI有名信号量)來同步共享記憶體的操作
 * (2) 程式建立一塊共享記憶體，然後父子程序采用信号燈共同修改共享記憶體
 * Date: 2019-08-31
 * make: gcc posix_semaphore.c -o posix_semaphore -pthread
 *       (posix庫不包含在Linux預設庫中)
 */
#include <stdio.h>
//#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/stat.h>       /* for mode constants */
#include <semaphore.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <fcntl.h>          /* for O_* constants */

#define SEM_PATH    "/my_posix_sem"
#define SHM_KEY 0x33


int main(void)
{
    pid_t pid;
    int shmid;
    sem_t *sem;
    int i;
    int *ptr;
    int status;

    /* 建立一塊共享記憶體，存一個int變量 */
    shmid = shmget(SHM_KEY, sizeof(int), IPC_CREAT | 0600);
    if(shmid == -1) {
        perror("shmget error!");
    }
    /* 将共享記憶體映射到程序，fork後子程序可以繼續映射 */
    ptr = (int *)shmat(shmid, NULL, 0);
    if(ptr == (void *)-1) {
        perror("shmat error!");
    }
    *ptr = 100;
    printf("initial int value: %d\n", *ptr);

    /* posix的有名信号量是核心持續的 */
    /* 調用sem_unlink删除以前的信号量 */
    sem_unlink(SEM_PATH);
    /* 建立一個新的信号量，初始值為1。sem_open會建立共享記憶體，是以信号量是核心持續的 */
    sem = sem_open(SEM_PATH, O_CREAT, 0600, 1);
    if(sem == SEM_FAILED) {
        perror("sem_open error!");
    }

    /* 父子程序修改共享記憶體的資源 */
    pid = fork();
    if(pid < 0) {
        perror("fork error");
    }
    else if(pid == 0) {     // 子程序
        /* 子程序對共享記憶體的資料加1 */
        for(i=0; i<5; i++) {
            sem_wait(sem);       // 子程序占用資源
            (*ptr)++;
            sem_post(sem);       // 子程序釋放資源
            printf("(child)讀取共享記憶體資料中的值: %d\n", *ptr);
        }
    }
    else {                  // 父程序
        /* 父程序對共享記憶體的資料減1 */
        for(i=0; i<5; i++) {
            sem_wait(sem);
            (*ptr)--;
            sem_post(sem);
            printf("(father)讀取共享記憶體資料中的值: %d\n", *ptr);
        }

        if(waitpid(pid, &status, 0) != pid) {
            printf("child process failed!\n");
        }
        else {
            printf("child process returned value = %d\n", status);
        }

        printf("finally int value: %d\n", *ptr);
        printf("father process return.\n");
    }

    return 0;
}

2.3.5 共享記憶體（Shared Memory）

共享記憶體：多個程序共享一塊記憶體空間，程序可以直接讀寫記憶體，效率高（程序間通信最快的方式），讀寫前需要某種同步機制（如互斥鎖和信号量）。

參考：https://blog.csdn.net/qq_27664167/article/details/81277096

共享記憶體的使用流程：

① ftok函數生成鍵值，key_t ftok(const char *path, int id);

② shmget函數建立共享記憶體空間并傳回共享記憶體辨別符，int shmget(key_t key, size_t size, int flag);

③ shmat函數根據共享記憶體辨別符擷取共享記憶體空間的位址，void *shmat(int shmid, const void *addr, int flag);

④ shmdt函數進行分離（不是從系統中删除共享記憶體和結構），int shmdt(const void *addr);

⑤ shmctl函數進行删除共享存儲空間，int shmctl(shmid, IPC_RMID, NULL);

示例：

（1）建立一個新的共享記憶體，并寫入一個資料。

嵌入式和Linux知識總結

（2）建立共享記憶體空間（如果已經存在，則直接使用），并讀取其中的資料。

嵌入式和Linux知識總結

2.3.6 套接字（Socket）

套接字：可用于不同機器之間的程序通信。

2.4 線程與多線程

線程：程序的一個實體，是CPU排程和分派的基本機關。

2.4.1 多線程

2.4.2 多線程的實作

pthread_create()，例如：

pthread_t thread1;

ret = pthread_create(&thread1, NULL, (void *)myThread1, NULL);

2.4.3 線程同步機制

（1）互斥鎖（也稱互斥量）可以用來同步同一程序中的多個線程，用于保護臨界區（共享資源），以保證在任何時刻隻有一個線程能夠通路共享的資源。

互斥鎖的操作流程：

1）定義一個全局的鎖；pthread_mutext_t

2）初始化鎖；pthread_mutex_init()

3）建立線程；

4）上鎖、操作共享資源、解鎖；pthread_mutex_unlock(), pthread_mutex_lock()

5）線程退出，釋放資源（銷毀鎖）。pthread_mutex_destroy()

例子：

嵌入式和Linux知識總結

如果線程thread1或線程thread2通路g_value資源前不上鎖，則這2個線程的運作會不同步，導緻g_value資料計算結果不是預期的。

（2）條件鎖（也稱條件變量）：用于線上程之間同步共享資料的值。條件變量提供一種線程間通信機制：當某個共享資料達到某個值時，喚醒等待這個共享資料的一個/多個線程。即，當某個共享變量等于某個值時，調用 signal/broadcast。此時操作共享變量時需要加鎖。

主要的系統調用為：

1）初始化條件變量；pthread_cond_init()

2）喚醒一個等待目标條件變量的線程；pthread_cond_signal()

3）等待目标條件變量，需要一個加鎖的互斥鎖確定操作的原子性；pthread_cond_wait()

4）銷毀條件變量；pthread_cond_destroy()

2.4.4 鎖機制

Linux的4種鎖：

（1）互斥鎖：在任何時刻都隻能有一個線程通路該對象。當擷取鎖操作失敗時，線程會進入睡眠，直到鎖被釋放。

（2）讀寫鎖：分為讀鎖和寫鎖。同一時刻隻能有一個線程獲得寫鎖，但處于讀操作時可以允許多個線程同時獲得讀鎖。

（3）自旋鎖：在任何時刻都隻能有一個線程通路該對象。但當擷取鎖操作失敗時，會原地自旋，直到鎖被釋放。

（4）RCU：在修改資料時，首先需要讀取資料，然後生成一個副本，對副本進行修改。修改完成後，再将老資料update成新的資料。

死鎖産生的4個必要條件：

（1）互斥條件：程序對所配置設定到的資源不允許其他程序通路。

（2）不可剝奪條件：程序已獲得的資源，在未完成使用之前，不可被剝奪，隻能在使用後自己釋放。

（3）請求和保持條件：程序獲得一定的資源後，又對其他資源送出請求，但是該資源可能被其他程序占有，此時請求阻塞，但該程序不會釋放自己已經占有的資源。

（4）環路等待條件：程序發生死鎖後，必然存在一個程序 - 資源之間的環形鍊。

死鎖消除的方法：

（1）可剝奪資源：即當程序新的資源未得到滿足時，釋放已占有的資源，進而破壞不可剝奪的條件。

（2）剝奪請求和保持條件：資源一次性配置設定。

（3）資源有序配置設定法：系統給每類資源賦予一個序号，每個程序按編号遞增的請求資源，釋放則相反，進而破壞環路等待的條件。

3. 硬體接口和協定

3.1 ARM架構

。。。。。

3.2 RAM和ROM的差別

ROM：（Read Only Memory）斷電不丢失資料。隻讀存儲器在單片機中用來存儲程式資料、常量資料或變量資料。

RAM：（Rondom Access Memory）斷電丢失資料。随機通路存儲器用來存儲程式中用到的變量。凡是整個程式中，所用到的需要被改寫的量，都存儲在RAM中，“被改寫的量”包括全局變量、局部變量、堆棧段。

單片機運作時需要調用某個程式/函數/固定函數時就需要讀取ROM，然後在RAM中執行這些程式/函數的功能，所産生的臨時資料也都存在RAM中，斷電後這些臨時資料就丢失了。

3.3 硬體接口

3.3.1 UART

3.3.2 SPI

SPI：（Serial Peripheral Interface）是一種同步的、全雙工的串行接口。

參考： https://blog.csdn.net/weiqifa0/article/details/82765892

SCLK: 時鐘信号，由主裝置産生
MOSI: 主裝置輸出從裝置輸入
MISO: 主裝置輸入從裝置輸出
CS: 片選信号

MOSI/MISO資料的傳輸是根據SCLK的時鐘脈沖來一位一位傳輸的（普通串行通信一次傳輸至少8位），資料在時鐘上升沿或下降沿時改變，在緊接着的下降沿或上升沿被讀取。支援資料的輸出和輸入同時進行，即全雙工。

SCLK信号線隻由主裝置控制。

SPI接口的一個缺點：沒有指定的流控制，沒有應答機制确認是否接收到資料。

SCLK時鐘的極性和相位：

CPOL: 時鐘極性選擇，0：SPI總線空閑為低電平，1：SPI總線空閑為高電平。
CPHA: 時鐘相位選擇，0：在SCK第一個跳變沿采樣，1：在SCK第二個跳變沿采樣。

3.3.3 I2C

3.3.4 USB

3.3.5 CAN

CAN總線标準之規定了實體層和資料鍊路層，不同的CAN标準僅實體層不同。

實體層和資料鍊路層：ISO11898；

應用層：不同的應用領域使用不同的應用層标準。

嵌入式和Linux知識總結

參考：https://zhuanlan.zhihu.com/p/32221140

CAN總線特征：

CAN總線采用差分信号傳輸。

當處于邏輯1，CAN_High和CAN_Low的電壓差小于0.5V時，稱為隐性電平（Recessive）；

當處于邏輯0，CAN_High和CAN_Low的電壓差大于0.9V時，稱為顯性電平（Dominant）。

CAN總線通信原理可簡單描述為多路載波偵聽+基于消息優先級的沖突檢測和非破壞性的仲裁機制（CSMA/CD+AMP），CSMA（Carrie

Sense Multiple Access），CD+AMP（Collision

Detection + Arbitration on Message Priority）。

資料幀：

資料幀以一個顯性位（邏輯0）開始，以7個連續的隐性位（邏輯1）結束。CAN總線的資料幀有标準格式（Standard Format）和擴充格式（Extended Format）的區分。

嵌入式和Linux知識總結

資料幀可以分為七段：

（1）幀起始（SOF）

辨別一個資料幀的開始，固定一個顯性位。

嵌入式和Linux知識總結

用于同步，總線空閑期間的任何隐性到顯性的跳變都将引起節點進行硬同步。隻有總線在空閑期間節點才能夠發送SOF。

（2）仲裁段（Arbitration Field）

仲裁段的内容主要為本資料幀的ID資訊，另外還有RTR, IDE, SRR位。在CAN協定中，ID決定着資料幀發送的優先級，也決定着其他裝置是否會接收這個資料幀（根據ID過濾封包）。

嵌入式和Linux知識總結

（3）控制段

最主要的是DLC（Data Length Code）段，它是用二進制編碼表示本封包中的資料段包含多少個位元組。

嵌入式和Linux知識總結

（4）資料段

資料幀的核心内容，有0-8個位元組長度，由DLC确定。

嵌入式和Linux知識總結

（5）CRC段

CAN的封包包含了一段15位的CRC校驗碼，一旦接收端計算出的CRC碼跟接收到的CRC碼不同，就會向發送端回報出錯資訊以及重新發送。

在CRC校驗碼之後，有一個CRC界定符（DEL），它為隐性位，主要作用是把CRC校驗碼與後面的ACK段隔開。

嵌入式和Linux知識總結

（6）ACK段

包含确認位（ACK slot）和界定符（Delimiter, DEL）。ACK在發送節點發送時，為隐性位。當接收節點正确接收到封包時，對其用顯性位覆寫。DEL界定符同樣為隐性位，用于隔開。

嵌入式和Linux知識總結

（7）幀結束段（End-of-Frame, EOF）

幀結束段由發送端發送7個隐性位表示結束。

嵌入式和Linux知識總結

參考（轉載）來自：https://zhuanlan.zhihu.com/p/32221140

同步：

CAN總線使用位同步的方式來確定通信時序，以及對總線的電平進行正确采樣。

3.3.6 CANFD

CANFD，參考：https://zhuanlan.zhihu.com/p/79389547。

3.3.7 RS485

3.4 無線通信方式和協定

3.4.1 WiFi協定

WiFi配網有兩種方式：

（1）AP-mode

（2）smartconfig（airkiss）

WiFi是指WLAN中的802.11，是MAC層協定。

802.11.n：因為傳輸速率在很大的程度上取決于Channel（信道）的ChannelWidth有多寬，而802.11n中采用了一種技術，可以在傳輸資料的時候将兩個信道合并為一個，再進行傳輸，極大地提高了傳輸速率（這又稱HT-40，high through）。

在802.11中的幀有三種類型：

（1）管理幀（Management Frame，例如Beacon幀、Association幀）：主要用來加入或退出無限網絡，以及處理基站之間的連接配接轉移。

（2）控制幀（Control Frame，例如RTS幀、CTS幀、ACK幀）：負責區域的清空、信道的獲得和載波監聽的維護；與資料幀搭配使用，收到資料時給予應答。

（3）資料幀（Data Frame，承載資料的載體，其中的DS字段用來辨別方向很重要）：負責在工作站之間的資料傳輸。

參考連結：https://wenku.baidu.com/view/51b4aedbdd88d0d233d46aaa.html

管理幀：

嵌入式和Linux知識總結

控制幀：

嵌入式和Linux知識總結

資料幀：

嵌入式和Linux知識總結

其他連結：

https://blog.csdn.net/leho666/article/details/89136542

https://www.jianshu.com/p/6cc4ea0dc0bc

3.4.2 BLE協定

3.4.3 ZigBee協定

ZigBee 3.0基于IEEE 802.15.4标準，2.4 GHz頻段，并且使用ZigBee PRO标準網絡層協定，即使最小、功耗最低的裝置也能實作可靠的通信。

ZigBee穩定可靠，使用多跳網狀網絡消除單點故障和擴大網絡覆寫範圍。

ZigBee非常安全，使用各種安全機制，如AES-128加密标準，裝置網絡密鑰以及幀計數器。

ZCL : Zigbee Cluster Library，Zigbee簇群庫

ZDO : Zigbee Device Object

3.4.4 LoRa協定

LoRa：僅包含鍊路層協定，并且非常适用于節點間的P2P通信。

LoRaWAN：也包含網絡層，是以可以将資訊發送到任何已連接配接到雲平台的基站。

幾種LoRa通信方式的對比：

嵌入式和Linux知識總結

LoRa和其他無限通信方式的對比：

嵌入式和Linux知識總結

LoRaWAN節點的入網：

End Node要加入LoRaWAN網絡，首先需要指派和激活。一般說來，有2種方法完成入網：ABP（Activation by Personalization，個性化激活）和OTAA（Over-the-Air Activation，空中激活）。

（1）ABP是一種簡單的入網機制，同時，它也不太安全，适合于建設私網。

它的核心原理是，LoRaWANServer和End Nodes雙方都儲存相同的3個參數：DevAddr、NwkSKey和AppSKey。

（2）OTAA是一種安全系統很高的入網機制，當然，它的代價是較複雜。

OTAA方式入網的node，在剛上電的時候，是不處于入網狀态的，此時就需要進行入網操作。

如果我們簡單的把伺服器看做一個整體，那麼入網操作的流程是這樣的：

1. node 發送入網請求，即join_request message

2. GW 收到 node 的資料，上傳給伺服器

3. 伺服器收到入網請求，同意入網，并且将裝置在伺服器注冊，建立長位址與短位址之間的聯系，生成通訊密鑰，将通訊密鑰的參數打包下發給GW，即 Join-accept message

4. GW 收到伺服器的資料，下發給 node

5. node 根據下發的資料包，得到 DevAddr、APPSKEY、NWKSKEY

LoRaWAN協定層次：

嵌入式和Linux知識總結

Class A: 終端在每次上行後緊跟2個短暫的下行接收視窗；

Class B: 除了Class A的接收視窗，裝置還會通過網關接收時間同步的信标（Beacon）在指定時間打開接收視窗

Class C: 終端基本是一直開着接收視窗，隻在發送時短暫關閉

LoRaWAN協定：

嵌入式和Linux知識總結

1.LoRa 的資料速率範圍可以從 0.3kbps 到 50kbps。為了最大程度地延長終端的電池壽命和擴大網絡容量，LoRa 網絡使用速率自适應(ADR)機制來獨立管理每個終端的速率和 RF 輸出。

2.PHY幀格式

嵌入式和Linux知識總結

3.MAC幀格式

嵌入式和Linux知識總結

4.MAC指令

嵌入式和Linux知識總結

3.4.5 NB-IoT

NB模組：移遠BC-26、芯訊通SIM7020、龍尚A9600R2

物聯網裝置管理平台：OceanConnect、中移物聯

3.5 網絡通信協定

3.5.1 TCP

參考連結：https://developer.51cto.com/art/201906/597961.htm

下圖為TCP/IP協定模型的資料組成結構。

嵌入式和Linux知識總結

TCP：是面向連接配接的、可靠的流協定。TCP通過序列号、檢驗和、确認應答、重發控制等提供可靠性傳輸。TCP處于OSI 參考模型的第4層 - 傳輸層。

TCP封包格式：

嵌入式和Linux知識總結

TCP的3次握手和4次揮手：

嵌入式和Linux知識總結

Linux socket的TCP連接配接：

Server：

Client：

3.5.1 IP

IP（IPV4、IPV6）協定處于 OSI 參考模型中的第3層 - 網絡層（主要是實作終端節點之間的通信，可以跨越不同的資料鍊路）。

IP 大緻分為三大作用子產品，它們是 IP 尋址、路由（最終節點為止的轉發）以及 IP 分包與組包。

IP封包格式：

嵌入式和Linux知識總結

IP位址分類：

A類IP位址（首位為0）: 0.0.0.0 ~ 127.255.255.255
B類IP位址（首位為10）: 128.0.0.0 ~ 191.255.255.255
C類IP位址（首位為110）: 192.0.0.0 ~ 223.255.255.255
D類IP位址（首位為1110）: 224.0.0.0 ~ 239.255.255.255

與IP相關的其他協定：

ARP及RARP協定

ARP是一種位址解析協定，根據IP位址擷取MAC位址。

RARP是将ARP反過來，從MAC位址定位IP位址的一種協定。
ICMP協定

ICMP是網絡控制封包協定。當傳送IP資料包發生錯誤，比如主機不可達、路由不可達等，ICMP協定将會把錯誤資訊封包，然後傳送回給主機。

ping是ICMP的最著名的應用，利用ICMP協定包來偵測另一個主機是否可達。原理是用類型碼為0的ICMP發請求，受到請求的主機則用類型碼為8的ICMP回應。
DNS協定

DNS（Domain Name System），用來将域名轉換為IP位址（也可以将IP位址轉換為相應的域名位址）。
DHCP協定

DHCP（Dynamic Host Configuration Protocol），動态主機配置協定，是運作在UDP協定之上。DHCP通常被用于區域網路環境，主要作用是集中的管理、配置設定IP位址。
NAT協定

NAT（Network Address Translator），在私有位址和全局位址之間轉換的協定。

3.5.3 UDP

UDP（User Datagram Protocol），使用者資料報協定，是處于OSI模型的第4層 - 傳輸層。

UDP是無連接配接的、不保證可靠的、面向封包的。

UDP封包格式：

嵌入式和Linux知識總結

3.5.4 HTTP

3.5.5 HTTPS

3.5.6 CoAP

CoAP：受限制的應用協定（Constrained Application Protocol），是一種基于消息請求/響應模型的應用協定。CoAP是基于UDP的第7層應用層協定。

1. CoAP協定的封包組成：

嵌入式和Linux知識總結

（1）Ver: 版本編号。

（2）T: 封包類型（CON、NON、ACK、RST）。

（3）TKL: CoAP辨別符長度。一種辨別符是Message ID(封包編号)，一種辨別符是Token(辨別符)。

（4）Code: 功能碼/響應碼。

（5）Message ID:

參考：https://www.jianshu.com/p/7fec0916a0d3

CoAP的DTLS介紹：

3.5.7 MQTT

MQTT：消息隊列遙測傳輸協定（Message Queuing Telemetry Transport），是一種基于釋出/訂閱模式的“輕量級”通訊協定。MQTT是基于TCP協定的第7層應用層協定。

MQTT的資料包組成：固定頭 + 可變頭（部分MQTT資料包存在） + 消息體（部分MQTT資料包存在）

嵌入式和Linux知識總結

1. MQTT固定頭

嵌入式和Linux知識總結

（1）MQTT資料包類型

嵌入式和Linux知識總結

（2）辨別位

嵌入式和Linux知識總結

QoS（服務品質）：

0: 至多一次，不確定消息到達，可能會丢失或重複。

1: 至少一次，確定消息到達，但可能會重複。

2: 隻有一次，確定消息到達，并隻有一次。

（3）剩餘長度

用來儲存可變頭和Payload消息體的總大小，bits 0 ~ 6。bit 7為1時，表示長度不夠，将使用2個Bytes來儲存長度。

嵌入式和Linux知識總結

2. MQTT可變頭

嵌入式和Linux知識總結

另外：很多控制封包的可變報頭部分包含一個2位元組的封包辨別符（資料包辨別Packet Identifier），用來識别一個唯一的資料包。這些封包是PUBLISH（QoS > 0時），PUBACK，PUBREC，PUBREL，PUBCOMP，SUBSCRIBE, SUBACK，UNSUBSCRIBE，UNSUBACK。

例如，PUBLISH的資料包辨別：資料包辨別隻需要保證在從 Sender 到 Receiver 的一次消息互動（比如發送、應答為一次互動）中保持唯一就好，隻在QoS大于1的消息中使用，因為QoS大于1的消息有應答流程。

嵌入式和Linux知識總結

封包辨別符的規定參考：https://mcxiaoke.gitbooks.io/mqtt-cn/content/mqtt/02-ControlPacketFormat.html

3. Payload消息體

嵌入式和Linux知識總結

參考：

https://www.jianshu.com/p/5c42cb0ed1e9

MQTT的TLS的介紹：

3.5.8 MQTT和TCP的差別

（1）協定位置

TCP是OSI模型的第四層傳輸層協定；MQTT是基于TCP的第七層應用層協定。

（2）協定定位

TCP是面向連接配接的、可靠的、基于位元組流的傳輸層通信協定；MQTT則是在旨在低帶寬、高延遲、不可靠的網絡下相對可靠傳輸資料的應用層協定。

（3）設計思想

TCP的核心思想是分組交換；MQTT的核心思想是簡單并适應物聯網環境。

（4）傳輸機關

TCP的傳輸機關是packet，當應用層發送位元組流，TCP将其分割成合适的封包段，最大傳輸段(MSS)受最大傳送單元(MTU)限制；MQTT的傳輸單元是消息，在MQTT Broker代理伺服器中可以設定超過1M大小的消息上限。

（5）服務品質

TCP是一個可靠的流傳輸服務，通過ACK确認和重傳機制；MQTT的QoS服務品質有3種，MQTT用戶端和MQTT Broker之間通過session機制保證消息的傳輸可靠性。

參考：

https://www.zhihu.com/question/23373904

3.5.9 OpenSSL加密

3.5.9 RTSP

4. 資料結構

程式設計 = 資料結構 + 算法

資料結構：是互相之間存在一種或多種特定關系的資料元素的集合。

算法：描述解決問題的方法。

算法的特性：有窮性、确定性、可行性、輸入、輸出；算法設計的要求：正确性、可讀性、健壯性、高效率和低存儲。

算法時間複雜度（大O階）推導方法：

用常數1取代運作時間中的所有加法常數；
在修改後的運作次數函數中，隻保留最高階項；
如果最高階項存在且不是1，則去除與這個項相乘的常數。

4.1 線性表

4.1.1 線性表的順序結構

線性表（list）：零個或多個資料元素的有限序列。

線性表的順序存儲結構優缺點：

優點：（1）無須為表示表中元素之間的邏輯關系而增加額外的存儲空間；（2）可以快速地存取表中任一位置的元素。

缺點：（1）插入和删除操作需要移動大量元素；（2）當線性表長度變化較大時，難以确定存儲空間的容量；（3）造成存儲空間的“碎片”。

（1）線性表的順序存儲結構：

typedef struct
{
	int data[MAXSIZE];
	int length;
}SqList;

（2）添加和删除元素：

/*
 * 線性表中插入一個元素
 * 時間複雜度為O(n)
 */
int ListInsert(SqList *L, int i, ElemType e)
{
	int k;

	if (L->length == MAXSIZE)
		return ERROR;
	if (i < 1 || i > L->length + 1)
		return ERROR;
	if (i <= L->length)	
	{
		for (k = L->length - 1; k > i-1; k--)
			L->data[k+1] = L->data[k];
	}

	L->data[i - 1] = e;
	L->length++;

	return OK;
 }

/*
 * 線性表中删除一個元素
 * 時間複雜度為O(n)
 */
int ListDelete(SqList *L, int i, ElemType *e)
{
	int k;

	if (L->length == 0)
		return ERROR;
	if (i < 1 || i > L->length)
		return ERROR;

	*e = L->data[i - 1];

	if (i < L->length)
	{
		for (k = i; k < L->length; k++)
			L->data[k - 1] = L->data[k];
	}

	L->length--;

	return OK;
}

4.1.2 線性表的鍊式結構

（1）線性表的鍊式存儲結構：資料域 + 指針域

typedef struct Node
{
	int data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;

（2）初始化連結清單

int InitList(LinkList *L) {
	*L = (LinkList)malloc(sizeof(Node));	// 産生頭結點，并使L指向此頭結點
	if(!(*L))
		return ERROR;
	(*L)->next = NULL;		// 頭結點的指針域為空

	return OK;
}

頭結點：

為了更友善地對連結清單進行操作，會在單連結清單的第一個結點前附設一個結點（頭結點）。頭結點的資料域可以不存儲任何資訊，也可以存儲如線性表的長度等附加資訊，頭結點的指針域存儲指向第一個結點的指針。

嵌入式和Linux知識總結

有了頭結點，對在第一進制素結點前插入結點和删除第一結點，其操作與其他結點的操作就統一了。頭結點不一定是連結清單必須要素。

（3）添加和删除元素：

/*
 * 連結清單中插入一個元素
 */
int ListInsert(LinkList *L, int i, ElemType e)
{
	LinkList p, s;
	int j;

	p = *L;
	j = 1;

	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
		return ERROR;

	s = (LinkList)malloc(sizeof(Node));		// 産生新的結點
	s->data = e;
	s->next = p->next;
	p->next = s;

	return OK;
}

/*
 * 連結清單中删除一個元素
 */
int ListDelete(LinkList *L, int i, ElemType *e)
{
	LinkList p, q;
	int j;

	p = *L;
	j = 1;

	while (p->next && j < i)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i)
		return ERROR;

	q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q);

	return OK;
}

4.2 棧（stack）

棧是限定僅在表尾（棧頂）進行插入和删除操作的線性表。

4.2.1 棧的順序結構

（1）順序結構的棧：

typedef int SElemType;
typedef struct {
	SElemType data[MAXSIZE];
	int top;
} SqStack;

（2）壓棧和出棧：

/*
 * 從棧頂中插入一個元素
 */
int Push(SqStack *S, SElemType e)
{
	if(S->top == MAXSIZE - 1)
		return ERROR;
	
	S->top++;
	S->data[S->top] = e;
	
	return OK;
}

/*
 * 删除棧頂的元素
 */
int Pop(SqStack *S, SElemType *e)
{
	if(S->top == -1)
		return ERROR;

	*e = S->data[S->top];
	S->top--;

	return OK;
}

4.2.2 兩棧共享空間

（1）兩棧共享空間結構

typedef struct {
	SElemType data[MAXSIZE];
	int top1;
	int top2;
} SqDoubleStack;

（2）壓棧和出棧

/*
 * 向棧1或棧2中插入一個元素
 */
int Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
	if(S->top1+1 == S->top2)	// 棧滿
		return ERROR;
	
	if(stackNumber == 1)			// 棧1
		S->data[++S->top1] = e;
	else if(stackNumber == 2)		// 棧2
		S->data[--S->top2] = e;
	
	return OK;
}
/*
 *
 */
int Pop(SqDoubleStack *S, SElemType *e, int stackNumber)
{
	if(stackNumber == 1) {
		if(S->top1 == -1)
			return ERROR;
		*e = S->data[S->top1--];
	}
	else if(stackNumber == 2) {
		if(S->top2 == MAXSIZE)
			return ERROR;
		*e = S->data[S->top2++];
	}
	
	return OK;
}

4.2.3 棧的鍊式結構

【易混淆點】通常，對于鍊式棧來說，是不需要頭結點的。

（1）鍊式結構棧：

typedef int SElemType;
typedef struct StackNode {
	SElemType data;
	struct StackNode *next;
} StackNode, *LinkStackPtr;
typedef struct {
	LinkStackPtr top;
	int count;
} LinkStack;

（2）壓棧和出棧：

/*
 * 從棧頂中插入一個元素
 */
int Push(LinkStack *S, SElemType e)
{
	LinkStactPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
	
	s->data = e;
	s->next = S->top;
	S->top = s;
	S->count++;

	return OK;
}

/*
 * 删除棧頂的元素
 */
int Pop(LinkStack *S, SElemType *e)
{
	LinkStackPtr q;

	if(S->count == 0)
		return ERROR;
	
	*e = S->top->data;
	q = S->top;
	S->top = q->next;
	free(q);
	S->count--;

	return OK;
}

4.3 隊列（queue）

隊列是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。隊列是一種先進先出（FIFO）的線性表。

4.3.1 順序隊列

順序隊列：頭尾相接的順序存儲結構的隊列。

（1）循環隊列的順序存儲結構：

typedef int QElemType;
typedef struct {
	QElemType data[MAXSIZE];
	int front;		// 頭指針
	int rear;		// 尾指針
} SqQueue;

（2）入隊和出隊：

/*
 * 若隊列未滿，則插入元素e為隊列的新的隊尾元素
 */
int EnQueue(SqQueue *Q, QElemType e)
{
	if((Q->rear + 1) % MAXSIZE == Q->front)
		return ERROR;
	
	Q->data = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;

	return OK;
}

/*
 * 若隊列不空，則删隊列中隊頭的元素
 */
int DeQueue(SqQueue *Q, QElemType *e)
{
	if(Q->rear == Q->front)
		return ERROR;
	
	*e = Q->data;
	Q->front = (Q->front + 1) % MAXSIZE;

	return OK;
}

（3）循環隊列的長度：

int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

4.3.2 鍊式隊列

鍊式隊列，是特殊的線性單連結清單，隻能尾進頭出的單連結清單。

【易混淆點】通常，對于鍊式隊列來說，為了操作上的友善，會将隊頭指針指向鍊式隊列的頭結點。

（1）鍊式隊列的結構：

typedef int QElemType;
typedef struct QNode {
	QElemType data;
	struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
	QueuePtr front, rear;
} LinkQueue;

（2）入隊和出隊：

/*
 * 在隊尾插入一個元素
 */
int EnQueue(LinkQueue *Q, QElemType e)
{
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if(!s)
		exit(OVERFLOW);
	
	s->data = e;
	s->next = NULL;		// 隊尾指向空指針
	Q->rear->next = s;
	Q->rear = s;
	
	return OK;
}

/*
 * 删除隊頭的一個元素（隊列不為空）
 */
int DeQueue(LinkQueue *Q, QElemType *e)
{
	QueuePtr q;

	if(Q->front == Q->rear)
		return ERROR;
	
	q = Q->front->next;
	*e = q->data;
	Q->front->next = q->next;
	
	if(Q->rear == q)
		Q->rear = Q->front;

	free(q);

	return OK;
}

4.4 字元串（string）

4.4.1 KMP模式比對算法

KMP模式比對算法的關鍵在于：主串S、子串T，若T中後部分中存在與前m個字元（m不是固定值）重複的字元，則将重複個數+1（重複個數其實是前m個字元的位置）記錄在next數組中。當T後部分在和S在比較不比對時，則讓T的指針跳到前m個字元的位置，繼續從T中與S部分比對的位置開始繼續比較（雖然T最後幾個字元和S中的不比對，但T前面部分k個字元（k < T最後部分不比對時的指針位置，k可能等于m）可能會存在與S目前指針前k個相同，其中k為next數組中T中重複字段的情況）。

next數組中的值計算時，後部分總是與前m個字元進行比較，以計算重複情況。

改良後的KMP模式比對算法：

改良後，next數組變化了：“若T中後部分中存在與前m個字元（m不是固定值）重複的字元，則将重複個數+1（重複個數其實是前m個字元的位置）記錄在next數組中”。改良的關鍵是：從T中後部分與第前m+1位不相同的那一位開始，把T中後部分與前m+1位值相同的位所對應的next數組值降低，以減少已比對過但也不相同的重複情況。

舉例：改變next[6]前面3個值，其他情況類似。

嵌入式和Linux知識總結

書中的描述：

嵌入式和Linux知識總結

4.5 樹（tree）

二叉樹

周遊

5. 算法

5.1 冒泡排序和選擇排序

（1）冒泡排序

時間複雜度：O(n^2)

冒泡排序的原理是：每相鄰的2個數比較，把大的放在兩者中的後面，每一輪的循環就會把一個目前最大的數排在目前的最後（即重的沉下去）。

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

#define N 10

int main(void)
{
	int i, j;
	int flag, tmp;
	int data[N] = {3,5,11,23,51,34,81,39,10,20};
	
	for(i=1; i<=N-1; i++) {
		flag = 1;
		for(j=0; j<N-i; j++) {
			if(data[j] > data[j+1]) {
				tmp = data[j];
				data[j] = data[j+1];
				data[j+1] = tmp;
				flag = 0;
			}
		}
		if(flag == 1)
			break;
	}
	
	printf("冒泡排序之後的結果為：\n");
	for(i=0; i<N; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	
	return 0;
}

（2）選擇排序

時間複雜度：O(n^2)

它的工作原理是：第 i 個與第 i+1 ~ N-1個來比較，把最小的數放在第 i 位，如此循環知道倒數第2個。

選擇排序是不穩定的排序方法（比如序列[5, 5, 3]第一次就将第一個[5]與[3]交換，導緻第一個5挪動到第二個5後面）

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

#define N 10

int main(void)
{
	int i, j;
	int minIndex, tmp;
	int data[N] = {3,5,11,23,51,34,81,39,10,20};
	
	for(i=0; i<N-1; i++) {
		minIndex = i;
		for(j=i+1; j<N; j++) {
			if(data[j] < data[minIndex])
				minIndex = j;
		}
		if(minIndex != i) {
			tmp = data[i];
			data[i] = data[minIndex];
			data[minIndex] = tmp;
		}
	}
	
	printf("選擇排序之後的結果為：\n");
	for(i=0; i<N; i++) {
		printf("%d ", data[i]);
	}
	printf("\n");
	
	return 0;
}

5.2 查找特定資料

（1）一個整型數組中有且僅有一個數字出現1次，其他都出現2次，找出隻出現一次的數字。（*頂科技面試）

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

#define N 11

int findNoDouble(int a[])
{
	int result = a[0];
	int i;

	for(i=1; i<N; i++) {
		result ^= a[i];
	}
	
	return result;
}

int main(void)
{
	int data[N] = {3, 1, 2, 5, 8, 3, 8, 9, 5, 2, 1};
	int ret;

	ret = findNoDouble(data);
	printf("the once number is: %d\n", ret);

	return 0;
}

（2）100 ~ 999的3位數整型數組中，查找符合以下條件的資料：3位數中有2位的數字相同，且3位數為某個數的平方，如144。（*為嵌入式C面試）

5.3 牛客網題目

5.3.1 資料結構

（1）連結清單從尾到頭列印所有元素

C語言：

/* 從尾到頭輸出清單的元素 */
int LinkListPrintFromTailToHead(LinkList L)
{
    LinkList p;
    int buff[1024];
    int i = 0, j;

    p = L->next;
    while(p) {
        buff[i++] = p->data;
        p = p->next;
    }

    for(j=i-1; j>=0; j--) {
        printf("%d ", buff[j]);
    }
    printf("\n");

    return OK;
}

C++：

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> result;
        stack<int> arr;
        int len;
        
        ListNode *p = head;
        while(p != NULL) {
            arr.push(p->val);
            p = p->next;
        }
        
        len = arr.size();
        for(int i=0; i<len; i++) {
            result.push_back(arr.top());
            arr.pop();
        }
        
        return result;
    }
};

（2）使用2個棧實作隊列

class Solution
{
public:
    void push(int node) {
        stack1.push(node);		// 棧1儲存新壓棧的那一部分資料
    }

    int pop() {
        int result;
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.top());	// 棧2為空的時候剪切棧1中目前所有資料
                stack1.pop();
            }
        }
        
        result = stack2.top();	// 棧2的棧頂元素即為隊列的隊頭元素
        stack2.pop();
        
        return result;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

5.4 C語言的經典問題

5.4.1 漢諾塔問題

https://www.zhihu.com/question/24385418

#include <cstdio>
using namespace std;

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 0)
        return;
    hannoi (n - 1, from, to, buffer);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hannoi (n - 1, buffer, from, to);
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

其他一些常見問題：

1.位元組對齊

2.如何比較2個結構體是否相等，是否可以用memcmp來比較

3.符合判斷2個float類型資料是否相等

4. 野指針

野指針不是NULL指針，是指向“垃圾”記憶體的指針。野指針的成因：

（1）指針變量沒有被初始化。任何指針變量剛被建立時不會自動成為NULL指針，它的預設值是随機的，它會亂指一氣。

（2）指針p被free或者delete之後，沒有置為NULL，讓人誤以為p是個合法的指針。free或delete指針p後，隻是把指針所指的記憶體給釋放調，但并沒有把指針本身幹掉（p的位址仍然不變）。

5.怎樣定位棧溢出

閱讀書籍：

《高品質嵌入式Linux程式設計》

《大話資料結構》