001-c语言复习

时间：2021年3月

0、新增内容

（1）函数strdup
strdup（）函数是c语言中常用的一种字符串拷贝库函数，一般和free（）函数成对出现。
strdup()在内部调用了malloc()为变量分配内存，不需要使用返回的字符串时，需要用free()释放相应的内存空间，否则会造成内存泄漏。该函数的返回值是返回一个指针,指向为复制字符串分配的空间;如果分配空间失败,则返回NULL值。
（2）函数strchr
在字符串里搜索某个字符
char *strchr(const char *str, int c)
（3）不定参数函数、vfprintf 和 fprintf函数例子（来自githu的netcwmp）：

void cwmp_log_write(int level, cwmp_log_t * log, const char * fmt, va_list ap)
{
    cwmp_log_t * logger;

    if (log)
    {
        if (log->level < level )
        {
            return;
        }
        logger = log;
    }
    else
    {
        if (g_cwmp_log_file.level < level)
        {
            return;
        }
        logger = &g_cwmp_log_file;
    }
    logger = g_ot_log_file_ptr;
    vfprintf(logger->file, fmt, ap);
    fprintf(logger->file, "\n");
    fflush(logger->file);
}

（4）C 标准库的 ctype.h 头文件提供了一些函数，可用于测试和映射字符。
（5）snprintf 用法例子：

snprintf(buf, 256, "http://%s:%d", local_ip, port);

（6）关于头文件的引用
“”代表在编译的目录下搜寻
<openssl/ssl.h>表示在 gcc -I <目录> 提供的目录下查找openssl文件夹，然后找到该文件夹下的ssl.h

一、C语言的由来、特点和用途

1.1 由来

• 1972年，美国贝尔实验室的 D.M.Ritchie 在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言；
• C89：1989年，ANSI发布了第一个完整的C语言标准——ANSI X3.159—1989，简称“C89”，不过人们也习惯称其为“ANSI C”；
• C90：C89在1990年被国际标准组织ISO(International Standard Organization)一字不改地采纳，ISO官方给予的名称为：ISO/IEC 9899，所以ISO/IEC9899: 1990也通常被简称为“C90”；
• C99：在1999年，ISO发布了新的C语言标准，命名为ISO/IEC 9899：1999，简称“C99”；
• C11 在2011年12月8日，ISO又正式发布了新的标准，称为ISO/IEC9899: 2011，简称为“C11”；

1.2 特点

• C 语言是一种面向过程的计算机程序设计语言；
• 处在高级语言（如java、c++）和低级语言（汇编语言）之间，编译出的目标文件的效率比汇编语言低10%~20%；

1.3 用途

• 嵌入式系统编程：因为C语言贴近底层硬件，面向对象的以及目标文件效率较高等，所以它经常被应用于消费类电子产品、工控机器、仪器仪表这些嵌入式设备的软件设计。
• 计算机系统设计，例如linux内核
• 电脑应用软件，例如nginx（高性能的HTTP和反向代理web服务器）、vim（linux自带的文本编辑器）、git（分布式版本控制）

二、编译

2.1 搭建环境

使用gcc编译器来编译代码。在windows下安装 "MinGW-gcc"，并把目录下的bin文件夹添加到windows的环境变量中。“Win+R”组合键，然后输入cmd，回车，就能打开cmd界面。命令“gcc <路径+文件名.c>"即可编译文件，生成可执行文件“a.exe”。

2.2 编译原理

2.2.1 过程

预处理、编译、汇编、连接

2.2.2 原理

【待续】

三、基础

3.1 程序结构

• 语句：程序执行的基本单元，; 代表一条语句的结束；
• {} 里面的一系列语句构成一个程序块；
• 函数：多个程序块构成，用与实现特定功能；
• C文件：由多个函数、全局变量定义构成的文件；
• 头文件：变量定义、函数声明的文件；
• C工程：诸多C文件和头文件构成的整体。

3.2 程序语句中的元素

3.2.1 标识符

