約瑟夫問題的解法-良好接口的重要性

本文用一個簡單的例子來說明接口設計的重要性。使用的是Linux kernel中list_head，順便說一句，如果你想使用複合模式組織你的對象，那麼Linux kernel中的kobject結構是個不錯的選擇，如果時間允許，我準備用一下，想象一下Linux是如何組織缤紛複雜的總線和外部以及内部裝置的吧。

       從一個古老的又比較簡單的問題說起，這個問題就是古羅馬的約瑟夫問題：設有n個人圍坐在圓桌周圍，現從某個位置 i 上的人開始報數，數到 m 的人就站出來。下一個人，即原來的第m+1個位置上的人，又從1開始報數，再是數到m的人站出來。依次重複下去，直到全部的人都站出來，按出列的先後又可得到一個新的序列。為了節省篇幅，将i定為1。

       對于解決這類問題，最後留下的最有價值的東西就是問題本身的解決思路，而不是一堆看起來很棒的代碼，這些代碼用盡了所有的文法特性，為了尋求更多的榮譽，動用了大量的程式設計語言…這些都是垃圾！古羅馬沒有程式設計語言，但是人家照樣完美的解決了這個問題，程式設計語言隻是一個工具，是以不要動不動就代碼啊代碼，實作啊實作，貌似啊貌似，作為從事精準工作的程式員，如果你覺得你的想法有道理，那就直說，絕對不要使用諸如“貌似…吧”之類的短語，而這種短語在程式設計相關的論壇上十分常見，實際上發言人所要做的僅僅是呈出一個意見，十有八九是在挑刺，挑出樓上一個人代碼的一個毛病。還是那句老話，程式設計并不一定比燒鍋爐更有技術含量，它在某種意義上稱不上一種真正的技術，就像鋤頭一樣，工具而已，真想搞有技術含量的，那就去搞火箭，衛星，生物醫學，基因工程，超弦之類的…言歸正傳，不管任何算法題目，最有價值的東西就是算法本身，也就是解決方案的思路，而不是什麼代碼。

用一個main函數實作的那種代碼絕對是寫給會C語言的人看的，不懂程式設計的人根本看不懂，竟然還上了wiki，這種實作絕對是垃圾！在這裡也就不貼代碼了，google一下或者擺渡一下，全都是這種代碼。我也不是說我實作的就一定好，其實我寫的代碼也很垃圾，但是絕對比把所有邏輯都交給main要好。以下是我的實作，一步一步引導，最終說明接口的重要性。

以下的代碼使用了最常見的普通單向連結清單，一般都是這種設計的，如果你不想花點時間設計通用接口的話。雖然這種實作展現了封裝，但是還是沒有辦法直接展現算法的思路，沒法讓人一眼看出你是怎麼想的。下面是代碼：

以上的單連結清單實作，我們發現了兩個問題，第一個問題就是在go_to函數中維護了三個指針，分别是目前指針，目前指針的前一個，目前指針的下一個。為了維護這三個指針中的後兩個，一定要在連結清單初始化時定位最後一個節點以及儲存連結清單頭。第二個問題就是在main函數中用遞推方法組織了整個算法，實際上我們發現，這是個明顯可以遞歸解決的問題。關于第一個問題，交給了list_head實作，關于第二個問題，以下給出遞歸實作。

基本思路沒有什麼變化，隻是更加清晰了，使用了遞歸

以上的代碼看來，明顯簡潔了不少，沒有用main函數組織邏輯，算法邏輯全部交給了go_to，需要注意的是go_to的傳回值，由于隻是介紹思路，是以沒有将“出列者”儲存于任何容器，隻是簡單的printf列印，而實際上，應該另外單獨維護一個容器，比如棧或者隊列，然後在printf的地方将出列者放進隊列，然後在main函數中統一列印之。

       在遞歸實作中，go_to函數中的三個指針依舊，能否去除它們呢？那就是使用雙向連結清單，可是我們怎麼實作雙向連結清單呢？

一步一步的，現在使用雙向連結清單實作，所謂雙向連結清單，那無非就是在單向連結清單中增加了一個指針，那就是：

接下來就不貼代碼了，和單向連結清單相差別的是初始化函數以及go_to函數，不必再維護三個指針了，也不用維護全局變量了，隻需要簡單取出prev和next即可。現在，唯一的問題就是代碼還是展現不出解決問題的思路，還是堆砌了很多程式設計技巧相關的代碼，比如連結清單操作之類的，很顯然的做法就是将這些封裝成接口，然而這種封裝隻能讓這個約瑟夫問題看起來好些，對于其它的問題是無法重用的，因為entry結構體是不可重用的。

        Linux核心中list_head解決了這個問題。

Linux核心中的list_head是一個展現OO思想的良好設計的“侵入式”雙向連結清單。所謂侵入式，那就是它不和任何特定的資料結構相耦合，誰想将自己組織成連結清單，隻需簡單包含list_head字段即可，然後可以通過該字段在對應結構體中的偏移來根據list_head字段的位址取出相應結構體的位址，十分友善好用，核心的list.h頭檔案定義了幾乎所有的操作，在約瑟夫實作中，還需要一個接口，那就是list_step，該接口實作向前(向後-還沒有實作)推進N的功能：

有了上述接口，連同kernel自帶的，我給出使用list_head實作的約瑟夫問題的代碼：

可見，這個代碼很簡單，除了我的函數以及變量命名不是很好之外，如果命名良好，隻要看英語就可以知道整個解決思路了，沒有任何讓人看來是程式設計者專利的東西。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1270877