莊周夢蝶

??? 放假這幾天，喝了很多酒，讀完一本書，想念一個人，花了不少錢
????3月1號上班了，明天提前出發去適應氣候（見鬼，明明是想MM嘛......），昨天在china-pub上訂的書也到了。計劃下最近的學習計劃，把3本書掃尾：《javascript高級程序設計》剩下兩章，《數據結構與算法》排序和圖論還沒讀完，另外有空再有選擇地重讀一遍《設計模式》。用ruby重寫osworkflow，開始寫吧，不知道能不能寫出來

1。概念：堆是一種特殊的二叉樹，具備以下兩種性質
1）每個節點的值都大于（或者都小于，稱為最小堆）其子節點的值
2）樹是完全平衡的，并且最后一層的樹葉都在最左邊
這樣就定義了一個最大堆。

2。堆可以用一個數組表示，有如下性質：
heap[i]>=heap[2*i+1]? 其中0<=i<=(n-1)/2
heap[i]>=heap[2*i+2]? 其中0<=i<=(n-2)/2

3。用數組實現堆，
1）插入操作
自頂向下，偽代碼：

自底向上，偽代碼：
??
2)moveDown的方法實現，此方法是堆排序的關鍵，也是刪除操作的關鍵。刪除操作，將根節點刪除，并把最末的樹葉換到根節點，通過moveDown方法找到正確的位置，恢復堆性質。

4。堆的一個實現：

// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;
////////////////////////////////////////////////////////////////
class Node
   {
   private int iData;             // data item (key)
// -------------------------------------------------------------
   public Node(int key)           // constructor
      { iData = key; }
// -------------------------------------------------------------
   public int getKey()
      { return iData; }
// -------------------------------------------------------------
   public void setKey(int id)
      { iData = id; }
// -------------------------------------------------------------
   }  // end class Node
////////////////////////////////////////////////////////////////
class Heap
   {
   private Node[] heapArray;
   private int maxSize;           // size of array
   private int currentSize;       // number of nodes in array
// -------------------------------------------------------------
   public Heap(int mx)            // constructor
      {
      maxSize = mx;
      currentSize = 0;
      heapArray = new Node[maxSize];  // create array
      }
// -------------------------------------------------------------
   public boolean isEmpty()
      { return currentSize==0; }
// -------------------------------------------------------------
   public boolean insert(int key)
      {
      if(currentSize==maxSize)
         return false;
      Node newNode = new Node(key);
      heapArray[currentSize] = newNode;
      trickleUp(currentSize++);
      return true;
      }  // end insert()
// -------------------------------------------------------------
   public void trickleUp(int index)
      {
      int parent = (index-1) / 2;
      Node bottom = heapArray[index];

      while( index > 0 &&
             heapArray[parent].getKey() < bottom.getKey() )
         {
         heapArray[index] = heapArray[parent];  // move it down
         index = parent;
         parent = (parent-1) / 2;
         }  // end while
      heapArray[index] = bottom;
      }  // end trickleUp()
// -------------------------------------------------------------
   public Node remove()           // delete item with max key
      {                           // (assumes non-empty list)
      Node root = heapArray[0];
      heapArray[0] = heapArray[--currentSize];
      trickleDown(0);
      return root;
      }  // end remove()
// -------------------------------------------------------------
   public void trickleDown(int index)
      {
      int largerChild;
      Node top = heapArray[index];       // save root
      while(index < currentSize/2)       // while node has at
         {                               //    least one child,
         int leftChild = 2*index+1;
         int rightChild = leftChild+1;
                                         // find larger child
         if(rightChild < currentSize &&  // (rightChild exists?)
                             heapArray[leftChild].getKey() <
                             heapArray[rightChild].getKey())
            largerChild = rightChild;
         else
            largerChild = leftChild;
                                         // top >= largerChild?
         if( top.getKey() >= heapArray[largerChild].getKey() )
            break;
                                         // shift child up
         heapArray[index] = heapArray[largerChild];
         index = largerChild;            // go down
         }  // end while
      heapArray[index] = top;            // root to index
      }  // end trickleDown()
// -------------------------------------------------------------
   public boolean change(int index, int newValue)
      {
      if(index<0 || index>=currentSize)
         return false;
      int oldValue = heapArray[index].getKey(); // remember old
      heapArray[index].setKey(newValue);  // change to new

      if(oldValue < newValue)             // if raised,
         trickleUp(index);                // trickle it up
      else                                // if lowered,
         trickleDown(index);              // trickle it down
      return true;
      }  // end change()
// -------------------------------------------------------------
   public void displayHeap()
      {
      System.out.print("heapArray: ");    // array format
      for(int m=0; m<currentSize; m++)
         if(heapArray[m] != null)
            System.out.print( heapArray[m].getKey() + " ");
         else
            System.out.print( "-- ");
      System.out.println();
                                          // heap format
      int nBlanks = 32;
      int itemsPerRow = 1;
      int column = 0;
      int j = 0;                          // current item
      String dots = "...............................";
      System.out.println(dots+dots);      // dotted top line

      while(currentSize > 0)              // for each heap item
         {
         if(column == 0)                  // first item in row?
            for(int k=0; k<nBlanks; k++)  // preceding blanks
               System.out.print(' ');
                                          // display item
         System.out.print(heapArray[j].getKey());

         if(++j == currentSize)           // done?
            break;

         if(++column==itemsPerRow)        // end of row?
            {
            nBlanks /= 2;                 // half the blanks
            itemsPerRow *= 2;             // twice the items
            column = 0;                   // start over on
            System.out.println();         //    new row
            }
         else                             // next item on row
            for(int k=0; k<nBlanks*2-2; k++)
               System.out.print(' ');     // interim blanks
         }  // end for
      System.out.println("/n"+dots+dots); // dotted bottom line
      }  // end displayHeap()
// -------------------------------------------------------------
   }  // end class Heap
