0%

上机实验的一些事儿

上机实验的一些事儿

C语言中当指针作为函数的参数传递

在写二叉树的先序创建时遇到的一个问题,刚开始写的时候,总想着传指针到函数里,然后递归创建二叉树,但实际上只创建了根结点,其他节点都没有连上,导致后面的先序遍历一直抛出异常,其他的地方不大可能出错,一定是传参的问题,但是它看起来也挺正常啊,一时间笔者感到深深的迷惑

下面是错误的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct tree {                       // 创建结构体
int data; // 数据域
tree* lchild; // 左孩子结点 指针域
tree* rchild; // 右孩子结点 指针域
};
tree* root = NULL; // 全局定义树的根结点
void creat_tree(tree* p) { // 先序创建二叉树
int data;
scanf("%d",&data);
if(data == 0) p = NULL;
else {
p = (tree*)malloc(sizeof(tree));
if(root == NULL) root = p;
p->data = data;
creat_tree(p->lchild);
creat_tree(p->rchild);
}
}

这时,万能的哥们跟我讲,指针创建链式结构不要像下面这么写,这么写基本上是要出问题的

1
2
3
4
5
void creat_tree(tree* p){
/* 省略 */
creat_tree(p->lchild);
/* 省略 */
}

应该这么写

1
2
3
4
5
tree* creat_tree(){
/* 省略 */
p->lchild = creat_tree();
/* 省略 */
}

这样马上就看出了区别,在前一种写法中,实参即传进函数的指针 p->lchild 原来指向一个 地址1,于是进入函数后,形参,也就是指针 p ,也只是指向 地址1 罢了,对此时的指针 p 的赋值操作 p->data = data; 根本与之前的 p->lchild 无关,更不用说此时的 p->lchild 了,这样子写来创建二叉树根本是无效的,应当采用函数返回值的方式

于是将上述错误代码修改并补全成以下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* 先序创建二叉树 */
#include<stdio.h>
#include<stdlib.h>

struct tree { // 创建结构体
int data; // 数据域
tree* lchild; // 左孩子结点 指针域
tree* rchild; // 右孩子结点 指针域
};
tree* root = NULL; // 全局定义树的根结点
tree* creat_tree() { // 先序创建二叉树
int data;
tree* p;
scanf("%d",&data);
if(data == 0) p = NULL;
else {
p = (tree*)malloc(sizeof(tree));
if(root == NULL) root = p;
p->data = data;
p->lchild = creat_tree();
p->rchild = creat_tree();
}
return p;
}

void Pre_Order_Traverse(tree* p) {
if (p != NULL) {
printf("%d\t", p->data);
Pre_Order_Traverse(p->lchild);
Pre_Order_Traverse(p->rchild);
}
}

int main()
{
creat_tree();
Pre_Order_Traverse(root);
return 0;
}

测试样例:

先序创建二叉树后先序遍历输出
15 98 20 30 0 0 40 0 0 10 0 0 6 45 0 60 70 0 0 0 0

avatar

测试结果:

avatar

层次遍历的优化

C语言中没有队列,不能使用常规的 BFS(广度优先搜索)来进行层次遍历,于是想到了运用二叉树的一个性质:即,若当前结点为编号为 $i$ ,则其 lchild 结点的编号应为 $2i$ ,其 rchild 结点的编号应为 $2i+1$,那么就可以先建立一个足够大的数组 Tree ,先将其全部初始化为 $0$ ,在先序创建二叉树的时候以 Tree[结点编号] = 结点的数值 的方式更新数组,相当于将这颗树按编号顺序存储到Tree数组里,最后依序输出数组的非零值即可完成二叉树的层次遍历。

avatar

实现的部分代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxn = 10000 + 5;

typedef struct BiTNode {
int data;
BiTNode* lchild, * rchild;
};

int Tree[maxn]; // 全局定义一个数组存储结点,以便层次遍历
int index; // 全局定义Tree数组的索引
int index_max;

BiTNode* Create_BiTree() {
/* 省略 */
Node->data = data;
Tree[index] = data;
index *= 2; if (index > index_max) index_max = index;
Node->lchild = Create_BiTree();
index++; if (index > index_max) index_max = index;
Node->rchild = Create_BiTree();
index = (index - 1) / 2;
/* 省略 */
return Node;
}

void Level_Traversal() {
printf("Level Traversal:\n");
for (int i = 1; i <= index_max; i++)
if (Tree[i] != 0)printf("%d\t", Tree[i]);
printf("\n");
}

这样虽然完成了层次遍历,但是一旦结点个数多起来,就需要一个巨大的数组来存储,并且如果树还比较稀疏,浪费的空间占所有存储的空间的比例就会很高,这显然不是一个好的算法。

这时,万能的哥们又及时提供了帮助:

1
2
3
4
5
6
7
8
9
10
11
12
13
void level(BiTNode* p, int lev)
{
if (lev < 1 || p == NULL) return;
if (p != NULL && lev == 1) printf("%d\t", p->data);
level(p->lchild, lev - 1);
level(p->rchild, lev - 1);
}

