2013-11-27

Shell

sed and awk

list文件内容：
$ cat list
John Daggett, 341 King Road, Plymouth MA
Alice Ford, 22 East Broadway, Richmond VA
Orville Thomas, 11345 Oak Bridge Road, Tulsa OK
Terry Kalkas, 402 Lans Road, Beaver Falls PA
Eric Adams, 20 Post Road, Sudbury MA
Hubert Sims, 328A Brook Road, Roanoke VA
Amy Wilde, 334 Bayshore Pkwy, Mountain View CA
Sal Carpenter, 73 6th Street, Boston MA

将 MA替换成, Massachusetts:

$ sed 's/ MA/, Massachusetts/' list
John Daggett, 341 King Road, Plymouth, Massachusetts
Alice Ford, 22 East Broadway, Richmond VA
Orville Thomas, 11345 Oak Bridge Road, Tulsa OK
Terry Kalkas, 402 Lans Road, Beaver Falls PA
Eric Adams, 20 Post Road, Sudbury, Massachusetts
Hubert Sims, 328A Brook Road, Roanoke VA
Amy Wilde, 334 Bayshore Pkwy, Mountain View CA
Sal Carpenter, 73 6th Street, Boston, Massachusetts

Sed 参数总结：

-e	后接命令
-f	后接脚本文件名
-n	阻止自动输出

{print $1}表示打印第一个字段到标准输出，字段是以空格或者制表符分割的；$1表示一个字段，
$2表示第二个字段，$3表示第三个字段，...以此类推。$0表示所有字段。
$ awk '{print $1}' list
John
Alice
Orville
Terry
Eric
Hubert
Amy
Sal

打印包含MA的行
$ awk '/MA/' list
John Daggett, 341 King Road, Plymouth MA
Eric Adams, 20 Post Road, Sudbury MA
Sal Carpenter, 73 6th Street, Boston MA

打印包含MA的所有行的第一个字段：
$ awk '/MA/ { print $1 }' list
John
Eric
Sal

awk的-F参数可以设定字段分隔符：

将字段分隔符改为`,`，然后打印第一个字段：
$ awk -F, '/MA/{print $1}' list
John Daggett
Eric Adams
Sal Carpenter

awk还可以同时处理多个命令，他们之间有分号;隔开：

打印1，2，3字段
$ awk -F, '{ print $1; print $2; print $3 }' list
John Daggett
 341 King Road
 Plymouth MA
Alice Ford
 22 East Broadway
 Richmond VA
Orville Thomas
 11345 Oak Bridge Road
 Tulsa OK
Terry Kalkas
 402 Lans Road
 Beaver Falls PA
Eric Adams
 20 Post Road
 Sudbury MA
Hubert Sims
 328A Brook Road
 Roanoke VA
Amy Wilde
 334 Bayshore Pkwy
 Mountain View CA
Sal Carpenter
 73 6th Street
 Boston MA

awk 参数总结：

-F	后接字段分隔符
-f	后接脚本文件名
-v	后接var=value

可以使用管道操作将sed与awk联合起来操作文本：
假设sedscript脚本的内容是

$ cat sedscript
s/ MA/, Massachusetts/
s/ PA/, Pennsylvania/
s/ CA/, California/
s/ VA/, Virginia/
s/ OK/, Oklahoma/

那么我们可以使用如下命令来打印州名：

$ sed -f sedscript list | awk -F ', ' '{print $4}'
Massachusetts
Virginia
Oklahoma
Pennsylvania
Massachusetts
Virginia
California
Massachusetts

2013-11-25

数据结构与算法

数据结构学习

一些数学知识：

$$
x^ax^b = x^{a+b}
$$
$$
\frac{x^a}{x^b} = x^{a-b}
$$
$$
(x^a)^b = x^{ab}
$$
$$
x^n + x^n = 2x^n \ne x^{2n}
$$
$$
2^n + 2^n = 2^{n+1}
$$
$$
x^a = b => \log_x b = a
$$
$$
\log_a b = \frac{\log_c b} {\log_c a}
$$
$$
\log {ab}= \log a+ \log b
$$
$$
\log a/b = \log a- \log b
$$
$$
\log a^b = b\log a
$$
$$
\log x < x (x > 0)
$$
$$
\sum_{i=0}^n 2^i = 2^{n + 1} -1
$$
$$
\sum_{i=0}^n a^i = \frac{a^{n+1}-1} {a-1}
$$
$$
\sum_{i=1}^N i^2 = \frac{N(N+1)(2N+1)} 6 \approx \frac {N^3} 3
$$
$$
\sum_{i=1}^N i^k \approx \frac {N^{k+1}} {| {k+1} | }(k\ne-1)
$$

