引文
今天分享一个喜欢佩服的伟人,应该算人类文明极大突破者.收藏过一张纸币类型如下
那我们继续科普一段关于他的简介
'高斯有些孤傲，但令人惊奇的是，他春风得意地度过了中产阶级的一生，而
没有遭受到冷酷现实的打击；这种打击常无情地加诸于每个脱离现实环境生活的
人。或许高斯讲求实效和追求完美的性格，有助于让他抓住生活中的简单现实。
高斯22岁获博士学位，25岁当选圣彼德堡科学院外籍院士，30岁任哥廷根大学数
学教授兼天文台台长。虽说高斯不喜欢浮华荣耀，但在他成名后的五十年间，这
些东西就像雨点似的落在他身上，几乎整个欧洲都卷入了这场授奖的风潮，他一
生共获得75种形形色色的荣誉，包括1818年英王乔治三世赐封的“参*”，
1845年又被赐封为“首席参*”。高斯的两次婚姻也都非常幸福，第一个妻子
死于难产后，不到十个月，高斯又娶了第二个妻子。心理学和生理学上有一个常
见的现象，婚姻生活过得幸福的人，常在丧偶之后很快再婚，他的晚年不幸福,
孩子和他关系不好...'
关于他的专业知识 业界评价如下
'能从九霄云外的高度按照某种观点掌握星空和深奥数学的天才。'地球上搞数学人类中公认前三diao.
有时候我们所有的一切 都是自己抉择的过程,
不是自己选择,就是别人选择. 很公平, 就看每个人觉醒的早晚,觉醒能力的 不同而已.
推荐参照
没有什么不同 http://music.163.com/#/song?id=25713024
再扯一点, '孤傲'的话题, 生活中有时候遇到一类人, 第一次见他觉得太傲了, 接触了一段时间
发现这人了不起, 后面了解多了, 还是很喜欢和他交朋友. 人不错.
人是最复杂的,也是最容易改变的.关键需要多了解.
前言
到这里逐渐切入正题了, 当一个构想 投入生产环境一般 需要下面几个步骤.
1算法/思路 构思
2算法实现 测试
3.封装基础算法结构库
4.算法/思路结构库 测试
5. 投入生产环境轻微重构
6.生产环境测试
7.实战检测.
所以封装一个库还是有些流程比较耗时的. 我们这里分享的是关于一个二叉树基础库的分享. 原先花了2天使用红黑树实现,
但是最后磕磕碰碰,抄抄补补搞出来但是代码很不好维护,最后退而求其次采用 二叉查找树构造了一个基础库. 并测试了一下基本可以.
等下一次直接用到实战环境中.
首选学习这个二叉树 库封装 需要
1.了解二叉树基础原理
2.了解C接口的简单设计
能够学到
1.C接口设计的一些技巧
2.接口简单测试
首先看下面接口文档 tree.h
#ifndef _H_TREE
#define _H_TREE //4.0 控制台打印错误信息, fmt必须是双引号括起来的宏
#ifndef CERR
#define CERR(fmt, ...) \
fprintf(stderr,"[%s:%s:%d][error %d:%s]" fmt "\r\n",\
__FILE__, __func__, __LINE__, errno, strerror(errno),##__VA_ARGS__)
#endif/* !CERR */ //4.1 控制台打印错误信息并退出, t同样fmt必须是 ""括起来的字符串常量
#ifndef CERR_EXIT
#define CERR_EXIT(fmt,...) \
CERR(fmt,##__VA_ARGS__),exit(EXIT_FAILURE)
#endif/* !ERR */ /*
* 这里是简单二叉查找树封装的基库,封装库的库
* 需要用的的一些辅助结构,主要是通用结构和申请释放的函数指针
*/
typedef struct tree* tree_t;
typedef void* (*pnew_f)();
typedef void (*vdel_f)(void* node);
typedef int (*icmp_f)(void* ln, void* rn); // __开头一般意思是不希望你使用,私有的,系统使用
struct __tnode {
struct __tnode* lc;
struct __tnode* rc;
};
/*
* 这个宏必须放在使用的结构体开头,如下
* struct persion {
_TREE_HEAD;
char* name;
int age;
...
* }
*
*/
#define _TREE_HEAD \
struct __tnode __tn /*
* new : 结点申请内存用的函数指针, 对映参数中是 特定结构体指针
* acmp : 用于添加比较
* gdcmp : 两个结点比较函数,用户查找和删除
* del : 结点回收函数,第一个参数就是 二叉树中保存的结点地址
* ret : 返回创建好的二叉树结构, 这里是 tree_t 结构
*/
tree_t tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del); /*
* proot : 指向tree_t 根结点的指针,
* node : 待处理的结点对象, 会调用new(node) 创建新结点
* ret : proot 即是输入参数也是返回参数,返回根结点返回状况
*/
void tree_add(tree_t* proot, void* node); /*
* proot : 输入和输出参数,指向根结点的指针
* node : 删除结点,这里会调用 cmp(node 左参数, foreach) 找见,通过del(find) 删除
*/
void tree_del(tree_t* proot, void* node); /*
* root : 根结点,查找的总对象
* node : 查找条件,会通过cmp(node, foreach)去查找
* parent : 返回查找到的父亲结点
* ret : 返回查找到的结点对象
*/
void* tree_get(tree_t root, void* node, void** parent); /*
* proot : 指向二叉树数结点指针
* 会调用 del(foreach) 去删除所有结点,并将所有还原到NULL
*/
void tree_destroy(tree_t* proot); #endif // !_H_TREE
上面有些代码在实战环节是要去掉和统一修改的.这里是为了降低耦合性,方便测试,就放在一起了.
接口比较精简,还可以更精简,下次再优化.应该一看都明白上面代码是干什么的. 需要注意的是
在你想使用二叉树性质的 结构体中 需要在第一个 成员位置 加入
_TREE_NODE;
举例如下
//通用结构体变量
struct dict {
_TREE_HEAD;
char* key;
char* value;
};
至于为什么,想一想也都明白了,这样的代码或者说技巧 太多了, Linux内核中结构喜欢 将其放在最末的位置,会有一个
typeof 宏 判断位置.那下面我们开始说说具体设计. 扯一点,一个需要C入门选手,要么把C语言之父的书看一遍,倒着看一遍.
写一遍或理解会用上面的结构体设计,基本C这块语法都明白了.
一定要多写代码, 因为未来不清楚, 但可以知道的是不好好写代码, 那现在都不清楚了. 大家觉得呢.
正文
1.说细节实现
首先看创建函数定义,这里主要用到函数指针技巧,比较直白.
//内部使用的主要结构
struct tree {
//保存二叉树的头结点
struct __tnode* root; //构建,释放,删除操作的函数指针
pnew_f new;
icmp_f acmp;
icmp_f gdcmp;
vdel_f del;
}; /*
* new : 结点申请内存用的函数指针, 对映参数中是 特定结构体指针
* acmp : 用于添加比较
* gdcmp : 两个结点比较函数,用户查找和删除
* del : 结点回收函数,第一个参数就是 二叉树中保存的结点地址
* ret : 返回创建好的二叉树结构, 这里是 tree_t 结构
*/
tree_t
tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del)
{
tree_t root = malloc(sizeof(struct tree));
if (NULL == root)
CERR_EXIT("malloc struct tree error!"); //初始化挨个操作
memset(root, , sizeof(struct tree));
root->new = new;
root->acmp = acmp;
root->gdcmp = gdcmp;
root->del = del; return root;
}
上面主要是需要注册4个函数, 第一个new自然是分配内存的操作返回void*就是构造好的内存, acmp是添加结点的时候比较函数,
gdcmp 是 get 和 del 时候需要调用的查找函数指针, 对于del可以没有这个时候,可以传入NULL,表示不需要帮忙回收内存.
大家可以仔细考虑一下为什么要这些.
首先创建和销毁是必须的,后面 add的时候添加的是 node 结点, 而查找的时候是比较的是 关键字key结构是不一样的.
同样看一下回收函数
static void __tree_destroy(struct __tnode* root, vdel_f del)
{
if (root) {
__tree_destroy(root->lc, del);
__tree_destroy(root->rc, del);
del(root); //结点删除采用注册方法
}
} /*
* proot : 指向二叉树数结点指针
* 会调用 del(foreach) 去删除所有结点,并将所有还原到NULL
*/
void
tree_destroy(tree_t* proot)
{
tree_t root;
if ((!proot) || !(root = *proot))
return;
if (root->root && root->del)
__tree_destroy(root->root, root->del);
free(*proot); //单独释放最外层内容
*proot = NULL;
}
比较质朴没有好解释的,最后会让释放的指针指向NULL.
后面就是二叉查找树插入查找和删除算法实现了,比较基础,对着书翻译就可以了.添加代码如下
/*
* proot : 指向tree_t 根结点的指针,
* node : 待处理的结点对象, 会调用new(node) 创建新结点
* ret : proot 即是输入参数也是返回参数,返回根结点返回状况
*/
void
tree_add(tree_t* proot, void* node)
{
tree_t tm;
struct __tnode *n, *p = NULL;
icmp_f cmp;
int tmp = ; if ((!proot) || (!node) || !(tm = *proot)) //参数无效直接返回
return;
if (!(n = tm->root)) { //插入的结点为头结点,直接赋值返回
tm->root = tm->new(node);
return;
}
//下面开始找 待插入结点
cmp = tm->acmp;
while (n) {
if ((tmp = cmp(node, n)) == ) //这种情况是不允许插入的
return;
p = n;
if (tmp < )
n = n->lc;
else
n = n->rc;
} //找见了开始插入结点
if (tmp < )
p->lc = tm->new(node);
else
p->rc = tm->new(node);
}
对于cmp
typedef int (*icmp_f)(void* ln, void* rn);
这里有点约定, ln == rn 返回0, ln>rn 返回 >0 反之返回<0. 其中 传入的基参数 .都是做第一个参数.
下一版本想改为
//int cmp(void* node, void* rn); 必须是这样格式
typedef int (*icmp_f)();
弱约束,可以用.毕竟底层库应该灵活,上层库应该写死. 这样在难处学习成本高,简单处学习成本低. 等同于红黑树的添加和查找.
后面还有一个删除代码
/*
* proot : 输入和输出参数,指向根结点的指针
* node : 删除结点,这里会调用 cmp(node 左参数, foreach) 找见,通过del(find) 删除
*/
void
tree_del(tree_t* proot, void* node)
{
tree_t tm;
struct __tnode *n, *p, *t, *tp;
if ((!proot) || (!node) || !(tm = *proot) || !(tm->root))
return;
//查找一下这个结点,如果不存在直接返回
if (!(n = tree_get(tm, node, (void**)&p)))
return;
//第一种删除和操作
if ((!n->lc || !n->rc) && !(t = n->lc))
t = n->rc;
else { //第二种情况,将右子树最小结点和当前删除结点交换
for (tp = n, t = tp->rc; (t->lc); tp = t, t = t->lc)
; //找见了最小的左子树结点n 和父结点p
if (tp->lc == t)
tp->lc = t->rc;
else
tp->rc = t->rc;
//移动孩子关系
t->lc = n->lc;
t->rc = n->rc;
} if (!p) //设置新的root结点
tm->root = t;
else {
if (p->lc == n) //调整父亲和孩子关系,需要你理解二叉查找树,否则那就相信我吧
p->lc = t;
else
p->rc = t;
}
//这里释放那个结点
if (tm->del)
tm->del(n);
}
删除思路解释,单节点删除,父节点指向后继, 多结点找到右子树中最小的结点当做新结点,再删除它.上一个版本用尾递归,这里采用的是非递归实现.
对于查找是这样的,也会一起找到父节点
/*
* root : 根结点,查找的总对象
* node : 查找条件,会通过cmp(node, foreach)去查找
* parent : 返回查找到的父亲结点
* ret : 返回查找到的结点对象
*/
void*
tree_get(tree_t root, void* node, void** parent)
{
struct __tnode *n, *p = NULL;
icmp_f cmp;
int tmp; if(parent) //初始化功能
*parent = NULL;
if ((!node) || (!root) || !(n = root->root))
return NULL;
//查找结点
cmp = root->gdcmp;
while (n) {
if ((tmp = cmp(node, n)) == ){ //这种情况是不允许插入的
//返回父亲结点,没有就置空
if (parent)
*parent = p;
break;
}
p = n;
if (tmp < )
n = n->lc;
else
n = n->rc;
} return n;
}
特别是开头的
if(parent) //初始化功能
*parent = NULL;
为了是查找返回数据都是正常数据,没有意外.
到这里基本上二叉树基库就整理完毕了. 主要是一些C接口设计的技巧 + 二叉树查找树的简单算法.
还是比较直白的.下一个版本 将公有头文件内容移除去,会更简约一点.
2.tree.c 代码完整展示
完整代码展示如下
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h> //内部使用的主要结构
struct tree {
//保存二叉树的头结点
struct __tnode* root; //构建,释放,删除操作的函数指针
pnew_f new;
icmp_f acmp;
icmp_f gdcmp;
vdel_f del;
}; /*
* new : 结点申请内存用的函数指针, 对映参数中是 特定结构体指针
* acmp : 用于添加比较
* gdcmp : 两个结点比较函数,用户查找和删除
* del : 结点回收函数,第一个参数就是 二叉树中保存的结点地址
* ret : 返回创建好的二叉树结构, 这里是 tree_t 结构
*/
tree_t
tree_create(pnew_f new, icmp_f acmp, icmp_f gdcmp, vdel_f del)
{
tree_t root = malloc(sizeof(struct tree));
if (NULL == root)
CERR_EXIT("malloc struct tree error!"); //初始化挨个操作
memset(root, , sizeof(struct tree));
root->new = new;
root->acmp = acmp;
root->gdcmp = gdcmp;
root->del = del; return root;
} /*
* proot : 指向tree_t 根结点的指针,
* node : 待处理的结点对象, 会调用new(node) 创建新结点
* ret : proot 即是输入参数也是返回参数,返回根结点返回状况
*/
void
tree_add(tree_t* proot, void* node)
{
tree_t tm;
struct __tnode *n, *p = NULL;
icmp_f cmp;
int tmp = ; if ((!proot) || (!node) || !(tm = *proot)) //参数无效直接返回
return;
if (!(n = tm->root)) { //插入的结点为头结点,直接赋值返回
tm->root = tm->new(node);
return;
}
//下面开始找 待插入结点
cmp = tm->acmp;
while (n) {
if ((tmp = cmp(node, n)) == ) //这种情况是不允许插入的
return;
p = n;
if (tmp < )
n = n->lc;
else
n = n->rc;
} //找见了开始插入结点
if (tmp < )
p->lc = tm->new(node);
else
p->rc = tm->new(node);
} /*
* proot : 输入和输出参数,指向根结点的指针
* node : 删除结点,这里会调用 cmp(node 左参数, foreach) 找见,通过del(find) 删除
*/
void
tree_del(tree_t* proot, void* node)
{
tree_t tm;
struct __tnode *n, *p, *t, *tp;
if ((!proot) || (!node) || !(tm = *proot) || !(tm->root))
return;
//查找一下这个结点,如果不存在直接返回
if (!(n = tree_get(tm, node, (void**)&p)))
return;
//第一种删除和操作
if ((!n->lc || !n->rc) && !(t = n->lc))
t = n->rc;
else { //第二种情况,将右子树最小结点和当前删除结点交换
for (tp = n, t = tp->rc; (t->lc); tp = t, t = t->lc)
; //找见了最小的左子树结点n 和父结点p
if (tp->lc == t)
tp->lc = t->rc;
else
tp->rc = t->rc;
//移动孩子关系
t->lc = n->lc;
t->rc = n->rc;
} if (!p) //设置新的root结点
tm->root = t;
else {
if (p->lc == n) //调整父亲和孩子关系,需要你理解二叉查找树,否则那就相信我吧
p->lc = t;
else
p->rc = t;
}
//这里释放那个结点
if (tm->del)
tm->del(n);
} /*
* root : 根结点,查找的总对象
* node : 查找条件,会通过cmp(node, foreach)去查找
* parent : 返回查找到的父亲结点
* ret : 返回查找到的结点对象
*/
void*
tree_get(tree_t root, void* node, void** parent)
{
struct __tnode *n, *p = NULL;
icmp_f cmp;
int tmp; if(parent) //初始化功能
*parent = NULL;
if ((!node) || (!root) || !(n = root->root))
return NULL;
//查找结点
cmp = root->gdcmp;
while (n) {
if ((tmp = cmp(node, n)) == ){ //这种情况是不允许插入的
//返回父亲结点,没有就置空
if (parent)
*parent = p;
break;
}
p = n;
if (tmp < )
n = n->lc;
else
n = n->rc;
} return n;
} //实际的删除函数,采用后续删除
static void __tree_destroy(struct __tnode* root, vdel_f del)
{
if (root) {
__tree_destroy(root->lc, del);
__tree_destroy(root->rc, del);
del(root); //结点删除采用注册方法
}
} /*
* proot : 指向二叉树数结点指针
* 会调用 del(foreach) 去删除所有结点,并将所有还原到NULL
*/
void
tree_destroy(tree_t* proot)
{
tree_t root;
if ((!proot) || !(root = *proot))
return;
if (root->root && root->del)
__tree_destroy(root->root, root->del);
free(*proot); //单独释放最外层内容
*proot = NULL;
}
总长度还是比较短的.上面代码写了几遍,都没有加测试接口. 后面单独写测试demo.因为是封装库的库,测试代码会多一点.
3.说测试结果
到这里就是说测试的时候,先简单看一个test.c 测试,编译命令是
gcc -g -Wall -o test.out test.c tree.c
源码如下
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h" //通用结构体变量
struct dict {
_TREE_HEAD;
char* key;
char* value;
}; static void* __dict_new(void* arg)
{
return arg;
} //为了通用库,这种比较算法比较不好,采用hash不能够唯一确定
static int __dict_acmp(struct dict* ln, struct dict* rn)
{
return strcmp(ln->key, rn->key);
}
static int __dict_gdcmp(const char* ln, struct dict* rn)
{
return strcmp(ln, rn->key);
} /*
* 这里测试 tree.c 基类型测试的
*/
int main(int argc, char* argv[])
{
struct dict *pd , *pp;
struct dict dt1 = { { , }, "", "" };
struct dict dt2 = { { , }, "","" };
struct dict dt3 = { { , }, "","" };
struct dict dt4 = { { , }, "", "" };
struct dict dt5 = { { , }, "","" }; //创建一个结点,后面创建删除
tree_t root = tree_create(__dict_new, (icmp_f)__dict_acmp, (icmp_f)__dict_gdcmp, NULL); //开始添加结点
tree_add(&root, &dt1);
tree_add(&root, &dt2);
tree_add(&root, &dt3);
tree_add(&root, &dt4);
tree_add(&root, &dt5); //得到这个结点,并返回
pd = tree_get(root, "", NULL);
printf("key:[%s], value:[%s].\n", pd->key, pd->value); pd = tree_get(root, "", (void**)&pp);
printf("key:[%s], value:[%s].\n", pd->key, pd->value);
printf("key:[%s], value:[%s].\n", pp->key, pp->value); //删除结点测试,这个普通树型结构确实不好
tree_del(&root, "");
pd = tree_get(root, "", (void**)&pp);
printf("key:[%s], value:[%s].\n", pd->key, pd->value);
if (!pp)
puts("应该不存在的!"); //通过单点调试,内存检测一切正常
tree_destroy(&root); system("pause");
return ;
}
测试结果,原先是在window上,后面在Linux上测试了.结果如下
一切正常.
第二个测试,测试在堆上分配是否正常 main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "tree.h" //继续测试堆上分配
struct node {
_TREE_HEAD;
char* key;
char* value;
}; //构建运用到的函数
static void* __node_new(struct node* n)
{
struct node* nn = calloc(, sizeof(struct node));
if(NULL == nn)
CERR_EXIT("malloc struct node error!");
nn->key = n->key;
nn->value = n->value;
//返回最终结果
return nn;
} //添加时候查找函数
static int __node_acmp(void* ln, void* rn)
{
return strcmp(((struct node*)ln)->key, ((struct node*)rn)->key);
} //查找和删除的查找函数
static int __node_gdcmp(void* ln, void* rn)
{
return strcmp(ln, ((struct node*)rn)->key);
} //简单测试函数
static void __node_puts(void* arg)
{
struct node* n = arg;
if(NULL == n)
puts("now node is empty!");
else
printf("key:%s, value:%s.\n", n->key, n->value);
} //简单释放函数
static void __node_delete(void* arg)
{
__node_puts(arg);
free(arg);
} //写到这里自己都想抱怨一句前戏太长了, tree.c 其实本质是个通用算法库,... /*
* 这里继续测试一下 tree 基类库接口
*/
int main(int argc, char* argv[])
{
tree_t root = tree_create(__node_new, __node_acmp, __node_gdcmp, __node_delete); //这里就添加结点
struct node ntmp = { {NULL, NULL}, "a", ""};
tree_add(&root, &ntmp); ntmp.key = "bb";
ntmp.value = "ccccccc";
tree_add(&root, &ntmp); ntmp.key = "bbc";
ntmp.value = "ccccccc";
tree_add(&root, &ntmp); ntmp.key = "bbcc";
ntmp.value = "ccccccc";
tree_add(&root, &ntmp); ntmp.key = "bbcccc";
ntmp.value = "dd你好ccc";
tree_add(&root, &ntmp);
//tree_destroy(&root); if(NULL == root)
puts("root is null");
ntmp.key = "好的";
ntmp.value = "cccok就这样c";
tree_add(&root, &ntmp); //这里查找结点
void *p, *n;
n = tree_get(root, "好的", &p);
if(p)
__node_puts(p);
else
puts("没有父结点");
__node_puts(n); //删除结点
tree_del(&root, "好的"); tree_destroy(&root); return ;
}
编译命令,Makefile文件内容如下
main.out:main.c tree.c
gcc -g -Wall -o $@ $^
运行结果截图如下
一切正常没有内存泄露.
后面准备到库再进行生产测试.
后记
这里,这个基础tree C库基本封装了,根据库简单修改一下基本就可以用在开发中了.下一个版本利用这个库 构造一个 C 配置文件读取接口.
让框架具备简单配置文件热读取的能力.扯一点,像这些解析配置的引擎难点都在 语法解析上.其它都好搞.以后有机会带大家手把手写json,csv 解析'引擎'.
这里就这样了. 错误是难免的, 因为经历的太少, 拜~.