2015年2月9日 星期一

C# Design Pattern - Template Method Pattern 範本方法模式

Template Method Pattern定義了一個演算法的步驟,並允許次類別為一個或多個步驟提供其實踐方式。讓次類別在不改變演算法架構的情況下,重新定義演算法中的某些步驟。 

架構是準備一個抽象類別,將部分邏輯以具體方法以及具體構造子的形式實現,然後聲明一些抽象方法來迫使子類實現剩餘的邏輯。不同的子類可以以不同的方式實現這些抽象方法,從而對剩餘的邏輯有不同的實現。這就是模版方法模式的用意。
其實,Template Method Pattern實際上是所有模式中最為常見的幾個模式之一。Template Method Pattern是基於繼承的代碼複用的基本技術,Template Method Pattern的結構和用法也是物件導向設計的核心。
Template Method需要開發抽象類別和具體子類的設計師之間的協作。一個設計師負責給出一個演算法的輪廓和骨架,另一些設計師則負責給出這個演算法的各個邏輯步驟。代表這些具體邏輯步驟的方法稱做基本方法(primitive method);而將這些基本法方法總匯起來的方法叫做模版方法(template method)。

模版方法模式的結構

模版方法模式的靜態結構如下圖所示:


應用場景
  1. 某些類別的演算法中,實做了相同的方法,造成程式碼的重複。
  2. 控制子類別必須遵守的一些事項。
  3. ASP.NET的BasePage。
  4. WinForm的BaseForm。


模式特色
  1. 將子類別共用的部分, 提到父類別。
  2. 使用虛擬方法隔離非共同部分。


解決問題的方式是減少子類別共用的程式碼,如下面範例:

using System.IO;
using System;

class Program
{
    static void Main()
    {
        // Start Here
        BasePage page;

        page = new Page1();
        page.TemplateMethod();

        Console.WriteLine("------------------------------");

        page = new Page2();
        page.TemplateMethod();

        // Keep Screen
        Console.ReadLine();
    }

}

// Template 範本
abstract class BasePage
{
    public abstract bool Create();
    public abstract bool Update();

    public void TemplateMethod()
    {
        Console.WriteLine("Page Start with no error!");
        Console.WriteLine("Create Button Click");
        Create();
        Console.WriteLine("Update Button Click");
        Update();
        Console.WriteLine("");
    }
}

// Concrete 具體
class Page1 : BasePage
{
    public override bool Create()
    {
        Console.WriteLine("Page1(Order) Create Date");
        return true;
    }
    public override bool Update()
    {
        Console.WriteLine("Page1(Order) Update Date");
        return true;
    }
}

class Page2 : BasePage
{
    public override bool Create()
    {
        Console.WriteLine("Page2(PurchaseOrder) Create Date");
        return true;
    }
    public override bool Update()
    {
        Console.WriteLine("Page2(PurchaseOrder) Update Date");
        return true;
    }


}
 
這裡涉及到兩個角色:

抽象模版AbstractClass):
定義了一個或多個抽象操作,以便讓子類實現。這些抽象操作叫做基本操作,它們是一個頂級邏輯的組成步驟。

定義並實現了一個模版方法。這個模版方法一般是一個具體方法,它給出了一個頂級邏輯的骨架,而邏輯的組成步驟在相應的抽象操作中,推遲到子類實現。頂級邏輯也有可能調用一些具體方法。

具體模版ConcreteClass):
實現父類所定義的一個或多個抽象方法,它們是一個頂級邏輯的組成步驟。
每一個Template Method角色都可以有任意多個具體模版角色與之對應,而每一個具體模版角色都可以給出這些抽象方法(也就是頂級邏輯的組成步驟)的不同實現,從而使得頂級邏輯的實現各不相同。

下面程式範例:

// Template Method pattern -- Structural example
using System;

abstract class AbstractClass
{
    abstract public void PrimitiveOperation1();
    abstract public void PrimitiveOperation2();

    public void TemplateMethod()
    {
        Console.WriteLine("In AbstractClass.TemplateMethod()");
        PrimitiveOperation1();
        PrimitiveOperation2();
    }
}

