3

我是一个初级 C 程序员,正在编写一个涉及队列操作的练习题,在调试时,我遇到了以下场景:

代码示例 1

int dequeue (struct queue_node * Q) {

    struct queue_node * curr = Q->next;
    if(!Q->next)
            return -2;
    else
    {
            int s = Q->next->v_no;
            Q->next = curr->next;
            free(curr);
            return s;
    }

}

代码示例 2(以稍微修改的方式编写的相同函数):

int dequeue (struct queue_node * Q) {

    struct queue_node * curr = Q;
    if(!curr->next)
            return -2;
    else
    {
            int s = curr->next->v_no;
            Q->next = curr->next->next;
            free(curr->next);
            return s;
    }

}

预定义的数据结构如下

struct queue_node {

    int v_no;
    struct queue_node * next;

};

void enqueue (struct queue_node * Q , int s) {

    struct queue_node * curr = Q;
    while (curr->next)
            curr = curr->next;

    curr->next = malloc(sizeof(struct queue_node));
    if(!curr->next)
            exit(10);   //No specific reason for errno 10, just wanted to exit
    curr->next->v_no = s;
    curr->next->next = NULL;

}

问题: 场景 1 中的代码允许程序成功执行并输出预期的答案,但根据我的理解,场景 2 中的代码也尝试实现相同的目标,但给出了分段错误。有人可以指出我的理解是否有缺陷,或者我的代码本身有什么问题吗?

谢谢!

4

5 回答 5

5

假设您的队列结构当前具有三个元素:

{a} -> {b} -> {c} -> NULL

当前Q指向.b

让我们来看看你的每个函数会做什么。

/* Example 1 (working) */
int dequeue (struct queue_node * Q) {

    struct queue_node * curr = Q->next;    // curr = {c}
    if(!Q->next)                           // c != NULL, so OK
            return -2;
    else
    {
            int s = Q->next->v_no;         // s = c.v_no
            Q->next = curr->next;          // Q->next = NULL
            free(curr);                    // free({c})
            return s;                      // return c.v_no
    }
}

因此,示例 1 提供了一个指向 Q 节点的指针,它使下一个节点出列并删除,返回其v_no.

/* Example 2 (segfaults) */
int dequeue (struct queue_node * Q) {

    struct queue_node * curr = Q;          // curr now points to the same element as q
    if(!curr->next)                        // {b}->next == {c}, so OK
            return -2;          
    else 
    {
            int s = curr->next->v_no;      // s = Q
            Q->next = curr->next->next;    // Q->next = NULL ({c}->next)
            free(curr->next);              // same as free (Q->next) == free(null)
            return s;
    }

}

所以在第二个例子中,你释放了一个空指针——段错误!

于 2013-10-22T16:58:20.007 回答
4

问题是你在哪里释放。这是一个有效的:

int s = Q->next->v_no;
Q->next = curr->next;
free(curr);

这是一个没有的:

int s = curr->next->v_no;
Q->next = curr->next->next;
free(curr->next);

请记住,在第二种情况下,您有curr= Q。因此,在第一个中,我们设置Q->nextQ->next->next,然后删除 Q->next的。

在第二个中,我们设置Q->nextQ->next->next,但随后我们删除了当前 Q->next的。

于 2013-10-22T16:57:04.750 回答
3

这就是场景 2 中的问题:

curr = Q;          
...  
Q->next = curr->next->next;   
free(curr->next);

因为Q == curr如果你设置Q->next到另一个指针,你也会改变curr->next. 所以 subsequenffree(curr->next)不会释放 dequed 元素,而是释放新分配的元素。

于 2013-10-22T16:56:14.627 回答
3

在第二个代码部分中,当您执行以下操作时:

curr = Q;

接着:

Q->next = curr->next->next;

Q并且curr指向相同的东西,所以当你改变时Q->next,你也在改变curr->next,你的调用free(curr->next)出错了。

在第一个代码部分中,在开头curr设置为,而不是,因此当您更改时,不受影响,因此您的指针正确。Q->nextQQ->nextcurrfree()

于 2013-10-22T16:56:50.227 回答
0

下线导致问题

 Q->next = curr->next->next;

因为 Q 和 curr 是同一个指针,所以在赋值之后, Q->next 可以为空(如果您的队列只有一个元素)。所以,当你打电话

free(curr->next);

您正在尝试释放 null。还有逻辑错误,你永远不会释放出队的元素。

于 2013-10-22T17:01:34.100 回答