背景:如果我们需要将元素划分到若干不相交的子集中,使用并查集可以快速确定某两个元素是否位于同一个子集。
并查集是一种数据结构,除了Union-Find Set,又叫做Disjoint-Set。更确切的说,它主要包含了两种操作:Find和Union。具体信息可以见维基百科:《Disjoint-set data structure 》
并查集主要包含两个操作:
Find(x):返回元素位于那个划分的子集合内。
Union(x, y):将x, y两个集合中的元素合并为一个集合。[......]
背景:如果我们需要将元素划分到若干不相交的子集中,使用并查集可以快速确定某两个元素是否位于同一个子集。
并查集是一种数据结构,除了Union-Find Set,又叫做Disjoint-Set。更确切的说,它主要包含了两种操作:Find和Union。具体信息可以见维基百科:《Disjoint-set data structure 》
并查集主要包含两个操作:
Find(x):返回元素位于那个划分的子集合内。
Union(x, y):将x, y两个集合中的元素合并为一个集合。[......]
队列(queue)是一种先进先出(FIFO)的线性表。只允许在一端进行插入,而在另一端删除元素。
允许插入的一端叫做队尾,允许删除的一端叫做队头。
双端队列(deque):限定插入和删除操作在表两端进行的线性表。
双端队列在一些限定条件下可以退化为:
(1)普通队列(只能在一端插入而另外一端删除)
(2)两个栈底相连的栈
队列 / 双端队列的定义:
由于可以在双端操作,所以肯定得有一个head,一个rear(tail)。我觉得确实用一个多的空头表示比较合适,然后[......]
堆栈与递归是相辅相成的。
比如Fibnacci数列就是递归定义:
Fib(n) = Fib(n-1) + Fib(n-2) (n>=2) Fib(0) = 0 Fib(1) = 1
Fibnacci数列:1, 1, 2, 3, 5, 8, 13, 21, ....
说到这里再写个Fibnacci的通项公公式:
然后再一个例子是书上的Ackerman函数:
转回经典的汉诺塔问题:假设有三个命名为X,Y[......]
例如对如下的表达式求值:
4+2*3-10/5,注意是有优先级顺序的。
我们首先定义算符优先关系如下表:
注意这个表和我们所掌握的算数定义不同,如+和-是的优先级关系不是同等。
其中,#为终止符。
接着,我们预定义两个辅助函数:
Precede(opr1, opr2),比较两个运算符opr1和opr2,如果opr1优先级大于opr2,返回'>',小于返回'<',相等返回'='。
我们使用两个栈模拟:OPTR存放寄存[......]
检查括号匹配,形如如下的字符串:
[([][])] 认为是匹配的。
而[(][])这种认为是不匹配的。
算法很简单,就是栈:
(1)如果是左括号([{等,直接入栈(使得原有在栈中的所有未消解的期待括号的紧迫级别下降一位)。
(2)如果是右括号,比如],则栈顶要么是与它匹配的左括号如[,否则就是括号不匹配。
(3)如果所有字符串都处理完,栈是空的,则是匹配的,否则不匹配。
代码如下:
// 1 for succ, 0 for false
int kuo[......]