C语言使用栈反转链表

Question

C语言使用栈反转链表
为什么代码1可以完成，而代码2无法完成

代码1

#include<stdio.h>
#include<stdlib.h>
#define max_size 101
typedef struct 
{
    char data[max_size];
    int first;
}stack;
struct node
{
    int data;
    struct node* next;
};
struct node* head;
void head_insert(int data){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    temp->next = head;
    head = temp;
}
void print(){
    struct node* temp = head;
    while (temp != NULL)
    {
        printf(" %d",temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void init(stack *s){
    s->first = -1;
}
void push(stack *s,char str){
    if (s->first == max_size-1)
    {
        return;
    }
    s->data[s->first++] = str;
}
char top(stack *s){
    return s->data[--s->first];
}
void reverse(){
    stack s;
    init(&s);
    struct node* temp = head;
    while (temp != NULL)
    {
        push(&s,temp->data);
        temp = temp->next;
    }
    temp = head;
    while (temp != NULL)
    {
        temp->data = top(&s);
        temp = temp->next;
    }
}
int main(){
    //创建一个链表
    head = NULL;
    head_insert(2);
    head_insert(3);
    head_insert(4);
    head_insert(5);
    print();// 5 4 3 2
    //反转一个链表
    reverse();
    print();// 2 3 4 5
}

代码2

#include<stdio.h>
#include<stdlib.h>
#define max_size 101
typedef struct 
{
    char data[max_size];
    int first;
}stack;
struct node
{
    int data;
    struct node* next;
};
struct node* head;
void head_insert(int data){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    temp->next = head;
    head = temp;
}
void print(){
    struct node* temp = head;
    while (temp != NULL)
    {
        printf(" %d",temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void init(stack *s){
    s->first = -1;
}
void push(stack *s,char str){
    if (s->first == max_size-1)
    {
        return;
    }
    s->data[s->first++] = str;
}
void pop(stack *s){
    if (s->first == -1)
    {
        return;
    }
    s->first--;
}
char top(stack *s){
    return s->data[s->first];
}
void reverse(){
    stack s;
    init(&s);
    struct node* temp = head;
    while (temp != NULL)
    {
        push(&s,temp->data);
        temp = temp->next;
    }
    temp = head;
    while (temp != NULL)
    {
        temp->data = top(&s);
        pop(&s);
        temp = temp->next;
    }
}
int main(){
    //创建一个链表
    head = NULL;
    head_insert(2);
    head_insert(3);
    head_insert(4);
    head_insert(5);
    print();// 5 4 3 2
    //反转一个链表
    reverse();
    print();// 2 3 4 5
}

Answer 1

引用 皆我百晓生 小程序回复内容作答：

代码1可以完成链表的反转，而代码2无法完成链表的反转的原因是在代码2中，pop函数没有正确地更新栈的指针位置。在push函数中，s->first++表示将元素插入栈顶，而在pop函数中，s->first--应该表示将栈顶元素弹出，但是代码2中的pop函数实际上没有更新栈顶指针的位置，导致在第二次循环中，temp->data = top(&s)会一直取到栈底的元素，而不是栈顶的元素。因此，代码2无法正确地完成链表的反转。要修复代码2，需要在pop函数中添加s->first--的操作来正确更新栈顶指针的位置。