C语言复习笔记

Lesson 1: 输入输出

1. program程序 Operations运算符 expressions表达式 statements语句

2. 理解第一个程序hello.c的各个部分：

   #include : preprocessor directive 预处理指令
   main: function 函数
   int main(): takes no arguments, return an integer 无参数, 返回整型
   main: .c contains one and only one main function 一个.c文件有且仅有一个main函数
   printf: print+f: format 格式化输出

3. %f或者%lf都表示匹配输出double类型的值；但是scanf输入只能使用%lf匹配

4. 如果是输入输出的是long double类型, 对应的格式串是 %Lf.

5. const double PI; 定义常量, 常量要全大写命名。

6. % 和 f 中间可以有一些东西. 例如%10.2f这里的点不是小数点, 而是分隔的意思, 10表示字段的宽度为 10 个字符, 如果浮点数本身不足 10 个字符, 那么会在左侧用空格填充; 2表示小数点后要保留2位数字.

7. %.2d 或 %02d // 最少这个整数要输出2个数字，不足则前面补0

   %.2s // 输出前2个字符 (如果不足2个字符就有多少输出多少), 空字符在尾部补齐

   %2s // 输出长度为至少为2的字符串, 不够就在前面补空格

8. 注意字符串定义时要多定义一位，因为字符串的最后是\0,

   例如: char first_name[5] = "Tayu";

9. %c在匹配用户输入的时候不会忽略空白符，所以要注意在scanf中就要加入空白符以匹配掉0到任意个空白符。

   scanf("%s%s %c",                               
        first_name, last_name, &gender);       

10. 字符串越界, 会出现UB. 所以要用%9s 限制输入的最长长度。

11. %*lf的意思是虽然让你输入, 但是变量该是什么还是什么. 这样的话scanf(“%*f”,&a);用来输入double类型也是可以的。

12. printf 默认遇到 '\0' 就会停止打印.

13. pow函数: 注意可能引起报错, 底数 a为负数并且指数 b 不是整数, 将会导致 domain error 错误

Lesson 2: if-for-array

1. 要养成分行定义多个变量的编码风格.

2. 变量在声明的时候一定尽可能给一个初始值, int a = 0;

3. 较小数程序:

   if (a >= b) {
     min = b;
   } else {
     min = a;
   }

4. ? : //Ternary Operator 三目运算符

5. 输出单个字符也要用"", 因为是字符串: printf("A");

6. undefined behavior：未定义行为

   例:

   char a;

   scanf("%d", &a);

   就是一个undefined behavior (UBs)

   c语言标准没有规定发生什么情况, 出现任何情况都有可能, 这取决于编译器厂商.

   所以, Avoid UBs! ! !

7. 用宏定义的常量叫符号常量, const关键字定义的叫字面常量.

   推荐所有的数组长度都用宏定义的符号常量

8. 可变长数组:

   int n;

   int a[n];

   这样做是非常不推荐的

9. : subscript operator (下标运算符)

10. 数组访问越界错误, 经典的UB, 编译器会悄无声息地换成另一个值.

11. for循环的第一部分 int i = 1; 可以是一个定义(C99以后才可以).

12. 下标0的元素可以被赋值一个不影响后面元素的值 , 后面所有其余元素自动被赋值为0.

13. 一个变量有左值和右值, i = 1; //左值， 指代的是i所在的空间

    j = i; //右值，指的才是它真正的值

14. int num[] = {0};这样只是开了一个元素, 不要以为开了任意个. 并且也不要不写长度.

15. int num[20] = {[2] = 1};这种写法是可以的

16. int numbers[NUM] = {};什么都没有, 标准上这样不允许.

17. 不推荐不对数组初始化.

18. 如果字符数组不初始化(即在等号后面写上字面量的话), 那么它是什么值都有可能(每个元素都是垃圾值), 且最后一位也==不是'\0'==而是垃圾值. 所以要么就给出字面量, 要么就使用sprintf初始化, 否则自己一定记得把结尾后面的元素手动写成'\0'. (另: memset(str, 0, strlen(str))是毫无问题的字符串初始化为全零的操作)

Lesson 3: for-while

1. VLA: variable-length array 可变长数组 C99 introduces VLA

   C11 makes it optional 也就是说C11又把它去掉了(也就是说有没 有取决于编译器)

   而且VLA在声明时不需要(也不支持)初始化

2. 每写一段代码之后就应当下意识去运行一下, 以免错误积累...

3. 如何输入任意次直到EOF:

   int len = -1;
       while (scanf("%d", &numbers[++len]) != EOF); //先加，再判断。len++就是先判断再加

   这个操作值得掌握.

4. do-while 语句:

   do {
     // ...
   } while (a > 0);  //注意这里有一个分号, 不要忽略了

5. 程序员在写代码时不要太聪明 (不是说不设计一个好的算法) , 是说要让代码可读且简单.

6. 写代码就像写诗 -- 多换行.

7. 在合适的场景多用布尔变量.

8. scanf是有返回值的. 一般来说, 匹配了几个就返回几.

   %d%d%d, &a, &b, &c

   如果输入 1 2就返回2

   如果输入 abc 不能匹配, 就返回0

   如果是 " " 这样的空输入就返回EOF, (end of file, 文件结束符, 一般来说其值= -1 )

9. 读取int数组:

   do {
       scanf("%d", &n);
       arr[i++] = n;
     } while( getchar() != '\n');

10. 读取字符串:

    while( (string[i++] = getchar()) != '\n'); // 读入一个无换行的字符串,美中不足是最后一个位置会是'\n'(垃圾值)

11. strlen() 返回字符串长度

12. memset() 只能初始化值为0和-1

Lesson 4: 多维数组

1. game-of-life.c 中涉及的系统调用:

   Sleep(1000); //表示暂停的毫秒 ，在windows.h头文件下
   
   system("cls");  //清屏
   
   //Linux
   sleep(1); //表示暂停的秒数; 在unistd.h下
   system("clear"); // 在stdlib.h下
   printf("\033c"); // 清空

