我有一个Node结构体,我在C中的堆栈实现中使用了该结构体:这是:
/* Do not modify */
#ifndef CQUEUE_H
#define CQUEUE_H
struct node_struct {
char *data;
struct node_struct *next;
};
typedef struct node_struct Node;
struct stack_struct {
Node *head, *tail;
};
typedef struct stack_struct Stack;
我已经实现了通常在堆栈实现中找到的函数,如push,print等,但我似乎对我的pop函数有问题,下面是我的实现:
char* pop(Stack* q) {
if (isEmpty(q)) {
return NULL;
}
Node* temp = q->head;
char* A = temp->data;
q->head = temp->next;
free(temp);
return A;
}
int isEmpty(Stack* q) {
return (q == NULL);
}
我有一个文件,我的预期输出应该是:
No items
//Push
a
b
c
//Pop
a
b
c
但我的代码
No items
//Push
a
b
c
//Pop
a
Segmentation fault
我的代码有什么问题?
编辑:如果有问题,这里是我的完整代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "stack.h" \\this is where the struct that I mentioned above is defined
void push(Stack** q, char* word) {
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->data = word;
newnode->next = NULL;
Stack* temp = *q;
if (temp == NULL) {
temp = (Stack*)malloc(sizeof(Stack));
temp->head = newnode;
temp->tail = newnode;
} else {
newnode->next = temp->head;
temp->head = newnode;
}
*q = temp;
}
char* pop(Stack* q) {
if (q == NULL) {
return NULL;
}
Node* temp = q->head;
char* A = temp->data;
q->head = temp->next;
free(temp);
return A;
}
void print(Stack *q) {
if (!isEmpty(q)) {
Node *curr_node = q->head;
while (curr_node != NULL) {
printf("%s\n", curr_node->data);
curr_node = curr_node->next;
}
} else {
printf("No items\n");
}
}
int isEmpty(Stack* q) {
return (q == NULL);
}
void delete(Stack** q) {
Stack* temp = *q;
Node* curr_node = temp->head;
while (curr_node != NULL) {
Node* next_node = curr_node->next;
free(curr_node->data);
free(curr_node);
curr_node = next_node;
}
free(temp);
*q = NULL;
}
int main(void) {
Stack *q = NULL;
// print the stack
print(q);
// push items
push(&q, "a");
push(&q, "b");
push(&q, "c");
print(q);
// pop items
while (!isEmpty(q)) {
char *item = pop(q);
printf("%s\n", item);
free(item);
}
char *item = pop(q);
assert(item == NULL);
// push again
push(&q, "d");
push(&q, "e");
push(&q, "f");
print(q);
// destroy the stack
delete(&q);
// print again
print(q);
// check copy
char *s = (char *)malloc(10);
strcpy(s, "Hello");
push(&q, s);
strcpy(s, "World");
char *t = pop(q);
printf("s = %s\n", s);
printf("t = %s\n", t);
free(t);
free(s);
// free the stack
free(q);
}
1条答案
按热度按时间67up9zun1#
对于初学者,函数
pop
定义如下从不将指向动态分配堆栈的原始指针设置为
NULL
。所以这个while循环已经调用了未定义的行为。
堆栈存储指向具有静态存储持续时间的字符串文字的指针。所以这份声明
还调用未定义的行为。
函数
delete
中也存在同样的问题您的堆栈应该存储动态分配的字符串,这些字符串是所用字符串的副本。在这种情况下,您确实需要为字符串释放已分配的内存。
Stack类型的对象不应在函数
push
内部动态分配。该函数应该向已经存在的堆栈添加新节点。堆栈本身也不应该有数据成员
tail
。堆栈不是队列。所以它应该只有数据成员head
,可能还有堆栈中的节点数。