[已解决]有没有大佬帮忙看看我的程序哪里出错了

人造人

1613551 发表于 2023-12-12 21:46
我用的vscode，我一直都写的c程序呀

vscode是编辑器，你用的哪个编译器？

人造人

递归转迭代的方法，我大概是真的弄明白了
参考：https://www.zhihu.com/question/20418254
我一开始是写入栈的时候发现 刚进入函数的时候和递归返回之后 这是两个状态，执行的代码是不一样的
于是我弄了一个vector来保存这个状态，如果当前节点在vector里面，那就是 递归返回之后 的状态
但是当我写到中序遍历的时候，发现递归返回之后，还分两种情况，一种是输出当前节点，然后右孩子入栈，另一种是右孩子也递归返回
于是我又给栈里面多弄了一个status变量来区分这两种情况
然后我又发现，其实给这个栈里面添加了一个状态之后，这个状态就完全能够表示递归函数里面的全部情况，所以我就删除了vector，只用栈实现了 前序遍历、中序遍历和后序遍历
下面是代码，你可以先看看能不能看懂

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

typedef size_t tree_elem_t;

typedef struct tree_node_tag {
    struct tree_node_tag *lchild, *rchild;
    tree_elem_t e;
} tree_t;


typedef struct {
    const tree_t *tree;
    size_t status;
} stack_elem_t;

typedef struct {
    stack_elem_t *data;
    size_t size, top;
} stack_t;

stack_t *stack_init(void) {
    stack_t *stack = malloc(sizeof(*stack));
    stack->data = NULL;
    stack->size = stack->top = 0;
    return stack;
}

void stack_deinit(stack_t *stack) {
    free(stack->data);
    free(stack);
}

size_t stack_size(const stack_t *stack) {
    return stack->top;
}

bool stack_empty(const stack_t *stack) {
    return stack_size(stack) == 0;
}

void stack_push(stack_t *stack, stack_elem_t e) {
    if(stack->top == stack->size)
        stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    stack->data[stack->top++] = e;
}

void stack_pop(stack_t *stack) {
    if(stack_empty(stack)) return;
    --stack->top;
}

stack_elem_t stack_top(const stack_t *stack) {
    if(stack_empty(stack)) abort();
    return stack->data[stack->top - 1];
}

typedef const tree_t *vector_elem_t;

typedef struct {
    vector_elem_t *data;
    size_t size;
} vector_t;

vector_t *vector_init(void) {
    vector_t *vector = malloc(sizeof(*vector));
    vector->data = NULL;
    vector->size = 0;
    return vector;
}

void vector_deinit(vector_t *vector) {
    free(vector->data);
    free(vector);
}

size_t vector_size(const vector_t *vector) {
    return vector->size;
}

size_t vector_empty(const vector_t *vector) {
    return vector_size(vector) == 0;
}

void vector_set(vector_t *vector, size_t index, vector_elem_t e) {
    if(index >= vector->size)
        vector->data = realloc(vector->data, sizeof(vector_elem_t) * (vector->size = index + 1));
    vector->data[index] = e;
}

vector_elem_t vector_get(const vector_t *vector, size_t index) {
    if(index >= vector->size) abort();
    return vector->data[index];
}

void vector_append(vector_t *vector, vector_elem_t e) {
    vector_set(vector, vector_size(vector), e);
}

bool vector_find(const vector_t *vector, vector_elem_t e) {
    for(size_t i = 0; i < vector_size(vector); ++i) {
        if(vector_get(vector, i) == e) return true;
    }
    return false;
}

tree_t *tree_init(FILE *fp) {
    tree_elem_t value;
    fscanf(fp, "%zu", &value);
    if(value == -1) return NULL;
    tree_t *root = malloc(sizeof(*root));
    root->e = value;
    root->lchild = tree_init(fp);
    root->rchild = tree_init(fp);
    return root;
}

void tree_deinit(tree_t *tree) {
    if(!tree) return;
    tree_deinit(tree->lchild);
    tree_deinit(tree->rchild);
    free(tree);
}

