c++ - 区间树中链表元素的插入

Question

我通过使用 struct 创建了一个区间树。列表中有要插入的键。定义为

• l - 下限

• u - 上限

• h - 树的高度

• top - 链表的头。 left和right分别指向左 child 和右 child 。

  #include<stdio.h>
  #include<stdlib.h>
  #include<math.h>    
  struct list{
      int data;
      struct list *next;
  };
  
  struct node{
      int l,u,h;
      struct list *top;
      struct node *left,*right;
      };
  int lower[100],upper[100],size;
  struct node *root;
  }
  

我尝试过两种方法。第一个如下，“i”是要插入的元素。我创建了链表头部的拷贝并将其存储在“a”中。我继续直到找到 NULL 指针，此时我插入“i”，然后将 a 的值复制到 head->top 中。导致段错误。

void insert_interval_tree(struct node *head,int i)
{
    if(i<(head->u) && i>=(head->l))
    {
        struct list *a=head->top;
        if(head->top==NULL)
        {
            head->top=(struct list *)malloc(sizeof(struct list));
            head->top->data=i;
            head->top->next=NULL;
        }
        else
        {
            while(head->top->next!=NULL)
                head->top=head->top->next;

            head->top=(struct list *)malloc(sizeof(struct list));
            head->top->data=i;
            head->top->next=NULL;
        }           
        head->top=a;
        return;
    }
    else if(i<(head->l))
        return insert_interval_tree(head->left,i);
    else
        return insert_interval_tree(head->right,i);
}

同样导致段错误的第二种方法是，我制作了一个单独的函数来在尾部插入列表的元素。每次我们想要插入任何元素时，我都会调用此函数。

void insert_list(struct  list *head,int i)
{
    if(head==NULL)
    {
        head=(struct list *)malloc(sizeof(struct list));
        head->data=i;
        head->next=NULL;
    }
    else
    {
        while(head->next!=NULL)
            head=head->next;
        head->next=(struct list *)malloc(sizeof(struct list));
        head->next->data=i;
        head->next->next=NULL;
    }
}
void insert_interval_tree(struct node *head,int i)
{    
    if(i<(head->u) && i>=(head->l))
    {
        insert_list(head->top,i);
        return;
    }
    else if(i<(head->l))
        return insert_interval_tree(head->left,i);
    else
        return insert_interval_tree(head->right,i);
}

树是由用户按排序顺序输入的间隔数组生成的。这是用于构建树的函数

struct node * create_interval_tree(int start,int end)
{
    struct node *head=(struct node *)malloc(sizeof(struct node ));
    head->l=lower[(start+end)/2];
    head->left=NULL;
    head->top=NULL;
    head->u=upper[(start+end)/2];
    head->right=NULL;
    head->h=0;
    if(((start+end)/2)-start>0)
        head->left=create_interval_tree(start,(start+end)/2-1);
    if(end-((start+end)/2)>0)
        head->right=create_interval_tree((start+end)/2+1,end);
    return head;
}

我不明白在上述两种情况下段错误发生在哪里。有人有解决办法吗？

Answer 1

在这两种方法中，您都可以调用 insert_interval_tree(head->left,i) 而不检查 head->left 是否不为 NULL。与head->right相同。这意味着 insert_interval_tree 会被 head==NULL 调用，并且不会在那里进行检查。这就是它崩溃的原因。

还有其他错误。例如，在第二种方法中，在 insert_list 内部修改 head，但是 head 没有作为引用传递，因此 this 没有任何内容除了分配从未释放的内存之外的效果。

如果您想通过引用传递 head，请按如下方式声明该函数:

void insert_list(list *&head,int i)