c

first

基于”C Primer Plus 第6版 中文版”

chapter1

1. 了解标准,及各个编译器,以及搭建学习环境,使用gcc 10.2.1,使用clangd作为lsp.
2. 编译和链接.整个cc过程实际分为2部分,编译和链接.
   • 编译,将源码配合头文件编译成目标代码,也就是机器语言代码,但是这个目标代码并不可执行,缺少启动代码和相关库文件
   • 链接,将你的目标代码和库函数(只提取需要的函数),以及系统对应的启动代码链接成可执行文件,此时才能真正的执行.

chapter4

1. C语言没有专门的字符串类型，用char数组

2. 数组以\0结束(不是放在数组最后一个元素,哪里结束久放它后面),这是空字符(null character),这个字符ASCII码值为0,意味者数组只能存储length - 1个字符

3. 数组是一段连续的内存单元(这也是为什么数组是O(1)的效率,可以直接计算元素地址)

4. char ch,ch一个字节;char ch[4],长度为4个字节的数组

5. “x”表示字符串常量,占用2个字节,x和\0,‘x’表示字符常量,是char类型,占用一个字节

6. 预处理器#include可以引入头文件,预处理器#define可以用来定义常量,编译时会将常量的值在所有位置展开.

7. printf()转换说明:

   • %a: 浮点数,十六进制数和p计数法
   • %A: 同上
   • %c: 单个字符
   • %d: 有符号十进制整数
   • %f: 浮点数,十进制计数法
   • %e: 浮点数,e计数法
   • %E: 同上
   • %g: 根据值的不同自动选择%f或%e
   • %G: 同上
   • %i: 同%d
   • %o: 无符号8进制整数
   • %p: 指针
   • %s: 字符串
   • %u: 无符号十进制整数
   • %x: 无符号十六进制整数(0f)
   • %X: 同上
   • %%: 打印一个百分号

   

8. 转换修饰符

   200页

   

9. 转换本质上是翻译,二进制在视图层的表现

10. printf类型不匹配,无发强制转换的处理过程,见4.12_floatcnv.c文件,关于栈布局的解释.可以强制转换的都会正确转换,不能的采用栈布局模型处理.

11. 字符串""中不能使用Enter来换行,必须用\n

12. scanf读取键盘输入,注意输入的一定都是字符,scanf的一个重要作用就是类型转换

13. scanf从第一个非空字符开始读取,如果遇到和表达式类型不匹配的输入会放回输入中,如果一个有效字符都没有匹配,则不会赋值给指定标量

14. *可以表示一个表达式，在printf中*一般可以表示宽度和精度,在scanf中表示跳过该输出(不赋值给变量),即消耗掉这些输入

chapter5

1. C99规定整数取整时,使用趋零截断(就是往0靠拢),即-5/3得-1,而不是-2

2. C99规定求模时,第一个运算符是负数,模为负数,为正数,则模为正数

3. 每个表达式都有一个值,5 > 3表达式结果为1,flase则为0,1 + (c = 1 + 1)也是合法表达式,c = 1 + 1表达式的值就是c的值2.

4. side effect副作用,a = 3,算表达式的值为3,副作用是将变量a赋值为3(这不是主要作用吗),副作用的核心是change.

5. sequence points序列点,序列点保证了执行的顺序,在序列点所有的副作用都会完成,即可以保证change完成了.

6. 序列点的问题在自增,自减上表现的很明显,因为自增,自减不仅仅是获取还有赋值.

   // Unsequenced modification and access to 'num' clang (-Wunsequenced) [11, 37]
   int ans = num / 2 + 5 * (1 + num++);

   为什么出现这个警告? +左右2个子表达式执行的顺序不确定(和编译器有关),假设先执行了右边,num++返回了num,然后执行num = num + 1但是num++没有自己的序列点,无法保证change是否完成,前面的num / 2拿到的num就不确定了;如果是先从左边执行,那执行过程就没有冲突,num可以拿到确定的值,同时num的chang和ans的change都在;这里的序列点完成.

   int y = n++ + n++; // 这和上面的问题一样,n++没有序列点,造成另一个子表达式无法拿到确定的值,结果就是不确定的,同时2次n+1对n的赋值顺序不确定,结果进一步不确定

   以上都是undefined behavior. 那下面的为什么不是undefined behavior呢?

   int x = ++n + 1; // ++n返回n+1,并执行n = n + 1,同时+1赋值给x,在;序列点x和n的副作用都会完成,这时的副作用x和n的change互相没有影响
   int y = n++ + 1; // n++返回n,并执行n = n + 1,同时+1赋值给y,在;序列点y和n的副作用都会完成,这时的副作用y和n的change互相没有影响
   // 看个副作用有影响的
   int n = ++n + 1; // 编译器一般都会给出类似上面ans的警告.因为最后在序列点的2个副作用都是针对n的,且没有顺序,结果就是不确定的

   一个更有意思的例子:

   #include <stdio.h>
   int i = 0;
   void foo(int bar)
   {
       printf("i = %d\n", i);     // 1
       printf("bar = %d\n", bar); // 0
   }
   int main(void)
   {
       foo(i++); // i++返回0,所以传入的是0,在序列点;(此时函数还没有执行)i完成自增,所以执行函数时i就是1
       return 0;
   }

7. 涉及2种类型的计算,值会转换为参与计算的最高级别

8. 类型高到低的顺序: long double,double,float,unsigned long long,long long,unsigned long,long,unsigned int,int.当long和int大小相同时,unsigned int > long

9. 当作为函数参数传递时,char和short被转换为int,float转换为double.(注意,这种转换主要是使用函数声明,而不是函数原型时导致的,函数声明是ANSI C之前的用法)

10. 类型升级一般没有问题,毕竟可以覆盖,比如int ⇒ long,但是降级就可能有问题了,比如int ⇒ char,4 bytes塞入1 bytes可能塞不下

chapter8

1. printf默认输出到stdout stream,它是一个buffer,以下情况会输出到屏幕
   • buffer满了
   • 遇到\n
   • 需要输入时
   • 手动flush
2. 对于输入,也有输入缓冲区,输入的字符进入缓冲区,直到Enter才被送入程序使用(这针对行缓冲,也有完全缓冲,此时必须要缓冲区满了才发送给程序)

chapter10

1. 指针变量里存地址

2. &获取”内存区域”的地址,表达式只能用作右值

3. 普通变量代表”内存区域”,可以被&运算

4. *间址运算,针对指针变量(或者说针对地址),结果为”内存区域”,所以可以作为左值和右值(就像普通变量一样).*是针对地址,&针对”内存区域”.

   Note

   为左值时表示给间址到的内存位置赋值，不要和定义指针变量混肴。

5. 数组名可以表示数组首元素的地址,大多数情况下数组名可以当作指针变量: 比如: int arr[10],arr的类型实际可以看作 int * arr,所以arr[n] == *(arr + n) 从指针的角度看,数组很显然没有明确的物理界限,仅仅是首地址 + offset(index)去读取,所以实质上并没有物理”越界”,越界是逻辑上的概念

6. 但是数组又不是完全的指针,比如 在使用sizeof 和 &时,数组和指针不同:

   int a[10];
   int * b = a;
   sizeof(a) == 40;
   sizeof(b) == 8; // 仅针对当前系统
   &a == &a[0];  // &a理解为数组的首地址

   &b != &a[0],表示变量b代表的内存区域的地址

7. 在处理数组时,数组名可以转换为指针,指向数组首元素(个人理解,编译器将它解释为指针以方便获得对应元素的内存区域,方便操作),又可以是普通的变量,表示整个数组内存区域.就像数组有个隐含的指针一样.但是注意,这只是C语言利用了指针来操作数组,本质还是数组,不是指针,比如不能给数组名赋值其他地址(否则就指向其他地方了),但是正常的指针是可以的. 为什么要用指针来操作数组,因为数组是一段连续的内存,天然适合用首地址+偏移量的形式去操作. 有个疑问:

   int a[2];
   a == &a; // 这个结果是true,虽然中间涉及了一个类型转换

   分别是什么类型: a表示指向首元素的指针,类型是int *;(这里a是指针) &a表示指向数组的指针,类型是 int (*)[2]; (这里a是数组内存区域) 为什么是true: a的值是首元素的地址,即a[0]的第一个字节地址(假设机器编址单元是字节) &a表示数组的地址,实际也是数组第一个字节的地址,也就是a[0]第一个字节的地址 所以相等.

8. 数组,索引,偏移量,首地址+偏移量可以看作相对地址(当然运行时会自动转换为物理地址),引入单位长度(数据类型),计算元素物理地址.

9. const可用于形参数组,表示不能修改该数组,因为数组传参只能是指针来传,不是值传,可以会破坏原数组

10. const 修饰指针时

int a = 1;
int b = 2;
const int *p1 = &a; // 可以改变指针变量的值,但是不能改变指向的值.
*p1 = 3;  // 不行
p1 = &b; // 可以
int * const p2 = &a; // 此时p不能指向其他地方了
p2 = &b // 不行
*p2 = 3; // 可以
const int c = 10;
int * p3 = &c; // 编译器给出警告,如果通过p3修改c,这个行为是未定义的,结果未知

注意: 多级嵌套指针(间接指针)时的const问题. 11. 多重间址,即*p得到的还是指针,还需要**p继续,比如二维数组(参考7的说明去理解) 比如:

 int a[5][2];
 a == &a[0]; // a指向首元素
 a[0] == &a[0][0]; // a[0]也指向首元素
 *a == a[0]; // 间址a,得到a[0]这块内存区域
 **a == *a[0] == *&a[0][0] == a[0][0]; // 多重间址

1. int (*pz)[2],*pz是数组,pz就是指向数组的指针,pz又是一个间接指针,因为*pz作为数组名在需要的时候会被处理成指针;int * pz[2],这个是指pz里有2个int * ,即这是一个元素为指针的数组. []的优先级高于*,所以2者含义完全不同.