////////////////////////////////////////////////////////////////
class HeapApp
   {
   public static void main(String[] args) throws IOException
      {
      int value, value2;
      Heap theHeap = new Heap(31);  // make a Heap; max size 31
      boolean success;

      theHeap.insert(70);           // insert 10 items
      theHeap.insert(40);
      theHeap.insert(50);
      theHeap.insert(20);
      theHeap.insert(60);
      theHeap.insert(100);
      theHeap.insert(80);
      theHeap.insert(30);
      theHeap.insert(10);
      theHeap.insert(90);

      while(true)                   // until [Ctrl]-[C]
         {
         System.out.print("Enter first letter of ");
         System.out.print("show, insert, remove, change: ");
         int choice = getChar();
         switch(choice)
            {
            case 's':                        // show
               theHeap.displayHeap();
               break;
            case 'i':                        // insert
               System.out.print("Enter value to insert: ");
               value = getInt();
               success = theHeap.insert(value);
               if( !success )
                  System.out.println("Can't insert; heap full");
               break;
            case 'r':                        // remove
               if( !theHeap.isEmpty() )
                  theHeap.remove();
               else
                  System.out.println("Can't remove; heap empty");
               break;
            case 'c':                        // change
               System.out.print("Enter current index of item: ");
               value = getInt();
               System.out.print("Enter new key: ");
               value2 = getInt();
               success = theHeap.change(value, value2);
               if( !success )
                  System.out.println("Invalid index");
               break;
            default:
               System.out.println("Invalid entry/n");
            }  // end switch
         }  // end while
      }  // end main()
//-------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
//-------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
//-------------------------------------------------------------
  }  // end class HeapApp
////////////////////////////////////////////////////////////////

樹的平衡，我們已經知道DWL算法，不過DWL算法需要從整體上平衡樹，但是樹的平衡也可以局部的進行，由Adel'son-Vel'skii-Landis提出了一種經典方法，稱為AVL樹。

