概述

一些面向对象的编程方式，提供了一种构建对象间复杂网络互连的能力。当对象们连接在一起时，它们就可以相互提供服务和信息。

通常来说，当某个对象的状态发生改变时，你仍然需要对象之间能互相通信。但是出于各种原因，你也许并不愿意因为代码环境的改变而对代码做大的修改。也许，你只想根据你的具体应用环境而改进通信代码。或者，你只想简单的重新构造通信代码来避免类和类之间的相互依赖与相互从属。

问题

当一个对象的状态发生改变时，你如何通知其他对象？是否需要一个动态方案――一个就像允许脚本的执行一样，允许自由连接的方案？

解决方案

观察者模式 ：定义对象间的一种一对多的依赖关系, 当一个对象的状态发生改变时, 所有依赖于它的对象都得到通知并被自动更新。

观察者模式允许一个对象关注其他对象的状态，并且，观察者模式还为被观测者提供了一种观测结构，或者说是一个主体和一个客体。主体，也就是被观测者，可以用来联系所有的观测它的观测者。客体，也就是观测者，用来接受主体状态的改变 观测就是一个可被观测的类（也就是主题）与一个或多个观测它的类（也就是客体）的协作。不论什么时候，当被观测对象的状态变化时，所有注册过的观测者都会得到通知。

观察者模式将被观测者（主体）从观测者（客体）种分离出来。这样，每个观测者都可以根据主体的变化分别采取各自的操作。（观察者模式和 Publish/Subscribe 模式一样，也是一种有效描述对象间相互作用的模式。）观察者模式灵活而且功能强大。对于被观测者来说，那些查询哪些类需要自己的状态信息和每次使用那些状态信息的额外资源开销已经不存在了。另外，一个观测者可以在任何合适的时候进行注册和取消注册。你也可以定义多个具体的观测类，以便在实际应用中执行不同的操作。

将一个系统分割成一系列相互协作的类有一个常见的副作用：需要维护相关对象间的一致性。我们不希望为了维持一致性而使各类紧密耦合，因为这样降低了它们的可重用性。

适用性

在以下任一情况下可以使用观察者模式:

• 当一个抽象模型有两个方面, 其中一个方面依赖于另一方面。将这二者封装在独立的对象中以使它们可以各自独立地改变和复用。
• 当对一个对象的改变需要同时改变其它对象 , 而不知道具体有多少对象有待改变。
• 当一个对象必须通知其它对象，而它又不能假定其它对象是谁。换言之 , 你不希望这些对象是紧密耦合的。

结构

模式的组成

观察者模式包含如下角色：

• 目标（Subject）: 目标知道它的观察者。可以有任意多个观察者观察同一个目标。 提供注册和删除观察者对象的接口。
• 具体目标（ConcreteSubject）: 将有关状态存入各 ConcreteObserver 对象。
• 观察者 (Observer): 为那些在目标发生改变时需获得通知的对象定义一个更新接口。当它的状态发生改变时, 向它的各个观察者发出通知。
• 具体观察者 (ConcreteObserver): 维护一个指向 ConcreteSubject 对象的引用。存储有关状态，这些状态应与目标的状态保持一致。实现 O b s e r v e r 的更新接口以使自身状态与目标的状态保持一致。

观察者模式的优缺点

Observer 模式允许你独立的改变目标和观察者。你可以单独复用目标对象而无需同时复用其观察者, 反之亦然。它也使你可以在不改动目标和其他的观察者的前提下增加观察者。

下面是观察者模式其它一些优点 :

• 观察者模式可以实现表示层和数据逻辑层的分离, 并定义了稳定的消息更新传递机制，抽象了更新接口，使得可以有各种各样不同的表示层作为具体观察者角色。
• 在观察目标和观察者之间建立一个抽象的耦合 ：
  一个目标所知道的仅仅是它有一系列观察者 , 每个都符合抽象的 Observer 类的简单接口。目标不知道任何一个观察者属于哪一个具体的类。这样目标和观察者之间的耦合是抽象的和最小的。因为目标和观察者不是紧密耦合的, 它们可以属于一个系统中的不同抽象层次。一个处于较低层次的目标对象可与一个处于较高层次的观察者通信并通知它 , 这样就保持了系统层次的完整。如果目标和观察者混在一块 , 那么得到的对象要么横贯两个层次 (违反了层次性), 要么必须放在这两层的某一层中 (这可能会损害层次抽象)。
