4

我有以下实现来镜像二叉树。

#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？另外我们为什么要强制转换（结构节点*）？

4

6 回答 6

7

首先，在 C 中使用 malloc 时不需要进行强制转换。（见这里）

您正在 malloc-ing，因为您正在分配节点结构大小的堆内存。您在 C 中看到，您必须记住所有变量的存储位置。即stackand heap（见这里）

在函数内部，您的变量称为局部变量，存储在stack. 一旦你离开函数，堆栈中的变量就会被清除。

为了能够在函数之外引用或使用局部变量，您必须在 中分配内存heap，这就是您在这里所做的。您在堆中分配内存，以便您也可以在其他函数中重用相同的变量。

总之：

  • 函数中的变量是函数的局部变量，因此术语局部变量
  • 要让其他函数访问局部变量，您必须在堆中分配内存以与其他函数共享该变量。

为了给你一个例子，请考虑以下代码：

#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_strinsome_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 '\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 库之间的区别、为什么使用 Makefile 是一个好主意、Make 是如何工作的，以及之前在常见的C类书籍，绝对值得一看。

另一个很好的在线资源是 Zed Shaws Learn C the Hard way，他在其中提供了很好的代码示例和注释。

于 2013-09-21T18:16:26.197 回答
3

读：void *malloc(size_t size);

该malloc()函数分配size字节并返回一个指向已分配内存的指针。内存未初始化。如果 size 为 0，则malloc()返回NULL或稍后可以成功传递给 的唯一指针值free()。

因此，在

struct node* node = (struct node*)malloc(sizeof(struct node));
  //                                     ^----size---------^

您正在分配内存块，并从存储在指针size = sizeof naode中的 malloc 返回地址。node

注意你有错误的变量名不应该node是结构名。你可以！但不是很好的做法。此外，如果类型发生更改，sizeof(*pointer)则优先于sizeof(Type)

旁注：避免不通过 malloc 和 calloc 函数转换返回地址是安全的。阅读：我要转换 malloc 的结果吗？

所以正确的上述陈述的优选形式是：

struct node* nd = malloc(sizeof *nd);
  //                     ^----size-^

两个更正：（1）删除类型转换和（2）将变量名更改为nd.

于 2013-09-21T18:19:37.473 回答
1

使用sizeof-

sizeof( T ) 将告诉存储类型T的变量所需的字节数

使用malloc-

Malloc 动态分配内存，即在运行时（当您的程序实际由 CPU 执行时，它在内存中）。当我们不确定运行时所需的内存量时，我们主要使用它。所以我们在运行时使用动态分配它malloc。

使用 ( struct node*)-

Malloc返回指向具有您要求的空间量的内存块的指针（在其参数中）。这个空间只是内存中的一些空间。因此，该指针没有与之关联的类型。我们将此指针转换为 ( struct node*)，因为它会让机器知道 ( struct node) 类型的变量将保存在此内存中。

于 2013-09-21T18:30:13.730 回答
0 
void* malloc (size_t size);

分配内存块

分配一块 size 字节的内存，返回一个指向块开头的指针。新分配的内存块的内容未初始化，剩余的值不确定。如果 size 为零，则返回值取决于特定的库实现（它可能是也可能不是空指针），但不应取消引用返回的指针。

并且不要投射malloc.

您还需要释放此内存：

void free (void* ptr);

释放内存块

先前通过调用 malloc、calloc 或 realloc 分配的内存块被释放，使其再次可用于进一步分配。

于 2013-09-21T18:18:13.833 回答
0

您使用 malloc 通常让指针有指向的东西。

指针就像街道地址，位于地址上的建筑物是由 malloc 建造的——或者至少是建造建筑物所需的大小——你在那里建造什么取决于你。

在您的示例中，树中的每个节点都是用 malloc 分配的字节数，节点的大小是保存节点所有内容所需的字节数。

二叉树将为其每个节点分配 malloc，其中在内存中无关紧要，这可能是使用 malloc 和指针难以理解的事情。只要有指向这些位置的指针，一切都很好。

于 2013-09-21T18:22:23.940 回答
0 
struct node* node = (struct node*)malloc(sizeof(struct node));

分配足够的空间来容纳一个node结构

于 2013-09-21T21:53:35.697 回答