1。概念：AVL樹，或者說可適應樹，是指樹中每個節點的的平衡因子的絕對值不大于1，即只能為-1，0，1
平衡因子：節點的右子樹的高度減去左子樹的高度

2。AVL樹的插入：從新插入節點到根的路徑上，修改遇到的節點的平衡因子即可，對其他部分沒影響
1）向右子女的右子樹插入一個節點，單旋轉就可以
2）向右子女的左子樹插入一個節點，雙旋轉，先圍繞父節點，再圍繞祖父節點

3。AVL樹的刪除：從刪除節點到根的路徑上，任何不平衡因子的節點都需要修改，與插入不同，需要O(lgn)次旋轉。

4。一個java實現：
http://www.koders.com/java/fid3B5247D34968077A6EFD4216589026D343559FF9.aspx?s=avl%2Btree

1。遞歸的定義：
遞歸的定義由兩部分組成：
1）稱作定位點（anchor）或者基本情況（ground case），它們是一些基本元素，這些基本元素是集合序列中其他所有對象的基礎。
2）給出除基本元素或者已創建對象之外的新對象的構造規則，可以再三使用這個規則不斷產生新的對象。

2。遞歸的實現：一般是由操作系統完成的，但是大部分的計算機系統的遞歸定義都是利用運行時堆棧實現的。在系統內，無論何時調用一個方法都會創建一個活動記錄。一個遞歸調用并不僅僅是一個方法調用其自身，而是方法的一個instance調用相同方法的另一個instance，在計算機內部，這些調用是用不同的活動記錄表示，并由系統區分。

3。尾遞歸：
僅在方法的末尾實行一次遞歸調用，這樣的遞歸叫尾遞歸。尾遞歸很容易被循環所替換，或者說它只是一個名字比較好聽的循環，如：

替換為循環：


尾遞歸對一些沒有顯式循環結構的語言（如Prolog）特別重要

4。非尾遞歸：
遞歸相比于迭代結構的優點就是非常清晰并易于理解，這一點可以在二叉樹遍歷上得到體現。3種遍歷方式的遞歸版本與迭代版本在可讀性上不可同日而語。
問題：逆序輸出一行輸入（以ruby語言為例）



運行此程序，輸入一行字符，將逆序輸出，本質上是利用運行時堆棧完成的遞歸調用

5。間接遞歸：
方法通過一連串的調用，然后間接地調用它自身，這樣的遞歸稱為間接遞歸。
6。嵌套遞歸
一般出現在函數的定義中，如果這個函數不僅用它自身定義，而且還江它自身作為一個參數，如：
???? 0????? ???? ?n=0
h(n)=n??? ???? n>4
h(2+h(2n))?? n<=4

7。過分遞歸：遞歸帶來的邏輯簡單性和可讀性的代價是拖長了運行時間并且相對于非遞歸方法，它占用了更多的運行時堆棧空間。如果遞歸層次太深，可能導致運行時堆棧溢出，程序非正常結束的錯誤。

8。回溯（backtracking技術）：在某點有多條道路供選擇的時候，但不清楚哪一條能解決問題。在嘗試一條道路失敗后，返回岔口再試另一條道路。但是必須確定所有的道路都是可嘗試的，可返回的。這種技術成為回溯。
在迷宮問題中和8皇后問題中使用此技術。具體程序不再列出（好長@_@）

一。直接插入排序
1。直接插入排序：直接插入排序是一種簡單的排序方法，它的基本思想是將待排序的記錄按照其值的大小插入到已排好序的有序表的適當位置，直到全部插入完為止。舉個整型的排序例子
2。直接插入排序的偽代碼：

insertionsort(data[])
???for?i=1?to?data.length-1
???????tmp=data[i];
???????將所有大于tmp的元素data[j]向后移動一位;
???????將tmp放在正確的位置上;

3.簡單例子，以整型為例。
A）ruby語言實現：
?

