基于ＸＭＬ鏈?zhǔn)浇Y(jié)構(gòu)的研究

摘 要：提出一種基于鏈?zhǔn)浇Y(jié)構(gòu)的XML文檔生成方法。其解析得到的元素內(nèi)容及文本內(nèi)容生成的結(jié)點插入到相應(yīng)的位置，以二叉鏈表的數(shù)據(jù)結(jié)構(gòu)將樹的信息存儲在數(shù)據(jù)庫中。服務(wù)器端將數(shù)據(jù)庫中樹的信息轉(zhuǎn)化成XML，客戶端將其加載到瀏覽器的(DOM實例中，并采用深度優(yōu)先搜索算法對該實例中的結(jié)點進行遞歸遍歷，生成瀏覽器端樹的HTML代碼。

關(guān)鍵詞：樹形結(jié)構(gòu)；XML；二叉鏈表；鏈?zhǔn)浇Y(jié)構(gòu)

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ù)結(jié)構(gòu)中，樹型結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu)，樹形結(jié)構(gòu)是結(jié)點之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機構(gòu)都可用樹形象地表示。樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。這里可以充分利用其優(yōu)點進行系統(tǒng)管理。

XML( Extensible Markup Language，可擴展的標(biāo)記語言。XML是一套定義語義標(biāo)記的規(guī)則，這些標(biāo)記將文檔分成許多部件并對這些部件加以標(biāo)識。它也是元標(biāo)記語言，即定義了用于定義其他與特定領(lǐng)域有關(guān)的、語義的、結(jié)構(gòu)化的標(biāo)記語言的句法語言。其起源于SGML( Standard Generalized Markup Language，是SGML的一個子集合，即SGML的一個簡化版本，它非常適合于在Web上或其他多種數(shù)據(jù)源間進行數(shù)據(jù)的交換。XML非常適合表達樹的層次邏輯，為此將XML與數(shù)據(jù)庫技術(shù)結(jié)合起來，實現(xiàn)樹的顯示和維護。

2 二叉鏈表的結(jié)構(gòu)

在計算機中存儲一棵樹，不僅要存儲樹中每個結(jié)點的數(shù)值，而且還要存儲結(jié)點與結(jié)點之間的關(guān)系。二叉樹(Binary Tree是n(n≥0個結(jié)點的有限集，它或者是空集(n=0，或者由1個根結(jié)點及2棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。

3 樹形結(jié)構(gòu)的具體實現(xiàn)

3.1 二叉鏈表結(jié)構(gòu)的設(shè)計

給出一個二叉樹接點的Java接口，稱之為BinNode。BinNode類中存儲指向Object類的引用。創(chuàng)建二叉樹時，可以根據(jù)需要而采用實際的數(shù)據(jù)類型。成員函數(shù)包括返回元素的值，返回左、XML右節(jié)點指針，設(shè)置元素的值，判斷該結(jié)點是否為葉結(jié)點。

Interface BinNode{ [JY]//二叉樹結(jié)點的抽象數(shù)據(jù)類型

//返回并設(shè)置元素值

public Object element(;

public Object setElement(Object V;

//返回并設(shè)置左孩子

public Binnode left(;

public Binnode setLeft(BinNode p;

//返回并設(shè)置右孩子

public Binnode right(;

public Binnode setRight(BinNode p;

//判斷是否為葉結(jié)點

public boolean isLeaf(;

} //interface BinNode

3.2 將數(shù)據(jù)庫中樹的信息轉(zhuǎn)化成XML

初始條件:樹T存在，id是樹中某個結(jié)點編號。操作目的:將以id為根結(jié)點的子樹轉(zhuǎn)化為XML格式。算法思想:根據(jù)當(dāng)前根結(jié)點找出左孩子和右兄弟，添加當(dāng)前結(jié)點信息到XML中，然后遞歸以左孩子為根結(jié)點的子樹，最后在遞歸以右兄弟為根結(jié)點的子樹。還要注意如果當(dāng)前結(jié)點為該樹的根結(jié)點，則不能遞歸以它的右兄弟為根結(jié)點的子樹。

算法描述:



void genTreeViewXML( String rootNode，String currNode{

//根據(jù)當(dāng)前結(jié)點currNode找出其左孩子llink和右兄弟rlink以及name，

XML+=\"

if(llink==′0′{XML+=\">\"}

else( XML+=\">\"

genTreeViewXML( rootNode，llink;

XML+=\"\" ;}

if(rlink!=′0′ currNode!=rootNode{

//遞歸調(diào)用生成右兄弟的子樹

genTreeViewXML(rootNode，rlink; 

}}

3.3 解析XML顯示樹形結(jié)構(gòu)

將數(shù)據(jù)庫中以二叉鏈表結(jié)構(gòu)存儲的樹的信息通過上述方法轉(zhuǎn)化為所需的XML后，現(xiàn)在就可以通過操作XML文檔對象模型將數(shù)據(jù)島顯示在瀏覽器端。

初始條件:XML形式的數(shù)據(jù)島。操作目的:通過JavaScript解析XML并以HTML的形式在瀏覽器端顯示樹。算法思想:將數(shù)據(jù)島加載到DOM對象后，向瀏覽器添加根結(jié)點的HTML代碼，對DOM對象根結(jié)點的所有一級子結(jié)點，再遞歸調(diào)用顯示其下一級子結(jié)點的HTML代碼。

算法描述:



function getTreeHTML(rootNode{

[JY]//將結(jié)點rootNode的HTML信息以htm1形式添加到瀏覽器端

for(i=0;i< rootNodechidNodeslength;i++

{

//遞歸調(diào)用生成其各子結(jié)點的HTML代碼 

getTreeHTML( rootNodechildNodes ［i］ ; 

}}

3.4 基于樹形結(jié)構(gòu)的維護

從數(shù)據(jù)庫中提取樹的信息后，在瀏覽器端樹上設(shè)置JavaScript事件，通過它們我們可以對該樹進行維護，包括插入、刪除、更新、移動等操作。維護的時候，JavaScript事件將用戶對樹的維護情況記錄到XML對象中。

<插入目標(biāo)結(jié)點編號=\" \">

<插入項屬性名=\"name\"值=\" \"/>

<插入項屬性名=\"id\"值=\" \"/>



其他刪除、更新、移動結(jié)點操作需要對XML增加的信息與此相似。用戶維護結(jié)束，將該XML對象提交到服務(wù)器，后臺負責(zé)根據(jù)設(shè)置的插入、刪除等操作標(biāo)志解析上述XML對象，就可以生成相應(yīng)的插入、刪除、更新的SQL語句，最后提交到數(shù)據(jù)庫。另外需要注意的是，由于數(shù)據(jù)庫中存儲的二叉鏈表形式的各結(jié)點相互間有關(guān)聯(lián)，所以對其進行插入、刪除、移動操作時候還必須考慮因此操作而引起的相關(guān)結(jié)點的信息的更新，比如當(dāng)刪除一個結(jié)點時，除了需要刪除該結(jié)點外，還可能要修改其父結(jié)點的左孩子指針的值，或者需要修改其上一個兄弟結(jié)點的右兄弟指針的值。

4 結(jié) 語

軟件設(shè)計中數(shù)據(jù)結(jié)構(gòu)的選擇十分重要。對目前應(yīng)用非常廣泛的樹形結(jié)構(gòu)做了比較深入的研究，發(fā)現(xiàn)應(yīng)用XML技術(shù)和二叉鏈表的存儲結(jié)構(gòu)相結(jié)合能夠非常方便穩(wěn)定地存儲、顯示、維護樹，并且此種存儲結(jié)構(gòu)應(yīng)用于支持遞歸SQL的Oracle數(shù)據(jù)庫時更能體現(xiàn)其方便性，如獲取該樹的一個子樹，以及取得某結(jié)點的父結(jié)點等都可以通過1條簡潔的遞歸SQL語句實現(xiàn)，為該樹的可擴展性和可通用性提供了必要的條件。

參 考 文 獻

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版［M］.北京:清華大學(xué)出版社，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ù)結(jié)構(gòu)[M].武漢：華中理工大學(xué)出版社，2000.