区间树插入链表元素

Question

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

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 的值复制到头部 - >top.This 导致分段错误。

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)

区间树插入链表元素

Insertion of linked list elements in interval tree

c

c++

tree

linked-list

segmentation-fault