def?insertion_sort(a)
??i=1
??while?i<a.length
????tmp=a[i]
????j=i
????while?j>0
??????break?if?tmp>a[j-1]
??????a[j]=a[j-1]
??????j-=1
????end
????a[j]=tmp
????i+=1
??end
end???????
a=[10,2,3]
insertion_sort(a)
a.each{|i?|?print?i.to_s+"?"}

B）java語言實現：

package?com.sohu.blog.denns_zane.sort;

public?class?InsertSort{
????public?static?void?main(String?args[]){
????????int?[]data={12,2,3,56,90};
????????insertsort(data);
????????for(int?i=0;i<data.length;i++){
????????????System.out.print(data[i]+"?");
????????}
????}
????public?static?void?insertsort(int?[]data){
????????for(int?i=1,j;i<data.length;i++){
????????????int?tmp=data[i];
????????????for(j=i;j>0&&tmp<data[j-1];j--)
???????????????data[j]=data[j-1];
????????????data[j]=tmp;???
????????}
????}
}

5。算法復雜度：
最好情況：進行n-1次比較和2(n-1)次移動，盡管他們其實都是多余的，復雜度O(n)
最壞情況：具體計算略，O(n*n)
平均情況：O(n*n)，也就是接近最壞情況，在平均情況下，數組大小翻倍，它的排序工作將是原來的4倍。

二。選擇排序
1。算法描述：選擇算法試圖先查找一個放錯位置的元素并將它放到最終位置上，以此來局部化數組元素的交換。選擇值最小的元素并將它和第一個位置上的元素交換。在第i步中，查找data[i],...,data[n-1]中的最小元素，并將它和data[i]進行交換。重復此過程，直到所有的元素都放入正確的位置為止。

2。偽代碼描述：

selectionsort(data[])
?????for?i=0?to?data.length-2
????????從data[i],,data[n-1]中選取最小的元素
????????將它和data[i]交換

?
3。實現，以整型數組為例：
1)ruby語言實現：

def?selection_sort(a)
??least=0
??for?i?in?(0..(a.length-2))
????j=i+1
????least=i
????while?j<a.length
??????if?a[j]<a[least]
????????least=j
??????end
??????j+=1??
????end
????a[least],a[i]=a[i],a[least]?unless?least==i?#交換
??end
end
a=[12,4,34,23,45,35]
selection_sort(a)
a.each{|i|?print?i.to_s+"?"}

代碼很好理解，不做解釋。

2）java語言實現：

package?com.sohu.blog.denns_zane.sort;

public?class?SelectionSort{
????public?static?int[]?selection_sort(int?[]?data){
????????int?i,j,least=0;
????????for(i=0;i<data.length-1;i++){
????????
??????????for(j=i+1,least=i;j<data.length;j++)
????????????if?(data[j]<=data[least])
????????????????????least=j;
??????????if?(least!=i)
????????????swap(data,least,i);??//????data[i]oí×?D??a??
????????}????
????????return?data;???
????}
????public?static?void?swap(int[]data,int?least,int?i){
????????int?tmp=data[least];
????????data[least]=data[i];
????????data[i]=tmp;
????}
????public?static?void?main(String?args[]){
????????int[]?t={10,29,12,23,56};
????????selection_sort(t);
????????for(int?i:t){
????????????System.out.print(i+"?");
????????}?
????}
}

4.算法效率：
任何情況下，都需要進行n*(n-1)/2次比較，也就是O(n*n)的復雜度
最好情況：數組已經排序，不需要交換任何元素
最壞情況：最大元素在第一個位置而其他元素有序時，需要進行3*(n-1)次交換，即O(n)，也是很好的結果

三。冒泡排序
1。算法偽代碼描述：

bubblesort(data[])
??for?i=0?to?data.length-2
?????for?j=data.length-1?downto?i+1
?????????如果順序錯誤，就交換j和j-1位置上的元素