2. 二维数组实现上下左右移动:

   int vectors[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // vector[i][j]可以认为是第i组里面的第j个元素
   
   int count = 0;
   for (int k = 0; k < 4; ++k) {
       int newI = i + vectors[k][0];
       int newJ = j + vectors[k][1];
       if (arr[newI][newJ] == '?') { // 实现上下左右方向的统计雷的个数
           count++;
       }
   }

Special Lesson: Learning debug

Don't be too afraid, and learn from coding!

1. debugging思想: 削减到最小出现bug的问题 (以方便集中注意力debug, 如果你不能debug, 那么至少你要先把bug的出现域缩小, 你可以另写一个函数, 最好就几行, 以便锁定bug, 节省自己和别的帮你debug的人的精力!) -- by Mr. Niu
2. 编写测试代码, 调用检查函数, 尝试发现到底错在哪里.
3. 有用的检查错误命令:

   1. gcc -Wall hello.c

   2. gcc -Wall -Werror hello.c

   3. clang -Wall hello.c

4. 运行时内存检查: gcc -fsanitize=address hello.c 可以看到泄漏的内存总大小 / 泄漏位置, 有用极了.
5. 函数性能分析 Linux 下用 perf

Lesson 5: 函数

1. 函数名命名使用大驼峰 (谷歌).

2. 形参可以和实参同名.

3. 避免全局变量.

4. int IsPrime(int number);

   函数先声明, 后定义.

5. int BinarySearch(int key, int dict[], int len); // 这里的形参不能不写上数组长度.

6. int BinarySearch(int key, const int dict[], int len)

   如果你不想修改数组， 那么传入时一定要用const修饰.

7. 多维数组传值: 一定要写除了第一维以外所有维的数值, 如:arr[] [][][][[LEN] [LEN][LEN]

8. 在函数定义上面写 /** 加回车, 以对函数功能及参数含义作注解.

9. C语言只有传值, 以传地址的值的方法来实现传引用.

10. 无参数输入的函数声明: int Fun(void); C语言的老特性, 不能省略void, 否则可能出问题. 但是C++等其它语言则不需.

Lesson 6: 递归

1. how? C语言语法支持自调用甚至可以调用main函数自己 (c++就不能自调用main).

2. why? 适用情景: 解决问题时又遇到了和原问题差不多的问题.

3. 会不会一直递归下去, 无穷无尽? 有可能.

4. 要用递归的思维去思考问题: 子任务是比原来任务规模更小的任务, 直到最后碰到了一个最小的任务, 然后把它直接解决掉. (困难, 需要有意识训练, 需要花很长很长的时间).

5. 训练递归思维 (Ask the mirror right questions) :

   1. ==What is a smaller task?== (更小的问题是什么?)

   2. How to solve the task given the solution to the smaller one? (如果知道了小问题的解, 怎么推出原问题的解?)

   3. What is the smallest task? (最小规模的任务是什么?)

6. 像一个计算机一样思考, 理解递归的底层实现.

7. 栈空间(Stack), 堆空间(Heap), 栈帧(Stack Frame):

   Stack

   main (bottom)
   a 25 |
   b 37 |
   min 25 (top)

   min
   a 25
   b 37 (new top)

   栈空间(用以存储局部变量), 生长的方向是从上往下(自底向顶).

   调用一个函数时,会为这个函数准备一个栈帧 栈帧存储局部变量. 函数结束后, 栈帧消失.

​ 遵循FILO的一个结构. 最后调用的最先消失, 先是往栈空间不断压栈帧的过程, 后是不断弹出栈帧的过程.

8. 想要更深入理解栈空间/堆空间, 请移步计算机系统基础.

9. 注意函数里变量的生命周期问题, 函数里的数组如果是在栈空间里, 那么这个数组会随着函数的结束而消失, 所以你无法通过{int a[1005]; ... return a;}来用返回这个数组的首地址的方式试图返回这个数组/ 字符串字面量.

   解决方案 1. malloc函数申请堆空间, 但是要注意判断是否申请成功, 且调用者须把空间free掉. 2. 操作外面的数组 (传入的/ 全局的)

Lesson 7: 数据类型

1. 基础数据类型 int double char bool

2. 聚合数据类型 []

3. 整型 short (int) , int(至少4个字节), long (int), long long (int) (至少8个字节) 只是不会减少, 但不一定严格递增 signed vs. unsigned

4. printf函数 无符号整型%u, 有long就加一个l printf("ULONG_MAX = %lu\n\n", ULONG_MAX);

5. 有符号整数溢出是UB, 无符号整数溢出会发生回绕现象.

6. size_t 就是一个unsigned long long. 输出时使用%zu

7. 混用有符号和无符号就会出错 -1 > 256(unsigned). 所以尽量不要用无符号, 除非你很有把握不会与有符号数比较. (有符号会被隐式转换成无符号的)

8. 注意 可以使用typedef unsigned long long int size_t

9. 如果只写一个char, 无从得知是有符号还是无符号. (看具体系统)

10. 隐式类型转换 (1) 算术/逻辑表达式(类型提升) (2)定义初始化, 赋值(类型转换) (3)函数调用时(类型转换) (4)函数赋值时(类型转换)

11. 想要明确表示是float 后缀要加F. float pi = 3.1415926F 不加F的话就不是float, 默认是double.

12. long double 的话后缀加L.

13. 在C语言中, 0开头的数字为八进制数, 010就是十进制的8.

14. epsilon 表示浮点数所能表示的两个最近的能精确表示的数字之间的gap. (这个gap不可能为0, 为什么?)

15. 浮点数实在太复杂, 但是好在我们实际上基本用不到. (如: 做web开发就几乎和浮点数无任何关系)

16. 浮点数表示能力不够的情况除了overflow还有underflow也就是太接近0了, 无法表示(且这个gap一定会存在).

Lesson 8: 指针

1. printf("%p", &radius); // 打印地址变量(指针)要用%p, 其输出为一个十六进制数

2. 存储的其实是int类型中4个连续字节的首地址, 而不是一个字节一个字节地存储. 拿到这个首地址就可以根据int这个变量类型来解析出那4个所要的字节.

3. 左值与右值, 等号左边叫左值, 代表变量所在的一块==存储空间==(not the first address), 而右值代表空间里的那个内容

   所以, 我们可以使用 (*ptr) = 20; 这样的语句来给所指的变量赋值

4. int a = 0; 直接访问a, 或者可以int *prt = &a; 访问*p来间接访问a

5. * 叫作"解引用运算符"或者"间接寻址运算符".

6. ==动态数组: ==

   #include <stdlib.h>
   
   int *numbers = (int *) malloc(len * sizeof(int)); // (老版本 / C++)需要强制类型转换, 因为malloc返回值是void型; 且返回的是整块内存的首地址(所以使用指针变量来存).
   
   int *numbers = malloc(len * sizeof(*numbers)); // 本质上就是数组声明
   
   // recommended way
   for (int i = 0; i < len; i++) {
       printf("%d ", &numbers[i]);
     } // 把这块连续的空间当成数组使用(也可作其他用途)

7. 如果写int *prt = ...那么其实是无法判定指向的是一个int型变量还是一个以此变量开头的数组(需要C程序员自己清楚).

8. ==指针与数组== 数组名即是数组第一个元素的地址(指向int的一个指针) 所以, 可以把指向一块内存空间的首个元素的指针名接作为数组名使用.

   即 numbers[i] 就等价于 *(numbers + i)

   ​ &numbers[i] 等价于 numbers + i

   数组的名字本质上不是一个变量, 而永远都是这个数组首元素的地址.我们只能取它的值, 而不能修改它(右值).

   如果硬想把它变成一个变量, 则再定义一个指针等于它. int *prt = arr;

9. 指针的加法 *(numbers + 1) 并不是在数值上加1, 而是说一次跳过一块内存. (区别于普通的整数运算)

10. 类似的, 指针和指针可以相减, 不可以相加, 相减结果表示连续的一块内存地址两个地址之间相差的元素数. (注意不是字节数)

11. 那么arr[i] 就是 *(arr + i) 就是 *(i + arr) 就是 i[arr] // 但是你不要这么写, 码风不好.

12. 另外&arr[i] 就是 &(*(arr + i)) 就是 arr + i

13. 动态内存申请的空间用完了还需要还回去.

    为什么要还, 因为此空间不是存在栈帧里的, 而是在堆上面

    如果不free的话, 申请这块内存的指针已经没了, 但是内存里这块空间还被占据着, 没人能够再访问它. 发生内存泄漏 (引用这块内存的指针变量已经没有了但是没有释放被引用的内存)

    free(numbers); // 注意: 同一块内存不能free两次

    Q: 怎么分析是否一块内存是否被free了两次, 这其实是无法静态分析出的.

14. 如果不是堆空间不可free.

15. 申请内存有可能失败, 失败就返回一个空指针.(指向NULL的指针)

    if (numbers == NULL) { // 就是空指针
        printf("Error; No dynamic memory any more.\n");
        return 0;
      }

16. calloc : malloc 之后赋予所有元素0, 而非垃圾值

    realloc : 重新申请一个内存, 并且把原来的数组已有值赋给现在的内存.

17. 指针和字符串 1) 声明 char msg[20] = "Hello World!"; 也可以 char *msg = "Hello World!";

    ​ 2) 默认的使用指针定义的字符串字面量不可以修改char *msg = "Hello World!"; msg[0] = "N"; // 这是UB

    ​ 3) 但是如果用数组定义字符串字面量就可以修改 char msg[20] = "Hello World!"; msg[0] = "N"; // 允许

18. ()++的优先级高于*, (至于++(), 和 * 优先级相同) 所以以下语句先让str++, 且str++返回的是自增之前的值(不同于++str).

    ＊str++ != '\0';

19. const char ＊str 作为参数的意思是, 不允许通过str这个指针来修改它指向的字符, 不等同于不能修改这个字符本身.

20. const char ＊str 和 char const ＊str 是一样的, 限制str指针所指向的字符不能修改. 但是, char * const str 就不同了, 它限制了str 这个指针是一个常量指向char类型, 限制指针不能被修改 (即str++不允许)

21. size_t 是什么类型, 可以理解成无符号长长整型, 且与机器无关, 配合%zu使用.

22. 指针是怎么来的? 1) 所有的数据存放在内存里 2) 内存可以编号, 即地址, 通过地址可访问内容 3) 一个数据类型占有若干个byte(字节), 那么把其占据的几个byte的第一个byte的地址作为指针的值.

Lesson 9: 指针高级

1. strcpy:

   void StrCpy(char *dest, const char *src) {
     while ((*dest++ = *src++)); // 写成指针, 去掉循环控制变量, '\0' 的ascii就是 0
   }

2. strncmp: 比较两个字符串中的最多前n个字符

3. 指针数组: 每个元素是一个指针.

   const char *names[LEN] //指针数组定义
   
   Swap(&str[i], &str[min_index]); 
   // 相应的, 要再取一次地址, 才能传入一个二级指针
       
   void Swap(char **left, char **right) {
     char *tmp = *left; // left 实际上是二级指针, 用 * 解一次引用解出来一个指向char的指针
     *left = *right; // 这样修改的是指向字符串字面量的指针
     *right = tmp;
   }

   关于多维数组, 你只需要记住: C语言没有二维数组, 只有数组的数组.

   二维数组是一个指向数组的指针, 二维数组是一个二级指针.

   int score[ROWS][COLS] = malloc(ROWS * COLS * sizeof **score); // 感觉不如写sizeof(int)
   if (score == NULL) return 0;

4. 运算符优先级 :

   ​ (suffix)++, (), [], . , ->

   ​ ++(prefix) , * , & , ! , ~ , sizeof

   ​ *, /, %

   ​ +, -

   ​ <<, >>

5. [] // 取数组下标符具有左结合性, 即

   int student_score_table[5][3] = {
         {0,  10, 20},
         {10, 20, 30},
         {20, 30, 40},
         {30, 40, 50},
         {40, 50, 60}
     }; // 可以理解为是一个大小为5的数组, 数组里面是一个大小为3的数组
   
   /**指针访问二维数组*/
   printf("student_score_table[3][2] = %d\n",
            student_score_table[3][2]);
     printf("student_score_table[3][2] = %d\n",
            (*(student_score_table + 3))[2]);
     printf("student_score_table[3][2] = %d\n",
            (*(*(student_score_table + 3) + 2)));

Lesson 10: 函数指针/结构体

1. main函数里面是可以有参数的, main函数可以接受两个参数 argc (argument count计数, 调用了几个参数) 和 argv (argument vector) 一个数组, 数组里每个元素是一个指针, 指向char.

   int main(int argc, char *argv[]) {}

2. C语言中约定argv[0]存储了程序的名字(argv[0] is the name of program)(当然一些环境或操作系统中argv[0]是一个空指针, 不存放任何东西但是占了位), 所以真正的存入argv[]是从下标1开始存入的.

3. C语言标准规定 argv[argc] is NULL (一定是一个空指针).

   如: hello world

   argc == 3;

   argv[0] == "echo"(文件名), argv[1] == "hello", argv[2] == "world", argv[3] ==NULL

4. printf函数可以结合表达式使用 printf((argc > 1) ? "%s " : "%s", *++argv);

5. void qsort( void *ptr, size_t count, size_t size, int (*comp)(const void *, const void *) );

   参数含义: 1. 待排序数组首地址(数组名) 2. 数组中元素数 3. 每一个元素的字节数 4. comp是一个指针, 指向一个函数 ==(函数指针, functional pointer)==, 指向的函数有两个参数是void型, 返回值是int.

6. 如何获取数组长度:

   int integers[] = {1, 2, 3, 4} 
   int size_of_integers = sizeof integers / sizeof *integers; // 计算数组长度 sizeof一个数组就是返回整个数组的字节数, 注意这里sizeof不要在后面跟(), 但是sizeof(int)需要

7. 在C语言中函数名本身就是一个指针. CompareInts()这个函数, 在作为第四个参数传入qsort()时, 只要写CompareInts就代表一个函数指针.

8. 当函数名出现在表达式中时, C语言解释其为函数指针(也就是说, C语言中, 函数就是函数指针).

9. 函数指针和其它指针一样用, 你还可以构建一个函数指针数组.

   double (*fps[2])(double) = {sin, cos};  // fps是一个数组, 有两个元素, 每个元素是一个指针, 指向一个函数, 这个函数接受一个double返回一个double

10. 函数指针说到底是一个变量, 是变量就可以声明, 可以修改.

    int (*comp)(const void *, const void *) = CompareInts; // 很诡异的一个声明和赋值, 这样之后comp就完全等价于CompareInts, 在C语言中是不需要再对函数指针再解引用了(即不需要写*comp, 区别于传统指针)

11. 除了qsort, C语言还有bsearch

    void *bsearch(const void *key, const void *base, size_t nmem, size_t size, int (*comp)(const void *, const void *)); // base指向被查找的数组, nmem为查找长度, size为每个元素的大小, comp同qsort()的

12. 那么有了函数指针, 函数就是一个一般变量了, 可以作为函数的参数, 函数的返回值, 数组的元素 , 可以声明, 定义, 可以赋值, 函数指针可以干任何一般变量能做到的. 函数就成为了一等公民.

13. 复杂的函数声明: 核心是指针与数组 / *, [], ()三个运算符的结合与优先.

    题目1: 解释以下输出

    int (*arr)[3];
    printf("%lu", sizeof (arr)); // 8
    printf("%lu", sizeof (*arr)); // 12

    题目2: 解释以下声明

    void (*signal(int sig, void (*handler)(int)))(int);

14. 使用typedef定义特定类型函数指针的别名 typedef int (*NICKNAME)(int, int); 这样 NICKNAME fun; 就是对fun的一个声明.

15. struct: 一种数据类型, 与int, char等等一样.

16. 使用 typedef struct musician {, , , ,} Musician; // 用别名Musician替代struct musician

17. 结构体填充/内存对齐, 结构体的存储是有要求的, 结构体成员里面最大字节数如果为8, 那么必须要首地址是8的倍数, 尾地址也要是8的倍数.

18. 结构体也可以通过赋值号( = )来赋值, 当然, 前提是两个结构体类型相同.

19. 结构体变量也可以直接作为参数进行函数传参, 但是, 应该使用结构体指针进行传参以避免直接传结构体降低程序效率.

20. 结构体成员名可以和main函数中的变量重名.

21. 使用 结构体变量名 . 内部的变量名 (点表达式) 来访问结构体内部.

22. 结构体变量名就是一个结构体变量, 对其取址(&musician)得到的就是一个结构体指针(指向结构体变量的指针) (用结构体指针可以实现结构体的跨函数传递, 比直接传递结构体性能更高).

23. C语言不支持结构体直接判断相等. 即struct1 == struct2是不可以的(C中能用==判断相等的只能是基本数据类型), 思考:

    1. ptr1 == ptr2 意味着什么?

    2. struct1和struct2的每一个成员都相等, 又意味着什么?

24. 结构体指针示例:

    void PrintMusician(Musician *m) { // m为一个结构体指针(特别常用的做法)
    	(*m).name // 通过指针访问结构体内部的变量方法1(注意.的优先级最高, 所以括号不能省略)
        m->gender // 通过指针访问结构体内部的变量方法2
    }

25. 动态申请结构体:

    struct book *book1;
    book1 = malloc(sizeof(*book1));
    
    //也可以写成: 
    struct book *book1 = malloc(sizeof(*book1));
    // malloc之后下意识检查是否malloc到了空指针
    if (book1 == NULL) {...}

26. enum 枚举类型.

​ 定义某一个数据类型, 这种类型只有几种可能, 在定义的同时将这些可能一一列举出来, 这样的类型就叫枚举.

Lesson 11: 链表

1. 链表的每一个节点(Node)就是一个结构体, 这个结构体的第一个域可以是一个整数, 第二个域需要是一个指针(叫作next, 指向链表的下一个节点). 链表就是通过指针把多个结构体连在一起.

2. 链表和数组的区别在于数组的内存空间是连续的, 而链表每个节点都是malloc动态申请来的, 没法保证每一个的内存空间是连续的.

   所以要访问链表的某个节点就只能从头开始往后扫描(最坏的时间复杂度是O(n)而数组为O(1) ).

   (好处在于灵活, 所以插入/删除链表节点时间复杂度O[1], 而插入/删除数组元素时间复杂度最 坏O(n) )

3. 链表实现了数据的动态保存, 不需要预先分配内存空间, 而是在需要时动态申请, 整个空间可以根据需要扩大或缩小.

4. 双向链表: 一个指针(pre)指向前面, 一个指针(next)指向后面.

5. 循环链表: 最后一个节点的next指针指向Head.

6. 解决链表问题: 先想一般情况, 再讨论特殊情况 (空链表/链表只有一个节点), 再看这两类有没有可以合并的.

7. 删除节点函数Delete写的时候不应该传递被删除节点, 应传前一个指针. (双向链表无所谓)

8. 如果删了head或tail节点, 要记得更新head或tail.

9. 如果只想要在某函数符合特定条件的时候才调用一个函数, (如只有只剩1人时才return幸存者编号, 其它情况不使用该函数).

   # include <assert.h>
   assert(IsSingleton(list)); // 做一个判断, 不成立就报错. (assert 断言)
   /**
   * assert一般用于调试, 真正发布时, 要将assert去掉
   **/

10. 常见的链表操作补充:

    void Insert(LinkedList *list, Node *prev, int val);
    Node *Search(LinkedList *list, int val);

11. 特殊头节点: 不存数据, 链表的长度. 对头节点的删除操作, 不用特殊化处理. (方便读取链表的长度, 可用于频繁获取链表长度的情形)

12. 打印/遍历链表:

    while(p != NULL) {
        printf("%d", p->data);
    	p = p->next;
    }

Lesson 12: 预处理

1. 预处理就是字符串替换.

2. 宏函数可以接受不定长度的参数

   例如

   #define print(a, ...) if(a) printf(__VA_ARGS__)
   // or another way: 
   // #define print(format, ...)  printf(format, ##__VA_ARGS__)
   
   print(1, "%s", "To C or not to C");

3. 当你想要把多个语句放在一起作为一个宏函数时, use do{ }while(0)

   这样的好处是, 如果调用宏函数, 就需要在末尾加;

   #define foo() do {bar(); baz();} while(0)
   
   if (1) foo(); // 这样就十分自然地写出了看起来没有问题, 实际上也没问题的代码.

4. 一些系统给的宏 __x86_64__ 如果定义了就是在64-bit 环境下.

   #ifdef __x86_64__
   // do sth
   #else 
   // do sth
   #endif
   
   // 帮助定位错误的宏: 
   __FUNCTION__
   __LINE__
       
   __VA_ARGS__ // C99引入, 表示一个或多个参数, 类似函数可变参数中的省略号
   // 示例:
   #define print(format, ...) printf(format, ##__VA_ARGS__) // 为什么使用## 如果不带##, __VA_ARGS__会替换为省略号匹配的所有参数, 同时会将省略号前面的一个逗号带上, 导致编译器报错, ##提示编译器把多余的逗号删除

5. #和##运算符:

   #define concat(a, b) a ## b // 把a和b字符串合并
   #define string(a) #a // 给a的两边加上双引号, 变成字符串

6. ## 运算符

   ##可以将两个记号 (如标识符) "粘合" 在一起, 成为一个记号. (##运算符被称为"记号粘合") 如果其中一个操作数是宏参数, "粘合"会在形式参数被相应的实参替换后发生.

   #define MK_ID(n) i##n
   
   int MK_ID(1), MK_ID(2), MK_ID(3);
   // 就是int i1, i2, i3;

   #define GENERIC_MAX(type)
   type type##_max(type x, type y) {  \
       return x > y ? x : y;  \
   }
   
   GENERIC_MAX(float)
   // float float_max(float x, float y) { return x > y ? x : y;}

7. 如果对于字符串进行宏定义替换, 替换之后又要进行 ## 或者是 # 的操作, 又不希望因为直接做##或#而忽略掉之前的宏定义, 就可以使用一个temp宏作为中介使得一趟替换之后没有到位, 而是转入temp宏, 这样就能够使得字符串替换不被忽略掉.

8. 预处理指令

   #include 包含

   #define 宏定义

   (根据条件判断来选择编译的内容)

   #if 如果, 则预定义

   #else 否则, 预定义

   #elif 否则如果, 则预定义

   #endif 结束条件判断

   #ifdef 如果定义了, 则 (if define)

   #ifndef 如果没定义, 则 (if not define)

9. #include

​ 两种形式 <> 到配置目录中找和 " "从当前目录开始找, 无则到配置目录里找.

​ 文件包含允许嵌套. A包含B, B包含C, 那么A包含了B和C

3. #define

   宏定义, 可以带参数.

4. 条件编译 (为了提高可移植性的)

   #if (常量表达式) --> 注意常量, 非变量

   仅当表达式为真, 才编译它与#endif之间的代码

   #define debug 0
   #define beta 1
   
   #define status 1
   
   #if (status == debug)
   	printf("程序调试中\n");
   #elif (status == beta)
   	printf("程序测试中\n");
   #else 
   	printf("欢迎使用正式版!\n");
   #endif
   /*-----------------------------------*/
   #ifndef PI        // 这个判断是为了避免重复定义, 常用于一些复杂的文件
   	define PI 3.14 
   #endif         

5. 常用宏函数:

   #define SWAP(a, b) \        // 这里的反斜杠是续行, 一般在C语言中只在宏定义中才会用到
       do {           \        // 为什么不给a, b加括号, 因为 = 是除了 , 最低优先级的运算符
           int t = a; \
           a = b;     \
           b = t;     \
       } while (0) //宏需写在代码头文件下面，此为简单版，交换两个 int 型数字
   
   // 最简洁的swap
   x ^= y ^= x ^= y;  //异或真神奇！不过这究竟是为什么呢？

6. 定义宏函数:

   #define ture 1 // 把前面的字符串替换为后面的字符串
   #define false 0 
   #define foo(bar) bar + 1
   
   #define dist(x1, y1, x2, y2) (abs((x1) - (x2) + abs((y1) - (y2))) // 注意这里每一个变量都要加括号, 以避免变量内部有一个比'-'优先级更小的运算符
   static inline int Dist(int x1, int y1, int x2, int y2) {
   	return abs(x1 - x2) + abs(y1 - y2);
   }

7. #include 预编译的机制, 其实就是把被 include 的代码copy到当前的c文件中, 只是做了一个substitute的工作, 你可以写出以下的代码:

   // hello.c
   int main() {
   	printf(
       #include "inc.h"
       );
       return 0;
   }

   // inc.h
   #include "hello.h" 

   // hello.h
   hello world

8. 用gcc预编译 gcc -E a.c | less

9. 然后用vim命令\printf搜索对应的函数的声明

   extern int printf (const char *__restrict __format, ...);

10. 将这行代码copy也可以实现 printf 函数.

    其实 #include <stdio.h> 就是把以上预编译的东西全部粘贴过来, 而其中起作用的就是 printf 的声明.

11. 这就是C语言的规定, #include 做的就是纯文本的复制粘贴.

12. 预处理过程:

    #include <stdio.h>
    
    int main() {
    #if aa == bb
        printf("Yes\n");
    #else
        printf("No\n");
    #endif
    }

    这段代码被预编译为:

    #include <stdio.h>
    
    int main() {
    
        printf("Yes\n");
    
    }

    其它信息全部被擦除了. 一个变量如果是在预编译指令中, 那么不需要定义就可以使用, 其值是系统赋予的, 如__x86_64__, 而本例中, aa和bb都是空, 所以二者相等.

13. 适当使用预编译指令, 不要滥用.

14. 预编译也称为元编程 (meta-programing) , 发生在实际编译之前. (C++的模板元编程) (gcc的预处理器同样可以处理汇编代码)

Lesson 13: 位运算

1. 移位运算符: << >> ( 有符号数右移, 高位补什么视编译器而定, 一般补的是符号位(最高位) )

   为什么有符号数右移视编译器而定? 历史久, 需要兼容各类系统, C标准没有规定.

   向右移动x位相当于除以\(2^x\)

2. 移位运算的使用

   • 在能满足需求的情况下, 使用无符号数进行移位运算
   • 如果需要使用有符号数的移位运算, 请验证高位补偿的规则并考虑可移植性问题.

3. 按位与 ( & ) 按位或 ( | ) 按位异或 ( ^ )

4. 一元运算 按位取反 ( ~ ) 会对操作数进行整型提升 (不能忽略前面的位)

5. 优先级: ~ > 二元算术运算 > <<, >> > 关系运算 > & > | > 逻辑运算

6. 几个常见的错误示例:

   status & 0x4000 != 0 表示先不等于0, 然后与运算

   i << 2 + 1 表示先把 2 + 1, 再移位

7. 使用位运算访问位 将num的 (从低开始的) 第i位读取出来.

   num & (1 << i)

   将该位设置成0

   num &= ~(1 << i)

   将该位设置成1

   num |= (1 << i)

8. 使用位运算访问位域

   将 1 << i 替换为多个1bit (如 0x0070) 操作第4 - 6位

9. 异或加密

   a ^ a = 0
   a ^ 0 = a
   a ^ b ^ b = a

   加密方式: 有信息M, 秘钥K, 可以使用M' = M ^ K获得密文, 再使用M' ^ K = M ^ K ^ K = M进行解密.

10. bit vector 位向量

    一个长度为N的bit流可以表示一个最多有N个元素的集合. 下标 i 对应元素的布尔值如果为true就代表i这个数字在集合set中, 以此表示一个N个元素的集合.

    有什么用? 代替bool数组, (因为bool类型是C99后才有的), 可以换取空间优势.

    做集合的 交 / 并 / 差 运算时性能可观.

11. 例: 交换一个32位整数的高16位和低16位.

    y = ((x & 0xFFFF) >> 16) | ((x >> 16) & 0xFFFF)

12. 例: 取以2为底的对数的整数部分 [Log₂ x]

    int getLg(int x) {
    	int ans = 0;
    	if(x & 0xffff0000) {ans += 16; x &= 0xffff0000;}
    	if(x & 0xff00ff00) {ans += 8; x &= 0xff00ff00;}
    	if(x & 0xf0f0f0f0) {ans += 4; x &= 0xf0f0f0f0;}
    	if(x & 0xcccccccc) {ans += 2; x &= 0xcccccccc;}
    	if(x & 0xaaaaaaaa) {ans += 1; x &= 0xaaaaaaaa;}
    	return ans;
    }

Sp Lesson-1 git

1. git就是一系列快照, git add 就是把文件加到临时快照里, commit就是把临时快照持久化, 而分支就是不同的程序员在进行各自的开发时使用便于管理的.

2. 常用命令:

   git init git status git commit -m "" git log git add -A //把当前文件夹中所有的纳入跟踪, 添加到暂存区 git checkout fe923 // fe923就是你某一次提交代号的前几位 git checkout 8f49c // 回到某一次具体的提交(可以是已经被回退掉的版本号)

   git checkout -b "git" // 新建并转到命名为"git"的分支 git checkout master // 回到"master"分支 git branch // 查看分支信息 git merge // 合并分支

   git merge git 进入一个界面, vim模式, 先按i进行insert编辑后, 按esc退出

3. 主流的版本控制器 Git SVN

4. 版本控制分类 1) 本地版本控制 2) 集中版本控制(所有的版本数据存在服务器上, 代表工具SVN) 3) 分布式版本控制 (每个人都拥有全部的代码, 服务器或者任一用户的保存损坏了都不会有影响, 只要再重新拷贝一份就可以了, 代表Git)

