基于ＸＭＬ鏈式結構的研究
2008-04-12 00:00:00謝佳譚歆姚斌
現(xiàn)代電子技術 2008年12期
摘 要：提出一種基于鏈式結構的XML文檔生成方法。其解析得到的元素內容及文本內容生成的結點插入到相應的位置，以二叉鏈表的數(shù)據(jù)結構將樹的信息存儲在數(shù)據(jù)庫中。服務器端將數(shù)據(jù)庫中樹的信息轉化成XML，客戶端將其加載到瀏覽器的(DOM實例中，并采用深度優(yōu)先搜索算法對該實例中的結點進行遞歸遍歷，生成瀏覽器端樹的HTML代碼。
關鍵詞：樹形結構；XML；二叉鏈表；鏈式結構
Research of Chain-link Structure Based on XML
XIE Jia，TAN Xin，YAO Bin
(Telecommunication College，Shaanxi University of Science and Technology，Xi′an，710021，China
Abstract：This paper introduces a measure of storing，showing and vindicating the tree structure.The element and text contents are inserted into the correct position，we store the tree structure information to the relational database by the data structure of binary chained list.The server translates it from database to a format of XML，then the client loads it to DOM and traverses recursively for each node of DOM by arithmetic and creates a tree which has the same structure with the XML document in the way of HTML.
eywords：tree structure;XML;binary chained list;chain-link structure
1 引 言
在數(shù)據(jù)結構中，樹型結構是一種非常重要的非線性結構，樹形結構是結點之間有分支，并具有層次關系的結構。它非常類似于自然界中的樹。樹結構在客觀世界中是大量存在的，例如家譜、行政組織機構都可用樹形象地表示。樹在計算機領域中也有著廣泛的應用，例如在編譯程序中，用樹來表示源程序的語法結構；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。這里可以充分利用其優(yōu)點進行系統(tǒng)管理。
XML( Extensible Markup Language，可擴展的標記語言。XML是一套定義語義標記的規(guī)則，這些標記將文檔分成許多部件并對這些部件加以標識。它也是元標記語言，即定義了用于定義其他與特定領域有關的、語義的、結構化的標記語言的句法語言。其起源于SGML( Standard Generalized Markup Language，是SGML的一個子集合，即SGML的一個簡化版本，它非常適合于在Web上或其他多種數(shù)據(jù)源間進行數(shù)據(jù)的交換。XML非常適合表達樹的層次邏輯，為此將XML與數(shù)據(jù)庫技術結合起來，實現(xiàn)樹的顯示和維護。
2 二叉鏈表的結構
在計算機中存儲一棵樹，不僅要存儲樹中每個結點的數(shù)值，而且還要存儲結點與結點之間的關系。二叉樹(Binary Tree是n(n≥0個結點的有限集，它或者是空集(n=0，或者由1個根結點及2棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。
3 樹形結構的具體實現(xiàn)
3.1 二叉鏈表結構的設計
給出一個二叉樹接點的Java接口，稱之為BinNode。BinNode類中存儲指向Object類的引用。創(chuàng)建二叉樹時，可以根據(jù)需要而采用實際的數(shù)據(jù)類型。成員函數(shù)包括返回元素的值，返回左、XML右節(jié)點指針，設置元素的值，判斷該結點是否為葉結點。
Interface BinNode{ [JY]//二叉樹結點的抽象數(shù)據(jù)類型
//返回并設置元素值
public Object element(;
public Object setElement(Object V;
//返回并設置左孩子
public Binnode left(;
public Binnode setLeft(BinNode p;
//返回并設置右孩子
public Binnode right(;
public Binnode setRight(BinNode p;
//判斷是否為葉結點
public boolean isLeaf(;
} //interface BinNode
3.2 將數(shù)據(jù)庫中樹的信息轉化成XML
初始條件:樹T存在，id是樹中某個結點編號。操作目的:將以id為根結點的子樹轉化為XML格式。算法思想:根據(jù)當前根結點找出左孩子和右兄弟，添加當前結點信息到XML中，然后遞歸以左孩子為根結點的子樹，最后在遞歸以右兄弟為根結點的子樹。還要注意如果當前結點為該樹的根結點，則不能遞歸以它的右兄弟為根結點的子樹。
算法描述:
void genTreeViewXML( String rootNode，String currNode{
//根據(jù)當前結點currNode找出其左孩子llink和右兄弟rlink以及name，
XML+=\" if(llink==′0′{XML+=\">\"} else( XML+=\">\" genTreeViewXML( rootNode，llink; XML+=\"\" ;} if(rlink!=′0′ currNode!=rootNode{ //遞歸調用生成右兄弟的子樹 genTreeViewXML(rootNode，rlink; }} 3.3 解析XML顯示樹形結構 將數(shù)據(jù)庫中以二叉鏈表結構存儲的樹的信息通過上述方法轉化為所需的XML后，現(xiàn)在就可以通過操作XML文檔對象模型將數(shù)據(jù)島顯示在瀏覽器端。 初始條件:XML形式的數(shù)據(jù)島。操作目的:通過JavaScript解析XML并以HTML的形式在瀏覽器端顯示樹。算法思想:將數(shù)據(jù)島加載到DOM對象后，向瀏覽器添加根結點的HTML代碼，對DOM對象根結點的所有一級子結點，再遞歸調用顯示其下一級子結點的HTML代碼。 算法描述: function getTreeHTML(rootNode{ [JY]//將結點rootNode的HTML信息以htm1形式添加到瀏覽器端 for(i=0;i< rootNodechidNodeslength;i++ { //遞歸調用生成其各子結點的HTML代碼 getTreeHTML( rootNodechildNodes ［i］ ; }} 3.4 基于樹形結構的維護 從數(shù)據(jù)庫中提取樹的信息后，在瀏覽器端樹上設置JavaScript事件，通過它們我們可以對該樹進行維護，包括插入、刪除、更新、移動等操作。維護的時候，JavaScript事件將用戶對樹的維護情況記錄到XML對象中。 <插入目標結點編號=\" \"> <插入項屬性名=\"name\"值=\" \"/> <插入項屬性名=\"id\"值=\" \"/> 其他刪除、更新、移動結點操作需要對XML增加的信息與此相似。用戶維護結束，將該XML對象提交到服務器，后臺負責根據(jù)設置的插入、刪除等操作標志解析上述XML對象，就可以生成相應的插入、刪除、更新的SQL語句，最后提交到數(shù)據(jù)庫。另外需要注意的是，由于數(shù)據(jù)庫中存儲的二叉鏈表形式的各結點相互間有關聯(lián)，所以對其進行插入、刪除、移動操作時候還必須考慮因此操作而引起的相關結點的信息的更新，比如當刪除一個結點時，除了需要刪除該結點外，還可能要修改其父結點的左孩子指針的值，或者需要修改其上一個兄弟結點的右兄弟指針的值。 4 結 語 軟件設計中數(shù)據(jù)結構的選擇十分重要。對目前應用非常廣泛的樹形結構做了比較深入的研究，發(fā)現(xiàn)應用XML技術和二叉鏈表的存儲結構相結合能夠非常方便穩(wěn)定地存儲、顯示、維護樹，并且此種存儲結構應用于支持遞歸SQL的Oracle數(shù)據(jù)庫時更能體現(xiàn)其方便性，如獲取該樹的一個子樹，以及取得某結點的父結點等都可以通過1條簡潔的遞歸SQL語句實現(xiàn)，為該樹的可擴展性和可通用性提供了必要的條件。 參 考 文 獻 ［1］嚴蔚敏，吳偉民.數(shù)據(jù)結構(C語言版［M］.北京:清華大學出版社，2002. ［2］XML Encryption WG[EB/OL].http://www.w3.org/Encryption/2001/（Accessed Nov.6，2004）. ［3］XML Signature WG[EB/OL].http://www.w3.org/Signature/ （Accessed Nov.6，2004）. ［4］薛超英.數(shù)據(jù)結構[M].武漢：華中理工大學出版社，2000.