2. 指针的类型取决于所指向的值

3. 变长数组,比如二维: int arr[rows][cols],变长不是类似js中的不定长数组,而是可以通过变量指定数组大小,但是变量一但确定,创建了数组,这个数组长度依然不可变.相关函数原型必须是这样:

   int fn(int rows,int cols,int arr[rows][cols]);

   而且顺序不能变,因为rows,cols指定了第3个参数的维度. 当然,形参中的数组,依然不是真的创建了一个局部数组,和前面的内容一样,这里还是指针:

   int fn(int rows,int cols,int (*arr)[cols]);

   本质依然没有所谓的变长,“变长”体现在运行时上. 另外: 变长数组由于是运行时动态分配内存(大小运行时才确定),所以不能初始化,因为初始化是编译期完成的,此时必须要先知道数组大小,这和变长数组矛盾.虽然不能初始化,但是可以给对应位置赋值,编译不会给出警告. 15. 字面量数组.什么是字面量,比如10,'a',"hello",就是字面量int,char,string.数组也可以. (int[2]){1,2},字面量一维数组,匿名数组(既然代表数组,那根据7.中,它也表示首元素地址),对应 int *pt; (int[2][3]){{1,2,3},{4,5,6}},字面量二维数组,对应 int (*pt)[3];

chapter11

1. 字符串字面量在编译时后面会自动加上\0,所以字符串存储在char中时,要多留一个位置.所以如果char[]最后一个字符为\0,则认为这是一个字符串,否则就是一个普通字符数组.
2. 类似int[]在不完全初始化时,其他未明确的位置初始化为0,而char[]则初始化为\0.
3. 很多函数读取字符数组都是读到\0为止,比如puts,就算后面还有非\0字符也不会管.所以实际上并不是char[]最后一个字符是\0,而是只要有\0,就可以认为有字符串.
4. fgets函数读取stdin时,读取了最多n-1个字符(有可能包括\n) + \0(自行补充),把这些写入数组对应位置,数组没有写入的地方保持不变

chapter12

1. 合理管理内存是c语言的重要部分,也是无gc语言的要点

2. #include,预处理实际上是用包含的头文件内容替换#include指令,所以入口源文件和包含的头文件都被看作是一个文件,这个文件被称为翻译单元.有多个源代码文件,也就有多个翻译单元.

3. 文件作用域,也就是俗称的”全局作用域”,它的实际作用范围为整个翻译单元.

4. C的变量有3种链接属性:外部链接,内部链接,无链接 具有块作用域,函数作用域和函数原型作用域的变量都是无链接变量. 具有文件作用域的变量可以是外部链接或内部链接.内部链接变量只能在一个翻译单元中使用. static修饰的变量只能在当前翻译单元中使用,即内部链接.

5. 作用域和链接描述了标识符的可见性.

6. C对象有4种存储期: 静态存储期,线程存储期,自动存储期,动态分配存储期.

   • 静态存储期在程序执行期间一直存在,文件作用域变量具有静态存储期.
   • 线程存储期,从被声明到线程结束一直存在.以关键字_Thread_local修饰的变量,每个线程都获得它的私有备份.
   • 块作用域的变量通常都有自动存储期,进入快时分配,退出块时释放,除了变长数组,它是从声明开始到块末尾结束.(一般使用的局部变量都是自动类别)
   • 块作用域也是可以具有静态存储期的,很简单,虽然在块内,但是我可以把地址暴露出去.

7. 自动变量不会初始化,比如int x;不要指望x是0(有也是碰巧这个内存区域没有使用过),x会是分配的内存块当前的值,这个值是什么都有可能

8. 寄存器变量,使用register关键字声明的变量,实际上是请求编译器将它存储在cpu寄存器中,但是并不一定会实现,没有的话就是普通的自动变量.寄存器变量,无法使用&操作,且类型有限制,毕竟寄存器支持的bits有限.

9. 有静态存储期的变量,是指该变量对应的内存区域不变,但是里面的值是可以变的.

10. 静态存储期的变量在编译时初始化一次(很好理解,因为不能改变地址),没有显示初始化会初始化为0(根据类型).

11. 块中可以使用static表示一个静态存储器的自动变量(形参中不能使用static,形参没有默认值).但是本质上它并不属于这个块,因为运行时并没有执行(静态数据编译时确定,载入程序时,分配内存),放在块内仅仅表示作用域范围.

12. 外部变量,声明在所有函数外的变量的,具有外部链接,静态存储期和文件作用域.在函数中可以使用extern修饰变量表示要引用这个外部变量(当然前提是外部有),虽然这看起来完全多余,如果不使用extern则表示声明了一个自动变量.

int Hocus; // 定义式声明外部变量,外部链接
int magic();
int main(void){
    int Hocus; // 自动变量,且隐藏了外部变量Hocus
    ...
}
int Pocus; // 又声明了一个外部变量,但是在main之后声明,所以main不可见,magic可见
int magic(){
    auto int Hocus; // 使用auto显示声明了一个自动变量,且隐藏了外部变量Hocus
}

Warning

由于外部变量是静态存储期,所以有默认值.并且只能用常量表达式初始化(表达式不能有变量).

1. 具有内部链接的外部变量,用static修饰的外部变量

   static int svil = 1; // 静态存储期,文件作用域,内部链接(当前翻译单元使用)
   int main(void) {
       extern int svil; // 引用式声明,并不会改变链接属性
       ...
   }

2. 多文件中共享外部变量同样遵循上面的原则,即一个位置进行定义,其他位置使用extern引用.

   Warning

   如果extern修饰的变量具有文件作用域,则引用的变量必须是外部链接的.

3. 函数也可以有内部链接外部链接的定义区别.

   double gamma(double); // 可以当作外部链接的函数
   static double beta(int, int); // 可以当作内部链接的函数
   extern double delta(double, int); // 引用式声明,表明定义在其他文件中,默认值

4. malloc()分配一块内存,并返回内存块首字节的地址,即一个指针,此时需要明确这个指针指向的是什么类型,使用强制类型转换即可.malloc的返回值是void *类型(可以理解为通用类型),可以转换为任何类型.

   // 原型
   void *malloc(unsigned long);

   int * pt;
   pt = (int *)malloc(30 * sizeof(int)); // sizeof而不是4,可以适应不同的系统,提高可移植性

   此时指针指向某个元素了.根据数组的用法,可知,指向某个元素后就可以操作这一系列元素,即数组操作.

5. 通过malloc()分配的内存块,只能通过free()释放(不释放容易造成内存泄露),free()是知道malloc()返回的指针对应了多大的一块内存的,有其他额外的信息被存储了,但是这些信息无法通过编程手段获得.另外,free()不能释放其他方式分配的内存,比如声明一个数组.

   // 原型
   void free(void *)

   free()只是根据传入的地址,释放这个地址对应的内存块,它并不能改变传值给它的变量,最简单的原因这是值复制传递过来的,free根本不知道原始的变量是谁,更不可能把它赋值为NULL.

6. malloc()如果无法分配,则返回一个空指针,即NULL. NULL是一个macro,它的值是常量(void *) 0,空指针表示不指向任何有效位置.

   // 空指针判断
   if (pt == NULL){...}
   if (pt == 0){...}
   if (!pt){...}

   空指针并不一定是0x0,它有可能是别的值,比如0xDEADBEEF,但是这并不影响它的值就是常量(void *) 0 ,编译器会正确的处理

7. calloc()函数也可以分配类型,和malloc()不同的是,它会把申请的内存块所有bit设置为0.同样使用free()释放.

   // 原型
   void *calloc(unsigned long, unsigned long)

8. 变长数组和动态内存分配,在二维数组上的表现.

   // 变长二维
   int ar[n][m];
   // 使用malloc模拟
   int (*p2)[6]; // p2指向int[6],p2可以表示n * int[6]二维数组
   p2 = (int(*)[6])malloc(n * 6 * sizeof(int)); // 转换为int(*)[6]指针类型,即指向int[6]一维数组
   // 扩展到变长二维
   int (*p3)[m];
   p3 = (int(*)[m])malloc(n * m * sizeof(int));

   二维数组还是用变长数组的表示方法更简洁一些,且是自动存储类型,不用free.

9. 静态存储类型,自动存储类型,动态分配内存,这3种分别会使用不同的内存区域,从12.15_where.c代码中很明确的能看到地址区别.

   // 地址非固定,仅供参考
   // 静态存储类型,地址0x5627ea37开头
   int static_store = 30;
   const char *pcg = "String Literal";
   // "Quoted String" 字符串字面量也是静态的
    
   // 自动类型的,地址0x7ffd3269开头
   int auto_store = 40;
   char auto_string[] = "Auto char Array";
    
   // 手动分配的,地址0x5627eb28开头
   pi = (int *)malloc(sizeof(int));
   pcl = (char *)malloc(strlen("Dynamic String") + 1);

10. 限定符

• const,限定不能修改

  const int *pt1; // pt1指向的位置是只读的,但是pt1可以指向其他位置
  int * const pt2; // pt2不能指向其他位置,但是它指向的位置里的值可以改
  const int * const pt3; // 既不能改变指向,也不能改变指向的值
  int const *pt4; // 同pt1,核心是在*左边还是右边,左边限定指向的值,右边限定指向

  // 最常见的做法,限定作为形参的指针,确保不会修改原始数据
  void fn(const int *arr,int limit);

  对于全局变量,如果要在多个文件中#include,必须用static修饰为内部链接,否则多个文件都有相同的定义式声明,因为外部链接可以跨翻译单元,这样就造成了整个作用域有多个相同的定义式声明,这是不被允许的. 这种模式实际上是给每个翻译单元创建了单独的副本,如果是const,那共享数据的目的也达到了,但是这种模式由于保留多个副本,如果数据占用较大就会造成内存的浪费.

