[C++知识库]C/C++

C语言简介

? C语言诞生于1970年~1973年，在 肯·汤普逊 和 丹尼斯·里奇 的编写下完成，归属于美国贝尔实验室。

? C语言专门用于编写操作系统而发明的编程语言，所有天生适合对硬件编程，也以运行速度快而著称，也非常适合实现数据结构和算法。

? 由于出现时间过早，有很多缺陷，已经存在着很多的陷阱，但是我们的前辈给我们总结了一些避免陷阱的经验教训 《c陷阱与缺陷》

? C语言的语法很自由，但是也意味着危险。

? 自由源于自律！

? C89语法标准，默认是gcc语法编译器的语法标准

? C99语法标准，对C语言的扩展和增强 Ubuntu 16.04 默认C99 (-std=gnu99 指定为C99语法标准)

? C11语法标准，全新的升级

第一个C语言程序

程序员所写的代码不是标准C代码，需要一段程序把它翻译成标准C代码，负责翻译的程序叫做预处理器，翻译的过程叫预处理，需要被翻译的代码佳作预处理指令，以#开头的代码叫做预处理指令

gcc E hello.c 只执行hello.c 的预处理

#include 功能是导入头文件

? #include <xxx.h>

? <> 从系统指定路径查找头文件并导入

? #include “xxx.h”

? “” 从当前的工作路径找头文件，如果找不到再从系统指定路径找并导入

#include<stdio.h>
int main(){
    printf("Hello World!\n");
    return 0;
}

? 1. vim xxx.c 创建.c源文件

? 2. 编译代码，并保存退出

? 3. gcc xxx.c 编译.c源文件，成功会得到a.out文件

		4.	./a.out	运行可执行文件

注意： gcc xxx.c && ./a.out 可以编译并执行

stdio.h 标准输入输出文件

? 头文件：以.h结尾，里面存储的是辅助性代码，绝大多数都是函数的说明

main函数：

? C语言中以函数为单位管理代码，一个函数就是具有某项功能的代码段

? main函数是程序的执行入口，必须有且只能有一个

? int 是一个数据类型，表示main函数的执行结果是个整数。

? return 功能有两个：1.返回一个结果给函数的调用者

? 2.结束函数进程

? main函数的调用者是操作系统，它的返回值给了操作系统。* vim echo 程序 查询操作系统接收的return返回值

? 正数 出现异常

? 0 一切正常

? 负数 出现错误

? printf/scanf 是标准库中的函数，负责输出、输入数据

? printf（“想要输出的内容”);

? 转义字符：键盘上一些无法直接打印显示的符号，用一些特殊的字符组合来表示，这种特殊的字符组合称为转义字符， \n 换行

? \r 回到行首

? \t 制表符，相当于Tab键

? \b 退格键

? \a 响铃

? \\ 表示一个 \

? %% 表示一个%

? C语言中以分号作为一行代码的结束，使用大括号划分区域

C语言编译器gcc

? 负责把人能看懂地记录着代码的文件，翻译成计算机能看得懂的二进制文件，由预处理器，编译器，链接器组成。

? gcc是由GNU社区为了编译Linux内核代码而开发的一款免费的编译器

? gcc编译器常用编译参数：

? -E 只显示预处理的结果到终端

? -std=gnu99 设置C99语法标准

? -c 只编译不链接

? -o 指定编译结果名 -oname / -o name

? -S 生成汇编代码

? -I（大写 i） 指定头文件的加载路径 -I 加载路径

? -Wall 尽可能多地产生警告

? -Werror 将警告当错误处理

? -l(小写L) 指定要加载（使用）的代码库 -lm(加载math.h库)

C代码变成可执行文件的详细过程

1. 预处理 把源文件翻译成预处理文件
   gcc -E code.c 显示预处理结果到终端
   gcc -E code.c -o code.i 生成以.i结尾的预处理文件
2. 编译 把预处理文件翻译成汇编文件
   gcc -S code.i 生成以.s结尾的汇编文件
3. 汇编 把汇编文件翻译成二进制的目标文件
   gcc -c code.s 生成以.o结尾的目标文件
4. 链接 把若干个目标文件合并成一个可执行文件
   gcc a.o b.o c.o ···· 默认生成一个a.out可执行文件

C语言的文件类型

? .c 源文件

? .h 头文件

? .h.gch 头文件的编译结果文件，它会被优先使用

? .i 预处理文件

? .s 汇编文件

? .o 目标文件

? .a 静态库文件

? .so 共享库文件

存储空间的单位

? Bit（位） 比特 一个二进制位，只能存储0或1，计算机中存储数据的最小单位

? byte 字节 八个二进制位，计算机存储器描述存储容量的基本单位

? KB 1024字节

? MB 1024KB

? GB 1024MB

? TB 1024GB

数据类型

? 为什么要对数据进行分类？

1. ? 现实中的数据本身就自带类别属性

2. 对数据进行分类可以节约存储空间，提升运行速度

   C语言中数据分类为两大类：自建类和内建类

   自建类：程序员自己设计的类型

   内建类：C语言自带的类型

   注意：运算符 sizeof 可以计算类型，变量的字节数

      整型：
   
      	signed		有符号
   
      		signed char					1Btye				-128~127
   
      		signed short					2 Btye				-32768~32767
   
      		signed int					4 Btye				+-20亿
   
      		signed long					4/8 Btye				+- 9开头的19位整数
   
      		signed long long				8 Btye
   
      	unsigned	无符号
   
      		unsigned char					1Btye				0~255
   
      		unsigned short					2 Btye				0~65535
   
      		unsigned int					4 Btye				0~40亿
   
      		unsigned long					4/8 Btye				0~1开头的20位整数
   
      		unsigned long long				8 Btye				
   

   signed不加就代表了加！由于定义无符号整型时比较麻烦，C标准库中把一些类型重定义成一些新的简单的类型名：（需要导入同文件：<stdint.h>）

   uint8_t uint16_t uint32_t uint64_t

   int8_t int16_t int32_t int64_t

      浮点型：	有小数部分的类型
   
      		float			单精度		4Btye
   
      		double		双精度		8Btye
   
      		long double				12Btye/16Btye
   

   注意：小数点后六位有效！编程时，尽量使用整性。

   注意：采用一定的算法对真实的浮点数型到二级制数据进行转化，

   这个过程比存储，读取整数要慢得多。

      模拟型：
   
      		字符型：	char
   
      				字符就是符号或者图案，在内存中存储的依然是整数，需要显示出字符时，
   
      				会根据ASCII表中对应的关系显示出对应的字符或者图案
   
      		‘0’	~	48		‘A’	~	65		‘a'	~	97		'\0'	~	空字符（NULL或空格）
   
      		布尔型：	bool
   
      				先有了C语言后有的bool类型，所以C语言中不可能有真正的布尔类型，
   
      				在头文件stdbool.h 中对布尔类型进行了模拟
   
      				bool			TRUE			FALSE
   

?

 # 变量和常亮

 		什么是变量：程序运行期间的数值可以发生变化的佳作变量，相当于一个存储数据的盒子

 		定义：	类型名	变量名；

 						int		number;

 						变量名取名规则：

 						1.由字母，数字，下划线组合

 						2.不能以数字开头

 						3.不能与C语言的32个关键字重名

 						4.见名知意（功能，类型，作用范围）

 		使用：

 				赋值：	变量名	=	常量；

 				参与运算：		变量名嵌入表达式

  C语言中变量的初始值是随机的，为了安全起见，一般在定义时初始化为0。

 关键字：

?

 char	short	int	long	void	float	double

 struct	union	enum	sizeof

 auto	const	static	volatile	register	

 typedef	extern	signed

 unsigned

 if	else	switch	case	default

 for	do	while

 break	continue	goto	

?

 变量的输入输出：

 		int	printf(const	char	*format,	· · ·  );

 		功能：输出数据

 		format：”双引号包含的提示信息	+	占位符“

 		· · · ：变量名列表

 		printf返回值：输出字符的个数

 	类型占位符：C语言中通过类型占位符传递变量的类型

	signed：%hhd	%hd	%d	%ld	%lld

 unsigned：%hhu	%hu	%u	%lu	%llu

		float：%f

	double：%lf

 long double：%LF

 字符型  char：%c	

		int	scanf(const	char	*format, · · · )；

		功能：输入数据

		format：“双引号包含占位符”

		· · · ：	变量地址列表

		scanf返回值：成功输出的变量的个数

	scanf需要提供变量的地址(	&变量名	==	地址符	)

练习1：定义各种类型的变量并初始化，使用printf显示它们各自的值

练习2：定义各种类型的变量并初始化为0，使用scanf输入，使用printf显示

