李宗杰（1983－）
男，浙江人，（華北計(jì)算機(jī)系統(tǒng)工程研究所，北京  100083）華北計(jì)算機(jī)系統(tǒng)工程研究所碩士研究在讀生，研究方向?yàn)橛?jì)算機(jī)工業(yè)過程控制。

摘要：本論文首先描述了一種數(shù)據(jù)恢復(fù)功能的總體設(shè)計(jì)思想；在此基礎(chǔ)上，根據(jù)樹型數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，具體化總體設(shè)計(jì)思想，設(shè)計(jì)出一套高效數(shù)據(jù)恢復(fù)功能的實(shí)現(xiàn)方案，達(dá)到時(shí)間和空間上的優(yōu)化；最后，以接近C++的偽代碼方式，描述了該方案實(shí)現(xiàn)的部分算法。

關(guān)鍵詞：樹型結(jié)構(gòu)；數(shù)據(jù)恢復(fù)；撤銷；重復(fù)

Abstract: This paper describes a total strategy on recovery of data. According to the characteristic of tree structure, the paper shows a concrete shape of total strategy just mentioned to realize the recovery of tree structure effectively. At last, the algorithm implementation is given by the C++ pseudo-code.

Key words:  Tree Structure；Data Recovery；Undo；Redo

1 引言

    很多的軟件離不開數(shù)據(jù)的操作，包括數(shù)據(jù)的修改、刪除和增加，而在操作的時(shí)候，用戶存在誤操作的可能，尤其是一些編輯軟件，例如微軟的word、excel等。在這種情況下，如果軟件提供數(shù)據(jù)恢復(fù)的功能，用戶將可以十分方便的通過此功能使數(shù)據(jù)回到歷史的某個(gè)狀態(tài)。

    另一方面，樹型結(jié)構(gòu)是一種應(yīng)用十分廣泛的數(shù)據(jù)結(jié)構(gòu)，比如組織結(jié)構(gòu)，物料清單，資料檔案管理，資產(chǎn)管理等等都是以樹型結(jié)構(gòu)為基礎(chǔ)。在現(xiàn)實(shí)生活中，有許多事物可以抽象為樹狀結(jié)構(gòu)。這種結(jié)構(gòu)可以簡(jiǎn)化對(duì)某些事物的理解，使概念清晰[1]。而且，樹作為一種常見的數(shù)據(jù)結(jié)構(gòu)，已經(jīng)有了一套成熟的研究成果。因此，有很多項(xiàng)目采用樹型結(jié)構(gòu)來抽象具體的事物，實(shí)現(xiàn)軟件的開發(fā)。

    為此，對(duì)樹型結(jié)構(gòu)數(shù)據(jù)恢復(fù)功能的探討是很有意義的。

    下文首先描述了一個(gè)可行的比較通用的數(shù)據(jù)恢復(fù)設(shè)計(jì)思想，在此基礎(chǔ)上，分析樹型數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，設(shè)計(jì)出一套針對(duì)樹型數(shù)據(jù)結(jié)構(gòu)的高效數(shù)據(jù)恢復(fù)方案。

