月度归档：2010年07月

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序

1条回复

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序
【基本概念】
排序：排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
内排序：内排序指的是待排序记录在放在计算机随机存储器中进行的排序过程
内排序大致可分为插入排序、交换排序、选择排序、归并排序和计数排序
在排序的过程中需要进行两种基本操作：1、比较两个关键字的大小，2、将记录从一个位置移动到另一个位置
【冒泡排序过程】
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较批二个记录和第三个记录的关键字，依次类推，直至第n-1个元素和第n个元素进行过比较为止。以上为一次冒泡排序，礤结果是使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二真趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录安置到第n-1人的位置上，如此类似
【冒泡排序的PHP实现】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

<?php
/**
 * 数据结构中冒泡排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                    
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 冒泡排序 将数组从小到排序
 * @param array $array 需要排序的数据
 * @return array
 */
function bubble_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(bubble_sort($array));
?>

【简单选择排序的过程】
选择排序的基本思想是：每一趟在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录
其中最简单的是简单选择排序，其过程如下：
通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并各第i个记录交换之。
【简单选择排序的PHP实现】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

<?php
/**
 * 数据结构中简单选择排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                 
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 简单选择排序，将数组从小到大排序
 * @param array $array 需要进行排序的数组
 * @return array $array
 */
function select_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(select_sort($array));
?>

温故知新，以前对这两种排序方式一直模糊不清，总算了结了

PHP设计模式笔记：使用PHP实现策略模式

2条回复

PHP设计模式笔记：使用PHP实现策略模式

【意图】
定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换。策略模式可以使算法可独立于使用它的客户而变化
策略模式变化的是算法

【策略模式结构图】

策略模式

策略模式

【策略模式中主要角色】
抽象策略(Strategy）角色：定义所有支持的算法的公共接口。通常是以一个接口或抽象来实现。Context使用这个接口来调用其ConcreteStrategy定义的算法
具体策略(ConcreteStrategy)角色：以Strategy接口实现某具体算法
环境(Context)角色：持有一个Strategy类的引用，用一个ConcreteStrategy对象来配置

【策略模式的优点和缺点】
策略模式的优点：
1、策略模式提供了管理相关的算法族的办法
2、策略模式提供了可以替换继承关系的办法 将算封闭在独立的Strategy类中使得你可以独立于其Context改变它
3、使用策略模式可以避免使用多重条件转移语句。

策略模式的缺点：
1、客户必须了解所有的策略 这是策略模式一个潜在的缺点
2、Strategy和Context之间的通信开销
3、策略模式会造成很多的策略类

【策略模式适用场景】
1、许多相关的类仅仅是行为有异。“策略”提供了一种用多个行为中的一个行为来配置一个类的方法
2、需要使用一个算法的不同变体。
3、算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的，与算法相关的数据结构
4、一个类定义了多种行为，并且 这些行为在这个类的操作中以多个形式出现。将相关的条件分支移和它们各自的Strategy类中以代替这些条件语句

【策略模式与其它模式】
Template模式：模板方法模式与策略模式的不同在于，策略模式使用委派的方法提供不同的算法行为，而模板方法使用继承的方法提供不同的算法行为
享元模式(flyweight模式)：如果有多个客户端对象需要调用 同样的一睦策略类的话，就可以使它们实现享元模式

【策略模式PHP示例】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

 
<?php
/**
 * 策略模式的PHP简单实现 2010-07-25 sz
 * @author 胖子 phppan.p#gmail.com  http://www.phppan.com                                                  
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象策略角色，以接口实现
 */
interface Strategy {
 
    /**
     * 算法接口
     */
    public function algorithmInterface();
}
 
/**
 * 具体策略角色A
 */
class ConcreteStrategyA implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface A<br />';
    }
}
 
/**
 * 具体策略角色B
 */
class ConcreteStrategyB implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface B<br />';
    }
}
 
/**
 * 具体策略角色C
 */
class ConcreteStrategyC implements Strategy {
 
    public function algorithmInterface() {
        echo 'algorithmInterface C<br />';
    }
}
 
/**
 * 环境角色
 */
class Context {
    /* 引用的策略 */
    private $_strategy;
 