class ConcreteClass : AbstractClass
{
    // Methods
    public override void PrimitiveOperation1()
    {
        Console.WriteLine("Called ConcreteClass.PrimitiveOperation1()");
    }

    public override void PrimitiveOperation2()
    {
        Console.WriteLine("Called ConcreteClass.PrimitiveOperation2()");
    }
}

/// <summary>
/// Client 測試
/// </summary>
public class Client
{
    public static void Main(string[] args)
    {
        ConcreteClass c = new ConcreteClass();
        c.TemplateMethod();
    }


}

使用繼承作為複用的手段必須慎重,C#語言的設計師對使用繼承作為複用的工具有著不同層次上的認識。

首先,初學C#的程式師可能不知道什麼是繼承,或者認為"繼承"是高深的方法。那時候,大部分的功能複用都是通過委派進行的。

然後慢慢地,他們發現在C#語言裡實現繼承並不困難,並且初步認識到繼承可以使子類一下子得到基類的行為。這時他們就會躍躍欲試了,試圖使用繼承作為功能複用的主要工具,並把原來應當使用委派的地方,改為使用繼承,這時繼承就有被濫用的危險。

很多物件導向的設計專家從1986年就開始警告繼承關係被濫用的可能。有一些物件導向的程式設計語言,如SELF語言,甚至將類的繼承關係從語言的功能中取消掉,改為完全使用委派。

其他的設計師雖然不提倡徹底取消繼承,大部分都鼓勵在設計中盡可能使甩委派關係代替繼承關係。比如狀態模式、策略模式、裝飾模式、Bridge Pattern以及Abstract Factory Pattern均是將依賴在繼承的實現轉換為基於物件的組合和聚合的實現,這些模式的要點就是使用委派關係代替繼承關係。

資料的抽象化、繼承、封裝和多態性並稱C#和其他絕大多數的物件導向語言的幾項最重要的特性。繼承不應當被濫用,並不意味著繼承根本就不該使用。因為繼承容易被濫用就徹底拋棄繼承。

繼承使得類型的等級結構易於理解、維護和擴展,而類型的等級結構非常適合於抽象化的設計、實現和複用。很多模式都是用繼承的辦法定義、實現介面的。多數的Design Pattern都描寫一個以抽象類別作為基類,以具體類作為實現的等級結構,比如Iterator PatternComposite PatternBridge PatternState Pattern等。

Template Method Pattern則更進了一步:此模式鼓勵恰當地使用繼承。此模式可以用來改寫一些擁有相同功能的相關的類,將可複用的一般性的行為代碼移到基類裡面,而把特殊化的行為代碼移到子類裡面。因此,熟悉模版方法模式便成為一個重新學習繼承的好地方。

下面的例子演示了資料庫訪問的範本方法。實際應用時,請確保C目錄下有nwind.mdb這個Access資料庫(可以從Office的安裝目錄下找到。中文版用戶的請注意欄位名可能有所不同)。

// Template Method pattern -- Real World example
using System;
using System.Data;
using System.Data.OleDb;

// "AbstractClass"
abstract class DataObject
{
    // Methods
    abstract public void Connect();
    abstract public void Select();
    abstract public void Process();
    abstract public void Disconnect();

    // The "Template Method"
    public void Run()
    {
        Connect();
        Select();
        Process();
        Disconnect();
    }
}

// "ConcreteClass"
class CustomerDataObject : DataObject
{
    private string connectionString =
        "provider=Microsoft.JET.OLEDB.4.0; "
        + "data source=c:\\nwind.mdb";
    private string commandString;
    private DataSet dataSet;

    public override void Connect()
    {
        // Nothing to do
    }

    public override void Select()
    {
        commandString = "select CompanyName from Customers";
        OleDbDataAdapter dataAdapter = new OleDbDataAdapter(
        commandString, connectionString);
        dataSet = new DataSet();
        dataAdapter.Fill(dataSet, "Customers");
    }

    public override void Process()
    {
        DataTable dataTable = dataSet.Tables["Customers"];
        foreach (DataRow dataRow in dataTable.Rows)
            Console.WriteLine(dataRow["CompanyName"]);
    }