2。實現：
1)ruby語言實現：

def?bubble_sort(data)
??for?i?in?(0..(data.length-2))
?????j=data.length-1
?????while?j>i
????????if?data[j]<data[j-1]
???????????data[j],data[j-1]=data[j-1],data[j]???#交換
????????end
????????j-=1
?????end
??end
end
a=[12,3,56,7,89,87]
bubble_sort(a)
a.each{|i|?print?i.to_s+"?"}

2）java語言實現：

package?com.sohu.blog.denns_zane.sort;

public?class?BubbleSort{
????public?static?void?bubble_sort(int?[]?data){
????????for(int?i=0;i<data.length-1;i++)
????????????for(int?j=data.length-1;j>i;j--)
??????????????if(data[j]<data[j-1])
????????????????swap(data,j,j-1);
????????
????}
????public?static?void?swap(int[]data,int?least,int?i){
????????int?tmp=data[least];
????????data[least]=data[i];
????????data[i]=tmp;
????}
????public?static?void?main(String?args[]){
????????int[]?t={10,29,12,23,56};
????????bubble_sort(t);
????????for(int?i:t){
????????????System.out.print(i+"?");
????????}?
????}
}

3。算法效率：
冒泡排序的比較次數近似是插入排序的兩倍，和選擇排序相同；移動次數和插入排序相同，是選擇排序的n倍。可以說，插入排序比冒泡排序快兩倍。

     摘要: 一。棧1。概念：棧（stack）是一種線性數據結構，只能訪問它的一端來存儲或者讀取數據。棧是一種后進先出的結構（LIFO)2。棧的主要操作：.clear()——清棧.isEmpty()——檢查棧是否為空.push(e)——壓棧.pop()——出棧.topEl()——返回棧頂元素3。棧的java實現：使用數組鏈表實現/**?*//**?*??*/package?com.sohu.blog.denns...  閱讀全文

     摘要: 一 樹、二叉樹和二叉查找樹 1。樹的概念： 遞歸定義： 1） 一個空結構是一個空樹 2）如果t1,...,tk是分離的樹，那么以t1,...,tk的根為子節點的根結構也是樹 3）只有按照1，2規則產生的結構才是樹 樹的概念更多用于分層結構，比如數據庫管理系統的分層模型。 2。二叉樹（binary tree）：所有節點都有兩個子節點（可以為空），并且每個子節...  閱讀全文

     摘要: 數組的兩大缺點： 1。若改變數組的大小就要創建一個新的數組，并需要從原數組復制所有的數據到新的數組 2。數組元素在內存中依次順序存儲，這意味著向數組插入一項要移動數組中的其他元素 因此，我們使用鏈式結構，鏈式結構是存儲數據的結點以及指向其他節點的指針的集合。如此一來，節點可以位于內存的任意位置，而且從一個節點到另一個節點的傳遞可以通過在結構中存儲節點間引用來實現。 一。單向...  閱讀全文

C#的using語句設計的蠻貼心，比java的import有趣一點。轉一篇文章.

C#中的using除了作為命名空間指示符(using System)，類型的別名指示符(using Dos=System.Console)，還有資源管理的語句功能：
using (R r1 = new R ()) {
? ?r1.F();
}
在C#中被翻譯為：

R?r1?=?new?R();
try?{
???r1.F();
}
finally?{
???if?(r1?!=?null)?((IDisposable)r1).Dispose();
}

r1當然要支持Dispose()方法了

再來一個例子：

使用using會自動調用MyObject的Dispose方法.

