1

所以我正在制作一个异或链表，每当我试图为新节点分配内存时，程序就会崩溃。这是我的插入功能代码：

void add(DataType value, XORList ** xlist)
{
    XORListNode * node;
    node = ( XORListNode* )malloc( sizeof (XORListNode) );
    printf("node memory allocated\n");

    if ((*xlist)->head->prevPNext == NULL && (*xlist)->tail->prevPNext == NULL) //XOR linked list is empty: [ H - T ] + N => [ H<->T<->N ] => [ H<->A<->T ]
    {
        node->prevPNext = (*xlist)->tail; //new element points to tail
        (*xlist)->tail->prevPNext = ( XORListNode * )( (uintptr_t)(*xlist)->head ^ (uintptr_t)(*xlist)->tail ); //tail points to head and new value
        (*xlist)->head->prevPNext = (*xlist)->tail;

        (*xlist)->tail->value = value;
        (*xlist)->tail = node;
    }
    else    //Otherwise: [ H<->A<->B<-...->X<->T ] + N => [ H<->A<->B<-...->X<->T<->N ] => [ H<->A<->B<-...->X<->Y<->T ]
    {
        node->prevPNext = (*xlist)->tail;
        (*xlist)->tail->prevPNext = ( XORListNode * )( (uintptr_t)(*xlist)->tail->prevPNext ^ (uintptr_t)node );

        (*xlist)->tail->value = value;
        (*xlist)->tail = node;
    }
}

这是 XORList 的定义：

typedef struct XORList
{
    XORListNode * head, * tail;
} XORList;

这是 XORListNode 的定义：

typedef struct XORListNode
{
    DataType value;
    struct XORListNode * prevPNext;
} XORListNode;

我也很感激有关代码的任何其他评论，因为我还没有使用指针的经验。

感谢您的帮助。

4

1 回答 1

0

这malloc不是您实施的问题。您可以通过删除除前三行之外的整个函数体来测试这一点。

正如 Sourav Ghosh 指出的那样，主要问题是在 if-clause 中使用这些指针之前，您没有检查 if xlist, *xlist, (*xlist)->heador is NULL 。(*xlist)->tailif ((*xlist)->head->prevPNext == NULL && (*xlist)->tail->prevPNext == NULL)

因此，如果您有一个“未初始化”列表head并且tail将会NULL（或者如果您没有将它们设置为NULL它们将是某个值0xcccccccc或完全未定义的值）导致访问冲突，因为您尝试访问的地址不是可用于您的应用程序。

要解决此问题，您必须在 add 函数中处理以下情况：

void add(DataType value, XORList ** xlist)
{
    XORListNode * node;

    if ((xlist == NULL) || ((*xlist) == NULL))
    {
        printf("INVALID INPUT (xlist)\n");
        return;
    }

    node = ( XORListNode* )malloc( sizeof (XORListNode) );
    if (node == NULL)   // always check return values
    {
        printf("FAILED TO ALLOCATE !!!\n");
        return;
    }

    if (((*xlist)->head != NULL) && ((*xlist)->tail != NULL))
    {
        /* your current implementation goes here */
    }
    else
    {
        /*
        ** no item within list, yet!
        ** - initialize head and tail attributes of *xlist
        ** - set node->prevPNext to NULL
        */
    }
}

还有三件事：

  • 我强烈建议为您的XORList结构实现一个零函数，以确保headandtail成员为 NULL。否则它们未初始化，并且检查它们是否为 NULL 将不起作用，并且您再次遇到访问冲突。
  • 为什么你XORList在函数中使用双指针add？对于您发布的代码，单个指针就足够了。
  • 由于malloc在某些情况下可能会失败，因此您应该为 function 实现返回值add。否则调用者无法知道添加是否成功。我会简单地返回node. 如果函数失败，则在成功的情况下返回值为NULL或非零。
于 2015-05-09T18:42:33.430 回答