• 用来标识变量名、函数名、宏名的一组字符串，该字符串不可与关键字相同；
• 规则：
  （1）开头字符可以是字母 A-Z 或 a-z 或下划线 _ 开始；
  （2）开头字符后面是零个或多个字母、下划线和数字（0-9）（注：换言之，开头为数字是错误的标识符！）；
  （3）区分大小写

3.2.2 运算符

• 算术运算符
  +：加
  -：减
  *：乘
  /：除
  %：取余
  ++：自加（a++表示运算完自加；++a表示先自加再运算）
  --：自减
• 关系运算符
  ==：等于
  !=：不等于
  >：大于
  <：小于
  >=：大于等于
  <=：小于等于
• 逻辑运算符
  &&：与
  ||：或
  !：非
• 位运算符
  位运算符作用于位，并逐位执行操作，包括
  &： 与
  |： 或
  ^： 非
  >>：右移
  <<：左移
• 赋值运算符
  =：等于
  +=：先做加运算，然后赋值
  -=：先做减运算，然后赋值
  *=：先做乘运算，然后赋值
  /=：先做除运算，然后赋值
  %=：先做取余运算，然后赋值
  >>=：先做右移位运算，然后赋值
  <<=：先做左移位运算，然后赋值
  &=：先做按位与运算，然后赋值
  |=：先做按位或运算，然后赋值
  !=：先做按位非运算，然后赋值
• 杂项运算符
  sizeof() 返回变量的大小。
  & 返回变量的地址。
  * 指向一个变量。 *a; 将指向一个变量。
  ?: 条件表达式 如果条件为真 ? 则值为 X : 否则值为 Y

3.2.3 成对的符号

[]：用于数组
{}：代码块或函数
()：if语句、函数声明、for循环、while循环等

3.3 数据类型

变量的数据类型决定了变量的存储方式。

• 基本类型
  整数类型和浮点类型
• void 类型
• 枚举类型
• 派生类型
  包括指针类型、数组类型、结构体类型、共用体类型和函数类型

3.3.1 整型

类型	字节数	范围
signed char	1	-128~127（也即 -2^7 ~ 2^7-1）
unsigned char	1	0~255 （也即 0 ~ 2^8）
char	1
signed short	2
unsigend short	2
short	2
singed int	4
unsigned int	4
int	4
singned long	4
unsigned long	4
long	4
singed long long	8
unsigned long long	8
long long	8

无标题.png

3.3.2 浮点类型

类型	字节大小	范围	精度
float	4		6位小数
double	8		15位小数
long double	16		18位小数

修饰词：unsigned（带符号的）和signed（不带符号的）

3.3.3 void空类型

• 函数声明前方填void：代表该函数没有返回值；
• 函数参数填void：表示该函数没有参数；
• 指针指向void，即void *，表示不指定指针指向的数据类型。

3.3.4 类型强转

强转前>	整形	浮点型	指针	结构体	共用体
整形	-	可以	可以（指针的地址值做为整形值）	错误
浮点型	可以	-	错误	错误
指针	可以（把整形值当做地址值）	错误	-	错误
结构体	错误	错误	不可（报错）	不同结构体不能互转（报错）
共用体	错误	错误	错误	错误

3.4 指针

3.4.1 指针的类型

• 指向数据的一维指针的类型由该数据的类型决定，例如指向char数据的指针类型为char *；
• 指向函数的一维指针的类型由该函数的返回值类型及其参数类型决定（个人理解）；

#include <stdio.h>
char fun(int a)
{
  return a;
}
char (*fun_p)(int);

int main(void)
{
    
    fun_p=&fun;
    printf("%d\n", fun_p(10));
    return 0;
}

• 指向一维指针的指针，是二维指针，类型由一维指针决定；
• 指向一维数组的指针，是二维指针；
• 指向void类型数据，如void *，表示该数据为空类型，可以强转为其他类型；
• 指针常量NULL，称为空指针，是一个在标准库中定义的值为零的常量。