• volatile,将一个变量修饰为易变的,告诉编译器代理(其他进程)可能改变它的值. 这有什么意义? 这主要涉及到编译器的优化问题,在没有volatile前,编译器无法知道这个值会不会被其他程序改变,如果不改变则可以把值临时存储在寄存器中,以达到快速读取的目的,如果会改变则不进行优化. 所以ANSI加入了volatile,用来进行标识,以供编译器尝试优化.

  Warning

  注意,volatile不是用来限定本程序的,是对代理程序的说明,所以在本程序中依然可以同时使用const,表示”我”不会改变它,但是其他程序可能改变它.

  // 同时使用,是常见做法
  volatile const int n;
  const volatile int * pt; // 顺序不重要

• restrict,修饰指针,表示这个指针是访问内存块,唯一且初始的方式.同样是用作编译器优化.

  int * restrict pt = (int *)malloc(10 * sizeof(int)); // ar是唯一且初始的方式
  int ar[10];
  int *pt = ar; // pt不能设置为restrict,因为不是唯一且初始的方式

  编译器是怎么优化的?

  int * restrict pt = (int *)malloc(10 * sizeof(int));
  pt[n] += 3;
  ...
  pt[n] += 5;
  // 由于pt是唯一且初始的方式,所以编译器进行了合并优化
  pt[n] += 8;

  如果不是唯一且初始的访问方式,则合并就可能出现问题,因为中间可能被其他指针修改了数据. restrict可以用于修饰形参,表示这个函数体内其他指针不会修改这个数据.

  Warning

  注意,restrict并不是类似const的强制,它仅仅是一个约定,你要确保你修饰的变量满足唯一且初始,编译器只是根据限定符来优化,它并不检查是不是真的唯一且初始,所以要严格遵守约定,否则可能产生不可预料的后果.

• _Atomic,原子化操作,用于线程安全,依赖编译器的实现.

  #include <stdatomic.h>
  #include <threads.h>
  _Atomic int hogs; // 声明原子类型的变量
  atomic_store(&hogs,12); // 原子化操作,类似上锁

1. 旧关键字的新位置,C99允许把类型限定符和存储类别说明符static放在函数原型和函数头的形式参数的初始方括号中.

   • 限定符的新用法

     // 旧写法
     void ofmouth(int * const a1, int * restrict a2, int n);
     // 新写法(增加心智负担,吃饱了撑的)
     void ofmouth(int a1[const],int a2[restrict],int n); // 注意是要修饰参数,所以 const int *a1不能改成这种写法

   • static的新用法,完全和原来的static无关

     double stick(double ar[static 20]); // 表示这个数组至少有20个元素

chapter13

1. C中使用文本模式或二进制模式来访问文件.

   • 二进制模式下,程序可以访问文本的每个字节(原封不动的)
   • 文本模式下,程序会做额外的处理,比如屏蔽换行符和文件结尾的差异

2. 可以使用操作系统提供的I/O,也可以使用C提供的标准I/O.底层I/O根据操作系统的不同而不同,可能造成代码无法移植,建议使用标准I/O库.

3. fopen()函数的使用:

   extern FILE *fopen(const char *restrict __filename, const char *restrict __modes);

   _modes由很多选项:

   模式字符串	含义
   "r"	以读模式打开
   "w"	以写模式打开,把现有文件的长度截为0(清空),如果文件不存在,则创建一个新文件
   "a"	以写模式打开,在文件末尾添加,文件不存在则创建一个新文件
   "r+"	以更新模式打开(可读写),从指针位置开始覆盖
   "w+"	以更新模式打开(可读写),类似w,这里的读是读取写入后的内容
   "a+"	和w+的区别是,在文件末尾添加内容
   "[rwa]\+?b\+?"	和上面对应的相同,但是是以二进制模式,而不是文本模式打开文件
   "w[b\+]?[\+b]?x"	类似非x模式,但是如果文件已存在,则打开失败

   

   函数返回文件指针FILE *,通过该指针来操作文件.FILE是派生类型,包含文件信息(不是文件本身),比如缓冲区信息等.这个FILE是用来操作文件的窗口!

4. getc()和putc()

   extern int getc(FILE *__stream);
   extern int putc(int __c, FILE *__stream);

   很明显的用法,从文件中读取,写入文件中. 和getchar(),putchar()非常类似,实际上putc(ch, stdout)和putchar(ch)效果相同,stdout本身就被操作系统抽象为文件描述符,在C中它的类型就是FILE *. 同理getchar()和getc(stdin)也是一样的.

   OS会抽象3个文件描述符,stdin,stdout,stderr,对应的值为0,1,2,一般关联为键盘和显示器,可以通过重定向改变关联,比如重定向到文件.

5. fclose(),关闭文件,必要时刷新缓冲区,正确关闭返回0,否则EOF.

   if(fclose(fp) != 0)
       printf("Error in closing file %s!\n",argv[1]);

6. fprintf()和fscanf()用法

   extern int fprintf(FILE *restrict __stream, const char *restrict __format, ...);
   extern int fscanf(FILE *restrict __stream, const char *restrict __format, ...);

   类似printf和scanf,只是第一个参数都是FILE *,__format和printf,scanf的格式相同.

7. fgets()和fputs()用法.

   fgets(char *__restrict s, int n, FILE *__restrict stream);
   fputs(const char *__restrict s, FILE *__restrict stream);

   fgets在遇到\n,文件结尾,到达LEN-1时停止读取,并自动添加\0.注意,\n也会添加进char *中去,前提是没有读取到字符上限. fputs为配合fgets并不会在末尾添加换行符.

8. fseek()和ftell()的使用

   extern int fseek(FILE *__stream, long __off, int __whence);
   extern long ftell(FILE *__stream);

   fseek的作用是,文件好像数组一样,可以跳转到任意位置.标准提供了几个默认的绝对位置whence(第二个参数就是相对这些位置的offset):

   • SEEK_SET,文件开始

   • SEEK_CUR,当前位置

   • SEEK_END,文件末尾.这里有个注意点,对SEEK_END,且偏移量为0时,定位在”结尾符”上,并不是最后一个内容字节,但是此时ftell返回的又是最后一个内容字节的位置,这种情况不确定是否在不同文本格式下都存在,所以慎用SEEK_END的offset.

     fseek(fp, 0L, SEEK_END);
     // ftell(SEEK_END,offset 为0) == ftell(SEEK_END,offset 为-1)

     ftell返回的是字节位置,有些编译器可能返回的是相对第一个字节的offset.

   DOS下的换行符\r\n,在文本下统一处理为\n,但是二进制下却是2个字符,又比如CTRL^Z表示结尾符的时候,文本模式可以正常识别,但是二进制模式时却把它当作正常的字符了,这就导致各种不统一的行为.

   二进制模式和文本模式的影响,不同的文本格式下二者是有区别的,比如

   为保证可移植性,建议使用下面的模式:

   函数调用	效果
   fseek(file, 0L, SEEK_SET)	定位至文件开始处
   fseek(file, 0L, SEEK_CUR)	保持当前位置不变
   fseek(file ,0L, SEEK_END)	定位至文件结尾
   fseek(file, ftell-pos,SEEK_SET)	定位至文件开始处ftell-pos位置

   具体怎么用还是应优先使用环境.

9. fseek和ftell限制在long类型,对于大文件来说,肯定是不够的,此时需要使用fgetpos和fsetpos.

   int fgetpos(FILE *restrict stream, fpos_t *restrict pos); // 获得文件中的位置,用fpos_t描述
   int fsetpos(FILE *stream, const fpos_t *pos); // 将fpos_t的值,设置进文件中fpost_t所示的位置

   fpost_t不是基本类型,表示文件定位类型,一般实现为结构.

10. 标准I/O的机制

11. 使用fopen打开一个文件,本质上是打开了一个stream,根据模式不同,分为文本流和二进制流.fopen在逻辑上会创建一个(读写模式下会创建两个)缓冲区,和一个数据结构FILE(包含文件和缓冲区信息). 结构一般包括:

    • 文件位置指示器,指明流中的当前位置
    • 错误指示器
    • 文件结尾指示器
    • 指向缓冲区的指针
    • 文件标识符
    • 计数器(统计拷贝进缓冲区的字节数)

12. 调用输入函数,比如fscanf,getc,fgets等.此时开始将数据块拷贝进缓冲区(大小为512的倍数),同时初始化FILE数据,比如流中的当前位置,一般为文件开头.

13. 初始化后,开始从缓冲区读取数据,并同步更新FILE,比如文件位置指示器会逐渐后移.直到缓冲区读取完成,会请求把下一个缓冲大小的数据块继续从文件拷贝进缓冲区.

    只要使用相同的FILE,就会沿用已有的值,即状态是连续的.

14. 直到全部读完,此时会将文件结尾指示器设置为真,于是下次的调用就返回了EOF.

输出同理.

