青青的专栏--C/C++ OOA/D Design Pattern

给大家一个效率较高的后序遍历非递归算法（c语言编写，本算法不需要改变二叉树的结点结构）：typedef struct node  { /*二叉树的结点存储类型为链式*/    char data;    struct node *lchild,*rchild;}node,*btree;void backordertraverse(btree t)  {  /*用栈标记法（本人喜欢这样叫）*/   

[摘要]    本文介绍了启发式算法中一种重要而有效的算法------A*算法的理论，并给出了寻路问题的交互式实现。[关键词]   A*，启发式算法，最优路径，交互，AS2 [历史回顾]       P. E. Hart , N. J

<br />Combitarial search:<br />     Background:  <br />     Algorithm 比较：<br />     Backtracking<br />     prunning<br />     heuristic search:<br />     A*  search<br />     simutaneous anealing

<br />在看下面这篇文章之前，先介绍几个理论知识，有助于理解A*算法。<br /> <br />启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。<br />估价函数：从当前节点移动到目标节点的预估费用；这个估计就是启发式的。在寻路问题和迷宫问题中，我们通常用曼哈顿（manhattan）估价函数（下文有介绍）预

关于A*算法求解最短路径的问题介绍, 给出了一个搜索最短路径的程序。<br />近来不少的朋友问我关于 A* 算法的问题, 目的是写一个搜索最短路径的程序. 这个在鼠标控制精灵运动的游戏中(不算智冠出的那些用鼠标充当键盘方向键的弱智 RPG) 大量使用,尤其是即时战略类的. 但是我个人认为 A* 算法只适合处理静态路径求解, 对即时战略游戏中大量对象堵塞过道时,疏通交通很难实现(也不是不能实现, 这需要一个相当好的估价函数,且不能一次搜索路径) 我奇怪的是, A* 算法应该是算法课的基础知识了,

DFS 搜索：对一个问题的解空间用树来表示， 并且用DFS的方法来遍历这个解空间。回溯：就是DFS搜索+剪枝。尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分

作为通用解题法的回溯，虽然在方法本质上毫无高妙之处，却是解决许多NP时间复杂性问题的唯一选择。这个假期笔者接触了一些比较有代表意义的回溯题目，从一些犯下的错误中获得了一些感受，下面谈一谈我的一点粗浅的体会。一、谨慎地辨别是不是仅用贪心算法而不用回溯就可以解决问题大家知道，

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的

题目大意给出起始位置和终点位置，要求在指定的时间刚好达到终点，每移动一步为一秒钟，并且不能返回。题目分析1.     要求在指定时间内达到，唯一想法就是能不能枚举出所有的抵达方案，再通过检查时间是否吻合得到结果。这就自然得到了用 DFS 进行搜索。2.

KMP算法解决的问题是字符匹配，是由Knuth–Morris–Pratt共同开发出来的，这个算法把字符匹配的时间复杂度缩小到O（m+n）,而空间复杂度也只有O(m),n是target的长度，m是pattern的长度，在此算法在发明之前并不是没有如此高效的算法，但是原算法比较复杂。Kmp算法优雅高效，但是实现却不难理解且代码长度很短，是优秀算法设计的典范，值得拿出来仔细分析。< xmlnames

http://freelet.blogspot.com/2008/12/amortized-analysis.html在平摊分析中，执行一系列数据结构操作所需要的时间是通过执行的所有操作求平均而得出的。平摊分析可以用来证明在一系列操作中，通过对所有操作求平均之后，即使其中单一的操作具有较大的代价，平均代价还是很小的。平摊分析不牵涉到概率, 平摊分析保证在最坏情况下，每个操作具有的平

I'm "studying" this algorithmic technique: Backtracking. This is an algorithmic approach to problem solution that I trust every good Computer Scientist already uses; but taking agood theo-practica

http://bigocheatsheet.com/Know Thy Complexities!Hi there!  This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.  When preparing for techni

In my previous post related to “How HashMap works in java“, I explained the internals of HashMap class and how they fit into whole concept. But when interviewer ask you about HashMap related concept

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue AlgorithmsPseudocode from article of the above name in PODC96 (with two typos corrected), by Maged M. Michael and Michael

http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/多线程队列（Concurrent Queue）的使用场合非常多，高性能服务器中的消息队列，并行算法中的Work Stealing等都离不开它。对于一个队列来说有两个最主要的动作：添加（enqueue）和删除（dequeue）节点。在

随着多线程基础总结的增多，却明显的感觉知道的越来越少，好像转了一圈又回到了什么都不懂的起点。不过还是试着介绍一下队列的并发实现，努力尽快的驱散迷雾。队列这个数据结构已经很熟悉了，利用其先进先出的特性，多数生产消费模型的首选数据结构就是队列。对于有多个生产者和多个消费者线程的模型来说，最重要是他们共同访问的Queue是线程安全的。JDK中提供的线程安全的Queue的实现还是很丰富的：ArrayBlo

1．哈夫曼树的定义    给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 2．哈夫曼树的构造    假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为： (1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作

<br />3.1 算法思想<br /><br />和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。<br /><br />例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径，即选择此路径所经过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所要求解的问题变成：选

1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。struct link {   int da

UNLIKE INTEGERS, which are either different or equal, floating pointnumbers may be different, equal, or "close enough." This is adown-to-earth practitioners dis-cussion on how to determine, in a

排序简介 排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章介绍常用的如下排序方法，并对它们进行分析和比较。1、插入排序（直接插入排序、折半插入排序、希尔排序）；2、交换排序（起泡排序、快速排序）

Comparingfloating point numbersBruceDawsonComparingfor equalityFloatingpoint math is not exact. Simple values like 0.2 cannot be precisely representedusing binary floatin

     对于一般的二叉树来说，删去树中的一个结点是没有意义的，因为它将使以被删除的结点为根的子树变成森林，破坏了整棵树的结构但是，对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点后不改变二叉排序树的特性即可。      在二叉排序树上删除一个结点的算法如下：btree * DeleteBST(btree *b, ElemType x){  

红黑树一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：1. 每个结点或者为黑色或者为红色。2. 根结点为黑色。3. 每个叶结点(NIL)都是黑色的。4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。

二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：   1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；   2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；   3. 它的左、右子树也分别为二叉排序树。二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序

<br />倘若你去问一个木匠学徒：你需要什么样的工具进行工作，他可能会回答你：“我只要一把锤子和一个锯”。但是如果你去问一个老木工或者是大师级的建筑师，他会告诉你“我需要一些精确的工具”。由于计算机所解决的问题都是从生活中抽象出来的问题，其复杂性不言而喻，所以我们需要这样精确有效的工具去解决现实生活中的复杂问题。算法、数据结构都是程序设计中必不可少的精确工具。算法的重要性是每一个程序员都十分清楚的。 <br /><br />    程序设计当中解决得相当一部分问题都会涉及各种各样的科学计算

<br />转：动态规划与排列组合<br />2008年11月22日 星期六 下午 09:54<br />最近在学习动态规划，感觉很难彻底理解，也许这真的不是一时半会能会的。<br />有人说：DP非一日之功。我想也是，先转个帖子做启发吧。<br /><br /><动态规划与排列组合><br />原作者不详<br /><br />   1. 像所有的新手一样，对一种算法思想的理解需要经历从肤浅（流于表面形式）到逐渐触摸到本质的过程。为什么说"逐渐"触摸到本质，是因为很多时候你并不确定

我常感叹到，学计算机的人是幸福的，因为在这个领域中有如此多的通俗易懂（相对来说）的经典好书，你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了（抱怨一下），除了论文就是论文，满篇公式，晦涩坚深，真不是给人看的（虽然我也没看过几篇）。在这里列出一些我看过或者准备看的算法书籍，以供参考。1. CLRS 算法导论算法百科全书，只做了前面十几章的习题，便感觉受益无穷。2. Algorithms 算法概论短小精悍，别据一格，准经典之作。一个坏消息: 同算法导论，该书没有习题答案。好消

<br />http://blog.chinaunix.net/u/18135/article_38654.html

<br /> 转自 http://blog.csdn.net/helihui123/archive/2009/11/16/4814530.aspx<br /> <br />动态规划总结<br />写在前面的话：<br />1、本总结的题目均出自vijos动态规划分类和其他著名题库。每道例题都添加了对应的vijos题目的地址链接，可以通过ctrl+单击进入题目。读者在阅读本文以后可以将这些练习题温习以充实提高。<br />2、本文以例题为主，一些具体定义可能会有所偏差，但并不影响算法的

<br />   任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是，本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有

<br />本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。<br /><br />1.1 最优化问题<br /><br />    本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合

<br />寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于

<br />转自 http://www.cnblogs.com/tuyile006/archive/2007/06/07/774721.html<br />本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。<br /><br />2.1 算法思想<br /><br /><br />分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的

在企业里面从事大数据相关的工作到底需要掌握哪些知识呢？我认为需要从两个角度来看：一个是技术；一个是业务。技术上主要涉及到概率和数理统计，计算机系统、算法和编程等；而业务的角度呢则是因公司业务的不同而异。对于从事大数据的工程人员来说，需要学会使用数据挖掘方法在计算机系统和编程工具的帮助下解决实际的问题，这样才能够在海量数据中挖掘出业务增长的助推剂，才能在激烈的市场竞争中为企业创造更多的价值。