    public override void Disconnect()
    {
        // Nothing to do
    }
}

/// <summary>
///  TemplateMethodApp test
/// </summary>
public class TemplateMethodApp
{
    public static void Main(string[] args)
    {
        CustomerDataObject c = new CustomerDataObject();
        c.Run();
    }
}


六、 模版方法模式中的方法
模版方法中的方法可以分為兩大類:模版方法(Template Method)和基本方法(Primitive Method)

模版方法
一個模版方法是定義在抽象類別中的,把基本操作方法組合在一起形成一個總算法或一個總行為的方法。這個模版方法一般會在抽象類別中定義,並由子類不加以修改地完全繼承下來。

基本方法
基本方法又可以分為三種:抽象方法(Abstract Method)、具體方法(Concrete Method)和鉤子方法(Hook Method)。

  • 抽象方法:一個抽象方法由抽象類別聲明,由具體子類實現。在C#語言裡一個抽象方法以abstract關鍵字標示出來。
  • 具體方法:一個具體方法由抽象類別聲明並實現,而子類並不實現或置換。在C#語言裡面,一個具體方法沒有abstract關鍵字。
  • 鉤子方法:一個鉤子方法由抽象類別聲明並實現,而子類會加以擴展。通常抽象類別給出的實現是一個空實現,作為方法的默認實現。(Visual FoxPro中項目嚮導建立的項目會使用一個AppHook類實現監視專案成員變化,調整系統結構的工作。)鉤子方法的名字通常以do開始。

在對一個繼承的等級結構做重構時,一個應當遵從的原則便是將行為儘量移動到結構的高端,而將狀態儘量移動到結構的低端。一個類的實現首先建立在行為的基礎之上,而不是建立在狀態的基礎之上。

在實現行為時,是用抽象狀態而不是用具體狀態。如果一個行為涉及到物件的狀態時,使用間接的引用而不是直接的引用。換言之,應當使用取值方法而不是直接引用屬性。

給操作劃分層次。一個類的行為應當放到一個小組核心方法(Kernel Methods)裡面,這些方法可以很方便地在子類中加以置換。

將狀態屬性的確認推遲到子類中。不要在抽象類別中過早地聲明屬性變數,應將它們儘量地推遲到子類中去聲明。在抽象超類中,如果需要狀態屬性的話,可以調用抽象的取值方法,而將抽象的取值方法的實現放到具體子類中。
如果能夠遵從這樣的原則,那麼就可以在等級結構中將介面與實現分隔開來,將抽象與具體分割開來,從而保證代碼可以最大限度地被覆用。這個過程實際上是將設計師引導到模版方法模式上去。

-雲遊山水為知已逍遙一生而忘齡- 電腦神手

解決unable to find Webclass.vstemplate的問題

應該在用Visual Studio開發時,都會有可能遇到下面的情況:

unable to find C:\Program Files (x86)\Microsoft Visual Studio 10.0\Common7\IDE\ItemTemplatesCache\CSharp\Web\1033\Webclass.vstemplate


其實這種情況,有許多的可能,可能用了什麼清理的軟體,所以在此不了解原因,直接在了解如何處理這情況。

開啟 visual studio command prompt(如果是Win7 / Win8建議要以管理員身份執行),然後執行下面的命令:

devenv /installvstemplates

這樣應該就會解決此問題。

-雲遊山水為知已逍遙一生而忘齡- 電腦神手

2015年2月2日 星期一

C# - 二元搜索樹演算法概念Binary Search Tree

二元搜索樹是一種二元樹,給定某個排序函數,比如 < ,每個元素的左子樹都 < 該元素,而該元素 < 其右子樹。圖 下展示了根據 < 排序的二元樹。


(Tree)是由一些有連結的節點(node)組成,且架構如下:
1.有一個特別的節點叫做根節點(root)
2.除了root以外剩下的節點被分成 個相互獨立的點集合,每一個集合都構成樹。我們稱這些樹為根節點的子樹(node subtree),每個子樹的根節點被稱為子節點(Child)
換個方法定義,樹(Tree)是一個連通的圖(graph),兩點之間恰有一條路徑可達。此外,一個節點的度數(degree)就是這個節點的子節點個數。整棵樹的度數N也就定義為所有節點度數的最大值,此時定義這棵樹是個N元樹。森林(Forest)是許多樹的聯集。