1. 其他标准I/O函数

   • int ungetc(int c, FILE *stream),放回输入流,也就是反操作

   • int fflush(FILE *stream),刷新输出缓冲区,写入文件,如果stream为NULL将刷新所有输出缓冲区,对于输入缓冲区效果是未定义的(危险).

   • int setvbuf(FILE *stream, char *buf, int mode, size_t size),主要作用是自定义缓冲区,比如指定一个数组作为缓冲区,size为数组大小.如果buf为空指针,则会自行分配缓冲区. 返回非0则表示创建缓冲区失败. mode:

     • _IOFBF,完全缓冲,即满了再刷新.
     • _IOLBF,行缓冲,遇到换行符或满了就刷新
     • _IONBF,无缓冲,也就是立即刷新

     Warning

     必须是打开流但是没有做其他操作时才能调用.

   • fread和fwrite 首先要明白文本(字符)和二进制数据的区别,比如字符123和int 123,存储在文件中,前者存储了3个字符,1,2,3的ASCII的二进制表示;后者存储了123这个整数的int二进制表示0000 0000 ... 0111 1011,即所谓的二进制数据,这种数据都需要反序列化,因为和环境强相关. 用二进制表示的好处是数据是原封不动的,没有信息丢失.转换为字符(字符串,文本)可能丢失信息,比如小数,可能丢失精度.

     // __size表示单位长度(一般为sizeof(类型)),__n表示写入或读取的单位数量,返回的是成功写入或读取的数量,一般<=__n.
     extern unsigned long fwrite(const void *restrict __ptr, size_t __size, size_t __n, FILE *restrict __s);
     extern unsigned long fread(void *restrict __ptr, size_t __size, size_t __n, FILE *restrict __stream);

     由于本质上都是存储二进制数据(0 1),所以对于一个文件,不管是文本还是二进制类型,都可以用相同的逻辑去处理,当然有些可能毫无意义,比如getc读取二进制文件,读出来的压根无法解析为某个字符.所以建议用二进制模式处理二进制文件,文本模式处理文本文件.

     文字处理工具生成的文件一般都是二进制的,因为包含了大量非文本信息,如格式,字体.就像word文本,用文本编辑器打开,看到的都是乱码,因为没有对应的字符.

   • feof和ferror

     int feof(FILE *stream); // 对于输入流,如果到达文件尾,该函数返回非0,否则返回0
     int ferror(FILE *stream); // 对于输入,输出流,如果出现错误返回非0,否则返回0

     这样就可以检测一个输入流返回EOF时,是到达文件尾了还是出现错误了.

     考虑这种中间检测在多线程中的问题.

chapter14

1. 定义结构struct,即定义一个类型,定义只是告诉编译器如何表示数据,此时没有分配空间,只有声明变量时才会分配空间.此时会分配整个结构所需要的内存空间.

   struct book {
       char title[50];
       char author[50];
       double value;
   };
   // 结构名非必须,可以匿名
   struct {...} var;

2. struct的普通初始化

    // 初始化,赋值
   struct book library = {
       "title",
       "author",
       9.9
   } // 像数组

   和指定初始化,可以按照任意顺序

   // 还是类似数组,指定初始化器后面的普通初始化,为指定成员后面的成员提供初始值,并且后面的会覆盖前面的
   struct book library = {
       .value = 10.0,
       .author="author",
       9.9 // 根据顺序,是给value赋值,会覆盖前面的指定初始化器
   };

   实际上struct和数组在很多地方都非常类似,只是数组的索引是offset,struct的索引是key.

   内存分配上,数组是连续的,struct也是相对连续的(涉及内存对齐(边界对齐),导致总大小大于成员大小和,中间会出现空隙,但是逻辑上可以这么理解),只是每个子元素所占大小可能不同,但是逻辑上和数组没什么不同.

3. 嵌套结构

   struct guy
   {
       // 嵌套结构
       struct name handle;
       char favfood[LEN];
       char job[LEN];
       float income;
   }

4. 使用.运算符访问.

   struct guy fellow = {...};
   printf("%s\n",fellow.hanlde.first);

   大部分语言都是这么访问这种复合数据结构.

5. 类似数组本身操控起来较麻烦,但是引入指针就非常方便且容易了(可以说是契合),struct用指针操控也非常方便.

   struct guy *him; // 声明一个指向结构体的指针
   him = &fellow; // 获取某个结构体的地址,赋值给指针.

   和数组不同的是,结构名不会被处理成指向第一个子元素的指针,所以需要用到&运算.

   指针怎么操作成员?

   him = &fellow;
   fellow.job;
   (*him).job; // 效果同上,.优先级高于*,必须用()
   him -> job; // 同上,最常用法,表示获取指针指向结构的job成员
   // 上面3种方法效果完全一样

6. 不同于数组,struct是可以类似基本变量,比如int直接赋值给相同类型的.

   struct guy someone = fellow; // 相当于将fellow复制给someone了,也就是值复制.

   所以在函数参数传递时,可以直接传递结构值(需要编译器允许,一般都支持了). 所以现在有2种方式操作struct了:

   • 值,保护原始数据,代码风格更自然,但是浪费空间,执行效率更低.通常只用在处理小型结构上.
   • 指针,除了代码更难懂,其他都是优点,且有const来避免意外的修改.

7. 字符数组在struct中的使用问题.

   struct person {
       char name[LEN];
   };
   struct pperson {
       char *name;
   };
   struct person p1;
   struct pperson p2;
   p1.name = "foo";
   p2.name = "bar";

   p1,p2都未初始化,p1中的name就在结构中,赋值后改变结构中的内容;p2没有初始化导致name可能指向任何地方,赋值会进行意外的改变,造成不可预知的危险! 所以慎用未初始化的指针,不仅仅是struct中. 更安全的做法是提前用malloc进行分配(不要忘记free).

   p2.name = (char*)malloc(strlen(need)+1);

8. 字面量结构,类似字面量数组.用作临时使用,特别是实参传递.

   (struct book){"name","author",18.99} // struct
    (int[]){1,2} // 数组

   复合字面量(结构和数组)在所有函数外部,具有静态存储期;在块中,则具有自动存储期.

   字面量可以只作用于编译期间,编译时拷贝给变量,运行时就只存在于变量了(可能是临时变量,即匿名).(字符串字面量特殊一点,会存在于静态区,方便复用).

9. 伸缩型数组成员,struct中的最后一个成员是数组,且不指明长度.也就是它的长度可以是动态的.(C99新增)

   struct flex {
       int count;
       double average;
       double scores[];
   };
   struct flex foo; // foo不能使用scores,因为压根没有分配空间

   所以实际上伸缩数组并不是这么用的,而是使用指针,然后分配对应的固定 + 弹性空间

   struct flex *pf1,*pf2;
   pf1 = (struct flex *)malloc(sizeof(struct flex) + n * sizeof(scores)); // 前面为常规内容所需空间,后面为伸缩数组的弹性空间
   pf2 = (struct flex *)malloc(sizeof(struct flex) + m * sizeof(scores));

   注意sizeof(struct xxx)一般都大于成员大小之和,这主要是内存对齐的原因.

   伸缩数组好处很明显,但是也有限制,比如不要进行结构间的赋值和拷贝(即值传递),像*pf1 = *pf2,这样做只能拷贝除伸缩数组外的成员,确实需要拷贝应该使用memcpy()函数. 另外带伸缩数组的struct不能作为数组成员和其他struct的成员.

10. 匿名struct,主要就是作为内部结构使用

struct person {
    int id;
    struct {first char[10];char last[10];};
};
// first,last可以当作person的成员使用
printf("%s %s\n",person.first,person.last);

1. struct存储到文件

   • 文本流,反序列化是个大问题,因为开始和结束的位置不好确定,且效率过低;
   • 字节流,符合直觉,效率高.但是移植是个大问题,比如最简单的大端小端问题,更别说系统间二进制表示不同的问题,甚至不同的编译器都能导致字节布局不同.

2. 在数组和struct的基础上,就可以引申出其他丰富的结构,比如队列,二叉树,堆,哈希表,图表等,很多数据结构都涉及到链式结构,即对象之间是有关联的,他们有链路存在.

   参考相关数据结构书籍.

3. union联合数据类型.类似struct,但是struct是同时存储子成员,而union同时只存储其中一个,声明该类型的变量,编译器会分配占用最大空间的子成员所需的空间.

   union hold {
      int digit;
      double bigfl;
      char letter;
   };
   union hold valA;
   valA.letter = 'R';
   valA = valB; // 用另一个同类型的变量初始化
   valA = {88}; // 初始化第一个成员
   valA = {.bigfl=9.9}; // 使用指定初始化器

   union的使用:

   union hold fit;
   fit.digit = 23; // 存储23,占用4个byte
   fit.bigfl = 2.0; // 清除digit,存储2.0,占用8个byte
   fit.letter = 'h'; // 清除bigfl,存储h,占用1个byte

   使用指针,和struct相同:

   pu = &fit;
   char c = pu -> letter;

   union本质是同一个内存块的不同解释.

   完全可以把union当作有限的动态类型来看待,比如可以把union和它当前的类型标记放在一个struct中.

4. 匿名union.参考匿名struct,操作完全一致.

5. 枚举类型.枚举类型中的常量都是int类型.

   // 声明一个枚举类型,以及他可能的常量值,本质都是int
   enum spectrum {red, orange, yellow, green, blue, violet};
   // 声明一个该类型的变量,他可以取上面的常量值
   enum spectrum color;
   // 赋值
   color = red;

   由于本质上enum值都是int(在C中,使用起来也和int没有差别),所以可以赋值给任意整数类型,当然前提是该整数类型能存储枚举常量.比如上面的例子中,color其实完全可以声明为unsigned char,因为只有6个值,0 ~ 5.

   任何使用enum的地方都可以直接用对应的整数替代,对程序没有任何影响,enum仅仅是为了提高程序可读性和可维护性.

6. 枚举常量的值.默认都是从0开始,自动递增.也可以直接指定.

   enum spectrum {red, orange, yellow, green, blue, violet}; // red = 0, orange = 1, yellow = 2, ...
   enum levels {low = 100, medium = 200, high = 500}; // 直接指定
   // 如果只进行部分指定,那后面的也会自动递增
   enum feline {cat, lynx = 10, puma, tiger}; // cat = 0, puma = 11, tiger = 12

7. namespace名称空间.struct,union,enum共享一个名称空间,且和普通变量的名称空间不同,所以在一个作用域中(作用域也是namespace概念的一部分)允许普通变量名和struct|union|enum标记名相同(有点类似Typescript中的类型和变量,分属不同的命名空间),但是不建议这么做.当然同一个作用域中不允许同名标记或同名变量名.

   struct person {char name[20]; float age;};
   char person[]; // 并不冲突,但是不建议

8. typedef给类型取别名.别名通常用大写. 主要作用:

   • 取一个更具有识别性的名称

   typedef char * STRING; // 用STRING代替char *
   STRING name,sign; // 等同char *name,*sign

   • 方便移植

   // 对于某些值,C标准委员会认为不同的平台有不同的具体类型
   // 但是为了规范统一,就设置了一个新的类型,让具体的实现通过typedef来定义具体的类型
   // size_t,time_t都是这种情况,比如本机time_t是long,有些机器可能是unsigned long
   time_t time(time_t *);

   • 给复杂类型取别名

   typedef char (* FRPTC())[5]; // FRPTC是一个函数类型,该函数返回一个指向包含5个char元素的数组的指针

