一种效率极高的分类算法

2008-02-23 05:06:34来源:互联网 阅读 ()

新老客户大回馈,云服务器低至5折

分类算法要解决的问题
网站建设中,分类算法的应用非常的普遍。在设计一个电子商店时,要涉及到商品分类;在设计发布系统时,要涉及到栏目或者频道分类;在设计软件下载这样的程序时,要涉及到软件的分类;如此等等。可以说,分类是一个很普遍的问题。

我常常面试一些程序员,而且我几乎毫无例外地要问他们一些关于分类算法的问题。下面的举几个我常常询问的问题。你认为你可以很轻松地回答么^_^.

1、分类算法常常表现为树的表示和遍历问题。那么,请问:如果用数据库中的一个Table来表达树型分类,应该有几个字段?
2、如何快速地从这个Table恢复出一棵树;
3、如何判断某个分类是否是另一个分类的子类;
4、如何查找某个分类的所有产品;
5、如何生成分类所在的路径。
6、如何新增分类;

在不限制分类的级数和每级分类的个数时,这些问题并不是可以轻松回答的。本文试图解决这些问题。

分类的数据结构
我们知道:分类的数据结构实际上是一棵树。在《数据结构》课程中,大家可能学过Tree的算法。由于在网站建设中我们大量使用数据库,所以我们将从Tree在数据库中的存储谈起。

为简化问题,我们假设每个节点只需要保留Name这一个信息。我们需要为每个节点编号。编号的方法有很多种。在数据库中常用的就是自动编号。这在Access、SQL Server、Oracle中都是这样。假设编号字段为ID。

为了表示某个节点ID1是另外一个节点ID2的父节点,我们需要在数据库中再保留一个字段,说明这个分类是属于哪个节点的儿子。把这个字段取名为FatherID。如这里的ID2,其FatherID就是ID1。

这样,我们就得到了分类Catalog的数据表定义:

Create Table [Catalog](

[ID] [int] NOT NULL,

[Name] [nvarchar](50) NOT NULL,

[FatherID] [int] NOT NULL

);

约定:我们约定用-1作为最上面一层分类的父亲编码。编号为-1的分类。这是一个虚拟的分类。它在数据库中没有记录。

如何恢复出一棵树
上面的Catalog定义的最大优势,就在于用它可以轻松地恢复出一棵树—分类树。为了更清楚地展示算法,我们先考虑一个简单的问题:怎样显示某个分类的下一级分类。我们知道,要查询某个分类FID的下一级分类,SQL语句非常简单:

select Name from catalog where FatherID=FID

显示这些类别时,我们简单地用<LI>来做到:


<%

REM oConn---数据库连接,调用GetChildren时已经打开

REM FID-----当前分类的编号


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

%>

现在我们来看看如何显示FID下的所有分类。这需要用到递归算法。我们只需要在GetChildren函数中简单地对所有ID进行调用:GetChildren(oConn,Catalog(“ID”))就可以了。

<%

REM oConn---数据库连接,已经打开

REM FID-----当前分类的编号


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分类的所有子分类的任务。要显示所有的分类,只需要如此调用就可以了:

<%

REM strConn--连接数据库的字符串,请根据情况修改

set oConn = Server.CreateObject("ADODB.Connection")

oConn.Open strConn

=GetChildren(oConn,-1)

oConn.Close

%>


如何查找某个分类的所有产品;
现在来解决我们在前面提出的第四个问题。第三个问题留作习题。我们假设产品的数据表如下定义:

Create Table Product(

[ID] [int] NOT NULL,

[Name] [nvchar] NOT NULL,

[FatherID] [int] NOT NULL

);

其中,ID是产品的编号,Name是产品的名称,而FatherID是产品所属的分类。

对第四个问题,很容易想到的办法是:先找到这个分类FID的所有子类,然后查询所有子类下的所有产品。实现这个算法实际上很复杂。代码大致如下:

<%

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 递归调用

Loop

rsCatalog.Close


GetAllID = strTemp

End Function


REM strConn--连接数据库的字符串,请根据情况修改

set oConn = Server.CreateObject("ADODB.Connection")

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Microsoft IIS 真的如此「不安全」吗?(1)

下一篇:不刷新页面的情况下调用远程ASP