拉动让他抓住生活中的不难现实,或许高斯讲求实效和追求完美的人性

引文

引文

  前几日享受一个喜爱佩服的壮烈,应该算人类文明极大突破者.收藏过一张钞票类型如下

  前日享受一个喜爱佩服的远大,应该算人类文明极大突破者.收藏过一张钞票类型如下

图片 1

图片 2

那我们三番五次科普一段有关他的简介

那大家后续科普一段关于她的简介

*  ’高斯有些孤傲,但令人惊呆的是,他喜出望外地度过了中产阶级的毕生,而 

*  ’高斯有些孤傲,但让人惊异的是,他热情洋溢地走过了中产阶级的一世,而 

从未有过受到到冰冷现实的打击;那种打击常无情地加诸于每个脱离现实环境生存的 

从来不遇到到冰冷现实的打击;这种打击常凶横地加诸于每个脱离现实环境生存的 

人。或许高斯讲求实效和追求完美的人性,有助于让他抓住生活中的简单现实。 

人。或许高斯讲求实效和追求完善的秉性,有助于让他吸引生活中的容易现实。 

高斯22岁获硕士学位,25岁当选圣彼德堡科大学外籍院士,30岁任哥廷根大学数 

高斯22岁获学士学位,25岁当选圣彼德堡科高校外籍院士,30岁任哥廷根大学数 

学授课兼天文台台长。虽说高斯不爱好奢华荣耀,但在她成名后的五十年间,那 

学授课兼天文台台长。虽说高斯不爱好奢华荣耀,但在她成名后的五十年间,那 

些东西如同雨点似的落在她随身,差不多全体北美洲都卷入了本场授奖的浪潮,他一 

些东西如同雨点似的落在他身上,大致全体亚洲都卷入了这一场授奖的风潮,他一 

生共获取75种形形色色的得体,包含1818年英王乔治三世赐封的“参议员”, 

生共赢得75种形形色色的荣耀,包含1818年英王乔治三世赐封的“参议员”, 

1845年又被赐封为“首席参议员”。高斯的一回婚姻也都不行甜美,第二个爱妻 

1845年又被赐封为“首席参议员”。高斯的几遍婚姻也都优良甜蜜,第二个老婆 

死于子宫破裂后,不到十个月,高斯又娶了第四个老伴。心情学和生农学上有一个常 

死于新生儿窒息后,不到十个月,高斯又娶了第一个内人。心情学和生历史学上有一个常 

见的风貌,婚姻生活过得幸福的人,常在丧偶之后连忙再婚,他的老年不美满,*

见的现象,婚姻生活过得幸福的人,常在丧偶之后很快再婚,他的老龄不美满,*

男女和他提到不佳…’

儿女和他关系不佳…’

  关于他的专业知识 业界评价如下

  关于他的专业知识 业界评价如下

  ‘能从太空云外的惊人根据某种观点明白星空和深邃数学的天赋。’地球上搞数学人类中公认前三diao. 

  ‘能从太空云外的惊人根据某种观点了然星空和深邃数学的天赋。’地球上搞数学人类中公认前三diao. 

偶尔我们所有的满贯 都是自己挑选的进度,

有时候我们具备的方方面面 都是上下一心选择的长河,

不是友好拔取,就是别人选取. 很公道, 就看每个人顿觉的一定,觉醒能力的 差距而已. 

不是祥和挑选,就是人家选用. 很公道, 就看每个人茅塞顿开的必定,觉醒能力的 不相同而已. 

 

 

推荐参照

引进参照

    没有怎么两样
http://music.163.com/#/song?id=25713024

    没有何样两样
http://music.163.com/#/song?id=25713024

再扯一点, ‘孤傲’的话题, 生活中偶然蒙受一类人, 第五回见他认为太傲了, 接触了一段时间

再扯一点, ‘孤傲’的话题, 生活中偶尔遇到一类人, 第三遍见她认为太傲了, 接触了一段时间