二叉树

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有
$$
2^{i-1}
$$
个结点；深度为k的二叉树至多有
$$
2^{k-1}
$$
个结点；对任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则
$$
n_0=n_2+1
$$

完全二叉树和满二叉树

满二叉树：一棵深度为k，且有2^k-1个节点成为满二叉树
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中序号为1至n的节点对应时，称之为完全二叉树

二叉查找树

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。

AVL树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。
查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

AVL平衡二叉树的实现：

avl.h:

#ifndef _AVL_H
#define _AVL_H
typedef struct node *Position;
typedef Position AVLtree;

typedef struct node
{
	int height;
	AVLtree left;
	AVLtree right;
	int data;
}node;

int Height(Position p); //return the height of a node
Position SingleRotateWithRight(Position k2); //left rotate when in RR operation
Position SingleRotateWithLeft(Position k2); // LL
Position DoubleRotateWithLeft(Position k3); // LR
Position DoubleRotateWithRight(Position k3); // RL
Position Rotate(Position k);
AVLtree insert(AVLtree root, int data); //Insert operation
Position search(AVLtree root, int data);
AVLtree delete(AVLtree root, int data);
void inorder_print(AVLtree root);
void dispose(AVLtree root); //free the tree
#endif

avl.c:

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#include "avl.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
	AVLtree root = NULL;
	char choice;
	printf("Welcome to the AVL tree program\n");
	while (1) {
		printf("Please make a choice\n");
		printf("----------------------\n");
		printf("i. insert an element\n");
		printf("p. print the tree\n");
		printf("d. delete an element from the tree\n");
		printf("f. find an element \n");
		printf("q. quit the program\n");
		printf("----------------------\n");

		/*get rid of '\n' in buffer*/
		if ((choice = getchar()) == '\n')
			choice = getchar();

		int number;
		Position p;
		switch (choice) {
			case 'i':
				printf("Which number to insert?\n");
				scanf("%d", &number);
				root = insert(root, number);
				break;
			case 'p':
				printf("The tree is \n");
				printf("######################\n");
				inorder_print(root);
				printf("######################\n");
				break;
			case 'd':
				printf("Which number to delete?\n");
				scanf("%d", &number);
				root = delete(root, number);
				break;
			case 'f':
				printf("Which number to find?\n");
				scanf("%d", &number);
				if (p = search(root, number)) {
					printf("%d is found\n", number);
				}
				else
					printf("Not found\n");
				break;
			case 'q':
				printf("Byebye!\n");
				dispose(root);
				goto QUIT;
			default:
				printf("Wrong choice! Please try again\n");
				break;
		}
	}
	QUIT: return 0;
}

int Height(Position p) {
	if (p == NULL)
		return -1;
	else
		return p->height;
}

Position SingleRotateWithRight(Position k2) {
	Position k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;

	k1->height = MAX(Height(k1->left), Height(k1->right)) + 1;
	k2->height = MAX(Height(k2->left), Height(k2->right)) + 1;
	return k1;
}

Position SingleRotateWithLeft(Position k2) {
	Position k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;

	k2->height = MAX(Height(k2->left), Height(k2->right)) + 1;
	k1->height = MAX(Height(k1->left), Height(k1->right)) + 1;
	return k1;
}

Position DoubleRotateWithLeft(Position k3) {
	k3->left = SingleRotateWithRight(k3->left);
	return SingleRotateWithLeft(k3);
}

Position DoubleRotateWithRight(Position k3) {
	k3->right = SingleRotateWithLeft(k3->right);

	return SingleRotateWithRight(k3);
}

Position Rotate(Position k) {
	if (Height(k->left) - Height(k->right) == 2) {
		if (Height(k->left->left) >= Height(k->left->right)) {
			k = SingleRotateWithLeft(k);
		}
		else {
			k = DoubleRotateWithLeft(k);
		}
	}

	if (Height(k->right) - Height(k->left) == 2) {
		if (Height(k->right->right) >= Height(k->right->left)) {
			k = SingleRotateWithRight(k);
		}
		else {
			k = DoubleRotateWithRight(k);
		}
	}

	return k;
}

