有没有大佬帮忙看看我的程序哪里出错了,C\C++交流,技术交流,鱼C论坛

人造人 发表于 2023-12-12 21:47:28

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

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

人造人 发表于 2023-12-13 02:26:48

递归转迭代的方法，我大概是真的弄明白了
参考：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 = 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;
}

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 = e;
}

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

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 = 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;
}

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-13 16:34:07

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

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

1613551 发表于 2023-12-13 16:37:45

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

不知道为啥，你这些程序我一个都运行不了{:10_254:}

人造人 发表于 2023-12-13 16:41:00

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

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

人造人 发表于 2023-12-13 16:42:17

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

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

人造人 发表于 2023-12-13 16:43:16

本帖最后由人造人于 2023-12-13 16:44 编辑

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

1613551 发表于 2023-12-13 16:44:54

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

我就只装了这个插件

1613551 发表于 2023-12-13 16:46:55

本帖最后由 1613551 于 2023-12-13 16:49 编辑

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

我试试吧

页: 1 [2]

鱼C论坛's Archiver