我有以下实现来镜像二叉树。
#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?还有我们为什么要铸造(结构节点*)?
首先,在 C 中使用 malloc 时不需要强制转换。(看这里)
您正在错误定位,因为您正在分配节点结构大小的堆内存。你看到在C中,你必须记住所有变量的存储位置。即stack
和heap
(见这里)
在函数中,您的变量称为局部变量,它存储在 stack
中。离开函数后,堆栈中的变量将被清除。
为了能够在函数之外引用或使用局部变量,您必须在heap
中分配内存,这就是您在这里所做的。您在堆中分配内存,以便也可以在其他函数中重用相同的变量。
总结:
- 函数
- 中的变量是函数的局部变量,因此称为局部变量
- 要使其他函数访问局部变量,您必须在堆中分配内存以与其他函数共享该变量。
为了给您一个示例,请考虑以下代码:
#include <stdio.h>
#include <string.h>
char *some_string_func()
{
char some_str[13]; /* 12 chars (for "Hello World!") + 1 null ' ' char */
strcpy(some_str, "Hello World!");
return some_str;
}
int main()
{
printf("%sn", some_string_func());
return 0;
}
它非常简单,main
只是调用一个返回局部变量some_str
的函数some_str_func
,编译上面的代码就可以了,但并非没有警告:
test.c: In function ‘some_string_func’:
test.c:11:9: warning: function returns address of local variable [enabled by default]
虽然它编译注意some_str
some_str_func()
正在向函数返回一个局部变量(即在函数的堆栈中)。由于一旦你离开函数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 ' ' char */
some_str = calloc(13, sizeof(char));
strcpy(some_str, "Hello World!");
return some_str;
}
int main()
{
char *str = some_string_func();
printf("%sn", str);
free(str); /* remember to free the allocated memory */
return 0;
}
现在,当您编译并运行它时,您将获得:
$ gcc test.c
$ ./a.out
Hello World!
$
如果你很难理解C,我知道很多人发现Brian W. Kernighan和Dennis Ritchie的"C编程语言"是一个很好的参考,但是一本更现代和图形化(甚至读起来很有趣!认真)的书是David 和 Dawn Griffiths 的 Head First C,他们解释了许多重要的 C 概念,如堆和堆栈, 动态和静态 C 库之间的区别,为什么使用 Makefiles 是一个好主意,Make 如何工作,以及以前在普通 C 书籍中没有解释的更多概念,绝对值得一看。
另一个很好的在线资源是Zed Shaws Learn C the Hard way,他在其中提供了很好的代码示例和注释。
阅读:void *malloc(size_t size);
malloc()
函数分配size
个字节并返回指向 分配的内存。 内存未初始化。 如果大小为 0, 然后malloc()
返回NULL
或唯一指针值,该值可以 后来成功传递给free()
.
因此,在
struct node* node = (struct node*)malloc(sizeof(struct node));
// ^----size---------^
您正在分配 size = sizeof naode
字节的内存块,并从存储在指针node
malloc 返回地址。
注意 您有错误变量名称不应node
,因为它是结构名称。您可以!但这不是好的做法。此外,sizeof(*pointer)
优先于sizeof(Type)
,以防类型发生变化
旁注:避免不通过 malloc 和 calloc 函数转换返回地址是安全的。 阅读:我是否投射 malloc 的结果?
因此
struct node* nd = malloc(sizeof *nd);
// ^----size-^
两个更正:(1) 删除类型转换和 (2) 将变量名称更改为 nd
。
使用 sizeof
-
sizeof
(T) 将告知存储 T 类型变量所需的字节数
使用 malloc
-
Malloc 动态分配内存,即在运行时(当程序实际由 CPU 及其在内存中执行时)。当我们不确定运行时所需的内存量时,我们主要使用它。所以我们在运行时使用 malloc
动态分配它。
使用 ( struct node*
)-
Malloc
返回一个指向内存块的指针,其中包含您请求的空间量(在其参数中)。这个空间只是内存中的一些空间。因此,此指针没有与之关联的类型。我们把这个指针投射到(struct node*
),因为它会让机器知道(struct node
)类型的变量将被保存在这个内存中。
void* malloc (size_t size);
分配内存块
分配大小字节的内存块,返回指向 块的开头。新分配的块的内容 内存未初始化,保留不确定的值。如果 大小为零,返回值取决于特定的库 实现(它可能是也可能不是空指针),但返回的 指针不得取消引用。
并且不要投射malloc
的结果.
您还需要释放此内存:
void free (void* ptr);
释放内存块
以前通过调用 malloc、calloc 或 Realloc 已解除分配,使其再次可用于进一步 分配。
你使用 malloc 通常让指针有指向的东西。
指针就像一个街道地址,站在地址上的建筑物是由Malloc建造的 - 或者至少是建造建筑物所需的大小 - 你在那里建造什么取决于你。
在您的示例中,树中的每个节点都是使用 malloc 分配的字节数,节点的大小是保存节点所有内容所需的字节数。
二叉树将使其每个节点都使用 malloc 分配,其中内存中无关紧要,这可能是使用 malloc 和指针理解有点棘手的事情。 只要有指向这些位置的指针,一切都很好。
struct node* node = (struct node*)malloc(sizeof(struct node));
分配足够的空间来容纳node
结构