一.C#的統一類型系統
1.C#的類型系統是統一的，java的類型系統分為：基本類型（原生類型）和類類型，而C#的所有類型直接或間接地從object類類型派生而來，從類型系統上來看比java更OO。
2.C#的類型分為三類：
（1）值類型，一個值類型或是結構類型，或是枚舉類型
（2）引用類型
（3）指針類型
值類型與引用類型的不同在于：值類型的變量直接包含其數據，而引用類型的變量存儲對其數據的引用(reference)，后者稱為對象(object)。對于引用類型，兩個變量可能引用同一個對象，因此對一個變量的操作可能影響另一個變量所引用的對象。對于值類型，每個變量都有自己的數據副本，對一個變量的操作不可能影響另一個變量。
二。值類型
1.所有值類型從類System.ValueType隱式繼承，后者又從類object繼承。任何類型都不可能從值類型派生。

2.所有值類型都隱式聲明一個稱為默認構造函數(default constructor)的公共無參數實例構造函數。默認構造函數返回一個零初始化實例，它就是該值類型的默認值(default value)：

·???????? 對于所有simple-types，默認值是將其所有位都置零的位模式所形成的值：

o??????? 對于sbyte、byte、short、ushort、int、uint、long和ulong，默認值為0。

o??????? 對于char，默認值為'\x0000'。

o??????? 對于float，默認值為0.0f。

o??????? 對于double，默認值為0.0d。

o??????? 對于decimal，默認值為0.0m。

o??????? 對于bool，默認值為false。

·???????? 對于enum-typeE，默認值為0。

·???????? 對于struct-type，默認值是通過將所有值類型字段設置為它們的默認值、將所有引用類型字段設置為null而產生的值。

3.C#中有所謂的簡單類型概念（simple type），類似于java的基本類型，但又不同，C#的簡單類型本質上都是結構類型（預定義集合的結構類型），所以還是值類型，從System.ValueType繼承而來。C#的簡單類型包括：

保留字	化名的類型
sbyte	System.SByte
byte	System.Byte
short	System.Int16
ushort	System.UInt16
int	System.Int32
uint	System.UInt32
long	System.Int64
ulong	System.UInt64
char	System.Char
float	System.Single
double	System.Double
bool	System.Boolean
decimal	System.Decimal

這些簡單類型都是System命名空間中預定義結構類型的別名（ruby的別名實在貼心）

4.枚舉類型，枚舉類型是具有命名常量的獨特的類型。每個枚舉類型都有一個基礎類型，該基礎類型必須為 byte、sbyte、short、ushort、int、uint、long 或 ulong。如果沒有為枚舉類型中的元素指定基礎值，默認是從0開始逐一遞增。

三。引用類型

1.引用類型是類類型、接口類型、數組類型或委托類型。

2.類類型：包括預定義的類類型和用戶通過class關鍵字的自定義類類型

3.對象類型：

object類類型是所有其他類型的最終基類。C# ?中的每種類型都是直接或間接從object類類型派生的。

關鍵字object只是預定義類System.Object的別名。

4.string類型:
string類型是直接從object繼承的密封類類型。關鍵字string只是預定義類System.String的別名.
5.接口類型：
與java中的接口概念基本一致，可以變相實現多重繼承。

類類型	說明
System.Object	所有其他類型的最終基類。
System.String	C# ?語言的字符串類型。
System.ValueType	所有值類型的基類。
System.Enum	所有枚舉類型的基類。
System.Array	所有數組類型的基類。
System.Delegate	所有委托類型的基類。
System.Exception	所有異常類型的基類。

四。裝箱、拆箱概念
1.裝箱和拆箱的概念是C# ?的類型系統的核心。它在 value-type 和 reference-type 之間的架起了一座橋梁，使得任何 value-type 的值都可以轉換為 object 類型的值，反過來轉換也可以。
2.裝箱：裝箱轉換允許將value-type隱式轉換為reference-type。
裝箱的行為可以用下面的過程描述：

sealed class T_Box: System.ValueType
{
T value;

public T_Box(T t) {
???? value = t;
}
}

分配一個對象實例，然后將value-type的值復制到該實例中
3.拆箱：拆箱轉換允許將reference-type顯式轉換為value-type。
從對象box到value-typeT的拆箱轉換相當于執行表達式((T_Box)box).value