前言：在 前面一篇文章中，我們在反轉長度不等的兩塊連續記憶體塊的算法的基礎上推導出了反轉長度不等的兩塊不連續記憶體塊的算法。在本文中，我将使用前文分析的算法去解決一個更複雜的問題：反轉字元串中的單詞。
引子
話說有這樣一道算法題：
PROBLEM: Reverse Words
COMMENT: Write a function that reverses the order of the words in a string.For instance,your function should transform the string "Do or do not,there is no try." to "try.no is there not,do or Do". Assume that all words are space delimited and treat punctuation the same as letters.
這個問題常見國内外各大IT論壇中，而且被多家著名的IT公司頻繁拿來用來作為面試題去考察面試者的基本功。從題目涉及到的内容來看，這個題并不是很難，但是如果對時間複雜度和空間複雜度進行限制的話，在短時間内設計出一個讓面試官滿意的算法也并不是一件簡單的事情。接下來，我首先簡單介紹一下最常見的算法，這個算法思路比較直接，但是在時間複雜度和空間複雜度上很難滿足條件。然後我就"隆重"介紹我所采用的算法，這個算法是前篇文章介紹的算法的一個延伸，并采用一個重要的解決問題的技巧－"Divide-and-Conquer"。
分析篇
當我們初次接觸這個題的時候，我相信我們的腦海了已經浮現出一個完整的解決方案：
1。開辟一段記憶體用來存放反轉後的結果，這段記憶體的大小應該不小于源字元串的大小。
2。由于我們要反轉字元串，我們很自然的就會想到從字元串的尾部向字元串的頭部周遊。
3。在周遊的過程中，當我們找到一個單詞的時候，就把這個單詞拷貝到目标記憶體塊中。
4。當我們周遊了字元串中所有的字元時，周遊過程中。由于是從後向前周遊，這時并沒有什麼辨別符辨別結束，我們隻有先記錄下字元串的長度，當剩下的字元串長度為0時，周遊結束。
這個解決方案雖然簡單，但是在實作的時候卻總能碰到一些困難。由于我們是從後向前周遊，我們按順序獲得的單詞中的字元是反序的，但是當我們把這個單詞拷貝到目标記憶體塊時卻要正序拷貝。我們同時還要記錄要拷貝單詞的首位址和末位址，還要提防"Off-By-One"的錯誤。
除了實作起來會遇到點麻煩外，這個算法最大的問題就是在于目标記憶體塊的開辟，導緻在空間複雜度上不夠理想。由于我們事先不可能知道源字元串的長度，我們更不能假定源字元串的最大長度(還記得"緩沖區溢出"麼？)，是以我們至少要開辟一段和源字元串一樣長度的記憶體塊，這樣算法的空間複雜度就達到O(n)。同時這個算法首先要周遊字元串來獲得字元串的長度，然後還要對字元串再進行一次周遊來獲得字元串中的單詞，這樣算法的時間複雜度就達到O(n)。
是不是還存在優化的空間呢？答案當然時肯定的。如果我們跳出我們熟悉的思路架構，站的更高一點，從更高一級的抽象去分析這個問題，我們獲得了一個完全不同于傳統算法的解決方案。
從整體來說，我們要處理的是由多個單詞(單詞之間用空格分割)構成的字元串，這個字元串中基本的元素就是單詞和空格。我首先拿幾個簡單的特例來分析一下，看看有沒有什麼收獲。
1> 字元串中沒有空格。這樣字元串中的所有元素可以被看成是一個單詞。這時候，就沒有既要進行任何操作。
2> 字元串中有一個空格(此時暫時不考慮空格出現在字元串最前面或者最後面的情況)。這是反轉兩個單詞的操作就等價于反轉長度不等的兩個不連續記憶體塊的操作，這個操作我們已經在 前篇文章中實作了。
3> 字元串中有兩個空格。例如這樣的字元串"Tom Jerry Mike"，我們此時該如何處理這個字元串呢？結合前兩個特例的分析，我立即想到了一種最常見的解決問題的思路－"Divide-and-Conquer"。總體來說，我們可以将包含多于一個空格的字元串劃分成三個部分：
| 位于空格左邊的子字元串 | 空格 | 位于空格右邊的子字元串 |
這樣我們就要完成下面的處理：
step1。對位于空格左邊的子字元串進行"Reverse Words"操作；
step2。對位于空格右邊的子字元串進行"Reverse Words"操作；
step3。對整個字元串進行分轉處理。
如果左右字元串中還包含多于一個空格，我們可以分别對他們再進行這樣的分割+反轉的操作，直到字元串中空格的數量不大于1。
看到這裡，你是不是聯想到一個常見的算法和這個算法有驚人的相似？對，就是"Merge Sort"算法，它們之間唯一的差別就在于"Merge Sort"中是進行排序操作，而這裡需要進行反轉操作。借用"Merge Sort"算法的人氣，我把本文的算法稱為 "Merge Reverse"算法。
這裡還剩下一個問題，對于字元串中的多個空格，我們該選用那個空格做分割點？如果你聯想到了"Binary Search"，答案就霍然明朗了，我們可以選用處于中間位置(median)的空格作為分割點。
實作篇
有了上面的分析，再結合 前篇文章中實作的算法，本文的算法實作起來就顯得十分簡單了：
void * reverseStringByWord( void * pMemory,size_t memTotalSize)
... {
if (NULL == pMemory) return pMemory;
if (memTotalSize < 2) return pMemory;
unsigned char* pByteMemory = reinterpret_cast<unsigned char*>(pMemory);
int iTotalSeparator = 0;
size_t* pSeparatorIndexArray = reinterpret_cast<size_t*>(malloc(sizeof(size_t)*memTotalSize));
if (NULL == pSeparatorIndexArray) return pMemory;
for (size_t i = 0; i < memTotalSize; i++) ...{
if (*(pByteMemory+i) == SPACESEPARATOR) ...{
*(pSeparatorIndexArray+iTotalSeparator) = i;
iTotalSeparator++;
}
}
if (iTotalSeparator == 0) ...{
//do nothing
}else if (iTotalSeparator == 1) ...{
size_t iMiddleSeparatorIndex = pSeparatorIndexArray[0];
size_t iHeadBlockSize = iMiddleSeparatorIndex;
size_t iEndBlockSize = memTotalSize-iHeadBlockSize-SEPARATORLENGH;
swapNonadjacentMemory(pByteMemory,memTotalSize,iHeadBlockSize,iEndBlockSize);
}else ...{
size_t iMiddleSeparatorIndex = pSeparatorIndexArray[iTotalSeparator/2];
size_t iHeadBlockSize = iMiddleSeparatorIndex;
size_t iEndBlockSize = memTotalSize-iHeadBlockSize-SEPARATORLENGH;
reverseStringByWord(pByteMemory,iHeadBlockSize);
reverseStringByWord(pByteMemory+iHeadBlockSize+1,iEndBlockSize);
swapNonadjacentMemory(pByteMemory,memTotalSize,iHeadBlockSize,iEndBlockSize);
}
free(pSeparatorIndexArray);
return pMemory;
}
測試篇
我寫了一段測試用例來測試本文實作的算法：
void Test_reverseStringByWord() ... {
//table-driven test case
static const char* testString[] = ...{
"",
"ab",
" a",
"a ",
"a b",
"ab cd ef",
"ab cd ef ",
" ab cd ed",
"aaa bbb ccc"
};
void* pMemory = malloc(MAXMEMBUFFERSIZE);
if (NULL == pMemory) return;
for (int i = 0; i < sizeof(testString)/sizeof(const char*); i++) ...{
printf("|%s|==>",testString[i]);
size_t iStringLength = strlen(testString[i]);
memset(pMemory,0,MAXMEMBUFFERSIZE);
memcpy(pMemory,testString[i],iStringLength);
reverseStringByWord(pMemory,iStringLength);
printf("|%s| ",reinterpret_cast<char*>(pMemory));
}
free(pMemory);
}
值得注意的是，這個算法在處理空格位于字元串的首部(或者尾部)的情況，還需要商榷和進一步的分析。
後記
通過本文的算法分析，我們能發現和總結一些算法設計的原則：
原則1：The Power of Primitive
一個複雜的問題往往可以被抽象成一個最基本的問題，這個基本的問題雖然簡單，但是往往能夠描述問題的實質。在我們解決問題的時候，能否正确的抓住問題的實質往往就是能夠正确解決問題的關鍵。在本文介紹的算法中我們發現，在反轉字元串中的單詞的算法中最本質的操作就是交換不等長的兩段不連續記憶體塊。有了這個對問題本質的深入了解，我們就可以借助現有的算法輕松這個問題。
原則2：Divide-and-Conquer
這個思想不愧是解決很多問題的"不二法則"。看看算法書中有多少經典的算法應用了這個思路，我們就會驚歎的發現我們對它的認識還是很淺。這個思路最核心的本質，或者說成功的關鍵，就在于它可以将一個規模稍大的問題劃分成一個或者多個規模稍小的問題，同時規模稍小的問題要比規模稍大的問題容易解決，隻有這樣，"Divide-and-Conquer" 才能現露它的神奇之處。在本文的算法中，反轉字元串中的單詞的問題最終被劃分成反轉兩個不連續記憶體塊的問題。
曆史
12/16/2006 v1.0
原文的第一版
12/17/2006 v1.1
添加了後記部分，對本文中使用的兩個算法設計原則進行了簡單的總結
參考文獻
1。《 程式設計珠玑，第二版》
"The Power of Primitive"也是書中第二章的總結的一個算法分析原則。再一次強烈這本書。
2。《 Foundations of Algorithms Using C++ Pseudocode, Third Edition》
這本書中的第二章對"Divide-and-Conquer"進行深入分析，讀後你一定會對它有了更深的認識和了解，這種深入的認識和了解對我們解決很多問題有很大幫助。