3.4.2 指针的定义

指向基本变量

//定义的时候，可以是
int *p;
int (*p);
int*p;
int* p;
//但是不能是
(int*) p;

指向一维数组

#include <stdio.h>
int main(void)
{
    char a[10];
    a[1] = 10;
    char *p = NULL;
    p=a;
    printf("%d  %d", p[1], *(p+1));
    return 0;
}

指向二维数组

#include <stdio.h>
int main(void)
{
    char a[10][10];
    a[0][1] = 10;
    char (*p)[10];
    p=a;
    printf("%d  %d", p[0][1], (*p)[1]);
    return 0;
}

指向函数
指向函数数组
注：函数数组指针，指向的对象为多个函数组成的数组。

#include <stdio.h>
int fun1(int a)
{
    return a;
}
int fun2(int a)
{
    return -a;
}
int (*(fun_p[2]))(int);

int main(void)
{
    fun_p[0] = fun1;
    fun_p[1] = fun2;
    printf("%d  %d  %d  %d", fun_p[0](10), fun_p[1](10), (*fun_p)(10), (*(fun_p+ 1))(10));
    return 0;
}

指向数组函数
返回值为数组的函数？没有这样的而函数。但是可以返回一位数组的指针来实现功能。

3.4.3 指针数值

为地址值，一般为4个字节，得到指针值的方法

printf("%p", p);

3.4.4 指针的大小

参考：https://www.cnblogs.com/noble/p/4144167.html

3.5 数组

一组相同数据类型的变量的集合。

3.5.1 定义

使用 [] 符号，句法
<数据类型> <标识符>[<不小于0的整形数字>];
例子：

int var[10];

3.6 结构体、共用体和枚举

• 结构体：多个不同变量的集合，有点类似于高级语言的类，使用关键词 struct；
• 共用体：不同成员使用同一片内存，在同一时刻只有一个成员在使用，此时共用的内r存值服务于此成员。关键词unione。
• 枚举：赋予特定含义的整形数据。管关键词为enum。

3.6.1 结构体定义

#include <stdio.h>
//定义
typedef struct student{
    char *name;
    int num;
    double score;
}type_student;
//赋值
type_student st1={
    "xiaoming",
    53,
    80.2
};
//赋值2
type_student st2={
    .name = "xiaohong",
    .num = 20,
    .score = 91.2
};
int main(void)
{
    printf("%s  %d  %f\n", st1.name, st1.num, st1.score);
    printf("%s  %d  %f", st2.name, st2.num, st2.score);
    return 0;
}

3.6.2 共用体定义

#include <stdio.h>
//定义
union role
{
    int student_score;
    double teacher_salar;
};
typedef struct member{
    char *name;
    int age;
    union role r;
}type_member;
//赋值
type_member t1={
    "t1",
    29,
    .r.teacher_salar = 3400.9
};
type_member s1={
    "s1",
    17,
    .r.student_score = 80
};
int main(void)
{
    printf("%s  %d  %f\n", t1.name, t1.age, t1.r.teacher_salar);
    printf("%s  %d  %d", s1.name, s1.age, s1.r.student_score);
    return 0;
}

3.6.3 结构体位域

格式

//在结构体定义里面
type [member_name] : width ;

type 可以是int、unsigned int、signed int、char、unsigned char、signed char，不能是float、double等数据类型。

例子：

#include <stdio.h>
struct struct_t{
    int a:1;
    int c:10;
    int b;
};
int main(void)
{
    printf("%d", sizeof(struct struct_t));
    return 0;
}

3.6.4 结构体、共用体内存占用计算

#include <stdio.h>
int main(void)
{
    //数据类型对应占用的字节数
    printf("char\t%d\n", sizeof(char)); 
    printf("int\t%d\n", sizeof(int));
    printf("float\t%d\n", sizeof(float));
    printf("double\t%d\n", sizeof(double));
    int a;
    int b[3];
    char c;
    char *p;
    p = &c;
    //某个变量占用内存大小
    printf("a\t%d\n", sizeof(a));   
    //数组变量占用内存大小
    printf("b\t%d\n", sizeof(b));   
    //指针指向的内存大小
    printf("*p\t%d\n", sizeof(*p)); 
    //指针的大小
    printf("p\t%d\n", sizeof(p));   
    return 0;
}

