优先级队列（Priority Queue）是一种广泛使用的数据结构。其内部元素按照设定的关键字大小（亦可称为优先级别）出队。

使用原始的队列来实现优先级队列，虽然入队效率可以达到Θ(1)，但是出队需要对整个队列进行遍历，复杂度需要Θ(N)。

因而优先级队列一般不采用原始队列实现，转而使用堆结构(heap)，尤其是最小堆实现。

关于堆数据结构，请参考http://blog.kingsamchen.com/archives/547以及http://en.wikipedia.org/wiki/Heap_%28data_structure%29

基本操作

元素的插入-Insert

和堆排序不同，优先级队列是一个容器，元素需要依次插入。

插入算法比较简单：先将元素插入到下一个可用空间。此时在堆结构中，对应为一个叶子结点。由于元素的插入可能破坏堆特性，即：插入的元素key小于其父结点。此时从结点处向上调整，过程称为PercolateUp，上滤。

PercolateUp操作停止的断言为：{到达根结点 || 已符合堆结构}。

另外，如果堆内部数组从下标1开始存放数据，除了使得PARENT/LEFTCHILD/RIGHTCHILD的公式更简洁之外，还可以往首元素填入一个哨兵元素（元素值永远最小）用以简化PercolateUp操作，避免对是否到达根结点进行判断。

Insert操作的复杂度是O(logN)，这是最坏情况，但是实际应用中情形往往稍好。

元素获取-ExtractMin

首先，最小堆性质保证了根结点元素具有最大的优先级，所以我们只需要返回根结点的一个copy，并且删除根结点。

但是直接删除根结点会破坏整个堆，而且删起来也蛋疼（想想，的确够蛋疼的）。所以通常会用最后一个叶子的元素去取代根结点，以保持整个堆看起来还存在。

但是这种取代十有八九会破坏堆性质（除非叶子结点优先级和原先根结点相同），所以需要从根结点出向下调整，过程成为PercolateDown，下滤。

PercolateDown基本上都会将元素重新调整到最底层，所以需要临界条件的判断。

另外，PercolateDown和PercolateUp稍有不同：每一次向下一层递进，都一定要确保上浮的元素是几个元素中最小的。而这又会引发另外一个问题，父结点可能有一个孩子，可能有两个孩子。

所以Percolate实现相对较麻烦，而且也难以用哨兵。

ExtractMin的复杂度是O(logN)，而且由于下滤的特殊性，一般都会达到这个上界

扩展操作

元素查找-Find

对一种数据结构来说，查找要求是经常会发生的。比如在进程表中查找某个进程。

但是堆不像BinarySearch，并没有表现出太强的顺序性，所以查找通常之能遍历整个堆。复杂度为Θ(N)
Read the rest of this entry »

RT

好久没写Blog，写一篇凑凑数。

来自某个很无聊的“作业”，最初是让写一个简易科学计算器，为了避免做UI的麻烦，直接选择表达式求解的方式实现。

算法原型来自Lieo，经过部分改进后，支持负数和多重括号。

因为只是expression-evaluate的一个demo，所以没有写得太详细。

不支持小数，没有异常处理，包括除数为零。

这里说下算法：

首先需要有两个堆栈或者支持FILO性质的线性表（我用的是vector，便于调试时观察内部元素是否正确），分别保存操作数和操作符。

负数通过额外的符号位实现，并规定，操作符后面跟着的“-”表示负号，符号位逻辑求反。

遍历表达式时，如果碰到操作数，直接入操作数栈。碰到操作符op，先和操作符栈顶的元素比较优先级，如果优先级大于栈顶元素，入栈（如果操作符栈为空，直接入栈），否则取出操作符栈顶元素和操作数进行计算，一直到操作符栈空或者栈顶元素优先级小于操作符op。

对于括号特殊处理：

碰到“(”，直接入栈，碰到“)”，取出操作符栈和操作数栈计算，直到操作符栈中弹出“(”。

为了简化算法，表达式尾部需要有#符号充当哨兵元素，并规定#符号的优先级最小。

提供核心代码，全部代码请翻看SRC

#define pop(x) x.back(); \
				x.pop_back();

struct NumData
{
	NumData() : signal(false), pos(0)
	{
		wmemset(sz, L'\0', NUM_LEN);
	}

	enum{NUM_LEN = 10};
	wchar_t sz[NUM_LEN];
	bool signal;
	unsigned int pos;
};

int EvaluateExpression(wchar_t* pszExpression)
{
	stackOperand oprand;
	stackOperator oprator;
	bool isNumbericMode = true;
	NumData data;

	for (wchar_t* p = pszExpression; *p != NULL; ++p)
	{
		if (*p >= L'0' && *p <= L'9')
		{
			data.sz[data.pos++] = *p;
			isNumbericMode = false;
		}
		else if (L'-' == *p && isNumbericMode)
		{
			data.signal = !data.signal;
		}
		else	// pure operators
		{
			isNumbericMode = true;

			if (L'(' == *p)
			{
				oprator.push_back(*p);
			}
			else if (L')' == *p)
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					wchar_t op = pop(oprator);

					if (L'(' == op)
					{
						oprand.push_back(num);
						break;
					}
					else
					{
						int num2 = pop(oprand);
						num = Calculate(num2, num, op);
					}

				} while (true);
			}
			else	// operators except ( and )
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					if (oprator.empty() || (GetPriority(*p) > GetPriority(oprator.back())))
					{
						oprand.push_back(num);
						oprator.push_back(*p);

						break;
					}
					else
					{
						int num2 = pop(oprand);
						wchar_t op = pop(oprator);

						num = Calculate(num2, num, op);
					}

				} while (true);
			}

			//DumpStack(oprand);
		}
	}

	return oprand.back();
}

