老萬>碼工的故事——我和資料結構

2025-05-04 06:24 老萬故事會

上週（2024 年 12 月 10 日），清華大學的嚴蔚敏教授去世了，享年 86 歲。
嚴教授寫過《資料結構》大學教材。資料結構是程式設計師的基礎課。據睡在我上鋪的郭教授回憶，我在中國科大讀書時用的就是嚴老師的教材。願嚴老師安息。
這則訊息讓我想起了我學習資料結構的幾個小故事。
上中學時，我在蘋果機上學習了 Basic 語言和 6502 彙編。那時的我，不懂結構化程式設計為何物，沒有面對過物件，不知什麼是資料結構，更說不出來它有何用。
無知者最無畏。我認定：一切計算機問題都可以用陣列和全域性變數解決。如果不行，就上二維陣列。
我祖上有位名人，叫萬百千。他自小聰穎，三天就學會了寫字。

第一天，先生教他寫一橫，說：“這是一。”
第二天，先生教他寫兩橫，說：“這是二。”
第三天，先生教他寫三橫，說：“這是三。”
先祖一拍大腿：“我會了！”
先祖的母親說：“我兒，把你名字寫給娘瞧瞧。”

先祖卒。

我就像那位名人老祖，沒有意識到“能解決”和“能用合理代價解決”的區別。

後來我上了大學，聽高年級的老鄉說“資料結構”很有用，就有了瞭解一下的想法。
我不喜讀正兒八經的教材，但對有趣的東西卻一拍即合。我在報上讀到有一本書叫《資料結構趣談》，據說通俗易懂，適合我這樣的門外漢，便著手採辦。
我從科大西區跑到東區，又在合肥最繁華的三孝口和四牌樓來回跑了幾趟，書沒買到，倒是添了幾盤流行音樂的磁帶，花光了下個月和下下個月的預算。
為了能吃上飯，我停止了布朗運動，改成寫信，請一位在上海讀書的女同學代為購買。上海地方大，果然成功了。
讀了女同學寄的書，豁然開朗。從此我知道了二叉樹的三種遍歷法和排隊要先進先出的道理，言必稱指標。
學成文武藝，貨與帝王家。我自學了資料結構的知識，便常去機房逡巡，以圖有女同學問我問題。
然而在科大要見到女生已屬不易，要她們提問更是千年等一回。要知道我們班的獎學金是長期女生霸榜的。
傻人有傻福，愚公待兔最後還真給我等到了。
一個黃道吉日，我又在機房找了一個女同學邊的位置上機。
過了一會兒，女同學托腮沉思，顯然是遇到了難題。
我把鍵盤敲得噼啪響。這叫盲打，知道麼？
突然，女同學轉向我，發出天問：同學，在 Turbo C 的編輯器裡一直向右移動游標最多可以跑多遠？
這尼瑪超綱了啊！
如果我看過王家衛的《東邪西毒》，此刻或許可以雲淡風輕地回答“每個人都會經過這個階段，見到一個游標，就想知道游標後面是什麼。我很想告訴你，可能移過去，你會發覺沒什麼特別。再移回來，會覺得這邊更好”。
但王家衛不能讓我在 1991 年看到還沒開拍的《東邪西毒》，我也只能在震驚中石化在原地。
答不出女同學問題的恥辱，一直刻在了我的心上，成為我胸口永遠的痛。我恨！游標右移有時盡，此恨綿綿無絕期。
這傷痕直到我出國之前一年才被熨平。
那一天，秋日的陽光穿過中科院計算所稀疏的樹枝，斑駁地照在南樓緊閉的玻璃窗上，投射出忽明忽暗的圖案，讓正在除錯C++指標的我浮想聯翩。
這時系統提示我有郵件。
朋友們，這可是 1996 年，香港還是英國的殖民地，克林頓還在競選連任，全世界不會有5個人會想到給我發郵件，有電子信是一件大事，抵得萬金油一盒。
我開啟郵箱看標題，是一位先一步去美國的女同學的email。
我確認背後無人，才打開郵件。
這位女同學得了美國教育的真傳，跳過了對偉大友誼的回顧，開門見山進入主題：她有一道資料結構作業不會做，想要 wen wen 我。
這道題要求用線性時間判定一個單向連結串列是否有環。
五年之後，我看到了這道題的聰明解法：用兩個指標 p 和 q 同時從頭遍歷這個連結串列，但是它們前進的速度不一樣，p 每走一步，q 要走兩步。如果 p 和 q 在某一步又碰面了，就說明有環。如果 q 走到鏈尾也沒有重逢，就是沒環。如果連結串列有 N 個節點，最多迭代 N 次就會有結論，所以是線性時間複雜度。
但我不是大聰明，發明不了這個演算法。那時候也沒有谷歌雅虎，連在實驗室用 telnet 和 http 都是要罰款的，因為網路頻寬是稀缺資源，1KB 要兩毛錢人民幣。
但我一心要一雪前恥，冥思苦想數小時，終於在沒有演算法的地方想出了一個演算法，趕在女同學的 deadline 前做完了作業。
我的演算法也是從頭開始遍歷連結串列，但只用一個指標，一邊遍歷一邊將連結串列翻轉，也就是說遍歷到節點 n 時，順手把從 n 到後續節點 m 的指標改成從 m 到 n。如果遍歷結束時能回到起點，就說明有環，否則就沒有環。進一步分析表明，要是連結串列裡有 N 個節點，不超過 2N 步就會結束，所以時間複雜度也是線性的。
只是，我的演算法有一個問題：它不是無損的。跑完演算法後連結串列被翻了個個兒，不再是原來的連結串列。
但不怕，我有補救的辦法。
東東槍老師的六里莊人民廣播電臺有個廣受歡迎的欄目“房中有術”，專門介紹夫妻生活小常識。第一期房中有術節目送給大家的是一個冷知識：酒後行房，顛倒五臟，所以酒後不能行房。
但是有人問了：如果酒後偏要行房，就要行房，不得不行房，又該怎麼辦呢？
對此槍老師有一個妙方：酒後行房，顛倒五臟。那麼行過之後再行一次，不就把顛倒後的五臟又再顛倒回來了嗎？
對於連結串列環的判定演算法，我獨立於槍老師提出了類似的解法，那就是把連結串列翻轉之後再翻轉一次，連結串列不就還原了嗎？
當然，萬氏雙翻法效率堪憂，雖然滿足線性時間複雜度的要求，但操作步數比起聰明解法要多很多，實用性稍遜。
不過，這是我自己發明的演算法，必須敝帚自珍。
等我到了美國，讀完書工作了，在我歌面試程式設計師時資料結構是必考的，這門基礎課也就長期駐留記憶體。
現在學習資料結構的條件比我們那時候不知強了多少倍，有 LeetCode 可以刷題，有 GPT 可以答疑，那道曾經難倒科大女生的演算法題，只能算是入門級了。
只是塞翁得馬，焉知非禍。學習上不求人了，跟女同學套瓷的機會就少了許多，不知拆散了多少好姻緣。瓊瑤阿姨地下有知，一定會對成功刷題上岸的男同學講：
葛革你好無知好膚淺好愚昧，你得到的不過是百萬年薪，可你失去的卻是美眉的愛情啊！
～～～～～～～～～～
猜你會喜歡：
～～～～～～～～～～
關注老萬故事會公眾號：
本公眾號不開讚賞不放廣告。如果喜歡這篇文章，歡迎點贊、在看、轉發。謝謝大家🙏


相關文章