Question

C语言栈的问题，我main函数是想压入进栈1,2,3,4,5显示出来，可是运行的时候崩溃了，求解

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

struct node {
int value;
struct node *next;
};

struct node *chuangjian(void); //创建一个空栈
void push(struct node *head, int x); //压入栈
void print_stack(struct node *head); //显示栈里的元素
int is_empty(struct node *head); //是否是空栈
int top(struct node *head); //返回栈顶
void pop(struct node *head); //出栈
void make_empty(struct node *head1); //确保栈为空栈

int main(void)
{
struct node *head;
int n, i, x[100];
head = chuangjian();
printf("输入你想压入几个元素入栈: ");
scanf_s("%d", &n);
for (i = 0;i < n;i++) {
printf("你想压入多少进栈: ");
scanf_s("%d", &x[i]);
push(head, x[i]);
}
print_stack(head);
return 0;
}

struct node *chuangjian(void)
{
struct node *head;
head = (struct node *) malloc(sizeof(struct node));
if (head == NULL) {
printf("创建空栈的时候出现错误\n");
exit(EXIT_FAILURE);
}
head->next = NULL;
make_empty(head); //确保此栈为空栈
return head;
}

void make_empty(struct node *head) //确保此栈为空栈
{
if (head == NULL) {
printf("no\n");
exit(EXIT_FAILURE);
}
else {
while (is_empty(head) != 1) {
pop(head);
}
}
}

void push(struct node *head, int x)
{
struct node *t;
t = (struct node *) malloc(sizeof(struct node));
if (t == NULL) {
printf("压栈出错\n");
exit(EXIT_FAILURE);
}
else {
t->value = x;
t->next = head;
head = t;
}
}

int is_empty(struct node *head)
{
return head == NULL; // 1为空栈，0为非空栈
}

int top(struct node *head)
{
if (is_empty(head) != 1) {
return head->value;
}
return 0;
}

void pop(struct node *head)
{
struct node *t = NULL;
if (is_empty(head) == 1) {
printf("栈的元素以弹出完毕\n");
}
else {
head = t;
t = t->next;
free(head);
}
}

void print_stack(struct node *head)
{
printf("栈内元素是: ");
while (head != NULL) {
printf("%d ", head->value);
head = head->next;
}
printf("\n");
}

Answer 1

我觉得

is_empty

的判定应该是

head->next == NULL;

而不是head == NULL;

还有就是，push和pop要修改到head本身，所以传参要传入指向head的指针

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

struct node {
	int value;
	struct node *next;
};

struct node *chuangjian(void);  //创建一个空栈
void push(struct node **head, int x);        //压入栈
void print_stack(struct node *head);  //显示栈里的元素
int is_empty(struct node *head);  //是否是空栈
int top(struct node *head);     //返回栈顶
void pop(struct node **head);  //出栈
void make_empty(struct node **head1);  //确保栈为空栈

int main(void)
{
	struct node *head;
	int n, i, x[100];
	head = chuangjian();
	printf("输入你想压入几个元素入栈: ");
	scanf("%d", &n);
	for (i = 0;i < n;i++) {
		printf("你想压入多少进栈: ");
		scanf("%d", &x[i]);
		push(&head, x[i]);
		getchar();
	}
	print_stack(head);
	return 0;
}

struct node *chuangjian(void)
{
	struct node *head;
	head = (struct node *) malloc(sizeof(struct node));
	if (head == NULL) {
		printf("创建空栈的时候出现错误\n");
		exit(EXIT_FAILURE);
	}
	head->next = NULL;
	make_empty(&head);   //确保此栈为空栈
	return head;
}

void make_empty(struct node **head)       //确保此栈为空栈
{
	if (head == NULL) {
		printf("no\n");
		exit(EXIT_FAILURE);
	}
	else {
		while (is_empty(*head) != 1) {
			pop(head);
		}
	}
}

void push(struct node **head, int x)
{
	struct node *t;
	t = (struct node *) malloc(sizeof(struct node));
	if (t == NULL) {
		printf("压栈出错\n");
		exit(EXIT_FAILURE);
	}
	else {
		t->value = x;
		t->next = *head;
		*head = t;
	}
}

int is_empty(struct node *head)
{
	return head->next == NULL;   // 1为空栈，0为非空栈
}

int top(struct node *head)
{
	if (is_empty(head) != 1) {
		return head->value;
	}
	return 0;
}

void pop(struct node **head)
{
	struct node *t = NULL;
	if (is_empty(*head) == 1) {
		printf("栈的元素以弹出完毕\n");
	}
	else {
		*head = t;
		t = t->next;
		free(*head);
	}
}

void print_stack(struct node *head)
{
	printf("栈内元素是: ");
	while (head->next != NULL) {
		printf("%d ", head->value);
		head = head->next;
	}
	printf("\n");
}

追问

书上的代码就是这个差不多，我知道怎么改就是理解不了，我不理解为什么不能是head,而必须是head->next

追答

你直接使用head就有问题了，因为你创建栈的时候，就创建了一个元素，而且head指向了这个元素，但是这个元素并没有存值。而之后的push也都各自申请了新的空间。也就是有一个栈底元素没有使用，所以，判定就是判定栈底元素，而不是head为空，如果head为空，就说明这个栈根本不存在

追问

我还是不理解为什么不能是head,而必须是head->next，而且不用是**head，直接把下面的head都改成head->next，但我不知道为什么，比如压栈的时候，不应该是t是栈底，t的下一个是head吗，为什么非得是t->next = head->next，按您所说的话，我应该怎么改不用写成head->next也不用指向指针的指针？感觉非要多出一个不用的栈底的话感觉出栈什么的不好写了

追答

你要弄成空栈head为NULL也不是不可以，但是，需要改变pop的方式

追问

不明白，就改pop一个函数吗？如果不改，最后pop的时候那个没用的栈底也出去了？会不会出错？

追答

我调试了一下，你的pop函数是有问题的

pop的执行顺序有问题，应该是这样的逻辑

1. 保存head->next的值

2. 释放head，free(head);

3. 改写head为head->next;

   出现的问题就是因为创建完栈之后，没有判定到空，进行了一次pop操作，释放了一个非法指针

追问

head如果先被释放了，怎么进行head=head->next这一步？还有，我现在这样的写法多出了一个没用的栈底，是不是算不上真正的栈了？

追答

先保存了head->next的值，用保存的值来赋值head
其实多出来的不应该是栈底，应该是栈顶，按照物理栈的模式，sp指向的栈顶是空的，还未存放数据的状态

追问

还是不大理解，能写几句代码吗？

追答

通常物理栈有一个sp指针指向栈顶，栈顶是空的，没有放数据
当执行push操作的时候，先把值放入sp指向的内存，然后对sp进行自减（有的是自增，看处理器）使sp指向新的栈顶，新的栈顶仍然是空的
就你的程序，创建栈的时候，就相当于创建了一个栈顶，是空的，没有数据，当有push操作的时候，栈顶依然是栈顶，栈顶下一个数据是新push的数据，只需要让栈顶指向新数据，而新数据指向之前栈顶指向的位置就可以了