swap函数陷进

int32位 posted @ Oct 25, 2014 09:53:54 PM in c/cpp , 1133 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

使用c语言写一个函数实现两个数交换,很简单写下以下代码:

void swap(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

只有三行代码,且没有引入中间变量,使用位运算,效率高!

但首先必须保证a, b 不是空指针,否则就会出现段错误。

于是代码进一步改成:

void swap(int *a, int *b)
{
    if (a == NULL || b == NULL)
        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

似乎这样就完美了?

咋一看,真没有什么问题了,不信你可以测试,无论正数,负数,还是0,基本都不会出错了。。

那么请看以下代码:

static int count = 0;
void permutation(int *a, int from, int to)
{
    if (from == to) {
        cout << ++count << ":";
        for (int i = 0; i <= to; ++i)
            cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = from; i <= to; ++i) {
        swap(&a[from], &a[i]);
        permutation(a, from + 1, to);
        swap(&a[from], &a[i]);
    }
}

以上代码是求一个数组全排列的递归方法,算法应该没有错?

可是输出大量0!!为什么呢???

答案在下面:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

原因在于当swap(int *a, int *b)传的是同一个地址时,就会等于0

即若 a == b

*a ^= *b,此时 *a == 0, *b == 0

最后必然是 *a == 0, *b == 0,

 for (int i = from; i <= to; ++i) {
        swap(&a[from], &a[i]);
        permutation(a, from + 1, to);
        swap(&a[from], &a[i]);
    }

上面代码没有考虑当from == i的情况,即传递的是同一个地址。

所以正确的swap函数,应该是:

void swap(int* a, int* b)
{
    if (a == NULL || b == NULL || a == b)
        return;
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter