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

人造人

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

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

人造人

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. #include <string.h>
   
5. 
   
6. typedef size_t tree_elem_t;
   
7. 
   
8. typedef struct tree_node_tag {
   
9.     struct tree_node_tag *lchild, *rchild;
   
10.     tree_elem_t e;
    
11. } tree_t;
    
12. 
    
13. 
    
14. typedef struct {
    
15.     const tree_t *tree;
    
16.     size_t status;
    
17. } stack_elem_t;
    
18. 
    
19. typedef struct {
    
20.     stack_elem_t *data;
    
21.     size_t size, top;
    
22. } stack_t;
    
23. 
    
24. stack_t *stack_init(void) {
    
25.     stack_t *stack = malloc(sizeof(*stack));
    
26.     stack->data = NULL;
    
27.     stack->size = stack->top = 0;
    
28.     return stack;
    
29. }
    
30. 
    
31. void stack_deinit(stack_t *stack) {
    
32.     free(stack->data);
    
33.     free(stack);
    
34. }
    
35. 
    
36. size_t stack_size(const stack_t *stack) {
    
37.     return stack->top;
    
38. }
    
39. 
    
40. bool stack_empty(const stack_t *stack) {
    
41.     return stack_size(stack) == 0;
    
42. }
    
43. 
    
44. void stack_push(stack_t *stack, stack_elem_t e) {
    
45.     if(stack->top == stack->size)
    
46.         stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    
47.     stack->data[stack->top++] = e;
    
48. }
    
49. 
    
50. void stack_pop(stack_t *stack) {
    
51.     if(stack_empty(stack)) return;
    
52.     --stack->top;
    
53. }
    
54. 
    
55. stack_elem_t stack_top(const stack_t *stack) {
    
56.     if(stack_empty(stack)) abort();
    
57.     return stack->data[stack->top - 1];
    
58. }
    
59. 
    
60. typedef const tree_t *vector_elem_t;
    
61. 
    
62. typedef struct {
    
63.     vector_elem_t *data;
    
64.     size_t size;
    
65. } vector_t;
    
66. 
    
67. vector_t *vector_init(void) {
    
68.     vector_t *vector = malloc(sizeof(*vector));
    
69.     vector->data = NULL;
    
70.     vector->size = 0;
    
71.     return vector;
    
72. }
    
73. 
    
74. void vector_deinit(vector_t *vector) {
    
75.     free(vector->data);
    
76.     free(vector);
    
77. }
    
78. 
    
79. size_t vector_size(const vector_t *vector) {
    
80.     return vector->size;
    
81. }
    
82. 
    
83. size_t vector_empty(const vector_t *vector) {
    
84.     return vector_size(vector) == 0;
    
85. }
    
86. 
    
87. void vector_set(vector_t *vector, size_t index, vector_elem_t e) {
    
88.     if(index >= vector->size)
    
89.         vector->data = realloc(vector->data, sizeof(vector_elem_t) * (vector->size = index + 1));
    
90.     vector->data[index] = e;
    
91. }
    
92. 
    
93. vector_elem_t vector_get(const vector_t *vector, size_t index) {
    
94.     if(index >= vector->size) abort();
    
95.     return vector->data[index];
    
96. }
    
97. 
    
98. void vector_append(vector_t *vector, vector_elem_t e) {
    
99.     vector_set(vector, vector_size(vector), e);
    
100. }
     
101. 
     
102. bool vector_find(const vector_t *vector, vector_elem_t e) {
     
103.     for(size_t i = 0; i < vector_size(vector); ++i) {
     
104.         if(vector_get(vector, i) == e) return true;
     
105.     }
     
106.     return false;
     
107. }
     
108. 
     
109. tree_t *tree_init(FILE *fp) {
     
110.     tree_elem_t value;
     
111.     fscanf(fp, "%zu", &value);
     
112.     if(value == -1) return NULL;
     
113.     tree_t *root = malloc(sizeof(*root));
     
114.     root->e = value;
     
115.     root->lchild = tree_init(fp);
     
116.     root->rchild = tree_init(fp);
     
117.     return root;
     
118. }
     