5. Git是目前世界上最先进的分布式版本控制系统

6. 2005 Linus Torvalds 用2周时间开发出了自己的版本控制系统, 也就是后来的Git (为了辅助Linux内核, 开源, 免费)

7. Git Bash: Unix 与 Linux 风格的命令行, 使用最多, 推荐最多

   Git CMD: Windows 风格的命令行

   Git GUI: 图形界面的Git, 不建议使用

8. 环境变量只是为了全局使用.

9. Git 基本理论

   工作区域

   Git 本地有三个工作区域: 工作目录 ( Working Directory ) , 暂存区 (Stage/ Index) , 资源库 (Repository / Git Directory) , 如果在加上远程的git仓库 (Remote Directory) 就可以分成四个工作区域.

   • ==Workspace==: 工作区, 就是你平时存放项目代码的地方
   • Index / Stage: 暂存区, 用于临时存放你的变动, 事实上只是一个文件.
   • Repository: 仓库区 ( 或本地仓库 ) , 就是安全存放数据的位置, 有所有的版本的数据. 其中HEAD指向最新放入仓库的版本.
   • ==Remote==: 远程仓库, 托管代码的服务器.

   HEAD一开始指向的是master分支 (主分支).

   在文件中有一个隐藏文件夹.git 其中有Stage 和 Local Repo文件夹