樹的表示式
除了把Tree圖畫出來以外(這樣太佔空間了),我們可以用一個List列出來。如由上方的圖我們可以用括弧表示每個子樹,因此整棵樹列出來像這樣:
(1 (2 (4 (5, 6(7))), 3))
每一個node可以表示成如下:
data link 1       link 2       …     link 

但是這樣會有浪費記憶體的可能,所以我們考慮用另一種表示方法,讓這棵樹或是森林轉換成二元樹。這樣每個node只要記錄最多兩個link就好了。在此之前我們先介紹最重要的樹狀結構:二元樹(Binary Trees)

二元樹的每個節點至多有兩個子節點,且有分左右。下面以一個節點的結構可表示如下:


然後用C#呈現的範例:

1.先定義節點物件
public class BinaryTreeNode
{
    public BinaryTreeNode Left { get; set; }

    public BinaryTreeNode Right { get; set; }

    public int Data { get; set; }
    public BinaryTreeNode(int data)
    {
        this.Data = data;
    }
}

2.使用節點物件來建立二元樹
BinaryTreeNode nodeRoot = new BinaryTreeNode("A")
    {

        Left = new BinaryTreeNode("B")
        {

            Left = new BinaryTreeNode("D")
            {
                Left = new BinaryTreeNode("G"),
                Right = null
            },
            Right = new BinaryTreeNode("E")
            {
                Left = new BinaryTreeNode("H"),
                Right = new BinaryTreeNode("I")
            }
        },
        Right = new BinaryTreeNode("C")
        {
            Left = null,
            Right = new BinaryTreeNode("F")
        }
    };

3.前序訪問
Action<string> printValue = delegate(string v)
            {
                Console.Write(v + " ");
            };
    PreOrderTraversal(printValue, nodeRoot);


public static void PreOrderTraversal(Action<string> action, BinaryTreeNode root)
{
    if (root == nullreturn;

    action(root.Data);
    PreOrderTraversal(action, root.Left);
    PreOrderTraversal(action, root.Right);
}

4.中序訪問
Action<string> printValue = delegate(string v)
            {
                Console.Write(v + " ");
            };

InOrderTraversal(printValue, nodeRoot);

public static void InOrderTraversal(Action<string> action, BinaryTreeNode root)
{
    if (root == nullreturn;

    InOrderTraversal(action, root.Left);
    action(root.Data);
    InOrderTraversal(action, root.Right);
}

5.後序訪問
Action<string> printValue = delegate(string v)
    {
        Console.Write(v + " ");
    };
    PostOrderTraversal(printValue, nodeRoot);

public static void PostOrderTraversal(Action<string> action, BinaryTreeNode root)
{
    if (root == null) return;
    PostOrderTraversal(action, root.Left);
    PostOrderTraversal(action, root.Right);
    action(root.Data);
}
二元樹的走訪
因為要直接表示一棵二元樹有些困難,所以我們以某些特定順序探訪這棵樹,所得的序列就是這棵樹的資料。
前序表示法preorderroot, left-subtree, right-subtree
中序表示法inorderleft-subtree, root, right-subtree
後序表示法postorderleft-subtree, right-subtree, root
【題2】給定二元樹的preorder以及postorder,求inorder

將一般的TreeForest化簡為Binary Tree,有一種常用的方法Left-Child-Right-Sibling:也就是將所有節點重新定義,其左子節點仍為此節點的左子節點,右子節點定義為這個節點的右邊兄弟。

二元搜尋樹(Binary Search Tree)
Binary Search TreeBST)是一個二進制樹(最多每節點2兒童的)與每一個節點Key和相關聯的值。還一個BST具有為每個節點,左子樹僅包含具有較小(或相等)的關鍵節點和右子樹包含有嚴格較大密鑰僅節點的屬性。此屬性將讓我們在時間成正比,樹高進行插入和刪除操作。後來更多的時間複雜度。\

對於陣列來說,要查找一筆資料用二分搜尋法可以在 時間內達成,但是如果現在的資料結構不是陣列呢?假設這些資料分散在記憶體中,那麼只要建立二元搜尋樹(BST)的結構,平均只要 的時間就可以新增、查找資料。BST是一個二元樹,並滿足以下條件:對於任意節點SS的左子樹的所有節點的鍵值不大於S的鍵值,S的右子樹的所有節點的鍵值不小於S的鍵值。

堆積heap
堆積是一種二元樹。其最大的特點為每個節點的鍵值永遠比左子節點或右子節點上的鍵值小(或大)。這樣可每次以 取得最小值(或最大值),然後用 的時間整理heap,對於動態資料的處理相當方便。

BST類被聲明如下:

public class BinarySearchTree<Tkey, Tvalue> where Tkey : IComparable<Tkey>

BST的節點可以由任何類型實現IComparable被鍵入。對所用的值的類型沒有限制。簡單的節點定義範例:

protected class BinaryKeyValueNode<Tkey, Tvalue> where Tkey : IComparable<Tkey> 
    public Tkey Key { get; set; } 
    public Tvalue Value { get; set; } 
    public BinaryKeyValueNode<Tkey, Tvalue> Parent { get; set; } 
    public BinaryKeyValueNode<Tkey, Tvalue> LeftChild { get; set; } 
    public BinaryKeyValueNode<Tkey, Tvalue> RightChild { get; set; } 
    public BinaryKeyValueNode(Tkey key, Tvalue value) 
    { 
        Value = value; 
        Key = key; 
    } 
}