int FormatNumtoInt(NumData& data)
{
	assert(data.pos);

	int num = _wtoi(data.sz);
	num = data.signal ? -num : num;

	wmemset(data.sz, L'\0', NumData::NUM_LEN);
	data.pos = 0;
	data.signal = false;

	return num;
}

Download EvaluateExpression SRC

散列表（Hash Table）又称哈希表，是一种仅支持少数几种字典操作的表。其支持的操作有：Insert、Delete和Find

使用散列表的原因在于，对散列表中元素进行查找的期望效率很高，通常复杂度在O(1)

一、直接寻址表

在介绍散列表前，我们先介绍一种更高效的表：直接寻址表（Direct Addressing Table，DAT）

DAT查找的高效性在于采用的直接寻址技术（Direct Addressing），可以看作散列表的前身

设存在一些取自全域U的关键字元素k，即

此时n是一个不大的数，且规定

可以建立一个直接寻址表T[0...n-1]（可利用数组实现）。若关键字k在表中，则必有T[k]=k，否则T[k]=NIL

易知，DAT的各种操作效率很高，时间复杂度可以达到O(1)，但是局限性比较大

二、散列表

对于DAT来说，如果关键字全域U很大，那么实现一个大小为|U|的DAT就不太现实，且如果用到的关键字域|K|<<|U|，就会造成巨大的空间浪费

而利用散列表（Hash Table，HT），则可以保持查找期望复杂度为O(1)的情况下，是空间复杂度降低至O(|K|)

在DAT中，关键字k被存在T[k]中，而在HT中，关键字k保存在T[h[k]]中。其中，h(k)被称为散列函数（hash function），h(k)称为散列值(hash code)

散列函数h(k)利用关键字k,计算出k在HT中的位置，进而存储k

在HT中，有时会发生不同的关键字k得到相同的散列值的情况，即

这一情况称为碰撞（collision），后文对碰撞和解决碰撞的方法进行分析

三、散列函数

事实上，散列函数的好坏直接决定了散列表的性能，因为好的散列函数可以很大程度上降低碰撞发生的概率

在理想情况下，一个好的散列函数应满足每个关键字元素k映射到表的n个位置中是等可能发生的，且关键字之间各自独立，这个称为一致散列假设

但在实际情况中，这个假设很难成立，我们只能构造某些近似满足的情况

（1）求模取余散列法

使用求模取余散列法可能首先需要利用准备函数p(k),将关键字转化为自然数k

通过对关键字k进行模m操作来计算散列值（m为散列表大小），表达式为

此处h(k)应注意对m值的选取，由众多科学家及数学家的分析推导，m应取与2的整数次幂不太接近的一个素数
Read the rest of this entry »

一、概述

树是一种重要的数据结构，而二叉树则是树中重要的一类

二叉树是特殊的树，最明显的特点在于，每个结点都有左子结点和右子结点，且二者有序不能随意互换。

二叉树有两种特殊形式：满二叉树和完全二叉树，而且都具有一定的性质，具体参照偶之前写过《堆和堆排序》的文章

二叉树的重点是结点，通常存在二叉链接和三叉链接两种结点，区别在于三叉链接多了一个指向父结点的指针，因而三叉链接结点在遍历时比二叉具有优势。二叉与三叉结点适用于不同的场合和需求。

如无特殊说明，本文采用的是二叉结点

二、二叉树的建立

在堆中，我们利用数组来构建二叉树（完全二叉树）。但是如果用数组来表示一般的二叉树，则会造成内存空间的极度浪费。

所以，通常情况下，我们通过链表来建立二叉树。

和遍历类似，建立二叉树也有不同的方法，其建立的结果自然也有所不同。用的比较多的有“按顺序建立二叉树”、“从已有数据建立完全二叉树”等等。但是无论哪种方法，本质都需要通过递归实现。

本文的范例采用的是建立完全二叉树，因而需要了解一些与完全二叉树有关的数学性质

template<typename T>
struct TreeNode
{
	T Data;
	TreeNode<T>* pLeftNode;
	TreeNode<T>* pRightNode;
};

template<typename T>
CBinTree<T>::CBinTree(const T ary[], int nCount)
{
	CreateBinTree(m_pRoot, ary, 0, nCount - 1);
}