10. git的工作流程:

    1. 在工作目录中添加修改文件;
    2. 将需要进行版本管理的文件放入暂存区域; git add . (.表示全部)
    3. 将暂存区域的文件提交到git仓库

11. Git项目搭建

创建工作目录与常用指令

工作目录 (WorkSpace) 可以是项目的目录, 不要有中文.

本地仓库搭建

一种方法是创建全新的仓库, 另一种是克隆远程仓库.

• 创建全新的仓库, git init 执行后在项目目录多出了一个 .git目录, 关于版本的所有信息都在这个目录里面.

• 克隆远程仓库到本地. git clone ... 然后就行了

  HTTP	利于匿名访问	适合开源项目	可以方便被别人克隆和读取(但没有push权限, push需验证)
  SSH	不利于匿名访问	比较适合内部项目	只要配置了SSH公钥即可自由实现clone和push操作

  (HTTP 和 SSH协议的对比)

11. Git文件操作

    文件4种状态

    • Untracked: 未跟踪,在文件夹中, 但没有加入到git库, 不参与版本控制. 通过git add 状态变为Staged.
    • Unmodify: 文件已经入库, 未修改, 即版本库中的文件快照与文件夹中内容一致, 如果被修改, 状态变为Modified. 如果使用git rm则成为Untracked文件.
    • Modified: 文件已修改, 仅仅是修改, 并没有进行其他的操作. 有两个去处, 通过git add可进入暂存Stage状态, 使用git checkout则丢弃修改, 返回到unmodify状态, 这个git checkout即从库中取出文件, 覆盖当前修改.
    • Staged: 暂存状态, 执行git commit则将修改同步到库中, 这时库中的文件和本地文件又变为一致, 文件为Unmodify状态. 执行git reset HEAD filename取消暂存, 文件状态为Modified.

