标签归档:数据结构

PHP源码阅读笔记二十六:PHP快速排序源码实现的简化版本

PHP源码阅读笔记:PHP中的快速排序实现的简化版本
这段时间在复习数据结构,有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式,在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到,也许是为了兼容多种数据类型,所以其在交换及比较位置比较复杂,看起来也比较纠结,于是自己将
其中的类型全部换成int类型,得到简化版本的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
#include <stdio.h>
 
static qsort_swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
 
void qsort(int *base, int nmemb)
{
	int *begin_stack[10];
	int *end_stack[10];
	int *begin;
	int *end;
	int *seg1;
	int *seg2;
	int *seg2p;
	int loop;
	unsigned int offset;
 
	/* 使用栈而不是常见的递归实现 */
	begin_stack[0] = base;	//	开始元素位置栈,入栈
	end_stack[0]   = base + (nmemb - 1) ;	//	结束位置栈,入栈
 
	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];	//	开始位置出栈
		end   = end_stack[loop];	//	结束位置出栈
 
		while (begin < end) {
			offset = (end - begin) >> 1;	//	取中间位置
 
			qsort_swap(begin, begin + offset);	//	交换开始和中间的位置
 
			seg1 = begin;
			seg2 = end;
 
			while (1) {
				for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1);
 
				for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1);
 
				if (seg1 >= seg2)
					break;
 
				qsort_swap(seg1, seg2);
			}
 
			qsort_swap(begin, seg2);
 
			seg2p = seg2;
 
			if ((seg2p - begin) <= (end - seg2p)) {
				if (seg2p < end) {	//	右侧入栈
					begin_stack[loop] = seg2p + 1;
					end_stack[loop++] = end;
				}
				end = seg2p;
			} else {
				if (seg2p > begin) {	// 左侧入栈
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - 1;
				}	//	end if
				begin = seg2p;
			}	//	end if
		}	//	end while
	}	//	end for
 
}
int main(int argc, char *argv[])
{
	int a[10] = {14, 5, 7, 8, 2, 4, 55, 3};
	int i;
	qsort(a, 8);
	for (i = 0; i < 8;i++) 
	{
		printf("%d ", a[i]);
	}
	return 0;
}

看完后,有一个感受:强大的指针,受益非浅!

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

数据结构复习笔记:使用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实现

最近一段时间在看很基础的数据结构,本来想把一些数据结构和算法用PHP实现
但是google搜索后,发现一个使用php实现的基本的数据结构和算法,二叉树、二叉搜索树、AVL树、B树、链表和常见排序、搜索算法等等都有实现,而且全部是使用面向对象来实现的,只能膜拜。

源码地址:http://www.brpreiss.com/books/opus11/public/Opus11-1.0.tar.gz
文档地址:http://www.brpreiss.com/books/opus11/

阅读后,将其中对于二叉树及二叉排序树的实现提取出来,代码如下:

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
 
<?php
/**
 * 二叉树的定义
 */
class BinaryTree {
    protected $key = NULL;      //  当前节点的值
    protected $left = NULL;     //  左子树
    protected $right = NULL;    //  右子树
 
    /**
     * 以指定的值构造二叉树,并指定左右子树
     *
     * @param mixed $key 节点的值.
     * @param mixed $left 左子树节点.
     * @param mixed $right 右子树节点.
     */
    public function __construct( $key = NULL, $left = NULL, $right = NULL) {
        $this->key = $key;
        if ($key === NULL) {
            $this->left = NULL;
            $this->right = NULL;
        }
        elseif ($left === NULL) {
            $this->left = new BinaryTree();
            $this->right = new BinaryTree();
        }
        else {
            $this->left = $left;
            $this->right = $right;
        }
    }
 
    /**
     * 析构方法.
     */
    public function __destruct() {
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
    }
 
    /**
    * 清空二叉树.
    **/
    public function purge () {
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
    }
 
