麵試問題之 按單詞反轉字符串

按單詞反轉字符串

 

題目要求：把字符串“I am a student”反轉成為“student a am I”，不借助任何庫函數。

 

字符串中單詞順序反轉的方法有很多種，我們可以定義一個棧結構，根據棧的特性，先進後出。我們通過依次查找空格（在實際分析單詞應用中這隻是最簡單的情況，單詞之間可能直接用標點符號區分，但是使用標點符號並不意味著就是兩個單詞,西方世界計數方式喜歡使用三位數字加一個逗號形式比如“3,483,123”,雖然我們可以找到“,”但是不能把“3,483,123”作為三個單詞來區分，應該看作一個單詞。如果我們再考慮中英文等字符問題，區分單詞將更加複雜，不過幸運的是，這裏我們不用考慮這麼複雜的情況）來區分單詞，然後把每個單詞依次壓棧，然後再從棧中依次讀出每個單詞，這樣實現整個字符串的單詞順序反轉，但是在具體實現過程中我們不得不考慮三個問題：

1：我們要定義一個棧結構來保存每個單詞，並在反轉字符串的過程中要維護，管理，填充這個棧結構，我們還要為每次申請填充單詞中字符數目的多少做出判斷，以便動態申請空間保存這個單詞，當我們使用完成後，要即使delete這個結構，防止內存泄漏。這樣我們的主要精力將放在這個棧的維護上，而不是單詞順序反轉上。

2：單詞分析時，如果我們把直接分析出來的單詞直接壓棧，再輸出時我們簡單的在兩個單詞之間加空格，可能導致反轉字符串和原來字符串不匹配，比如說“I am a  student” a和student直接是兩個空格，那麼按上麵的方式輸出反轉單詞後的字符串就是“student a am I”student和a之間隻有一個空格，這裏可能不是很明顯，如果原字符串用標點符號區分兩個單詞，而我們再填充空格，得到的字符串可能與原字符串真正意義的反轉相差很大。比如“student a，am I”反轉後為“I am a student”而不是“I am，a student”。麵對這樣問題，你不得不再定義一個棧結構保存兩個單詞的之間的關係，或者原來入棧的單詞不是真正意義的單詞，把空格或標點符號一並保存。

3：因為我們用棧保存反轉單詞數據，所以每使用完一次反轉數據，棧就清空一次，下次再使用之前就必須再次分析單詞，重新入棧。避免這個問題方法，可以使用數組意義的棧，即在棧中加一個索引操作，按入棧逆序索引出數據，但是不幸的是到這一步，你又不等不重新修改自己的棧結構。

綜合考慮，使用棧結構，我們不得不花費過多的精力去考慮棧結構，以及使用過程中的棧維護，使用結束後，刪除棧結構，防止資源泄漏。並且使用棧結構後，算法不屬於“原地”算法。至少多使用字符串空間的一倍空間，在內存緊張的係統裏（比如說嵌入時）這種方式是不可取的。但是這種方法並不是沒有優點，優點就是：字符串（一段話）隻需要遍曆一遍，就可以得到反轉後的字符串。

這裏我們要講解另外一種方法：使用反轉字符串方法，來實現單詞順序反轉。基本原理：首先我們把待反轉字符串（一段話）整體反轉，比如說“I am a student”反轉為”tneduts a ma I”,然後再逐個單詞反轉，最後得到“student a am I”。使用這種方法，相對使用棧結構來說優點就是我們使用一個反轉算法，代替棧結構，這個算法屬於“原地”算法，不需要再申請空間，隻要內存能夠容納字符串，就可以實現單詞反轉。缺點是：你不得不再寫一個獲得字符串長度的函數，並且幾乎是遍曆兩次字符串。

 

下麵是使用這種方法具體代碼：

 

// 函數名稱: Ustrlen

// 輸入參數: strSource,待求長度字符串；

// 輸出參數: int，字符串的長度。

// 描    述: 通過判斷字符'/0'來得到字符串的長度

/************************************************************************/
int Ustrlen(const char *strSource)

     // 聲明變量

     // 遍曆字符串，查找字符'/0'

     // 返回字符串的長度

// 函數名稱: _ReversalChar

// 輸入參數: strSouce，待反轉字符串；iStart，旋轉字符串開始位置；iEnd，旋轉字符串結束位置

// 輸出參數: char*，反轉後字符串的指針；

// 描    述: 反轉iStart到字符串iEnd之間的字符串

char* _ReversalChar(char *strSouce,int iStart,int iEnd)

     // 反轉字符串

     // 返回字符串指針

 

// 函數名稱: ReversalChar

// 輸入參數: strSource，待反轉字符串

// 輸出參數: char*，反轉字符串後的指針

// 描    述: 按單詞反轉字符串

char * ReversalChar(char *strSouce)

     // 獲取字符串的長度

 

     // 反轉整個字符串

 

     // 聲明變量（單詞的開始以及結束默認從0開始）

 

     // 查找單詞

     // 像上麵討論的查找單詞的情況，我們隻需要修改這部分，就可以實現對不

     // 同格式類型單詞進行處理，為了更好的通用性，其實最好把查找單詞這部分

     // 作為單獨一個函數，或者一個類來處理

         // 查找空格分割符號

              // 找到一個單詞

              // 對於隻有一個字符的單詞比如說（I）沒有必要反轉

                   // 反轉單詞

              // 記錄下一個單詞的開始位置

         // 特殊處理幾種常見標點符號

     // 返回反轉後的字符串

 

測試上麵的方法：

char ch[] ="I am a student!!";
cout << "Source string: " << ch << endl;
cout << "Reversal string: " << ReversalChar(aa) << endl;

屏幕打印字符

Source string: I am a student!!

Reversal string: !!student a am I

 

以上代碼測試環境：Windows2003＋VC7.1，如果直接在TC下使用，需要把int iStart(0)類型的變量賦值，修改為int iStart=0;類型。

 

解決這個問題的方法有很多，比方說可以使用二叉樹來存儲單詞，然後采用不同方法後續遍曆的方法，逆轉單詞順序，通常也可以利用雙向鏈表實現單詞逆轉，存在眾多方法解決這種問題，這些方法本身並沒有什麼好壞之分，關鍵是如果這種算法適合我們的情況，那麼這個算法就是最好的。比方說，傳遞給我們是一個雙向鏈表結構的一段話，讓我們逆序，那麼隻需要我們從後向前讀取即可。

 

其實如果這道題改成分析一段話中的每個單詞，難度會大很多。

 

少年不識愁滋味，為賦新詞強說愁