日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

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

摘要：本論文首先描述了一種數(shù)據(jù)恢復(fù)功能的總體設(shè)計思想；在此基礎(chǔ)上，根據(jù)樹型數(shù)據(jù)結(jié)構(gòu)的特點，具體化總體設(shè)計思想，設(shè)計出一套高效數(shù)據(jù)恢復(fù)功能的實現(xiàn)方案，達(dá)到時間和空間上的優(yōu)化；最后，以接近C++的偽代碼方式，描述了該方案實現(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ù)的修改、刪除和增加，而在操作的時候，用戶存在誤操作的可能，尤其是一些編輯軟件，例如微軟的word、excel等。在這種情況下，如果軟件提供數(shù)據(jù)恢復(fù)的功能，用戶將可以十分方便的通過此功能使數(shù)據(jù)回到歷史的某個狀態(tài)。

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

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

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

2 總體設(shè)計思想

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

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

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

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

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

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

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

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

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

    樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹是n個結(jié)點的有限集，在一棵非空樹中有且僅有一個特定的稱為根的結(jié)點；其余結(jié)點可分為若干個互不相交的有限集，其中每一個集合的本身又是一棵樹，并且稱為根的子樹[1]。例如，圖2的內(nèi)容是一棵有15個結(jié)點的樹，其中A是根，其余結(jié)點分成四個互不相交的子集：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é)點），其余結(jié)點分為三個互不相交的子集：T21 = {c}，T22 = {D，f，g，h}，T23 = op7lbvq。T21、T22、T23都是B的子樹。

圖2   樹的示例圖

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

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

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

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

    4.1 方案的可行性

    “撤銷”、“重復(fù)”操作涉及的狀態(tài)是相鄰時刻的狀態(tài)，因此它們之間的數(shù)據(jù)有很多是一樣的，有變化的只是數(shù)據(jù)信息中的一部分，這些變化體現(xiàn)在樹型結(jié)構(gòu)上就是某一棵子樹的變化，本子樹的概念大則包括整棵樹，小則指單個葉子結(jié)點。子樹的根結(jié)點就是需要記錄的關(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é)點在當(dāng)前狀態(tài)下被刪除了。在此情況下，過去式棧的棧頂成員（當(dāng)前狀態(tài)上一狀態(tài)的關(guān)鍵信息）就是結(jié)點C。而E、i、j、k結(jié)點并沒有被記錄下來，這樣如果用戶想回到圖中左邊的數(shù)據(jù)狀態(tài)，怎樣復(fù)現(xiàn)E、i、j、k采用“虛擬刪除”的方案。

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

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

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

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

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

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

    4.3 恢復(fù)過程

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

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

    元素（結(jié)點）：

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

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

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

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

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

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ù)的方案，該方案在時間和空間上都體現(xiàn)了高效性，并成功應(yīng)用在實際的軟件開發(fā)項目中。
　　
參考文獻(xiàn)：

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

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

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