庄周梦蝶

    放假这几天，喝了很多酒，读完一本书，想念一个人，花了不少钱
    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]ºÍ×îСԪËØ
        }    
        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