12. git文件操作命令:

    git init
    git status # Untracked
    git add .
    git status #  to be commit (在*暂存区*里)
    git commit -m "commit message" # 提交到本地仓库
    git status
    git push

    忽略文件

    在主目录下建立".gitignore"文件, 此文件有如下规则:

    1. 忽略文件中的空行和以井号 ( # ) 开始的行.
    2. 可以使用Linux通配符. 例如 : 星号( * )代表任意多个字符, 问号( ? )代表一个字符, 方括号 ( [...] ) 代表可选字符范围, 大括号( {...} )代表可选的字符串等.
    3. 如果名称的最前面有一个感叹号 ( ! ) , 表示例外规则, 将不被忽略.
    4. 如果名称的最前面是一个路径分隔符 ( / ) , 表示要忽略的的文件在此目录下, 而子目录中的文件不忽略.
    5. 如果名称的最后面是一个路径分隔符 ( / ) , 表示要忽略的是此目录下该名称的子目录, 而非文件 (默认文件或目录都忽略).

    *.txt 		# 忽略所有.txt结尾的文件
    !lib.txt 	# 但lib.txt除外
    /temp	    # 仅忽略项目目录下的TODO文件, 不包括其它目录temp
    build/      # 忽略build/目录下的所有文件
    doc/*.txt   # (忽略某个文件夹下的文件)会忽略 doc/notes.txt 但不包括 doc/server/arch.txt

13. Git分支

    • master: 主分支
    • dev: 开发(develop)用
    • v4.2: 不同版本的分支

    git中常用的分支命令:

    git branch					 # 列出所有本地分支
    git branch -r 				 # 列出所有远程分支
    git branch [name] 			 # 新建一个分支, 但依然停留在当前分支
    git checkout -b [branch] 	 # 新建一个分支, 并切换到该分支
    git merge [branch] 			 # 合并分支到当前分支
    git branch -d [name] 		 # 删除分支
    
    # 删除远程分支
    git push origin --delete [name]
    git branch -dr [remote / branch]

    如果多个分支冲突了, 只要协商即可.

14. git commit --allow-empty 允许无修改

Sp Lesson-2 Vim

1. u 撤销上一步操作

2. ctrl v 块操作

3. 强制退出 :q!

4. 查找命令: :/ 正向查找 :? 反向查找

   n 前向查找 N 反向查找

   快速查找 : 1) 将光标移动到目标单词上 2) 按下*启动正向查找 # 反向查找

5. gg : 回到顶部 G : 回到底部

6. $: 跳转行末

7. 0: 行首

8. Ctrl+f：向文件尾翻一屏

   Ctrl+b：向文件首部翻一屏

   Ctrl+d：向文件尾部翻半屏

   Ctrl+u：向文件首部翻半屏

9. 1. dw 从光标当前的位置开始删除，直到删到单词最后。

   2. daw 算是1的属性扩充版，这个命令可以直接删除光标所在的一个单词。为了方便记忆，可以记忆为delete a word缩写。

   3. bdw 这也是一个复合命令。b可以让光标回退到单词开头的位置，而dw则是第1个描述过的命令。

   4. ciw 修改一个单词，change in word的缩写。

   5. Shift d 从光标处删除到行末尾.

10. vs 分栏 e 文件名 切换到文件

11. 重命名某一个字符串 %s/原字符串/新的字符串/g

Sp Lesson-3 命令行

1. cat /hello.txt 查看文件 ( 将文件内容输出至终端 ) (catch 抓来看看)

2. date 获取当前的日期和时间

3. pwd 获取当前的路径 (print work directory)

4. Linux下有一个整体的根目录. (从UNIX过来) Windows没有 (从DOS过来)

5. .表示当前目录, ./home

6. .. 表示上一级目录

7. echo: 回声

8. man ls : man即manual, 手册

9. which ls: 查看命令的位置

10. echo hello > hello.txt 输出重定向到 hello.txt 里

11. time 对于任何一个命令都可以使用 time 来查看运行时间. time ./a.out 来查看可执行文件的运行时间

12. timeout 倒计时 .. 秒, 若进程没有终止则强行停止. (可用于检测程序性能, 强行终止死循环等)

13. find 寻找文件, 如 find . | grep \.cpp$

14. grep命令用于查找文件里符合条件的字符串或正则表达式

15. wc 统计行数, 加-l只输出行数.

16. find . | grep \.c$ | xargs cat | wc -l 利用管道协作, 统计所有c语言代码行数 (xargs 的功能, 将输入转换成后面命令的参数)

17. 使用 ... | vim - , 用vim打开前面命令的输出.

18. 什么是管道命令? 命令1 | 命令2 命令1的标准输出是命令2的标准输入. (以前面命令的输出作为后面一个命令的输入, 以此类推 )

    (注: 管道命令后面接的命令必须能够接收输入的命令, 不能接不能接收输入的命令, 比如ls cp mv等)

19. 命令行中, 若要使用括号, 需要写作$( ... )左括号前加$

20. Linux命令行编程:

    for i in $(seq 1 100) # 所谓 $(seq 1 100) 本质上就是文本, 即 1 2 3 4 5 ... 100
    do
    	echo $i
    done

    (命令行的 2 个关键词: 文本, 工具)

21. 编写 .sh 文件 (shell 脚本) 来帮你对拍/ 调试程序.

    #!/bin/bash
    
    gcc bad.c -o bad.exe
    gcc ok.c -o ok.exe
    
    for i in $(seq 1 5)
    do 
    	echo ======= Test case $i ========
    	cp hello${i}.in hello.in
    	./a.out
    	cat hello.out
    done
    
    for T in $(seq 1 100)
    do
    	echo Testcase $T
    	./gen # 生成输入
    	echo "100 + 200" > in.txt
    	
    	diff -q \
    		<(timeout 1 ./ok.exe < in.txt) \
    		<(timeout 1 ./bad.exe < in.txt)
    	if [[ $? != 0]]
    	then 
    		echo 'Error!'
    	fi
    done

22. 创建 run.sh 文件, 编写文件内容为:

    for i in $(seq 1 3) 
    do 
    	./a.out < in$i.txt > out$i.txt
    	diff ans$i.txt out$i.txt || echo "Error on Testcase #$i"
    done

    这样就实现了一个对拍脚本.

    :: 在终端中运行脚本
    bash run.sh

Sp Lesson-4 gdb

1. GDB:

   gcc -g ...
   gdb ...

   start

   next (n) 5 : 步过5行

   step (s) : 步入

   continue (c): ==跳转至下一断点所在行== (from wherever we currently are)

   finish : tell gdb to finish this current function call and then stop once we finish the call

   bt : back trace 查看若干级函数调用的历史记录和参数值

   list : 看代码

   b codes/main.c: 127 : 设置断点

   ( 另可在函数上打断点, b main )

   info b (i b) : 查看断点信息

   run (r) : 从断点处或从头开始执行 (运行程序)

   print i (p i)

   print &i : 查看 i 的地址值

   set logging on : 将gdb输出结果打印至日志文件中.

   watch : 设置watchpoint以实时观察一个变量是否变化, 一旦变化, 就会输出变化信息. (查看设置了哪些watchpoint info breakpoints(watchpoints)) (用于避免反复p, 一般watch的是核心变量)

   delete ID : 删除断点 (delete 删除所有断点)

   display i : 每次n都打印出i的值.

   undisplay ID : 停止跟踪ID下标的那个变量, 一般第一个display的下标为1

   up : 返回上一级函数 (找到是谁在调用当前行)

   backtrace : 不再是一次一次地up , 而是直接全部 print the entire call stack , 看到所有的涉事指针作为参数传递时的函数调用栈. (进行 N 次up)

   fin : 执行完当前函数, 返回到上一调用层, 并打印返回值

   whatis j (what j) : 可以得知 j 的数据类型

2. gdb高级

   target record-full : 记录所有东西

   rn (reversed-next) : 回退一步 ( rs (reversed-step) rc (reversed-continue) )

   set var x=15 : 改变x的值但是不退出gdb运行.