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

目录

一、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）
                        稳定性：稳定

（4）快速排序

                选定基准值，从两头分别和基准值比较，比基准值大的向后，比基准值小的向前，优先排好基准值。
                      时间复杂度：O（nlogn）             
                      稳定性：不稳定

（5）希尔排序

                将待排的序列，按照增量分成若干个子系列，对子序列进行插入排序。

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

（6）二分查找

                   前提：有序的序列
                   时间复杂度：O（logn）