结果

char    1
int     4
float   4
double  8
a       4
b       12
*p      1
p       4

共用体内存占用字节规则
若共用体某成员的占用字节数最大，那么这个字节数就是共用体的字节数。

#include <stdio.h>
union union_t{
    char a;
    int b;
    double c;   
};

int main(void)
{
    printf("%d\n", sizeof(union union_t));
    return 0;
}

结构体内存占用字节规则
（1）首先确定对齐字节：

• 普通数据类型的对齐字节是它本身占用的字节数；
• 数组的对其字节是数组基本元素的数据类型对应的字节数；
• 结构体真实是成员对齐字节最大的作为自己的对齐字节；指针的对齐字节是4字节（32位的编译器）。

（2）把对齐字节看做梯子的一个个等距横档，当成员累加到n时才超过横档，那么则把n放在这个横档作为起步，继续累加。
（3）例子：结构体有且其仅有成员a（2），b（2），c（4），d（8）这成员，后面的数字代表成员的对齐字节（成员也可能是嵌套的结构体），如果排序为abcd（即 2 + 2 + 4 + 8），那么计算过程为：

• 对其字节为8，档次为 8、16、24、32等；
• a + b + c + d = 16，刚刚超过8这个档位，那么d拿出来，以8这个档位开始累加；
• 8 + d = 16，结果在大于或等于16 的档位中，16这个档位最近，所以此结构体占用16字节。

如果排序为adbc（即 2 + 8 + 2 + 4），那么计算过程为：

• 对其字节为8，档次为 8、16、24、32等；
• a + d = 10，刚刚超过8这个档位，那么d拿出来，以8这个档位开始累加；
• 8 + d + c = 16，刚刚超过16这个档位，那么c拿出来，以16这个档位开始累加；
• 16 + c = 20，结果在大于或等于20 的档位中，24这个档位最近，所以此结构体占用24字节。

#include <stdio.h>
struct struct_t1{
    char a;
    char b;
    int c;
    double d;
};
struct struct_t2{
    char a;
    double d;
    char b;
    int c;
};
int main(void)
{
    printf("%d    %d\n", sizeof(struct struct_t1), sizeof(struct struct_t2));
    return 0;
}

3.6.5 结构体和共用体的互相嵌套

结论：两者可以互相嵌套

#include <stdio.h>
struct struct_t1{
    char a;
    char b;
    int c;
    double d;
};
struct struct_t2{
    char a;
    double d;
    char b;
    int c;
};
union union_t{
    struct struct_t1 t1;
    struct struct_t2 t2;
};
struct struct_t3{
    char a;
    union union_t b;
    char c;
};
int main(void)
{
    printf("%d\t%d\t%d\t%d\n", sizeof(struct struct_t1), 
    sizeof(struct struct_t2), sizeof(union union_t),
    sizeof(struct struct_t3));
    return 0;
}
//打印： 16      24      24      40

3.7 函数

//函数定义
return_type function_name( parameter list )
{
   body of the function
}
//函数声明
return_type function_name( parameter list )；
//函数调用
function_name( parameter value )

3.7.1 传参特点

• 函数参数在函数程序执行完之后会被销毁；
• 如果把指针当做传入的参数，那么可以修改指针指向的内容。

3.7.2 函数递归

例子1：递归实现数字排列组合（多层循环）