    /**
     * 测试当前节点是否是叶节点.
     *
     * @return boolean 如果节点非空并且有两个空的子树时为真,否则为假.
     */
    public function isLeaf() {
        return !$this->isEmpty() &&
            $this->left->isEmpty() &&
            $this->right->isEmpty();
    }
 
    /**
     * 测试节点是否为空
     *
     * @return boolean 如果节点为空返回真,否则为假.
     */
    public function isEmpty() {
        return $this->key === NULL;
    }
 
    /**
     * Key getter.
     *
     * @return mixed 节点的值.
     */
    public function getKey() {
        if ($this->isEmpty()) {
            return false;
        }
        return $this->key;
    }
 
 
    /**
     * 给节点指定Key值,节点必须为空
     *
     * @param mixed $object 添加的Key值.
     */
    public function attachKey($obj) {
        if (!$this->isEmpty())
            return false;
        $this->key = $obj;
        $this->left = new BinaryTree();
        $this->right = new BinaryTree();
    }
 
    /**
     * 删除key值,使得节点为空.
     */
    public function detachKey() {
        if (!$this->isLeaf())
            return false;
        $result = $this->key;
        $this->key = NULL;
        $this->left = NULL;
        $this->right = NULL;
        return $result;
    }
 
    /**
     * 返回左子树
     *
     * @return object BinaryTree 当前节点的左子树.
     */
    public function getLeft() {
        if ($this->isEmpty())
            return false;
        return $this->left;
    }
 
    /**
     * 给当前结点添加左子树
     *
     * @param object BinaryTree $t 给当前节点添加的子树.
     */
    public function attachLeft(BinaryTree $t) {
        if ($this->isEmpty() || !$this->left->isEmpty())
            return false;
        $this->left = $t;
    }
 
    /**
     * 删除左子树
     *
     * @return object BinaryTree  返回删除的左子树.
     */
    public function detachLeft() {
        if ($this->isEmpty())
            return false;
        $result = $this->left;
        $this->left = new BinaryTree();
        return $result;
    }
 
    /**
     * 返回当前节点的右子树
     *
     * @return object BinaryTree 当前节点的右子树.
     */
    public function getRight() {
        if ($this->isEmpty())
            return false;
        return $this->right;
    }
 
    /**
     * 给当前节点添加右子树
     *
     * @param object BinaryTree $t 需要添加的右子树.
     */
    public function attachRight(BinaryTree $t) {
        if ($this->isEmpty() || !$this->right->isEmpty())
            return false;
        $this->right = $t;
    }
 
    /**
     * 删除右子树,并返回此右子树
     * @return object BinaryTree 删除的右子树.
     */
    public function detachRight() {
        if ($this->isEmpty ())
            return false;
        $result = $this->right;
        $this->right = new BinaryTree();
        return $result;
    }
 
    /**
     * 先序遍历
     */
    public function preorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        echo ' ', $this->getKey();
        $this->getLeft()->preorderTraversal();
        $this->getRight()->preorderTraversal();
    }
 
    /**
     * 中序遍历
     */
    public function inorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        $this->getLeft()->preorderTraversal();
        echo ' ', $this->getKey();
        $this->getRight()->preorderTraversal();
    }
 
    /**
     * 后序遍历
     */
    public function postorderTraversal() {
        if ($this->isEmpty()) {
            return ;
        }
        $this->getLeft()->preorderTraversal();
        $this->getRight()->preorderTraversal();
        echo ' ', $this->getKey();
    }
}
 
/**
 * 二叉排序树的PHP实现
 */
 
class BST extends BinaryTree {
  /**
     * 构造空的二叉排序树
     */
    public function __construct() {
        parent::__construct(NULL, NULL, NULL);
    }
 
    /**
     * 析构
     */
    public function __destruct() {
        parent::__destruct();
    }
 