    public function __construct(Strategy $strategy) {
        $this->_strategy = $strategy;
    }
 
    public function contextInterface() {
        $this->_strategy->algorithmInterface();
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
    /**
     * Main program.
     */
    public static function main() {
        $strategyA = new ConcreteStrategyA();
        $context = new Context($strategyA);
        $context->contextInterface();
 
        $strategyB = new ConcreteStrategyB();
        $context = new Context($strategyB);
        $context->contextInterface();
 
        $strategyC = new ConcreteStrategyC();
        $context = new Context($strategyC);
        $context->contextInterface();
    }
 
}
 
Client::main();
?>

PHP设计模式笔记：使用PHP实现状态模式

3条回复

PHP设计模式笔记：使用PHP实现状态模式

【意图】
允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类
状态模式变化的位置在于对象的状态

【状态模式结构图】

状态模式

状态模式

【状态模式中主要角色】
抽象状态(State)角色：定义一个接口，用以封装环境对象的一个特定的状态所对应的行为
具体状态（ConcreteState)角色：每一个具体状态类都实现了环境（Context）的一个状态所对应的行为
环境(Context)角色：定义客户端所感兴趣的接口，并且保留一个具体状态类的实例。这个具体状态类的实例给出此环境对象的现有状态

【状态模式的优点和缺点】
1、它将与特定状态相关的行为局部化
2、它使得状态转换显示化
3、State对象可被共享

【状态模式适用场景】
1、一个对象的行为取决于它的状态，并且它必须在运行时刻根据状态改变它的行为
2、一个操作中含有庞大的多分支的条件语句，且这些分支依赖于该对象的状态。这个状态通常用一个或多个枚举常量表示。通常，有多个操作包含这一相同的条件结构。State模式模式将每一个条件分支放入一个独立的类中。这使得你可以要所对象自身的情况将对象的状态作为一个对象，这一对象可以不依赖于其他对象而独立变化

【状态模式与其它模式】
单例模式(singleton模式)：具体状态对象通常是单例模式
享元模式(flyweight模式)：享元模式解释了何时以及怎样共享状态对象

【状态模式PHP示例】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

<?php
 
/**
 * 状态模式的PHP简单实现 2010-07-25 sz
 * @author 胖子 phppan.p#gmail.com  http://www.phppan.com                                                     
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象状态角色
 */
interface State {
 
    /**
     * 方法示例
     */
    public function handle(Context $context);
}
 
/**
 * 具体状态角色A
 * 单例类
 */
class ConcreteStateA implements State {
    /* 唯一的实例 */
    private static $_instance = null;
 
    private function __construct() {
 
    }
 
    /**
     * 静态工厂方法，返还此类的唯一实例
     */
    public static function getInstance() {
        if (is_null(self::$_instance)) {
            self::$_instance = new ConcreteStateA();
        }
 
        return self::$_instance;
    }
 
    public function handle(Context $context) {
        echo 'Concrete Sate A handle method<br />';
        $context->setState(ConcreteStateB::getInstance());
    }
 
}
 
/**
 * 具体状态角色B
 * 单例类
 */
class ConcreteStateB implements State {
    /* 唯一的实例 */
 
    private static $_instance = null;
 
    private function __construct() {
    }
 
    /**
     * 静态工厂方法，返还此类的唯一实例
     */
    public static function getInstance() {
        if (is_null(self::$_instance)) {
            self::$_instance = new ConcreteStateB();
        }
 
        return self::$_instance;
    }
 
    public function handle(Context $context) {
        echo 'Concrete Sate B handle method<br />';
        $context->setState(ConcreteStateA::getInstance());
    }
 
}
 
/**
 * 环境角色
 */
class Context {
 
    private $_state;
 
    /**
     * 默认为StateA
     */
    public function __construct() {
        $this->_state = ConcreteStateA::getInstance();
    }
 
    public function setState(State $state) {
        $this->_state = $state;
    }
 
    public function request() {
        $this->_state->handle($this);
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
    /**
     * Main program.
     */
    public static function main() {
        $context = new Context();
        $context->request();
        $context->request();
        $context->request();
        $context->request();
    }
 
}
 
Client::main();
?>