//递归实现数字排列组合
#include <stdio.h>
#define recourse_n 3
int para_list_t[] = {5, 4, 3};
int record[recourse_n];
int fun(int n, int *para_list)
{
    int i;
    if(n == 0)
    {
        for(i = 0; i < recourse_n; i ++)
        {
            if(i != 0)
            {
                printf("-");
            }
            printf("%d", record[i]);
        }       
        printf("\n");
        return 0;
    }
    else 
    {
        int ret;
        for(i = 0; i < *para_list; i++)
        {
            record[recourse_n - n] = *para_list - i;            
            ret = fun(n - 1, para_list + 1);
            if(ret == -1)
            {
                return -1;
            }
        }
    }
    return 0;
}

int main(void)
{
    fun(recourse_n, para_list_t);
    return 0;
}

3.7.3 回调函数

把另一个函数fun_other()的指针当做本函数fun()的参数，函数fun_other()当做回调函数。
作用：可以根据情况更改函数的接口。

3.8 流程控制语句

流程语句包括判断、选择、循环、跳转，相应的语句有 if、switch、for、do-while、goto语句

四、基础2

• 代码注释风格
• 关键字
• 变量
• 常量
• 宏
• 内存管理

4.1 代码注释风格

• 单行注释用//
• 多行注释用 /**/

4.2 关键字

（32个）

关键字	说明	关键字	说明
auto	声明自动变量	break	跳出当前循环
case	开关语句分支	char	声明字符型变量或函数返回值类型
const	定义常量，如果一个变量被 const 修饰，那么它的值就不能再被改变	continue	结束当前循环，开始下一轮循环
default	开关语句中的"其它"分支	do	循环语句的循环体
double	声明双精度浮点型变量或函数返回值类型	else	条件语句否定分支（与 if 连用）
enum	声明枚举类型	extern	声明变量或函数是在其它文件或本文件的其他位置定义
float	声明浮点型变量或函数返回值类型	for	一种循环语句
goto	无条件跳转语句	if	条件语句
int	声明整型变量或函数	long	声明长整型变量或函数返回值类型
register	声明寄存器变量	return	子程序返回语句（可以带参数，也可不带参数）
short	声明短整型变量或函数	signed	声明有符号类型变量或函数
sizeof	计算数据类型或变量长度（即所占字节数）	static	声明静态变量
struct	声明结构体类型	switch	用于开关语句
typedef	用以给数据类型取别名	unsigned	声明无符号类型变量或函数
union	声明共用体类型	void	声明函数无返回值或无参数，声明无类型指针
volatile	说明变量在程序执行中可被隐含地改变	while	循环语句的循环条件

C99和C11有新增的关键词。

4.2.1 个别关键字讲解

• volatile（不稳定的、易变的）
  参考：https://blog.csdn.net/tigerjibo/article/details/7427366
  由于访问寄存器要比访问内存单元快,所以编译器一般都会作减少存取内存的优化，但有可能会读取到错误的数据。使用volatile声明变量的时候，系统总是重新从它所在的内存读取数据，这就避免了“优化”带来的可能错误。
• register
  这个关键字请求编译器尽可能的将变量存在CPU内部寄存器中，而不是通过内存寻址访问，以提高效率（和volatile作用相反了）。
• auto
  auto修饰的变量，表示其作用域为当前函数或代码段，是局部变量。
• const
  关键字const用来定义只读变量，被const定义的变量它的值是不允许改变的。
  使用： int const var; 或者 const int var;

4.2.2 static和const使用

• 使用例子：

#include <stdio.h>
int main(void)
{   
    const int b1;
    int const b2;
    static int b3;
    int static b4;
    int const static c1;
    int static const c2;
    const int static c3;
    const static int c4;
    static int const c5;
    static const int c6;
    return 0;
}

• static 修饰局部变量：存于静态变量区，此时局部变量不会再函数执行完后销毁；
• static修饰全局变量：存于静态变量区，限定该变量只在本c文件中使用；
• static修饰函数：限定该函数只在本c文件中使用；
  -const修饰函数：修饰函数返回值有const属性；
• 被const 修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的健壮性；
  参考：https://blog.csdn.net/u010260855/article/details/23106099
• static const组合让变量或者函数有双重属性？？

4.3 变量

4.4 常量

4.4.1 整形常量

