交换不连续的两个内存块.docx
交换不连续的两个内存块Io假设有两段连续的内存块a和b;2首先对内存块a进行反转：a,=reverse(a);3o接着对内存块b进行反转：b,=reverse(b);3o最后对内存块ab进行反转：(aby=ba;是不是很神奇？当我第一次看到这个算法的时候，我就惊叹为什么这三步简单的操作就能解决看似很复杂的问题？如果你还不相信的话(我一开始和你一样也是不相信)，请看下面的例子：Io假如有两段连续的内存块，a内存块的内容是匕bed”，b内存块的内容是“efgh”;2o首先对内存块a进行反转：a,=reverse(nabcd")=',dcba,'3o接着对内存块b进行反转:b,=reverse(',efgh")=",hgfe"4o最后对内存块a'b'进行反转：(a,b,),=reverse(1,dcbahgfen)=efghabcd;那”reversa1a1gorithm”和本文中需要解决的问题有什么联系呢？在看到这个问题的时候，我就立即联想到了“reversa1a1gorithm",我试图通过已有的方法去解决类似的问题。幸运的是经过简单的分析和推论，我就找到了一个简单的方法，这个方法只要对“reversa1a1gorithm”进行简单的修改就可以解决本文的问题：1假设有三段连续的内存a,b和c,这样a和C是不连续的;2首先对内存块a进行反转：a,=reverse(a);3接着对内存块b进行反转：b'=reverse(b);4接着对内存块c进行反转：c,=reverse(c);5最后对内存块a'bc进行反转：reverse(a'b'c')=cba;是不是超简单？这里使用了和"reversa1a1gorithm”一样的思路。最后一次反转，不仅分别将内存块a和c中的数据调整为初始状态，而且还交换它们的位置。由于内存块b处于中间的位置，最后一次反转只将它的内容调整到初始状态。实现篇有了上面的分析，编写代码实现这个算法就显得相对比较简单了：Io首先我们需要一个反转内存块的函数。这个函数应该说比较简单：/*/IIIIIII/swaponeadjacentmemoryb1ock/Thememory1ayout1ikethis:/11/memTota1Size/RETURNVA1UE:Theaddressofthememoryjustbeingswappedvoid*swapMemory(void*pMemoryzsize_tmemTota1Size).if(NU11=pMemory)returnpMemory;if(memTota1Size<2)returnpMemory;unsignedchar*pByteMemory=reinterpret_cast<unsignedchar*>(pMemory);for(size_ti=O;i<memTota1Size2;i+).unsignedchartempByte=*(pByteMemory+i);*(pByteMemory+i)=*(pByteMemory+memTota1Size-1-i);*(pByteMemory+memTota1Size-1-i)=tempByte;returnpMemory;)就这个函数的实现，有以下几点需要说明：I0在函数的开始，我对函数的参数进行了一定的约束，这个在"DesignByCOntraCt”中被称作前项约束"Precondition”。相应的，在函数的最后还有一个后项约束"PoStConditiorT；在函数中间的部分，应该还有一个被称为不变式(InVariant)的东西。这些约束的目的就是保证函数在开始/中间/结束过程中处于一个正确的状态。2如果要对内存进行逐字节的访问，我们可以通过一个字符指针来完成。一个字符所占的内存空间是一个字节，它在内存块中的索引值就等于它相对于内存块首地址的偏移量。2有了上面的函数，按照本文前面的分析，我们就可以很容易实现本文的算法了：SW叩twononadjacentmemoryb1ock/Thememory1ayout1ikethis:/I111/memHeadSizememTota1Size-memHeadSize-memEndSizememEndSize/Thestart/endindexforthethreememoryb1ocksare:/Theheadb1ock:Oz(memHeadSize-1);/Themidd1eb1ock:memHeadSize,(memTota1Size-memEndSize-1);/Theendb1ock:(memTota1Size-memEndSize)z(memEndSize-1);/RETURNVA1UE:Theaddressofthememoryjustbeingswappedvoid*swapNonadjacentMemory(void*PMemOry,sizememTota1Size,size_tmemHeadSize,size_tmemEndSize).if(NU11=pMemory)returnpMemory;if(memTota1Size<3)returnpMemory;if(memTota1Size<memEndSize)returnpMemory;if(memTota1Size<(memHeadSize+memEndSize)returnpMemory;unsignedchar*pByteMemory=reinterpret_cast<unsignedchar*>(pMemory);/step1:reversetheheadb1ockswapMemory(pByteMemor½memHeadSize);/step2:reversethemidd1eb1ockswapMemory(pByteMemory+memHeadSize)1(memTota1Size-memHeadSize-memEndSize);/step3:reversetheendb1ockswapMemory(pByteMemory+memTota1Size-memEndSize)zmemEndSize);/step4:reversethewho1eb1ockswapMemory(pByteMemoryzmemTota1Size);returnpMemory;)在这个函数的前项约束中，第一个和第二个约束很好理解，第三个和第四个约束是如何得到的？一开始我也就写了前两个约束，当我写完了所有的代码后进行复查的时候，我看到了这样的函数调用：swapMemory(pByteMemory+memTota1Size-memEndSize)zmemHeadSize);如果(memTota1Size-memEndSize)小于0,那就有可能访问到不属于它的内存，这个操作是非常危险的，是绝对要禁止的，所在我们需要添加约束来避免这样的参数进入到函数的内部。接着我又在随后的代码中找到需要约束的地方：swapMemory(pByteMemory+memHeadSize)z(memTota1Size-memHeadSize-memEndSize);这里需要约束(memTota1Size-memHeadSize-memEndSize)不小于Oo经过以上的代码复查过程，我就添加了第三个和第四个前项约束。测试篇我写了一个函数用来测试本文实现的算法：voidTest_swapNonadjacentMemory()./tab1e-driventestcasestaticconstchar*testString=.I1/",ab"zabc,zabcdefghn)；void*pMemory=ma11oc(MAXMEMBFFERSIZE);if(NU11=pMemory)return;for(inti=0;i<sizeof(testString)sizeof(costchar*);i+).size_tiString1ength=str1en(testStringi);/c1earthememoryb1ockmemset(pMemoryzOzMAXMEMBUFFERSIZE);/copyfromthestringmemcpy(pMemoryztestStringiziString1ength);/reversethememoryb1ockSWaPNOnadjaCemMemory(PMemory,iString1ength,3,3);)free(pMemory);)值得注意的是，这里我把所有的测试字符串都放在一个“表”中，然后用一个简单的循环语句就可以对所有的测试字符串进行测试，同时如果想修改测试字符串或者添加新的测试用例，只需要对表进行操作就可以了。后记在随后的文章中，我将使用本文的算法去解决更复杂的问题：反转一个字符串中所有单词。有兴趣的朋友也可以思考一下这个问题，据说这个问题是微软的一个面试题。参考资料Io编程珠矶，第二版本人强烈推荐此书！此书博大精深，是修炼内功的好资料。看看大家是怎么评价这本书的吧：这里还有此书的配套网站：转载：httpbenny5609archive200804252327022.aspx
