在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 % 2是负面的，-1的结果是n。然后，当您使用isOdd而不是负数时，每个负奇数将从总计数中减去一。

至少有3种可能的修复方法：

• 使用& 1（假定2的补码）
• 使用!!将其反转为布尔值，然后再次反转（将强制它为0或1）
• 计算绝对值的模​​数：abs(n) % 2。这适用于超过2的模数。如果系统使用2的补码且值等于INT_MIN（感谢@ user694733），则不起作用。
• 计算余数的abs：abs(n % 2)，甚至应该在INT_MIN情况下工作。

---

(-1) % 2生产-1的原因在于C11 6.5.5p6：

6. 当整数被划分时，/算子的结果是代数商，丢弃任何小数部分。如果商a/b是可表示的，则表达式(a/b)*b + a%b应等于a;否则，a/b和a%b的行为都是不确定的。

现在，给定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。