所以,每個節點由一個鍵和一個值,並保持一個參考子樹均(子節點)和其父。這些字段和建構的BST
private Random random;
protected BinaryKeyValueNode<Tkey, Tvalue> Root { get; set; }
public int Count { get; protected set; }
public BinarySearchTree() 
{
    Root = null
    random = new Random(1); 
    Count = 0; 
}

我們維持計數(可選)和參考根節點(最初為null)。
插入的內容如下:
public void Insert(Tkey key, Tvalue value) 
    BinaryKeyValueNode<Tkey, Tvalue> parent = null
    BinaryKeyValueNode<Tkey, Tvalue> current = Root; 
    int compare = 0; 
    while (current != null
    {
        parent = current; 
        compare = current.Key.CompareTo(key); 
        current = compare < 0 ? current.RightChild : current.LeftChild; 
    }
    BinaryKeyValueNode<Tkey, Tvalue> newNode = new BinaryKeyValueNode<Tkey, Tvalue>(key, value); 
    if (parent != null
        if (compare < 0) 
            parent.RightChild = newNode; 
        else 
            parent.LeftChild = newNode; 
    else 
        Root = newNode; 
    newNode.Parent = parent; 
    Count++; 
}

Reference current是我們嘗試插入和家長是當前子樹的父的子樹。只要當前指向的節點(第6行),我們不論向左或向右,根據當前節點的鍵和鍵,我們要在插入的值之間做比較。如果當前的key是我們要插入比右子樹的key更好,否則會到左側(10號線)。當我們已經達到了一個外部節點,Reference current將等於null。現在,我們建立了新節點並設置了所有正確的引用(線12-20)。

找到一個值,由於其主要的,工作方式非常相同,範例如下:

public Tvalue FindFirst(Tkey key) 
    return FindNode(key).Value; 
 
public Tvalue FindFirstOrDefault(Tkey key) 
    var node=FindNode(key, false); 
    return node == null ? default(Tvalue) : node.Value; 
 
protected BinaryKeyValueNode<Tkey, Tvalue> FindNode(Tkey key, bool ExceptionIfKeyNotFound = true
    BinaryKeyValueNode<Tkey, Tvalue> current = Root; 
    while (current != null
    { 
        int compare = current.Key.CompareTo(key); 
        if (compare == 0) 
            return current; 
        if (compare < 0) 
            current = current.RightChild; 
        else 
            current = current.LeftChild; 
    } 
    if (ExceptionIfKeyNotFound) 
        throw new KeyNotFoundException(); 
    else 
        return null
}

root開始,我們比較這賦予key到當前節點的key。如果它們相等,就可以將其返回。如果這賦予key是完全地較大,我們繼續在右子樹的搜索,不然就在左側。接下來我們刪除操作:

protected void DeleteNode(BinaryKeyValueNode<Tkey, Tvalue> node) 
    if (node == null
        throw new ArgumentNullException(); 
    if (node.LeftChild != null && node.RightChild != null) //2 childs 
    { 
        BinaryKeyValueNode<Tkey, Tvalue> replaceBy = random.NextDouble() > .5 ? InOrderSuccesor(node) : InOrderPredecessor(node); 
        DeleteNode(replaceBy); 
        node.Value = replaceBy.Value; 
        node.Key = replaceBy.Key; 
    } 
    else //1 or less childs 
    { 
        var child = node.LeftChild == null ? node.RightChild : node.LeftChild; 
        if (node.Parent.RightChild == node) 
            node.Parent.RightChild = child; 
        else 
            node.Parent.LeftChild = child; 
    } 
    Count--; 
 
protected BinaryKeyValueNode<Tkey, Tvalue> InOrderSuccesor(BinaryKeyValueNode<Tkey, Tvalue> node) 
    BinaryKeyValueNode<Tkey, Tvalue> succesor = node.RightChild; 
    while (succesor.LeftChild != null
        succesor = succesor.LeftChild; 
    return succesor; 
 
protected BinaryKeyValueNode<Tkey, Tvalue> InOrderPredecessor(BinaryKeyValueNode<Tkey, Tvalue> node) 
    BinaryKeyValueNode<Tkey, Tvalue> succesor = node.LeftChild; 
    while (succesor.RightChild != null
        succesor = succesor.RightChild; 
    return succesor;
}

一個節點的缺失很容易造成,如果有零個或一個child。我們可以只連接parentchild ,忘了刪除節點(行12-18)。該BST屬性將仍持有。如果需要刪除節點有2名兒童,那麼我們就需要找到一個合適的節點來代替它由要么是在右子樹的最低鍵(按順序後繼)的節點,或者與節點在左子樹(在階前身)的最高鍵(行5-11)。我們決定哪一個有coinflip
現在我們都必須在BST完成基本操作。假設要traversal整個樹狀結構,列舉的所有元素,其實有多種方法可以做到這一點,即depth-firstbreadth-first。下面是執行所有3種方式進行depth-first traversal


public IEnumerable<Tvalue> TraverseTree(DepthFirstTraversalMethod method) 
    return TraverseNode(Root, method); 
 
protected IEnumerable<Tvalue> TraverseNode(BinaryKeyValueNode<Tkey, Tvalue> node, DepthFirstTraversalMethod method) 
    IEnumerable<Tvalue> TraverseLeft = node.LeftChild == null ? new Tvalue[0] : TraverseNode(node.LeftChild, method), 
        TraverseRight = node.RightChild == null ? new Tvalue[0] : TraverseNode(node.RightChild, method), 
        Self = new Tvalue[1] { node.Value }; 
    switch(method) 
    { 
        case DepthFirstTraversalMethod.PreOrder: 
            return Self.Concat(TraverseLeft).Concat(TraverseRight); 
        case DepthFirstTraversalMethod.InOrder: 
            return TraverseLeft.Concat(Self).Concat(TraverseRight); 
        case DepthFirstTraversalMethod.PostOrder: 
            return TraverseLeft.Concat(TraverseRight).Concat(Self); 
        default
            throw new ArgumentException(); 
    }             
 
public enum DepthFirstTraversalMethod 
    PreOrder, 
    InOrder, 
    PostOrder 
}

上面的深度討論,是透過C#產生的一種子樹搜尋的演算。BST在資料結構中佔有很重要的地位,一些高級樹結構都是其的變種,例如AVL樹、紅黑樹等,因此理解BST對於後續樹結構的學習有很好的作用。同時利用BST可以進行排序,稱為二叉排序,也是很重要的一種思想。

-雲遊山水為知已逍遙一生而忘齡- 電腦神手