• 一般的数字默认是十进制；
• 0x或者0X开头，后面为数字或者是a、b、c、d、e、f的，代表十六进制数；
• 0开头，后面为数字0到7的表示为八进制，形如 0001 也是8进制数

4.4 宏

参考： https://blog.csdn.net/qq997843911/article/details/62042697

• 普通的宏，预处理中的代码替换，替换代码元素或者代码块，常用的有：
  （1）常量替代，让某个常量具有字面意义；
  （2）函数名、常量名替代，可用于函数封装、标识符别名的应用
  （3）替代重复使用的代码块（类似于内联（inline）函数），让代码更简洁
• 参数宏，在宏代表的代码块中，可以使用到参数值，有点类似于函数，但是更加灵活，例如

#define PRINT(x) printf("%d", x);

用于打印参数值；

• 宏的拼接和字符串化
  参数宏里的参数，用 #实现字符串化， 用 ## 实现拼接，例如:

#include <stdio.h>
#define COMMOND(x) {#x, x ## _commond}

int local_var = 0;
int print_commond(int num, void *para_list)
{
    printf("local_var=%d", local_var);
    return 0;
}
int set_commond(int num, void *para_list)
{
    local_var = *(int *)para_list;
}
struct struct_t{
    char *name;
    int (*fun)(int, void *);
};
struct struct_t cmd[]={
    COMMOND(set),
    COMMOND(print)
};
int main(void)
{
    int para = 100;
    int tmp;
    cmd[0].fun(0, (void *)(&para));
    cmd[1].fun(0, &tmp);
    return 0;
}

4.6 内存管理

参考：https://blog.csdn.net/u014630142/article/details/82428028

4.6.1 程序对内存的使用

分区	描述
堆区（stack）	动态内存使用（管道：先进先出）
栈区（heap）	对自动变量、函数形参的操作（杯子：先进后出）
静态存储区(static area)	静态变量、全局变量存储区域
代码区(code area)	存放可执行代码（程序代码指令、常量字符串等）

4.6.2 栈区的使用

4.6.2 堆区的使用（动态内存分配）

• 使用malloc和free函数进行动态内存的分配和销毁;
• 相关头文件 stdlib.h;
• 例子

int *p = (int *)malloc(8);  //分配8个字节的动态内存，并把地址赋给指针p

五、拓展

• 库函数列表
• 文件IO
• 字符串处理系列（string.h）
• 常用算法
• 链表

5.1 c标准库列表

参考：https://www.runoob.com/cprogramming/c-standard-library.html

• assert.h
• ctype.h
• errno.h
• float.h
• limits.h
• locale.h
• math.h
• setjmp.h
• signal.h
• stdarg.h
• stddef.h
• stdio.h
• stdlib.h
• string.h
• time.h

5.2 文件IO（在文件stdio.h中）

参考“linux基础学习3”：https://www.jianshu.com/p/82f2bf75c49c

FILE *fopen(const char *path, const char *mode);    //打开文件
int fclose(FILE *fp);   //关闭文件
int fgetc(FILE *stream);    //字符写入
int fputc(int c, FILE *stream); //字符读取
char *fgets(char *s, int size, FILE *stream);   //按行读取
int fputs(const char *s, FILE *stream);     //按行写入
char *fgets(char *s, int size, FILE *stream);   //按行写入

5.2.1 文件夹

示例

#include <stdio.h>
#include "dirent.h"  
#define  FilePath "./"
int main()  
{     
int i = 0;
int filesize = 0;  
    DIR *dir = NULL;  
    struct dirent *entry;  
  
    if((dir = opendir(FilePath))==NULL)  
    {  
        printf("opendir failed!");  
        return -1;  
    }
else  
    {  
         while(entry=readdir(dir))  
        {  
            i++;
            printf("filename%d = %s",i,entry->d_name);  //输出文件或者目录的名称
            printf("\tfiletype = %d\n",entry->d_type);  //输出文件类型   
        }  
  
         closedir(dir);    
    }  
    return 0;    
}  

