資料結構實踐——“求兩集合交集”的一個錯解分析

　　本文點評一位學生對基于線性表存儲集合，然後對集合進行求并運算的錯解，供學習者參考。

【項目 - 求集合并集】

　　假設有兩個集合 a 和 b 分别用兩個線性表 la 和 lb 表示，即線性表中的資料元素即為集合中的成員。設計算法，用函數unionlist(list la, list lb, list &lc )函數實作該算法，求一個新的集合c=a∪b，即将兩個集合的并集放線上性表lc中。

提示： （1）除了實作unnionlist函數外，還需要在main函數中設計代碼，調用unionlist進行測試和示範； （3）也可以将實作算法中需要的線性表的基本運算對應的函數，與自己設計的所有程式放在同一個檔案中。

【錯解】

【我的點評】

　　閱讀代碼知道，第8行lc=la，意即從此lc指向的也就是la指向的線性表了。對照題目要求，合并後的lc應該是一個新的線性表，此處處理不合要求。

　　若不考慮這一要求，lc=la後，合并的結果就儲存在la（也是lc）中了。在記憶體通路的機制中，這是合法的。（這兒和記憶體管理中的什麼堆區、棧區之類的沒有關系。記憶體管理機制對于計算機類的學生很重要，但一般入門級階段并不講。）合法僅是在合乎文法要求的層面，事實上，lc原先指向的空間從此沒有由任何變量指向，也沒有被釋放，成了“遊離”的垃圾。　　

　　接下來的讨論，我們就以合并後的結果儲存到la中為起點。

　　第9-15行的處理，可以看出學生在算法設計時沒有理清頭緒。la（lc）中已經是并集中的第一部分元素了，接下來，應該是“将lb中有，但la沒有的元素，加到lc中”（嚴格講，“lb中的元素”指lb指針指向的線性表代表的集合中的元素，la、lc同），代碼沒有展現出這層意思。為了完成這一任務，要考察lb中的每個元素，最外層的循環，應該針對的是lb，而不是la。

　　故算法架構應該是：

　　如何知道“lb集合中的第i個元素不在原la集合中”？這需要和la集合中的元素逐個比較的！于是這裡需要針對“原la集合”構造一個循環，以便逐個比較。顯然，11-14行的一個分支結構，僅完成“la和lb相同序号的元素是否相等”，是不足以考察la中的每一個元素的。于是上面是算法架構拓展為：

　　于是，盡可能在原錯誤程式基礎上修改，且合并後的結果lc實際就是la的情況下，得到的完整代碼為：

　　需要強調的是，<code>for (j = 0; j &lt;lena; j++)</code>中的lena是“原la”的長度，不能用<code>la-&gt;length</code>代替，因為在la、lc混用的情況下，<code>la-&gt;length</code>随着插入，是動态變化着的。

　　在上面的解答中，我将<code>displist(lc);</code>放到main函數中了。unionlist隻管合并，不管别的任何事情。這是軟體工程中“高内聚”的要求——一個子產品盡可能隻完成單一的工作。“顯示結果”是“求并”以後做的工作，兩者是“平級”的，不要将顯示作為合并的一部分。

　　還有，新代碼中的27和30（在原代碼中也有）沒有必要，這樣建立了線性表，卻在合并時直接将lc和la共用空間了，何必呢，反倒使一塊空間徹底成了垃圾。

　　在初學者的學習中，一定要争取自己寫出來。可以參考一切可以用到的資料啟發自己，給出自己的解答。寫出這樣的錯解，也是好的成果，中間的思考、嘗試過程是我們真正要的東西。這個過程價值連城。當自己已經經過一定的思考之後，再看一些相對規範的解法（例如本文中的參考解答），也是很必要的。觀摩、閱讀是學習方法。如果能在觀摩中品到其味道，再去仿制一份，也便極好。