9. typedef和struct

   typedef struct complex {
       float real;
       float imag;
   } COMPLEX;

   可以省略结构标签,但是和不省略标签的情形在语义上有一点不同.

   typedef struct {double x; double y;} rect;
   rect r1 = {3.0, 4.0};
   rect r2;
   r2 = r1;
   // 上面看不出什么问题,类型还原后再看
   struct {double x; double y;} r1 = {3.0, 4.0};
   struct {double x; double y;} r2;
   // 关键在这个拷贝的过程,正常只有同类型才能拷贝,但是r1,r2实际上都是匿名结构,匿名结构之间怎么判定是同类型?
   r2 = r1;

   r2 = r1会正确的拷贝,虽然他们都没有明确的类型,但是他们的结构成员完全一样,C就认为他们结构相同,可以赋值.

   这里涉及到”结构化类型系统”的概念,Typescript就是,特征是如果子成员是兼容的那他们就可以看作一个类型.

10. typedef和#define.在处理类型上它们之间有共同点,但是也有不同. 比如:

typedef unsigned char BYTE;
BYTE b; // 等于unsigned char b;
#define BYTE unsigned char;
BYTE b; // 等于unsigned char b;

但是:

typedef char * STRING;
STRING name, sign; // 等于 char *name, *sign; name,sign都是指针,符合要求
#define STRING char *;
STRING name, sign; // 等于 char *name, sign; name是指针,sign是char类型,不符合要求

1. 复杂类型 声明复杂类型时,可以用到的符号:

   符号	含义
   *	表示一个指针
   ()	表示一个函数
   []	表示一个数组

   数组相关例子:

   • int board[m][n]; ,二维数组,和int (*board)[n];相同 注意: []是从左到右结合的,所以是m个子数组,每个子数组n个int元素
   • int **ptr; ,ptr指向一个指针,该指针指向int类型
   • int * risks[n]; ,risks是一个有n个元素的数组,元素类型为指向int的指针
   • int (* risks)[n]; ,risks是一个指向int[n]数组的指针
   • int * off[m][n]; ,m*n二维数组,数组元素都是指向int的指针
   • int (* uuf)[m][n]; ,uuf是一个指向m*n二维数组的指针,数组元素都是int类型
   • int (* uof[m])[n]; ,uof是一个包含m个指针的数组,每个指针都指向int[n] 可以这么理解: 先看()外面,表示指向int[n]的指针,再看()里面,指针放在uof[m]中,有m个

   函数相关例子:

   • char * fump(int);, 函数,返回指向char的指针,接收int参数
   • char (* frump)(int);, 指针,指向一个返回char,接收int的函数
   • char (* flump[m])(int);, 内含m个指针的数组,每个指针都指向一个返回char,接收int的函数

   [](数组)和()(函数)有相同的优先级,且都比*高

   上面的类型声明都足够复杂,如果要多次使用,更是眼花缭乱,更别说更复杂的类型结合了,此时typedef就非常有用了:

   typedef int arr5[5]; // arr5表示int[5[]
   typedef arr5 * p_arr5; // p_arr5表示指向arr5的指针
   typedef p_arr5 arrp10[10]; // arrp10表示一个10个元素,每个元素都是p_arr5的数组
   arrp10 ap; // ap是一个10个元素的数组,每个元素都是指向arr5的指针,即都是指向int[5]的指针

2. 函数和指针 指针持有一个内存块的地址(起始地址),指向那个内存块,并且明确内存块中数据的类型. 函数本质上是一段机器指令,也会被加载到内存中,存储到某个内存块中,所以也可以被指向,只是需要明确函数的类型. 函数的类型,本质上是函数的签名:

   // 签名就是类型,即返回值和参数的限定
   void fn(char *);

   现在可以申明一个指针,它指向的数据是这个类型:

   // pf是一个指向返回值是void,参数是char *的函数的指针
   void (* pf)(char *); // 注意 * pf的括号不能省略,因为()的优先级大于*

   有了指针,可以给指针赋值,即相同类型的函数的地址可以赋给pf,在这种上下文中函数名可以表示函数的地址

   void ToUpper(char *);
   pf = ToUpper; // pf指向ToUpper函数

   指针函数的调用:

   // 最直观的,就是解引用,然后调用
   (*pf)("string");
   // 但是上面的赋值,也能看出函数名被当作指针了,那指针也可以是函数名,所以
   pf("string");

   上面2种形式都可以,但是建议用第一种,更符合直觉.

   指针函数最重要和最常见的用法就是函数参数:

   void show(void (* fp)(char *),char * st) { (*fp)(st); }

   结合typedef可以进行更好的可读性改写:

   typedef void (* V_FP_CHARP)(char *);
   void show(V_FP_CHARP fp,char * st) { (*fp)(st); }

   ()调用外,其他都一样.

   核心就一个,把函数当作普通的数据来处理,除了可以

chapter15

1. 关于原码,补码等二进制相关内容参考计算机组成原理 这里简要说明为什么一个字节(假设为8位)的大小表示范围为-128 - 127. 负数的补码计算公式: $x_{补}=x+2^{n+1}$,x为真值,进行计算,得到的无符号二进制表示就是补码,现在要得到最小的$x$,即$x_{补}$的无符号表示要最小,也就是1000 0000(负数的补码表示一定是1开头的),结果为$2^n-2^{n+1}$,即$-2^n$,为-128.

   负数的原码计算公式: $x_{原}=-x+2^n$ 注意,这里所说的都是指定点整数.

2. 关于浮点数 浮点数,一般由2部分组成,定点小数和指数.就像有些分数比如1/3无法用十进制准确的表示一样,有些分数也无法用二进制准确的表示,二进制本质只能表示$2^{-1}+2^{-2}+...+2^{-n}$,所以类似1/3,3/5,2/7之类的无法被二进制精确表示. 浮点数一般都是$定点小数\ast 2^{指数}$,表现出来就是定点小数左右移动多少位.

   定点小数就是定点整数的基础上,在符号位后面加了一个.,比如0.1101000,当然是逻辑上的加.

3. 其他进制 使用最多的就是8进制和16进制,因为它们都是2的幂,方便对应.

   • 8进制 每3位对应一个8进制位.假设有6位,低到高,为a,b,c,d,e,f. $a\ast 2^0+b\ast 2^1+c\ast 2^2+d\ast 2^3+e\ast 2^4+f\ast 2^5$,进行转换 $(a\ast 2^0+b\ast 2^1+c\ast 2^2)\ast (2^3{)}^0+(d\ast 2^0+e\ast 2^1+f\ast 2^2)\ast (2^3{)}^1$ 每3位都是0 - 7表示,所以8进制和2进制之间的转换非常方便,1对3,3对1即可. 8进制可以用0开头表示.
   • 16进制 原理同上,只是和二进制变成了4对1.使用0 ~ 9,A ~ F表示0 ~ 15. 一般描述地址时偏向用16进制,比如0x17ff.

4. 位运算符 位运算只能操作整型.

   • 按位取反~,就是简单的0 -> 1,1 -> 0

   char c = 0b00010001;
   int d = ~c;

   • 按位与&,对应位都是1则为1,否则0

   int d = (0b000010001) & (0b00001111);

   掩码的作用,进行&运算时,被操作数隐藏了掩码0位对应的位,真实展示掩码1位对应的位,因为0求与得0,1求与取决于对方的值. 比如ch &= 0xff;,相当于保留了ch后8位,前面的全部隐藏(置0)了.总的来说&的作用是突出某些位,这可以用于检查某些位是否为1. 应用: 关闭某个位,只需要在该位赋0,其他位赋1然后求&即可.

   • 按位或|,对应位有1个1则为1,否则0

   int d = (0b000010001) | (0b00001111);

   应用: 打开某个位,只需要在该位赋1,其他位赋0,然后求|即可,因为0 | 任意数都等于任意数,1 | 任意数都等于1.

   • 按位异或^,对应位相同为0,不同为1

   int d = (0b000010001) ^ (0b00001111);

   异或可以理解为不进位相加.特点是0 ^ 任意值等于任意值,1 ^ 任意值 等于~任意值. 应用: 切换某些位,只需要在这些位上赋1,其他位赋0,进行异或,则1对应的位就会切换.

5. 移位运算 算术移位时符号位不变,即只移数值位,逻辑移位才会整体移动. 逻辑移位总是补0,算术移位时见下表:

   数值类型	原/反/补	移位规则
   正数	/	补0
   负数	原	补0
   负数	反	补1
   负数	补	左移: 补0; 右移: 补1

   计算机存储的有符号数为补码,如无特殊说明参考上表补码移位规则.无符号数参考逻辑移位规则. 当我使用进制赋值时,比如char c = 0b10000001,存储在计算机中的就是这个二进制,并不会有原码/补码的转换,转换为8进制,16进制时也是拿存储的二进制直接转换,并不会涉及到原码/补码的转换. 类型转换时,比如char -> int对于负数前面填充的就是1(就像右移一样),unsigned char则填充0,int是不是unsigned不影响填充什么(int和unsigned int的二进制表示一样).而int -> char转换时直接丢失高位,剩下的是多少就是多少.

   char ct = 0b10000001;
   int ut = ct;
   printf("%x\n", ut);
   /*
   * char ct -> ffffff81
   * unsigned char ct -> 81
   * unsigned int ut -> ffffff81
   */

   运算符:

   • 左移<<.每移1位,绝对值*2,直至出现丢失.
   • 右移>>.每移1位,绝对值/2,直至出现丢失.

   所以移位可以快速进行2的幂运算. 还可以结合&运算快速提取某些位,比如书中1149页中的例子,就很典型:

   // 从unsigned long中提取3个字节
   #define unsigned char MASK 0xff
   unsigned long color = 0x002a16f2;
   unsigned char blue,green,red;
   red = color & MASK; // 取低阶8位
   green = (color >> 8) & MASK; // 取从低阶开始数的第2个字节,8位
   blue = (color >> 16) & MASK; // 取从低阶开始数的第3个字节,8位

   Tip

   位逻辑运算和移位都不会改变原始值.

   通过位逻辑运算和移位,可以实现很多hack操作.

