一.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;}}
}