2 總體設(shè)計(jì)思想

    實(shí)現(xiàn)數(shù)據(jù)恢復(fù)的前提是記錄各個(gè)時(shí)刻的歷史信息，即各個(gè)時(shí)刻的數(shù)據(jù)；然后，在必要的時(shí)候響應(yīng)“撤銷”、“重復(fù)”的命令，實(shí)現(xiàn)歷史的無損復(fù)現(xiàn)。

    從“撤銷、重復(fù)”操作的角度，可以把不同時(shí)間點(diǎn)的內(nèi)存數(shù)據(jù)信息劃分為三個(gè)狀態(tài)：過去式、當(dāng)前、將來式。

    在每一個(gè)時(shí)間點(diǎn)上都有其對(duì)應(yīng)的數(shù)據(jù)信息。在響應(yīng)用戶“撤銷”或“重復(fù)”操作后，當(dāng)前內(nèi)存數(shù)據(jù)就需要恢復(fù)到特定時(shí)刻的內(nèi)存數(shù)據(jù)。要實(shí)現(xiàn)這樣的功能，顯然，在每一個(gè)時(shí)間點(diǎn)上，需要記錄反映此時(shí)內(nèi)存數(shù)據(jù)信息的相關(guān)信息（簡(jiǎn)稱為關(guān)鍵信息）。

    “時(shí)間點(diǎn)”可以根據(jù)每個(gè)軟件的具體情況，在設(shè)計(jì)的時(shí)候予以明確，一般地可以定義在增加數(shù)據(jù)，刪除數(shù)據(jù)，修改數(shù)據(jù)的時(shí)刻。下文為了便于說明，單獨(dú)使用修改的時(shí)候，“修改”的涵義包含了“增加”和“刪除”。

    以當(dāng)前狀態(tài)為分界點(diǎn)，在當(dāng)前狀態(tài)以前的各個(gè)時(shí)刻的狀態(tài)稱為過去式狀態(tài)，在當(dāng)前狀態(tài)以后的各個(gè)時(shí)刻的狀態(tài)稱為將來式狀態(tài)。在實(shí)現(xiàn)上，過去式和將來式的狀態(tài)都采用“棧”的結(jié)構(gòu)來存儲(chǔ)。

    圖1描述了在各狀態(tài)的轉(zhuǎn)換情況。

圖1   狀態(tài)變化示意圖

    歷史記錄要求有延續(xù)性，不允許在歷史中間插入一個(gè)新的狀態(tài)，因?yàn)槿绻谥虚g插入一個(gè)新的狀態(tài)，那么整個(gè)歷史記錄就是一個(gè)亂序的狀態(tài)集合，而不是一個(gè)連續(xù)的狀態(tài)集合。在修改后即有了新的狀態(tài)，而這個(gè)原來的狀態(tài)是在歷史中間的某個(gè)時(shí)間點(diǎn)上，那么新的狀態(tài)應(yīng)該怎么記錄呢？在這種情況下，只有刪除原來狀態(tài)后面的所有歷史記錄，形成一個(gè)新的歷史記錄表。

3 樹型結(jié)構(gòu)的特點(diǎn)

    樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹是n個(gè)結(jié)點(diǎn)的有限集，在一棵非空樹中有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為若干個(gè)互不相交的有限集，其中每一個(gè)集合的本身又是一棵樹，并且稱為根的子樹[1]。例如，圖2的內(nèi)容是一棵有15個(gè)結(jié)點(diǎn)的樹，其中A是根，其余結(jié)點(diǎn)分成四個(gè)互不相交的子集：T1 = {a}，T2 = {B，c，D，f，g，h}，T3 = {C，E，i，j，k}，T4 = {b}；T1、T2、T3和T4都是根A的子樹，且本身也是一棵樹。例如T2，其根為B（下文中稱呼為分支的根結(jié)點(diǎn)），其余結(jié)點(diǎn)分為三個(gè)互不相交的子集：T21 = {c}，T22 = {D，f，g，h}，T23 = si2y2m0。T21、T22、T23都是B的子樹。

圖2   樹的示例圖

    樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹稱為結(jié)點(diǎn)的度。例如圖2中，A的度為4，a的度為0。度為0的結(jié)點(diǎn)稱為葉子。結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子（又稱為子結(jié)點(diǎn)），相應(yīng)地，該節(jié)點(diǎn)成為孩子的雙親（又稱為父結(jié)點(diǎn)）。子結(jié)點(diǎn)有唯一一個(gè)父結(jié)點(diǎn)，父結(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)。

4 樹型結(jié)構(gòu)的數(shù)據(jù)恢復(fù)設(shè)計(jì)

    在“總體設(shè)計(jì)思想”一節(jié)中，描述了整體的設(shè)計(jì)思路。其中，關(guān)鍵點(diǎn)在于確定每一個(gè)“時(shí)間點(diǎn)”需要記錄的是哪些信息。
