在網(wǎng)站建設(shè)中，分類算法的應(yīng)用非常的普遍。在設(shè)計一個電子商店時，要涉及到商品分類；在設(shè)計發(fā)布系統(tǒng)時，要涉 及到欄目或者頻道分類；在設(shè)計軟件下載這樣的程序時，要涉及到軟件的分類；如此等等。可以說，分類是一個很普遍的 問題。 我常常面試一些程序員，而且我?guī)缀鹾翢o例外地要問他們一些關(guān)于分類算法的問題。下面的舉幾個我常常詢問的問 題。你認為你可以很輕松地回答么^_^. 1、 分類算法常常表現(xiàn)為樹的表示和遍歷問題。那么，請問：如果用數(shù)據(jù)庫中的一個Table來表達樹型分類，應(yīng)該有幾個字 段？ 2、 如何快速地從這個Table恢復(fù)出一棵樹； 3、 如何判斷某個分類是否是另一個分類的子類； 4、 如何查找某個分類的所有產(chǎn)品； 5、 如何生成分類所在的路徑。 6、 如何新增分類； 在不限制分類的級數(shù)和每級分類的個數(shù)時，這些問題并不是可以輕松回答的。本文試圖解決這些問題。 分類的數(shù)據(jù)結(jié)構(gòu) 我們知道：分類的數(shù)據(jù)結(jié)構(gòu)實際上是一棵樹。在《數(shù)據(jù)結(jié)構(gòu)》課程中，大家可能學(xué)過Tree的算法。由于在網(wǎng)站建設(shè)中 我們大量使用數(shù)據(jù)庫，所以我們將從Tree在數(shù)據(jù)庫中的存儲談起。 為簡化問題，我們假設(shè)每個節(jié)點只需要保留Name這一個信息。我們需要為每個節(jié)點編號。編號的方法有很多種。在數(shù) 據(jù)庫中常用的就是自動編號。這在access、SQL Server、Oracle中都是這樣。假設(shè)編號字段為ID。 為了表示某個節(jié)點ID1是另外一個節(jié)點ID2的父節(jié)點，我們需要在數(shù)據(jù)庫中再保留一個字段，說明這個分類是屬于哪個 節(jié)點的兒子。把這個字段取名為FatherID。如這里的ID2，其FatherID就是ID1。 這樣，我們就得到了分類Catalog的數(shù)據(jù)表定義： Create Table [Catalog]( [ID] [int] NOT NULL, [Name] [nvarchar](50) NOT NULL, [FatherID] [int] NOT NULL ); 約定：我們約定用-1作為最上面一層分類的父親編碼。編號為-1的分類。這是一個虛擬的分類。它在數(shù)據(jù)庫中沒有記 錄。 如何恢復(fù)出一棵樹 上面的Catalog定義的最大優(yōu)勢，就在于用它可以輕松地恢復(fù)出一棵樹-分類樹。為了更清楚地展示算法，我們先考慮 一個簡單的問題：怎樣顯示某個分類的下一級分類。我們知道，要查詢某個分類FID的下一級分類，SQL語句非常簡單： select Name from catalog where FatherID=FID 顯示這些類別時，我們簡單地用<LI>來做到：
<% REM oConn---數(shù)據(jù)庫連接，調(diào)用GetChildren時已經(jīng)打開 REM FID-----當(dāng)前分類的編號
Function GetChildren(oConn,FID) strSQL = "select ID,Name from catalog where FatherID="&FID set rsCatalog = oConn.Execute(strSQL) %> <UL> <% Do while not rsCatalog.Eof %> <LI><%=rsCatalog("Name")%> <% Loop %> </UL> <% rsCatalog.Close End Function %> 現(xiàn)在我們來看看如何顯示FID下的所有分類。這需要用到遞歸算法。我們只需要在GetChildren函數(shù)中簡單地對所有ID 進行調(diào)用：GetChildren(oConn,Catalog("ID"))就可以了。 <% REM oConn---數(shù)據(jù)庫連接，已經(jīng)打開 REM FID-----當(dāng)前分類的編號
Function GetChildren(oConn,FID) strSQL = "select Name from catalog where FatherID="&FID set rsCatalog = oConn.Execute(strSQL) %> <UL> <% Do while not rsCatalog.Eof %> <LI><%=rsCatalog("Name")%> <%=GetChildren(oConn,Catalog("ID"))%>
<% Loop %> </UL> <% rsCatalog.Close End Function %> 修改后的GetChildren就可以完成顯示FID分類的所有子分類的任務(wù)。要顯示所有的分類，只需要如此調(diào)用就可以了： <% REM strConn--連接數(shù)據(jù)庫的字符串，請根據(jù)情況修改 set oConn = Server.CreateObject("ADODB.Connection") oConn.Open strConn =GetChildren(oConn,-1) oConn.Close %>
如何查找某個分類的所有產(chǎn)品； 現(xiàn)在來解決我們在前面提出的第四個問題。第三個問題留作習(xí)題。我們假設(shè)產(chǎn)品的數(shù)據(jù)表如下定義： Create Table PRoduct( [ID] [int] NOT NULL, [Name] [nvchar] NOT NULL, [FatherID] [int] NOT NULL ); 其中，ID是產(chǎn)品的編號，Name是產(chǎn)品的名稱，而FatherID是產(chǎn)品所屬的分類。 對第四個問題，很容易想到的辦法是：先找到這個分類FID的所有子類，然后查詢所有子類下的所有產(chǎn)品。實現(xiàn)這個算 法實際上很復(fù)雜。代碼大致如下： <% Function GetAllID(oConn,FID) Dim strTemp
If FID=-1 then strTemp = "" else strTemp ="," end if
strSQL = "select Name from catalog where FatherID="&FID set rsCatalog = oConn.Execute(strSQL) Do while not rsCatalog.Eof strTemp=strTemp&rsCatalog("ID")&GetAllID(oConn,Catalog("ID")) REM 遞歸調(diào)用 Loop rsCatalog.Close
GetAllID = strTemp End Function
REM strConn--連接數(shù)據(jù)庫的字符串，請根據(jù)情況修改 set oConn = Server.CreateObject("ADODB.Connection") oConn.Open strConn
FID = Request.QueryString("FID")
strSQL = "select top 100 * from Product where FatherID in ("&GetAllID(oConn,FID)&")" set rsProduct=oConn.Execute(strSQL) %> <UL><% Do while not rsProduct.EOF %> <LI><%=rsProduct("Name")%> <% Loop %> </UL> <%rsProduct.Close oConn.Close %>
位編碼算法 對任何順序編碼的Catalog表，我們可以設(shè)計一個位編碼算法，將所有的類別編碼規(guī)格化為位編碼。在具體實現(xiàn)時，我們先 創(chuàng)建一個臨時表： Create TempCatalog( [OldID] [int] NOT NULL, [NewID] [int] NOT NULL, [OldFatherID] [int] NOT NULL, [NewFatherID] [int] NOT NULL ); 在這個表中，我們保留所有原來的類別編號OldID和其父類編號OldFatherID，以及重新計算的滿足位編碼要求的相應(yīng) 編號NewID、NewFatherID。 程序如下： <% REM oConn---數(shù)據(jù)庫連接，已經(jīng)打開 REM OldFather---原來的父類編號 REM NewFather---新的父類編號 REM N---編碼總位數(shù) REM Ni--每一級的編碼位數(shù)數(shù)組 REM Level--當(dāng)前的級數(shù)
sub FormatAllID(oConn,OldFather,NewFather,N,Nm,Ni byref,Level) strSQL = "select CatalogID , FatherID from Catalog where FatherID=" & OldFather set rsCatalog=oConn.Execute( strSQL )
j = 1 do while not rsCatalog.EOF i = 2 ^(N - Nm) * j if Level then i= i + NewFather
OldCatalog = rsCatalog("CatalogID") NewCatalog = i
調(diào)用這個算法的一個例子如下： <% REM 定義編碼參數(shù)，其中N為總位數(shù)，Ni為每一級的位數(shù)。 Dim N,Ni(5)
Ni(1) = 4
N = Ni(1)
for i=2 to 5 Ni(i) = 7 N = N + Ni(i) next
REM 打開數(shù)據(jù)庫，創(chuàng)建臨時表 strSQL = "Create TempCatalog( [OldID] [int] NOT NULL, [NewID] [int] NOT NULL, [OldFatherID] [int] NOT NULL, [NewFatherID] [int] NOT NULL);" Set Conn = Server.CreateObject("ADODB.Connection") Conn.Open application("strConn") Conn.Execute strSQL
REM 調(diào)用規(guī)格化例程 FormatAllID Conn,-1,-1,N,Ni(1),Ni,0
REM ------------------------------------------------------------------------ REM 在此處更新所有相關(guān)表的類別編碼為新的編碼即可。 REM ------------------------------------------------------------------------
REM 關(guān)閉數(shù)據(jù)庫 strSQL= "drop table TempCatalog;" Conn.Execute strSQL Conn.Close %>
第四個問題 現(xiàn)在我們回頭看看第四個問題：怎樣得到某個分類下的所有產(chǎn)品。由于采用了位編碼，現(xiàn)在問題變得很簡單。我們很 容易推算：某個產(chǎn)品屬于某個類別的條件是Product.FatherID&（Catalog.ID的特征碼）=Catalog.ID。其中"&"代表位與算 法。這在SQL Server中是直接支持的。 舉例來說：產(chǎn)品所屬的類別為：1092787200，而當(dāng)前類別為1092780032。當(dāng)前類別對應(yīng)的特征值為：4294950912，由 于1092787200&4294950912=8537400，所以這個產(chǎn)品屬于分類8537400。 我們前面已經(jīng)給出了計算特征碼的公式。特征碼并不多，而且很容易計算，可以考慮在Global.asa中Application_OnStart 時間觸發(fā)時計算出來，存放在Application("Mark")數(shù)組中。 當(dāng)然，有了特征碼，我們還可以得到更加有效率的算法。我們知道，雖然我們采用了位編碼，實際上還是一種順序編 碼的方法。表現(xiàn)出第I級的分類編碼肯定比第I+1級分類的編碼要小。根據(jù)這個特點，我們還可以由FID得到兩個特征碼，其 中一個是本級位特征碼FID0，一個是上級位特征碼FID1。而產(chǎn)品屬于某個分類FID的充分必要條件是： Product.FatherID>FID0 and Product.FatherID<FID1 下面的程序顯示分類FID下的所有產(chǎn)品。由于數(shù)據(jù)表Product已經(jīng)對FatherID進行索引，故查詢速度極快： <% REM oConn---數(shù)據(jù)庫連接，已經(jīng)打開 REM FID---當(dāng)前分類 REM FIDMark---特征值數(shù)組，典型的情況下為Application("Mark") REM k---數(shù)組元素個數(shù)，也是分類的級數(shù) Sub GetAllProduct(oConn,FID,FIDMark byref,k) REM 根據(jù)FID計算出特征值FID0,FID1 for i=k to 1 if (FID and FIDMark = FID ) then exit next
strSQL = "select Name from Product where FatherID>"FIDMark(i)&" and FatherID<"FIDMark(i-1) set rsProduct=oConn.Execute(strSQL)%> <UL><% Do While Not rsProduct.Eof%> <LI><%=rsProduct("Name") Loop%> </UL><% rsProduct.Close End Sub %>