• 支持广播通信 : 不像通常的请求, 目标发送的通知不需指定它的接收者。通知被自动广播给所有已向该目标对象登记的有关对象。目标对象并不关心到底有多少对象对自己感兴趣 ; 它唯一的责任就是通知它的各观察者。这给了你在任何时刻增加和删除观察者的自由。处理还是忽略一个通知取决于观察者。
• 观察者模式符合 “开闭原则” 的要求。

观察者模式的缺点 :

• 如果一个观察目标对象有很多直接和间接的观察者的话，将所有的观察者都通知到会花费很多时间。
• 如果在观察者和观察目标之间有循环依赖的话，观察目标会触发它们之间进行循环调用，可能导致系统崩溃。
• 观察者模式没有相应的机制让观察者知道所观察的目标对象是怎么发生变化的，而仅仅只是知道观察目标发生了变化。
• 意外的更新 因为一个观察者并不知道其它观察者的存在 , 它可能对改变目标的最终代价一无所知。在目标上一个看似无害的的操作可能会引起一系列对观察者以及依赖于这些观察者的那些对象的更新。此外 , 如果依赖准则的定义或维护不当，常常会引起错误的更新 , 这种错误通常很难捕捉。

简单的更新协议不提供具体细节说明目标中什么被改变了 , 这就使得上述问题更加严重。如果没有其他协议帮助观察者发现什么发生了改变，它们可能会被迫尽力减少改变。

实现

在 php 的 SPL 支持观察者模式，SPL 提供了 SplSubject 和 SplObserver 接口。

SplSubject 接口提供了 attach()、detach()、notify() 三个方法。而 SplObserver 接口则提供了 update() 方法。

SplSubject 派生类维护了一个状态，当状态发生变化时 - 比如属性变化等，就会调用 notify() 方法，这时，之前在 attach() 方法中注册的所有 SplObserver 实例的 update() 方法就会被调用。接口定义如下：

<?php  
/** 
* 这一模式的概念是 SplSubject 类维护了一个特定状态，当这个状态发生变化时，它就会调用 notify() 方法。 
* 调用 notify() 方法时，所有之前使用 attach() 方法注册的 SplObserver 实例的 update 方法都会被调用。 
* 
*/  
interface SplSubject{  
    public function attach(SplObserver $observer);// 注册观察者  
    public function detach(SplObserver $observer);// 释放观察者  
    public function notify();// 通知所有注册的观察者  
}  
interface SplObserver{  
    public function update(SplSubject $subject);// 观察者进行更新状态  
}

实现代码：

<?php  
/** 
* 具体目标 
* 
*/  
class ConcreteSubject implements SplSubject {  
        private $observers, $value;  
        public function __construct() {  
        $this->observers = array();  
    }  

    public function attach(SplObserver $observer) { // 注册观察者  
        $this->observers[] = $observer;  
    }  

    public function detach(SplObserver $observer) { // 释放观察者  
        if($idx = array_search($observer,$this->observers,true)) {  
        unset($this->observers[$idx]);  
    }  
    }  

    public function notify() { // 通知所有观察者  
        foreach($this->observers as $observer) {  
        $observer->update($this);  
    }  
    }  

    public function setValue($value) {  
        $this->value = $value;  
        $this->notify();  
    }  

    public function getValue() {  
        return $this->value;  
    }  

}  
/** 
* 具体观察者 
* 
*/  
class ConcreteObserver1 implements SplObserver {  

    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver1  value is',$subject->getValue(), '<br>';  
    }  

}  
/** 
* 具体观察者 
* 
*/  
class ConcreteObserver2 implements SplObserver {  

    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver2 value is', $subject->getValue(), '<br>';  
    }  

}  

$subject = new ConcreteSubject();  
$observer1 = new ConcreteObserver1();  
$observer2 = new ConcreteObserver2();  
$subject->attach($observer1);  
$subject->attach($observer2);  
$subject->setValue(5);  
?>

我们扩展上面的例子，根据目标状态而更新不同的观察者：

<?php    
/** 
* 具体目标  
*  
*/    

class ConcreteSubject implements SplSubject {  

    private $observers, $_state;  

