当前位置：首页 > news >正文

数据结构——Makefile、算法、排序（2025.2.13）

news 2025/8/20 23:43:43

一、Makefile

1.功能

2.基本语法和相关操作

（1）创建Makefile文件

（2）编译规则

（3）编译

（4）变量

①系统变量

②自定义变量

二、算法

1.定义

2.算法的设计

（1）正确性

（2）可读性

（3）健壮性

（4）高效率

（5）低存储

三、练习

1.排序算法

（1）冒泡排序

（2）选择排序

（3）插入排序

（4）快速排序

（5）希尔排序

（6）二分查找

一、Makefile

1.功能

管理工程代码的编译和链接，可一键化实现代码工程的编译和管理。

时间戳：根据时间戳，可以只编译发生修改后的文件

2.基本语法和相关操作

（1）创建Makefile文件

vi Makefile 或 vi 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.算法的设计

（1）正确性

        ①语法正确
       ②合法的输入能得到合理的结果
       ③对非法的输入，给出满足要求的规格说明
       ④对精心选择，甚至刁难的测试都能正常运行，结果正确

（2）可读性

便于交流，阅读，理解高内聚低耦合

（3）健壮性

输入非法数据，能进行相应的处理，而不是产生异常

（4）高效率

时间复杂度需尽可能更低

（5）低存储

空间复杂度需尽可能更低

算法时间复杂度

即执行这个算法所花时间的度量

将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。

一般用大O表示法：O（n）----->时间复杂度是关于数据n的一个函数
随着n的增加，时间复杂度增长较慢的算法时间复杂度低

时间复杂度的计算规则

        ①用常数1 取代运行时间中的所有加法常数
        ②在修改后的运行函数中，只保留最高阶项。
        ③如果最高阶存在且系数不是1，则去除这个项相乘的常数。

三、练习

1.排序算法

        ①思想
        ②代码
        ③时间复杂度
        ④排序算法的稳定性:对于两个相同的数据，经过排序，两个相同数据的相对位置没有发生变化，这就是一个稳定的排序算法。

（1）冒泡排序

相邻两两比较，优先排好最大值

时间复杂度：O（n^2）
稳定性：稳定

（2）选择排序

将待排位置的数据和后续的数据依次进行比较，将小的存放在待排位置，经过一趟，优先排好最小值。
for(int i = 0; i < len-1; i++)
{
for (int j = i+1,; j < len; j++)
{
if (a[i] > a[j])
swap(a[i], a[j]);
}
}
时间复杂度：O（n^2）
稳定性：不稳定

（3）插入排序

将待排的元素，依次插入到一个有序序列中，确保插入后任然有序。
for (int i = 1; i < len; i++)
{
j = i;
int temp = a[i];
while (j > 0 && a[j-1] > temp)
{
a[j] = a[j-1];
--j;
}
a[j] = temp;
}
时间复杂度：O（n^2）
稳定性：稳定