在间隔树中插入链表元素

Question

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

• l - 下限

• u - 上限

• h - 树的高度

• 链表的顶部。左边和右边分别指向左边的孩子和右孩子。

  #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"，然后在 head->top 中复制 a 的值。这会导致分段错误。

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不会作为引用传递，因此除了分配永远不会释放的内存外，这没有任何效果。

如果要通过引用传递head，请按如下方式声明函数：

void insert_list(list *&head,int i)