我有以下实现来镜像二叉树。
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
*/
void mirror(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);
/* Convert tree to its mirror */
mirror(root);
/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);
getchar();
return 0;
}
我说的是下面一行:
struct node* node = (struct node*)
malloc(sizeof(struct node));
我有c/c++的中级知识,但我很害怕指针。即使经过几次尝试,我也从未得到指点。我尽可能避免使用它们,但是在实现像树这样的数据结构时没有其他选择。为什么我们在这里使用 malloc 和 sizeof?另外,我们为什么要强制转换 (struct node*)?
最佳答案
首先,在 C 中使用 malloc 时不需要强制转换。 (参见 here)
你正在 malloc-ing 因为你正在分配节点结构大小的堆内存。你看到在 C 中你必须记住所有变量的存储位置。即 stack
和 heap
(参见 here)
在函数内部,您的变量称为局部变量,它存储在堆栈
中。一旦离开函数,堆栈中的变量就会被清除。
为了能够在函数外部引用或使用局部变量,您必须在堆
中分配内存,这就是您在这里所做的。您在堆中分配内存,以便您也可以在其他函数中重用相同的变量。
总结:
- 函数内的变量是函数的局部变量,因此称为局部变量
- 要让其他函数访问局部变量,您必须在堆中分配内存以与其他函数共享该变量。
为了举例说明原因,请考虑以下代码:
#include <stdio.h>
#include <string.h>
char *some_string_func()
{
char some_str[13]; /* 12 chars (for "Hello World!") + 1 null '\0' char */
strcpy(some_str, "Hello World!");
return some_str;
}
int main()
{
printf("%s\n", some_string_func());
return 0;
}
很简单,main
只是调用一个函数some_str_func
,它返回一个局部变量some_str
,编译上面的代码是可行的,但是并非没有警告:
test.c: In function ‘some_string_func’:
test.c:11:9: warning: function returns address of local variable [enabled by default]
尽管编译时注意 some_str_func()
中的 some_str
正在返回一个局部变量 给函数(即在函数的堆栈中)。由于一旦您离开函数 some_str_func()
就会清除堆栈,因此在 main()
中将不可能获取 some_str
即“Hello World”。
如果您尝试运行它,您会得到:
$ gcc test.c
$ ./a.out
$
它什么都不打印,因为它无法访问 some_str
。为了补救它,您改为为字符串“Hello World”分配一些内存空间。像这样:
#include <stdio.h>
#include <string.h>
char *some_string_func()
{
char *some_str;
/* allocate 12 chars (for "Hello World!") + 1 null '\0' char */
some_str = calloc(13, sizeof(char));
strcpy(some_str, "Hello World!");
return some_str;
}
int main()
{
char *str = some_string_func();
printf("%s\n", str);
free(str); /* remember to free the allocated memory */
return 0;
}
现在当你编译并运行它时,你会得到:
$ gcc test.c
$ ./a.out
Hello World!
$
如果您很难理解 C,我知道很多人会发现 Brian W. Kernighan 和 Dennis Ritchie 合着的“The C Programming Language”是一个非常好的引用书,但是更现代和图形化(甚至读起来很有趣!说真的) 书是 Head First C David 和 Dawn Griffiths 解释了许多重要的 C 概念,例如堆和堆栈、动态和静态 C 库之间的区别、为什么使用 Makefiles 是个好主意、Make 是如何工作的,以及许多以前没有解释过的概念普通的C书,绝对值得一看。
另一个很好的在线资源是 Zed Shaws Learn C the Hard way ,他在其中提供了很好的代码示例和注释。
关于c - 以下带有 malloc 的代码行是做什么的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18935943/