    public function __construct() {  
        $this->observers = array();  
    }  
    /** 
    *  注册观察者   
    * 
    * @param SplObserver $observer 
    */  
    public function attach(SplObserver $observer) {  
        $this->observers[] = $observer;  
    }  
    /** 
    *  // 释放观察者   
    * 
    * @param SplObserver $observer 
    */  
    public function detach(SplObserver $observer) {  
        if($idx = array_search($observer,$this->observers,true)) {  
            unset($this->observers[$idx]);  
        }  
    }  
    /** 
    * 通知所有观察者   
    *  
    */  
    public function notify() {  
        /** 
        * 只要状态改变，就通知观察者 
        */  
        foreach($this->observers as $observer) {  
            if ($observer->getState() == $this->_state) {  
                $observer->update($this);  
            }  
        }  
    }  
    /** 
    * 设置状态 
    * 
    * @param unknown_type $state 
    */  
    public function setState($state) {  
        $this->_state = $state;  
        $this->notify();  
    }  

    public function getState() {  
        return $this->_state;  
    }  

}  

/** 
* 抽象观摩者 
* 
*/  
abstract class observer{  
    private $_state;  

    function __construct($state) {  
        $this->_state = $state;  
    }  

    public function setState($state) {  
        $this->_state = $state;  
        $this->notify();  
    }  

    public function getState() {  
        return $this->_state;  
    }  

}  
/** 
* 具体观察者 1 
*  
*/    
class ConcreteObserver1 extends observer  implements SplObserver {  

    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver1  state is',$subject->getState(), '<br>';  
    }  

}  

/** 
* 具体观察者 2 
*  
*/    
class ConcreteObserver2 extends observer   implements SplObserver {  
    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver2 state is', $subject->getState(), '<br>';  
    }  

}  
/** 
* 具体观察者 3 
*  
*/    
class ConcreteObserver3 extends observer   implements SplObserver {  
    function __construct($state) {  
        parent::__construct($state);  
    }  
    public function update(SplSubject $subject) {  
        echo 'ConcreteObserver3 state is', $subject->getState(), '<br>';  
    }  

}  

$subject = new ConcreteSubject();  
$observer1 = new ConcreteObserver1(1);  
$observer2 = new ConcreteObserver2(1);  
$observer3 = new ConcreteObserver3(2);  
$subject->attach($observer1);  
$subject->attach($observer2);  
$subject->attach($observer3);  
echo 'Subject state is 1', '<br>';  
$subject->setState(1);  
echo 'Subject state is 2', '<br>';  
$subject->setState(2);  
?>

与其他相关模式

• 终结者模式 Mediator: 通过封装复杂的更新语义 , ChangeManager 充当目标和观察者之间的中介者。
• 单例模式 Singleton: ChangeManager 可使用 Singleton 模式来保证它是唯一的并且是可全局访问
  的。

总结与分析

通过 Observer 模式，把一对多对象之间的通知依赖关系的变得更为松散，大大地提高了程序的可维护性和可扩展性，也很好的符合了开放 - 封闭原则。

分类

工厂模式主要是为创建对象提供过渡接口，以便将创建对象的具体过程屏蔽隔离起来，达到提高灵活性的目的。

工厂模式可以分为三类：

• 简单工厂模式 （Simple Factory, 简单工厂模式可看为工厂方法模式的一种特例，两者归为一类。 ）

• 工厂方法模式 （Factory Method）

• 抽象工厂模式 （Abstract Factory）

这三种模式从上到下逐步抽象，并且更具一般性。

GOF在《设计模式》一书中将工厂模式分为两类：工厂方法模式（Factory Method）与抽象工厂模式（Abstract Factory）。

区别

• 简单工厂模式 ：

  一个工厂类, 这个工厂类能创建多个具体产品类的实例。
  一个抽象产品类，可以派生出多个具体产品类。

• 工厂方法模式 ：

  一个抽象工厂类，可以派生出多个具体工厂类。
  一个抽象产品类，可以派生出多个具体产品类。

  每个具体工厂类只能创建一个具体产品类的实例。

• 抽象工厂模式 ：

  一个抽象工厂类，可以派生出多个具体工厂类。
  多个抽象产品类，每个抽象产品类可以派生出多个具体产品类。

  每个具体工厂类可以创建多个具体产品类的实例。

