ＪＳＰ实现基于中值排序基数法的ＢＢＳ树状结构.doc

ＪＳＰ实现基于中值排序基数法的ＢＢＳ树状结构 　　摘要：用JSP实现基于中值排序基数法的BBS树状结构，给出数据结构的设计以及具体的算法实现。 　　关键词： JSP；中值排序基数法；BBS 　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)29-0409-02 　　Using JSP Based in the Sort of the Middle Value of the Base of the Tree Structure of the BBS 　　YUAN An-cui, WANG Gong-qiang 　　(Rizhao Polytechnic,Rizhao 276826,China) 　　Abstract: Using JSP based in the sort of the middle value of the base of the tree structure of the BBS, given the data structure and the specific design of the algorithm. 　　Key words: JSP; the sort of the middle value of the base; BBS 　　 　　1 引言 　　 　　JSP是当今开发交互式网站的主流技术之一，也是实现BBS的首选技术之一。在BBS的实现中，很多人会选择树状展现，而实现树状展现比较简单是用递归算法。当然，递归是一个可行的办法，但对于BBS来说，这样做势必要进行大量的Sql查询，虽然可以使用存储过程来做，但要从根本上加快速度，则应该考虑更快的算法。本文中使用的中值排序基数法是一种彻底屏弃递归的实现树状结构的算法。 　　 　　2 算法思想 　　 　　2.1 数据结构的设计 　　在数据结构的设计中，表中的字段依次为：帖子id字段，记录父贴id的冗余字段pid,记录根id的rootid字段，记录帖子标题的title字段，记录帖子内容的cont字段，用于记录回复的深度的deep字段，排序基数字段ordernum，标识是否为叶子节点的字段isleaf。 　　2.2 具体实现算法 　　数据表的各字段中id、rootid、deep均为int型，ordernum为float型。根贴id自动生成为1，rootid为0，deep为0，ordernum为0；在回复同一根贴的贴子时，id顺序自动生成，rootid取根贴的id，deep取其父贴的deep加1，ordernum取其父贴与其父贴的下一贴两者ordernum的平均数（贴子按ordernum字段排序），对于根贴的第一个回帖，ordernum字段要取一个足够大的2的幂的数（如65536=216，为了简单起见，例子中取64），对于最后一贴的回帖，ordernum取父贴的ordernum加上一个2的幂。下面举例说明（只列出相关字段）： 　　例： id rootiddeepordernum 　　 1000 　　 211 64 　　在此基础上回复第1贴（即id为1的帖子），则新贴id自动生成为3，ordernum取第1、2基数的中值即(0+64)/2即32，deep取其父贴的deep加1，即为1。 　　排序后结果为： 　　 id rootiddeepordernum 　　 1000 　　 311 32 　　 211 64 　　回复第3贴，ordernum取3、2的基数中值即(32+64)/2，deep取其父贴的deep加1，即为2，排序后结果为: 　　 id rootiddeepordernum 　　 1000 　　 311 32 　　 412 48 　　 211 64 　　这样排序基数ordernum与回复深度deep一起就实现了如下的树状结构： 　　 id 　　 1 　　 ――3 　　 ――――4 　　 ――2 　　 　　3 实现 　　 　　由于中值排序基数算法主要体现在帖子的回复中，因此这里只给出对回复帖子进行处理的实现，通过request获得的参数均为添加回复页面传递过来的参数。数据库以Mysql为例。 　　int id = Integer.ParsInt(request.getParameter(‘id’));//被回复帖子的// id，即新帖的pid 　　int rootid = Integer.ParsInt(request.getParameter(‘rootid’)); 　　String title = request.getParameter(‘title’); 　　String cont = request.getParame