最直接的做法是把當(dāng)前時(shí)刻的所有數(shù)據(jù)信息都記錄下來，這樣回到任何時(shí)刻的狀態(tài)都不會(huì)有問題，而且，對(duì)于任何的數(shù)據(jù)結(jié)構(gòu)，都是適用的。但是，這種方式存在著明顯的缺點(diǎn)。首先，由于歷史記錄的數(shù)目大，占用了大量的內(nèi)存空間；其次，每次需要恢復(fù)大量的數(shù)據(jù)，這些附加的操作降低了程序運(yùn)行的效率。

    樹是以分支關(guān)系定義的層次結(jié)構(gòu)，根據(jù)樹型結(jié)構(gòu)的這一特點(diǎn)，可以把“關(guān)鍵信息”選擇為單個(gè)“結(jié)點(diǎn)”。

    4.1 方案的可行性

    “撤銷”、“重復(fù)”操作涉及的狀態(tài)是相鄰時(shí)刻的狀態(tài)，因此它們之間的數(shù)據(jù)有很多是一樣的，有變化的只是數(shù)據(jù)信息中的一部分，這些變化體現(xiàn)在樹型結(jié)構(gòu)上就是某一棵子樹的變化，本子樹的概念大則包括整棵樹，小則指單個(gè)葉子結(jié)點(diǎn)。子樹的根結(jié)點(diǎn)就是需要記錄的關(guān)鍵信息。

    圖3左邊是上一狀態(tài)的樹，右邊是下一狀態(tài)的樹，子樹C下的成員在當(dāng)前狀態(tài)下被刪除了。

圖3   相鄰狀態(tài)舉例

    圖3中，變化的子樹為T = {C，E，i，j，k}，其中，E、i、j、k結(jié)點(diǎn)在當(dāng)前狀態(tài)下被刪除了。在此情況下，過去式棧的棧頂成員（當(dāng)前狀態(tài)上一狀態(tài)的關(guān)鍵信息）就是結(jié)點(diǎn)C。而E、i、j、k結(jié)點(diǎn)并沒有被記錄下來，這樣如果用戶想回到圖中左邊的數(shù)據(jù)狀態(tài)，怎樣復(fù)現(xiàn)E、i、j、k采用“虛擬刪除”的方案。

    在刪除數(shù)據(jù)元素的時(shí)候，不是真正的刪除操作，如上圖中的元素E從C中刪除，那么需要切斷C與E的父、子結(jié)點(diǎn)的關(guān)系，形成兩棵獨(dú)立的樹；同時(shí)，如果內(nèi)存數(shù)據(jù)元素是可以被用戶直接操作的，需要修改元素的屬性，屏蔽這些元素達(dá)到刪除的效果。因此，在某一歷史狀態(tài)下的內(nèi)存數(shù)據(jù)可以分為：當(dāng)前可用的數(shù)據(jù)信息和當(dāng)前不可用的數(shù)據(jù)信息（虛擬刪除的信息）。

    在數(shù)據(jù)保存的時(shí)候，只需要保存當(dāng)前可用的數(shù)據(jù)信息，不需要保存已經(jīng)標(biāo)識(shí)為刪除的元素和歷史棧中的備份元素；而且保存操作之后，不需要再維持?jǐn)?shù)據(jù)恢復(fù)功能，因此，在保存之前可以把歷史棧和帶刪除標(biāo)記的元素徹底刪除。

    4.2 關(guān)鍵結(jié)點(diǎn)的查找

    在修改操作發(fā)生的時(shí)候，需要記錄新的關(guān)鍵結(jié)點(diǎn)。新的關(guān)鍵結(jié)點(diǎn)不是被操作的結(jié)點(diǎn)，而是子樹的根結(jié)點(diǎn)。

    下面從修改單個(gè)元素、多個(gè)元素不同的角度去分析關(guān)鍵結(jié)點(diǎn)的查找。前提：“修改元素的屬性”操作只適用于單個(gè)元素。

表1   各種操作的關(guān)鍵元素

    4.3 恢復(fù)過程

    恢復(fù)過程可以分為撤銷和重復(fù)兩種情況。它們共同的操作除了進(jìn)、出棧外，還包括根據(jù)出棧的元素找到當(dāng)前狀態(tài)下與之對(duì)應(yīng)的元素，完成替換操作。

    下面以接近C++的偽碼方式，描述本方案實(shí)現(xiàn)的主要算法。

    元素（結(jié)點(diǎn)）：

Class CElement
{
　　Attribute：
　　 Integer  ID；  //元素的ID號(hào)，標(biāo)識(shí)元素
Integer  parentID； //父結(jié)點(diǎn)的ID
Integer  index；  //在父結(jié)點(diǎn)的成員列表中的索引
Integer deepInTree； //元素在樹中所處的層次
CList  childIDList； //子結(jié)點(diǎn)成員列表
Bool  deleteFlag； //刪除標(biāo)志
 Method：
  GetParent()；   //得到父結(jié)點(diǎn)
  GetChild(Integer index)； //得到索引為index的子結(jié)點(diǎn)
  CopyElement()；  //備份該元素
  ShutElement()；  //屏蔽所有子元素，屏蔽的子元素需要設(shè)置deleteFlag
  ActiveElement()； //激活所有子元素，清除子元素的deleteFlag
  DeleteElement()； //虛擬刪除本元素，把子成員插入到父結(jié)點(diǎn)成員表中
}

    內(nèi)存元素表：CMap  ElementMap； //以元素ID為關(guān)鍵字，元素指針為值

    過去式棧、將來式棧：pastStack、futureStack  //存放備份的元素的指針

    約束條件：樹根結(jié)點(diǎn)是不可操作的

    算法1：尋找關(guān)鍵結(jié)點(diǎn)（本算法適合操作兩個(gè)元素；如果超過兩個(gè)元素，可以由多次兩個(gè)元素操作的疊加來完成），完成后返回關(guān)鍵結(jié)點(diǎn)的ID號(hào)。

Integer SearchBranchRoot(Integer IDOne， Integer IDTwo)
{
　　ElementMap.GetAt(IDOne，pElementOne)；
　　ElementMap.GetAt(IDTwo，pElementTwo)；
　　IF pElementOne->deepInTree = = pElementTwo->deepInTree
       IF pElementOne->parentID = = pElementTwo->ParentID
　　   RETURN pElementOne->parentID；
       ELSE
　　   RETURN SearchBranch(pElementOne->parentID，pElementTwo->parentID)；
　　ELSE
       IF pElementOne->deepInTree > pElementTwo->deepInTree
　　    RETURN SearchBranch(pElementOne->parentID，pElementTwo)；
       ELSE
　　    RETURN SearchBranch(pElementOne，pElementTwo->parentID)；
}
　　算法2：撤銷操作
　　Void Undo()
　　{
　　 pElement = pastStack.Pop()；
　　 ElementMap.GetAt(pElement.ID，pOriginal)；//找到備份元素的原型
　　 pOriginal->ShutElement()；
　　 pElement->ActiveElement()；//本條語句與上條語句的順序不可顛倒
　　 ElementMap.SetAt(pElement.ID，pElement)?；//取代
　　 futureStack.Push(pOriginal)?；
　　}
　　算法3：重復(fù)操作
　　Void Redo()
　　{
　　 pElement = futureStack.Pop()；
　　 ElementMap.GetAt(pElement.ID，pOriginal)；//找到備份元素的原型
　　 pOriginal->ShutElement()；
　　 pElement->ActiveElement()；
　　 ElementMap.SetAt(pElement.ID，pElement)?；//取代
　　 pastStack.Push(pOriginal)?；
　　}

5 結(jié)語

    本文介紹了一種樹型結(jié)構(gòu)數(shù)據(jù)恢復(fù)的方案，該方案在時(shí)間和空間上都體現(xiàn)了高效性，并成功應(yīng)用在實(shí)際的軟件開發(fā)項(xiàng)目中。
　　
參考文獻(xiàn)：

    [1] 嚴(yán)蔚敏,吳偉民等.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2002.

    [2] Donald E. Knuth，計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（影印版）[M].北京:清華大學(xué)出版社，2002.

    [3] 潘金貴（編譯）.現(xiàn)代計(jì)算機(jī)常用數(shù)據(jù)結(jié)構(gòu)和算法[M].南京：南京大學(xué)出版社，1992.