119. 
     
120. void tree_deinit(tree_t *tree) {
     
121.     if(!tree) return;
     
122.     tree_deinit(tree->lchild);
     
123.     tree_deinit(tree->rchild);
     
124.     free(tree);
     
125. }
     
126. 
     
127. void tree_traversal_recursion_preorder(const tree_t *tree) {
     
128.     if(!tree) return;
     
129.     printf("%zu\n", tree->e);
     
130.     tree_traversal_recursion_preorder(tree->lchild);
     
131.     tree_traversal_recursion_preorder(tree->rchild);
     
132. }
     
133. 
     
134. void tree_traversal_iteration_preorder(const tree_t *tree) {
     
135.     stack_t *stack = stack_init();
     
136.     vector_t *vector = vector_init();
     
137.     stack_elem_t se = {tree, 0};
     
138.     stack_push(stack, se);
     
139.     while(!stack_empty(stack)) {
     
140.         se = stack_top(stack);
     
141.         if(!vector_find(vector, se.tree)) {
     
142.             vector_append(vector, se.tree);
     
143.             printf("%zu\n", se.tree->e);
     
144.             if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
     
145.             if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
     
146.         } else stack_pop(stack);
     
147.     }
     
148.     vector_deinit(vector);
     
149.     stack_deinit(stack);
     
150. }
     
151. 
     
152. void tree_traversal_recursion_inorder(const tree_t *tree) {
     
153.     if(!tree) return;
     
154.     tree_traversal_recursion_inorder(tree->lchild);
     
155.     printf("%zu\n", tree->e);
     
156.     tree_traversal_recursion_inorder(tree->rchild);
     
157. }
     
158. 
     
159. void tree_traversal_iteration_inorder(const tree_t *tree) {
     
160.     stack_t *stack = stack_init();
     
161.     vector_t *vector = vector_init();
     
162.     stack_elem_t se = {tree, 0};
     
163.     stack_push(stack, se);
     
164.     while(!stack_empty(stack)) {
     
165.         se = stack_top(stack);
     
166.         if(!vector_find(vector, se.tree)) {
     
167.             vector_append(vector, se.tree);
     
168.             if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
     
169.         } else {
     
170.             if(se.status == 0) {
     
171.                 printf("%zu\n", se.tree->e);
     
172.                 stack_pop(stack);
     
173.                 stack_push(stack, (stack_elem_t){se.tree, 1});
     
174.                 if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
     
175.             } else stack_pop(stack);
     
176.         }
     
177.     }
     
178.     vector_deinit(vector);
     
179.     stack_deinit(stack);
     
180. }
     
181. 
     
182. void tree_traversal_recursion_postorder(const tree_t *tree) {
     
183.     if(!tree) return;
     
184.     tree_traversal_recursion_postorder(tree->lchild);
     
185.     tree_traversal_recursion_postorder(tree->rchild);
     
186.     printf("%zu\n", tree->e);
     
187. }
     
188. 
     
189. void tree_traversal_iteration_postorder(const tree_t *tree) {
     
190.     stack_t *stack = stack_init();
     
191.     vector_t *vector = vector_init();
     
192.     stack_elem_t se = {tree, 0};
     
193.     stack_push(stack, se);
     
194.     while(!stack_empty(stack)) {
     
195.         se = stack_top(stack);
     
196.         if(!vector_find(vector, se.tree)) {
     
197.             vector_append(vector, se.tree);
     
198.             if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
     
199.             if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
     
200.         } else {
     
201.             printf("%zu\n", se.tree->e);
     
202.             stack_pop(stack);
     
203.         }
     
204.     }
     
205.     vector_deinit(vector);
     
206.     stack_deinit(stack);
     
207. }
     