• win7中文件夹文件类型为16，Android手机为4；win7中普通文件文件类型为0，Android手机为8
• 函数原型
  【待续】

5.3 字符串处理系列（string.h）

• 字符串前n个字符里搜索某个字符

void *memchr(const void *str, int c, size_t n)

• 字节比较 int memcmp(const void *str1, const void *str2, size_t n)
• 字节复制 void *memcpy(void *dest, const void *src, size_t n)
• 复制n个字节 void *memmove(void *dest, const void *src, size_t n)
• 设置n个字节的数值 void *memset(void *str, int c, size_t n)
• 字符串追加 char *strcat(char *dest, const char *src)
• 追加n个字节 char *strncat(char *dest, const char *src, size_t n)
• 在字符串里搜索某个字符 char *strchr(const char *str, int c)
• 字符串比较 int strcmp(const char *str1, const char *str2)
• 字符串前n个字符比较 int strncmp(const char *str1, const char *str2, size_t n)
• 根据LC_COLLATE 的位置设置比较字符串 int strcoll(const char *str1, const char *str2)
• 字符串复制 char *strcpy(char *dest, const char *src)
• 字符串前n个字符复制 char *strncpy(char *dest, const char *src, size_t n)
• 检索字符串 str1 开头连续有几个字符都不含字符串 str2 中的字符
  size_t strcspn(const char *str1, const char *str2)
• 搜索错误号 errnum，并返回一个指向错误消息字符串的指针
  char *strerror(int errnum)
• 计算字符串长度 size_t strlen(const char *str)
• 检测str1包含str2字符串的位置charchar *strpbrk(const char *str1, const char *str2)
• 字符串中搜索最后一次出现字符出现的位置
  charchar *strrchr(const char *str, int c)
• 检索字符串 str1 中第一个不在字符串 str2 中出现的字符下标
  size_t strspn(const char *str1, const char *str2)
• 在字符串 haystack 中查找第一次出现字符串 needle（不包含空结束字符）的位置
  char *strstr(const char *haystack, const char *needle)
• 分解字符串 str 为一组字符串，delim 为分隔符
  char *strtok(char *str, const char *delim)
• 根据程序当前的区域选项中的 LC_COLLATE 来转换字符串 src 的前 n 个字符，并把它们放置在字符串 dest 中
  size_t strxfrm(char *dest, const char *src, size_t n)

5.4 常用算法

5.4.1 几个排序的方法

（1）冒泡法
那一个数两两比较其他所有未进行冒泡的数，根据情况来决定是否交换位置。
复杂度来看，n个数的排序有 0.5n^2 次比较，以及 0~0.5n^2 次范围的交换动作。
例子：

//冒泡排序从小到大
#include <stdio.h>
int num_list[]={
    1,7,8,70,56,32,77
};
#define member_n 7
void show(void)
{
    int i;
    for(i = 0; i < member_n; i ++)
    {
        printf("%d ", num_list[i]);
    }
    printf("\n");
}
int main()  
{     
    int i,j;
    show();
    for(i = 0; i < member_n - 1; i++)
    {
        for(j = i + 1; j < member_n; j++)
        {
            if(num_list[i] > num_list[j])
            {
                num_list[i] ^=  num_list[j];
                num_list[j] ^=  num_list[i];
                num_list[i] ^=  num_list[j];
            }   
        }
    }
    show();
    return 0;    
}  

（2）选择法
选一个数，与所有数比较，然后得出最小的那位数的索引，与序号为0的数交换，当做第一个数；然后按同样的方法取得其他数的最小数，与序号为1的数交换；以此类推。
复杂度来看，n个数有 0.5*n^2 次比较， 以及0~n次范围的数字交换。
例子：

