c_learning_note

				C Learning Note

1973 C language

C语言的特点：
	1. 基础性语言
	2.

需要阅读优秀的程序段
大量练习，面试题

1、数组和指针


hello.c:
编译器gcc：
源文件 - 预处理 - 编译 - 汇编 - 链接 -  可执行文件

需要了解：vim编辑器，常用脚本

				一、基本概念

1、以helloworld为例对写程序的思路提出如下要求：
	1）头文件包含的重要性
	2）以函数为单位来进行程序编写
	3）声明部分+实现部分
	4）return 0;
	5）多用空格和空行！
	6）适当添加注释(/* */, //...)

2、算法：解决问题的方法。（流程图，NS图，有限状态机FSM - Finite State Machine）
3、程序：用某种语言实现算法
4、进程：
	1）防止写越界，防止内存泄漏，谁打开谁关闭，谁申请谁释放

				二、数据结构，运算法和表达式

1、数据类型：（基本数据类型）
	1）基本类型
		- 数值类型：
			· 整形
				= 短整型short
				= 整型int
				= 长整型long
			· 浮点型
				= 单精度float
				= 双精度double
		- 字符类型 char
	2）构造类型
		- 数组
		- ...
		- 枚举 emu
	3）指针类型
	4）空类型 void

基本类型
	1）所占字节数：有类型之间的所占字节数范围区别，具体字节数取决于具体的机器（32位，64位等等）
	2）存储区别
		整型数是以补码形式存储
			-254 -> 254 -> 1111 1110 取反 +1
		浮点型数以0.314*10^1 -> 整数部分为0，精度和指数
			单精度 32位
				|31|30|..|23|22|...|0|
			符号1位  指数8位  浮点数23位
			双精度 64位
				剩下的位数都加在指数上，所以可以表示更大的数字
	3）不同类型的数据间类型转换
		example 
			254 -> unsigned int -> 32位（假设
			8421法：
				2进制转8进制，3个数字一组（111 -> 4+2+1 -> 7）
				2进制转16进制，4个数字一组 （1111 -> 8+4+2+1 -> F）
			(254)10 = (11111110)2 = (011 111 110)2 = (376)8 = (1111 1110)2 = (FE)16
			二进制 B111111110
			八进制 0376
			十六进制 0xFE
		隐性转换
			小容器不能装大内容，会失去精度		
			低精度和高精度进行运算，所得结果会是高精度类型
		显性转换 -> 强制类型转换
	4）特殊性：
		（1）布尔型bool
		（2）float类型，不是一个具体精确的值，只是一个有限精度的数，所以需要注意非常高精度的数运算
		（3）char型是否有符号，未定义的行为
		（4）不同形式的0值：0, '0', "0", '\0'
				需要进行区分
		（5）数据类型与后续代码中所使用的输入输出要相匹配

2、常量与变量
常量：在程序执行过程中值不会发生变化的量
	分类：
	1）整型常量
		1，790...
	2）实型常量
		3.14，5.26...
	3）字符常量：由单引号引起来的单个的字符或转义字符
		'a', '\n', '\t', '\015', '\x7f', ...
	4）字符串常量：由双引号的引起来的一个或多个字符组成的序列
		""（空串）, "string", "a", "abc\n\021\018"
	5）标识常量
		define, 处理在程序的预处理阶段，占编译时间，一改全改
			缺点：不检查语法，只是单纯的宏体与宏名之间的替换

变量：用来保存一些特定内容，并且在程序执行过程中值随时发生会变化的量
	定义：[存储类型] 数据类型 标识符 = 值;
					 TYPE	  NAME   = VALUE;

		标识符：由字母、数字、下划线组成且不能以数字开头的一个标识序列
				内存分配空间的名字
			写标识符的要求：尽量做到见名生义
		数据类型：基本数据类型+构造类型
		值：注意匹配（数据类型）
		存储类型：auto static register extern(说明型）
			auto：默认（没有指定存储类型所使用的类型）自动分配和回收空间
			register：（建议型）寄存器类型（寄存器存在于CPU中）只能定义局部变量，不能定义全局变量；
				大小有限制，只能定义32位大小的数据类型（在32位的环境下），如double就不行；
				寄存器没有地址，所以一个寄存器类型的变量无法打印出地址查看或使用。
			static：静态型，自动初始化为0值或空值，并其变量的值有继承性。另外，常用于修饰变量或函数
			extern：说明型，意味着不能改变被说明的变量的值或类型

	变量的生命周期和作用范围：
		1）全局变量和局部变量
		2）局部变量和局部变量
		3）存储类型比较 -- 图片

3、运算符和表达式

表达式与语句的区别
	加分号叫语句，不加叫表达式
	i = 1;
	i  = j * 2;

运算符部分：
	1）每个运算符所需要的参与运算的操作数个数
	...
	3）条件判断（op1 ? op2 : op3) -- 如果op1的值为真则取op2的值，否则取op3的值
	4）逻辑运算符（&&,||）的短路特性（是否对表达式进行运算）
	5）位运算的重要意义
		（在当前嵌入式开发中尤为重要）
		(<<,  >>, ~, |, ^, &)
		<< 左移一位，最右边补零，相当于乘以2
		>> 右移一位，最左边补零，相等于除以2
		~ 取反 (0 -- 1, 1 -- 0)

		｜ 按位取或
		
			1 1 0 0
		｜  1 0 0 1
		-------------
			1 1 0 1
	
		& 按位取与 
 
	        1 1 0 0
        &   1 0 0 1
        -------------
            1 0 0 0

		^ 异或， 相同为0，不同为1

	        1 1 0 0
        ^   1 0 0 1
        -------------
            0 1 0 1


		需要掌握的算法：
			（1）将操作数中第n位置1，其他位不变； num = num | 1 << n; 
				-- 将1左移n位，对num和1（n个0）取按位或，因为第n位是1，所以所得结果的第n位一定是1，其他位不变
			（2）将操作数中第n位清0，其他位不变； num = num & ~(1 << n);
				-- 将1左移n位之后取反，结果为，对num和0（n个0）取按位与，因为第n位是0，所以所得结果的
			（3）测试第n位：if(num & 1 << n);
			（4）从一个指定宽度的数中取出其中的某几位？

				三、输入输出专题

input & output -> I/O（标准IO，文件IO）
1、格式化输入输出函数：
	scanf
		int scanf(const char *restrict format, ...);
			format: 抑制符*
			%s的使用是比较危险的，因为不知道存储空间大小
			scanf放在循环结构中要注意能否接收到正常有效的内容
	printf
		int printf(const char * restrict format, ...);
			format: "%[修饰符]格式字符", 参照图片标准输出修饰符与输入输出格式
					修饰符，宽度，保留小数位数，对齐等等		
2、字符输入输出函数：
	getchar
		int getchar(void);
	putchar
3、字符串输入输出函数：
	gets(!)
		char *gets(char *str);
			it is not safe to use gets(), use fgets() or getline() instead
			
		char *fgets(char * restrict str, int size, FILE * restrict stream);

		ssize_t	getline(char ** restrict linep, size_t * restrict linecapp, FILE * restrict stream);
	puts

输入、输出部分的练习

				四、流程控制

顺序，选择，循环
NS图，流程图，工具Dia
简单结构与复杂结构：自然结构

顺序：语句逐句执行
选择：出现了一种以上的情况
循环：在某个条件成立的情况下，重复执行某个动作

详解switch-case

有限状态机

语法格式：

	switch(exp)
	{
		case 常量或常量表达式:
			break;
		case 常量或常量表达式:
            break;		
		...
		
		default:
	}


if-goto:（慎用）
	goto实现的是无条件跳转，且不能跨函数跳转
	
					五、数组
							构造类型之一，连续存放


一维数组
	1 定义
		[存储类型] 数据类型 标识符 [下标]

	2 初始化
			用以逗号分隔的值列表来初始化数组
		不初始化
		全部初始化
		部分初始化
		static -- 自动初始化所有值为0
		
	3 元素引用
		数组名[下标]

	4 数组名
		当前数组的起始位置 arr -- arr[0] 地址相同 数组名是地址常量
	5 数组越界
		由于存在指针偏移，数组越界编译器不检查
			int	arr[3] = {1,2,3}
			printf(arr[3]); -- 这一行是的值为 arr[3] = *(arr + 3) 其实是找到了arr位置+3的地址所代表的值
练习：
1. 求fibonacci数列的前十项，并在数组中逆序存放
2. 数据排序：冒泡，选择法，快速排序
3. 进制转换
4. 删除法求质数


二维数组
	1 定义，初始化
		[存储类型] 数据类型 标识符 [行下标] [列下标]
	2 元素引用
		数组名[行标][列标]
	3 存储形式
		顺序存储，按行存储
	4 深入理解二维数组
		行指针
	a[0]->	a[0][0]
			a[0][1]
			a[0][2]
	a[1]->	a[1][0]	
            a[1][1]
            a[1][2]

练习：
1 行列互换（转置）
2 求最大值及其所在位置
3 求各行各列的和
4 矩阵乘积


字符数组
	1 定义，初始化，存储特点
		[存储类型] 数据类型 标识符 [下标]...
		初始化：
			单个字符初始化
			字符串常量初始化
			
	2 输入输出
		fgets puts scanf printf
	3 常用函数
		strlen, strcat, strcpy, strcmp
				strncat, strncpy, strncmp
		
		带n的函数考虑数组越界的问题 security consideration


练习：
	计算一个string中的单词个数（以空格隔开）


多维数组

int arr[2][3][4]


							六、指针

1 变量与地址的关系
2 指针与指针变量
3 直接访问和间接访问

0x4000->	0x30000->	0x2000->
	0x3000		0x2000			1
	  q			  p				i

	int i = 1;
	int *p = &i;
	int **q = &q;

	q = 0x3000 = &p
	&q = 0x4000
	*q = *(&p) = p = &i = 0x2000
	**q = *p = i = 1
	&p = 0x3000
	*p = i = 1 （间接访问）
	&i = p = 0x2000
	i = 1  （直接访问）

4 空指针与野指针
	空指针 NULL
	将指针置为空是为了防止野指针
	指针一定义，就需要指向某块内存，如果没有，则置为NULL

	野指针，没有明确指向的指针

5 空类型的指针
	void *p
	当不明确当前需要的类型时，可以定义为void类型
6 定义、初始化的书写规则
	int *p = &i;	

7 指针运算
	& 取地址
	* 取值
	 ++ --
	关系运算（比较大小 -- 比较指向地址的高低）

8 指针与数组的关系
	指针与一维数组
		int a[3]
		----------------
		|  1 |  2 |  3 |
		----------------
		a[0] a[1] a[2]
		|	 |	  |
		|	 |	  |
	   a+0	a+1  a+2
		p	p+1  p+2

	int *p = a

	取值	a[i] = *(a+i) = *(p+i) = p[i]

	取地址	&a[i] = a+i = p+i = &p[i]

	a 是常量
	p 是变量

	指针与二维数组

		行指针和列指针
		a[2][3] -- a指向第一行，a+1指向第二行
		初始化*p = *a = &a[0][0]
		p 指向第一个元素，p+1指向第二个元素即&a[0][1]

	指针与字符数组
		了解字符指针 char *str 和字符数组 char str[]的区别		

9 const与指针
	const 将变量常量化

	常用的定义宏 #define PI 3.14
		问题在于只是进行宏名和宏体的替换，不检查语法（预编译）	

	可以用变量保存常量值 -- float pi = 3.14; （危险）
		因为pi值可能发生变化
	使用const：const float pi = 3.14; （安全）
		pi的值不会发生改变

	指针常量：指向的指向不可以发生改变，但指向的内容可以发生改变
	常量指针：指针的指向（值）可以发生改变，但指向的内容不能发生改变


10 指针数组与数组指针
	数组指针： [存储类型] 数据类型 （*指针名）[下标] = 值
			如：
				int (*p)[3];  -> TYPE NAME; -> int[3] *p;
					指针指向的是占3个int的数组，p+1移动的3个int的大小
	指针数组：
			如：[存储类型] 数据类型 * 数组名[下标]
				int * arr[3]; -> TYPE NAME; -> int *[3] arr;


11 多级指针的使用
	二级指针是比较常用的，再高级的指针就不是很常用了


				七、函数

1 函数的定义
	数据类型 函数名（[数据类型 形参名, 数据类型 形参名, ...]）
2 函数的传参
	值传递
		void print_value(int a, int b);
			call: print_value(i, j);
	地址传递
		void swap(int *p, int *q);
			call: swap(&i, &j);
	全局变量

3 函数的调用
	嵌套调用
		nested function --
			main: call dist()
				dist: call min() max()
	递归
		阶乘
		斐波那契数列

4 函数与数组

	(1)	一维数组

	传参与函数定义
	int a[n] = {1,2,3,4,5,6};
	int *p = a;

传参(实参)
-> a		*a		a[0]		&a[3]		p[i]		p		*p		p+1

函数定义(形参)
-> int*		int		int			int*		int			int*	int		int*

	(2)	二维数组

	传参与函数定义
	int a[M][N] = {...};
	int *p = *a;
	int (*q)[N] = a;

传参（实参）
-> a[i][j]	*(a+i)+j	a[i]+j		p[i]	*p		p+3		q[i][j]		*q			q		q+2

函数定义（形参）
-> int		int *		int *		int		int		int*	int			int*	int(*)[N]	int(*)[N] 


5 函数与指针
	指针函数
		返回值是一个指针
		返回值 * 函数名 （形参）
		如：int * func(int);
			
		如何去接收一个指针函数：
			需要定义一个指向指针函数的函数指针
				int * (*func) (int);
					
	函数指针
		指针指向函数
		类型 (*指针名) (形参)
		如：int (*p) (int);
	函数指针数组
		包含函数指针的数组
		类型 （*数组名[下标]）（形参）
		如：int (*arr[n]) (int);
	
	指向指针函数的函数指针数组
		数组中包含返回值为指针的函数
		int * (*funcp[N])(int);


				八、构造类型

结构体 struct
	1 产生的原因和意义
		把不同类型的数据存放在同一个空间
	2 类型的描述
		struct 结构体名
		{
			数据类型 成员1;
			数据类型 成员2;
			...	
		};

	3 嵌套定义
		struct name_st
		{
			int var_name1;

			...
			struct name_st
			{


			} varibale_name;
			...
		};
	4 定义变量（常规变量、数组、指针）、初始化及成员引用
		成员引用：
			变量名.成员名
			struct name_str varibale_name = {...};
			name_st.var_name1 = 1;
			指针 -> 成员名
			(*指针).成员名
		

	5 结构体在内存中所占空间的字节大小
		结构体地址对齐
			struct simple_st
			{
				int i;
				float f;
				char ch;
				char ch1;
			};

		struct simple_st a;
		// sizeof(a) = 12

	addr%sizeof(int) 是否等于0 -- 是否可以存储
		
内存空间序列
						5%4 6%4 7%4 8%4=0
					
|	  i			|ch	|	空		|	f		|
0	1	2	3	4	5	6	7	8	9	10	11			

sizeof = 12

                    5%1=0
						6%4 7%4 8%4=0

|     i         |ch |ch1|	空	|   f   	|
0   1   2   3   4   5   6   7   8   9   10  11



		取消地址对齐
		struct simple_st
		{
			int i;
			float f;
			char ch;
			char ch1;
		}__attribute__((packed)); //宏

|     i         |ch |   f   		|
0   1   2   3   4   5   6   7   8   9   10  11

sizeof = 9


	6 函数传参
		值传递
			临时创建结构体，开销大
		指针传递

共用体 union
	1 产生与意义
		成员共用空间		
		在同一时间，只有一个成员生效
	2 类型描述
		union 共用体名
		{
			数据类型 成员1;
			数据类型 成员2;
			...
		};
	3 嵌套定义
		共用体和结构体可以互相嵌套

	4 定义变量（常规变量、数组、指针）、初始化及成员引用
		union 共用体名 变量名;

		成员引用：变量名.成员名
				  指针->成员名 
	5 结构体在内存中所占空间的字节大小
		取最大的数据类型变量所占空间，如int为最大，则size为4
	6 函数传参
        值传递
            临时创建结构体，开销大
        指针传递
	7 位域
		可以定义变量的位数占用(bits)

	
	8bits:	|7	|6	|5	|4	|3	|2	|1	|0	|
			
		参考bit_range_union.c

枚举
	enum 标识符	 
	{
		成员1;
		成员2;
		...
	};

	在enum中的成员是变量，默认从0开始

		
					九、动态内存管理

malloc ralloc realloc free

原则：谁申请谁释放

关键字typedef
	对已有的数据类型定义新的名字

typedef 已有的数据类型 新名字;

	基本类型和指针	

		#define INT int
		typedef int INT;

		INT i; --> int i;

		#define IP int *
		typedef int * IP;

		IP p, q; --> int * p, q; -- define 定义了一个指针和一个整型
		IP p, q; --> int *p, *q; -- typedef 定义了两个指针（目标结果）

	数组typedef

		typedef int ARR[6] --> int [6] ARR
		ARR a; --> int a[6];

	结构体typedef

		struct node_st
		{
			int i;
			float f;
		};

		typedef struct node_st NODE;
		NODE a; -> struct node_st a;
		NODE *p; -> struct node_st *p;

		typedef struct node_st *NODEP;
		NODEP p; -> struct node_st *p;

		typedef struct
		{
			int i;
			float f;
		} NODE, *NODEP;

	函数typedef

		typedef int FUNC(int); --> int(int) FUNC;
		FUNC f; --> int f(int);

		typedef int *FUNCP(int);
		FUNCP p; --> int *p(int);

		typedef int *(*FUNCP)(int);
		FUNCP p; --> int *(*p)(int);


				十、Makefile工程管理
样例工程
	proj
		feat 1:
			module 1:
				1.c
				2.c
				3.c
			module 2:
				2.c
				4.c
				5.c
			module 3:
				2.c
				3.c
				4.c
		feat 2:
		...
		feat 3:
		...
	
手动编译存在的问题
	如果3.c中出现错误，则需要重新编译调试其他所有包含3.c的模块和功能


makefile编写语法规则

	(target): (dependencies)
		(command)

	1. 可以通过定义变量简化makefile的编写
	2. $^ 替换上一句的依赖文件; $@替换上一句的目标文件
	3. 可以通过%通配符，替换所有的command


				十一、数据结构

线性
	线性表	linear list 增删改查
		顺序 sequential list
			数组
				结构：
					1. 数组
					2. 当前存放的最后一个元素的下标 - 初始化为-1
				参考实现的代码
					要点：
					1. 增删改查功能的实现
					2. 传递参数时的本质，地址还是值
				
		链式(*指针) linked list
			有头结点
		 		在第一个有效结点之前是头结点，保存起始位置
			无头结点
				第一个有效结点的起始位置就是所获得的地址
					不需要创建，初始状态就是一个结点（指针设为空）
					实现功能时要注意保存指向第一个结点的指针
			练习
				1. 多项式合并 polynomial
			单链表
				单向不循环
				单向循环
					无头单向环链例子展示，约瑟夫算法

			双链表
				双向不循环
				双向循环
					双向环链
						结点结构（参考lib1）
						{
							*data;
							*prev;
							*next;
						}
						或者(变长结构体，参考lib2)
						{
							*prev;
							*next;
							char data[0]; // 作为占位符，是入口地址
						}
						面向对象（参考lib3）
							封装函数到结构体中 -- 通过函数指针调用
						完整的隐藏和封装（参考lib4）
			内核中双向环链的实现
				

	栈
		顺序存储，使用数组实现
			head：第一个有效元素
			tail：最后一个有效元素
			空满条件：
				空：head和tail值相等（指向同一个位置）
				满：(qu->tail+1)%MAXSIZE_QUEUE == qu->head 循环队列，tail的下一个元素是head
			参考stack/arr
		链式存储，使用链表实现，二次封装双向环链
			参考stack/list
	栈例子：四则运算计算器

	队列
		顺序存储，使用数组实现
			参考squeue/arr
		链式存储，使用链表实现，二次封装双向环链
			参考squeue/list
	
	栈、队列例子：球钟算法

	静态库和动态库实现
		静态库
			libxx.a
			xx 指代库名

			生成静态库	
				ar -cr libxx.a yyy.o

			发布到
				/usr/local/include
				/usr/local/lib
			链接静态库
				gcc (-L/usr/local/lib) -o main main.o -lxx
				-l 链接 xx 指代库名
				参数必须在最后，有依赖关系

			特定项目所带的库
			占用编译时间
		动态库
			查看关联动态库
				Linux: ldd ./main (./main 可执行文件，以main为例)
				MacOS: otool -L ./main
			
			生成动态库
			Linux:
				libxx.so
				gcc -shared -fpic -o libxx.so yyy.c
			macOS:
				libxx.dylib
				gcc -dynamiclib -fpic -o libxx.dylib yyy.c
				
			经测试，当库的.c文件包含另一个或多个其他的.c文件时，在生成动态库需要加上所包含的文件，例：gcc -dynamiclib -fpic -o libstack.dylib stack.c dl_list.c
				stack.c 中包含dl_list.h， 实现在dl_list.c
			这样的好处是，因为已经将所有需要的.c文件都已经包含进去，生成的库直接使用，而不需要在链接时加上dl_list库；缺点是多个库文件占用磁盘空间

			发布到
				/usr/local/include
				/usr/local/lib
			
			Linux:
				在 /etc/ld.so.conf 中添加路径
				/sbin/ldconfig 重读 /etc/ld.so.conf
			本机（macOS）：
				没有配置路径
			
			链接动态库
				gcc (-I/usr/local/include) (-L/usr/local/lib) -o main main.c -lxx
					使用多个库需要把所有的库都加上，例：gcc -o main main.c -lstack -ldl_list
			共享库

		以栈、队列实现作为例子
			双向环链的二次封装（调用）
		
树
	深度（层数）height

	度 degree
	叶子 leaves
	孩子 children
	兄弟 siblings
	堂兄弟 cousins

	二叉树：
		满二叉树 full binary tree
			Definition:
				A binary tree is full if it is empty, or if the heights of its two subtrees are the same and all nodes are either a leaf or a node with two children.
			Fact: if height = k, then the number of nodes = 2^k-1
		
		完全二叉树
			Definition:
				A binary tree is complete if it is empty, or if if the heights of its two subtrees differ at most 1, and the nodes with only one child can only has a left child.
	存储：
		顺序存储
			只能存储满二叉树，能够明确每一个数组空间对应的树结点
		链式存储
			结点结构（左孩子指针，值空间，右孩子指针）

	遍历方式：
						A
				B				E
					C				F
				D				G				
							H		K								
		按行 // 本质是BFS 广度优先
			A BE CF DG HK
		先序（根，左，右）
			A BCD EFGHK
		中序（左，根，右）
			BDC A EHGKF
		后序（左，右，根）
			DCB HKGFE A

		平衡二叉树
			平衡条件：结点的左子树和右子树的结点数差值最多为1（每一个结点都需要满足平衡条件）
				不满足平衡条件，通过左旋右旋，重新选择根结点，直到满足平衡条件
				树的左边（右边）的结点更多，则右旋（左旋）
					左旋：选择当前根结点的右孩子为根结点，将原来的根结点及其子树作为右孩子的左子树。如果右孩子的左子树不为空，则将原来的根结点及其子树连接到左子树的最末端。

		广义表描述二叉树
			(A(B()(C(D)()))(E()(F(G(H)(K))())()))
			写入文件，macOS测试得通过相对路径不能新建文件夹
			参考save_load文件夹中，广义表读写二叉树
		
	搜索树 retrieval
		以空间换时间，O(1)时间复杂度

		例子：字典查找
	
图

小项目：俄罗斯方块

1 图形
	ANSI-VT 可搜索控制码 用\033调用
	framebuffer 暂时跳过
2 输入设备
	termios设置标准输入的属性
3 并发
	

				十二、项目：基于IPv4的流媒体广播

暂时跳过
121 - 123

项目开发模块解析

参考书目：《UNIX环境高级编程（第二版）》

接下来是通过该项目的内容，各个模块击破

I/O

文件系统

并发

IPC