6. bit field位字段 用位来记录信息.前面使用过的最小结构为char,一般为8位,在某些情况下依然浪费空间了,比如一些只有2个选项的配置,用一个位来记录刚好. 位字段是一个unsigned int,signed int或_Bool类型,且位相邻,通过struct声明(操作和struct完全一致):

   解释很拗口,本质上就是在一个或多个unsigned int上使用其中的位,设置它们的类型,并进行标记,这样可以实现更紧凑的数据存储.

   struct {
       unsigned int field1 : 1;
       unsigned int field2 : 2;
       unsigned int field3 : 8;
       int field4 : 4;
   } stuff;

   上面定义了一个stuff,包括4个位字段,可以通过.运算符赋值:

   stuff.field1 = 1; // 只有1位,只能赋值0,1
   stuff.field2 = 3; // 有2位,可以赋值0,1,2,3
   stuff.field3 = 100; // 有8位,可以赋值更大的值,但是不要超过它的范围
   stuff.field4 = -6; // int类型,可以有负值

   本质上是自定义宽度的int,unsigned int,_Bool,赋值的时候也能看到,比如stuff.field2 = -6,结果为0b10即-6的最低2位,表现的值位2.

   由于可以自行设置位数,所以可能会出现总位数超过一个unsigned int(C以unsigned int作为位字段结构的载体,所以最小使用内存大小为一个unsigned int)位数的情况,此时会用到下一个unsigned int,但是一个字段是不允许跨两个unsigned int的,编译器会自动移动跨界的字段,这将造成第一个unsigned int出现未命名的”洞”. 可以使用未命名字段,来充当间隙,还可以使用未命名且宽度为0的位字段,强迫下一个字段去下一个unsigned int.

   struct {
       unsigned int field1 : 1;
       unsigned int  : 2; // field1和field2之间有2位的空隙
       unsigned int field2 : 8;
       unsigned int : 0; // 宽度为0
       int field3 : 4; // field3会存储在下一个unsigned int中
   } stuff;

   应用: 位字段核心在于宽度,宽度的重点在于几种可能性,值本身的意义不大,所以基本都使用unsigned int类型,它能更好的描述多种状态.

   Warning

   由于存在大端小端的问题,所以任何和位有关的内容在不同的机器上都需要额外的注意.

7. 实际上位字段是可以无缝转为按位运算符操作的,位字段就是一个unsigned int不同位进行标记,完全可以用位运算来模拟这个过程,只是很麻烦. 15.4_dualview.c中进行了演示,光进行位对应就非常繁琐,而使用标记显然人性化的多.

   Tip

   如无特殊说明,都是按低位到高位载入结构.

8. 内存对齐(边界对齐) 对齐是什么? 对齐是根据数据宽度,把数据存储在满足对齐要求的地址上,这些地址能被$2^n$整除.比如int一般存放在能被4整除的地址上. 为什么要对齐? 这涉及到内存读取数据的方式,只需要明确内存在读对齐的数据时效率更高.在数据没有对齐时,需要多次读取和组合才能完成数据读取,效率低是必然的,甚至某些CPU直接不支持读这样的数据.

   CPU在读取数据时,并不是一个字节一个字节的读,而是根据机器字长一次性读取,所以每次都是从满足要求的位置开始读,而不是任意位置,所以存储数据时尽量放在一次能读的范围内,这就是对齐.

   • _Aligof,返回一个类型的对齐值.

   size_t d_align = _Aligof(float);

   • _Aligas,指定变量或类型的对齐值.用作声明的一部分. 注意指定的对齐值不要小于该类型的基本对齐值.

   // 放在类型说明符前面后面都可以
   _Aligas(double) char c;
   _Aligas(8) int d;

   struct时,不同的排列可能使用的内存大小不同.

   实际上并不需要太过关注对齐,编译器一般会正确的处理,但是需要知道对齐的概念,比如在处理

   struct的内存对齐,假设有struct struct_name *sn指针,这个指针是依据struct的大小进行读取的,所以每个struct对象的大小都应该是一样的,否则指针读取就会乱套.但是引入对齐的概念后,怎么保证每个相同结构对象所占大小一致呢?是否存在这个结构对象为了对齐空出了一部分,另一个结构对象刚好放的下,没有留下空隙.这是不会的,结构中成员的类型和顺序决定了结构的相对空隙,每个结构对象都会以相同的空隙存放,就好像一个整体一样,这个整体有自己的对齐地址要求,且连续存放的首地址也一定满足对齐要求,就好像普通的内置类型一样.

   关于

   Caution

   本章所列的C语言特性,在使用时一定要注意是否是针对特定硬件或操作系统的.

chapter16

1. 预处理器仅限一个逻辑行.由于编译器会把换行符实例”<Enter>“删除,将多个物理行合并为一个逻辑行,所以换行符实例是允许出现在预处理指令中的.

2. #define分为3个部分,指令,宏,替换体.

   #define TWO 2 // 注释会被编译器处理成一个空格
   #define OW                                                                     \
       "Consistency is the last refuge of unimagina\
       tive.- Oscar Wilde" // 换行符实例是被允许的,编译器会处理
   #define FOUR TWO * TWO
   #define PX printf("X is %d.\n", x) // 表达式也可以作为宏的值
   #define FMT "X is %d.\n"

   宏分为:

   • 类对象宏,object-like macro,就是用宏代表值,上面例子中的宏都是.

   • 类函数宏,function-like macro,可以带参数,外形和作用都类似函数.但是和函数不同的是,函数是传递值,预处理器是传递token.

     #define SQUARE(X) X*X // 带参数预处理指令
     int z;
     int x = 5;
     z = SQUARE(x + 2); // x + 2*x + 2,会直接展开成这样

   预处理器将程序中的所有宏实例用替换体代替,这个过程被称为宏展开,宏展开的过程可以是递归的,也就是宏可以包括其他宏. 宏展开并不会进行计算,即使是常量表达式,常量表达式的计算是在编译过程中进行的.

   Warning

   双引号中的宏是不会被展开的.

3. 关于常量表达式 C中常量表达式中只能是常量.#define定义的都是宏常量,const声明的不能作为常量(有些编译器可以).

   #define LIMIT 20
   const int LIM = 50;
   static int arr1[LIMIT];  // 允许
   static int arr2[LIM]; // 部分编译器允许

   应尽量多的使用宏常量,可以助记,易更改,可移植.

4. 字符型字符串和记号型字符串 对于#define SIX 2 * 3,预处理器可能有2个解释:

   • 解释为字符型字符串,2 * 3中间的空格也是替换体的一部分
   • 解释为记号(token)型字符串,2 * 3表示为3个记号2,*,3,即用空格隔开的词.

   C编译器对比预处理器更能理解C语言,所以编译器在没有空格分隔的情况下也能正确识别记号.

5. 类函数宏 类函数宏是传递token实参对宏形参在替换体中进行直接替换. 在替换体中可以使用#宏形参将实参token转换为字符串.

   #define PSQR(X) printf("The square of " #X " is %d.\n", ((X) * (X)))
   PSQR(y); // printf("The square of y is %d.\n", ((y) * (y)))

   可以使用##将2个token组合成一个token,形成新的标识符,这在构建变量名上很有用.

   #define XNAME(n) x##n
   #define PRINT_XN(n) printf("x" #n " = %d\n", x##n)
   int XNAME(1) = 14; // x1 = 14

   可变参数宏,类似可变参数函数,参数个数不固定,最后的形参必须是...,在替换体中使用__VAR_ARGS__表示剩余的参数.

   #define PR(X, ...) printf("Message " #X ":"__VA_ARGS__)
   PR(1, "x=%g\n", x); // printf("Message " "1" ":""x=%g\n",x);

   不要忘记了字符串联的写法,"" "" ""...,会被串成一个字符串.

   #define就是各种字符串拼接替换的过程.

   本质上

6. 宏和函数的选择 很清晰的区别,宏生成语句,需要更多的空间,更少的时间,函数反之. 就像重复调用一个函数,和复制了多个函数一样. 当然,宏的灵活性更低些,且要求一个逻辑行中完成. 宏不关心或者说不检查变量类型. 一般的建议,简单的函数用宏,但是要注意把形参括起来,避免丢失执行顺序.

   #define MAX(X,Y) ((X) > (Y) ? (X) : (Y))

7. #include指令,用于包含文件.效果相当于把对应文件的内容加载到#include指令处. 关于路径搜索,有2种语法:

   • <filename>,用尖括号指从标准系统目录中查找.

   • "filename",用双引号指先从当前目录或文件名指定目录中查找,如果未找到再从标准系统目录中找.这里的”当前目录”和编译器设定有关,可以是源代码目录,工作目录或项目目录.

     #include "filename"
     #include "/usr/lib/filename"

   为什么需要#include头文件,因为编译器需要,比如函数原型,一些宏定义等语义上的要求,以及复用,抽象等工程上的应用. 通常.h表示头文件,使用#include引入,放在源文件顶部,辅助编译用,一般不会包括可执行代码,可执行代码通常放在源文件中.

   Note

   头文件的内容主要是编译器编译时需要的辅助信息,并不一定会添加到最终可执行二进制文件中.