void _Level_Fraversal(BiTNode* p) {
printf("Level Traversal:\n");
for (int i = 1; i <= DeepMax; i++) level(p, i);
printf("\n");
}

完美地去掉了数组


二叉树程序设计完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/***** 二叉树及其遍历的C语言实现 *****/
/***** 实验二 二叉树程序设计 *****/
/*
一、实验目的及要求
1.掌握二叉树的定义及其链式存储结构。
2.掌握二叉树的先序遍历、中序遍历和后序遍历,并将结果序列输出。
二、实验内容
1. 先序创建二叉树。
2. 计算树的层次、先序、中序和后序遍历。
3. 并输出叶子结点个数以及二叉树的高度。
三、实验步骤和要求
以下图所示的二叉树为例编制程序,实现实验内容中所述功能。
Undirected
Node Count:
10
Graph Data:
15
98
6
20
10
45
30
40
60
70
15 98
15 6
6 45
45 60
60 70
98 20
98 10
20 30
20 40
四、实验结果分析
对实验结果进行检验,如结果出现错误,分析产生错误的原因并修改程序、改正错误。
*/

const int maxn = 10000 + 5;

typedef struct BiTNode { // 二叉树的二叉链表存储
int data;
BiTNode* lchild, * rchild; // 左右孩子指针
};

BiTNode* BT = NULL; // 全局定义树的根结点
int LeafNodecnt = 0; // 全局定义树的叶子结点数
int Deep = 0; // 全局定义当前深度
int DeepMax = 0; // 全局定义二叉树深度
int Tree[maxn]; // 全局定义一个数组存储结点,以便层次遍历
int index; // 全局定义Tree数组的索引
int index_max;
FILE* fin = fopen("In.txt", "r+");

BiTNode* Create_BiTree() {
int data;
BiTNode* Node;
fscanf(fin,"%d", &data);
//scanf("%d",&data);
if (data == 0) Node = NULL;
else {
if (!(Node = (BiTNode*)malloc(sizeof(BiTNode)))) {
printf("ERROR!");
exit(0);
}
if (BT == NULL) {
BT = Node;
}
Node->data = data;
Tree[index] = data;
Deep++;
if (Deep > DeepMax) DeepMax = Deep;
index *= 2; if (index > index_max) index_max = index;
Node->lchild = Create_BiTree();
index++; if (index > index_max) index_max = index;
Node->rchild = Create_BiTree();
index = (index - 1) / 2;
Deep--;
}
return Node;
}

void Pre_Order_Traverse(BiTNode* p) {
if (p != NULL) {
printf("%d\t", p->data);
Pre_Order_Traverse(p->lchild);
Pre_Order_Traverse(p->rchild);
}
}

void In_Order_Traverse(BiTNode* p) {
if (p != NULL) {
In_Order_Traverse(p->lchild);
printf("%d\t", p->data);
In_Order_Traverse(p->rchild);
}
}

void Post_Order_Traverse(BiTNode* p) {
if (p != NULL) {
Post_Order_Traverse(p->lchild);
Post_Order_Traverse(p->rchild);
printf("%d\t", p->data);
}
}

void Level_Traversal() {
printf("Level Traversal:\n");
for (int i = 1; i <= index_max; i++)
if (Tree[i] != 0)printf("%d\t", Tree[i]);
printf("\n");
}

void level(BiTNode* p, int lev)
{
if (lev < 1 || p == NULL) return;
if (p != NULL && lev == 1) printf("%d\t", p->data);
level(p->lchild, lev - 1);
level(p->rchild, lev - 1);
}

void _Level_Fraversal(BiTNode* p) {
printf("Level Traversal:\n");
for (int i = 1; i <= DeepMax; i++) level(p, i);
printf("\n");
}

void pretrav_fln(BiTNode* p) {
if (p != NULL) {
if (p->lchild == NULL && p->rchild == NULL) LeafNodecnt++;
pretrav_fln(p->lchild);
pretrav_fln(p->rchild);
}
return;
}

void Find_leaf_node() {
BiTNode* p = BT;
printf("Leaf Node:");
pretrav_fln(p);
printf("%d\n", LeafNodecnt);
return;
}

void Count_Deepth() {
printf("Deepth:%d\n", DeepMax);
}

int main() {
index = 1;
memset(Tree, 0, sizeof(Tree));
Create_BiTree(); // 先序创建二叉树

printf("Pre-Order:\n"); // 先序遍历
Pre_Order_Traverse(BT);
printf("\n");

printf("In-Order:\n"); // 中序遍历
In_Order_Traverse(BT);
printf("\n");

printf("Post-Order:\n"); // 后序遍历
Post_Order_Traverse(BT);
printf("\n");

Level_Traversal(); // 层次遍历 法1

_Level_Fraversal(BT); // 层次遍历 法2

Find_leaf_node(); // 叶子结点个数

Count_Deepth(); // 二叉树高度

return 0;
}