?

 #include<stdio.h>
 #include<stdint.h>
 int main(){
     uint16_t num = 0;
     printf("请输入num的值：");
     scanf("%hu",&num);
     printf("num = %hu\n",num);
     return 0;
 }
 ```

?

? 什么是常量：程序运行期间数值不能改变的叫做常量

? 100 默认int类型

? 100l long

? 100ll long long

? 100u unsigned int

? 100lu unsigned long

? 100llu unsigned long long

? 3.14 默认double

? 3.14f float

? 3.14l long double

? 格式化输入输出

? %nd 显示n个字符宽度，不够则补充空格，右对齐

? %-nd 显示n个字符宽度，不够则补充空格，左对齐

? %0nd 显示n个字符宽度，不够则补充0，右对齐

? %n.mf 显示n个字符宽度（小数点也占一位），不够则补充则空格，m表示小数点后的位数（四舍五入），右对齐

? %g 不显示小数点后，多于的0

? 运算符

? 自变运算符 ++、-- 使变量的值自动加一和减一

? 前自变：++num/–num 立即生效

? 后自变：num++/num-- 下一行语句才有效

? 注意：不要再一行内，多次使用自变运算

#include<stdio.h>
int mainf(){
    int num = 10;
    printf("num = %d\n",++num);
    printf("num = %d\n",num++);
    return 0;
}

? 算术运算符：+ - * / %

? 整数/整数 结果还是整数，无小数点，只保留整数部分

? 整数%整数 取余

? / % 除数不能为0，否则就会浮点数例外，（核心已转存），这是个运行报错，一旦产生程序立即停止，后面不在执行

? 关系运算符：> < >= <= == !=

? 比较后得到结果为0（不成立）或1（成立），比较结果可以继续参与后续的计算

? int n = -100;

? if（10 < n <100） 恒成立

? 注意： == 建议常量放左边

? 逻辑运算符：&& || ！

? 先把运算的对象转化成逻辑值，0转化为假，非0转化为真

? A && B 一假即假

? A || B 一真即真

? ！A 求反

? && 和 || 运算符的短路特性：

	int num = 10;
	if( 100 < num && num++ ){	printf("Yes\n");}
	printf("%d\n",num);
//	当左边的值以及确定了结果，则右边不执行
    int n = 0;
	if( (100 > num) || (num++) && (n=10) ){	parint("ES");}
	printf("%d\n",n);

? 三目运算符：判断A的值是否为真，为真则执行B，否则就执行C A ? B : C ;

? 赋值运算符

? a = 10; a += 10; a -= 10; a *= 10; a /= 10; a %= 10;

? 位运算符： & | ~ ^ << >>

分支语言

 1. if(表达式){	表达式为真，则执行代码，否则不执行	}

 2. if(表达式){
    	表达式为真执行
    }else{
    	表达式为假执行
    }

 3. if(表达式1){
       表达式1真执行
    }else if(表达式2){
       表达式2真执行
       ······
    }else{
       如果以上都为假，则执行
    }

练习：输入三个整数，从小到大显示

练习：输入一个年份，判断是否是瑞年

练习：输入一个年份和月份，判断该月有多少天

练习：输入一个成绩判断等级

90~100 A

80~89 B

70~79 C

60~69 D

0~59 E

other 成绩有误

类型转换

? 只有相同类型的数据才能运算，如果类型不相同的数据需要先转换相同类型后再进行计算。

? 自动类型转换：

? 转换规则：以不丢失数据为基础，可以适当牺牲一些空间

? 1.字节少的，向字节多的转

? 2.有符号的，向无符号的转

? 3.整数，向浮点型转化

? 注意： char与short如果与不同类型的数据运算时，会优先提升为int类型后参与运算

? sizeof( 不计算内容，以大的字节数为基准！ )

? 强制类型转换：

? (新类型名)数据;

? 这种方式有可能会丢失数据，谨慎使用

switch分支语句

switch(n){	//	n可以是常量，变量，表达式（表达式的结果必须是整数常量，不能是浮点数类型）。
    case val:	//	val必须数常量,如果val==n则打开开关
        · · ·
        break;	//	关闭开关。
    case val2:
    default:	//	无开关打开，则执行！并且，放在任意位置都可以最后打开。
}

? case 1 ··· 3：可以表示[a,b]的范围，但是只有在GNU编译器才支持该语法，不建议使用。

练习：输入一个月份，判断它是什么季节

（春：123月份，夏：456月份，秋：789月份，冬：10,11,12月份）

练习：输入一个月份，判断该月有多少天。（不考虑闰年）

for循环语句

? 循环就是一种让代码反复执行的方法，到达你想要效果for循环是一种非常灵活，变样多样且危险的循环

//	for循环，一般使用一个变量来引导的执行，该变量叫做循环变量
for([1];[2];[3]){
	[4]
}
/*	[1]给循环变量初始值，C99以上标准才可以在此处定义变量	std:gun99
	[2]判断循环变量是否到达边界，进入循环变量
	[4]被反复执行的代码，称之为循环体
	[3]改变循环变量，防止出现死循环，一般对循环进行自加，自减
*/

? 大括号建议使用：

? 1.建议上下对齐

? 2.如果循环体中，只有一行代码，大括号可以省略

? 但是不利于扩展，一般的商业代码都要求大括号不能省略

//	for循环的各种写法
for(;;)
{
    //	死循环
}

int i = 0;
for(;i<10;i++){}

for(int i = 0 ;; i ++ ){
    if( i > 10 ) break;
}

for(int i = 0 ; i < 10 ;){
    · · ·
    i++;
}

练习：计算出所有的水仙花数（abc=a^3+b3+c^3)

练习：输入一个正整数，判断是否是素数

while循环语句

while(表达式)
{
    //	循环体
}
//	当表单式为真执行循环体，直到表达式为假，结束循环
do{
    //	循环体
}while(表达式);
//	先执行循环体，再判断循环条件，该循环至少执行一次

? 当明确直到循环次数时，用for循环

? while循环专门负责不知道循环次数

循环嵌套

? 循环里嵌套循环，外成循环执行一次，内层循环执行n次

练习：输入一个数，判断是否是回文数

练习：模拟输入六位密码，输入的密码正确显示“登录成功”，输入错误提示还有几次机会，并输入密码，最多错三次，否则显示“账号已锁定，请联系柜台”，并结束程序

练习：打印九九乘法表

练习：白钱白鸡问题

练习：计算出100~1000之间所有素数

跳转语句

1. goto
   可以在函数内，任意跳转。

   标签名：
       ···
       goto 标签名
   /*		可能会破坏已经设计好的分支或者循环结构，因此绝大多数公司禁止使用goto
       	但是在驱动编程时特别时候处理异常
   */
       练习：计算N的的阶乘，不能使用循环语句实现
       	int s = 1;
   lx:		
   		s *= N--;
   		if( N )
           {
               goto lx;
           }
   		printf("%d\n",s);
   

2. break

   1.	在switch中关闭case执行开关
   2.	跳出循环，只能跳一层循环
   

3. continue

   结束本次循环，进入下一次循环
   

4. return

   1.	结束函数的执行，返回到调用位置
   2.	返回一个数据给函数的调用者
   

数组

? 什么是数组：变量的组合，是一种批量定义类型相同的变量的方式

//	定义：	变量名	数组名[数量];
	int array[100];
//	使用方式：数组名[下标号];（下标号：从零开始。范围：[0,n-1]）
/*	数组遍历：与for循环配合，使用循环变量当做数组的下标
	数组的初始化：		int array[100] = {0,···};
	1.因为数组的值默认是随机的，所有一般都会进行初始化。
	2.初始化的数据过多，编译器会产生警告并把多出的数据丢弃
	3.初始化的数据不够,编译器会默认在末尾补0零
	4.   
	5.这种初始化语法只能在定义中使用，并且只能逐个赋值，不能整体赋值
	6.初始化时，数组的数量可以省略，编译器会自动统计初始化中数据的个数，并且告诉数据确认数组的数量，一旦数组数量确定，后期无法更改
	sizeof(array)/sizeof(array[0]) == 数组的成员个数
	sizeof(array) == 数组的字节长度
	sizeof(array[0]) == 数组的成员的字节数
*/

练习：定义一个长度为10的数组并进行初始化，计算出最大值，最小值和平均值

练习：定义一个长度为10的数组并初始化，进行升序排列

数组越界

为了程序的编译，运行效率，编译器不去检查数组的下表越界

? 数组越界的后果：

? 1.段错误

? 2.一些正常

? 3.脏数据

? 在使用数组的过程中，要注意不要越界

练习4：定义一个长度为10的数据并初始化，找出数组中第二大的数，不允许排序

#include <stdio.h>
int main()
{
    int array[10] = {-1,23,9,-32,-93,345,76,43,26,10};
    int max_1 = array[0] > array[1] ? array[0] : array[1];
    int max_2 = array[0] < array[1] ? array[0] : array[1];
    for(int i = 1 ; i < 10 ; i ++ )
    {
        if( max_1 < array[i] )
        {
            max_2 = max_1;
            max_1 = array[i];
        }
        else if( max_2 < array[i] )
        {
            max_2 = array[i];
        }
    }
}

二维数组

? 一维数组相当于把变量排成一排，通过编号访问

? 二维数组相当于把变量排成一个矩阵，通过行号和列号访问定义

? 定义： 类型名 数组名[行数][列数]

? 使用： 数组名[行下标][列下标]

? 遍历： 需要于双重循环配合使用，一般外层循环负责遍历行，内层循环负责遍历列

二维数组初始化：

? 类型名 数组名[行数][列数] = {{第一行},{第二行}, · · · · · ,{} };

练习：定义一个5*5的二维数组，找出数组中最大的值的坐标

变长数组

? 定义数组时使用变量作为数组的长度，在代码编译期间数据的长度是不确定的，当运行到数组的定义语句时数据到长度才最终确定下来，这种数组称为变长数组

? 优点：可以根据实际情况确定数组大小，以此节约内存空间

? 缺点：不能进行初始化，因为初始化发生在程序编译时

练习：输入两个整数n,m(1<=n,m<=6)，然后输入数组array[m][n]，各元素的值，然后统计每个元素之和，统计非零元素的个数，计算出所有元素的平均值，大于平均值的元素个数

#include <stdio.h>
int main(){
    int m = 0 , n = 0;
    printf("请输入m,n的值")；
    scanf("%d%d",&m,&n);
    int arr[m][n];
    double sum = 0 , avg = 0;
    int nozero_count = 0 , more_count = 0;
    
    printf("请输入各个元素的数据：");
    for(int i = 0 ; i < m ; i ++ )
    {
        for(int j = 0 ; j < n ; j ++ )
        {
            scanf("%d",&arr[i][j]);
            sum += arr[i][j];
            if( arr[i][j] )
            {
                nozero_count ++;
            }
        }
        avg = sum / (n*m);
        for(int i = 0 ; i < m ; i ++ )
        {
            for(int j = 0 ; j < n ; j ++ )
            {
                if( arr[i][j] > avg )
                {
                    more_count ++ ;
                }
            }
        }
    }
    printf("sum=%lf\n",sum);
    printf("nozero_count=%d\n",nozero_count);
    printf("avg=%lf\n",avg);
    printf("more_count"more_count);
    return 0;
}

练习：定义一个5*5的二维数组并初始化，找出最小值的坐标，并计算出最小值一圈数据之和

#include <stdio.h>
int main(){
    int arr[5][5] = {
        {1,2,3,4,5},
        {6,7,8,9,10}.
        {5,6,7,8,9},
        {4,1,4,7,4},
        {7,1,5,3,1}
    };
    int min = arr[0][0] , min_x = 0 , min_y = 0 ;
    for(int i = 0 ; i < 5 ; i ++ )
    {
        for(int j = 0 ; j < 5 ; j ++ )
        {
            if( min < arr[i][j] )
            {
                min = arr[i][j];
                min_x = i;
                min_y = y;
            }
        }
    }
    
    int sum = 0;
    for(int x = min_x-1 ; x <= min_x+1 ; x ++ )
    {
        for(int y = min_x-1 ; y <= min_y+1 ; y ++ )
        {
            if( 0 <= x && x <= 4 && 0 <= y && y <= 4 )
            {
                sum += arr[x][y];
            }
        }
    }
    printf("sum = %d\n",sum - min);
    return 0;
}

练习：输入N，显示N层杨辉三角

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1

练习：输入一个日期（yyyy-mm-dd），计算该日期距离1年1月1日过了多少天

走迷宫代码

? 数据分析：

? 1.定义二维字符数组作为迷宫地图

? 2.定义变量记录角色的位置 x y

? 逻辑分析：

? 一.进入死循环：

? 1.显示地图，遍历二维数组

? 2.等待获取方向键并处理

? 判读前方是不是路（空格字符）

? 如果是：

? 1.把旧位置变成空格字符

? 2.把新位置变成"@"

? 3.更新角色位置坐标 x y

? 3.判断是否到达出口

? 如果是：程序结束

#include <stdio.h>
#include <stdlib.h>	//	系统命令头文件
#include <getch.h>	//	自定义头文件
#include <time.h>	//	

int main(){
    char maze[10][10] = {
        {'#','#','#','#','#','#','#','#','#','#'},
        {'#',' ','#',' ','#',' ',' ',' ',' ','#'},
        {'#','@','#',' ','#',' ','#','#',' ','#'},
        {'#',' ',' ',' ','#',' ','#','#',' ','#'},
        {'#',' ','#','#','#',' ','#','#',' ','#'},
        {'#',' ','#','#','#',' ',' ','#',' ','#'},
        {'#',' ','#','#','#',' ','#',' ',' ','#'},
        {'#',' ','#','#','#',' ','#','#',' ','#'},
        {'#',' ',' ',' ',' ',' ','#','#',' ',' '},
        {'#','#','#','#','#','#','#','#','#','#'}
    };
    //	记录角色初始位置坐标：man_x,man_y;
    char man_x = 2, man_y = 1;
    time_t start_time = time(NULL);
    for(;;)
    {
        //	判断是否到达出口
        if( man_y == 9 )
        {
            printf("到达出口，游戏结束！")
            return 0;
        }
        //	清理屏幕
        system("clear");
        //	显示地图
        for(int i = 0 ; i < 10 ; i ++ )
        {
            for(int j = 0 ; j < 10 ; j ++ )
            {
                printf("%c ",maze[i][j]);
            }
            printf("\n");
        }
        
        //	获取反向键处理
        switch( getch() )
        {
            case 183:	case 'w':	//	上
                if( ' ' == maze[man_x-1][man_y] )
                {
                    maze[man_x][man_y] = ' ';
                    maze[--man_x][man_y] = '@';
                }
                break;
            case 184:	case 's':	//	下
                if( ' ' == maze[man_x+1][man_y] )
                {
                    maze[man_x][man_y] = ' ';
                    maze[++man_x][man_y] = '@';
                }
                break;
            case 186:	case 'a':	//	左
                if( ' ' == maze[man_x][man_y-1] )
                {
                    maze[man_x][man_y] = ' ';
                    maze[man_x][--man_y] = '@';
                }
                break;
            case 185:	case 'd':	//	右
                if( ' ' == maze[man_x][man_y+1] )
                {
                    maze[man_x][man_y] = ' ';
                    maze[man_x][++man_y] = '@';
                }
                break;
        }
            if( 8 == man_x && 9 == man_y )
    		{
        		printf("游戏胜利，过了%lu秒！\n",time(NULL)-start_time);
        		return 0;
   		 	}
    }

    return 0;
}

推箱子

? 数据分析：

? 1.确定数值与字符的对应关系

? 0 ‘ ’

? 1 ‘@’

? 2 ‘#’

? 3 ‘$’

? 4 ‘o’

? 5 ‘@’

? 7 ‘$’

? 2.定义8*8的整数地图并初始化

? 3.定义记录角色位置的变量 x y

? 4.定义记录步数的变量

? 逻辑分析：

? 一.进入死循环

? 1.清理屏幕，显示地图

? 2.判断是否游戏胜利

? 3.获取方向键并处理

? 1.前方是路、目标点

? 2.前方是箱子，箱子的前方是路或目标点

进制转换

? 为什么要使用二进制，八进制，十进制，十六进制？

? 1.因为现在的CPU只能识别高低电平，只能对二进制的数据进行计算

? 2.虽然二进制可以直接被CPU识别计算，但是不方便书写，记录，把二进制的数据转换成八进制是为了方便记录到文档

? 3.由于CPU的位数的不断发展不断增加，由于8位逐渐发展到现在的64位，因此八进制就不能满足需求了，所以发展出了十六进制，但是由于历史原因八进制不能完全淘汰

十进制转N进制：

? 1.对十进制数进行求余数，然后继续对商求余，直到商为零，倒取余数，得到结果

? 2.求权法：用数值去减 最高位的权值*数值 （不能出现负数），直到把数据减完

练习：输入一个正整数m，输入一个n（n>=2），显示m的n进制数，超过10的用字母表示 10->A

二进制转十进制：每位加权求和

二进制位转八进制位：每三位二进制位转换为一位八进制位

二进制转十六进制：每四位对应一位十六进制数

在C语言中，以0开头的数是八进制数，以0x开头的数是十六进制数；

? %o 以八进制显示

? %x 以十六进制显示

? %#o %#x 可以把对应的前缀显示出来

原码，反码，补码

? 原码：数据的二进制

? 反码：正数反码就是它的原码

? 负数的反码就是它原码的，除符号位外，其它按位求反

? 补码：正数补码就是它们的原码

? 负数的补码是它的反码+1

内存中所有数据的存储都是以他的补码的形式存储

1.负数转换为二进制

2.符号位不变，其余按位求反，得到反码

3.反码+1得到补码

补码转数据：

? 1.先看是否有符号位

			- 如果是无符号的，直接转成原码
			- 如果是有符号的，且最高位是零，也就直接转换成十进制，最高位不动

• 有符号且最高位是1：
  • 补码-1得到反码
  • 符号位不变，其它位，按位求反得到原码
    - 原码转化成十进制

位运算符

? A & B 按位与

? A | B 按位或

? ~A 按位求反 // 在位运算中优先级最高

? A ^ B 按位异或 相同为0，相异为1

? A << n 把A的补码向左移动n位 左边丢弃右面补0

? A >> N 把A的补码右移N位 右边丢弃，左边补符号位

（左移动，相当于乘2；右移动，相当于除2；

练习：输入一个整数，把它的4~7位设置为1010，其它位不能变；

优先级：单目 算数 位 关系 逻辑 三目 赋值

表达式中出现了位运算符，转换成二进制计算

函数

? 一段具有某项功能的代码，是C语言中管理代码的最小单位

? 把代码封装成一个个函数，可以方便管理和调用代码

• 函数的分类：

  • 标准库函数

    • 由C语言标准委员会为C语言以函数的形式提供的一些基础功能，被封装在libc.so库中，使用时需要包含对应的头文件，通过 对应的函数名（实参）方式即可调用标准库中的函数

    • 随机数：

      #include <stdlib.h>
      #include <time.h>
      srand( time(NULL) );
      int num = rand();
      

      
      > ?	练习：	获取10个[100,1000]之间的随机数，循环不超过10次
      >
      > ?					rand() % 901+100
      >
      > ?	练习：	红球6组，每组从1-33中抽取一个，六个相互不重复。
      >
      > ?					然后篮球是从1-16中抽取一个数字
      >
    > ?					随机产生一组	双色球号码
    

  • 系统函数

  • 是操作系统以函数的接口形式提供的一系列功能，但是它不是真正意义上的函数

• 内存管理，文件管理，文件IO，信号处理，进程管理，进程通信，线程管理，线程同步，网络通信

  • 第三方库函数

    • 由第三方提供的 开源或者收费的代码库
    • MD5 加密算法

  • Json 序列化，反序列化

  • Xml 配置文件解析算法

  • 自定义函数

    • 为了个更好地管理代码，减少代码冗余把代码封装成函数形式

      • 函数申明：

        • 函数申明，为了告诉其他代码该函数的调用格式

        • 返回值类型 函数名（类型1 形式参数1，类型2 形式参数，· · · ）；

          1.C语言中函数名一般全小写，下划线分隔

          2.如果返回值不需要，则写void

          3.如果不需要形式参数，建议也需要写void

      4.就算形式参数类型名相同，也要每个都加类型名

      • 函数定义：函数的实现代码

        • 返回值类型 函数名（类型1 形式参数1，类型2 形式参数，· · · ）{

          ? // 函数体

          ? return 返回值类型;

          }

      • 函数调用

        • 函数名(实参)

练习：实现一个函数，判断是否是素数，调用它显示100~1000以内所有的素数

练习：输入两个日期(yyyy-mm-dd)，计算两个日期间相隔多少天

练习：实现一个函数，判断一个整数是否是回文数，调用它显示1亿~10亿的所有有回文数

练习：输入一个数，显示它的补码

#include <stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    char bits[32] = {};
    for(int i = 0 ; i < 32 ; i ++ )
    {
        bits[i] = n >> i & 1;
    }
    for(int i = 31 ; i >= 0 ; i -- )
    {
        printf("%hhd",bits[i]);
    }
    return 0;
}

练习：计算出100的阶乘

#include <stdio.h>
int main(){
    char rets[256] = {1};
    int cnt = 1;
    /*将一个数放到rets数组中，rets[0]为这个数的个位*/
    for(int i = 2 ; i <= 100 ; i ++ )	
    {
        int carry = 0;	//	记录进位
        for(int j = 0 ; j < cnt ; j ++ )
        {
            int num = rets[j] * i + carry;	//	将rets数组记录的数，的每一位从个位开始，乘以将要
            rets[j] = num % 10;				//	被阶乘的数i，放入num中。更新rets数组中，正在执行
            carry = num/10;		//	的rets[j]。carry表示记录num中未被rets数组记录的*进位*
        }
        while( carry )		//		将进位carry赋值给rets数组中，当前的最高位cnt
        {	//	rets数组的每一位记录，阶乘的一位
            rets[cnt++] = carry % 10;	//	rets数组的最高位cnt,取carry进位的末位
            carry /= 10;	//	更新carry进位的值，除去以存储的末位
        }
    }
    //	打印数组
    for(int i = cnt-1 ; i >= 0 ; i -- )
    {
        printf("%hhd",rets[i]);
    }
    return 0;
}

函数传参

? 1.形式参数，函数内定义的变量都只属于它所在的函数，出了该函数就不能再用

? 2.普通 实参与形参之间是通过赋值的方式传递数据的(单向值传递)

? 3.return 其实是将数据存放在一个公共区域(函数都可以访问)，如果不写return语句，那么就会读该区域原来的数据，就调用一个 垃圾 数据

? 4.当数组作为函数的参数时，中括号中的长度就会丢失，需要额外增加一个变量传递数组的长度

? 5.数组作为函数参数传递是，传递是数组的首地址，叫做“址传递”。函数和函数的调用者可以共享一个数组！

练习：使用函数，实现找出数组中的最大值

练习：实现一个函数，对数组进行升序排序

练习：实现一个函数，查找数组是否存在某个值，如果存在则返回数组的下标。

设计函数的建议：

? 1.一个函数最好就解决一个问题，减低错误率，提高可读性

? 2.尽量减少函数之间的依赖层数（降低耦合度）

? 3.数据由调用者提供，结果返回给调用者（提高函数的通用性）

? 4.考虑函数的非法参数，可以通过返回值的方式告诉调用者参数有误，也可以通过注释方式写明情况

进程映像

程序：存储在磁盘上的可执行文件(二进制文件，脚本文件)

进程：在系统中运行中的程序

进程映像：指的是进程内存的分布情况

? text 代码段 存储二进制指令，常量数据，权限是只读。强制地修改就会产生段错误

? data 数据段 初始化的全局变量/初始化的静态局部变量

? bss 静态数据段 未初始化的全局变量/未初始化的局部变量。在程序进程运行前，该段内存会自动清理为0

? stack 栈 局部变量 操作系统自动管理，会自动申请和释放内存(小)

? heap 堆 由程序员手动管理 内存(大)

变量分类：局部变量 和 全局变量

• 全局变量：定义在函数外的变量

  • 存储位置：data(初始化) 或者 bss(未初始化)
  • 生命周期：从程序开始到程序结束
  • 作用范围：在程序的任意位置都可以使用

• 局部变量：

  • 存储位置：stack 栈内存
  • 生命周期：从函数调用开始，到函数结束
  • 作用范围：只能在函数内使用

  块变量： 定义在语句块中的变量

  • 存储位置：stack 栈内存
  • 生命周期：从函数调用开始，到函数结束
  • 作用范围：只能在函数内使用

注意：局部变量可以和全局变量同名，在函数内使用局部变量会屏蔽同名的全局变量，块变量在语句块内

会屏蔽同名的全局变量，块变量在语句块内会屏蔽同名的全局变量，局部变量，因此建议全局变量首字母大写

类型限定符

auto 用于定义自动分配内存，释放内存的变量(局部变量)，不加就代表了加

注意：全局变量不能用auto修饰的

C11中用于自动识别类型

extern 声明变量 extern 类型名 变量名

? 告诉编译器此变量已经在别处定义过了，请放心使用

? 它只能临时让编译通过，但是在 链接时，如果找不到该变量，依旧会报错

? 在多文件编程中使用：假设a.c中定义了全局变量N，想要在b.c中使用N，需要在使用前声明变量

static

• 改变存储位置：

  • 改变局部变量的存储位置，从stack改为data或者bss（取决于是否初始化）
    • 被static修饰的局部变量，叫做静态局部变量

• 延长生命周期：

  • 延长了局部变量的生命周期，直到进程结束

• 限制作用范围：

  • 限制 全局变量 · 函数 的使用范围，只能在本文件内使用

  可以防止全局变量，函数命名冲突，也可以防止被别的文件使用

const

	- "保护"变量的值不能被显示地修改，但是能可以通过访问内存来修改值
	- 但是如果修饰的是初始化的全局变量，初始化的静态变量，则该变量会从data改为text，变成“常量”

volatile

	- 如果变量的值没有被显示的修改，那么在使用该变量时，不会从内存中读取，而是继续使用上一次读取的结果，这个过程叫做取值优化，一般变量都会进行。
	- 变量被volatile修饰后，编译器不对该变量进行取值优化，每次都是从内存中重新读取
	- 一般硬件编程，多线程编程时会使用到

register

• 申请把变量的存储介质由内存改为寄存器，由于寄存器数量有限，不一定申请成功
• 存储介质：硬盘 - 内存 - 高级缓存 - 寄存器
• 寄村器变量不能取地址

typedef

	- 类型重定义，在定义变量时，在类型前加typedef，那么变量名就变成了这个类型的新名字
	- 注意：typedef不是替换关系

小项目：五子棋

? 需要的数据：

• 定义一个字符类型的数组15*15

• 定义变量，记录落子位置

• 定义变量，记录该落子为哪位棋手(黑棋“@” ，白棋 “$" )

  逻辑：

  • 定义需要的数据
  • 是否需要对数据进行初始化
  • 清理屏幕，显示棋盘
  • 落子。判断坐标是否合法，该位置不能有其它棋子。
  • 判断：检查是否五子连珠
  • 交换棋手

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

// 棋盘数组
char board[15][15];
//	棋子的位置
char key_x , key_y;
//	角色字符	黑棋 @	白棋 $
char role = '@';
//	初始化棋盘
void init_board(void){
    for(int i = 0 ; i < 15 ; i ++ )
    {
        for(int j = 0 ; j < 15 ; j ++ )
        {
            board[i][j] = '*';
        }
    }
}
//	显示刷新棋盘
void show_board (void){
    system("clear");
    for(int i = 0 ; i < 15 ; i ++ )
    {
        for(int j = 0 ; j < 15 ; j ++ )
        {
            printf("%c ",board[i][j]);
        }
        printf("\n");
    }
}

void get_key(void){
    while(1){
        printf("请%c输入棋子坐标：",role);
        scanf("%hhd%hhd",&key_x,&key_y);
        //	检查坐标是否合法
        if( key_x < 0 || key_y < 0 || key_x > 14 || key_y > 14 ){
            printf("坐标不合法，请重新输入！");
            continue;
        }
        //	检查是否有棋子
        if( '*' != board[key_x][key_y] ){
            printf("该位置已有棋子！请重新输入！");
            continue;
        }
        board[key_x][key_y] = role;
        return;
    }
}
//	重写get_key函数，并起名Luozi
void Luozi(void){
    printf("请%c落子",role);
    while(1){
        printf("\33[%hhd;%hhdH",key_x+1,(key_y+1)*2);
        switch( getch() ){
            case 183:	key_x > 0	&&	key_x--;	break;
            case 184:	key_x < 14	&&	key_x++;	break;
            case 186:	key_y > 0	&&	key_y--;	break;
            case 185:	key_y < 14	&&	key_y++;	break;
            case 10:	if( '*' == board[x][y] ){
                board[key_x][key_y] = role;
                return;
            }
        }
    }
}

//	检查是否五子连珠
bool is_win(void){
    //	左上 右下
    int cnt = 0;
    //	左上
/*    for(int x = key_x-1, y = key_y-1 ; x >= 0 && y >= 0 ; x-- , y-- )
    {
        if( role == board[x][y] ){
            cnt ++ ;
        }else{
            break;
        }
    }
    if( cnt >= 4 ) return true;
*/  
    if( count_key(-1,0)  + count_key(1,0)  >= 4 ) return true;
    if( count_key(0,-1)  + count_key(0,1)  >= 4 ) return true;
    if( count_key(-1,-1) + count_key(1,1)  >= 4 ) return true;
    if( count_key(-1,1)  + count_key(1,-1) >= 4 ) return true;
    return false;
}
//	检查是否五子连珠重写
int count_check(int ox,int oy){
    int count = 0;
    for(int x=key_x+ox, y=key_y+oy; x>0&&x<15&&y>0&&y<15; x+=ox,y+=oy ){
        if( role == board[x][y] ){
            count ++ ;
        }else{
            break;
        }
    }
    return count;
}

int main(){
    init();
    for(;;)
    {
    	show_board();
//      get_key();
        Louzi();
        if( /*is_win()*/ )
        {
            show_board();
            printf("%c胜利\n",role);
            return 0;
        }
        role = '@'==role? '$' : '@';
    }
    return 0;
}

函数递归

? 函数自己调用自己的这种行为叫做函数递归，可能会产生死循环。

? 递归是可以实现分治的这种思想，把一个大问题，分解成多个小问题，知道所有问题全部解决

• 如何写好递归
  • 写好一个出口
    • 解决一个小问题
      • 调用自己

练习：计算前N项斐波那契数列

1 1 2 3 5 8 13 21 ······

• 递归函数每一次调用都会在栈内产生一份自己的拷贝，直到执行到达出口，才会释放一层递归函数，因为此与循环相比递归非常消耗内存，速度很慢，因此如果能用循环解决的问题不要使用递归
• 递归优缺点：
  • 好理解，思路清晰
  • 很好地解决非线性问题
  • 耗费内存，速度很慢

练习：使用递归模拟N层 汉诺塔

#include <stdio.h>

void hanio(int n,char star,char m,char end){
    if( 1 == n )
    {
        printf("%d:form %c to %c\n",star,end);
    }
    else
    {
        hanio(n-1,star,end,m);
        printf("%d:from %c to %c\n",star,end);
        hanio(n-1,m,star,end);
    }
}

思考：显示出0~9的全排列

指针

• 什么是指针？

  • 指针是一种特殊的数据类型，使用它可以定义指针变量，
    指针变量存储的是整数数据，代表了内存的编号。
  • 通过编号可以直接访问对应的内存

• 为什么要使用用指针？

  • 函数之间是相互独立的，但是有使用需要共享变量。
    传参是单向值传递
    全局变量容易命名冲突
    数组使用不便，还需要额外传递数组长度
    虽然函数命名空间是独立的，但是地址空间是同一个，因此指针可以解决共享变量的问题
  • 由于函数之间的传参是值传递(内存拷贝)，对于字节数较多的变量，值传递的效率较低，如果传递变量的地址只需要传递 4 或 8 个字节。
  • 堆内存无法取名字，它不像data，bss，stack让变量名与内存建立联系，只能使用指针记录堆内存的地址来访问对应的内存

• 如何使用指针：

  • 定义： 类型名* 指针变量名_p；
    类型名 *指针变量名_p;

  • 指针变量与普通变量的用法有很多区别，建议在取名时，以p结尾以式区分

  • 指针的类型表示，指针指向的是什么类型变量的地址。它决定了通过这个指针变量可以访问的字节数

  • 一个*号只能定义一个指针变量

    • int *p1,p2,p3; // p1是指针，p2,p3是int

      int *p1,*p2,*p3; // p1,p2,p3都是指针

    • 指针变量与普通变量一样默认值是随机的，一般初始化为NULL(空指针)

  • 赋值：变量名_p = 地址；// 必须是有意义且有权限的地址

    • 指向栈内存：
      • int num；
      • int* p = &num;
    • 指向堆内存：
      • int* p = malloc(4);

  • 解引用： *变量名_p

    • 通过指针变量中记录的内存的编号去访问对应的内存，该过程可能会产生段错误，原因是里面存储的内存编号是非法的。
    • 注意：访问的字节数由指针定义时类型决定，后面都不会改变

练习：实现一个交换变量的函数，用着函数进行排序

练习：实现一个函数计算两个整数的最大公约数，最小公倍数，最大公约数用return返回，最小公倍数使用指针输出型参数

#include <stdio.h>
int max_min_num(int x,int y,int* p){
    int max = 1;
    for(int i = 2 ; i <= x ; i ++ ){
        if( x % i == 0 && y % i == 0 ) max = i;
    }
    for(int i = x*y ; i >= x && i >= y ; i-- ){
        if( 0 == i%x && 0 == i%y ) *p = i;
    }
    return max;
}
int main(){
    
}

使用指针时需要注意的问题：

• 空指针：

  • 值为NULL的指针变量叫做空指针
    • 如果对空指针解引用，一定产生段错误
      • NULL一般作为一种错误标志，当一个函数的返回值是指针类型时，可以使用NULL指针作为返回出错的结果

• 如何避免空指针带来错误：

  • 使用来历不明的指针前先进性判断

  if( NULL == p )		if( !p )
  //	注意：NULL在绝大部分操作系统上是0，也有个别老的操作系统中是1
  

  • 当函数的参数是指针，别人传给你的指针可能是空指针
  • 从函数获取的返回值是指针类型时，可能会返回空指针

• 野指针：

  • 指向不确定的内存空间的指针叫做野指针
  • 对野指针解引用的后果：
    • 一切正常
    • 段错误
    • 脏数据
  • 野指针比空指针的危害更严重，因为它无法判断出来，而且可能是隐藏性的错误，短时间不暴露。
  • 所有的野指针都是程序员自己制造出来的，如何避免产生野指针
    • 定义指针变量时一定要初始化( int *p = NULL )
    • 函数不要返回栈内存（函数内的局部变量）的地址
    • 指针指向的内存被释放后，指针变量要及时置空NULL

• 指针的运算

  • 指针变量中存储的是整数，理论上整数可以使用的运算符它都可以使用，
    但是绝大部分运算符无意义的
  • 指针 + n：指针+指针类型的宽度*n <==> 相当于指针前进n个元素
  • 指针 - n：指针-指针类型的宽度*n <==> 相当于指针后退n个元素
  • 指针- 指针：(指针 - 指针)/指针类型宽度 <==> 相当于计算两个指针之间，间隔多少个指针元素

• 指针与const

  • 当我们为了提高传参效率而使用指针为函数传参时，传参效率提高了，但是变量被共享在被修改的风险，可以使用const保护指针所指向内存
  • const int* p; // 保护指针所指向的内存不被修改
  • int const *p; // 保护指针所指向的内存不被修改
  • int* const p; // 保护指针变量不被修改
  • const int* const p; // 指针变量和指所指向内存都不能改
  • int const * const p; // 指针变量和指所指向内存都不能改

• 指针数组和数组指针

  • 指针数组：由指针变量组成的数组，指针数组。

    ? 它的成员变量都是 类型相同的指针变量

    ? 类型* arr[长度]；

    ? int *arr[10] = {};

  • 数组指针：专门指向数组的指值

    ? 类型 (*int)arr[长度];

• 数组名和指针：

  • 数组名就是一种特殊的指针

  • 数组名是常量，不能修改它的值，数组名没有自己的存储空间，它与数组首地址之间是映射关系。
    数组名 == &数组名

    当指针变量指向数组首地址时，指针可以当做数组名使用，数组名也可以当做指针使用

    数组名[i] == *(数组名+i)

    *(p+i) == p[i];

    注意：当数组作为函数的参数时锐变成了指针，所以长度丢失

  • 指针是变量是拥有自己存储空间，它与所指向的内存，是指向关系

• 二级指针

  • 二级指针就是指向指针的指针，里面存储的是指针变量的地址

  • 定义：类型名** 变量名_pp

  • 赋值：变量名_pp = &指针变量

  • 解引用：*变量名_pp <> 指针变量
    **变量名_pp <> 变量的地址

    注意：但需要函数之间共享指针变量，传递指针的地址(二级指针)

• 函数指针

  • 函数名就是一个地址，函数名代表了函数在代码段(data)中所处的入口位置
  • 函数指针就是指向函数的指针，它里面存储的是函数在代码段处的入口位置
  • 返回值类型 (*p)(类型1，类型2，······ );
  • 可以通过函数指针，把函数当做参数传递给另一个函数，这种方式称之为函数的回调模式；

堆内存(heap)

一.什么是堆内存

? 是进程的一个内存段(text/data/bss/heeap/stack)，由程序员手动管理

? 优点足够大，缺点使用麻烦

二.为什么要使用堆内存

	1. 随程序的复杂，数据量变多

 		2. 其它内存段的申请释放不受控制，堆内存的申请释放受控制，可以适时地节约内存

三.如何使用堆内存

? 注意：C语言中没有控制堆内存的语句，只能使用C语言标准库中的函数

? #include <stdlib.h>

? void *malloc (size_t size);

功能：从堆内存中申请size个字节的内存，申请的内存数据的值不确定

返回值：成功申请返回值的连续内存的首地址，失败返回NULL

? void free(void *prt);

功能：释放一块堆内存

prt：要释放堆指针的首地址

注意：free释放只是使用权限，数据不会全部清理

注意：不能连续释放同一内存，但可以连续释放空指针

? void *calloc(size_t nmemb, size_t size);

功能：从堆内存申请nmemb块，每块size字节大小的内存

calloc(10,4) == malloc(40)

注意：calloc申请的内存会被初始化为0；calloc比malloc慢！

? void *realloc(void ptr, size_t size);

功能：可以改变已有的堆内存的大小，size表示改变后的大小，在原有的基础上调大调小。

注意：返回值是调整后内存块新的首地址，一定要从新接受返回值，可能不是在原位置进行调整

? 如果无法在原位置进行调整：

? 1.申请一块新的符合大小的内存

? 2.拷贝原内存中的数据

? 3.释放原内存，返回新内存的首地址

malloc的内存管理系统

? 1.当我们首次向malloc申请内存，malloc会向操作系统申请内存,操作系统会直接分配33页（1页=4096字节）内存交给malloc管理，但是并不意味着可以越界访问，因为malloc可能把其它的内存分配给“其他人”，这样就会产生脏数据

#include <stdio.h>
int main(){
    int* p = malloc(4);
    for(int i = 0 ; i <= 4096*33-2 ; i ++ ){
        
    }
    return 0;
}

? 2.每个申请内存块之间会有空隙(4~12字节)，一部分空隙是为了内存对齐，其中一定有4个字节记录了malloc的维护信息，这些信息决定了下次malloc分配内存的位置，如果破坏了维护信息，会影响下一次malloc或free的过程。

使用堆内存需要注意的问题

? 内存泄漏：内存无法再使用，也无法被释放，而需要在次使用时只能重新申请。

? 上述过程重复使用，会将内存逐渐耗尽

注意：一旦进程结束属于该进程的所有资源都会被操作系统会回收

? 如何尽量地避免内存泄漏：谁申请内存，谁释放；谁知道该释放，谁释放；

? 如何判断，定位内存泄漏：

1. ps -aux Linux系统查看运行的进程

   任务管理器 Windows系统

   2. 借助代码分析工具 mtrace ，检查malloc和free是否成对出现

   3. 封装malloc，free，记录申请，释放的信息到日志文件中

? 内存碎片：已经释放了，但依然无法继续使用的内存叫做内存碎片。由于申请和释放的时间不协调导致的，无法完全避免只能尽量减少

? 如何减少内存碎片：

			1. 尽量使用栈内存

  				2. 尽量不要频繁的申请和释放内存
                   				3. 尽量申请较大块的内存自己管理

内存清理函数

#include <strings.h>
void bzero(void *s, size_t n);
/*	
	功能：把一块内存清理为0；
	s：内存块的首地址
	n：内存块的字节数
*/

#include <string.h>
void *memset(void *s, int c, size_t n);
/*
	功能：把内存块按字节设置为c
	s：内存块的首地址
	c：想要设置的ASCII值
	n：内存块的字节数
	返回值：成功设置后的首地址
*/

#include <stdio.h>
#include <stdlib.h>
void CreateHeap(void** p,size_t n){
    *p = malloc(n);
//	printf("func:%p\n",p);    
    if( NULL == *p ){
        printf("Create error\n");
        return;
    }
}
int main(){
    int* p = NULL;
    CreateHeap();
    printf("%p",p);
    return 0;
}

堆内存定义二维数组

? 指针数组

? 定义n行，m列二维数组

		int*	arr[n];
		for(int i = 0 ; i < n ; i ++ ) {
            arr[i] = malloc(m*sizeof(arr[i]));
        }

注意：每一行的m值可以不同，这种方式可以定义不规则的二维数组

优点：可以不规则，对内存要求较低

缺点：申请麻烦，容易产生内存碎片

?

? 数组指针

? 定义n行，m列二维数组

//		int* p = malloc(4*10);
		int (*arrp)[10] = malloc(sizeof(int)*10*m);
		for(int i = 0 ; i < 10 ; i ++ ){
            for(int j = 0 ; j < m ; j ++ ){
                printf("%d",arrp[i][j]);
            //  printf("%d",*(*(arrp+i)+j));
            }
        }

? 缺点：对连续内存要求高，可能申请失败

? 优点：申请简单

练习：计算出100~10000之间所有的素数，结果存储在堆内存中，尽量不要浪费内存

• 先计算有多少个，在一个全申请出来
• 一边算，一边申请

字符串

由字符组成的串型结构，结束标志是’\0’。

字符

在计算机中字符都是以整数形式存储，当需要显示字符时，就会根据ASCII码表中对应关系显示出相应的符号或段

‘\0’ 0 空字符

‘0’ 48

‘A’ 65

‘a’ 97

串

串：是一种数据结构，由一组连续的若干个类型相同的数据组成，末尾一定有一个结束标志。

? 对于这种数据结构的处理都是批量性，从开始的地方一直处理到结束标志停止

字符串的存在形式

? 字符数组： char str[5] = {‘a’,‘b’,‘c’,‘d’,‘\0’};

由char类型组成的数组，要为’\0’预留位置

使用的是stack内存，因此数据是可以中途修改的

? 字符串字面值： “由英文的双引号包含的若干个字符”

末尾会自动补’\0’

字符串字面值以地址的形式存在，字符数据存在text(代码)段，如果修改一定会产生段错误

常用方式

字符数组[] = “字符串字面值”；

会自动给’\0’预留位置，可以修改内容，初始化简单

当赋值完成后，字符串存在两份，一份在代码段，一份在栈内存

完全相同的字符串字面值，在代码段中，只存在一份。

const char* p = “12435adsf”;

sizeof§; 4/8 计算指针字节数

sizeof(“asdf”); 5 计算字符串字面值在代码段的字节数

字符串的输入输出

? 输入：

? char str[200] = {};

? scanf(“%s”,str);

缺点：scanf不能输入带空格的字符串

? char *gets (char *s );

功能：可以输入带空格的字符串

返回值：返回s的首地址，为了可以链式调用，一个函数的返回值作为另一个函数的参数

缺点：不限制输入长度，会有安全隐患，编译器会有警告

?

? char *fgets（char *s, int size, FILE *stream）;

功能：从stream中最多输入size-1个字符到s中

s：字符数组

size：最多接收的字符个数+1

stream：stdin 相当于键盘文件 固定写

返回值：链式调用

如果输入超过size-1个字符，多出来的不接收

如果不住size-1个字符，'\n’也会接收

? 输出：

? printf(“%s”,字符数组，字符串字面值)

int puts(const char *s);

功能：输出字符串

返回值：成功输入字符的个数

注意：会自动打印换行符

练习：实现一个判断字符串是否是回文串的函数

#include <stdio.h>
#include <stdbool.h>

bool is_palin_str(const char* str){
    int len = 0;
    while( str[len] ){
        len++;
    }
    for(int i = 0 ; i < len/2 ; i ++ ){
        if( str[i] != str[len-1-i] ){
            return false;
        }
    }
    return true;
}

int main(){
    char str[256] = {};
    scanf("%s",str);
    printf("%s\n",is_palin_str(str)? "yes":"no");
}

练习：实现一个函数，把一个有数组字符组成的字符串转换成对应的整数

#include <stdio.h>
int str_to_int(const char* str){
    int sum = 0;
    while( *str ){
        if( *str >= '0' && *str <= '9' ){
            sum = 10*sun + (*str-'0');
        }
        str++;
    }
    return sum;
}
int main(){
    char str[256] = {};
    scanf("%s",s);
    printf("%d\n",str_to_int(str))
    return 0;
}

练习：实现一个函数，将字符串逆序输出

#include <stdio.h>
char* reverse_str(char* str){
    int len = 0;
    while( str[len] ) len++;
    for(int i = 0 ; i ; i < len/2 ; i ++ ){
        char temp = str[i];
        str[i] = str[len-1-i];
        str[len-1-i] = temp
    }
    return str;
}
int main(){
    char str[256] = {};
    scanf("%s",str);
    puts( reverse_str(str) );
    return 0;
}

输入输出缓冲区

? 程序中要输出显示的数据并不会立即显示在屏幕上，而是先存储在输出缓冲区中，当满足一定条件时才会从缓冲区中显示在屏幕上

1. 遇到’\n’换行字符后
2. 遇到输入语句时
3. 当输出缓冲区满的时候，也会全部显示出来
4. 当程序结束时，结束之前会显示在屏幕上
5. Linux中手动刷新 fflush(stdout);

输入缓冲区

程序并不是立即从键盘获取输入的内容，而是当按下回车后，终端输入的内容会先存储到输入缓冲区中，然后函数再从输入缓冲区中读取数据到内容中。

1. 当你想要输入的数据是整性或浮点型数据，但是缓冲区中的数据是符号或字符时，读取会失败，数据会残留在缓冲区中，影响接下来所有数据的读取

   ? 解决：

   ? 判断scanf的返回值是反全部正确，如果不是，先清理输入缓冲区残留数据，在提示重新输入。

2. fgets可以接受指定size-1个字符，如果有多余的字符会残留在缓冲区中，可能会影响接下来的输入
   解决：

   先判断’\n’在不在字符串内，如果不在，则说明在缓冲区内，需要缓冲清理
   scanf(“%*[^\n]”); 从缓冲区中读任意数据并丢弃，如果不是’\n’，继续读取，直到运用’\n’，停止读取(正则表达式)
   scanf(“%*c”)；从缓冲区中读入一个字符并丢弃

   注意：可以考虑封装新的fgets函数解决输入过多问题

   Linux:

   stdin->_IO_read_ptr = stdin->_IO_read_end;

   将当前缓冲区中的当前位置指针，移动到缓冲区末尾，相当于清理了输入缓冲区，但是只能在Linux、UNIX系统中使用这两个位置指针

3. 当先输入整数，浮点型数据，再输入字符，字符字符串时，前一次的输入会残留’\n’，影响了后面的字符字符串的输出

解决：scanf(“(空格)%c”,&ch);

字符串相关操作函数

size_t strlen(const char *s);

功能：计算字符串字符长度，不包括’\0’

char *strcpy(char *dest, const char *src);

功能：把src拷贝给dest,相当于给dest赋值 =

返回值：链式调用

char *strcat(char *dest, const char *src);

功能：把src追加到dest末尾，相当于合并两个字符串， +=

返回值：链式调用

int strcmp(const char *s1,const char *s2);

功能：比较两个字符大小

? 从头开始，每一个字符一对一进行比较，按照字典序。

? 一旦比较出结果，立即返回结果，后面的不再比较

返回值：

0 s1 == s2

正数 s1 > s2

负数 s1 < s2

练习：自己实现strlen/strcpy/strcat/strcmp四个字符串处理函数【常考】

#include <assert.h>
size_t str_len(const char* str){
    assert( NULL != str );
    char* p = str;
    while( *p )	p++;
    return p-str;
}
char* str_cpy(char* dest,const char* src){
    assert( NULL != dest && NULL != src );
    char* p = dest;
    while( *p++ = *src++ );
    return dest;
}
char* str_cat(char* dest,const char* src){
    assert( NULL != dest && NULL != src );
    char* p = dest;
    while( *p ) p++ ;
    while( *p++ = *src++ );
    return dest;
}
size_t str_cmp(const char* s1,const char* s2){
    while( *s1 == *s2 && *s1 ) s1++,s2++;
    return *s1-*s2;
}

字符串相关操作函数

#include <stdilb.h>
int atoi(const char *nptr);
//	功能：字符串转int类型
long atol(const char *nptr);
//	功能：字符串转long类型
long long atoll(const char *nptr);
//	功能：字符串转long long类型
double atof(const char *nptr);
//	功能：字符串转double类型

#include <string.h>
char *strstr(const char *haystack,const char *needle);
//	功能：在字符串haystack中查找子串needle
//	needle在haystack中首次出现的位置，如果找不到则返回NULL

int sprintf(char *str,const char *format,··· );
//	功能：把各种类型的数据输出给字符串str
//	返回值：转换后字符个数
int sscanf(const char *str,const char *format,··· );
//	功能：从str中解析读取数据到变量
//	返回值：成功解析出来的变量个数

void *memcpy(void *dest,const void *src,size_t n);
//	功能：从src位置拷贝n个字节到dest位置
//	返回值：链式调用
int memcmp(const void *s1,const void *s2,size_t n);
//	功能：比较两块内存的值，按照字节比较，一旦比较出结果后面不再比较
/*	返回值：
			s1 == s2 0
			s1 < s2  负数
			s1 > s2  正数
*/

通讯录系统

? 要求：存储联系人信息：姓名，性别，电话。最多存50人。

? 功能要求：

增加

除（按名字）

修改（按名字）

查找联系人，按电话或姓名，支持模糊查找

显示所有联系人信息

退出系统

#include <stdio.h>
#include <stdlib.h>
#include <getch.h>
#include <unistd.h>		//	sleep函数库
#include <string.h>

static char name[50][20];	//	姓名
static char sex[50];		//	性别
static char tel[50][12];	//	电话
static int count = 0;		//	当前有效联系人的数量

int main(){
    while(1){
        //	显示主界面
        switch( menu() ){
            case '1':	add();break;
            case '2':	del();break;	
            case '3':	mod();break;
            case '4':	find();break;
            case '5':	show();break;
            case '6':	return 0;
        }
    }
}

int menu(void){
    system("clear");
    puts("****欢迎使用阿斯利康通讯录****\n");
    puts("1.添加练习人\n");
    puts("2.删除练习人\n");
    puts("3.修改练习人\n");
    puts("4.查询练习人\n");
    puts("5.查询所有人\n");
    puts("6.退出通讯录\n");
    puts("**************************\n");
    char cmd = getch();
    printf("%c\n",cmd);
    return cmd;
}
//	printf("%s\n",__func__);	两个下划线func两个下滑线：
void add(void){
    printf("%s\n",__func__);	//	测试函数调用
    if( 50 <= count ) {
        puts("系统正在升级中，请等待··· ");
        return;
    }
    int i = 0;
    while( sex[i] ){ i++; }
    printf("请输入姓名，性别，电话：");
    scanf("%s %c %s",name[i],&sex[i],tel[i]);
    count++;
    msg_show("成功添加联系人！\n",1.5);
}
void del(void){
    printf("%s\n",__func__);	//	测试函数调用
    char key[20] = {};
    printf("请输入要删除的联系人姓名：");
    scanf("%s",key);
    
    for(int i = 0 ; i < 50 ; i ++ ) {
        if( sex[i] && 0 == scrcmp(key,name[i]) ) {
            sex[i] = 0;
            count--;
            msg_show("删除成功！\n",1.5);
            return;
        }
    }
    msg_show("查无此人，删除失败！",1.5);
}
void mod(void){
    printf("%s\n",__func__);	//	测试函数调用
    char key[20] = {};
    printf("请输入要修改的联系人姓名：");
    scanf("%s",key);
    
    for(int i = 0 ; i < 50 ; i ++ ) {
        if( sex[i] && 0 == scrcmp(key,name[i]) ) {
            printf("请重新输入联系人的姓名，性别，电话：");
            scanf("%s %c %s",name[i],&sex,tel[i]);
            msg_show("修改联系人成功！\n",1.5);
            return;
        }
    }
    msg_show("查无此人，修改失败！",1.5);
}
void find(void){
    printf("%s\n",__func__);	//	测试函数调用
    char key[20] = {};
    printf("请输入要查询的关键字：");
    scanf("%s",key);
    for(int i = 0 ; i < 50 ; i ++ ) {
        if( sex[i] && ( strstr(name[i],key) || strstr(tle[i],key) ) ) {
            printf("姓名：%s,性别：%s,电话号码：%s\n",name[i],'w'==sex[i]?"女":"男",tel[i]);
        }
    }
}
void show(void){
    printf("%s\n",__func__);	//	测试函数调用
    for(int i = 0 ; i < 50 ; i ++ ) {
        if( sex[i] ) { 
            printf("姓名：%s,性别：%s,电话号码：%s\n",name[i],'w'==sex[i]?"女":"男",tel[i]);
        }
    }
    anykey_continue();
}
//	打印提示信息
void msg_show(const char* msg,float sec){
    printf("%s",msg);
    fflush(stdout);		//	手动刷新
    usleep(sec*1000000);
}
//	按任意键继续
void anykey_continue(void) {
    stdin->_IO_read_ptr = stdin->_IO_read_end;
    puts("请按任意键继续:");
    getch();
}

预处理指令的分类

#include	//	导入头文件 或 头文件包含
	#include <>		//	在系统指定路径查找头文件
	#include ""		//	先从当前工作路径查找，找不到再从系统指定路径查找，并导入头文件
gcc code.c -I path	//	编译时指定头文件的加载路径为phth，最先从该路径查找
修改 ~/.bashrc 终端配置文件 //	可以通过设置环境变量来修改，真加系统指定头文件加载路径

#define 定义宏

• 宏常量：#define 宏名 常量值

  • 本质上就是，在代码中，将宏名替换成对应的常量值！
  • 优点：降低维护成本，提高可读性，提高安全性，提高可扩展性（可以与case连用）
  • 注意：宏常量名一般全大写，末尾不加分号
    • 局部变量，函数名全小写；局部变量首字母大写
    • 数组arr 指针 _p , _pp ，字符串 str

• 宏函数：

  • 预定义宏函数：

  	__func__	获取函数名
  	__FILE__	获取文件名
  	__DATE__	获取当前函数
      __TIME__	获取当前日期
      __LIME__	获取当前行数 %d
  

  • 宏函数：
  • 定义：#define 宏名（参数）替换代码
  • 宏函数不是真正的函数，不检查参数类型，没有传参，只有表达式的计算结果没有返回值

  替换过程：

  1. 先把代码中使用到宏函数的笛梵替换为宏函数后面的代码

     2. 再把宏函数代码中使用到的函数替换为调用者提供的数据

• 宏的二义性

  • 由于宏代码所处的位置，参数位置优先级的问题，导致同一个宏函数有不同的可解释结果

• 如何避免二义性：

  • 给每个参数加小括号，给每个式子加小括号
  • 在使用宏函数时，不要提供带自变运算符的参数

注意：宏函数后面的替换不能直接换行，需要在每一行末尾通过续行符 \ 来换行

? 如果有多行代码也可以使用大括号保护

练习：实现一个交换两个变量的值的宏函数，数据类型通用，能写多少个，分析优劣

#define SWAP(a,b) a=a+b,b=a-b,a=a-b;	//	数据可能会溢出，不能够交换结构体数据，不能交换指针数据
#define SWAP1(a,b) a=a*b,b=a/b,a=a/b;
#define SWAP2(a,b) a=a^b,b=a^b,a=a^b;	//	不会溢出，只能交换整性，不能交换同一变量
#define SWAP3(A,B) long double t=a;a=b;b=t;	//	不能交换结构体
#define SWAP4(a,b,type) type t=a;a=b;b=t;	//	可以传结构体，节约内存
#define SWAP5(a,b) typeof(a) (t)=(a);(a)=(b);(b)=(t);

? typeof ：返回变量名类型，只能在GNU编译器中使用

常考笔试面试题：

• #define 与 typedef 的区别

  • #define INT int
    • typedef int INT

  INT num;

  如果是普通类型，他们功能能上没有区别

  #define INTP(1) int*

  typedef int* INTP(2);

  INTP(1) p1,p2,p3; p1为指针，p2,p3为普通的变量

  INTP(2) P1,P2,P3; p1,p2,p3皆为指针

• 宏函数与普通函数的区别，优缺点

  • 是什么？

    宏函数：带参数的宏替换，只是代码替换，只能使用时想函数而已，不是真正的函数

    函数：是一段具有某项功能的代码集合，会被翻译成二进制指令存储代码段，函数名就是它的首地址，有独立的栈内存，命名空间

  • 有什么不同？

    函数：有返回值，类型检查 内存的申请释放 不冗余

    宏函数：运算结果 不检查内容类型 通用 替换 冗余 快

  • 注意：调用频繁，内容简单的功能适合写成宏函数

条件编译预处理

• 根据条件决定哪些代码是否参与最终的编译

• 版本控制：

  #if	条件
  #elif 条件
  #else
  #endif
  

• 头文件卫士：防止头文件被 重复包含

  • 格式：

    #ifndef		宏名
    #define		宏名
    #endif
    //	宏名为文件名全部大写，小数点用下划线代替
    //	注意头文件中必加头文件卫士
    

• 判断调试：

  #ifdef		宏名
  //	如果宏名定义了，此处代码参与编译
  #else		
  //	否则，此处编译
  #endif
  //	gcc code.c -D宏名		可以在编译时定义宏
  

#include <stdio.h>
//	定义打印调试信息的宏函数
//	gcc 文件名	-D	宏名		进行编译
#ifdef DEBUG
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...)
#endif

//	打印错误信息的宏函数
#define error(...) printf("%s:%s %d %s :%m %s %s",__FILE__,__func__,__LINE__,__VA_ARGS__,__DATE__,__TIME__)

int main(){
    int num = 88;
    printf("----------\n");
    debug("提示信息：%d\n",num);
    printf("----------\n");
    return 0;
}

头文件

• 头文件中应该写什么？

  • 头文件可能会被任意的源文件包含，意味着头文件中的内容会在多个目标文件同时存在，因此要满足合并内容不能有冲突

  • 重点：头文件中只能编写申明语句，绝对不能有定义语句

    函数申明，全局变量，宏常量，宏函数，typedef，结构，联合，枚举的类型声明

• 头文件的编写原则：

  • 为每个.c文件编写一份.h文件，.h文件对.c文件的说明
  • 如果需要用到某个.c文件中的全局变量，函数，宏文件等内容时，只需要把它的头文件导入即可
  • .c文件也要导入自己的.h文件,目的是为了声明与定义一致

• 头文件的相互包含：

  • 假设：a.h包含b.h，b.h又包含了a.h，此时编译会出错（错误提示：未知类型名“XXX”）
  • 解决方案：将a.h需要导入b.h的内容和b.h需要导入a.h的内容提出来另一个c.h

Makefile

• Makefile是由一系列编译指令组成的可执行文本文件，也叫编译脚本
• 在终端执行make命令，就会自动执行Makefile脚本文件中的编译指令，它可根据文件的最后修改时间来判断哪些需要重新编译，哪些不需要重新编译，从而提高编译效率
• 一个最简单的Makefile格式：
  • 执行目标：依赖
  • Tab键 执行命令
  • 被依赖目标1：依赖文件
  • Tab键 执行命令
  • ···
  • 被依赖目标2：依赖文件
  • Tab键 执行命令

CC   =  gcc
BIN  =  main
OBJ  =  main.o func.o tool.o
STD  =  -std=gnu99
FLAG =  -Wall -Werror
 LD  =  -lm
INCLUDE = -I
    
all : $(OBJ)
    $(CC) $(OBJ) -O $(BIN)
    
%.O:%.C
    %(CC) $(STD) -C %< -O $@
/*
main.o : maic.c func.h tool.h
	$(CC) -c main.c
func.o : func.c tool.h
	$(CC) -c func.c
tool.o : tool.c
	$(CC) -c tool.c
*/
clean:
	rm -rf $(BIN) $(OBJ)

练习项目 2048游戏

• 文件规则：
  • main.c 程序入口
  • game2048.c game2048.h 游戏的业务逻辑
  • direction.c direction.h 四个方向处理
  • tools.c tool.h 工具函数
  • Makefile 编译脚本

//	系统命令，创建所有可能要写的空文件
    vim create_project.sh // 创建脚本文件

        touch main.c
        
    	touch game2048.c game2048.h
        
        touch direction.c direction.h
        
        tools.c tool.h
#编译脚本
        ls > Makefile

        ls > game2048.conf
        
        
//chmod +x create_project.sh
//	写Makefile文件
CC = gcc
BIN = game2048.bin
OBJ = direction.o game2048.o main.o tools.o
FLAG = -Wall -Werror

all : $(OBJ)
    $(CC) -O $(BIN) $(OBJ)
%.o : %.c
    $(CC) $(STD) $(FLAG) -C $< -O $@
clear:
	rm -rf $(BIN) $(OBJ)
        
        
//	vim game2048.conf
        gedit + 要打开的文件
 

//	 2048游戏代码

//game2048.c
    
int (*view)[4] = NULL;
#include <stdlib.h>
#include <time.h>
#include "game2048.h"
#inlcude "tool.h"

void init_game(void){
    debug("%s\n"n__func__);
    //	申请堆内存
    view = calloc(sizeof(view[0][0])*16);
    //	初始化数据
    srand(time(NULL));
    //	读取文件,加载数据;
}

void start_game(void){
    
}

void end_game(void){
    debug("%s\n",__func__);
    //	保存数据
    //	在释放内存
    free(view);
	view = NULL;
}

// tool.h文件
{
    #include <stdbool.h>
    extern int (*view)[4];
    extern int score;
    
    void show_view(void);
	void rand_two(void);
	bool is_die(void);
}

//	tool.c文件
#include <stdbool.h>
#include "tool.h"
void show_view(void){
    system("clear");
    printf("---------------------\n");
    for(int i = 0 ; i < 4 ; i ++ ){     
        for(int j = 0 ; j < 4 ; j ++ ){
            if( view([i][j] ){
                printf("|%4d");
            }else{
                printf("    ");
            }
        }
        printf("|\n");
        printf("---------------------\n");
    }
}
static bool is_full(void){
    int *num = (int*)view;
	for(int i = 0 ; i < 16 ; i ++ ){
        if( 0 == num[i] ) return false;
    }
    return true;
}
void rand_two(void){
    
}
void is_die(void){}

结构，联合，枚举

结构struct：

• 结构是一种由程序员自己设计的数据类型，用于描述一个事务的各项特征数据，由若干个不同的基础类型组成

• 设计：定义变量：

• 注意：struct在C语言中，定义结构变量时不能省略

• 变量初始化

  • struct 结构类型名 结构变量名 = {v1,v2,···};
  • struct 结构类型名 结构变量名 = {.成员名3=常量，.成员名2=常量 };
  • 注意：同类型的结构变量可以给另一个结构变量初始化

• 由于结构体的字节数一般都比较大，普通的值传递效率非常地低，因此传递结构变量的地址，也即是传递结构指针变量，此时想要通过结构指针变量访问成员是借助 向右的箭头→，如果不需要修改，用const保护。

• typedef 重定义结构类型名

  • typedef struct 结构类型名 结构类型名；

  • 结构指针变量名->成员变量
    
    typedef struct 结构类型名{
        
    }结构类型名;
    

struct 结构类型名{
    类型 成员名1;
    类型 成员名2;
    ···
};
//	定义结构变量
struct 结构类型名 结构变量名;
//	注意：结构类型名

//	列如：设计学生结构类型
#include <stdio.h>
#include <string.h>
struct Student{
    char name[20];
    char sex;
    char id[10];
    double score;
}
//	初始化
struct Student to = {"小明",'m',"10086",309.0};
struct Student stu;		//	定义一个学生结构变量

strcpy(stu.name,"小三");
stu.sex = 'w';			//	访问结构体成员：结构体变量.成员名
strcpy(stu.id,"10000");
stu.score = 230.5;
printf("%s %c %s %lf\n",stu.name,stu.sex,stu.id,stu.score);

练习：设计一个教师结构体类型，类型成员有：姓名，性别，工号，工龄。定义一个教师结构变量，使用scanf输入每个成员的值并显示。

• 如何计算一个结构体的总字节数：
  • 结构成员顺序会影响它的总字节数，如果能够在设计结构体时合理地安排成员顺序，可以大大地节约内存
  • 内存对齐：假设第一个成员从零地址开始，存储每个成员的地址编号必须能被该成员的类型的字节数整除，如果不能整除，就用空白字节填充。
  • 内存补齐：结构体的总字节数，必须是它最大成员的整数倍，如果不够，则在末尾补空白字节。
  • 注意：在Linux系统下计算对齐补齐时，如果成员数超过4字节，按4对齐补齐。Windows系统按实际字节数对齐补齐。

联合union：联合与结构使用方法基本一致，与联合的所有成员共用一块内存，一个成员的值发生改变，其它成员也发生改变

联合的效果就是使用少量的内存对应多个标识符，以此达到节约内存的目的，但是现在基本不使用

union Data{
    char ch[5];		//	0~4
    int num;		//	0~3
}
//	注意：计算联合字节数时，不需要考虑内存对齐，但是需要考虑内存补齐

• 如何判断系统的大小端问题?
  • 假设十六进制数0x01020304存储在0x0A~0x0D范围内的四字节内存中
  • 大端系统：高位数据存储在低位地址
  • (0x0A：0x01，0x0B：0x02，0x0C：0x03，0x0D：0x04)
  • 小端系统：低位数据存储在低位地址
  • (0x0A：0x04，0x0B：0x03，0x0C：0x02，0x0D：0x01)
• 个人计算机一般都是小端系统，而Unix服务器和网络设置都是大端。网络字节序也就是大端模式的数据，本地字节序就是小端模式的数据 序列化和反序列化

枚举enum：枚举就是一种数据类型，将可能出现的所有值罗列出来，并起一个有意义的名字表示这些值，除此之外给该类型的变量赋其它值，是非法的 (愿望) 。

• 枚举可以看做一种值受限的int类型，但在C编译器为了效率不检查，所以在C语言中枚举就相当于int类型的数据
• 如果不给成员值，那么枚举中的值第一个默认从0开始，逐渐+1，如果设立某个值，后面的成员在它的基础上逐渐+1
• 为什么要用枚举：
  • 为无意义的值取一个有意义的名字，提高代码的可读性，提高安全性 (比变量安全)。

练习：修改前次的通讯录，改为结构体存储数据，使用堆内存。

文件

• 文本文件：存储的ASCII码值的二进制文件
• 二进制文件：存储数据的补码

文件IO：

#include <stdio.h>
FILE *fopen(const char *path,const char *mode);
//	功能：打开或创建文件
path:	文件路径
mode：	文件打开模式
    r		以只读权限方式打开文件，如果不存在则失败
    r+		在r的基础上，增加写权限
    w		以只写权限打开文件，如果存在则清空打开，如果不存在则新建文件再打开
    w+		在w的基础上，增加读权限
    a		以只写权限打开文件，如果存在则在末尾追加内容，不存在则新建
    a+		在a的基础上，增加读权限
返回值：文件指针，不需要关心里面有什么数据，只需要知道它是一个针对已打开的文件凭证，打开文件失败会返回NULL。
int fclose(FILE *stream);
功能：关闭一个打开的文件
返回值：成功返回0，失败返回-1；
> 注意：如果需要立即修改文件的内容，最好先关闭文件

二进制方式的读写：

#include <stdio.h>
size_t fwrite(const void *ptr,size_t size,size_t nmemb,FILE *stream);
//	功能：把内存中的数据写入到文件中
pty：待写入的内存的首地址;
size：一次写入的字节数
nmemb：写入的次数
stream：文件指针，fopen的返回值，表示：将要写入数据的文件
返回值：成功写入的次数
    
size_t fread(void *ptr,size_t size,size_t nmemb,FILE *stream);
//	功能：从文件中读取数据到内存中
pty：从文件中读取数据到内存
size：一次读取的字节数
nmemb：读入的次数
stream：文件指针，表示：从哪个文件中读取数据
返回值：成功读取的次数

练习：设计并定义一个教师结构变量并初始化，以二进制方式写入到文件中

练习：从文件中读取一个教师结构体数据到变量中并显示

以文本方式读写：

#include <stdio.h>
int fprintf(FILE *stream,const char *format,···);
功能：以文本形式写入数据到文件中
stream：要写入的文件
format：占位符和提示信息
· · · ：变量列表
返回值：成功写入的字符个数
    
int fscanf(FILE *stream,const char *format,···);
功能：从文件中读取数据到变量中
stream：要读取的数据
format：占位符 (数据格式)
· · · ：变量列表
返回值：成功写入的字符个数

练习：设计并定义一个教师结构变量并初始化，以文本方式写入到文件中

练习：从文件中读取一个教师结构体数据到变量中并以文本方式显示

文件的位置指针：

• 每个通过fopen打开的文件都有一个文件位置指针来记录着接下来要读写的位置，以r,r+,w,w+打开文件，位置指针在文件的开头，以a,a+打开文件，位置指针自动在末尾

• 如果想要随意读写文件的任意位置，那么可以通过手动设置文件位置指针的位置

  #include <stdio.h>
  fseek	ftell	rewind
  int fseek(FILE *stream,long offset,int whence);
  stream：文件指针
  offset：偏移值
  whence：基础位置
      SEEK_SET	文件开头
      SEEK_CUR	当前位置
      SEEK_END	文件末尾
  返回值：调整成功（调整后位置指针还在文件中）返回0，失败返回-1。
  void rewind(FILE *stream);
  功能：把文件位置指针设置到文件开头
      
  long ftell(FILE *stream);
  功能：获取当前文件位置指针的位置
  返回值：在第几个字节
      
  int fgetc(const *stream);
  功能：从文件中读一个字节
  返回值：失败，读取完毕返回EOF（-1）
  char *fgets(char *s,int size,FILE *stream);
  功能：读取一行字符串到s中，最多读size-1个
  int fputc(int c,FILE *stream);
  功能：读取一个字符到文件中
  返回值：成功返回非负整数，失败返回-1；
  int fputs(int ,FILE *stream)
  功能：写一个字符串到文件中
  返回值：成功返回非负整数，失败返回-1；
  int remove(const char *pathname);
  功能：删除文件
  pathname：文件路径
  返回值：成功返回0，失败返回-1；
  int rename(const char *oldpath,const char *newpath)；
  功能：文件重命名
  返回值：成功返回0，失败返回-1；
  

练习：实现cp命令 （cp dest src）( fread fwrite )

先读，存起来char buf[256],然后写进去，循环直到读完为止

#include <stdio.h>
int main(int argc,const char* argv[]){
    if( 3 == argc ){
        printf("User: ./cp src dest");
    }
    FILE* src = fopen(argv[1],"r");
    if( NULL == src ){
        printf("源文件不存在，请检查命令！\n");
        return -1;
    }
    FILE* dest = fopen(argv[2],"r");
    if( dest ){
        printf("目标文件已存在，是否覆盖！(y\\n)");
        char cmd = getcher();
        if( cmd != 'Y' && cmd != 'y' ){
            printf("停止拷贝\n");
            fclose(src);
            fclose(dest);
            src = NULL;
            dest = NULL;
        }
    }
    fclose(dest);
    dest = fopen(argv[2],"w");
    if( NULL == dest ){
        printf("文件路径权限有误，请检查\n");
    }
    char buf[250] = {};
    int ret = 0;
    while( ret = fread(buf,1,sizeof(buf),src) ){
        fwrite(buf,1,ret,dest);
    }
    fclose(src);
    fclose(dest);
    src = NULL;
    dest = NULL;
}

命令行参数：main函数的参数

• 是为了获取 a.out命令行中的参数
• argc 代表了命令行参数的个数
• argv 每个参数字符串的首地址

注意：a.out是argv[0];

C语言大项目：学生信息管理系统

数据结构

• 什么是数据结构？

  • 数据结构的起源

    1968年，美国高德纳教授，《计算机程序设计艺术》第一卷《基本算法》，开创了数据结构和算法的先河

    数据结构是研究数据之间关系和操作的学科，而非计算方法

    数据结构 + 算法 = 程序 美国沃斯提出 这句话揭露了程序的本质

  • 数据结构相关基础概念

    • 数据：所有能够输入到计算机中，能够被程序处理的描述客观事务的符号
    • 数据项：有独立含义的数据的最小单位，也称为数据域
    • 数据元素：组成数据的有一定含义的基本单位，也称为节点，结点，记录
    • 数据结构：相互之间存在，有一种或多种特殊关系的数据元素的集合
    • 算法：数据结构中所具备的功能，解决某种特定问题的方法

• 数据结构的三大方面

  • 数据之间的逻辑关系
  • 数据的存储关系
  • 数据结构的运算

• 数据结构的逻辑关系和存储关系

  • 逻辑关系：
    集合：数据元素同属于一个集合，但元素之间没有任何关系

    ? 线性结构：数据元素之间存在一对一关系

    ? 树形结构：数据元素之间存在一对多关系

    ? 图型结构：数据元素之间存在多对多关系

  • 存储（物理）关系：

    ? 顺序结构：数据元素存储在连续的内存中，用数据元素的相对位置来表示关系

    ? 优点：支持随机访问，访问速度查找效率高，适合用于查找数据频繁的结构

    ? 缺点：对插入，删除时，效率低不方便，内存空间利用率低，要求高

    ? 链式结构：数据元素存储在彼此相互独立的内存中，每个独立的元素也叫做结点，每个结点中增加一项数据项用于存储其它相关结点的地址，以此表示结点之间的关系

    ? 优点：空间利用率极高，对内存要求不高。插入，删除，更快更方便

    ? 缺点：不支持随机访问，只能从头到尾逐个访问

    注意：逻辑结构，存储结构采用哪种根据实现难度，空间，时间要求，操作习惯等方面综合考虑选择适合的结构

• 逻辑结构与存储结构的关系：

  ? 线性表 顺序 链式

  ? 树 链式 顺序

  ? 图 顺序 + 链式

• 数据结构的运算

  • 创建数据结构 create/creat
  • 销毁数据结构 destory
  • 清空数据结构 clean
  • 数据结构排序 sort
  • 插入元素 insert
  • 删除元素 delete
  • 访问元素 access
  • 查询元素 query
  • 修改元素 modify
  • 遍历数据结构 ergodic show print

线性表

顺序表和链式表实现

顺序表：

• 数据项：
  表的容量
  存储元素的连续内存首地址
  当前元素的数量
  • 运算：
    创建，销毁，清空，插入，删除，访问，查询，修改，排序，遍历

注意：1.保证数据元素的连续性。2.不要越界

链式表：list（《大话数据结构》）

• 元素（结点）的数据项：

  ? 数据域：可以是任何类型的若干个数据项
  ? 指针域：指向下一个结点

  由若干个结点通过指针域连接到一起形成了链表

  不带头结点的单链表：

  ? 第一个结点的数据域存储有效数据

  ? 缺点：添加，删除结点时，可能会修改第一个结点的指针，参数就需要使用二级指针，才能更改指针的指向，比较麻烦

  带头结点的单链表：

  ? 第一个结点的数据域不存有效元素，仅仅只是使用它的指针域永远指向链表的第一个数据有效的结点

  ? 优点：添加，删除时会比不带头结点的链表更方便

  ? 注意：其它操作要从头结点的下一个结点开始

功能受限的表结构

对表结构的部分功能加以限制，形成特殊的表结构

栈：只有一个进出口的表结构，先进后出，又名 FILO

• 栈的应用：
  函数的调用，栈内存的特点
  生产者和消费者模型（仓库 - 》栈 ）
  表达式解析

• 顺序栈：
  数据域：存储元素的内存首地址，栈的容量，栈顶位置
  运算：创建，销毁，入栈，出栈，栈满，栈空

• 链式栈：
  栈结构数据项：栈顶结点，结点数量

  ? 运算：创建，销毁，入栈，出栈，

• 栈的常考笔试题面试题
  某个序列是一个栈的入栈顺序，判断，哪个是正确的出栈顺序(有可能边进边出)

  1	2	3	4	5	入栈
  1	2	3	4	5	YES
  3	2	1	4	5	YES
  3	1	2	5	4	NO
  

• 两个容量相同的顺序栈，如何能够让空间利用率最高

练习：实现一个函数，序列a为入栈顺序，判断序列B是否是A的出栈顺序

队列：有两个端口，一个端口只能入队，另一个只能出队先进先出，又名FIFO

? 顺序队列：

? 数据项：存储内存首地址，容量

? 队头，队尾

? 运算：创建，销毁，入队，出队，队空，队满，查队头，查队尾，队中数量

• 顺序队列的注意点：由队头下标front加对尾下标tail组成，人队tail++，出队front++，为了让队列能够反复使用，我能把队列相像成一个环，因此当front和tail加1后，都要用队列容量求余再重新赋值

  ? front = (front+1)%cal; tail = tail%cal

如何判断队空队满：二外多申请一个元素的内存

额外多申请一个元素的内存

? 队空： front == tail

? 队满： （tail+1）%cal == front

? 代价是空了一个位置不能使用，计算数量时较麻烦(最常考)

? 计算数量：(tail-front+cal)%cal

另一种方式是队列结构中增加一项数据项用于记录队列中元素个数，判断或空或满直接判断该数据即可，更方便

链式表

? 由链表结点组成的队列结构

? 数据项：

? 队头指针

? 队尾指针

? 结点数量

? 运算：创建，销毁，队空，入队，出队，队头，队尾

队列应用：

• 消息队列
• 树的层序遍历(使用队列)
• 图的广度优先遍历(使用队列)
• 封装线程池，数据池

练习：使用两个相同顺序的栈，来模拟一个队列

提示：栈2必须为空，栈1才能入栈2。栈1到栈2必须一个不留

Queue{
    stack* s1;
    stack* s2;
}

封装链表：

? 尾添加的效率低，非法下标的判断效率也非常低

• 单链表
  结点：
  数据域
  指针域
  单链表数据项：头结点，尾结点，结点数量

• 静态链表
  结点：
  数据域
  指针域
  静态链表的结点存储在连续的内存中，通过游标来访问下一个结点
  这种链表在插入删除时时需要修改游标的值，而不用中请，释放结点内存就可以达到类似链式结构的效果

  注意：静态链表牺牲了随机访问的功能，也没有达到链表动态申请内存的效果，只是给没有指针的编译语言实现链表的一种方式，适用范围不大

• 循环链表
  链表的最后一个结点的next不再指向NULL，而是指向头结点，这种链表称为单向循环链表，简称循环链表。优点是可以通过任意结点来遍历整个链表

• 双向链表

  ? 结点：

  ? 前驱指针： prev

  ? 数据域：

  ? 后继指针： next

  ? 数据项：

  ? 头结点

  ? 结点数量

  ? 特点：在任意结点都可以遍历整个列表。相比单链表，删除，插入更直接。

  如果已知结点位置，可以选择从前往后，或者从后往前，访问比单链表更有效率。

树型结构

? 树的基本概念：一种表示层次关系（一对多）的数据结构，有且只有一个特点的结点，该结点没有前驱结点，被称为根结点。剩余的n个互不相交的子集也都是一棵树，都被称为根节点的子树

注意：树型结构具有递归型（树中有树）

• 树的表示方式：倒悬树，嵌套法，凹凸法

• 树的专业术语：

  ? 结点：组成树的基本元素，同时它也是一棵树

  ? 结点的度：该结点子树的数量

  ? 树的度：一棵树中，最大的节点的度称为树的度；

  树的深度（高度）：树的最大乘次数

  ? 结点的乘次：根节点的层次为1，它的孩子层次为2，孩子的孩子层次为3

  ? 叶子结点：结点的度为0的结点

  双亲结点和孩子结点：结点的子树被称为该结点的孩子结点，该结点就是被称为孩子的双亲结点

  ? 兄弟结点：具有同一个双亲结点的结点，互为兄弟结点

  ? 祖先结点：从根节点出发到该结点，路径上经过的所有结点都称为该结点的祖先

  ? 子孙结点：一个结点的子树中任意一个结点都是它的子孙

  ? 堂兄弟结点：双亲结点互为，兄弟结点。

• 树的存储

  • 树可以顺序存储，链式存储，还可以混合存储

  • 可以根据存储的信息不同，树有以下存储方式：

    双亲表示法：顺序存储

    ? 位置 data 双亲下标

    ? 0 A -1(EOF)

    ? 1 B 0

    ? 2 C 0

    ? 3 D 1

    ? 4 E 1

    ? 5 F 1

    ? 6 G 2

    • 优点：方法寻找双亲
    • 缺点：查找孩子结点时麻烦

    孩子表示法：

    ? 顺序存储：耗费内存。array_son。

    ? 链式存储：节约了内存空间。ListHead。

    ? 位置 data 子节点下标（son_arr存储子节点下标）

    ? 0 A [1,2]

    ? 1 B [3,4,5]

    ? 2 C [6]

    ? 3 D []

    ? 4 E [7]

    ? 5 F

    ? 6 G

    ? 7 H

    • 优点：查找孩子下标方便
    • 缺点：查找双亲下标不便

? 兄弟表示法：

? 链式

? 双亲只存储第一个子节点 数据 链式指向所有兄弟节点

? 优点：可以方便找所有兄弟节点

? 缺点：找双亲不便

注意：普通数不常用，一般会使用二叉树进行存储

二叉树

? 一种常用的数据结构，比普通树处理起来要简单，而且普通也比较方便地转换成二叉树。

? 定义：节点的度为2。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 [1] 。

? 满二叉树：每层的节点数都是2^(i-1)，则这种树就是满二叉树

1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 [4] 。

2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 [4] 。

二叉树性质（重点）

**性质1：**二叉树的第i层上至多有2^(i-1)（i≥1）个节点 [6] 。

**性质2：**深度为h的二叉树中至多含有(2^h)-1个节点 [6] 。

**性质3：**若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1 。

**性质4：**具有n个节点的满二叉树深为log2n+1。

**性质5：**若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点： [6]

当i=1时，该节点为根，它无双亲节点 。

当i>1时，该节点的双亲节点的编号为i/2 。

若2i≤n，则有编号为2i的左节点，否则没有左节点 。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。

二叉树的操作

? 构建，销毁，遍历，高度，密度，插入，删除，查询，求左，求右，求根。

二叉树的存储

顺序存储：必须要安照完全二叉树的格式，把每个节点按从上到下，从左到右的顺序依次存入连续的内存中，如果有空位置则使用特殊数据代替存入

数据项：存储节点的内存首地址，

链式存储

二叉树的遍历

• 前序遍历：根，左，右
• 中序遍历：左，根，右
• 后序遍历：左，右，根

注意：无论是前中后，由根节点决定，并且左右子树的遍历顺序不会改变

根据前序+中序，或者，后序+中序 就可以还原一颗树

• 层序遍历：从上到下，从左到右，依次遍历，一颗树。

注意：层序遍历，配合队列使用

有序二叉树

• 左子树的数据小于根，右子树的数据大于根，这种树被称为有序二叉树，二叉树搜索树，二叉排序树

注意：这种树的节点需要频繁地插入，删除，因此不适合顺序存储

有序二叉树的中序遍历刚好就是升序或降序，所以有序二叉树也是一种排序算法，查找又天然是二分查找。

练习：

1. 把一棵二叉树转换为它的镜像树。
2. 输入两棵二叉树A，B，判断B是不是A的子结构（我们约定空树不是任意一个树的子结构）。
3. 将一棵有序二叉树转换成一个有序的双向链表。
4. 计算出有序二叉树中倒数第K个大的数。
5. 判断一个二叉树是否对称。
6. 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

线索二叉树

• 规律：在N个节点的链式二叉树中必定有N+1个空指针域（NULL指针）。
• 有序链式二叉树中有很多的空指针。如果要使之有意义，可以让它们的空指针指向下一个，或前一个，这样在遍历时，可以不用递归，而可以使用循环遍历，提高树的遍历速度。

中序线索二叉树节点数据项

? 数据

? 左子树指针

? 右子树指针

? 由子树指针标准位

实现过程：

1. 创建有序二叉树
2. 建立线索
3. 通过线索遍历二叉树

选择树(胜者树，败者树)

? 是一种完全二叉树，待比较的数据都存储在最后一层，根节点是根据左右子树其中一个生成，因此更节点是最大或者最小的，选择树的功能是快捷地找出最大值或最小值。

堆：是一种完全二叉树

• 大顶堆（大根堆）：根节点比左右子树大
• 小顶堆（小根堆）：根节点比左右子树小

数据项：

? 存储数据的内存首地址

? 容量

? 数量

平衡二叉树(AVL树)

前提是有序的二叉树，它的左右子树的高度不超过1，而且它的所有子树也满足这个条件

如果一个有序二叉树呈现单支状(类似链表)，它的查找效率接近链表，因此只有达到平衡时它的查找效率最高。

由于节点的值受限，因此只能通过调整达到有序，而不能进行值的修改

二叉树不平衡的基础原因： Y

? X - 以Y为轴向右旋转 Z X

? / \ T1

? Y T1

Z

红黑树(了解)

红黑树是一种自平衡树，它不是根据子树的高度差来调整平衡的，而是给节点设置一种颜色，来达到平衡。

红黑树的特性：

1. 每个节点或者是黑色，或者是红色
2. 根节点必须是黑色
3. 每个叶子节点（NULL）是黑色
4. 如果一个节点是红色，则它的子节点必须是黑色。(不能有两个红色的节点)
5. 从一个节点出发，到该节点的子孙节点的所有路径上包含了相同数量的黑色节点
   保证大致上红黑树是平衡的（最长路径不超过最短路径的两倍）。
6. 插入的节点一定是红色

红黑树插入后的调整：

• 插入的节点一定是红色

1. 如果父节点是黑色，直接插入

2. 如果父节点是红色，需要调整

   ? 叔叔不存在 or 叔叔为黑色

   ? 进行 左旋 or 右旋

   ? 祖父节点置红，父节点置黑

   ? 叔叔存在且为红色

   ? 祖父置红，父节点和叔叔置黑

   ? 把祖父节点当做当前节点

优点：插入，删除的效率比AVL树高

缺点：没有AVL树平均，查找效率没有AVL树高，但也并不差

哈夫曼树(了解)

• 基本概念：

  • 路径长度：从一个节点到另一个节点之间的路径条目数。（根节点到第N层节点的路径长度为N-1）
    数的路径长度：从根节点出发，到每个节点的路径长度和。
    节点的权：若将书中节点赋予一个有某种意义的数值，该数值称为该节点的权
    节点的带权路径长度：从根节点出发到该节点的路径长度与该节点的权的乘积。
    树的带权路径长度：所有的叶子节点的带权路径长度的和，称为WPL
    (哈夫曼树是衡量一颗带权二叉树优劣的关键，目的是为了生成一颗WPL最小的带权二叉树）

• 构建哈夫曼树：

  • 把N个带权节点存入一个集合中F中，把每个节点左右子树置空
  • 从F中选取权值最小的两个节点作为左右子树构建成一颗新的二叉树，且新的根节点的权为左右子树的权值之和
  • 从F中删除刚刚选出来的两个节点，把新得到的根节点放入F中
  • 重复2,3步骤，直到F中为空

• 哈夫曼编码：

  • 目的：解决当年远距离通信(电报)的数据传输的最优解

    待发送的文字：BADCA DFEED

    方法1：转成二进制发送 A 000 B 001 共30个字符

    方法2：

    • 根据文字出现频率，构建哈夫曼树
      • 假设频率：A27 B8 C15 D15 E30 F5
        • A(01) B (1001) C (101) D (00) E (11) F (1000)
          • BADCA DFEED（1001 01 00 101 01 00 1000 11 11 00）
    • 根据哈夫曼树的左右分支为0，右分支为1，则从根节点到叶子节点经过的路径分支所组成的0,1编码序列为该对应字符的哈夫曼编码

  • 作用：数据压缩，文件压缩的其中一种方式

数组与矩阵

• 数组：存储空间连续的表结构

• 矩阵：带二维信息的数据，一般用二维数组来存储矩阵

• 特殊矩阵：

  • 稀殊矩阵：有效的信息数据不多，绝大多数都是无效信息数据不需要存储，没有特定的标准，全凭感觉

    这些矩阵如果使用二维数组来存储的话，会非常浪费存储空间，为了节约空间，我们可以对这些矩阵进行压缩

    • 普通的稀蔬矩阵压缩方式：
      • 三元组：有三个数据项：行，列，值。

  • 上三角矩阵

    [X][X][X][X]
    [ ][X][X][X]
    [ ][ ][X][X]
    [ ][ ][ ][X]
    /*
    压缩方法：使用一维数组进行存储
    上三角矩阵N行N列:	第i行	第J列
    一维数组长度：n*(n+1)/2
    对应关系：(j+1)*j/2+i
    数据位置：i >= j
    */
    

  • 下三角矩阵

    [X][ ][ ][ ]
    [X][X][ ][ ]
    [X][X][X][ ]
    [X][X][X][X]
    /*
    压缩方法：使用一维数组进行存储
    上三角矩阵N行N列:	第i行	第J列
    一维数组长度：n*(n+1)/2
    对应关系：(i+1)*i/2+j
    数据位置：i <= j
    */
    

  • 对称矩阵

    [-][1][2][3]
    [1][-][ ][ ]
    [2][ ][-][ ]
    [3][ ][ ][-]
    

  • 对角矩阵、对状矩阵

    [-][1][ ][ ]
    [2][-][3][ ]
    [ ][4][-][5]
    [ ][ ][6][-]
    /*
    数组长度：3*N-2
    对应关系：i*2+j
    i和j要满足：abs(i-j) <= 1  的位置有值
    */
    

图

• 图型结构：由有穷且非空的顶点和顶点之间边的集合组成
• 通常表示：G(V,E) G表示一个图，V是图中顶点集合(元素)，E是图中所有边(元素之间的关系)的集合
• 无向图：
  • 边用(A,B)方式表示，A到B之间互通
• 完全无向图：
  • 在无向图中，任意两个顶点之间都有边，这种叫完全无向图。
  • 含有N个顶点的完全无向图中，共有N*(N-1)/2
• 有向图：
  • 边<A,B>方式表示，仅仅表示A点到B点的边，有向图中边也叫做弧，A是弧头，B是弧尾
• 有向完全图：
  • 在有向图中任意两个顶点之间都有方向相反的两条弧，这种图叫做有向完全图
  • 含有N个顶点的有向完全图中，共有N*(N-1)条边

注意：不讨论顶点到自身的边，且不讨论重复的边，这种图统称为简单图，数据结构中只研究简单图

稀疏图：顶点多边少的图称为稀疏图，反之称为稠密图。

边的权重：图中的边附带有意义的数据，这些数据叫做边的权重，带权重度图，也称为网

度：依附于顶点的边的数量称为该顶点的度，有向图中，度分为出度(从该顶点出发的弧的数量)，入度(指向该顶点的弧的数量)

路径：从一个顶点出发，到一个顶点之间，经过的边加路径

路径长度：路劲的边的条目树

环：图中从某个顶点出发，最终回到该点

回路：专指有向图，从某个点出发，最终会到该点

简单路径：边经过顶点序列中不重复的路径称为简单路径

简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复的回路称为简单回路

连通：如果顶点V到顶点V1之间路径，则成V和V1是连通的

连通图：任意顶点之间都是连通的，称之为连通图，如果一个图有N个低昂单则至少需要N-1条百年才能达到连通图

生成树顶点数为N，仅仅需要N-1条边的连通图，称之为生成树，如果个边配上权重，权重和最小的生成树称之为最小生成树

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "list_queue.h"

//	邻接矩阵
typedef struct Graph
{
    char* v;	//	顶点一维数组
    char* e;	//	边的二维数组
    int cnt;	//	顶点数量
}Graph;
Graph* create_graph(const char* str)
{
    //	申请邻接矩阵内存
    Graph*graph = malloc(sizeof(Graph));
    //	计算顶点数量
    graph->cnt = strlen(str);
    //	申请顶点所需堆内存
    graph->v = malloc(graph->cnt);
    //	存储数据
    strcpy(str->v,str);
    //	申请存储边所需内存
    graph->v = calloc(graph->cnt,graph->cnt);
    return graph;
}
bool add_edge(Graph* graph,char v1,char v2)
{
    int x = -1, y = -1;
    for(int i = 0 ; i < graph->cnt ; i ++ ){
        if( graph->v[i] == v1 ) x = i;
        if( graph->v[i] == v2 ) y = i;
    }
    if( x == -1 || y == -1 ) return false;
    graph->e[x*graph->cnt+y] = 1;
    return true;
}
void show_graph(Graph* graph)
{
    printf(" ");
    for(int i = 0 ; i < graph->cnt ; i ++ ){
        printf(" %c",graph->v[i]);
    }
    pirntf("\n");
    for(int i = 0 ; i < graph->cnt ; i ++ )
    {
        printf("%c ",graph->v[i]);
        for(int j = 0 ; j < graph->cnt; j ++){
            printf("%hhd ",graph->e[i*graph->cnt+j]);
        }
        printf("\n");
    }
}
int od_graph(Graph* graph,char v)
{
    for(int i = 0 ; i < graph->cnt ; i ++ )
    {
        if( v == graph->v[x] )
        {
            int od = 0;
            for(int j = 0 ; j < graph->cnt ; j ++ )
            {
                od += graph->e[x*graph->cnt+y];
            }
            return od;
        }
    }
    return -1;
}
int id_graph(Graph* graph)
{
    for(int y = 0 ; y < graph->cnt ; y ++ )
    {
        if( v == graph->v[y])
        {
            int id = 0;
            for(int x = 0 ; x < graph->cnt ; x ++ )
            {
                id += graph->e[x*graph->cnt+y];
            }
            return id;
        }
    }
    return -1;
}
void _DFS(Graph* graph,int i,char* vflag)//	从第I个顶点进行深度优先遍历
{
    if( vflag[i] ) return;
    printf("%c ",graph->v[i]);
    vflag[i] = 1;
    for(int j = 0 ; j < graph->cnt ; j ++ ){
        if( graph->e[i*graph->cnt+j] ) _DFS(graph,j,vflag);
    }
}
void DFS_show(Graph* graph)
{
    //	给顶点加标志位
    char vflag[graph->cnt];
    memset(vflag,0,graph->cnt);
    for(int i = 0 ; i < graph->cnt ; i ++ )
    {
        _DFS(graph,0,vflag);
    }
}
void BFS_show(Graph* graph)
{
    char vflag[graph->cnt];
    memset(vflag,0,graph->cnt);
}
int main(int argc,const char* argv[])
{
    Graph* graph = create_graph("ABCDEFG");
}

图的遍历：深度优先遍历和广度优先遍历

• 深度优先遍历（DFS）：
• 广度优先遍历（BFS）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list_queue.h"
//	边
typedef struct Edge
{
    int index;			//	边指向顶点的下标
    struct Edge* next;	//	指向下一条边
}Edge;
//	顶点
typedef strcut Vertex
{
    char vertex;	//	顶点数据
    Edge* first;	//	指向该顶点的第一条边
}Vertex;
//	图
typedef struct Graph
{
    Vertex* v;	//	顶点数组
    int cnt;	//	顶点数量
}
int od_graph(Graph* graph,char v)
{
}
int main(){
     
}

算法

• 数据结构中的算法，指的是数据结构所具备的功能（决绝待定概念的方法）

• 评价一个算法：

  • 时间复杂度：算法的执行次数来代表算法的时间复杂度
    一般使用O(公式) 一般忽略常数
  • 空间复杂度：执行一个程序所需要的内存空间大小，是对一个算法在运行工程中临时占用存储空间大小的衡量。（一般只要算法不涉及东岱分配的内存以及递归，通常空间复杂度为O(1)）

  注意：对于一个算法而言，其时间复杂度与空间复杂度往往是相互影响的，没有一个标准，需要结合实际

分治：分而治之，将一个大且复杂的问题，分解成小且简单的问题

• 实现分治的方法：循环，递归

• 查找算法：

  • 顺序查找

    • 对待查找的数据没有要求，从头到尾逐一比较，在小规模的查找中比较常见，

    #include <stdio.h>
    #include <stdlib.h>
    
    #define swap(a,b) {typeof(a) t = (a); (a) = (b) ; (b) = t;}
    #define show_arr(arr,len) { for(int i = 0 ; i < len ; \
    printf("%d ",arr[i++]) ); }
    
    //	顺序查找
    int order_search(int* arr,int len,int key){
        for(int i = 0 ; i < len ; i ++ ) {
            if( key == arr[i] ) return i;
        }
        return -1;
    }
    //	计数排序
    void count_sort(int* arr,size_t len) {
        int max = arr[0], min = arr[0];
        for(int i = 1 ; i < len ; i ++ ) {
            if( arr[i] > max ) max = arr[i];
            if( arr[i] < min ) min = arr[i];
        }
        //	哈希表
        int* tmp = calloc(4,max-min+1);
        //	标记哈希表
        for(int i = 0 ; i < len ; i ++ ){
            tmp[ arr[i] - min ] ++ ;
        }
        for(int i = 0, j = 0; i <= max-min ; i ++ ) {
            while( tmp[i]-- ) {
                arr[ j ++ ] = i + min;
            }
        }
    }
    //	哈希查找
    bool hash_search(int* arr,int len,int key){
        //	直接定址法
        int hash[1000000] = {};
        for(int i = 0 ; i < len ; i ++ ){
            hash[ arr[i] ] ++ ;
        }
        return hash[ key ];
      //	数据分析法
        int max = arr[0], min = arr[0];
      for(int i = 0 ; i < len ; i ++ ){
            if( arr[i] > max ) max = arr[i];
          if( arr[i] < min ) min = arr[i];
        }
        int hash[ max-min+1 ];
      memset(hash,0,sizeof(hash));
        for(int i = 0 ; i < len ; i ++ ){
          hash[ arr[i-min] ] ++;
        }
      return hash[ key-min ];
    }
    void (){
        bool flag = true;
        for(int i = len-1 ; i > 0 && flag ; i -- ){
            flag = false;
            for(int j = 0 ; j < i ; j ++ ){
                if( arr[j] > arr[j+1] ){
                    swap(arr[j],arr[j+1]);
                    flag = true;
                }
            }
        }
    }
    void select_sort(TYPE* arr,size_t len){
        for(int i = 0 ; i < len-1 ; i ++ ){
            int min = i;
            for(int j = i + 1 ; j < len ; j ++ ){
                if( min > arr[j] ) min = j;
            }
            if( i != min ) swap(arr[i],arr[min]);
        }
    }
    //	插入排序
    void insert_sort(TYPE* arr,size_t len){
        for(int i = 1 , j = 0 ; i < len ; i ++ ){
            int temp = arr[i];
            for( j = i-1 ; j >= 0 && arr[j] > temp; j -- ){
                arr[j+1] = arr[j];
            }
            if( j+1 != i ) arr[j+1] = temp; 
        }
    }
    //	希尔排序
    void shell_sort(TYPE* arr,size_t len){
        for(int k = len/2 ; k > 0 ; k /= 2 ){
            for(int i = k ; i < len ; i ++ ){
                int temp = arr[i];
                for(int j = i-k ; j >= 0 && arr[j] > temp; j -= k ){
                    arr[j+k] = arr[j];
                }
                if( j+k != i ) arr[j+1] = temp; 
        	}
        }
        
    }
    int main(){
        int arr[10];
        for(int i = 0 ; i < 10 ; i ++ ) {
            arr[i] = rand()%100;
            printf("%d ",arr[i]);
        }
    }
    

  • 二分查找

    • 待查找的数据必须有序，从数据中间位置开始比较查找。
    • 时间复杂度：O(logN)

  • 块查找

    • 是一种数据处理的理想，不是一种特定的算法，当数据量非常多时，可以先把数据进行分块处理，然后再根据分块的条件进行查找

  • 哈希查找 (Hash)

    • 数据 经过 哈希函数 计算出数据在哈希表中的位置，然后标记位置，方便之后的查找，它的时间复杂度可以达到O(1)
    • 哈希函数的设计方法：
      • 直接定址法：直接把数据当做哈希表的下标，把哈希表中该下标的位置+1
      • 数据分析法：
      • 平方取中法，折叠法，随机数法，但都无法保证哈希数据的唯一性，出现所谓的哈希冲突，一般使用链表解决
    • Hash函数的应用：MD5,SHA-1都属于Hash算法中的应用

• 排序算法：

  • 排序算法的稳定性：如过有值相同的数据，在排序的过程中的全程中都不会改变它们的先后顺序，则认为该排序算法是稳定的

  • 冒泡排序：将相邻的左右数据进行比较，按一定规则（升序：左比右大，交换。降序：左比右小，交换），该算法对数据的有序性比较敏感。如果，待排序的数据基本有序，则效率高。

    • 时间复杂度：最优O(n)，平均：O(n^2)
    • 稳定

  • 选择排序：假定最开始的位置是最小值，并记录计入下标min，然后与后面的数据比较，如果有比min为下标的数据还要小，则更新min，最后判断如果min的值发生了该变，则交换min位置的数据与最开始的数据。

    • 时间复杂度：O(n^2)

    虽然选择排序的时间复杂度较高，但是数据交换次数少，因此实际运行效率并不慢

    是冒泡排序的变种，但是没有对数据有序敏感性，数据混乱情况下比冒泡块

    注意：算法的时间复杂度不能代表算法的实际时间，有时候时间复杂度高的反而速度更快

• 插入排序：将数据看做两部分，一部分是有序的，将剩余数据逐个插入到有序的

  • 时间复杂度O(n^2)
  • 稳定

• 希尔排序：是在插入排序的增强版，由于插入排序数

• 快速排序：找到一个标杆，备份标杆的值val，一面从左找比val大的数，找到后，交换给P赋值，更新标杆P的位置到左标杆；在右边找比val小的数，找到后也赋值给P，更新P标杆到右标杆的位置。最终形成左边比右边小，右边比左边大。之后，用同样方法进行快排。

  • 时间复杂度：O(NlogN) 不稳定 快速排序的综合性能最高。

  #define TYPE int
  void _quick_sort(TYPE* arr,size_t left,int right){
      if( left >= right ) return;
      //	计算标杆下标
      int pi = (left+right)/2;
      //	备份标杆的值
      TYPE pv = arr[pi];
      //	备份左右标杆下标
      int l = left, r = right;
      while( l < r ){
          //	在标杆pi左边找比标杆大的数
          while( l < pi && arr[l] <= pv ) l++;
          if( l < pi ){
              //	找到了比pv大的数
              arr[pi] = arr[l];
              //	更新pi
              pi = l;
          }
          //	从pi的右边找比PV小的数
          while( r > pi && arr[r] >= pv ) r--;
          if( r > pi ){
              //	找到比pv小的数
              arr[pi] = arr[r];
              //	更新pi
              pi = r;
          }
      }
      //	pi左边小于PV，右边大于PV，还原PV
      arr[pi] = pv;
      if( pi - left > 1 ) _quick_sort(arr,left,pi-1);
      if( right - pi > 1 ) _quick_sort(arr,pi+1,right);
  }
  void quick_sort(TYPE* arr,size_t len){
      _quick_sort(arr,0,len-1);
  }
  

• 归并排序：先把一组待排序的数据分成单独的个体，存放到临时空间中，然后两两比较合并。

  • 时间复杂度：O(NlogN) 稳定