8. 头文件中常包括哪些内容:

   • 明示常量

   • 宏函数

   • 函数声明(原型)

   • 结构模板定义

   • 类型定义

   • 引用式声明变量,比如extern int var;

     对于外部链接的变量和函数,都可以使用extern来引用.外部链接是跨翻译单元的,不允许重名(编译也不通过).extern本质也是辅助编译用,当编译链接了多个文件时(多个翻译单元),当我可以使用这个外部链接的变量时,应该怎么去用?extern就是形式.

   • const static声明,这和extern的区别是,这是内部链接,存在于每个翻译单元.

   • 内联函数

   对于项目开发,良好的头文件设计是一个好的习惯.

9. 其他指令

   • #undef,取消#define
   • 条件编译

     • #ifdef,#else,#endif,顾名思义.注意这里的#ifdef是预处理器进行了定义的,普通变量并不是预处理器定义的,对预处理器来说就是未定义的.

        #ifdef MAVIS
        #    include "horse.h"
        #    define STABLE 5
        #else
        #    include "cow.h"
        #    define STABLE 15
        #endif

       不仅仅是预处理指令,正常的可执行代码也可以进行控制.

     • ifndef,和ifdef相反 除了上面的用法,还一个常见用法可以防止多次包含同一个文件. 比如对某个头文件things.h:

       ifndef THINGS_H_
       #    define THINGS_H_
       ...
       #endif

       这样只有第一次引入时有效,后面引入因为已经定义了THINGS_H_导致不会真的被引入. 这在于深度嵌套#include时非常有用. 这种宏标识符,一般约定使用大写的文件名,用_代替.,使用_或__作为前缀或后缀.标准一般作前缀,用户建议作后缀,避免冲突.

     • #if,elif,不是判定是否定义了宏,而是判定常量表达式是否为真,和C本身的判定很像,非0即真.

       #if SYS == 1
       #include "some.h"
       #elif SYS == 2
       #include "this.h"
       #else
       #include "other.h"
       #endif

       #if也可以实现#ifdef的效果,要用到defined运算符:

       #if defined (SOME_H_)

10. 预定义宏

宏	含义
__DATE__	预处理的日期,格式”Mmm dd yyyy”
__FILE__	当前文件的文件名字符串字面量
__LINE__	当前文件中所在行号整型常量
__STDC__	设置为1时,表明实现遵循C标准
__STDC_HOSTED__	本机环境设置为1;否则设置为0
__STDC_VERSION__	支持C99标准,设置为199901L;支持C11标准,设置为201112L
__TIME__	编译代码的时间,格式为”hh:mm:ss”

__func__返回当前所在的函数的函数名字符串,特殊的是这个具有函数作用域,而宏都是具有文件作用域,所以__func__被认为是C语言的预定义标识符,而不是预定义宏.

这个特性在很多语言中都有,比如js(nodejs),python等

1. #line和#error #line重置__FILE__和__LINE__.注意这里是重置”基准”,__LINE__都是相对这个基准输出. #error让预处理器发出一条错误信息,一般会中断编译.

   #line 10 "foo.c"
    
   #if __STDC_VERSION__ != 201112L
   #    error "Not C11"
   #endif

2. #pragma 可以通过命令行参数修改编译器选项,比如-std=c11,指定使用c11标准.通过#pragma可以在源文件中设置编译器参数,这些设置又被称为”编译指示”. C99还提供了_Pragma运算符,将字符串转换为编译指示.

   _Pragma("nonstandardtreatmenttypeB on")
   // 等同于
   #pragma nonstandardtreatmenttypeB on

   书中1239页,还展示了利用宏完成的例子.

3. 泛型

   泛型,即不确定的类型,然后根据指定的类型,应用为这个明确的类型.

   C11提供了泛型选择表达式,这不是个预处理器指令,但是通常和#define一起使用.

   _Generic(x,int: 0,float: 1,double: 2,default: 3)

   表达式的值,取决于第一个项的类型.非常类似switch,只不过_Generic使用表达式的类型去匹配.

   #define MYTYPE(X) _Generic((X),int: "int",float: "float",double: "double",default: "other")
   char *s = MYTYPE(5); // 返回int
    
   // 还可以拼接出函数调用形式.本质要明白宏替换就是字符串替换
   #define SIN(X) _Generic((X), long double: sinl, float: sinf, default: sin)(X)

4. 内联函数 函数调用需要额外的开销,建立调用+传递参数+执行函数体+返回.除了执行函数体其他都可以算额外的开销. 利用宏可以实现代码内联,本质上就是复制了多个函数体.

   还可以利用内联函数的特性,让编译器去优化(依赖编译器的实现,所以有可能优化,也有可能不优化),优化的逻辑依然是用内联代码替换函数调用,即复制函数体. 内联函数的定义和调用必须在一个文件中,即内联函数必须是内部链接的,所以多个文件想要调用同一个inline函数只能使用多份相同的定义,放在头文件是个好的选择. 所以内联函数的定义:

   inline static void fn(void){...};

   内联函数通常比较短小,毕竟如果函数体执行时间很长,那内联的意义就不大了.

   如果省略static,将被视为可替换的外部定义(见1247页).

   From:

   When an inline function is not static, then the compiler must assume that there may be calls from other source files; since a global symbol can be defined only once in any program, the function must not be defined in the other source files, so the calls therein cannot be integrated. Therefore, a non-static inline function is always compiled on its own in the usual fashion.

5. _Noreturn函数 该函数说明符的含义是调用后不返回主调函数,比如exit()就是.编译器可根据该说明符进行一些优化,但是千万别滥用.

6. 库文件 头文件只负责辅助编译,并不管具体的执行,具体的执行需要链接对应的库文件(或其他指定源文件),有些会自动链接,有些需要手动指定,可以直接手动指定,或使用相关的编译参数来指定.

7. 对于某些封装好的类函数宏,和函数名一样,如何强制调用函数,而不是类函数宏呢? 使用(function_name)(args)方式,因为类函数宏后面必须跟(),否则无法调用宏.

8. atexit用来注册exit时回调的函数,可以做一些清理动作.注册模型为栈,即最后注册的最先执行.

   // 传入一个函数指针,且函数类型为参数和返回值都是void
   extern int atexit(void (*__func)(void))

   main方法,会隐式的调用exit.

   exit函数在执行完atexit注册的函数后,会做一些清理工作,比如刷新所有输出流,关闭所有打开的流,关闭临时文件等,然后把控制权返回主机环境,并报告终止状态,比如在UNIX系统中0表示成功终止,非0表示终止失败.

9. qsort,这是一个排序函数.

   extern void qsort(void *__base, size_t __nmemb, size_t __size,
                     __compar_fn_t __compar)
   typedef int (*__compar_fn_t)(const void *, const void *)

   根据函数签名可以看到,第一个参数和最后一个比较函数都使用了void *指针,这可以看作通用指针,即它可以是任何类型的指针.使用void *是为了通用性,这也就舍弃了便捷性,比如第一个参数为数组,但是一个void *指向,你什么都做不了,还需要告知数组大小及元素大小,也就是第2个和第3个参数.比较函数中的void *,同理,这是无法直接比较的,同样需要强制转换为具体类型.

   // 调用例子
   double vals[NUM];
   qsort(vals, NUM, sizeof(double), mycomp);
   int mycomp(const void *a1, const void *a2)
   {
           // 必须要先强转,否则指针压根不知道所指向的对象大小,也就无法正确的读取了
           const double *p1 = (const double *)a1, *p2 = (const double *)a2;
    
           // 利用bool表达式true为1,false为0特征
           return (*p1 > *p2) - (*p1 < *p2);
   }

   完全可以借助泛型表达式做一个通用数字类型的比较器.

10. assert断言库,调试用. 使用assert.h头文件,利用相关宏.assert的好处是调试相关代码是否正确,当表达式为false时,会输出相关文件名和行号,同时使用abort终止程序. 为什么不用if,if也能达到目的.if一般属于程序本身,调试代码和业务代码应解耦. 在assert.h头文件前使用#define NDEBUG即可关闭assert.

assert(z >= 0); // 断言z >= 0,否则抛出错误,并终止程序

#define NDEBUG // 关闭断言
#include <assert.h>

还有另一种断言,可以在编译期就生效(assert是运行时检查).

_Static_assert(CHAR_BIT == 16, "16-bit char falsely assumed!");

接收2个参数,第一个为常量表达式(编译期求值,只能是常量表达式),为0或false时,显示后面的字符串,并停止编译.

