ＪＳＰ實(shí)現(xiàn)基于中值排序基數(shù)法的ＢＢＳ樹狀結(jié)構(gòu)

摘要：用JSP實(shí)現(xiàn)基于中值排序基數(shù)法的BBS樹狀結(jié)構(gòu)，給出數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)以及具體的算法實(shí)現(xiàn)。

關(guān)鍵詞： JSP；中值排序基數(shù)法；BBS

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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是當(dāng)今開發(fā)交互式網(wǎng)站的主流技術(shù)之一，也是實(shí)現(xiàn)BBS的首選技術(shù)之一。在BBS的實(shí)現(xiàn)中，很多人會(huì)選擇樹狀展現(xiàn)，而實(shí)現(xiàn)樹狀展現(xiàn)比較簡單是用遞歸算法。當(dāng)然，遞歸是一個(gè)可行的辦法，但對(duì)于BBS來說，這樣做勢必要進(jìn)行大量的Sql查詢，雖然可以使用存儲(chǔ)過程來做，但要從根本上加快速度，則應(yīng)該考慮更快的算法。本文中使用的中值排序基數(shù)法是一種徹底屏棄遞歸的實(shí)現(xiàn)樹狀結(jié)構(gòu)的算法。

2 算法思想

2.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

在數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)中，表中的字段依次為：帖子id字段，記錄父貼id的冗余字段pid，記錄根id的rootid字段，記錄帖子標(biāo)題的title字段，記錄帖子內(nèi)容的cont字段，用于記錄回復(fù)的深度的deep字段，排序基數(shù)字段ordernum，標(biāo)識(shí)是否為葉子節(jié)點(diǎn)的字段isleaf。

2.2 具體實(shí)現(xiàn)算法

數(shù)據(jù)表的各字段中id、rootid、deep均為int型，ordernum為float型。根貼id自動(dòng)生成為1，rootid為0，deep為0，ordernum為0；在回復(fù)同一根貼的貼子時(shí)，id順序自動(dòng)生成，rootid取根貼的id，deep取其父貼的deep加1，ordernum取其父貼與其父貼的下一貼兩者ordernum的平均數(shù)（貼子按ordernum字段排序），對(duì)于根貼的第一個(gè)回帖，ordernum字段要取一個(gè)足夠大的2的冪的數(shù)（如65536=216，為了簡單起見，例子中取64），對(duì)于最后一貼的回帖，ordernum取父貼的ordernum加上一個(gè)2的冪。下面舉例說明（只列出相關(guān)字段）：

例：id rootiddeepordernum

1000

211 64

在此基礎(chǔ)上回復(fù)第1貼（即id為1的帖子），則新貼id自動(dòng)生成為3，ordernum取第1、2基數(shù)的中值即(0+64)/2即32，deep取其父貼的deep加1，即為1。

排序后結(jié)果為：

id rootiddeepordernum

1000

311 32

211 64

回復(fù)第3貼，ordernum取3、2的基數(shù)中值即(32+64)/2，deep取其父貼的deep加1，即為2，排序后結(jié)果為:

id rootiddeepordernum

1000

311 32

412 48

211 64

這樣排序基數(shù)ordernum與回復(fù)深度deep一起就實(shí)現(xiàn)了如下的樹狀結(jié)構(gòu)：

id

1

——3

————4

——2

3 實(shí)現(xiàn)

由于中值排序基數(shù)算法主要體現(xiàn)在帖子的回復(fù)中，因此這里只給出對(duì)回復(fù)帖子進(jìn)行處理的實(shí)現(xiàn)，通過request獲得的參數(shù)均為添加回復(fù)頁面?zhèn)鬟f過來的參數(shù)。數(shù)據(jù)庫以Mysql為例。

int id = Integer.ParsInt(request.getParameter(‘id’));//被回復(fù)帖子的// id，即新帖的pid

int rootid = Integer.ParsInt(request.getParameter(‘rootid’));

String title = request.getParameter(‘title’);

String cont = request.getParameter(‘cont’);

Class.forname(“com.mysql.jdbc.Driver”);

String url = ”jdbc:mysql://localhost/bbs?user=rootpassword=root”;

Connection conn = DriverManager.getConnection(url);

Statement stmt = conn.createStatement();

ResultSet rs = stmt.excuteQuery(“select * from article where rootid =” + rootid + “order by ordernum asc);

ordernum1 = 0;

ordernum2 = 0;

int deep = 0;

while (rs.next()){

if(rs.getInt(“id”) == id ){

ordernum1 = rs.getInt(“ordernum”);

deep = rs.getInt(“deep”) + 1;

rs.next();

ordernum2 = rs.getInt(“ordernum”);

break;

}}

int ordernum = (ordernum1 + ordernum2)/2;

String sql = “insert into article values(1，?，?，?，?，?，?，0)”;

PreparedStatement pstmt = conn.PrepareStatement(sql);

pstmt.setInt(1，id);

pstmt.setInt(2，rootid);

pstmt.setString(3，title);

pstmt.setString(4，cont);

pstmt.setInt(5，deep);

pstmt. setInt(6，ordernum);

pstmt.executeUpdate();

stmt.excuteUpdate(“update article set isleaf = 1 where id = ”+ id);

//將新帖的父貼設(shè)置成非葉子節(jié)點(diǎn)

stmt.close();

pstmt.close();

conn.close();

4 總結(jié)

本文給出了jsp實(shí)現(xiàn)中值排序基數(shù)法，從而實(shí)現(xiàn)BBS的樹狀結(jié)構(gòu)，是一種效率比較高的實(shí)現(xiàn)方法。但是實(shí)現(xiàn)并不完美，沒有考慮錯(cuò)誤處理以及數(shù)據(jù)庫訪問的同步等問題，在實(shí)際的應(yīng)用中應(yīng)該加以完善。

參考文獻(xiàn)：

[1] 廖彥華.基于Jsp技術(shù)的網(wǎng)上購物系統(tǒng)[J].電腦知識(shí)與技術(shù):學(xué)術(shù)交流，2007(12):1276-1279.

[2] 陳欣，繆天鵬.基于JSP動(dòng)態(tài)網(wǎng)站的建設(shè)[J].計(jì)算機(jī)與數(shù)字工程，2004，32(4):94-96．

[3] Vikram Vaswani.MySQL完全手冊[M].北京:電子工業(yè)出版社，2004.