Makefile和树

MakefileMakefile是用于管理项目构建过程的工具它通过定义规则和指令自动化编译、链接等步骤大大简化了开发者的工作基本概念Makefile 主要包括以下三部分内容目标 最终生成的可执行程序或中间文件依赖 生成目标所需要的源码文件命令实现编译的具体操作语句基本语法1. 自定义变量以字符串的方式定义 自定义变量的名称值 和: 给变量直接赋值 在原变量基础上增加新值? 变量如果没有被赋值则赋新值如果之前有被赋值则保留原值引用变量$(变量名) 相当于使用该变量中的值2. 系统变量$ : 目标文件$^ : 所有的依赖文件$: 第一个依赖文件3.时间戳gcc编译的4步骤预处理处理#相关的命令 gcc -E main.c -o main.i编译将源文件编译成汇编程序 gcc -S main.i -o mian.s汇编将汇编指令转换成二进制指令 gcc -c main.s -o main.o链接完成函数库等的链接操作 gcc main.o xxx.o -o a.out根据文件修改的时间戳只编译最后发生修改的源文件最后完成所有文件的链接。OBJa.out SRCmain.c tree.c CCgcc $(OBJ) : $(SRC) $(CC) $^ -o $ clean: rm $(OBJ)树1.概念一对多的结构由一个根节点和若干个分支节点构成的具有一对多关系的数据的集合。根节点最顶层的节点分支节点有子节点的节点叶子节点终端节点没有子节点的节点树的深度树的层数树的广度度树中节点的度最大的值极为该树的度节点的度节点的子节点个数2.二叉树度为2的树是二叉树3.满二叉树在不增加层数的前提下无法增加一个节点这种二叉树是一个满二叉树满二叉树第K层节点数2^(K-1)K层总节点数2^K-14.完全二叉树在满二叉树的基础上按照从上至下从左至右的方式增加若干个连续的节点。满二叉树一定是一棵完全二叉树。5.二叉树的遍历1深度优先前序遍历根左子树右子树中序遍历左子树根右子树后序遍历左子树右子树根2广度优先层序遍历从上至下从左至右逐层遍历3倒推已知一个前序遍历和中序遍历结果可以确定一棵唯一的二叉树已知一个后序遍历和中序遍历结果可以确定一棵唯一的二叉树6.代码实现1.结构体定义#ifndef __TREE_H__ #define __TREE_H__ typedef char DataType_t; typedef struct trnode { DataType_t data; struct trnode *pl; struct trnode *pr; }TNode_t;2.创建二叉树遍历预定义的字符串#代表NULL。通过递归构建二叉树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(malloc error\n); return NULL; } pnode-data data; pnode-pl create_bin_tree(); pnode-pr create_bin_tree(); return pnode; }3.前序遍历二叉树根-左节点-右结点void pre_order(TNode_t *proot) { if (NULL proot) { return ; } printf(%c, proot-data); pre_order(proot-pl); pre_order(proot-pr); }4.中序遍历二叉树左节点-根-右结点void mid_order(TNode_t *proot) { if (NULL proot) { return ; } mid_order(proot-pl); printf(%c, proot-data); mid_order(proot-pr); }5.后序遍历二叉树左节点-右结点-根void pos_order(TNode_t *proot) { if (NULL proot) { return ; } pos_order(proot-pl); pos_order(proot-pr); printf(%c, proot-data); }6.获取二叉树节点总个数空节点返回0非空返回1依次累加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); }7.获取二叉树层数空节点返回 0非空节点分别计算左、右子树的深度取两者最大值并加一,最后判断谁是深度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; }8.销毁void destroy_bin_tree(TNode_t *proot) { if (NULL proot) { return ; } destroy_bin_tree(proot-pl); destroy_bin_tree(proot-pr); free(proot); }