//选择排序，从小到大
#include <stdio.h>
int num_list[]={
    1,7,8,70,56,32,77,100,4,32
};
#define member_n 10
void show(void)
{
    int i;
    for(i = 0; i < member_n; i ++)
    {
        printf("%d ", num_list[i]);
    }
    printf("\n");
}
//选出最小的数，得到它的序号，然后和前面的未排序的数
//进行交换
int main()  
{     
    int i,j;
    int min_idx;
    show();
    for(i = 0; i < member_n - 1; i++)
    {
        min_idx = i;
        for(j = i + 1; j < member_n; j++)
        {
            if(num_list[min_idx] > num_list[j])
            {
                min_idx = j;
            }   
        }
        if(i != min_idx)
        {
            num_list[i] ^= num_list[min_idx];
            num_list[min_idx] ^= num_list[i];
            num_list[i] ^= num_list[min_idx];
        }
        
    }
    show();
    return 0;    
}  

（3）插入排序
先把部分排序好，后面的数一个个插入到合适的位置。
判断次数和交换次数一样，n个数排列的话，在 n-1 ~ 0.5*n^2 之间

//插入排序，从小到大
#include <stdio.h>
int num_list[]={
    132,7,8,70,56,32,77,100,4,32
};
#define member_n 10
void show(void)
{
    int i;
    for(i = 0; i < member_n; i ++)
    {
        printf("%d ", num_list[i]);
    }
    printf("\n");
}
int main()  
{     
    int i,j;
    show();
    for(i = 0; i < member_n - 1; i++)
    {
        for(j = i + 1; num_list[j] < num_list[j - 1]; j--)
        {
            if(j == 0)break;
            num_list[j] ^= num_list[j - 1];
            num_list[j - 1] ^= num_list[j];
            num_list[j] ^= num_list[j - 1];
        }       
    }
    show();
    return 0;    
}  

（4）希尔排序
插入排序的改进版。
刚开始从 1/2 处序号开始插入排序，依次为 1/4 、1/8 等序号处插入排序，直到开始的序号为0

//参考菜鸟教程
void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

（5）（6）参考： https://www.runoob.com/cprogramming/c-sort-algorithm.html
（5）归并排序

（6）快速排序
在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

5.5 链表

参见 https://git.lug.ustc.edu.cn/bigbang/code/-/tree/master/%E5%B7%A5%E7%A8%8B/%E9%93%BE%E8%A1%A8

包括 单向非循环链表、单向循环链表、双向非循环链表、双向循环链表

六、应用例子

6.1 字母排列组合

//遍历26个字母的排类组合
/*
例如26个字母，任选5个字母，进行排列组合，结果有26^5种可能（字母可以
重复）。那么遍历数字0到26^5 - 1，把数字转换为26进制数，显然5位数即可
表示完全，每个位置上的数，组成一个序列，例如
100=0*26^4+0*26^3+0*26^2+3*26^1+22*26^0，换言之是0、0、0、3、22，
于是对应字母序号得出aaadw
*/
#include <stdio.h>
char letter[]={
    'a','b','c','d','e','f','g','h','i','j','k','l','m',
    'n','o','p','q','r','s','t','u','v','w','x','y','z'
};

int mypow(int a, int b)
{
    int ret = 1;
    int i;
    for(i = 0; i < b; i++)
    {
        ret *= a;   
    }
    return ret;
}
int getQuenue(int num, int basic, int shift_num, int *result)
{
    int i;
    for(i = 0; i <= shift_num - 1; i++)
    {
        *(result + i) = (num % mypow(basic, shift_num - i)) / mypow(basic, shift_num - i - 1);
    }
    return 0;
}
int main(void)
{   
    int i, j;
    int basic = 26, shift_num = 5;
    int result_t[shift_num];
    int cnt;
    cnt = 0;
    for(i = 0; i < mypow(basic, shift_num); i++)
    {
        getQuenue(i, basic, shift_num, result_t);
        for(j = 0; j < shift_num; j++)
        {
            printf("%c", letter[result_t[j]]);          
        }
        printf("  ");
        cnt++;
        if(cnt >= 15)
        {
            cnt = 0;
            printf("\n");   
        }       
    }   
    return 0;
}