数据结构 树

makefileMakefile是一个自动化编译工具的控制文件用于管理程序的编译和链接过程。它定义了源文件之间的依赖关系并指定如何编译和链接程序。通过make命令执行 Makefile 中的指令。只重新编译修改过的文件避免重复编译自动化复杂的编译过程简化大型项目的构建管理提高开发效率Makefile 基本编写规则目标文件: 依赖文件列表[TAB]命令目标要生成的文件如可执行文件、目标文件依赖生成目标所需要的文件或目标命令从依赖生成目标的具体操作Makefile 基本语法1.自定义变量字符串的方式自定义变量的名称值 :给变量直接赋值在原变量基础上增加新值变量如果没有被赋值则赋新值如果之前有被赋值则保留原值引用变量$(变量名)使用该变量中的值2.系统变量$:目标文件$^:所有的依赖文件$:第一个依赖文件时间戳gccgcc编译分为四个阶段1.预处理展开宏头文件处理#相关gcc -E main.c -o main.i2.编译生成汇编代码将源文件编译成汇编程序gcc -S main.i -o main.s3.汇编生成目标文件将汇编指令转换成二进制指令gcc -c main.s -o main.o4.链接生成可执行文件完成函数库等的链接操作gcc main.o -o programMakefile 通过检查源文件的最后修改时间戳来判断是否需要重新编译。当执行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 idx0;//当前处理到数组的哪个位置索引 TNode_t *create_bin_tree() { DataType_t datatree[idx]; if(#data) { return NULL; } TNode_t *pnodemalloc(sizeof(TNode_t)); if(NULLpnode) { printf(error\n); return NULL; } pnode-datadata; pnode-plcreate_bin_tree(); pnode-prcreate_bin_tree(); return pnode; }前序遍历void pre_order(TNode_t *proot) { if(NULLproot) { 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 1get_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); }