C 程序正在占用一个分支，即使它不应该

Question

我编写了一个C程序，该程序从数组中构造了二进制搜索树。它通过以下步骤：

1：用qsort()。

对数组进行排序

2：使用递归函数treeify()：

将数组的排序元素放在二进制树中

2a：以数组的中间元素(通过将其长度除以2(，并将其作为树结构的content字段(该子树的根节点(。

2b：然后函数将其余元素的左和右半复制为较小的数组，并分别为这些数组中的每个数组呼唤。

2c：通过根节点返回树。

3：递归穿越树并以缩进格式打印其内容。

基本上，我使用了一个分隔和诱饵范式从已经分类的数组中构建树。令人惊讶的是(因为这是我第一次设计D＆amp; c算法(这部分进行得很顺利。

我真正遇到麻烦的地方是在步骤3中。有时它有效，而当它做到时，所有元素的顺序都正确，因此该部分显然有效。但是我运行该程序的90％的次

这是完整的程序文本。我已经更改了打印功能，以便打印节点的地址(用于调试目的(。最初显示数字值...

#include <stdio.h>
#include <stdlib.h>
struct tree {
    int content;
    struct tree *left;
    struct tree *right;
};
struct tree *treeify( int *, size_t );
void printtree( struct tree *, int );
int comp( int *, int * );
int main( int argc, char **argv ){
    int array[] = { 5, 6, 7, 2, 3, 4, 9, 1, 8, 0 };
    /* Sort array */
    qsort( (void *) array, 10, sizeof( int ), (int (*)(const void *, const void *)) &comp );
    for( int i = 0; i < 10; i++ ){
        printf( "%d ", array[i] );
    }
    printf( "n" );
    /* Treeify array */
    struct tree *rootnode = treeify( array, 10 );
    /* Print tree */
    printtree( rootnode, 0 );
    return 0;
}
// Place sorted array elements in a tree
// Function is called for each subtree
struct tree *treeify( int *array, size_t size ){
    struct tree *root = (struct tree *) malloc( sizeof( struct tree ) );
    size_t middle = size/2;
    int leftsize = middle, rightsize = size-middle-1;
    int left[leftsize], right[rightsize];
    for( int i = 0; i < leftsize; i++ ) left[i] = array[i];
    for( int i = 0; i < rightsize; i++ ) right[i] = array[i+middle+1];
    root->content = array[middle];
    if( leftsize > 0 ) root->left = treeify( left, leftsize );
    if( rightsize > 0 ) root->right = treeify( right, rightsize );
    return root;
}
// Print tree contents in indented format
void printtree( struct tree *node, int level ){
    for( int i = 0; i < level; i++ ) printf( "  " );
    printf( "%xn", &(node->content) );
    if( node->left ) printtree( node->left, level+1 );
    if( node->right ) printtree( node->right, level+1 );
}
// Comparison function for qsort
int comp( int *xp, int *yp ){
    int x = *xp, y = *yp;
    if( x < y ) return -1;
    if( x > y ) return 1;
    return 0;
}

我通过在穿过树时打印节点的地址来隔离问题。这是成功运行的输出：

0 1 2 3 4 5 6 7 8 9 
cbe00000
  cbe00020
    cbe00040
      cbe00060
    cbe00080
      cbe000a0
  cbe000c0
    cbe000e0
      cbe00100
    cbe00120

和不成功的运行：

f04032b0
  f04032d0
    f04032f0
      f0403310
        0   
Segmentation fault: 11

请注意，成功的运行仅在返回并返回之前仅经过三个级别。失败的运行经历了四个级别，达到了无效指针。

特别是，当程序到达此行时：

        if( node->left ) printtree( node->left, level+1 );

尽管node->left评估为零，但仍将分支占用(如输出的第五行所示(。

这是我一生所理解的我所无法理解的。该条件明确评估为false(我已经证实了这一点(，但是该程序仍在将该分支视为true(并且在大多数，不是全部，案例(中。

。

这实际上从来没有发生过。我需要一个比我对C更了解C的人。

我唯一能想到的可能性：

• 一些古怪的编译器优化

• 我在某处犯了一个愚蠢的单个字符错误

• 我的CPU部分油炸

Answer 1

问题是您尝试从结构的一个无关紧要的成员中读取，第一次发生的是这里

if (node->left) 

在printtree()功能中。

非初始化的价值观被保存下来并试图阅读它们是不确定的行为，因此这就是为什么您的程序并不总是相同的行为。

您需要初始化两个成员，实际上最好拥有

struct tree *create_node(int content)
{
    struct tree *node;
    node = malloc(sizeof(*node));
    if (node == NULL)
        return NULL;
    node->content = content;
    node->left = NULL;
    node->right = NULL;
    return node;
}

您也应该，

1. 由于此处讨论的内容，请避免施放malloc()或任何返回void *的功能。
2. 检查malloc()在使用指针之前是否返回NULL。

Answer 2

启动器的功能comp应像

一样声明

int comp( const void *, const void * );

在函数treeify中，数据成员right的数据成员left要么在leftsize或rightsize等于0时具有不确定的值。

可以在不使用辅助数组的情况下更简单地实现该函数。

struct tree * treeify( const int *array, size_t size )
{
    struct tree *node = NULL;
    if ( size )
    {
        node = malloc( sizeof( struct tree ) );
        size_t middle = size / 2;
        node->content = array[middle];
        node->left = treeify( array, middle );
        node->right = treeify( array + middle + 1, size - middle - 1 );
    }
    return node;
}

功能printtree(是错误的。例如，它不检查第一个参数是否等于NULL。

这是一个指示的程序

#include <stdio.h>
#include <stdlib.h>
struct tree 
{
    int content;
    struct tree *left;
    struct tree *right;
};
int comp( const void *, const void * );
struct tree * treeify( const int *, size_t );
void printtree( const struct tree *, int level );
int main(void) 
{
    int array[] = { 5, 6, 7, 2, 3, 4, 9, 1, 8, 0 };
    const size_t N = sizeof( array ) / sizeof( *array );
    qsort( array, N, sizeof( *array ), comp );
    for ( size_t i = 0; i < N; i++ ) printf( "%d ", array[i] );
    putchar( 'n' );
    struct tree *rootnode = treeify( array, N );
    printtree( rootnode, 0 );
    return 0;
}
int comp( const void *left, const void *right )
{
    int x = *( const int * )left;
    int y = *( const int * )right;
    return ( y < x ) - ( x < y );
}
struct tree * treeify( const int *array, size_t size )
{
    struct tree *node = NULL;
    if ( size )
    {
        node = malloc( sizeof( struct tree ) );
        size_t middle = size / 2;
        node->content = array[middle];
        node->left = treeify( array, middle );
        node->right = treeify( array + middle + 1, size - middle - 1 );
    }
    return node;
}
void printtree( const struct tree *node, int level )
{
    if ( node )
    {
        printf( "%*s", level, "" );
        printf( "%dn", node->content );
        if( node->left ) printtree( node->left, level + 1 );
        if( node->right ) printtree( node->right, level + 1 );
    }
}

其输出是

0 1 2 3 4 5 6 7 8 9 
5
 2
  1
   0
  4
   3
 8
  7
   6
  9