1. memcpy和memmove,数组拷贝. 数组是无法直接赋值为字面量数组的,所以需要拷贝进行数组赋值.

   extern void *memcpy(void *restrict __dest, const void *restrict __src,
   extern void *memmove(void *__dest, const void *__src, size_t __n)

   2个函数都可以拷贝数组,区别在于一个有restrict一个没有.使用memcpy函数,编译器认为这2个内存区域没有重叠(唯一且初始的访问方式),可以优化拷贝过程;而使用memmove,编译器无法确定有没有内存重叠,只能使用拷贝到缓冲区,再拷贝到目标位置的形式.

   可以想象内存区域有重叠时,如果边读边拷贝,有可能拷贝后又影响到了原数组的值.

   restrict要求,使用者要对这个行为负责.

   编译器并不检查是否真的满足

   拷贝过程中也无需知道数据类型,因为是按字节数拷贝(第3个参数),这也意味着拷贝后,读取数据时有可能因类型问题读出来的值完全没有意义.

2. 可变参数 前面提到过function-like宏的可变参数,但是终究不是真正的可变参数函数. stdarg.h提供了可变参数函数的使用方法,但是用起来非常的难受.

   1. 函数的定义要求,最后一个形参为...,倒数第2个形参为int类型,因为它代表可变参数的个数,被称为paramN.

   2. 要定义一个va_list类型的变量,用于存放可变参数

   3. 使用va_start(va_list,paramN)宏,将可变参数拷贝到前面定义的va_list变量中

   4. 使用va_arg(va_list,type)访问参数,每调用一次按顺序返回一个参数,且过程不可逆. 鉴于这种不可逆,又提供了va_copy宏,用于复制va_list,方便重新读取.

      va_copy(apcopy,ap);

   5. 最后使用va_end(va_list)进行清理

   double sum(int n, ...)
   {
       va_list args;
       va_start(args, n);
       double total = 0;
       for (int i = 1; i <= n; i++)
            total += va_arg(args, double);
       va_end(args); // 不要忘记清理
       return total;
   }

chapter17

1. 程序设计的一个重要过程首先是设计或选择一种数据类型,即确定数据结构,以及针对该结构的有效操作(这也是面向对象的思路).

2. 链表的意义 如何保存不确定个数的对象? 使用数组,如果数量太多了,栈溢出了怎么办?使用静态数组!但是这样大小就是固定的了. 能不能使用动态数组?可以,但是为避免栈溢出问题,此时要先评估数量,再malloc.但是前提是你评估的数量是准确的,否则依然浪费或不够. 能不能确定一个就分配一个的内存,这样即不浪费,也不用担心不够.可以,但是有一个问题,多次malloc的内存块并不能保证连续性,不像一次malloc的,只需要一个指针就能访问所有对象,此时需要保存N个指针,怎么保存?数组或链式存储都可以,这里的数组保存的是指针,需要的空间非常有限,而链式存储就是链表的特征了.

   下面是一个简单的链表添加实现,非常粗糙,通过3个指针:head,prev,current协作完成结构的链接. 这个例子不是一个良好的设计,把业务和链表功能耦合了,正常应该是暴露链表接口,隐藏具体的实现细节,供业务调用即可.

   struct film *head = NULL;
   struct film *current, *prev;
   char input[TSIZE]; // 这里没有直接创建结构,应尽量简单
   puts("Enter first movie title:");
   while (s_gets(input, TSIZE) != NULL && input[0] != '\0')
   {
       current = (struct film *)malloc(sizeof(struct film));
       current->next = NULL;
       strcpy(current->title, input);
       if (head == NULL)
           head = current;
       else
           prev->next = current;
       // prev完成链接后,前移
       prev = current;
       puts("Enter its rating<0-10>:");
       scanf("%d", &current->rating);
       while (getchar() != '\n')
           continue;
       puts("Enter next movie title:(blank to quit)");
       // input[0] = '\0';
   }

3. 什么是类型? 类型特指2类信息: 属性和操作. 书中1320页,列举了整数的概念,整数的属性本身在C语言之外有很完备的定义和抽象,C自己也实现了整数的部分属性和操作,但并不是全部. 定义一个新类型的方法:

   1. 提供类型属性和操作的抽象描述,这种描述和实现以及编程语言都无关,被称为抽象数据类型ADT
   2. 开发一个实现ADT的编程接口(存储数据和操作数据接口),也就是用程序语言去描述相关接口
   3. 实现接口

   这种模式的好处是,ADT是高度抽象的,使用者只关注怎么调用,具体的实现细节毫不关心,也不用关心.实现接口的人员可以随时调整实现细节,而调用程序完全不需要调整.当然这些的前提是抽象要合理且实用,这就需要良好的开发经验和水平了.比如17.3_list.h,17.5_list.c实现的简单链表,甚至在list.c的具体实现中都可以不用链表来完成相关功能,只要满足接口就行,这些细节对外是隐藏的.

4. 队列 实现队列可以利用环形数组和链表,因为这2个结构都可以快速修改首元素指向.

   环形数组,物理上没有,逻辑上可以实现,比如i = (i + 1) % (sizeof(arr)/sizeof(arr[0]))作为下一个索引值,就可以完成轮回.

   链表实现如下:

   #ifndef _QUEUE_H_
   #define _QUEUE_H_
   #include <stdbool.h>
    
   // 示例数据结构
   typedef int Item;
   #define MAXQUEUE 10
    
   // 抽象节点
   typedef struct node
   {
       Item item;
       struct node *next;
   } Node;
    
   // 抽象队列
   typedef struct
   {
       Node *front;
       Node *rear;
       int count;
   } Queue;
    
   // 抽象操作
   void InitializeQueue(Queue *pq);
   bool QueueIsFull(const Queue *pq);
   bool QueueIsEmpty(const Queue *pq);
   int QueueItemCount(const Queue *pq);
   // 添加到队首
   bool EnQueue(Item item, Queue *pq);
   // 删除队尾的元素
   bool DeQueue(Item *item, Queue *pq);
   void EmptyTheQueue(Queue *pq);
    
   #endif // !_QUEUE_H_

   #include "queue.h"
   #include <stdio.h>
   #include <stdlib.h>
    
   static void CopyToNode(Item item, Node *pnode);
   static void CopyToItem(Node *pnode, Item *pitem);
    
   void InitializeQueue(Queue *pq)
   {
       pq->front = pq->rear = NULL;
       pq->count = 0;
   }
    
   bool QueueIsEmpty(const Queue *pq) { return pq->count == 0; }
    
   bool QueueIsFull(const Queue *pq) { return pq->count == MAXQUEUE; }
    
   int QueueItemCount(const Queue *pq) { return pq->count; }
    
   bool EnQueue(Item item, Queue *pq)
   {
       Node *pnew;
       if (QueueIsFull(pq))
           return false;
       pnew = (Node *)malloc(sizeof(Node));
       if (pnew == NULL)
       {
           fprintf(stderr, "Unable to allocate memory\n");
           exit(EXIT_FAILURE);
       }
       CopyToNode(item, pnew);
       pnew->next = NULL;
       if (QueueIsEmpty(pq))
           pq->front = pnew;
       else
           pq->rear->next = pnew;
       pq->rear = pnew;
       pq->count++;
       return true;
   }
    
   bool DeQueue(Item *item, Queue *pq)
   {
       Node *pt;
       if (QueueIsEmpty(pq))
           return false;
       pt = pq->front;
       pq->front = pq->front->next;
       CopyToItem(pt, item);
       free(pt);
       pq->count--;
       if (pq->count == 0)
           pq->rear = NULL;
       return true;
   }
    
   void EmptyTheQueue(Queue *pq)
   {
       Item dummy;
       while (DeQueue(&dummy, pq))
           continue;
   }
    
   // 可用于处理不能直接拷贝的情况,比如数组
   static void CopyToNode(Item item, Node *pnode) { pnode->item = item; }
   static void CopyToItem(Node *pnode, Item *pitem) { *pitem = pnode->item; }

5. 链表和数组

   数据形式	优点	缺点
   数组	随机访问	编译时确定大小.插入,删除麻烦(需要移动多个元素)
   链表	运行时确定大小	不能随机访问,C没有内置,需要自行编程实现(C++有内置)

   所以需要频繁查找的应该使用数组(数组还支持二分查找法,随机访问的优点),需要频繁添加删除的应该考虑链表. 如果2种情况需要,此时应该考虑使用二叉查找树.

6. 二叉树 最简单的二叉树是二叉查找树BST,可以说是一个实现了二分查找的链表.

   二叉树家族还有平衡二叉树,红黑树,B-Tree,B+Tree等变种,用于不同的情况.

   实现一个二叉树.

   二叉树ADT(1396页):

   类型名: 二叉查找树 类型属性: 二叉树要么是空节点集合(空树),要么是有且只有一个根节点的节点集合.每个节点都有2个子树,左子树和右子树,每个子树本身也是二叉树.每个节点有一个项.左子树的项都小于根节点的项,右子树的项都大于根节点的项. 类型操作:

   • 初始化空树
   • 确定树是否为空
   • 确定树是否已满
   • 确定树的项数
   • 在树中添加一个项(节点)
   • 在树中删除一个项(节点)
   • 在树中查找一个项
   • 在树中访问一个项
   • 清空树

   接口抽象: 虽然实现方法有多种,甚至可以用数组来实现(利用下标,比如根放在n/2,左子树放0 ~ n/2 - 1,右子树放n/2 + 1 ~ n-1).但是最直观的方法依然是使用链式节点完成.

   接口实现: 17.10_tree.h,17.11_tree.h进行了上面ADT接口的实现,比链表要复杂许多,很容易犯错,好在这种程序一般都有对应的库.

   二叉树的项可以是非常多样性的,比如可以是索引(key),然后再去索引对应的结构中进一步操作,这可以极大扩展使用场景.

7. 平衡二叉树 为什么要平衡,设想1,2,3,4,5...的顺序写入二叉树,按上面的逻辑,这个二叉树只有右子树,完全跑偏,执行效率和普通的链表基本没区别,失去了二叉查找的效率.所以要平衡,让左右子树高度接近,但是这要不停的调整树,所以插入,删除的效率较低,但是却可以最大化查找效率.

其他

变量

变量就是地址，编译运行时全部转换为了地址，它本身是助记符。

引用类型和值类型

引用类型和值类型的最大区别是定义变量时，分配了几块内存，引用类型会分配2块，一个是类指针，一个是对象，而值类型只会给对象分配内存。

比如C，它是完全的值类型:

int a[3] = {1,2,3}

a就是这个数组的首地址，并不是a有一个单独的地址，里面存放的是这个数组的地址，所以上面的初始化只分配了一块内存，但是比如js中：

let a = [1,2,3]

这实际分配了2个地址，a，和[1,2,3], a存储了数组的地址。

引用类型拷贝是拷贝的地址，值类型拷贝就是拷贝的本身(浅拷贝)。

Tip

实际从赋值的角度看，没有什么引用类型和值类型，都是对某个地址里存储的数据进行复制。

对引用类型的操作（比如最常见的.运算符）会自动解引用到对应的对象去操作：

let a = [1,2,3]
a.push(4)
// 本质上
(*a).push(4) // 当然，js没有指针的概念，这是逻辑上的意义

引用类型的最大的限制是，你知道这个变量里存的是对象的地址，但是你无法获取，你只能对这个”指针”进行操作，它会自动解引用。

C语言通过指针来手动实现”引用类型“，好处是非常灵活，当然也够麻烦。

而Go是混合类型，值和引用都存在，够灵活，但是也带来混乱，比如指针有些时候会自动解引用，有些时候又像普通的类型比如int去操作。