• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

线段树的实现[C语言](原创)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

线段树也是一种二叉树,只不过它的节点用来表示一个区间,其特征是将当前区间二分后分别作为左右孩子节点

的区间,如下图(来自百度图片)所示:

线段树在处理区间覆盖问题时,比较有用处,它支持的基本操作如下:

1)  给定区间[i, j],创建一个线段树;【时间复杂度为O(j – i)】

2)  将某个区间[i,j]插入到线段树中; 【时间复杂度为O(log(j-i))】

3)  从线段树中删除某个区间[i,j]。【时间复杂度为O(log(j-i)】

下面是使用C语言实现的一个线段树(VC++编译器编译运行):

/*
* Author:puresky
* Date: 2008/12/22
* Version: 线段树1.0,
* Refer to:数据结构教程(V2)
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct ltree_node
{
      int i, j; //表示区间[i, j]
      int cover; //表示区间被覆盖的次数
      struct ltree_node *left, *right; //左右儿子节点
} LTree;

//创建线段树

LTree* ltree_create(int i, int j)
{
      if(i > j) return (NULL);
      LTree* pNode = NULL;
      pNode = (LTree*)malloc(sizeof(LTree));
      pNode->i = i;
      pNode->j = j;
      pNode->cover = 0;
      if(j - i > 1)
      {
            int mid = i + (j - i) / 2;
            pNode->left = ltree_create(i, mid);
            pNode->right = ltree_create(mid, j);
      }
      else
      {
            pNode->left = pNode->right = NULL;
      }
      return pNode;
}

//插入一个区间

void ltree_insert(LTree* ltree, int i, int j)
{
      if(i > j) return;
      if(i <= ltree->i && ltree->j <= j)
      {
            ltree->cover++;
      }
      else
      {
            int mid = ltree->i + (ltree->j - ltree->i) / 2;
            if(j <= mid)
            {
                  ltree_insert(ltree->left, i, j);
            }
            else if(mid <= i)
            {
                  ltree_insert(ltree->right, i, j);
            }
            else
            {
                  ltree_insert(ltree->left, i, mid);
                  ltree_insert(ltree->right, mid, j);
            }
      }
}

//删除一个区间,注意只能删除已经插入的区间
void ltree_delete(LTree* ltree, int i, int j)
{
      if(i > j) return;
      if(i <= ltree->i && ltree->j <= j)
            ltree->cover--;
      else
      {
            int mid = ltree->i + (ltree->j - ltree->i) / 2;
            if(j <= mid)
            {
                  ltree_delete(ltree->left, i, j);
            }
            else if(i >= mid)
            {
                  ltree_delete(ltree->right, i, j);
            }
            else
            {
                  ltree_delete(ltree->left, i, mid);
                  ltree_delete(ltree->right, mid, j);
            }
           
      }
}

//输出线段树

void ltree_print(LTree* ltree, int depth)
{
      if(ltree)
      {
            int i;
            for(i = 0; i < depth; ++i) printf("        ");
            printf("[%d,%d]:%d\n", ltree->i, ltree->j, ltree->cover);
           
            ltree_print(ltree->left, depth + 1);
            ltree_print(ltree->right, depth + 1);
      }
}

//释放线段树内存

void ltree_destroy(LTree* ltree)
{
      if(ltree)
      {
            LTree* pNode = ltree;
            ltree_destroy(ltree->left);
            ltree_destroy(ltree->right);
            //free(pNode);
      }
}

int main(int argc, char** argv)
{
     
      //测试线段树
      LTree* root = ltree_create(1, 10);
      ltree_print(root, 0);
      ltree_insert(root, 3, 6);
      ltree_print(root, 0);
      ltree_insert(root, 7, 9);
      ltree_print(root, 0);
      ltree_delete(root, 3, 5);
      ltree_print(root, 0);
      ltree_destroy(root);
      system("pause");
      return 0;
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
哈希表(HashTable)的简单实现[C语言](原创)发布时间:2022-05-14
下一篇:
二叉搜索树(BST)的实现(C语言)(原创)发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap