国产欧美日韩精品a在线观看-国产欧美日韩精品一区二区三区-国产欧美日韩精品综合-国产欧美中文字幕-一区二区三区精品国产-一区二区三区精品国产欧美

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

摘要：本論文首先描述了一種數據恢復功能的總體設計思想；在此基礎上，根據樹型數據結構的特點，具體化總體設計思想，設計出一套高效數據恢復功能的實現方案，達到時間和空間上的優化；最后，以接近C++的偽代碼方式，描述了該方案實現的部分算法。

關鍵詞：樹型結構；數據恢復；撤銷；重復

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 引言

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

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

    為此，對樹型結構數據恢復功能的探討是很有意義的。

    下文首先描述了一個可行的比較通用的數據恢復設計思想，在此基礎上，分析樹型數據結構的特點，設計出一套針對樹型數據結構的高效數據恢復方案。

2 總體設計思想

    實現數據恢復的前提是記錄各個時刻的歷史信息，即各個時刻的數據；然后，在必要的時候響應“撤銷”、“重復”的命令，實現歷史的無損復現。

    從“撤銷、重復”操作的角度，可以把不同時間點的內存數據信息劃分為三個狀態：過去式、當前、將來式。

    在每一個時間點上都有其對應的數據信息。在響應用戶“撤銷”或“重復”操作后，當前內存數據就需要恢復到特定時刻的內存數據。要實現這樣的功能，顯然，在每一個時間點上，需要記錄反映此時內存數據信息的相關信息（簡稱為關鍵信息）。

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

    以當前狀態為分界點，在當前狀態以前的各個時刻的狀態稱為過去式狀態，在當前狀態以后的各個時刻的狀態稱為將來式狀態。在實現上，過去式和將來式的狀態都采用“棧”的結構來存儲。

    圖1描述了在各狀態的轉換情況。

圖1   狀態變化示意圖

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

3 樹型結構的特點

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

圖2   樹的示例圖

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

4 樹型結構的數據恢復設計

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

    樹是以分支關系定義的層次結構，根據樹型結構的這一特點，可以把“關鍵信息”選擇為單個“結點”。

    4.1 方案的可行性

    “撤銷”、“重復”操作涉及的狀態是相鄰時刻的狀態，因此它們之間的數據有很多是一樣的，有變化的只是數據信息中的一部分，這些變化體現在樹型結構上就是某一棵子樹的變化，本子樹的概念大則包括整棵樹，小則指單個葉子結點。子樹的根結點就是需要記錄的關鍵信息。

    圖3左邊是上一狀態的樹，右邊是下一狀態的樹，子樹C下的成員在當前狀態下被刪除了。

圖3   相鄰狀態舉例

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

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

    在數據保存的時候，只需要保存當前可用的數據信息，不需要保存已經標識為刪除的元素和歷史棧中的備份元素；而且保存操作之后，不需要再維持數據恢復功能，因此，在保存之前可以把歷史棧和帶刪除標記的元素徹底刪除。

    4.2 關鍵結點的查找

    在修改操作發生的時候，需要記錄新的關鍵結點。新的關鍵結點不是被操作的結點，而是子樹的根結點。

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

表1   各種操作的關鍵元素

    4.3 恢復過程

    恢復過程可以分為撤銷和重復兩種情況。它們共同的操作除了進、出棧外，還包括根據出棧的元素找到當前狀態下與之對應的元素，完成替換操作。

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

    元素（結點）：

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

    內存元素表：CMap  ElementMap； //以元素ID為關鍵字，元素指針為值

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

    約束條件：樹根結點是不可操作的

    算法1：尋找關鍵結點（本算法適合操作兩個元素；如果超過兩個元素，可以由多次兩個元素操作的疊加來完成），完成后返回關鍵結點的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：重復操作
　　Void Redo()
　　{
　　 pElement = futureStack.Pop()；
　　 ElementMap.GetAt(pElement.ID，pOriginal)；//找到備份元素的原型
　　 pOriginal->ShutElement()；
　　 pElement->ActiveElement()；
　　 ElementMap.SetAt(pElement.ID，pElement)?；//取代
　　 pastStack.Push(pOriginal)?；
　　}

5 結語

    本文介紹了一種樹型結構數據恢復的方案，該方案在時間和空間上都體現了高效性，并成功應用在實際的軟件開發項目中。
　　
參考文獻：

    [1] 嚴蔚敏,吳偉民等.數據結構[M].北京：清華大學出版社，2002.

    [2] Donald E. Knuth，計算機程序設計藝術（影印版）[M].北京:清華大學出版社，2002.

    [3] 潘金貴（編譯）.現代計算機常用數據結構和算法[M].南京：南京大學出版社，1992.