定义它的存储结构，典型的二叉树，只是多了一个权值。 ~~~ typedef struct { int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree; typedef char **HuffmanCode; ~~~ HuffmanCode是一个字符串数组，用来保存叶子结点最终的编码结果。 存储空间是多少呢? 从前一章讲的构造赫夫曼树的过程可以找出规律，n个叶子结点所构造的赫夫曼树共有2n-1个结点，这就是我们要分配的空间。 ~~~ int m = 2 * n - 1; *HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//多分配一个空间，0号不用 ~~~ 函数的接口形式如下: ~~~ bool HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n) ~~~ HT是最终构造的赫夫曼树，是个输出参数，HC也是个输出函数，就是个字符串数组，输出最终的编码。W存放n个叶子结点的权值，当然都是大于0的整数，n是叶子结点的个数, 最后这两个都是输入参数。 构造赫夫曼树的过程代码其实很简单: ~~~ //构建赫夫曼树 for (i = n + 1; i <= m; i++) { if (!Select(*HT, i - 1, &s1, &s2)) return false; (*HT)[s1].parent = i; (*HT)[s2].parent = i; (*HT)[i].lchild = s1; (*HT)[i].rchild = s2; (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight; } ~~~ select函数从HT[1...nEnd]中选出parent为0, 并且weight最小的两个结点，序号分别由s1 和 s2返回，它的实现如下: ~~~ static bool Select(HuffmanTree HT, int nEnd, int *s1, int *s2) { int i = 0; int nComp = 0; nComp = MAX; *s1 = MAX; *s2 = MAX; //第一轮循环，找到最小的给s1 for (i = 1; i <= nEnd; i++) { if ((HT[i].weight < nComp) && (HT[i].parent == 0)) { nComp = HT[i].weight; *s1 = i; } } //第二轮循环，找到次小的给s2 nComp = MAX; for (i = 1; i <= nEnd; i++) { if ((HT[i].weight < nComp) && (i != *s1) && (HT[i].parent == 0)) { nComp = HT[i].weight; *s2 = i; } } if ((*s1 == MAX) || (*s2 == MAX)) { return false; } return true; } ~~~ 编码的结果是保存在HC中的，为了方便采用逆向保存的形式，即从叶子到根求编码，然后输出时就是正向的了。 ~~~ for (i = 1; i <= n; i++) { start = n - 1; for (c = i, f = (*HT)[i].parent; f != 0; c = f, f = (*HT)[f].parent) { //左0右1 if ((*HT)[f].lchild == c) { cd[--start] = '0'; } else { cd[--start] = '1'; } } (*HC)[i] = (char *)malloc((n - start)); strcpy((*HC)[i], &cd[start]); } ~~~ 代码下载地址: http://download.csdn.net/detail/pony_maggie/8209175 或 https://github.com/pony-maggie/HuffmanCode

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/41594015 作者:小马 **一什么是赫夫曼树** 赫夫曼树是指带权路径最短的树，从根结点到叶子结点所经过的结点数(不包括根结点，包括叶子结点)叫路径，如果给叶子结点赋予权值，那么路径和权值的乘积就是访问该叶子结点的代价，对于一棵树来讲，使访问所有的叶子结点的代价最小的树，就是赫夫曼树。 比如下面三个图:  可以计算它们的带权路径长度，分别为 (a)    图是36 (b)    图是46 (c)    图是 35 所以c图是赫夫曼树。 **二如何构造赫夫曼树** 构造一棵赫夫曼树的步骤其实不复杂，简单来讲就是权值大的尽量靠近根结点，而且是越大的越靠近。这样得出的效果是权值越大的结点，可以经过相对较少的距离到达，从而使程序的效率提高。这里的所说的效率，即包括时间上也包括空间上，后面我会讲到两个应用例子，分别就是一个时间上的优化，一个空间上的优化。 赫夫曼本人给了一个基本的算法，如下: (1) 将w1、w2、…，wn看成是有n 棵树的集合F(每棵树仅有一个根结点)； (2) 在这些树中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从F中删除选取的两棵树，并将新树加入F (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树 **三应用举例** 了解的具体的算法之后，必须要知道它的应用场景，不然也就只能停留在理论阶段了。这里给出两个应用的例子。 比如统计一次考试中的学生成绩，划分为5个等级，60分以下为不及格，60到70之间是及格，70到80之间是中等，80到90之间是良好，90到100之间是优秀。本次考试各个阶段学生所占比例如下: | 分数 | 0-59 | 60-69 | 70-79 | 80-89 | 90-100 | |-----|-----|-----|-----|-----|-----| | 比例 | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 | 假设有10000个学生，然后我们用下面的代码来实现统计： ~~~ if (a < 60) b = "不及格"; else if (a < 70) b = "及格"; else if (a < 80) b = "中等"; else if (a < 90) b = "良好"; else b = "优秀"; ~~~ 代码对应的树结构如下:  这样一共需要比较30000多次。上面的代码不管你的分数是多少，总要从小于60开始比较，比如一个学生的成绩是85，他要被比较四次才能有结果，不幸的是, 大部分学生的成绩都是在70到90之间，都要经过至少三次以上的比较才能完成。 如果我们能把这个占大多数人的分数区间放在前面，不就可以大大减少比较的次数了吗？先按照前面章节讲的步骤构造一棵赫夫曼树，如下图:  对应的代码是: ~~~ if (a >= 70 && a < 80) b = "中等"; else if (a >= 80 && a < 90) b = "良好"; else if (a >= 60 && a < 70) b = "及格"; else if (a < 60) b = "不及格"; else b = "优秀"; ~~~ 这样比较的次数变为22000次，大大提高效率。 再来一个应用的例子。 电报传送时，一般要把字符转成二进制的编码，比如一串字符, “ABACCDA”, 四种字符，可以用二位表示一种，比如A是00, B是01, C是10, D是11，那么电报发送的就是00010010101100，对方收到电报时可以两位一组解出来。 上面的方法没有什么问题，但是一般传送电报肯定希望能用最短的长度传递尽量多的信息，是不是还可以优化呢。当然，我们用不同长度的编码来表示这些字符，出现次数多的字符尽可能的短，出现次数少的可以偏长一些，这样可以构造出一个比上面更短的电报编码。 上面的字符信息，A和C现的次数较多，分别为两次和三次，B和D都是一次。按照上面的方法来构造一棵赫夫曼树，如下:  规则是左0右1, 这样，A是0, B是110, C是10, D是111, 最后的编码是0110010101110, 一共是13个bit位，原来是14个bit位，确实变短了。 再来看看电报接收的一方收到这串编码能不能解出来，试一下发现可以正常解析，不会产生歧义。这是因为任意一个字符的编码都不是另一个字符的编码前缀。这也是二叉树本身自带的一个功能，我们通过这种左0右1的方式得到的编码就可以达到这种效果。 下篇讲如何用代码实现赫夫曼编码

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/38390513 作者:小马 一 二叉树的一些概念 二叉树就是每个结点最多有两个子树的树形存储结构。先上图，方便后面分析。  **1 满二叉树和完全二叉树** 上图就是典型的二叉树，其中左边的图还叫做满二叉树，右边是完全二叉树。然后我们可以得出结论，满二叉树一定是完全二叉树，但是反过来就不一定。满二叉树的定义是除了叶子结点，其它结点左右孩子都有,深度为k的满二叉树，结点数就是2的k次方减1。完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应。 **2 树的深度** 树的最大层次就是深度，比如上图，深度是4。很容易得出，深度为k的树，拥有的最大结点数是2的k次方减1。 **3 树的孩子，兄弟，双亲** 上图中，B,C是A的孩子，B,C之间互为兄弟，A是B,C的双亲。 二如何创建二叉树 先说说二叉树的存储结构，跟很多其它模型一样，也有顺序和链式两种方式。前者虽然使用简单，但是存在浪费空间的问题，举个例子，下图的二叉树，用顺序的方式存储(0表示空，没有子树)是: 1 2 3 4 5 6 7 0 0 0 0 8 0 0 0  是不是相当浪费空间呢。 链式结构可以定义如下: ~~~ typedef struct _BiTNode { int data; _BiTNode *leftChild; _BiTNode *rightChild; }BiTNode, *pBiTree; ~~~ 然后就可以写一个函数来创建二叉树，过程是在控制台输入a表示退出当前这一层,不再为该层创建左右孩子。输入其它字母表示继续创建。比如下面的输入序列：  创建了如下结构的二叉树,  每个结点里的数值是随机生成的小于100的数字。同时我也写了一个自动的命令序列函数，方便测试，不用手动输入，非自动和自动创建的函数如下: ~~~ //创建二叉树, 先序顺序 int CreateBiTree(pBiTree *root) { char ch = 0; fflush(stdin); if ((ch = getchar()) == 'a')//控制树的结构 { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTree(&(*root)->leftChild); CreateBiTree(&(*root)->rightChild); } return RET_OK; } int g_i = 0; //创建二叉树,自动执行，方便测试 int CreateBiTreeAuto(pBiTree *root) { char szOrder[] = "bbaabaa"; char ch = 0; if (szOrder[g_i++] == 'a')//控制树的结构 { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTreeAuto(&(*root)->leftChild); CreateBiTreeAuto(&(*root)->rightChild); } return RET_OK; } ~~~ 三遍历顺序 **先序遍历** 先序遍历是先访问根结点，再左子树，再右子树，比如图1中的右图，先序遍历的输出如下: A,B,D,H,I,E,J,K,C,F,G 根据上面的思想，很容易用递归的形式写出先序遍历的代码： ~~~ //先序遍历 int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit) { if (T) { (*pFuncVisit)(T->data); if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK) { if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK) { return RET_OK; } } return RET_ERROR; } else { return RET_OK; } } ~~~ **中序遍历和后序遍历** 有了先序的经验，这两个就很好理解了，中序是先访问左子树, 再根结点，再右子树, 后序是先访问左子树, 再右子树，再根结点。代码更容易，只要改一下调用顺序就可以了。 不过我这里给出一种非递归的实现。递归固然是清晰明了，但是存在效率低的问题，非递归的方案用栈结构来存结点信息，通过出栈访问来遍历二叉树。它思想是这样的，当栈顶中的指针非空时，遍历左子树，也就是左子树根的指针进栈。当栈顶指针为空时，应退至上一层，如果是从左子树返回的，访问当前层，也就是栈顶中的根指针结点。如果是从右子树返回，说明当前层遍历完毕，继续退栈。代码如下: ~~~ //中序遍历, 非递归实现 int InOrderVisitTree(pBiTree T, VisitType pFuncVisit) { ponyStack binaryTreeStack; InitStack(&binaryTreeStack, 4); Push(&binaryTreeStack, &T); pBiTree pTempNode; while (!IsEmptyStack(binaryTreeStack)) { while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL)) { Push(&binaryTreeStack, &(pTempNode->leftChild)); } Pop(&binaryTreeStack, &pTempNode); if (!IsEmptyStack(binaryTreeStack)) { Pop(&binaryTreeStack, &pTempNode); (*pFuncVisit)(pTempNode->data); Push(&binaryTreeStack, &(pTempNode->rightChild)); } } return RET_OK; } ~~~ 代码下载地址: http://download.csdn.net/detail/pony_maggie/7714493 或 https://github.com/pony-maggie/BinaryTreeDemo

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/37832707 作者:小马 在一个长串中查找一个子串是较常用的操作。各种信息检索系统，文字处理系统都少不了。本文介绍一个非常著名的KMP模式匹配算法用于子串查找。 先抛开KMP，正常情况一下我们会如何设计这个逻辑。一个主串S, 要在里面查找一个子串T，如果找到了返回T在S中开始的位置，否则返回-1。应该不难，需要一个辅助函数，从一个串口的指定位置，取出指定长度的子串。思想是这样： 在主串S中从开始位置，取长度和T相等的子串比罗，若相等，返回该位置的索引值，否则位置增加1, 继续上面的过程。代码很简单，如下: ~~~ //普通方法查找子串 //在主串s中查找t, 若找到匹配，返回索引位置(从0到len-1) //否则返回-1 int IndexOfString(char* srcString, char* keyString) { int nSrcLen = 0; int nKeyString = 0; int i = 0; char szTemp[1024] = {0};//假设足够大 if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyString = strlen(keyString); if (nKeyString > nSrcLen) { return -1; } while(i < (nSrcLen-nKeyString)) { memset(szTemp, 0x00, sizeof(szTemp)); SubString(srcString, szTemp, i, nKeyString); if (memcmp(szTemp, keyString, nKeyString) != 0) { i++; } else return i; } return -1; } ~~~ 再进一步，把辅助函数去掉，通过频繁操作下标也同样可以实现，思想跟上面查不多，只不过换成一个个字符比较，代码如下: ~~~ int IndexOfString1(char* srcString, char* keyString) { int nSrcLen = 0; int nKeyLen = 0; int i = 0; int j = 0; char szTemp[1024] = {0};//假设足够大 if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyLen = strlen(keyString); if (nKeyLen > nSrcLen) { return -1; } while((i < nSrcLen) && (j <nKeyLen)) { if (srcString[i] == keyString[j]) { i++; j++; } else { i = i - j + 1;//主串回退到下一个位置 j = 0; //子串重新开始 } } if (j >= nKeyLen) { return (i - nKeyLen);//找到 } return -1; } ~~~ 分析一下上面算法的时间复杂度（两个算法其实是一样的）。举个例子，主串是: “A STRING SEARCHING EXAMPLE CONSISTINGOF SIMPLE TEXT” 子串是 “STING” 用上面的算法，会发现除了上面标记红色的字符比较了两次，其它都是比较一次，如果主串的长度是m, 子串的长度是n, 时间复杂度基本是O(m+n)。好像不错，效率挺高。再来看一个。主串是: “000000000000000000000000000000000000000000000000000000000001” 子串是 “00000001” 在脑海里想像一下这个过程，很容易得出它的时间复杂度是O(m*n)。所以这种类似穷举的查找子串算法，时间复杂度与主串和子串的内容有很大关系，复杂度不固定。而且像上面那样的01串在计算机处理中还比较常见，所以需要更好的算法。 KMP（三个发明人的名字首字母）算法可以保证不论哪种情况都可以在O(m+n)的时间复杂度内完成匹配。它改进的地方是当出现比较不等时,主串中位置不回退,而是利用已经匹配的结果,将子串向右滑动尽可能远的距离后，再继续比较，看个例子:  在第三趟匹配中，当i=12, j=7时，字符不相等，这时不用回退到i=7,j=1重新比较，而是i不变，j变成next[j]的值就行了，上图中是3, 也就是图中第四趟的比较位置。 这个确实很强大，现在要解决的问题是next[j]如何计算。其实这个推导也不难，很多算法的书上都有详细的过程，我这里就不赘述了。只把结果给出来: 1 当j = 0时，next[j] =-1。 2 当j =1时，next[j] = 0。 3 满足1 < k < j,且p[0…k-1] =p[j-k…j-1]的最大的k, next[j] = k。 4 其它情况，next[j] = 0。 根据上面的逻辑，很容易写出一个计算next的函数，如下: ~~~ static void getNext(char* strSub) { int j, k, temp; int nLen = 0; j = k = temp = 0; nLen = strlen(strSub); memset(g_next, 0x00, sizeof(g_next));//每次进来都清空 for (j = 0; j < nLen; j++) { if (j == 0) { g_next[j] = -1; } else if (j == 1) { g_next[j] = 0; } else //取集合不为空时的最大值 { temp = j - 1; for (k = temp; k > 0; k--) { if (isEqual(strSub, j, k)) { g_next[j] = k; break; } } if (k == 0)//集合为空 { g_next[j] = 0; } } } } ~~~ 得到next之后，整个过程如下: 以指针i和j分别表示主串和子串中正在比较的字符，若Si = Pj, 则i和j都增1，继续下一个字符的比较。否则i不变，j退到next[j]的位置再比较，若相等，再各自增1，否则j再退到next[j]。循环进行，如果中间遇到next[j]为-1的情况，此时主串要增1，子串j变为0，表示要从主串的下一个位置重新开始比较。 把上面的过程转化为代码： ~~~ //KMP算法查找子串 //在主串s中查找t, 若找到匹配，返回索引位置(从0到len-1) //否则返回-1 int IndexOfStringKMP(char* srcString, char* keyString) { int i = 0; int j = 0; int nSrcLen = 0; int nKeyLen = 0; if ((srcString == NULL) || (keyString == NULL)) { return -1; } nSrcLen = strlen(srcString); nKeyLen = strlen(keyString); if (nKeyLen > nSrcLen) { return -1; } getNext(keyString);//先计算next值 while ((i < nSrcLen) && (j < nKeyLen)) { if ((srcString[i] == keyString[j]) || (j == -1)) { i++; j++; } else { j = g_next[j]; } } if (j >= nKeyLen) { return (i - nKeyLen);//找到 } return -1; } ~~~ 代码下载地址: http://download.csdn.net/detail/pony_maggie/7630329 或 https://github.com/pony-maggie/StringIndex

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/37729745 作者:小马 思考下面一个问题, 给定正整数n和m，计算出n个元素的集合可以划分为多少个不同的由m(m<=n)个不同的非空子集组成的集合。 这类题可以叫做集合划分问题。面试题里经常出现。先来考虑一个问题，这个算法有实际的应用吗？可能用在类似资源分配的例子上，比如有n个资源，m个工程，把这些资源分给不同的工程，需要求出不同的分法，然后计算不同的分法将获得的利润(这个例子似乎有点牵强，谁有更好的请给我留言，谢谢)。 解题的思路，一种是分治的思想。把n个元素编号，对於最后那个n号元素，有两种情况: 一种是独立组成一个集合，另一种是和别的元素混在一起。 对於第一种情况，等价于把前n-1个元素分成m-1份，然后n号元素单独放。 对於第二种情况，等价于把前n-1个元素分成m份，然后把n号元素放入这m个集合中的一个（有m种放法） 总数就是 F(n,m) =F(n-1,m-1) + m * F(n-1,m) 先想几种极端的情况， m=n的情况，结果很明显是1。 m=1的情况，结果也是1。 n=1的情况，m只能等于1, 结果也是1。 有了上面的思想，基本上基于递归的代码就可以出来了，如下: ~~~ //基于分治的思想，递归实现 int calculateSet(int n ,int m) { if ((m > n) ||(m == 0)) { return 0; } else if ((m == 1)||(n==1)||(m == n)) { return 1; } else { return (calculateSet(n-1, m-1) + m*calculateSet(n-1, m)); } } int _tmain(int argc, _TCHAR* argv[]) { int n1 = 4; int m1= 2; printf("%d\n", calculateSet(n1,m1)); return 0; } ~~~

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/37535577 作者:小马 先看两段代码, 一个是C，一个是java。 ~~~ int _tmain(int argc, _TCHAR* argv[]) { char b = 0x83; short s1 = (short)b; short s2 = (short)(b&0xff); printf("s1 = %d\n", s1); printf("s2 = %d\n", s2); return 0; } ~~~ ~~~ public static void main(String[] args) { byte b = (byte)0x83; short s1 = (short)b; short s2 = (short)(b&0xff); System.out.printf("s1 = %d\n", s1); System.out.printf("s2 = %d\n", s2); } ~~~ 运行结果其实是一样的: s1 = -125 s2 = 131 用两种语言，是想说明它的通用性，表示这个特性跟语言本身无关。那么原因是什么呢？ 首先，第二个结果才是我们期望的，这个应该都同意(至少大部分情况下都是这样)。其次如果变量b是正数(这里是负数，因为char表示有符号数，0x83最高位是1,表示负数)，S1和S2的结果是相等的。 所以，问题的核心其实还是变量b的这个符号位。计算机里从低精度数向高精度数转换时，比如这里从char到short, 肯定会在前面扩展一些bit位，从而达到高精度数的长度。那么扩展时，是补0还是补1呢？这里有个原则就是，有符号数扩展符号位，也就是1,无符号数扩展0。 再看看上面的代码，s1其实是0xff83, 是个负数，它表示的值就是-125(注意0xff83是补码表示，计算原值要换成原码)。而s2是0x0083, 因为它强制与上了0xff,其实就是与上了0x00ff。这样就把高字节转成了0x00,消除了符号位。 为了证明上面的理论，可以做一个实验，把代码改成这样： ~~~ int _tmain(int argc, _TCHAR* argv[]) { char b = 0x83; short s1 = (short)b; short s2 = (short)(b&0xffff); printf("s1 = %d\n", s1); printf("s2 = %d\n", s2); return 0; } ~~~ 运行，结果是s1=s2=-125。这也支持了上面的理论分析。 趁热打铁，再看一个示例： ~~~ int _tmain(int argc, _TCHAR* argv[]) { char a = 0xff; if (a == 0xff) { printf("equal\n"); } return 0; } ~~~ 运行的结果是, “equal”并没有打印出来。你可能已经分析出原因了。字符a在和0xff比较时，被隐式的转换成int(因为0xff是整型)，然后a做了符号位扩展，变为0xffffffff, 这个值和0x000000ff比较，当然是不等的。 我希望已经讲清楚了，欢迎拍砖。

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/36706131 作者:小马 一希尔排序 上一篇讲到的直接插入排序，时间复杂度O(n^2). 请在脑海里想一下它的过程。如果一个序列本来就是有序的，对它排序的时间复杂度是O(n)。所以当序列基本有序时，插入排序排序的效率大大提高，因为减少了移动的动作。 另外，直接插入排序还有一个特点，当n比较小时，它的效率比较高。 希尔排序正是基于上面两个思想做的一种改进算法。它先将整个序列分成若干个小序列，对每个小序列做直接插入排序，这样整个序列变得“基本有序”，然后对整个序列做一次直接插入排序，得到最终结果。不过希尔排序并不是简单地逐段分割，而用相隔某个增量的记录组成一个序列。如下图所示:  一开始增量为3, 有三组，{9，8，4}， {1， 3， 6}，{5，7，2}，分别直接插入排序得到2图,然后增加变为2，继续上面的过程，最后当增量为1时，数组就有序了。三趟排序用的增量构造一个增量序列{3,2,1}。这个不是固定的，但是一个好的增量序列，应该没有除1以外的公因子，并且最后一个增量必须等于1。思路很清晰了，上代码吧。 ~~~ //一趟插入排序, dk是单次的增量 static void shellInsert(int nArray[], int nLength, int dk) { int i = 0; int j = 0; int nSerity = 0; for (i = dk; i < nLength; i++) { if (nArray[i] < nArray[i-dk]) { nSerity = nArray[i]; for (j = i-dk; (j >= 0)&&(nSerity < nArray[j]); j-=dk) { nArray[j+dk] = nArray[j]; } nArray[j+dk] = nSerity; } } } int shellSort(int nArray[], int nLength) { int k = 0; int dkArray[] = {3, 2, 1}; //默认使用的增量序列 int dkLength = 3; for (k = 0; k < dkLength; k++) { shellInsert(nArray, nLength, dkArray[k]); } return 0; } ~~~ 它的复杂度计算涉及到一些数学难题，你只要知道它的效率比较直接插入排序要高一些就行了。 二快速排序 有些地方会提到快速排序是对冒泡排序的一种改进，我倒是觉得不要这么联想，会误导你学习快速排序。 快速排序思想先选取一个“枢纽元素”，一般就是序列的第一个元素。把比这个枢纽小的数据放一边，比它大的放另一边。这样一趟之后序列变为, 一部分中的所有元素都比另一部分中的所有元素小，但是部分之间的记录可能是无序的。然后对每一部分再用样的思想继续分，最后就变为有序序列。如下图所示:  通过上面的步骤，自然想到用递归来实现快速排序，没错，上代码。 ~~~ static int partition(int nArray[], int nLow, int nHigh) { int nPivot = nArray[nLow]; while (nLow < nHigh) { while ((nLow < nHigh) && (nArray[nHigh] >= nPivot)) nHigh--; nArray[nLow] = nArray[nHigh]; while ((nLow < nHigh) && (nArray[nLow] <= nPivot)) nLow++; nArray[nHigh] = nArray[nLow]; } nArray[nLow] = nPivot; return nLow; } static void sortProcess(int nArray[], int nLow, int nHigh) { int nPartition = 0; if (nLow < nHigh) { nPartition = partition(nArray, nLow, nHigh); sortProcess(nArray, nLow, nPartition-1); sortProcess(nArray, nPartition+1, nHigh); } } int quickSort(int nArray[], int nLength) { sortProcess(nArray, 0, nLength-1); return 0; } ~~~ 快速排序时间复杂度是O(nlogn),是目前公认的效率比较高的排序算法。 三归并排序 归并排序算是一种比较特殊的排序算法，它将两个有序表(长度分别是m,n)合并成另一个有序表，这个动作可在O(m+n)的时间复杂度实现。对于个有n个元素的无序序列，可以看成n个有序的子序列，然后两两归并，得到一个n/2长度为2或1(想想为什么有1)的有序子序列，继续两两归并，直接得到一个长度为n的有序序列为止。如下图所示:  这里我们用递归的方法来实现，好理解一些，非递归的方法稍复杂一些。代码如下: ~~~ //将有序的srcArray[i..m]和srcArray[m+1..n],归并到destArray[i..n] static void Merge(int srcArray[], int destArray[], int i, int m, int n) { int j = 0; int k = 0; for (j = m+1,k=i; (i<=m)&&(j<=n); ++k) { if (srcArray[i] < srcArray[j]) { destArray[k] = srcArray[i++]; } else { destArray[k] = srcArray[j++]; } } //剩下的直接拷过来 while (i <= m) { destArray[k++] = srcArray[i++]; } while (j <= n) { destArray[k++] = srcArray[j++]; } } static void MSort(int srcArray[], int destArray[], int s,int t) { int m = 0; int destArray2[256] = {0}; //辅助数组,空间根据实际情况分配. if (s == t) { destArray[s] = srcArray[s]; } else { m = (s + t)/2; MSort(srcArray, destArray2, s, m); MSort(srcArray, destArray2, m+1, t); Merge(destArray2, destArray, s, m, t); } } //递归方法实现归并排序 int MergeSort(int nArray[], int nLength) { int nDestArray[256] = {0}; int i = 0; MSort(nArray, nDestArray, 0, nLength-1); while (i<nLength)nArray[i] = nDestArray[i++]; return 0; } ~~~ 它的时间复杂度是O(nlog2n)。 代码下载地址: http://download.csdn.net/detail/pony_maggie/7568971 或 https://github.com/pony-maggie/SortDemo

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/35819279 作者:小马 从题目看，首先不是全部是若干。排序算法很多，我个人的能力也有限，不可能都讲到。另外，是简单汇总，是希望能用最简单的代码，最简短的语言说明问题，不搞太多理论分析。 就像前面说的，排序算法有很多，而且不存在哪一种最不好，哪一种最好这样的说法。根据用途不同选择最适合的就行了。不过仅从时间复杂度来看，基本上有两种，一种是O(n^2), 一种是O(nlogn)。 所谓的时间复杂度，其实是基于多少次基本操作定义的，在排序算法中，基本操作指两类，一是比较，二是记录从一个位置移动另一个位置。下面讲到的排序算法都会涉及到这些操作。 一直接插入排序 先从一个最简单的切入。它的思种是这样的，把一个数插入到已排好的序列中。比如已有一个有序序列: { 12, 23, 25, 40} 现在有一个数18要插入进来，并且保证插入后序列还是有序。18开始和序列中的所有数逐一比较(从右向左比较)，比40小，40后移，比25小，25后移，比23小，23后移，跟12比，发现比12大，停在这里，插入到23的位置，最终变为: { 12, 18, 23, 25, 40} 上面的过程叫一趟插入排序，基于这个思想, 我们可以认为数组第一个元素是有序的，所以可以从第二个元素开始，每个元素都做一趟插入排序就可以得到一个有序序列。代码就很简单了， ~~~ int insertSort(int nArray[], int nLength) { int i = 0; int j = 0; int nSerity = 0;//备份要插入的那个元素 for (i = 1; i < nLength; i++) { if (nArray[i] < nArray[i-1]) { nSerity = nArray[i]; nArray[i] = nArray[i-1]; for (j = i-2; (j >= 0)&&(nSerity < nArray[j]); j--) { nArray[j+1] = nArray[j]; } nArray[j+1] = nSerity; } } return 0; } ~~~ 很容易看出它的时间复杂度是O(n^2) 二冒泡排序 这个排序算法基本是大学老师必讲的，因为它除了简单之外，也确实比较好玩。思路是这样的，一个无序序列a[n], a[1]和a[2]比较，如果a[1]>a[2], 它们就交换位置，否则不做处理。继续a[2]和a[3]同样的原理比较，一直到a[n-1]和a[n]比较。 上面的过程叫一趟冒泡，请你在脑海里想像下这个过程，我下面要说的这个结论希望你能想明白，那就是经过一趟冒泡后，序列中最大的那个元素已经被换到a[n]的位置了。有没有觉得这个过程就像冒泡一样，只不过这个泡是向下冒的。 做第二趟冒泡时，只要对a[1]~a[n-1]操作就行了，结果是序列中第二大的那个元素在a[n-1]的位置了。然后经过n趟冒泡后，排序就完成了。 通过上面的过程也很容易得出冒泡排序的时间复杂度是O(n^2)，可以上代码了， ~~~ //bChange作用是为了对于已排好序的序列，能 //及时退出来。 int bubbleSort(int nArray[], int nLength) { int i = 0; int j = 0; int nTemp = 0; bool bChange = true; for (i = 0; (i < nLength) &&(bChange); i++) { bChange = false; for (j = 0; j < (nLength - i - 1); j++) { if (nArray[j] > nArray[j+1]) { nTemp = nArray[j]; nArray[j] = nArray[j+1]; nArray[j+1] = nTemp; bChange = true; } } } return 0; } ~~~ 可以好好理解一下代码中bChange变量的作用，这里不多说解释了，留给大家思考。 这篇就打算写这么多了，主要篇幅太长怕大家看着厌烦，过几天有空了再接着写吧。 代码下载地址: http://download.csdn.net/detail/pony_maggie/7568971 或 https://github.com/pony-maggie/SortDemo

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/31042651 作者:小马 一个包含n个元素的集合,求它的所有子集。比如集合A= {1,2,3}, 它的所有子集是: { {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, @}(@表示空集)。 这种问题一般有两种思路，先说说第一种，递归。递归肯定要基于一个归纳法的思想，这个思想用到了二叉树的遍历，如下图所示:  可以这样理解这张图，从集合A的每个元素自身分析，它只有两种状态，或是某个子集的元素，或是不属于任何子集，所以求子集的过程就可以看成对每个元素进行“取舍”的过程。上图中，根结点是初始状态，叶子结点是终结状态，该状态下的8个叶子结点就表示集合A的8个子集。第i层(i=1,2,3…n)表示已对前面i-1层做了取舍，所以这里可以用递归了。整个过程其实就是对二叉树的先序遍历。 根据上面的思想，首先需要一个结构来存储元素，这个”取舍”过程，其实就是在线性结构中的增加和删除操作，很自然考虑用链式的存储结构，所以我们先来实现一个链表： ~~~ typedef struct LNode { int data; LNode *next; }LinkList; //建立一个链表,你逆向输入n个元素的值 int listCreate(LinkList *srcList, int number) { LinkList *pTemp; int i = 0; srcList->next = NULL; srcList->data = 0; for (i = number; i > 0; --i) { pTemp = (LinkList *)malloc(sizeof(LNode)); pTemp->data = i+20;//随便赋值 pTemp->next = srcList->next; srcList->next = pTemp; } return 0; } //销毁一个链表 int listDestroy(LinkList *srcList) { if (!srcList || !srcList->next) { return 0; } LinkList *p1 = srcList->next; LinkList *p2 = p1->next; do { free(p1); p1 = p2; if (p2 != NULL) { p2 = p2->next; } }while (p1); return 0; } //插入操作 //在strList第nIndex之前插入数据data //nIndex最小为1 int listInsert(LinkList *srcList, int nIndex, int data) { LinkList *pStart = srcList; int j = 0; if (nIndex < 1) { return 0; } while((pStart) && (j < nIndex-1)) { pStart = pStart->next; j++; } if ((!pStart) || (j > nIndex-1)) { return -1;//出错 } LinkList *temp = (LinkList *)malloc(sizeof(LNode)); temp->data = data; temp->next = pStart->next; pStart->next = temp; return 0; } //删除操作 //strList第nIndex位置的结点删除，并通过data返回被删的元素的值 //通常情况下返回的这个值是用不到的，不过这里也保留备用 int listDelete(LinkList *srcList, int nIndex, int *data) { LinkList *pStart = srcList; int j = 0; if (nIndex < 1) { return 0; } while((pStart) && (j < nIndex-1)) { pStart = pStart->next; j++; } if ((!pStart) || (j > nIndex-1)) { return -1;//出错 } LinkList *pTemp = pStart->next; pStart->next = pTemp->next; *data = pTemp->data; free(pTemp); } ~~~ 有了这个链表，递归算法实现起来就很容易了: ~~~ //求冥集，nArray是存放n个元素的数组 //首次调用i传1,表示已对前面i-1个元素做了处理 void GetPowerSet(int nArray[], int nLength, int i, LinkList *outPut) { int k = 0; int nTemp = 0; if (i >= nLength) { printList(*outPut); } else { k = listLength(outPut); listInsert(outPut, k+1, nArray[i]); GetPowerSet(nArray, nLength, i+1, outPut); listDelete(outPut, k+1, &nTemp); GetPowerSet(nArray, nLength, i+1, outPut); } } ~~~ 还有一种思想比较巧妙，可以叫按位对应法。如集合A={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。 映射为子集： (a,b,c) (1,1,1)->(a,b,c) (1,1,0)->(a,b) (1,0,1)->(a,c) (1,0,0)->(a) (0,1,1)->(b,c) (0,1,0)->(b) (0,0,1)->(c) (0,0,0)->@(@表示空集) 观察以上规律，与计算机中数据存储方式相似，故可以通过一个整型数与集合映射...000 ~ 111...111（表示有，表示无，反之亦可），通过该整型数逐次增可遍历获取所有的数，即获取集合的相应子集。 实现起来很容易: ~~~ void GetPowerSet2(int nArray[], int nLength) { int mark = 0; int i = 0; int nStart = 0; int nEnd = (1 << nLength) -1; bool bNullSet = false; for (mark = nStart; mark <= nEnd; mark++) { bNullSet = true; for (i = 0; i < nLength; i++) { if (((1<<i)&mark) != 0) //该位有元素输出 { bNullSet = false; printf("%d\t", nArray[i]); } } if (bNullSet) //空集合 { printf("@\t"); } printf("\n"); } } ~~~ 分析代码可以得出它的复杂度是O(n*2^n)。 代码下载地址: https://github.com/pony-maggie/PowerSetDemo 或 http://download.csdn.net/detail/pony_maggie/7499161

转载请注明出处 http://blog.csdn.net/pony_maggie/article/details/30802249 作者:小马 作为一种常用的数据结构, 了解栈对于算法的学习是非常必要的。栈有先进后出的特点，栈底指向数据表中的第一个元素，栈顶指向最后一个元素的下一个位置。如下图所示:  栈和线性表类似，也是有两种存储结构，分别为顺序结构和链式结构。大部分情况下，栈使用前者，这和它的使用场景有关，因为通常情况下我们不会对栈进行频繁地，随机地插入，删除操作。下面是我用顺序结构实现的栈，这个栈有个特点就是它的通用性，因为我并没有限制它所存储的数据类型，代码如下: ~~~ //void**其为双指针，意味入栈和出栈的将只是对应数据的地址，而不需要对数据本身进行拷贝 typedef struct { char *base; char *top; int elementSize; //元素所点字节大小 int stackSize; //当前已分配的空间(注意不是元素的实际个数) }ponyStack; int InitStack(ponyStack *stack, int elementSize) { stack->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char)*elementSize); if (!stack->base) { return RET_ERROR; } stack->top = stack->base; //为空 stack->stackSize = STACK_INIT_SIZE; stack->elementSize = elementSize; return RET_OK; } int ClearStack(ponyStack *stack) { stack->top = stack->base; return RET_OK; } bool IsEmptyStack(ponyStack stack) { if (stack.top == stack.base) { return true; } return false; } ~~~ 这里没有贴出全部的代码，更完整的可以从最后的地址那里下载。注意elementSize,这个是栈可以做到通用的核心。不理解的可以再研究一下代码。 看一个栈的使用示例，数制转换。十进制转八进制。例如(1348)十进制= (2504)八进制,它基于如下的原理: N             N/8             N%8 1348        168               4 168           21                0  21             2                  5  2               0                   2 所以很明显，N不断的除8，每次的余数就是结果的其中一个因子，注意先出来的因子是低位的数，可以考虑用栈来保存每次取余的结果，那么出栈的顺序就是实际的结果顺序。代码很简单： ~~~ int decimalToOctonary(int decimalNumber) { double octNumber = 0; int nCount = 0; int nTemp = 0; ponyStack numberStack; InitStack(&numberStack, 4); while (decimalNumber) { nTemp = (int)decimalNumber%8; Push(&numberStack, &nTemp); decimalNumber = decimalNumber/8; } nCount = CountOfStack(numberStack);//元素个数也就是位数 while(!IsEmptyStack(numberStack)) { Pop(&numberStack, &nTemp); octNumber += (nTemp*pow(10.0, --nCount)); } DestroyStack(&numberStack); return (int)octNumber; } ~~~ 再来看一个行编辑程序的示例，用户在终端输入字符，完成后保存用户的数据区， 因为在输入的过程中可能出错，需要修改，所以不可能每输入一个字符就存入数据区。比较好的做法是先在内存里开一个输入的缓冲区，当用户输入完成一行后，再存入数据区。在行内可以修改。例如，当用户发现刚输入的一个字符是错的之后，可以再输入一个'#',表示前一个字符是错的，如果发现当前行输入的错误太多，可以输入一个退行符'@',表示当前行都无效，举个例子: whli#ilr#e(s#*s) outcha@putchar(*s=#++) 实际有效的字符是这样的: while(*s) putchar(*s++) 可以把内存里这个输入缓冲区定为栈,正常情况下每输入一个字符直接入栈，如果发现字符是'#',就栈顶pop一次，如果是'@'就清空栈.代码实现如下: ~~~ void lineEdit() { char ch = 0; char chTemp = 0; ponyStack lineStack; InitStack(&lineStack, 1); ch = getchar(); while (ch != EOF) { while (ch != EOF && ch != '\n') { switch (ch) { case '#': Pop(&lineStack, &chTemp); break; case '@': ClearStack(&lineStack); break; default: Push(&lineStack, &ch); break; } ch = getchar(); } writeToFile(lineStack);//存数据 ClearStack(&lineStack);//准备接收下一行 if (ch != EOF) { ch = getchar(); } } DestroyStack(&lineStack); } ~~~ 最后一个例子是表达式求值的算法，这个在计算器应用中比较多用到。比如， 求+4*9-16/4 建两个栈，一个存操作数，一个存运算符.为简单起，在运算符栈会预先存一个'#',表示表达式开始，然后以'#'结束。运算规则是这样的: 输入字符，如果是'#'，则结束，如果是操作数，直接进操作数栈。如果是运算符，则跟栈顶的运算符比较，如果栈顶的优先级低,直接进栈，接收下一字符，如果相等，脱括号，接收下一个字符，如果栈顶的优先级高，pop两个操作数，pop栈内操作符，运算，然后运算的结果进操作数栈。当前运算符继续跟栈顶比较。 要实现这个代码，首先要有一个表格，存储我们操作符之间的优先级关系，如下所示: ~~~ static char priority[7][7] = { '>','>','<','<','<','>','>', // + '>','>','<','<','<','>','>', // - '>','>','>','>','<','>','>', // * '>','>','>','>','<','>','>', // / '<','<','<','<','<','=',' ', // ( '>','>','>','>',' ','>','>', // ) '<','<','<','<','<',' ','=', // # };// + - * / ( ) # ~~~ 然后实现根据上面的思路，实现起来就比较容易了： ~~~ int evaluateExpression() { char chCurrent = 0; char chOnTop = 0; char chTemp = 0; int nResult = 0; int nTemp = 0; int a,b; int nOperandFlag = 0; ponyStack operatorStack;//运算符栈 ponyStack operandStack; //操作数栈 InitStack(&operatorStack, 1); chTemp = '#'; Push(&operatorStack, &chTemp); InitStack(&operandStack, 4); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); while ((chCurrent != '#')||(chOnTop != '#')) { if (!isOperator(chCurrent))//是操作数,要考虑多位整型数的情况 { nTemp = nTemp * (int)pow(10.0, nOperandFlag); nTemp += (int)(chCurrent - '0'); chCurrent = getchar(); nOperandFlag = 1; } else { if (nOperandFlag == 1) { Push(&operandStack, &nTemp);//操作数输入结束，入栈 nOperandFlag = 0; nTemp = 0; } GetTop(operatorStack, &chOnTop); switch (precede(chOnTop, chCurrent))//比较优先级 { case '<': //栈顶的优先级小 Push(&operatorStack, &chCurrent); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '=': //脱括号，接收下个字符 Pop(&operatorStack, &chTemp); chCurrent = getchar(); GetTop(operatorStack, &chOnTop); break; case '>': //栈顶的优先级大，出栈运算，结果入栈 { Pop(&operandStack, &a); Pop(&operandStack, &b); Pop(&operatorStack, &chTemp); nTemp = operate(a, chTemp, b); Push(&operandStack, &nTemp); nTemp = 0;//重置 GetTop(operatorStack, &chOnTop); } break; default: break; } } } GetTop(operandStack, &nResult); DestroyStack(&operatorStack); DestroyStack(&operandStack); return nResult; } ~~~ 代码下载地址: https://github.com/pony-maggie/StackDemo 或 http://download.csdn.net/detail/pony_maggie/7499167

> 原文出处：[那些年，一起追过的算法](http://blog.csdn.net/column/details/chasing-algorithm.html) 作者：[pony_maggie](http://blog.csdn.net/pony_maggie) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 那些年，一起追过的算法 > 希望借助这个专栏，能集合各种常用，经典的算法，为自己学习，也为分享给在校大学生或者已经工作的IT从业者。可以结合以下书籍阅读本专栏: &lt;&lt;数据结构&gt;&gt;(严蔚敏版)，&lt;&lt;算法设计与分析&gt;&gt;(郑宗汉版)