即使它不应该,C程序正在进行分支

Question

我编写了一个C程序,用于从数组构造二进制搜索树.它通过以下步骤:

1:使用排序数组qsort().

2:使用递归函数将数组的已排序元素放入二叉树中treeify():

2a:获取数组的中间元素(通过将其长度除以2)并将其作为content树结构的字段(此子树的根节点)放置.

2b:函数然后将剩余元素的左半部分和右半部分复制到较小的数组中,并分别为这些数组中的每一个调用自身.

2c:通过根节点返回树.

3:递归遍历树并以缩进格式打印其内容.

基本上,我使用了一个分而治之的范例来从已经排序的数组构建树.令人惊讶的是(因为这是我第一次设计D&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( "%x\n", &(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评估为零(如输出的第五行所示),它仍然需要分支.

这是我无法理解的生活.条件显然是评估为假(我已经验证过),然而程序仍然将该分支视为评估为真(并且仅在大多数情况下,而不是所有情况下).

这在我之前从未发生过.我需要一个对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.