免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 7439 | 回复: 12

C实现的一个avl树 [复制链接]

论坛徽章:
0
发表于 2010-10-23 16:09 |显示全部楼层
好久不写C语言程序了,欢迎找BUG

压缩包里有2个例子
demo1是统计demo1.c各个字符个数的
demo2是查找/etc/passwd文件的例子

论坛徽章:
0
发表于 2010-10-24 15:16 |显示全部楼层
回复 1# orangetouch


    下来看看。 谢谢lz共享。

论坛徽章:
0
发表于 2010-10-24 16:49 |显示全部楼层
下下来准备看看。

BTW:楼主知道二叉树的分类么。。 我感觉分不清楚二叉树,二叉查找树,等概念。平衡二叉树就是AVL么?还有红黑树,有具体分类没?

论坛徽章:
0
发表于 2010-10-24 19:43 |显示全部楼层
感觉const_size_mp.c好费解啊。。
既然block_size等于所有元素的bytes数目+sizeof( const_size_mp_header_t )

那这一个函数是啥意思啊。。。
void* csmp_block_alloccsmp_block_alloc( const_size_mp_t *mp ){
  void *block = malloc( mp->block_size );
  if( block ){
    ((const_size_mp_header_t*)block)->next = mp->mb;
    mp->mb = block;
    void *start = block + sizeof(const_size_mp_header_t);
    int n = mp->eles_n;
    for( int i = 0; i < n - 1; i++ ){
      *((void**)start) = (void*)start + mp->size;
      start += mp->size;
    }
    *((void**)start) = (void*)0;
    mp->all_ele_n += n;
  }
  return block;
}

论坛徽章:
0
发表于 2010-10-24 22:47 |显示全部楼层
回复 4# hdc1112

这样子应该说清楚了吧?


  1. void* csmp_block_alloc( const_size_mp_t *mp ){
  2.   /* 申请一块空间,大小是block_size=sizeof(const_size_mp_header_t) + 元素大小*n */
  3.   void *block = malloc( mp->block_size );
  4.   if( block ){
  5.     /* 每次申请的空间实际上是用链表组织在一起的。在这块空间的头部(const_size_mp_header_t)填上当前已有的block的地址。free的时候挨个释放 */
  6.     ((const_size_mp_header_t*)block)->next = mp->mb;
  7.     /* 把当前空间的指针指向这块刚申请的空间。free的时候,从新申请的空间开始,挨个释放 */
  8.     mp->mb = block;
  9.     /* 头部之后紧挨着就是存数据的地方了,一共有n个。 第0块可用的空间,就是在const_size_mp_header_t之后,所以加上const_size_mp_header_t的长度就是第0块存数据空间的地址 */
  10.     void *start = block + sizeof(const_size_mp_header_t);
  11.     int n = mp->eles_n;
  12.     /* 前n-1个位置,分别填上指向下一个位置的地址。形成一个链表 */
  13.     for( int i = 0; i < n - 1; i++ ){
  14.       *((void**)start) = (void*)start + mp->size;
  15.       start += mp->size;
  16.     }
  17.     /* 最后一个数据的位置,填0,表示后面没有了 */
  18.     *((void**)start) = (void*)0;
  19.     mp->all_ele_n += n;
  20.   }
  21.   return block;
  22. }
复制代码

论坛徽章:
0
发表于 2010-10-25 09:08 |显示全部楼层
本帖最后由 hdc1112 于 2010-10-25 10:54 编辑

额。。我有几个问题,说得不好请多见谅。。

malloc分配的是一片连续的内存,若是要访问的话,可以通过数组类似的形式访问,block,
若是要释放的话,直接释放free(block)便是。

我怕我理解free理解不清,我去查了下http://dev.firnow.com/course/3_p ... 0090303/157403.html
这个链接,觉得还是可以释放的。

还有,那个链表指向next的指针是存在哪的?。。没有在哪个地方看见定义啊。

请多指教。

论坛徽章:
0
发表于 2010-10-25 20:41 |显示全部楼层
malloc分配的是一片连续的内存,若是要访问的话,可以通过数组类似的形式访问,block,
若是要释放的话,直接释放free(block)便是。

反复多次分配空间,自然得反复多次free才行

我怕我理解free理解不清,我去查了下http://dev.firnow.com/course/3_p ... 0090303/157403.html
这个链接,觉得还是可以释放的。

还有,那个链表指向next的指针是存在哪的?。。没有在哪个地方看见定义啊。

指向next的指, 是存在每个block打头的地方。所以
  1. ((const_size_mp_header_t*)block)->next = mp->mb;
复制代码

论坛徽章:
0
发表于 2010-10-25 20:50 |显示全部楼层
恩。你的意思我有一小部分还是知道。

假设你创建一个512个元素的memory pool。那么在512个元素之前还有个结构。
该结构里就一个next指针。

我再慢慢看看代码吧。。。。

论坛徽章:
0
发表于 2010-10-25 22:14 |显示全部楼层
楼主解释一下删除就好了!

论坛徽章:
0
发表于 2010-10-25 23:04 |显示全部楼层
本帖最后由 orangetouch 于 2010-10-25 23:05 编辑
楼主解释一下删除就好了!
liexusong 发表于 2010-10-25 22:14
  1. 删除的方法是和普通的2叉树一样的。只是删除后要旋转一下。
  2. 具体方法是
  3. 1. 找到要搜索的节点,记为v
  4. 2. 如果这个节点v有左子树,就找到这个v的左子树最右边的节点,也就是左子树中值最大的节点,记为e。
  5.   2.1 把节点e放到v的位置
  6.   2.2 从左子树的最右结点向上,判断树有没有不平衡。如果不平衡,就旋转,直到根结点。
  7. 3. 如果这个节点v没有左子树,但有右子树
  8.   3.1右子树肯定只有一个节点。用右子树的唯一一个节点代替v,然后从v开始向上,判断树有没有不平衡。如果不平衡,就旋转,直到根结点。
  9. 4. 如果这个节点v既没有左子树也没有右子树,则直接删除这个节点。
  10.   4.1然后这个节点的父结点开始向上判断平衡、调整
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP