有关堆栈如何在C中工作的说明
我只是想在将数据推送到堆栈时对链接过程进行简单的解释。 我知道如何使用我书中的代码,但是当我将堆栈头链接从一个链接移动到另一个时,我不确定我是否理解该过程如何工作。
对于像这样的堆栈:
typedef struct node { void dataptr; struct node* link; }STRUCT_NODE; typedef struct { int count; STACK_NODE* top; }STACK;
如何更改链接以指向堆栈上推送的新数据。 我也不知道
堆栈可以通过各种方式实现,但是按照你的问题的方式我假设你的堆栈只是一个链表,类似于
head ↓ A → B → C → D → 0
“当你将堆栈头链接从一个移动到下一个”时,图片只会变为:
head ↓ A → B → C → D → 0
当然A在这个图中不再可以访问,所以你最好在某个地方有另一个指向它的指针(只是处理它),但这是如何弹出堆栈的要点(通过使head = head->next
如果堆栈中的每个节点都是一个struct node
,其next
字段是一个struct node*
,当然head
也是一个struct node*
。
这是为了从堆栈中弹出一些东西(在这种情况下你应该释放A
使用的内存)。 在详细步骤中,它将是:
1 /保存旧头。
head ↓ old → A → B → C → D → 0
2 /调整头部。
head ↓ old → A → B → C → D → 0
3 /回头(旧指着)。
相反,如果您正在谈论将某些东西推入堆栈,那么这是一个涉及以下操作的操作:
1 /创建一个新元素。
head ↓ ZA → B → C → D → 0
2 /指向当前的头部
head ↓ Z → A → B → C → D → 0
3 /调整头部指向它。
head ↓ Z → A → B → C → D → 0
给定表示堆栈上节点的数据结构,以及实际堆栈本身:
typedef struct node { void *dataptr; struct node *link; } NODE; typedef struct { int count; NODE *top; } STACK;
您将按如下方式初始化堆栈:
STACK myStack; myStack.count = 0; myStack.top = NULL;
这基本上给你一个空堆栈。 我将使用top
来判断堆栈是否为空 – 您可以使用count
或top
(分别为0
或NULL
)来完成这项工作但是最好选择一个并坚持使用以防万一你写将来缓存计数和实际计数失效的一些错误代码:-)
要将节点推送到堆栈,这是一个简单的操作:
- 分配新节点并设置有效负载(1)。
- 将新节点的链接指向当前头部。
- 将头指向新节点(3)。
- 递增计数(4)。
以下代码显示了如何执行此操作:
/* 1 */ NODE *newNode = malloc (sizeof (NODE)); // should check for failure. newNode->dataptr = NULL; /* 2 */ newNode->link = myStack.top; /* 3 */ myStack.top = newNode; /* 4 */ myStack.count++;
这将推入空堆栈或填充堆栈。 空堆栈的边缘情况将newNode.link
设置为NULL
,然后myStack.top
设置为newNode
,这是正确的行为。
要从堆栈中弹出节点:
- 保存当前头部(1)。
- 如果当前头不是NULL,则前进到其链接(并减少计数)。
- 返回保存的当前头部(3)。
翻译成代码的是:
/* 1 */ NODE *popNode = myStack.top; /* 2 */ if (myStack.top != NULL) { myStack.top = myStack.top->link; myStack.count--; } /* 3 */ return popNode;
这将返回弹出节点的地址,如果堆栈为空,则返回NULL
。
整个操作集可以封装如下。 希望这些评论能够与上述评论一起使其不言自明,但随时提出任何疑虑,我将通过编辑解决这些问题。
// Error codes (probably should be enums). #define STACK_ERR_OKAY 0 #define STACK_ERR_NOTEMPTY 1 #define STACK_ERR_NOPAYLOAD 2 #define STACK_ERR_NOMEMORY 3 // Structures. typedef struct sNode { void *data; // Payload pointer. struct sNode *next; // Link to next node. } tNode; typedef struct { int count; // Count for fast sizing. NODE *top; // First node. } tStack; // Make a new stack returning its pointer or NULL on failure. tStack *stackNew (void) { tStack stack = malloc (sizeof (tStack)); if (stack != NULL) { stack->count = 0; stack->top = NULL; } return stack; } // Delete a current stack, must be empty first. int stackDel (tStack *stack) { if (stack->top != NULL) return STACK_ERR_NOT_EMPTY; free (stack); return STACK_ERR_OK; } // Push a pointer payload (no NULLs allowed) onto the stack. int stackPush (tStack *stack, void *payload) { if (payload == NULL) return STACK_ERR_NOPAYLOAD; tNode *node = malloc (sizeof (tNode)); if (node == NULL) return STACK_ERR_NOMEMORY; node->data = payload; node->next = stack->top; stack->top = node; stack->count++; return STACK_ERR_OK; } // Pop a pointer payload from the stack. Returns NULL if stack was empty. int stackPop (tStack *stack) { tNode *node = stack->top; if (node == NULL) { return NULL; stack->top = node->next; stack->count--; return node->data; } // Get stack size. int stackSize (tStack *stack) { return stack->count; }
我之所以坚持在删除之前必须为空的原因是因为代码不确定有效负载是什么。 它可能是一个指向内存块(浅)的简单指针,在这种情况下你可以使用:
void stackDel (tStack *stack) { tNode *node = stackPop (stack); while (node != NULL) { free (node); node = stackPop (stack); } free (stack); }
但是,如果它是一个指向内存的指针,其他指针指向内存,则自动释放它引用的内存会更加成问题(它可能最好作为对API调用者的回调来完成,因为它将是唯一知道的内容确定如何正确释放内存)。 更简单的做法是让前面的呼叫者成为先决条件。
假设您有一个名为my_stack的STACK和一个名为my_node的STACK_NODE。 要将my_node添加到my_stack,请执行以下操作:
my_node.link = my_stack.top; my_stack.top = &my_node; my_stack.count = my_stack.count + 1;