208. 
     
209. int main(void) {
     
210.     tree_t *tree = tree_init(stdin);
     
211.     tree_traversal_recursion_postorder(tree);
     
212.     printf("\n");
     
213.     tree_traversal_iteration_postorder(tree);
     
214.     printf("\n");
     
215.     tree_traversal_recursion_inorder(tree);
     
216.     printf("\n");
     
217.     tree_traversal_iteration_inorder(tree);
     
218.     printf("\n");
     
219.     tree_traversal_recursion_preorder(tree);
     
220.     printf("\n");
     
221.     tree_traversal_iteration_preorder(tree);
     
222.     tree_deinit(tree);
     
223.     return 0;
     
224. }
     

复制代码

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. #include <string.h>
   
5. 
   
6. typedef size_t tree_elem_t;
   
7. 
   
8. typedef struct tree_node_tag {
   
9.     struct tree_node_tag *lchild, *rchild;
   
10.     tree_elem_t e;
    
11. } tree_t;
    
12. 
    
13. 
    
14. typedef struct {
    
15.     const tree_t *tree;
    
16.     size_t status;
    
17. } stack_elem_t;
    
18. 
    
19. typedef struct {
    
20.     stack_elem_t *data;
    
21.     size_t size, top;
    
22. } stack_t;
    
23. 
    
24. stack_t *stack_init(void) {
    
25.     stack_t *stack = malloc(sizeof(*stack));
    
26.     stack->data = NULL;
    
27.     stack->size = stack->top = 0;
    
28.     return stack;
    
29. }
    
30. 
    
31. void stack_deinit(stack_t *stack) {
    
32.     free(stack->data);
    
33.     free(stack);
    
34. }
    
35. 
    
36. size_t stack_size(const stack_t *stack) {
    
37.     return stack->top;
    
38. }
    
39. 
    
40. bool stack_empty(const stack_t *stack) {
    
41.     return stack_size(stack) == 0;
    
42. }
    
43. 
    
44. void stack_push(stack_t *stack, stack_elem_t e) {
    
45.     if(stack->top == stack->size)
    
46.         stack->data = realloc(stack->data, sizeof(stack_elem_t) * (stack->size += 10));
    
47.     stack->data[stack->top++] = e;
    
48. }
    
49. 
    
50. void stack_pop(stack_t *stack) {
    
51.     if(stack_empty(stack)) return;
    
52.     --stack->top;
    
53. }
    
54. 
    
55. stack_elem_t stack_top(const stack_t *stack) {
    
56.     if(stack_empty(stack)) abort();
    
57.     return stack->data[stack->top - 1];
    
58. }
    
59. 
    
60. tree_t *tree_init(FILE *fp) {
    
61.     tree_elem_t value;
    
62.     fscanf(fp, "%zu", &value);
    
63.     if(value == -1) return NULL;
    
64.     tree_t *root = malloc(sizeof(*root));
    
65.     root->e = value;
    
66.     root->lchild = tree_init(fp);
    
67.     root->rchild = tree_init(fp);
    
68.     return root;
    
69. }
    
70. 
    
71. void tree_deinit(tree_t *tree) {
    
72.     if(!tree) return;
    
73.     tree_deinit(tree->lchild);
    
74.     tree_deinit(tree->rchild);
    
75.     free(tree);
    
76. }
    
77. 
    
78. void tree_traversal_recursion_preorder(const tree_t *tree) {
    
79.     if(!tree) return;
    
80.     printf("%zu\n", tree->e);
    
81.     tree_traversal_recursion_preorder(tree->lchild);
    
82.     tree_traversal_recursion_preorder(tree->rchild);
    
83. }
    
84. 
    