template<typename T>
void CBinTree<T>::CreateBinTree(TreeNode<T>*& pNode, const T ary[], int i, int nIdxMax)
{
	pNode = new TreeNode<T>;
	_ASSERT(m_pRoot != NULL);

	// zero-based
	int nLeftIdx = (i << 1) + 1;
	int nRightIdx = (i + 1) << 1;

	pNode->Data = ary[i];

	// if leftchild is empty, rightchild is empty too
	if (nLeftIdx <= nIdxMax)
	{
		CreateBinTree(pNode->pLeftNode, ary, nLeftIdx, nIdxMax);

		if (nRightIdx <= nIdxMax)
		{
			CreateBinTree(pNode->pRightNode, ary, nRightIdx, nIdxMax);
		}
		else
		{
			pNode->pRightNode = NULL;
		}
	}
	else
	{
		pNode->pLeftNode = NULL;
		pNode->pRightNode = NULL;
	}
}

三、二叉树的遍历

二叉树的遍历方法有多种，最常用的有中序遍历、先序遍历和后序遍历。毫无例外，这三种遍历方法都是基于递归/迭代的思想

为了更好的说明三种遍历，结合图片。
Read the rest of this entry »

栈（stack）和队列（queue）是最常见的线性表数据结构之一，用途十分广泛。而且可以使用数组或者链表作为其存储容器

1.栈

栈是一种先进后出（First-In-Last-Out FILO）的数据结构。数据进入栈的操作称为“压栈（Push）”，而出栈的操作称为“出栈（Pop）”。

FILO线性表的特点是：存取元素的操作只在一段进行。即：先压栈的元素必定后出栈。

就好象常见的桶装饼干，最底层的饼干一定是最先装进去的，而我们先拿出来吃的饼干，则是最后装入的。

栈的最顶部称为栈顶，压栈和出栈都在这里进行。而底部由于没有什么大用途，所以也没有赋予特定的名称

如图，是一个栈的简单示意图

栈的应用包括函数的调用以及回文识别等等。

2.栈的实现

为了方便使用，在C++中，我们设计一个CStack类，通过这个类来操作堆栈。如你所见，这个类是模板类

关于模板函数和模板类，请参见模板函数和模板类
Read the rest of this entry »

1.什么是堆

这里的堆（二叉堆），指得不是堆栈的那个堆，而是一种数据结构。

堆可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

如下图，是一个堆和数组的相互关系

二叉堆一般分为两种：最大堆和最小堆。两种堆内部的数据都要满足自己的特点。

比如最大堆的特点是，每个父节点的元素值都不小于其孩子结点（如果存在）的元素值，因此，最大堆的最大元素值出现在根结点（堆顶）

最小堆的性质与最大堆恰好相反

由于堆排序算法使用的是最大堆，所以我们这里以最大堆为例，最小堆情况类似，可以自己推导

对于给定的某个结点的下标i，可以很容易的计算出这个结点的父结点、孩子结点的下标，而且计算公式很漂亮很简约

但是这里有一个很大的问题：目前主流的编程语言中，数组都是Zero-based，这就意味着我们的堆数据结构模型要发生改变
Read the rest of this entry »

自从OO（Object-Oriented）出现之后，随着思想模型的逐步确立和SE开发的需要，泛型编程开始并逐渐成为一种重要的编码手段。

使用泛型的好处是，可以将源程序的具体行为和具体的类型无关，最终的类型确定要到最后阶段的绑定。这有点像类中的多态。

而模板是泛型编程的基础，很难想象没有模板的泛型会成为啥样子。

本文旨在帮助你了解熟悉并掌握如何编写自己简单的模板函数和模板类

1.模板是什么

其实，如过你本身对C++没有什么了解，我很难告诉你什么是模板……

模板在语言中的意思大致是“生产一类具有相同功能的模子和器具”，比如民间传统手工作品中制作泥塑的模子，当你把一坨像shit一样的泥巴放入泥塑模子中，然后经过一堆工序，最终出来的就是特定的泥塑作品了。而C++中的模板也有如此的作用。

如果你用过STL中的容器，就可能会接触过vector/deque/lis/map等容器，他们都是利用模板特性设计的。而这些容器的好处是，好多好多的类型都可以通吃而不会产生消化不良的症状。

2. 为什么要用模板

这是一个很有趣的问题，也是一个很严肃的问题。

在还是C的时代，数据结构重用是很让程序员头疼的一个问题，比如你写了一个以int为操作类型的堆栈，那么这个堆栈是不能用来操作char甚至是double(不考虑类型转换)。如果你需要操作其他类型的堆栈，那么基本上只能重写一次了。

所以通常Coder们都用ElementType来代替具体的类型，然后在使用这个数据结构的文件的某处写上typedef int ElementType

俗话说，躲得过初一，躲不过十五，于是新的问题随之而来，这样的做法不能在一个文件中同时对两种数据类型生效。
Read the rest of this entry »