void tree_traversal_recursion_preorder(const tree_t *tree) {
    if(!tree) return;
    printf("%zu\n", tree->e);
    tree_traversal_recursion_preorder(tree->lchild);
    tree_traversal_recursion_preorder(tree->rchild);
}

void tree_traversal_iteration_preorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    vector_t *vector = vector_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        if(!vector_find(vector, se.tree)) {
            vector_append(vector, se.tree);
            printf("%zu\n", se.tree->e);
            if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
            if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
        } else stack_pop(stack);
    }
    vector_deinit(vector);
    stack_deinit(stack);
}

void tree_traversal_recursion_inorder(const tree_t *tree) {
    if(!tree) return;
    tree_traversal_recursion_inorder(tree->lchild);
    printf("%zu\n", tree->e);
    tree_traversal_recursion_inorder(tree->rchild);
}

void tree_traversal_iteration_inorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    vector_t *vector = vector_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        if(!vector_find(vector, se.tree)) {
            vector_append(vector, se.tree);
            if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
        } else {
            if(se.status == 0) {
                printf("%zu\n", se.tree->e);
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.tree, 1});
                if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
            } else stack_pop(stack);
        }
    }
    vector_deinit(vector);
    stack_deinit(stack);
}

void tree_traversal_recursion_postorder(const tree_t *tree) {
    if(!tree) return;
    tree_traversal_recursion_postorder(tree->lchild);
    tree_traversal_recursion_postorder(tree->rchild);
    printf("%zu\n", tree->e);
}

void tree_traversal_iteration_postorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    vector_t *vector = vector_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        if(!vector_find(vector, se.tree)) {
            vector_append(vector, se.tree);
            if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
            if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
        } else {
            printf("%zu\n", se.tree->e);
            stack_pop(stack);
        }
    }
    vector_deinit(vector);
    stack_deinit(stack);
}

int main(void) {
    tree_t *tree = tree_init(stdin);
    tree_traversal_recursion_postorder(tree);
    printf("\n");
    tree_traversal_iteration_postorder(tree);
    printf("\n");
    tree_traversal_recursion_inorder(tree);
    printf("\n");
    tree_traversal_iteration_inorder(tree);
    printf("\n");
    tree_traversal_recursion_preorder(tree);
    printf("\n");
    tree_traversal_iteration_preorder(tree);
    tree_deinit(tree);
    return 0;
}

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

typedef size_t tree_elem_t;

typedef struct tree_node_tag {
    struct tree_node_tag *lchild, *rchild;
    tree_elem_t e;
} tree_t;


typedef struct {
    const tree_t *tree;
    size_t status;
} stack_elem_t;

typedef struct {
    stack_elem_t *data;
    size_t size, top;
} stack_t;

stack_t *stack_init(void) {
    stack_t *stack = malloc(sizeof(*stack));
    stack->data = NULL;
    stack->size = stack->top = 0;
    return stack;
}

void stack_deinit(stack_t *stack) {
    free(stack->data);
    free(stack);
}

size_t stack_size(const stack_t *stack) {
    return stack->top;
}

bool stack_empty(const stack_t *stack) {
    return stack_size(stack) == 0;
}

void stack_push(stack_t *stack, stack_elem_t e) {
    if(stack->top == stack->size)
        stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    stack->data[stack->top++] = e;
}

void stack_pop(stack_t *stack) {
    if(stack_empty(stack)) return;
    --stack->top;
}

stack_elem_t stack_top(const stack_t *stack) {
    if(stack_empty(stack)) abort();
    return stack->data[stack->top - 1];
}

tree_t *tree_init(FILE *fp) {
    tree_elem_t value;
    fscanf(fp, "%zu", &value);
    if(value == -1) return NULL;
    tree_t *root = malloc(sizeof(*root));
    root->e = value;
    root->lchild = tree_init(fp);
    root->rchild = tree_init(fp);
    return root;
}

