C实现的一个avl树

orangetouch

好久不写C语言程序了，欢迎找BUG

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

zhanglistar

回复 1# orangetouch


    下来看看。 谢谢lz共享。

hdc1112

下下来准备看看。

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

hdc1112

感觉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;
}

orangetouch

回复 4# hdc1112

这样子应该说清楚了吧？

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

复制代码

hdc1112

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

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

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

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

请多指教。

orangetouch

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;

复制代码

hdc1112

恩。你的意思我有一小部分还是知道。

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

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

liexusong

楼主解释一下删除就好了！

orangetouch

楼主解释一下删除就好了！
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然后这个节点的父结点开始向上判断平衡、调整

复制代码