发觉那人了不起, 后边通晓多了, 照旧很欢愉和他交朋友. 人不错.

发觉这人了不起, 前面精晓多了, 仍旧很开心和她交朋友. 人不错.

  人是最复杂的,也是最不难改变的.紧要须要多驾驭.

  人是最复杂的,也是最不难改变的.重点须要多了然.

 

 

前言

前言

   到这边逐渐切入大旨了, 当一个构想 投入生产环境一般 必要上面多少个步骤.

   到那边渐渐切入主旨了, 当一个构想 投入生产条件一般 需求上面多少个步骤.

1算法/思路 构思

1算法/思路 构思

2算法完成 测试

2算法达成 测试

3.封装基础算法结构库

3.封装基础算法结构库

4.算法/思路结构库 测试

4.算法/思路结构库 测试

5. 投入生产环境轻微重构

5. 投入生产条件轻微重构

6.生产条件测试

6.生产条件测试

7.实战检测.

7.实战检测.

  所以封装一个库如故有些流程相比较耗时的. 我们那里享用的是关于一个二叉树基础库的分享. 原先花了2天使用红黑树完结,

  所以封装一个库照旧有些流程相比较耗时的. 大家那里享用的是有关一个二叉树基础库的分享. 原先花了2天使用红黑树已毕,

可是最后磕磕碰碰,抄抄补补搞出来可是代码很倒霉维护,最终退而求其次选拔 二叉查找树构造了一个基础库. 并测试了眨眼之间间要旨可以.

不过最终磕磕碰碰,抄抄补补搞出来然则代码很不好维护,最终退而求其次采取 二叉查找树构造了一个基础库. 并测试了刹那间主导可以.

等下一次直接用到实战环境中.

等下一回直接用到实战条件中.

  首选学习这一个二叉树 库封装 须要

  首选学习这些二叉树 库封装 须要

    1.打探二叉树基础原理

    1.叩问二叉树基础原理

    2.掌握C接口的简易设计

    2.通晓C接口的粗略设计

  可以学到

  可以学到

    1.C接口设计的部分技术

    1.C接口设计的有的技巧

    2.接口简单测试

    2.接口简单测试

第一看上边接口文档 tree.h

首先看上边接口文档 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
#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;

_TREE_NODE;

举例来说如下

比方如下

//通用结构体变量
struct dict {
    _TREE_HEAD;
    char* key;
    char* value;
};
//通用结构体变量
struct dict {
    _TREE_HEAD;
    char* key;
    char* value;
};

有关怎么,想一想也都知道了,那样的代码或者说技巧 太多了, Linux内核中结构喜欢 将其位于最末的岗位,会有一个

有关缘何,想一想也都精晓了,那样的代码或者说技巧 太多了, Linux内核中结构喜欢 将其位于最末的职位,会有一个

typeof 宏 判断地点.那上边我们开首说说现实设计. 扯一点,一个亟需C入门选手,要么把C语言之父的书看一回,倒着看五回.

typeof 宏 判断地方.那上面大家伊始说说现实设计. 扯一点,一个急需C入门选手,要么把C语言之父的书看三遍,倒着看一回.

写五遍或精晓会用下边的结构体设计,基本C那块语法都了解了.

写一遍或知道会用上边的结构体设计,基本C那块语法都精通了.

  一定要多写代码, 因为前景不清楚, 但可以知晓的是不佳好写代码, 那现在都不明了了. 大家认为呢.

  一定要多写代码, 因为前景不知晓, 但可以明白的是不佳好写代码, 那现在都不通晓了. 大家认为呢.

 

 

正文

正文

1.说细节完成 

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, 0, sizeof(struct tree));
    root->new = new;
    root->acmp = acmp;
    root->gdcmp = gdcmp;
    root->del = del;

    return root;
}
//内部使用的主要结构
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, 0, sizeof(struct tree));
    root->new = new;
    root->acmp = acmp;
    root->gdcmp = gdcmp;
    root->del = del;

    return root;
}

地点根本是亟需登记4个函数, 第三个new自然是分配内存的操作再次回到void*就是构造好的内存, acmp是加上结点的时候相比较函数,

上边根本是需求注册4个函数, 第四个new自然是分配内存的操作重回void*就是结构好的内存, acmp是丰富结点的时候可比函数,

gdcmp 是 get 和 del 时候需求调用的搜索函数指针, 对于del可以没有这些时候,可以流传NULL,表示不需求救助回收内存.

gdcmp 是 get 和 del 时候必要调用的检索函数指针, 对于del可以没有这么些时候,可以流传NULL,表示不要求帮衬回收内存.

大家可以仔细考虑一下为何要这一个. 

大家能够仔细考虑一下为啥要那么些. 

率先创设和销毁是必须的,后边 add的时候增加的是 node 结点, 而查找的时候是相比的是 关键字key结构是不等同的.

先是创设和销毁是必须的,前面 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;
}
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.

相比简朴没有好解释的,最终会让释放的指针指向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 = 0;

    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)) == 0) //这种情况是不允许插入的
            return;
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    //找见了开始插入结点
    if (tmp < 0)
        p->lc = tm->new(node);
    else
        p->rc = tm->new(node);
}
/*
* 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 = 0;

    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)) == 0) //这种情况是不允许插入的
            return;
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    //找见了开始插入结点
    if (tmp < 0)
        p->lc = tm->new(node);
    else
        p->rc = tm->new(node);
}

对于cmp

对于cmp

typedef int (*icmp_f)(void* ln, void* rn);
typedef int (*icmp_f)(void* ln, void* rn);

此地有点约定, ln
== rn 再次回到0, ln>rn 重临 >0 反之重返<0. 其中 传入的基参数
.都是做第二个参数.

此间有点约定, ln
== rn 重回0, ln>rn 重临 >0 反之重临<0. 其中 传入的基参数
.都是做第二个参数.

下一版本想改为

下一版本想改为

//int cmp(void* node, void* rn); 必须是这样格式
typedef int (*icmp_f)();
//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);
}
/*
* 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)) == 0){ //这种情况是不允许插入的        
            //返回父亲结点,没有就置空
            if (parent)
                *parent = p;    
            break;
        }
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    return 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)) == 0){ //这种情况是不允许插入的        
            //返回父亲结点,没有就置空
            if (parent)
                *parent = p;    
            break;
        }
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    return n;
}

专程是开始的

特意是发端的

    if(parent) //初始化功能
        *parent = NULL;
    if(parent) //初始化功能
        *parent = NULL;

为了是寻觅重返数据都是正常数据,没有意外.

为了是寻觅重回数据都是常规数据,没有意外.

到那边大约二叉树基库就打点完成了. 重若是部分C接口设计的技巧
+ 二叉树查找树的简易算法.

到这边大致二叉树基库就整治落成了. 重假设一对C接口设计的技艺
+ 二叉树查找树的概括算法.

抑或比较直接的.下一个版本 将公有头文件内容移除了,会更简便一点.

抑或相比较直接的.下一个版本 将公有头文件内容移除了,会更简约一点.

 

 

2.tree.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, 0, 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 = 0;

    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)) == 0) //这种情况是不允许插入的
            return;
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    //找见了开始插入结点
    if (tmp < 0)
        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)) == 0){ //这种情况是不允许插入的        
            //返回父亲结点,没有就置空
            if (parent)
                *parent = p;    
            break;
        }
        p = n;
        if (tmp < 0)
            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;
}
#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, 0, 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 = 0;

    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)) == 0) //这种情况是不允许插入的
            return;
        p = n;
        if (tmp < 0)
            n = n->lc;
        else
            n = n->rc;
    }

    //找见了开始插入结点
    if (tmp < 0)
        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)) == 0){ //这种情况是不允许插入的        
            //返回父亲结点,没有就置空
            if (parent)
                *parent = p;    
            break;
        }
        p = n;
        if (tmp < 0)
            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.因为是封装库的库,测试代码会多一点.

总长度仍然相比较短的.上边代码写了五遍,都未曾加测试接口. 后边单独写测试demo.因为是封装库的库,测试代码会多一点.

 

 

3.说测试结果

3.说测试结果

  到此地就是测试的时候,先不难看一个test.c 测试,编译命令是

  到此地就是测试的时候,先不难看一个test.c 测试,编译命令是

gcc -g -Wall -o test.out test.c tree.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 = { { 0, 0 }, "123", "123" };
    struct dict dt2 = { { 0, 0 }, "1","1" };
    struct dict dt3 = { { 0, 0 }, "2","2" };
    struct dict dt4 = { { 0, 0 }, "456", "456" };
    struct dict dt5 = { { 0, 0 }, "7","7" };

    //创建一个结点,后面创建删除
    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, "123", NULL);
    printf("key:[%s], value:[%s].\n", pd->key, pd->value);

    pd = tree_get(root, "456", (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, "123");
    pd = tree_get(root, "456", (void**)&pp);
    printf("key:[%s], value:[%s].\n", pd->key, pd->value);
    if (!pp)
        puts("应该不存在的!");

    //通过单点调试,内存检测一切正常
    tree_destroy(&root);

    system("pause");
    return 0;
}
#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 = { { 0, 0 }, "123", "123" };
    struct dict dt2 = { { 0, 0 }, "1","1" };
    struct dict dt3 = { { 0, 0 }, "2","2" };
    struct dict dt4 = { { 0, 0 }, "456", "456" };
    struct dict dt5 = { { 0, 0 }, "7","7" };

    //创建一个结点,后面创建删除
    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, "123", NULL);
    printf("key:[%s], value:[%s].\n", pd->key, pd->value);

    pd = tree_get(root, "456", (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, "123");
    pd = tree_get(root, "456", (void**)&pp);
    printf("key:[%s], value:[%s].\n", pd->key, pd->value);
    if (!pp)
        puts("应该不存在的!");

    //通过单点调试,内存检测一切正常
    tree_destroy(&root);

    system("pause");
    return 0;
}

测试结果,原先是在window上,前边在Linux上测试了.结果如下

测试结果,原先是在window上,前边在Linux上测试了.结果如下

图片 3

图片 4

全副正常.

成套正常.

第三个测试,测试在堆上分配是不是正常 main.c

其次个测试,测试在堆上分配是不是正常 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(1, 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", "123"};
    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 0;
}
#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(1, 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", "123"};
    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 0;
}

编译命令,Makefile文件内容如下

编译命令,Makefile文件内容如下

main.out:main.c tree.c
    gcc -g -Wall -o $@ $^
main.out:main.c tree.c
    gcc -g -Wall -o $@ $^

运转结果截图如下

运行结果截图如下

图片 5

图片 6

一切正常没有内存走漏.

一切正常没有内存泄露.

末端准备到库再拓展生产测试.

背后准备到库再开展生产测试.

 

 

后记

后记

  那里,这一个基础tree C库基本封装了,按照库简单修改一下主导就可以用在开发中了.下一个本子选取那么些库 构造一个 C 配置文件读取接口.

  那里,那几个基础tree C库基本封装了,依据库简单修改一下为主就足以用在支付中了.下一个本子选用这么些库 构造一个 C 配置文件读取接口.

让框架具备不难安插文件热读取的能力.扯一点,像这么些分析配置的发动机难题都在 语法解析上.其它都好搞.将来有机会带大家手把手写json,csv 解析’引擎’.

让框架具备简单安顿文件热读取的能力.扯一点,像那么些分析配置的引擎难点都在 语法解析上.此外都好搞.未来有时机带大家手把手写json,csv 解析’引擎’.

此间就这么了. 错误是免不了的, 因为经验的太少, 拜~.

那边就这么了. 错误是在所难免的, 因为经历的太少, 拜~.

 

 

相关文章