数据结构 树

makefile

Makefile是一个自动化编译工具的控制文件，用于管理程序的编译和链接过程。它定义了源文件之间的依赖关系，并指定如何编译和链接程序。通过make命令执行 Makefile 中的指令。

• 只重新编译修改过的文件，避免重复编译

• 自动化复杂的编译过程

• 简化大型项目的构建管理

• 提高开发效率

Makefile 基本编写规则

目标文件: 依赖文件列表
[TAB]命令

• 目标：要生成的文件（如可执行文件、目标文件）

• 依赖：生成目标所需要的文件或目标

• 命令：从依赖生成目标的具体操作

Makefile 基本语法

1.自定义变量

字符串的方式
自定义变量的名称=值

= :=给变量直接赋值
+=在原变量基础上增加新值
=变量如果没有被赋值，则赋新值，如果之前有被赋值，则保留原值
引用变量
$(变量名)
使用该变量中的值
2.系统变量
$@:目标文件
$^:所有的依赖文件

$<:第一个依赖文件

时间戳

gcc

gcc编译分为四个阶段

1.预处理：展开宏，头文件，处理#相关

gcc -E main.c -o main.i

2.编译：生成汇编代码，将源文件编译成汇编程序

gcc -S main.i -o main.s

3.汇编：生成目标文件，将汇编指令转换成二进制指令

gcc -c main.s -o main.o

4.链接：生成可执行文件，完成函数，库等的链接操作

gcc main.o -o program

Makefile 通过检查源文件的最后修改时间戳来判断是否需要重新编译。当执行make命令时，它会对比目标文件（如可执行文件或目标文件.o）与对应源文件（如.c文件）的时间戳：

- 如果目标文件不存在，或其时间戳早于任一依赖源文件的时间戳，则认为源文件已被修改，需重新编译；
- 如果目标文件时间戳新于所有依赖源文件，则跳过编译，避免重复构建。

例如，若只修改了main.c，而link.c未改动，Makefile 会仅重新编译main.c生成新的main.o，再链接生成最终程序，而不重新编译未改动的文件，从而提升效率。

这一机制依赖于文件系统的时间戳记录，是 Make 自动化构建的核心逻辑 。

树

一对多的结构，由一个根节点和若干个分支节点构成的具有一对多关系的数据的集合

根节点：最顶层的节点

分支节点：有子节点的节点

叶子节点（终端节点）：没有子节点的节点

树的深度：树的层数

树的广度（度）：树中节点的度最大值为该树的度

节点的度：节点的子节点个数

二叉树

度为2的树是二叉树

满二叉树

在不增加层数的前提下，无法增加一个节点，这种二叉树就是一个满二叉树

完全二叉树

头文件定义

#ifndef _TREE_H #define _TREE_H typedef char DataType_t; typedef struct trnode { DataType_t data; struct trnode *pl; struct trnode *pr; }TNode_t;

二叉树创建

DataType_t tree[]={"ABE##F#I##DHM###J##"};//存储树的先序遍历序列（字符串） int idx=0;//当前处理到数组的哪个位置（索引） TNode_t *create_bin_tree() { DataType_t data=tree[idx++]; if('#'==data) { return NULL; } TNode_t *pnode=malloc(sizeof(TNode_t)); if(NULL==pnode) { printf("error\n"); return NULL; } pnode->data=data; pnode->pl=create_bin_tree(); pnode->pr=create_bin_tree(); return pnode; }

前序遍历

void pre_order(TNode_t *proot) { if(NULL==proot) { return ; } printf("%c",proot->data); pre_order(proot->pl); pre_order(proot->pr); }

中序遍历

void mid_order(TNode_t *proot) { if (NULL == proot) { return ; } mid_order(proot->pl); printf("%c", proot->data); mid_order(proot->pr); }

后序遍历

void pos_order(TNode_t *proot) { if (NULL == proot) { return ; } pos_order(proot->pl); pos_order(proot->pr); printf("%c", proot->data); }

节点个数

int get_tree_node_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } return 1+get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr); }

层数

int get_tree_layer_cnt(TNode_t *proot) { if (NULL == proot) { return 0; } int cntl = get_tree_layer_cnt(proot->pl); int cntr = get_tree_layer_cnt(proot->pr); return cntl > cntr ? cntl + 1 : cntr + 1; }

销毁

void destroy_bin_tree(TNode_t *proot) { if (NULL == proot) { return ; } destroy_bin_tree(proot->pl); destroy_bin_tree(proot->pr); free(proot); }