一.Makefile
1. 功能：
管理工程代码的编译和链接
一键化实现代码工程的编译和管理。
时间戳：根据时间戳，可以只编译发生修改后的文件
gcc编译：xxx.c ------>二进制指令：xxx. o-----链接->可执行程序a.out
1)预处理：gcc -E test.c -o test.i 对预编译指令都做相应的处理
2)编译：gcc -S test.i -o test.s 编译成汇编指令代码
3)汇编：gcc -c test.s -o test.o 将汇编指令代码转化为目标文件
4)链接：gcc test.o -o test 将目标文件与库文件（静态库或动态库）链接得到可执行文件。
2. Makefile基本语法和相关操作
（1）创建一个Makefile文件
Makefile makefile
（2） 编译规则
目标文件：依赖的源文件（多个源文件可以通过空格隔开）
编译方法：
-I ： 指定头文件存放位置
-L : 指定库存放的位置
gcc main.c queue.c tree.c -o app -g -lm -I../include -L../lib
（3）编译：
make : 执行Makefile，进行编译源码
make clean ： 删除可执行程序，二进制文件
4.变量
（1） 系统变量
$@: 代表目标文件
$^: 代表所有依赖文件
$<: 代表第一个依赖文件
（2）自定义变量
变量名=值
+= 在原来变量内容的基础上增加
:= 在原来的基础上覆盖
变量引用：使用变量中的内容
$(变量名)
#要生成的目标可执行文件
DST=app#生成目标可执行文件需要的源二进制文件
SRC=main.o
SRC+=queue.o
SRC+=tree.o
#编译器
CC=gcc
#编译时需要的链接或者选项标志
FLAG=-g -lm
#指定需要的头文件的位置
INC=../include
#指定需要的库的位置
LIBS=../lib#编译规则
$(DST):$(SRC)$(CC) $^ -o $@ $(FLAG) -I$(INC) -L$(LIBS)#生成可链接的二进制文件
%.o:%.c$(CC) -c $^ -o $@ $(FLAG) -I$(INC) -L$(LIBS)#清除目标
clean:rm $(DST) *.o
二.算法
程序 = 数据结构 + 算法
算法：解决特定问题的求解步骤
衡量算法：
1.正确性： 语法正确， 合法的输入能得到合理的结果。 对非法的输入，给出满足要求的规格说 明， 对精心选择，甚至刁难的测试都能正常运行，结果正确
2. 可读性：便于交流，阅读，理解 高内聚 低耦合
3. 健壮性：输入非法数据，能进行相应的处理，而不是产生异常
4. 高效率(时间复杂度)
5. 低存储（空间复杂度）
算法时间复杂度
执行这个算法所花时间的度量
将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。
一般用大O表示法：O（n）-----时间复杂度是关于数据n的一个函数
随着n的增加，时间复杂度增长较慢的算法时间复杂度低
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
时间复杂度的计算规则
1.用常数1 取代运行时间中的所有加法常数
2.在修改后的运行函数中，只保留最高阶项。
3.如果最高阶存在且系数不是1，则去除这个项相乘的常数。
排序算法：
排序算法的稳定性:对于两个相同的数据，经过排序，两个相同数据的相对位置没有发生变化，这 就是一个稳定的排序算法。
（1）选择排序
将待排位置的数据和后续的数据依次进行比较，将小的存放在待排位置， 经过一趟，优先排好最小值。
时间复杂度：O（n^2） 稳定性：不稳定
void choice_sort(int *a,int len)
{int i,j,t;for(i = 0;i < len - 1;++i){for(j = i + 1;j < len;++j){if(a[i] > a[j]){t = a[i];a[i] = a[j];a[j] = t;}}}
}（2）冒泡排序
相邻两两比较，优先排好最大值。
时间复杂度：O（n^2） 稳定性：稳定
void bobble_sort(int *a,int len)
{int i,j,t;for(j = len - 1;j > 0;--j){for(i = 0;i < j;++i){if(a[i] > a[i + 1]){t = a[i];a[i] = a[i + 1];a[i + 1] = t;}}}
}
（3）插入排序
将待排的元素，依次插入到一个有序序列中，确保插入后仍然有序。
时间复杂度：O（n^2） 稳定性：稳定
void insert_sort(int *a,int len)
{int i,j,t;for(i = 1;i < len;++i){j = i;t = a[i];while(j > 0 && a[j - 1] > t){a[j] = a[j - 1];--j;}a[j] = t;}
}（4）快速排序
选定基准值，从两头分别和基准值比较，比基准值大的向后，比基准值小的向前，优先排好基准值。
时间复杂度：O（nlogn） 稳定性：不稳定
void quick_sort(int *a, int begin, int end)
{if (begin >= end){return ;}int key = a[begin];int i = begin;int j = end;while (i < j){while (i < j && a[j] >= key){j--;}a[i] = a[j];while (i < j && a[i] <= key){i++;}a[j] =a[i];}a[i] = key;quick_sort(a, begin, i-1);quick_sort(a, i+1, end);}
（5）希尔排序
将待排的序列，按照增量分成若干个子系列，对子序列进行插入排序。
时间复杂度：O（nlogn）~ O（n^2） 稳定性：不稳定
void shell_sort(int *a,int len)
{int i,j,inc;for(inc = len / 2;inc > 0;inc /= 2){for(i = inc;i < len;++i){j = i;int t = a[i];while(j >= inc && a[j - inc] > t){a[j] = a[j - inc];j = j - inc;}a[j] = t;}}
}