区别：

工厂方法模式只有一个抽象产品类，而抽象工厂模式有多个。

工厂方法模式的具体工厂类只能创建一个具体产品类的实例，而抽象工厂模式可以创建多个。

简单工厂模式

<?php
/**
  车子系列
 
 */
abstract Class BWM{
    function construct($pa) {

    }
}
Class BWM320 extends BWM{
    function construct($pa) {

    }
}
Class BMW523 extends BWM{
   function construc($pb){

   }
}

/**
  工厂创建车
 
 */
class Factory {


    static function  createBMW($type){
        switch ($type) {
          case 320:
             return new BWM320();
          case 523:
             return new BMW523();
        //….
   }
}

/**
  客户通过工厂获取车
 
 */
class Customer {
    private $BMW;
    function getBMW($type){
        $this¬-> BMW =  Factory::createBMW($type);
    }
}

工厂方法模式

<?php
/**
  车子系列
 
 /
abstract Class BWM{
function construct($pa) {

}
}
Class BWM320 extends BWM{
function construct($pa) {

}
}
Class BMW523 extends BWM{
   function construc($pb){

}
}

/**
  创建工厂的接口
 
 */
interface FactoryBMW {
       function createBMW();
}


/**
  
  创建BWM320车
 **/
class FactoryBWM320 implements FactoryBMW {
   function  createBMW($type){
      return new BWM320();
   }

}


/**
 
  创建BWM523车
 **/
class FactoryBWM523 implements FactoryBMW {
   function  createBMW($type){
      return new BMW523();
   }
}

/**
  
  客户得到车
 */
class Customer {
   private $BMW;
   function  getBMW($type){
      switch ($type) {
        case 320:
           $BWM320 = new FactoryBWM320();
           return $BWM320->createBMW();
        case 523:
           $BWM523 = new FactoryBWM523();
           return $BWM320->createBMW();
            //….
      }

  }
}

抽象工厂模式

<?php
/**
  车子系列以及型号
 
 */
abstract class  BWM{
}

class BWM523 extends  BWM {
}
class BWM320 extends  BWM {


}

/*
  空调
 
 */
abstract class aircondition{
}
class airconditionBWM320  extends aircondition {

}
class airconditionBWM52 extends aircondition {

}

/*
  创建工厂的接口
 
 */
interface FactoryBMW {
     function createBMW();
     function createAirC();
}


/**
 
  创建BWM320车
 /
class FactoryBWM320 implements FactoryBMW {
    function  createBMW(){
    return new BWM320();
}
function  createAirC(){ //空调
    return new airconditionBWM320();
}
}


/*
  
  创建BWM523车
 */
class FactoryBWM523 implements FactoryBMW {
    function  createBMW(){
    return new BWM523();
}
function  createAirC(){
    return new airconditionBWM523();
}
}

/*
  
  客户得到车
 */
class Customer {
   private $BMW;
   private $airC;
   function  getBMW($type){
       $class = new ReflectionClass(‘FactoryBWM’ .$type );//建立 Person这个类的反射类
        $instance  = $class->newInstanceArgs();//相当于实例化Person 类
        $this->BMW =  $instance->createBMW();
       $this->airC =  $instance->createAirC();
   }
}

分布式系统特性

CAP是分布式系统里最著名的理论，wiki百科如下

• Consistency(all nodes see the same data at the same time)
• Availability (a guarantee that every request receives a response about whether it was successful or failed)
• Partition tolerance (the system continues to operate despite arbitrary message loss or failure of part of the system)