AVLtree insert(AVLtree root, int data) {
	if (root == NULL) {
		/*if the tree is empty then create a node*/
		root = (node*)malloc(sizeof(node));
		root->left = root->right = NULL;
		root->data = data;
		root->height = 0;
	}

	else if (data < root->data) {
		root->left = insert(root->left, data);
		if (Height(root->left) - Height(root->right) == 2) {
			if (data < root->left->data) {
				root = SingleRotateWithLeft(root);
			}
			else {
				root = DoubleRotateWithLeft(root);
			}
		}
	}
	else if (data > root->data) {
		root->right = insert(root->right, data);
		if (Height(root->right) - Height(root->left) == 2) {
			if (data > root->right->data) {
				root = SingleRotateWithRight(root);
			}
			else {
				root = DoubleRotateWithRight(root);
			}
		}
	}
	else {
		/*data already exsits*/
		fprintf(stderr, "%d exsits\n", data);
	}

	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

Position search(AVLtree root, int data) {
	if (root == NULL) {
		return root;
	}

	if (root->data == data)
		return root;
	else if (root->data < data) {
		return search(root->right, data);
	}
	else {
		return search(root->left, data);
	}
}

AVLtree delete(AVLtree root, int data) {
	if (root == NULL) {
		fprintf(stderr, "Not found\n");
		return NULL;
	}

	else if (data == root->data) {
		if (root->right == NULL) {
			/*if right child is NULL then delete it*/
			Position temp = root;
			root = root->left;
			free(temp);
			printf("%d is deleted\n", data);
		}
		else {
			Position temp = root->right;
			while (temp->left) {
				temp = temp->left;
			}

			root->data = temp->data;
			root->right = delete(root->right, temp->data);
			root->height = MAX(Height(root->left), Height(root->right)) + 1;
			printf("%d is deleted\n", data);
		}

		return root;
	}

	else if (data < root->data) {
		root->left = delete(root->left, data);
	}
	else {
		root->right = delete(root->right, data);
	}

	if (root->left) {
		root->left = Rotate(root->left);
	}
	if (root->right) {
		root->right = Rotate(root->right);
	}

	root = Rotate(root);
	root->height = MAX(Height(root->left), Height(root->right)) + 1;

	return root;
}

void inorder_print(AVLtree root) {
	if (root != NULL) {
		inorder_print(root->left);
		printf("%d\n", root->data);
		inorder_print(root->right);
	}
}

void dispose(AVLtree root)
{
    if( root != NULL )
    {
        dispose( root->left );
        dispose( root->right );
        free( root );
    }
}

B树

A B-tree of order m is an m-way tree (i.e., a tree where each node may have up to m children) in which:

the number of keys in each non-leaf node is one less than the number of its children and these
keys partition the keys in the children in the fashion of a search tree
all leaves are on the same level
all non-leaf nodes except the root have at least ceil(m / 2) children
the root is either a leaf node, or it has from two to m children
a leaf node contains no more than m – 1 keys

Hash表

散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

Hash表处理碰撞

为了知道碰撞产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对碰撞结果进行处理。而不发生碰撞的可能性是非常之小的，所以通常对碰撞进行处理。常用方法有以下几种：

开放寻址法（open addressing）：

$$
hash_i=(hash(key)+d_i) \,\bmod\, m, i=1,2…k\,(k \le m-1)
$$

其中hash(key)为散列函数，m为散列表长，
$d_i$为增量序列，$i$为已发生碰撞的次数。增量序列可有下列取法：

$$
d_i=1,2,3…(m-1)
$$

称为线性探测；即 $d_i=i$ ，或者为其他线性函数。
相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。

$$
d_i=\pm 1^2, \pm 2^2,\pm 3^2…\pm k^2 (k \le m/2)
$$
称为平方探测。相对线性探测，
相当于发生碰撞时探测间隔 $d_i=i^2$ 个单元的位置是否为空，如果为空，将地址存放进去。

$d_i=$伪随机数序列，称为伪随机探测。

Hash表载荷因子

散列表的载荷因子定义为：
$\alpha = $填入表中的元素个数 / 散列表的长度。$\alpha$是散列表装满程度的标志因子。

由于表长是定值，载荷因子与“填入表中的元素个数”成正比，所以，载荷因子越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，载荷因子越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子载荷因子的函数，只是不同处理冲突的方法有不同的函数。

对于开放寻址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放寻址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

To be continued…

2013-11-16

编程语言

PHP Notes

PHP 中的所有函数和类都具有全局作用域，而且函数和类可以在其声明之前调用，即函数和类声明会被提到作用域顶部(hoisted)。（注意：如果函数是定义在其他文件中，则必须先require进来而且require必须在调用之前。）而且嵌套的函数可以访问外围函数。下面这段代码是可以正确运行的：

<?php
foo();
function foo() {
	echo "Hello World!";
}

$bar = new Bar();
echo $bar->a;

class Bar {
	public $a = 1;
}
?>
//输出 Hello World!1

再看下面的例子：

<?php
function out($value='25')
{
	echo "$value<br />";
}

function test() {
	function inner() {
		echo "I am inner function<br />";
		function innermost() {
			out();
			inner();
		}
	innermost();
	}

	inner();
}

test();
?>
/***
输出结果为：
I am inner function
25
I am inner function
*/

静态变量可以分为：

1.静态全局变量，PHP中的全局变量也可以理解为静态全局变量，因为除非明确unset释放，在程序运行过程中始终存在。

2.静态局部变量，也就是在函数内定义的静态变量，函数在执行时对变量的操作会保持到下一次函数被调用。

3.静态成员变量，这是在类中定义的静态变量，和实例变量相对应，静态成员变量可以在所有实例中共享。

最常见的是静态局部变量及静态成员变量。局部变量只有在函数执行时才会存在。通常，当一个函数执行完毕，它的局部变量的值就已经不存在，而且变量所占据的内存也被释放。当下一次执行该过程时，它的所有局部变量将重新初始化。如果某个局部变量定义为静态的，则它的值不会在函数调用结束后释放，而是继续保留变量的值。

来看下面的例子：

<?php
function &test() {
	static $a = 1;
	return ++$a;
}
$b = &test();
echo $b; //2
echo test(); //3
$b = 10;
$c = test();
echo $c; //11
echo $b; //11

/*
static变量在函数内部只初始化一次，而且函数执行完毕后其值不会释放。第一次调用test()时返回值为2，
所以echo $b显示2；第二次调用test()时则返回3；如果将$b的值改为10，注意函数test()前有个&符号，
在PHP中表示引用，变量$b是函数test()的引用，所以当$b的值改变时，它将改变return那个变量($a)的初始值，
所以返回11；函数调用也会改变$b的值，所以$b变为11。（注：如果返回值是个表达式则$b不会影响其值）
*/
?>

exit()/die()用于中止脚本的执行。

即脚本执行到exit()或die()那一行为止，如果在被包含文件中使用exit()或die()，则同时会中断包含文件的脚本执行。（但在exit()或die()之后声明的函数或类则可以被调用，因为它们会被hoisted到作用域顶部，见上面）

test.php:
<?php
echo 1;
test();
$b = new Bar();
echo $b->a;
require 'test1.php';
echo 5;

function test()
{
	echo "hello";
}

/**
 *
 */
class Bar {
	public $a = 9;
}

?>

test1.php:
<?php
echo 2;
require 'test2.php';
echo 4;
?>

test2.php
<?php
echo 3;
exit("Nothing!");
?>

/*显示结果为：1hello923Nothing!*/

声明类属性或方法为静态，就可以不实例化类而直接访问。静态属性不能通过一个类已实例化的对象来访问（但静态方法可以）。
urlencode()和rawurlencode()

返回字符串，此字符串中除了-_. 之外的所有非字母数字字符都将被替换成百分号（%）后跟两位十六进制数，urlencode()将空格则编码为加号（+），而rawurlencode()将空格编码为%20。
在编码时应该只对部分URL编码，否则URL中的冒号和反斜杠也会被转义。

htmlentities 与 htmlspecialchars 的差別

两者都会转换以下符号：

& (ampersand) : &

" (double quote) : "

'(single quote) : '' 或者 '

<(less than) : <

>(greater than) : >

htmlspecialchars 只转换以上的 HTML 符号
htmlentities 除了转换以上的 HTML 符号, 也转换中文
两者都不会转换英文、数字、括号及分号
htmlspecialchars 速度比 htmlentities 快
静态成员变量通过继承在子类和父类中共享，子类可以改变父类中静态变量的值。

<?php
class foo
{
    public static $id = 1;
}

class bar extends foo
{

}

echo foo::$id; // 1
echo bar::$id; // 1

bar::$id = 2;

echo foo::$id; // 2
echo bar::$id; // 2
?>

PHP_INI_* 模式的定义

PHP_INI_USER 可在用户脚本（例如 ini_set()）或 Windows 注册表（自 PHP 5.3 起）以及 .user.ini 中设定
PHP_INI_PERDIR 可在 php.ini，.htaccess 或 httpd.conf 中设定
PHP_INI_SYSTEM 可在 php.ini 或 httpd.conf 中设定
PHP_INI_ALL 可在任何地方设定

Passion of life

I am a dreamer

sed and awk

数据结构学习

一些数学知识：

PHP Notes