    /**
     * 测试二叉排序树中是否包含参数所指定的值
     *
     * @param mixed $obj 查找的值.
     * @return boolean True 如果存在于二叉排序树中则返回真,否则为假期
     */
    public function contains($obj) {
        if ($this->isEmpty())
            return false;
        $diff = $this->compare($obj);
        if ($diff == 0) {
            return true;
        }elseif ($diff < 0)
            return $this->getLeft()->contains($obj);
        else
            return $this->getRight()->contains($obj);
    }
 
    /**
     * 查找二叉排序树中参数所指定的值的位置
     *
     * @param mixed $obj 查找的值.
     * @return boolean True 如果存在则返回包含此值的对象,否则为NULL
     */
    public function find($obj) {
        if ($this->isEmpty())
            return NULL;
        $diff = $this->compare($obj);
        if ($diff == 0)
            return $this->getKey();
        elseif ($diff < 0)
            return $this->getLeft()->find($obj);
        else
            return $this->getRight()->find($obj);
    }
 
    /**
     * 返回二叉排序树中的最小值
     * @return mixed 如果存在则返回最小值,否则返回NULL
     */
    public function findMin() {
        if ($this->isEmpty ())
            return NULL;
        elseif ($this->getLeft()->isEmpty())
            return $this->getKey();
        else
            return $this->getLeft()->findMin();
    }
 
    /**
     * 返回二叉排序树中的最大值
     * @return mixed 如果存在则返回最大值,否则返回NULL
     */
    public function findMax() {
        if ($this->isEmpty ())
            return NULL;
        elseif ($this->getRight()->isEmpty())
            return $this->getKey();
        else
            return $this->getRight()->findMax();
    }
 
    /**
     * 给二叉排序树插入指定值
     *
     * @param mixed $obj 需要插入的值.
     * 如果指定的值在树中存在,则返回错误
     */
    public function insert($obj) {
        if ($this->isEmpty()) {
            $this->attachKey($obj);
        } else {
            $diff = $this->compare($obj);
            if ($diff == 0)
                die('argu error');
            if ($diff < 0)
                $this->getLeft()->insert($obj);
            else
                $this->getRight()->insert($obj);
        }
        $this->balance();
    }
 
 
 /**
     * 从二叉排序树中删除指定的值
     *
     * @param mixed $obj 需要删除的值.
     */
    public function delete($obj) {
        if ($this->isEmpty ())
            die();
 
        $diff = $this->compare($obj);
        if ($diff == 0) {
            if (!$this->getLeft()->isEmpty()) {
                $max = $this->getLeft()->findMax();
                $this->key = $max;
                $this->getLeft()->delete($max);
            }
            elseif (!$this->getRight()->isEmpty()) {
                $min = $this->getRight()->findMin();
                $this->key = $min;
                $this->getRight()->delete($min);
            } else
                $this->detachKey();
        } else if ($diff < 0)
                $this->getLeft()->delete($obj);
            else
                $this->getRight()->delete($obj);
        $this->balance();
    }
 
    public function compare($obj) {
        return $obj - $this->getKey();
    }
 
    /**
     * Attaches the specified object as the key of this node.
     * The node must be initially empty.
     *
     * @param object IObject $obj The key to attach.
     * @exception IllegalOperationException If this node is not empty.
     */
    public function attachKey($obj) {
        if (!$this->isEmpty())
            return false;
        $this->key = $obj;
        $this->left = new BST();
        $this->right = new BST();
    }
 
    /**
     * Balances this node.
     * Does nothing in this class.
     */
    protected function balance () {}
 
 
    /**
     * Main program.
     *
     * @param array $args Command-line arguments.
     * @return integer Zero on success; non-zero on failure.
     */
    public static function main($args) {
        printf("BinarySearchTree main program.\n");
        $root = new BST();
        foreach ($args as $row) {
            $root->insert($row);
        }
        return $root;
    }
}
 
$root = BST::main(array(50, 3, 10, 5, 100, 56, 78));
echo $root->findMax();
$root->delete(100);
echo $root->findMax();

以上代码看了几遍,有些望尘莫及的感觉
差距很大,而且还是2005年写的
再次膜拜!
EOF