c - 以下带有 malloc 的代码行是做什么的？

Question

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

#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*)？

Answer 1

首先，在 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 ，他在其中提供了很好的代码示例和注释。