void tree_deinit(tree_t *tree) {
    if(!tree) return;
    tree_deinit(tree->lchild);
    tree_deinit(tree->rchild);
    free(tree);
}

void tree_traversal_recursion_preorder(const tree_t *tree) {
    if(!tree) return;
    printf("%zu\n", tree->e);
    tree_traversal_recursion_preorder(tree->lchild);
    tree_traversal_recursion_preorder(tree->rchild);
}

void tree_traversal_iteration_preorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        switch(se.status) {
            case 0:
                printf("%zu\n", se.tree->e);
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.tree, 1});
                if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
                if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
                break;
            case 1:
                stack_pop(stack);
        }
    }
    stack_deinit(stack);
}

void tree_traversal_recursion_inorder(const tree_t *tree) {
    if(!tree) return;
    tree_traversal_recursion_inorder(tree->lchild);
    printf("%zu\n", tree->e);
    tree_traversal_recursion_inorder(tree->rchild);
}

void tree_traversal_iteration_inorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        switch(se.status) {
            case 0:
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.tree, 1});
                if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
                break;
            case 1:
                printf("%zu\n", se.tree->e);
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.tree, 2});
                if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
                break;
            case 2:
                stack_pop(stack);
        }
    }
    stack_deinit(stack);
}

void tree_traversal_recursion_postorder(const tree_t *tree) {
    if(!tree) return;
    tree_traversal_recursion_postorder(tree->lchild);
    tree_traversal_recursion_postorder(tree->rchild);
    printf("%zu\n", tree->e);
}

void tree_traversal_iteration_postorder(const tree_t *tree) {
    stack_t *stack = stack_init();
    stack_elem_t se = {tree, 0};
    stack_push(stack, se);
    while(!stack_empty(stack)) {
        se = stack_top(stack);
        switch(se.status) {
            case 0:
                stack_pop(stack);
                stack_push(stack, (stack_elem_t){se.tree, 1});
                if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
                if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
                break;
            case 1:
                printf("%zu\n", se.tree->e);
                stack_pop(stack);
        }
    }
    stack_deinit(stack);
}

int main(void) {
    tree_t *tree = tree_init(stdin);
    tree_traversal_recursion_postorder(tree);
    printf("\n");
    tree_traversal_iteration_postorder(tree);
    printf("\n");
    tree_traversal_recursion_inorder(tree);
    printf("\n");
    tree_traversal_iteration_inorder(tree);
    printf("\n");
    tree_traversal_recursion_preorder(tree);
    printf("\n");
    tree_traversal_iteration_preorder(tree);
    tree_deinit(tree);
    return 0;
}

1613551

人造人 发表于 2023-12-12 21:47
vscode是编辑器，你用的哪个编译器？

说实话，学了这么久编程我还真不知道自己用的哪个编译器，我就只知道vscode啥都可以编写，写python就把文件后缀改py，写前端就改成html，写c我就改成.c，c++同理

1613551

人造人 发表于 2023-12-13 02:51
嗯，对于图来说，确实需要一个vector来标记已经访问过的节点，不然会死循环，因为有多条路径
改成这样，非 ...

不知道为啥，你这些程序我一个都运行不了

人造人

1613551 发表于 2023-12-13 16:37
不知道为啥，你这些程序我一个都运行不了

说明你用的不是C语言的编译器，看起来你用的是C++的编译器

人造人

1613551 发表于 2023-12-13 16:37
不知道为啥，你这些程序我一个都运行不了

vscode只是一个编辑器，你怎么配置的vscode来编译C语言代码？
在vscode的配置里面配置了个C++编译器吧

人造人

百度，重新配置你的vscode，让他使用C语言的编译器

1613551

人造人 发表于 2023-12-13 16:42
vscode只是一个编辑器，你怎么配置的vscode来编译C语言代码？
在vscode的配置里面配置了个C++编译器吧

我就只装了这个插件

1613551

人造人 发表于 2023-12-13 16:43
百度，重新配置你的vscode，让他使用C语言的编译器

我试试吧