c - 在C中查找BST中奇数/偶数/负数的数量

Question

我正在编写一个函数，用于查找 BST 中奇数/偶数/负数的数量。您传入一棵树和一个指向函数的指针。

int countIf (treelink tree, int (*pred)(TreeItem)) {
    if ( tree == NULL ) return 0;
    return (*pred)(tree->item) + countIf(tree->left,pred) + countIf(tree->right,pred);
}

函数指针 pred 可以是这样的:

int isEven (TreeItem n) {
return !(n%2);
}

int isOdd (TreeItem n) {
    return n%2;
}

int isNegative (TreeItem n) {
    return (n < 0);
}

为什么 countIF 的代码不起作用？它只适用于某些情况，而不是全部。 谢谢

它正在处理这组数字:7 5 11 3 6 9 15 1 4 8 10 14 16 但不是这样的:7 -5 11 -9 3 10 15 1 4 8 14 16 6

Answer 1

如果n 为负数，n % 2 的结果为-1。然后，当您对负数使用 isOdd 时，每个负奇数都会从总数中减去 1。

至少有 3 个可能的修复方法:

• 使用 & 1(假定 2 的补码)
• 使用 !! 将其反转为 bool 值，然后再次反转(将强制其变为 0 或 1)
• 计算绝对值的模​​数:abs(n) % 2。这适用于超过 2 的模。如果系统使用 2 的补码并且值等于 INT_MIN，则不起作用(感谢 @user694733)。
• 计算余数的 abs:abs(n % 2)，即使在 INT_MIN 情况下也应该有效。

<小时/>

(-1) % 2 产生 -1 的原因位于 C11 6.5.5p6 :

6. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.

现在，给定 a = -1 和 b = 2 截断意味着 (-1)/2 生成 - 0.5 并且使用小数截断，其效果与向零舍入相同，因此结果为0。现在，由于 ((-1)/2) * 2 + (-1) % 2 必须等于 -1；并且 (-1)/2 为 0，因此 ((-1)/2) * 2 为 0，则 0 + (-1) % 2 为 (-1) % 2，并且根据规则，其计算结果必须为 -1。