  (摘自 ：http://en.wikipedia.org/wiki/CAP_theorem)
  

. . .

分布式系统中的概念

最简单的分布式系统

分布式可繁也可以简，最简单的分布式就是大家最常用的，

在负载均衡服务器后加一堆web服务器，然后在上面搞一个缓存服务器来保存临时状态，

后面共享一个数据库，其实很多号称分布式专家的人也就停留于此，

大致结构如下图所示：

这种环境下真正进行分布式的只是web server而已，

并且web server之间没有任何联系，所以结构和实现都非常简单。

最完备的分布式体系的模块组成

有些情况下，对分布式的需求就没这么简单，

在每个环节上都有分布式的需求，

比如Load Balance、DB、Cache和文件等等，

并且当分布式节点之间有关联时，

还得考虑之间的通讯，

另外，

节点非常多的时候，

得有监控和管理来支撑。这样看起来，

分布式是一个非常庞大的体系，

只不过你可以根据具体需求进行适当地裁剪。按照最完备的分布式体系来看，

可以由以下模块组成：

• 分布式任务处理服务：负责具体的业务逻辑处理

• 分布式节点注册和查询：负责管理所有分布式节点的命名和物理信息的注册与
  询，是节点之间联系的桥梁

• 分布式DB：分布式结构化数据存取

• 分布式Cache：分布式缓存数据（非持久化）存取

• 分布式文件：分布式文件存取

• 网络通信：节点之间的网络数据通信

• 监控管理：搜集、监控和诊断所有节点运行状态

• 分布式编程语言：用于分布式环境下的专有编程语言，比如Elang、Scala

• 分布式算法：为解决分布式环境下一些特有问题的算法，比如解决一致性问题的Paxos算法

三元组

其实，分布式系统说白了，就是很多机器组成的集群，靠彼此之间的网络通信，担当的角色可能不同，共同完成同一个事情的系统。

. . .

为什么不推荐递归

递归的调试难度奇高，就决定了实际项目中很少用递归。

而且递归确实运行效率低，因为函数一层一层调用存在调用栈，

在切换到更深层的函数时要产生断点，为了保证回来时继续运行，

必须保存现在所处函数的各种状态，回来时恢复状态，这样一层层下去性能损失就不断增加。

大量开辟在栈区的内存 ，直到每一层的递归结束或整个递归结束才释放 且这个内存空间可能呈几何级数增加， 空间效率不佳， 有可能会栈溢出

而要知道什么是尾递归， 首先得指到什么是尾调用

. . .

只谈一下单链表, 链表实在是太重要, 是前面两篇说算法博客的基础, 了解了其应用和衍生, 再去了解其本身就有动力了

存储结构

typedef struct Node
{
	DataType data;
	struct Node *next;
}Node, *Node_Ptr;

• 链表中第一个结点的存储位置叫做头指针
• 头指针和头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。
• 如果链表有头结点，那么头指针就是指向头结点数据域的指针。
• 单链表也可以没有头结点

头结点的优点:

• 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
• 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

有头结点和无头结点的建立链表方法头插法

include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//无头结点链表的头插法实现函数
link * creatLink(int * arc, int length) {
    int i;
    //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H
    link * H =(link*)malloc(sizeof(link));
    H->elem = arc[0];
    H->next = NULL;
    //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前
    for (i = 1; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //插入元素时，首先将插入位置后的链表链接到新结点上
        a->next = H;
        //然后再链接头指针 H
        H = a;
    }
    return H;
}
//有头结点链表的头插法实现函数
link * HcreatLink(int * arc, int length) {
    int i;
    //创建头结点 H，其链表的头指针也是 H
    link * H = (link*)malloc(sizeof(link));
    H->elem = 0;
    H->next = NULL;
    //采用头插法创建链表
    for (i = 0; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //首先将插入位置之后的链表链接到新结点 a 上
        a->next = H->next;
        //将新结点 a 插入到头结点之后的位置
        H->next = a;
    }
    return H;
}
//链表的输出函数
void display(link *p) {
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main() {
    int a[3] = { 1,2,3 };
    //采用头插法创建无头结点链表
    link * H = creatLink(a, 3);
    display(H);
    //采用头插法创建有头结点链表
    link * head = HcreatLink(a, 3);
    display(head);
    //使用完毕后，释放即可
    free(H);
    free(head);
    return 0;
}

运行结果：

3 2 1
0 3 2 1

提示：没有 0 的为无头结点的头插法输出结果，有 0 的为有头结点的头插法的输出结果

. . .

前言

使用SVN在管理代码的时候免不了进行代码的合并和还原，特别是当前版本的修改发现有重大问题的时候，还原是避免不了的，那么究竟应该怎样操作呢？

内容

使用SVN查看文件或目录的日志的时候，右键单击日志记录会弹出下面这个界面，今天我们来着重了解一下被红圈标记的三个选项——“Update item to this version”，“Revert to this version”，“Revert changes from this version”，这三个选项对于刚接触SVN的人确实不太好区分，一开始我也搞不懂，直到亲自试验一下才搞清楚这三个选项的用法。

在讲解这三个选项的作用之前，我们还是先来假定一个使用情景，假设我们的项目文件一共有8个版本，它版本号分别是1，2，3，4，5，6，7，8。

Update item to this version

这个选项的作用是将文件版本更新到对应所选的版本（当然内容也修改到了相应的版本）。如果我们是在版本4这里点击“Update item to this version”，表示5~8版本所作的修改全部作废，这个文件的历史回退到了版本4那个时代，但是需要注意的是，此时文件的版本是4，并不是最新的。我们知道SVN工具中如果文件不是最新版本就无法上传，所以说这个功能只是用来暂时还原一下版本，来查询某个问题的，不能将还原后的文件上传。这个特别是当你服务器启动不了了, 把版本退回一个可以启动版本的情况

Revert to this version

这个选项的作用是将文件的内容更新到对应的版本，版本号没有发生变化。如果我们是在版本4这里点击“Revert to this version”，表示5~8版本所作的修改全部被还原，此时svn里会有5-8被还原的文件改动可以提交, 此时文件和版本4的文件一模一样，但需要注意的是这项操作相当于我们把版本4这个文件拷贝了一份赋值给了当前目录下的文件，此时的文件版本还是8，并且是可以提交的，提交以后文件的版本变成了9，增加了一个新的版本，虽然这个版本和版本4的内容是一样的。

Revert changes from this version

这个选项的作用是将对应版本的修改还原，文件的版本号不发生变化，相当于在当前本版本上剔除某些版本所作的改变。如果我们是在版本4这里点击“Revert changes from this version”，表示版本4所作的修改被抹杀了，只剩下除版本4以外的7个修改了，但是此时文件是可以上传的，并且会生成新的版本9，只是版本9只包括除版本4以外的7次修改。这个选项是可以选择多个版本的，如果我们选择4,5,6,7这四个版本点击“Revert changes from this revision”，那么这几次修改都会被抹杀。如果我们选择5,6,7,8这四个版本点击“Revert changes from this revision”，表示取消这几个版本的修改，实际上和在版本4这里点击“Revert to this version”的作用是一样的。

考察cpp的静态绑定

struct MMPA{
	int value() const { return this->v_; }
	int tvalue() const { return 1; }
public:
	int v_;
};

int main(int argc, char* argv[]){
	{
		const MMPA* p = nullptr;
// 		std::cout << p->v_ << std::endl;
		std::cout << p->tvalue() << std::endl;
		std::cout << p->value() << std::endl;
		getchar(); return 0;
	}
}

会打印什么?

答案以及分析

答案: 打印1之后崩溃

真正的原因是：

因为对于非虚成员函数，Ｃ++这门语言是静态绑定的。这也是Ｃ++语言和其它语言Java, Python的一个显著区别。以此下面的语句为例：somenull->foo();这语句的意图是：调用对象somenull的foo成员函数。如果这句话在Java或Python等动态绑定的语言之中，编译器生成的代码大概是：找到somenull的foo成员函数，调用它。

（注意，这里的找到是程序运行的时候才找的，这也是所谓动态绑定的含义：运行时才绑定这个函数名与其对应的实际代码。有些地方也称这种机制为迟绑定，晚绑定。）但是对于C++。为了保证程序的运行时效率，Ｃ++的设计者认为凡是编译时能确定的事情，就不要拖到运行时再查找了。

所以C++的编译器看到这句话会这么干：

1. 查找somenull的类型，发现它有一个非虚的成员函数叫foo。（编译器干的）
2. 找到了，在这里生成一个函数调用，直接调B::foo(somenull)。

所以到了运行时，由于foo()函数里面并没有任何需要解引用somenull指针的代码，所以真实情况下也不会引发segment fault。这里对成员函数的解析，和查找其对应的代码的工作都是在编译阶段完成而非运行时完成的，这就是所谓的静态绑定，也叫早绑定。正确理解C++的静态绑定可以理解一些特殊情况下C++的行为。

求最大公约数

求 a 和 b 的最大公约数

int measure(int a, int b)
{
	int product = a * b;
	if (a == 0 || b == 0)
	{
		return -1;
	}
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (int mod = a % b)
	{
		a = b;
		b = mod;
	}
	//return b; // 最大公约数
	return product / b; // 记住这个公式： a*b=最小公倍数*最大公约数
}

棋盘/格子问题

在如下7*5的棋盘中，请计算从A移动到B一共有多少走法？要求每次只能向上或向右移动一格，并且不能经过P。(答案为492)

给定一个M*N的格子或棋盘，从左下角走到右上角的走法总数（每次只能向右或向上移动一个方格边长的距离）

运用动态规划来解答 :
我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的右上角看做二维坐标(M,N)(坐标系的单位长度为小方格的变长)
用f(i,j)表示移动到坐标f(i,j)的走法总数，其中0=<i,j<=n，设f(m,n)代表从坐标（0,0）到坐标（m,n）的移动方法，则
f(m,n)=f(m-1,n)+f(m,n-1).
于是状态f(i,j)的状态转移方程为：

f(i,j)=f(i-1,j)+f(i,j-1)   if i,j>0
f(i,j)=f(i,j-1)            if i=0
f(i,j)=f(i-1,j)            if j=0

初始情况就为：f(0,0)=0, f(0,1)=1, f(1,0)=1，这个问题可以在时间O(n^2)，空间O(n^2)内求解，非递归解.

所以答案为 492 =

SumWaysOfMoveOnChessBoard(7, 5) - SumWaysOfMoveOnChessBoard(3, 3) * SumWaysOfMoveOnChessBoard(7 - 3, 5 - 3)

递归解

int SumWaysOfMoveOnChessBoard_Recursion(int m, int n) 
{
    if (m == 0 && n == 0)
        return 0;
    if (m==0 || n==0)
        return 1;
    return SumWaysOfMoveOnChessBoard_Recursion(m, n - 1) + SumWaysOfMoveOnChessBoard_Recursion(m - 1, n);
}

非递归解

int SumWaysOfMoveOnChessBoard_NonRecursion_RawArray(int m, int n)
{
	if (m == 0 || n == 0)
		return 1;
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	int** arr = new int*[xSize];
	for (int i = 0; i < xSize; ++i)
		arr[i] = new int[ySize];

	arr[0][0] = 0;
	for (int i = 0; i < xSize; ++i) arr[i][0] = 1;
	for (int i = 0; i < ySize; ++i) arr[0][i] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];

	for (int i = 0; i < xSize; ++i)
		delete[] arr[i];
	delete[] arr;

	return arr[m][n];
}

int SumWaysOfMoveOnChessBoard_NonRecursion_STL(int m, int n)
{
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	std::vector< vector<int> > ChessBoardArray(xSize, vector<int>(ySize));;
	ChessBoardArray[0][0] = 0;
	for (int i = 0; i < xSize; ++i) ChessBoardArray[i][0] = 1;
	for (int j = 0; j < ySize; ++j) ChessBoardArray[0][j] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			ChessBoardArray[i][j] = ChessBoardArray[i][j - 1] + ChessBoardArray[i - 1][j];

	return ChessBoardArray[m][n];
}

大数加法/乘法

大数加法思路 :
模拟小学列竖式

        9  8
+       2  1
-------------
    (1)(1)(9)

大数乘法思路 :

模拟乘法累加 - 改进
简单来说，方法二就是先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位。

例如：计算98×21,步骤如下

        9  8
×       2  1
-------------
       (9)(8)   <---- 第1趟: 98×1的每一位结果 
   (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
   (18)(25)(8)  <---- 这里就是相对位的和，还没有累加进位

这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑。
从右向左依次累加，如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余后的个位数，而将十位数进位（通过模运算得到）累加到高位便可，循环直到累加完毕。

void BigIntAddition(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	size_t strlenA = strlen(bigIntA);
	size_t strlenB = strlen(bigIntB);
	size_t biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		//cout << int(strlenA - 1 - i) << endl;
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	int* bigIntSum = new int[biggerStrlen + 1];
	int x = 0; // 进位
						 // 模拟小学的列竖式加法, 满10进1
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		bigIntSum[i] = reversedA[i] + reversedB[i] + x;
		x = bigIntSum[i] / 10;
		bigIntSum[i] %= 10;
	}
	size_t printLen = biggerStrlen;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (x > 0)
	{
		bigIntSum[biggerStrlen] = x;
		printLen = biggerStrlen + 1;
	}
	for (size_t i = 0; i < printLen; ++i)
		cout << bigIntSum[printLen - 1 - i]; // --> 58023
	cout << endl;

	delete[] bigIntSum;
}

void BigIntMultiplication(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	int strlenA = static_cast<int>(strlen(bigIntA));
	int strlenB = static_cast<int>(strlen(bigIntB));
	cout << strlenA << ", " << strlenB << endl;
	int biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (int i = 0; i < biggerStrlen; ++i)
	{
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	// 分配一个空间，用来存储运算的结果，num1长的数 * num2长的数，
	// 结果不会超过num1+num2长
	int* bigIntProduct = new int[strlenA + strlenB];
	// 比如防止下面执行 bigIntSum[i + j] += reversedA[i] * reversedB[j]; 这句的时候
	// i+j = 0 时 出错, 因为 bigIntSum[0] 为一个未初始化的值
	for (int i = 0; i < strlenA + strlenB; ++i)
		bigIntProduct[i] = 0;
	int carry = 0; // 进位

	// 先不考虑进位问题，根据竖式的乘法运算，
	// num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上
	for (int i = 0; i < strlenA; ++i)
		for (int j = 0; j < strlenB; ++j)
			bigIntProduct[i + j] += reversedA[i] * reversedB[j];

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 3659707060341650
	cout << endl;

	//单独处理进位
	for (int i = 0; i < strlenA + strlenB - 1; ++i)
	{
		bigIntProduct[i] += carry;
		carry = bigIntProduct[i] / 10;
		bigIntProduct[i] %= 10;
	}

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 626770070
	cout << endl;

	int printLen = strlenA + strlenB - 1;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (carry > 0)
	{
		bigIntProduct[strlenA + strlenB - 1] = carry;
		printLen = strlenA + strlenB;
	}
	for (int i = 0; i < printLen; ++i)
		cout << bigIntProduct[printLen - 1 - i]; // --> 70077626
	cout << endl;
	delete[] bigIntProduct;
}

int main()
{
	char *bigIntA = "1234";
	char *bigIntB = "56789";
	BigIntAddition(bigIntA, bigIntB);
	BigIntMultiplication(bigIntA, bigIntB);
	return 0;
}

最长公共子串

问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。

比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

算法思路：

1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。

针对于上面的两个字符串我们可以得到的二维矩阵如下：

从上图可以看到，str和str2共有5个公共子串，但最长的公共子串长度为5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，
即某个二维矩阵元素的值由 item[i][j]=1 演变为 item[i][j]=1 +item[i-1][j-1] ，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：

故状态转移方程

X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j]，dp[i][j] = 0

int LongestCommonSubstring(char* strA, char* strB)
{
	if (!strA || !strB)
		return -1;

	int maxLen = 0;

	int strlenA = static_cast<int>(strlen(strA));
	int strlenB = static_cast<int>(strlen(strB));

	int biggerStrlen = strlenA > strlenB ? (strlenA + 1) : (strlenB + 1);
	char * lcs = new char[biggerStrlen];
	int lcsMaxIndex = 0;

	int** temp = new int*[strlenA];
	for (int i = 0; i < strlenA; ++i)
		temp[i] = new int[strlenB];

	for (int i = 0; i < strlenA; ++i)
	{
		for (int j = 0; j < strlenB; ++j)
		{
			if (strA[i] == strB[j])
			{
				if (i > 0 && j > 0)
					temp[i][j] = temp[i - 1][j - 1] + 1;
				else
					temp[i][j] = 1;
			}
			else
			{
				temp[i][j] = 0;
			}
			if (temp[i][j] > maxLen)
			{
				maxLen = temp[i][j];
				lcsMaxIndex = i;
			}
		}
	}

	for (int i = 0;i < maxLen; ++i)
		*(lcs + maxLen - i - 1) = strA[lcsMaxIndex--];
	*(lcs+maxLen) = '\0';
	cout << lcs << endl;

	for (int i = 0; i < strlenA; ++i)
		delete[] temp[i];
	delete[] temp;

	delete[] lcs;

	return maxLen;
}

int main()
{
	cout << "maxLen = " <<
		LongestCommonSubstring("wwwadfabcdeasdf", "wwweoruqpeorqabcdezcvnz") << endl;
	return 0;
}