c - Pointer Dequeue——指针训练

Question

我正在尝试在 C 中建立一个双端指针队列。到目前为止，我已经运行并测试了推送功能。我的问题似乎是两端弹出条目。

#include <stdlib.h>
#include <stdio.h>
#include "dequeue.h"

dequeue* dequeue_create()
{
    return NULL;
}
void dequeue_push_front(dequeue** dq, int data)
{
    dequeue* tmp = malloc(sizeof(*tmp));
    tmp->data = data;
    tmp->next=NULL;
    if((*dq) == NULL)
    {
        (*dq) = tmp;
    }
    else
    {
        if ((*dq)->next == NULL)
        {
            (*dq)->next = tmp;
            tmp->prev   = (*dq);

        }
        else
        {

            dequeue* tmp_it  = malloc(sizeof(struct _dequeue_));
            tmp_it = (*dq)->next;
            while(tmp_it->next != NULL)
            {
                tmp_it = tmp_it->next;

            }
            tmp_it->next = tmp;
            tmp->prev    = tmp_it;

        }
    }
}

void dequeue_push_back(dequeue** dq, int data)
{
    dequeue* tmp = malloc(sizeof(struct _dequeue_));
    tmp->data = data;
    tmp->prev=NULL;
    if((*dq) == NULL)
    {
        (*dq) = tmp;
    }
    else
    {

        if ((*dq)->prev == NULL)
        {
            (*dq)->prev = tmp;
            tmp->next   = (*dq);

        }
        else
        {
            dequeue* tmp_it  = malloc(sizeof(struct _dequeue_));
            tmp_it = (*dq)->prev;
            while(tmp_it->prev != NULL)
            {
                tmp_it = tmp_it->prev;
            }
            tmp_it->prev = tmp;
            tmp->next    = tmp_it;

        }
    }
}

int dequeue_pop_front(dequeue** dq)
{
    dequeue* tmp_get = malloc(sizeof(struct _dequeue_));
    int output = 0;

    if((*dq)->next == NULL)
    {
        printf("\ndqnext==null\n");
    }
    else
    {
        tmp_get = (*dq);
        while(tmp_get->next != NULL)
        {
            tmp_get= tmp_get->next;
            output = tmp_get->data;
        }
        tmp_get=tmp_get->prev;
        free(tmp_get->next);
        tmp_get->next=NULL;
    }
    return output;
}

int dequeue_pop_back(dequeue** dq)
{
    dequeue* tmp_get = malloc(sizeof(struct _dequeue_));
    int output = 0;

    if((*dq)->prev == NULL)
    {
        printf("\ndqprev==null\n");
    }
    else
    {
        tmp_get = (*dq);
        while(tmp_get->prev != NULL)
        {

            output = tmp_get->data;
            tmp_get= tmp_get->prev;

        }
        free(tmp_get);
        tmp_get=NULL;
    }
    return output;
}

出队.h:

#ifndef dequeue_H
#define dequeue_H

struct _dequeue_ {
  struct _dequeue_* next;
  struct _dequeue_* prev;
  int data;
};

typedef struct _dequeue_ dequeue;

dequeue* dequeue_create();
void dequeue_destroy(dequeue** queue);

int dequeue_pop_front(dequeue** dq);
void dequeue_push_front(dequeue** dq, int data);

int dequeue_pop_back(dequeue** dq);
void dequeue_push_back(dequeue** dq, int data);

#endif  /* dequeue_H */

主.c:

int main()
{
    dequeue* dq = dequeue_create();

    dequeue_push_front(&dq, 1);
    dequeue_push_back(&dq, 2);
    dequeue_push_front(&dq, 3);
    for (int cnt = 1; cnt <=4; cnt++)
    {
        printf("FINAL=%d ", dequeue_pop_front(&dq));
    }


    //TODO : dequeue_destroy(&dq);

    return 0;
}

我对指针很陌生，这似乎是我的问题。

我在弹出函数中尝试做的是遍历指针以到达最后一个指针并释放最后一个指针。但它似乎并没有释放指针。现在尝试了几种不同的方法，但似乎都不起作用，会不会是我设置推送功能的方式无法释放指针？

非常感谢任何帮助。干杯

Answer 1

在深入研究实际问题之前的一些提示:

• 在 dequeue.c 中，第一个 #include 应该是 dequeue.h 的 #include，因为这是一种确保 dequeue.h 包含其自身所需的一切的系统方法。
• 结构dequeue 应该只称为dequeue。 (后面的 typedef 可以使用相同的名字——这里没问题)

然后，有一些误解:您的 _dequeue_s 是出列的节点，而不是出列本身。所以，你应该有两个结构:

struct dequeue_node {
        struct dequeue_node * next;
        struct dequeue_node * prev;
        int data;
};

struct dequeue {
        struct dequeue_node * frst;
        struct dequeue_node * last;
        size_t size;
};

首先调用条目(而不是首先)是我的个人风格，它使它像 next/prev/last/size 一样长 4 个字符，但如果您愿意，可以先调用它。大小不是必需的，但允许 O(1) 检索出队的大小。

这样，您就不必遍历整个出队就可以找到它的结束。

那么，现在您的实际问题是:

当创建第一个节点时，dequeue_push_front 不会初始化 tmp->prev(并且 dequeue_push_back 不会初始化 tmp->next)。所以，你dequeue从一开始就处于非法状态。

然后，当我想到“front”时，我会想到“first”并假设还有下一个。所以，基本上，您是在交换下一个和上一个的含义。假设这个:

                       a               b               c
                +-------------+ +-------------+ +-------------+
                | next = b    | | next = c    | | next = NULL |
                | prev = NULL | | prev = a    | | prev = b    |
                +-------------+ +-------------+ +-------------+

我会称 a 为“第一个”，c 称其为“最后一个”。但是 dequeue_push_front 尝试在这个 ascii 艺术中添加一个 c 右边的元素。

鉴于您的命名，推送功能似乎是正确的(除了上述几点)。

pop 函数现在有一个错误，s.b 已经注意到了。谁再次删除了他的帖子 Ben Wainwright(他编辑了，显示为帖子删除)。您检查 (*dp)->next/prev == NULL，如果是，则退出，但您应该删除该节点。所以对于 dequeue_pop_front(在你的实现中):

if ((*dq)->next == NULL) {
    dequeue * tmp = (*dq);
    output = tmp->data;
    (*dq) = (*dq)->prev;
    if ((*dq)) {
            (*dq)->next = NULL;
    }
    free(tmp);
} else {
    ...

在 pop_back 中反之亦然。

剩下的问题是效率低下和内存泄漏，对于后者你应该学会使用http://valgrind.org/要找到它们，首先，您应该始终问自己，是否可以将语句移出循环，如下所示:(再次来自 dequeue_pop_front):

    while(tmp_get->next != NULL)
    {
        tmp_get= tmp_get->next;
        output = tmp_get->data; // this can be moved out
    }

输出变量会不断被覆盖，直到循环结束，所以，把它放出来:

    while(tmp_get->next != NULL)
    {
        tmp_get= tmp_get->next;
    }
    output = tmp_get->data; // this can be moved out

所以，最终确定的 dequeue.c(但你真的应该使用 dequeue 和 dequeue_node 进行更改):

dequeue* dequeue_create()
{
    return NULL;
}
void dequeue_push_front(dequeue** dq, int data)
{
    dequeue* tmp = malloc(sizeof(*tmp));
    tmp->data = data;
    tmp->next=NULL;
    tmp->prev=NULL;
    if((*dq) == NULL)
    {
        (*dq) = tmp;
    }
    else
    {
        if ((*dq)->next == NULL)
        {
            (*dq)->next = tmp;
            tmp->prev   = (*dq);

        }
        else
        {

            dequeue* tmp_it  = malloc(sizeof(struct _dequeue_));
            tmp_it = (*dq)->next;
            while(tmp_it->next != NULL)
            {
                tmp_it = tmp_it->next;

            }
            tmp_it->next = tmp;
            tmp->prev    = tmp_it;

        }
    }
}

void dequeue_push_back(dequeue** dq, int data)
{
    dequeue* tmp = malloc(sizeof(struct _dequeue_));
    tmp->data = data;
    tmp->next=NULL;
    tmp->prev=NULL;
    if((*dq) == NULL)
    {
        (*dq) = tmp;
    }
    else
    {

        if ((*dq)->prev == NULL)
        {
            (*dq)->prev = tmp;
            tmp->next   = (*dq);

        }
        else
        {
            dequeue* tmp_it  = malloc(sizeof(struct _dequeue_));
            tmp_it = (*dq)->prev;
            while(tmp_it->prev != NULL)
            {
                tmp_it = tmp_it->prev;
            }
            tmp_it->prev = tmp;
            tmp->next    = tmp_it;

        }
    }
}

int dequeue_pop_front(dequeue** dq)
{
    dequeue* tmp_get = malloc(sizeof(struct _dequeue_));
    int output = 0;

    if((*dq)->next == NULL)
    {
        dequeue * tmp = (*dq);
        output = tmp->data;
        (*dq) = (*dq)->prev;
        if ((*dq)) {
                (*dq)->next = NULL;
        }
        free(tmp);
    }
    else
    {
        tmp_get = (*dq);
        while(tmp_get->next != NULL)
        {
            tmp_get= tmp_get->next;
            output = tmp_get->data;
        }
        tmp_get=tmp_get->prev;
        free(tmp_get->next);
        tmp_get->next=NULL;
    }
    return output;
}

int dequeue_pop_back(dequeue** dq)
{
    dequeue* tmp_get = malloc(sizeof(struct _dequeue_));
    int output = 0;

    if((*dq)->prev == NULL)
    {
        dequeue * tmp = (*dq);
        output = tmp->data;
        (*dq) = (*dq)->next;
        if ((*dq)) {
                (*dq)->prev = NULL;
        }
        free(tmp);
    }
    else
    {
        tmp_get = (*dq);
        while(tmp_get->prev != NULL)
        {

            output = tmp_get->data;
            tmp_get= tmp_get->prev;

        }
        free(tmp_get);
        tmp_get=NULL;
    }
    return output;
}