85. void tree_traversal_iteration_preorder(const tree_t *tree) {
    
86.     stack_t *stack = stack_init();
    
87.     stack_elem_t se = {tree, 0};
    
88.     stack_push(stack, se);
    
89.     while(!stack_empty(stack)) {
    
90.         se = stack_top(stack);
    
91.         switch(se.status) {
    
92.             case 0:
    
93.                 printf("%zu\n", se.tree->e);
    
94.                 stack_pop(stack);
    
95.                 stack_push(stack, (stack_elem_t){se.tree, 1});
    
96.                 if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
    
97.                 if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
    
98.                 break;
    
99.             case 1:
    
100.                 stack_pop(stack);
     
101.         }
     
102.     }
     
103.     stack_deinit(stack);
     
104. }
     
105. 
     
106. void tree_traversal_recursion_inorder(const tree_t *tree) {
     
107.     if(!tree) return;
     
108.     tree_traversal_recursion_inorder(tree->lchild);
     
109.     printf("%zu\n", tree->e);
     
110.     tree_traversal_recursion_inorder(tree->rchild);
     
111. }
     
112. 
     
113. void tree_traversal_iteration_inorder(const tree_t *tree) {
     
114.     stack_t *stack = stack_init();
     
115.     stack_elem_t se = {tree, 0};
     
116.     stack_push(stack, se);
     
117.     while(!stack_empty(stack)) {
     
118.         se = stack_top(stack);
     
119.         switch(se.status) {
     
120.             case 0:
     
121.                 stack_pop(stack);
     
122.                 stack_push(stack, (stack_elem_t){se.tree, 1});
     
123.                 if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
     
124.                 break;
     
125.             case 1:
     
126.                 printf("%zu\n", se.tree->e);
     
127.                 stack_pop(stack);
     
128.                 stack_push(stack, (stack_elem_t){se.tree, 2});
     
129.                 if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
     
130.                 break;
     
131.             case 2:
     
132.                 stack_pop(stack);
     
133.         }
     
134.     }
     
135.     stack_deinit(stack);
     
136. }
     
137. 
     
138. void tree_traversal_recursion_postorder(const tree_t *tree) {
     
139.     if(!tree) return;
     
140.     tree_traversal_recursion_postorder(tree->lchild);
     
141.     tree_traversal_recursion_postorder(tree->rchild);
     
142.     printf("%zu\n", tree->e);
     
143. }
     
144. 
     
145. void tree_traversal_iteration_postorder(const tree_t *tree) {
     
146.     stack_t *stack = stack_init();
     
147.     stack_elem_t se = {tree, 0};
     
148.     stack_push(stack, se);
     
149.     while(!stack_empty(stack)) {
     
150.         se = stack_top(stack);
     
151.         switch(se.status) {
     
152.             case 0:
     
153.                 stack_pop(stack);
     
154.                 stack_push(stack, (stack_elem_t){se.tree, 1});
     
155.                 if(se.tree->rchild) stack_push(stack, (stack_elem_t){se.tree->rchild, 0});
     
156.                 if(se.tree->lchild) stack_push(stack, (stack_elem_t){se.tree->lchild, 0});
     
157.                 break;
     
158.             case 1:
     
159.                 printf("%zu\n", se.tree->e);
     
160.                 stack_pop(stack);
     
161.         }
     
162.     }
     
163.     stack_deinit(stack);
     
164. }
     
165. 
     
166. int main(void) {
     
167.     tree_t *tree = tree_init(stdin);
     
168.     tree_traversal_recursion_postorder(tree);
     
169.     printf("\n");
     
170.     tree_traversal_iteration_postorder(tree);
     
171.     printf("\n");
     
172.     tree_traversal_recursion_inorder(tree);
     
173.     printf("\n");
     
174.     tree_traversal_iteration_inorder(tree);
     
175.     printf("\n");
     
176.     tree_traversal_recursion_preorder(tree);
     
177.     printf("\n");
     
178.     tree_traversal_iteration_preorder(tree);
     
179.     tree_deinit(tree);
     
180.     return 0;
     
181. }
     

复制代码

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语言的编译器

我试试吧