两个数交换算法(不需要临时变量)
两个数交换算法(不需要临时变量)2011-03-24 12:17转载自 zhfdai最终编辑 zhfdai 两个数交换算法(包含不用第3个变量而直接交换的情况)2006-12-17 20:07对两个数进行交换，在C中可采用指针实现，而在C++可使用引用来实现，无论是用指针还是引用，都要借助第3个变量。本文将介绍两种直接交换的算法
******************************* 后附有完整算法和测试程序
方法一:
采用整数的加(减)法实现，属于算术运算
void SwapWithAri( int & lhs, int & rhs ) {
lhs += rhs ; // lhs = lhs + rhs; 结果 lhs 保存两者之和
rhs -= lhs ; // rhs = rhs - lhs; 结果 rhs == -lhs lhs += rhs ; // lhs = lhs + rhs; 结果 lhs == rhs rhs *= -1 ; // ... 结果 rhs == lhs
}
因为计算机C语言中的"="，它是赋值号，并非为等号。基于这个原理: 第一步:我们可以事先将两个数的和存储于同一个变量中(lhs和rhs是对称的，用那个都成，本本题中我们用lhs+=rhs;)
第二步:用rhs减去lhs并将结果保存在rhs中(即:rhs-=lhsl;)，此时rhs得到了“,lhs(这里的lhs的值是指原实参中的)”
第三步:将lhs变量(这时lhs变量的值是原实参中，两个的和)与rhs(其意义同上)作和，此时lhs变量便得到了，原实参中rhs的值(交换完毕了一半)。
第四步:由第二步知rhs存储的值实际是`-lhs`，此时对rhs求相反数即可实现另一半交换了(rhs *= -1;)。
NOTE:
,.现在内存比以前大多了，本题的意思并不是为了省一个整型变量，而是为了充分理解C语言乃至其它语言中的`,`并非为等号，它是值的存储过程，即为这个变量赋上一定的值(当然有时可以按等号来理解)
,.本编程为了体现一致性，采用时复合赋值运算，为追求代码的整齐，在第二步得到了“-lhs”,于是伴随着有了第四步。若改用单赋值运算，可将代码减少到,行以内(要保证可读性，其实到,行就可以了)
,.存在的缺点:就是第一步lhs+=rhs可能会导致溢出
方法二:
// 使用按位异或，实现交换 -- 逻辑运算
void SwapWithLog( int & lhs, int & rhs ) {
// 原理:一个数同另一数连续异或,次，可还原为自已
// 即: a == a ^ b ^ b
lhs = lhs ^ rhs ; // -1-
rhs = lhs ^ rhs ; // -2-
lhs = lhs ^ rhs ; // -3-
// -1- -2- 合并后即为 rhs = (lhs ^ rhs) ^ rhs // -2- -3- 合并后即为 lhs = lhs ^ (lhs ^ rhs) }
该算法利用二进制数(数在计算机就是以二进制的存储的<是补码>)按每一位求异或(两个相同时为,;一个是,,一个是,为,)的一个性质——对任意给定的一个二进制数来说，它与任意一个二进制数，连续异或两次最终得到的还是它本身即有(a = a ^ b ^b)。 证明:因为异或运算是可结合的(满足结合律)，且可交换的，所以任何情况一个数和另一个数连续异或都可成 “a ^b ^ b”的形式
再由结合性 a^b^b = a^(b^b) = a^0 = a ,
按照这个思想，再结合给出的注释，交换算法就很简单了。
小注:对于C的采用指针交换的方法，注以下算法是错误的，详见注解部分 void ErrSwap( int *plhs, int *prhs ) {
int *pTmp ;
pTmp = plhs ;
plhs = prhs ;
prhs = pTmp ;
// 只是交换了'址'而非'值'
// 即若执行 Swap( &lhs, &rhs ) ;
// 则 传入至函数入口处: _plhs = &lhs, _plhs = &rhs
// ***** 注: 函数调用时，为避免形、实参同名，在函数内形参名前有'_' // 临近函数结束时: _plhs 与 _prhs 发生了交换
// 即有: _plhs = &rhs, _prhs = &lhs // 但其中并为设计到 *_plhs 与 *_prhs 的相关信息
// 而 : lhs = *_plhs, rhs = *_prhs // 函数结束后 _plhs, _prhs 作为栈内存自动变量,生命期终结
// 从而 lhs 和 rhs 并未发生改变
}
一句话:指针只是作为两个独立空间的连接纽带罢了，指针值变了，而指针原来指向的原来内存空间的内容不一定变啊～
/****************************** 以下为完整的算法 *******************************/
#include
// 传统 C 交换 ,,使用指针
void Swap( int *plhs, int *prhs )
{
int tmp ;
tmp = *plhs ;
*plhs = *prhs ;
*prhs = tmp ;
}
// 一种错误的 数值交换!!
void ErrSwap( int *plhs, int *prhs ) {
int *pTmp ;
pTmp = plhs ;
plhs = prhs ;
prhs = pTmp ;
// 只是交换了'址'而非'值'
// 即若执行 Swap( &lhs, &rhs ) ;
// 则 传入至函数入口处: _plhs = &lhs, _plhs = &rhs // ***** 注: 函数调用时，为避免形、实参同名，在函数内形参名前有'_' // 临近函数结束时: _plhs 与 _prhs 发生了交换
// 即有: _plhs = &rhs, _prhs = &lhs // 但其中并为设计到 *_plhs 与 *_prhs 的相关信息
// 而 : lhs = *_plhs, rhs = *_prhs
// 函数结束后 _plhs, _prhs 作为栈内存自动变量,生命期终结 // 从而 lhs 和 rhs 并未发生改变
}
// C++ 交换 ,,使用引用
void Swap( int & lhs , int & rhs ) {
int tmp ;
tmp = lhs ;
lhs = rhs ;
rhs = tmp ;
}
// C++交换 ,,使用
模板
个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载
-- 代码同上
template
void Swap( Object & lhs, Object & rhs ) {
Object tmp ;
tmp = lhs ;
lhs = rhs ;
rhs = tmp ;
}
// 使用数值加(减)法，实现交换 -- 算术运算
void SwapWithAri( int & lhs, int & rhs ) {
lhs += rhs ; // lhs = lhs + rhs; 结果 lhs 保存两者之和 rhs -= lhs ; // rhs = rhs - lhs; 结果 rhs == -lhs lhs += rhs ; // lhs = lhs + rhs; 结果 lhs == rhs rhs *= -1 ; // ... 结果 rhs == lhs }
// 使用按位异或，实现交换 -- 逻辑运算
void SwapWithLog( int & lhs, int & rhs ) {
// 原理:一个数同另一数连续异或,次，可还原为自已
// 即: a == a ^ b ^ b
lhs = lhs ^ rhs ; // -1-
rhs = lhs ^ rhs ; // -2-
lhs = lhs ^ rhs ; // -3-
// -1- -2- 合并后即为 rhs = (lhs ^ rhs) ^ rhs // -2- -3- 合并后即为 lhs = lhs ^ (lhs ^ rhs) }
浙公网安备 33021202002483