c - 指针太困惑了 : Stack with singly linked list in C

Question

我是一名学生，正在学习一本名为 Fundamentals of Data Structures in C 的书，并使用 C 实现具有单链表的堆栈。

问题是，我希望这段代码的结果是 <5,3> 和 <9,6>但是控制台只显示 <5,3> 和 <9,3>。

事实上，我不确定我使用的指针是否是问题的根源。

有人可以向我解释为什么我会得到这个结果吗？

完整代码如下:

typedef struct {
int edge[1]; //edge array for saving 2 node's data
} element;

typedef struct stack *stackPointer;
typedef struct stack {
element data;
stackPointer link;
} stack;
stackPointer top[MAX_STACKS];

void initStack();
void push(int i, element item);
element pop(int i);

int top_counter = -1;

int main()
{
    int x, y;

    initStack();

    element *data = malloc(sizeof(element));


    top_counter++;
    data->edge[0] = 9;
    data->edge[1] = 6;

    push(top_counter, *data);


    top_counter++;
    data->edge[0] = 5;
    data->edge[1] = 3;

    push(top_counter, *data);

    *data = pop(top_counter);
    x = data->edge[0];
    y = data->edge[1];
    printf("<%d,%d>\n", x, y);
    top_counter--;

    *data = pop(top_counter);
    x = data->edge[0];
    y = data->edge[1];
    printf("<%d,%d>\n", x, y);
    top_counter--;

    // result of this code
    // <5, 3>
    // <9, 3>
    // WHY?!?!?!?!??!

}


void initStack() {
    for (int i = 0; i < MAX_STACKS; i++) {
        top[i] = NULL;
    }

}

void push(int i, element item) {
    // push item to top[i]
    stackPointer temp;
    temp = (stackPointer)malloc(sizeof(*temp));
    temp->data = item;
    temp->link = top[i];
    top[i] = temp;

}

element pop(int i) {
    stackPointer temp = top[i];
    element item;
    if (!temp) printf("\nStack Empty\n");
    item = temp->data;
    top[i] = temp->link;
    free(temp);
    return item;
}

Answer 1

正如 Jaybird 在对问题的评论中指出的那样，问题在于元素类型只包含一个 int，而不是两个。

但是，该代码对于示例来说过于复杂，因为它没有实现单个堆栈，而是实现了 MAX_STACKS 个堆栈。这就是为什么代码看起来很奇怪，而不是您在现实代码中可能看到的东西。

考虑以下反例:

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

struct node {
    struct node *next;
    int          data[2];
};

struct node *new_node(const int data0, const int data1)
{
    struct node *n;

    n = malloc(sizeof *n);
    if (!n) {
        fprintf(stderr, "new_node(): Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    n->next = NULL;
    n->data[0] = data0;
    n->data[1] = data1;

    return n;
}

void free_node(struct node *n)
{
    if (n) {
        /* Poison the node, so we can more easily
           detect use-after-free bugs. */
        n->next    = NULL;
        n->data[0] = -1;
        n->data[1] = -1;

        free(n);
    }
}

将单个节点推送(添加)到链表中，

void push_node(struct node **listptr, struct node *n)
{
    if (!listptr) {
        fprintf(stderr, "push_node(): No linked list (listptr is NULL).\n");
        exit(EXIT_FAILURE);
    } else
    if (!n) {
        fprintf(stderr, "push_node(): No node to push (n is NULL).\n");
        exit(EXIT_FAILURE);
    }

    n->next = *listptr;
    *listptr = n;
}

从链表中弹出第一个节点，

struct node *pop_node(struct node **listptr)
{
    if (!listptr) {
        fprintf(stderr, "pop_node(): No linked list specified (listptr is NULL).\n");
        exit(EXIT_FAILURE);

    } else
    if (!*listptr) {
        /* Linked list is empty, return NULL. */
        return NULL;

    } else {
        struct node *n;

        n = *listptr;
        *listptr = n->next;
        n->next = NULL;

        return n;
    }
}

为了调试，我们可以使用打印堆栈内容的例程:

void show_list(struct node *first, FILE *out)
{
    if (out) {
        fputs("[", out);
        while (first) {
           fprintf(out, " <%d,%d>", first->data[0], first->data[1]);
           first = first->next;
        }
        fputs(" ]\n", out);
    }
}

为了测试，我们写了一个小的 main():

int main(void)
{
    struct node *odds = NULL;
    struct node *evens = NULL;
    struct node *n;

    /* Push <1,3> and <5,7> to odds. */
    push_node(&odds, new_node(1, 3));
    push_node(&odds, new_node(5, 7));

    /* Push <2,2>, <4,2>, and <6,8> to evens. */
    push_node(&evens, new_node(2,2));
    push_node(&evens, new_node(4,2));
    push_node(&evens, new_node(6,8));

    /* Push <3,3> to odds. */
    push_node(&odds, new_node(3,3));

    /* Show the two stacks. */
    printf("odds stack after the pushes: ");
    show_list(odds, stdout);
    printf("evens stack after the pushes: ");
    show_list(evens, stdout);

    /* Pop each node off from the odds stack,
       and push them into the evens stack. */
    while ((n = pop_node(&odds)))
        push_node(&evens, n);

    /* Show the stacks again. */
    printf("odds stack after the while loop: ");
    show_list(odds, stdout);
    printf("evens stack after the while loop: ");
    show_list(evens, stdout);

    /* Pop each node from evens stack, and display it. */
    while ((n = pop_node(&evens))) {
        printf("<%d, %d>\n", n->data[0], n->data[1]);
        free_node(n);
    }

    printf("All done.\n");
    return EXIT_SUCCESS;
}

如果你编译并运行上面的代码，它会输出

odds stack after the pushes: [ <3,3> <5,7> <1,3> ]
evens stack after the pushes: [ <6,8> <4,2> <2,2> ]
odds stack after the while loop: [ ]
evens stack after the while loop: [ <1,3> <5,7> <3,3> <6,8> <4,2> <2,2> ]
<1, 3>
<5, 7>
<3, 3>
<6, 8>
<4, 2>
<2, 2>
All done.

几个句法细节:

• push 和 pop 操作修改指向列表中第一个节点的指针。如果您只传递指针本身，那么调用者将看不到该修改。这就是为什么指向指针 **listptr 的指针被用作参数，并且 *listptr 在访问指向列表中第一个节点的指针时在函数中使用的原因。

• if (out) 等同于 if (out != NULL) 当 out 是指针时。

• while ((n = pop_node(&odds))) { ... } 等同于 while ((n = pop_node(&odds)) != NULL) { ... 。另一种写循环的方法是

      while (1) {
  
          n = pop_node(&odds);
          if (n == NULL)
              break;
  
          ...
  
      }
  

  即n 首先被分配，然后与 NULL 进行比较。这是一种非常常见的速记形式。

  • if (!listptr) 等同于 if (listptr == NULL)。

  记住区别的一种方法是朗读非运算符 !，大声读出“not”或“no”。因此，if (!listptr) 读作“如果没有 listptr”。

考虑一下当您从一个堆栈中弹出项目并将它们插入另一个堆栈时会发生什么。他们的顺序被颠倒了。掌握它如何与三个 堆栈一起工作是 Tower of Hanoi / Tower of Brahma / Lucas' Tower 的原因太有趣了。

---

在这个例子中，根本没有“堆栈”抽象数据类型。压入和弹出操作的堆栈句柄只是指向第一项的指针。如果你想使用链表的相同句柄来实现堆栈和队列，你可以使用

typedef struct {
    struct node *newest; /* or first in list */
    struct node *oldest; /* or last in list */
} storq;
#define  STORQ_INIT  { NULL, NULL }

这样你就可以声明一个空的堆栈或队列使用

storq  stuff = STORQ_INIT;

无需调用一些 storq_init(&stuff); 函数将其初始化为已知(空)状态以供使用。

上面不是完全对称的，因为它允许恒定时间(O(1) 时间复杂度)storq_push()(推送或前置)， storq_pop() 和 storq_unshift()(类似于 push，但在队列/堆栈的另一端)操作，而 storq_shift()(类似于 pop ，但在队列/堆栈的另一端)将是“慢”(O(N)时间复杂度，其中 N 是队列/堆栈中的节点数)。

为了完整性，省略错误检查的操作是

void storq_push(storq *sq, struct node *n)
{
    n->next = sq->newest;
    sq->newest = n;
    if (!sq->oldest)
        sq->oldest = n;
}

void storq_unshift(storq *sq, struct node *n)
{
    n->next = NULL;
    if (sq->oldest) {
        sq->oldest->next = n;
    } else {
        sq->newest = n;
        sq->oldest = n;
    }
}

struct node *storq_pop(storq *sq)
{
    if (sq->newest) {
        struct node *n;

        n = sq->newest;
        if (n->next) {
            sq->newest = n->next;
        } else {
            sq->newest = NULL;
            sq->oldest = NULL;
        }

        n->next = NULL;

        return n;

    } else {
        return NULL;
    }
}

为了理解它们是如何工作的，我建议画图，每个节点用椭圆表示，箭头表示 next 成员指向的位置。 storq 句柄本身是一个带有两个箭头的框，一个指向列表中的第一个/最新成员，另一个指向列表中最后一个/最旧的成员。

对于每个操作(push、unshift、pop)，需要考虑三种情况:当列表为空时，当列表只有一个项目时，当列表有很多项目时。如果您找出全部九个函数，您就会了解上述函数的工作原理，以及它们为何如此行事。