C++实现树形选择排序 （tree selection sort）

2017年02月05日 35 阅读

C++实现树形选择排序 （tree selection sort）2015-10-12算法逻辑: 根据节点的大小, 建立树, 输出树的根节点, 并把此重置为最大值, 再重构树.因为树中保留了一些比较的逻辑, 所以减少了比较次数.也称锦标赛排序, 时间复杂度为O（nlogn）, 因为每个值（共n个）需要进行树的深度（logn）次比较.参考<数据结构>（严蔚敏版） 第278-279页.树形选择排序（tree selection sort）是堆排序的...

如何求数字在排序数组中出现的次数

2017年02月05日 38 阅读

如何求数字在排序数组中出现的次数2015-10-12题目: 统计一个数字在排序数组中出现的次数.通过折半查找, 找到首次出现的位置, 再找到末次出现的位置, 相减即可.时间复杂度O（logn）.代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <stdlib.h>#inc...

如何实现数组中的逆序对

2017年02月05日 37 阅读

如何实现数组中的逆序对2015-10-12题目: 在数组中的两个数字如果前面一个数字大于后面的数字, 则这两个数字组成一个逆序对.输入一个数组, 求出这个数组中的逆序对的总数.使用归并排序的方法, 辅助空间一个排序的数组, 依次比较前面较大的数字, 算出整体的逆序对数, 不用逐个比较.时间复杂度: O（nlogn）代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc...

如何求两个链表的第一个公共结点

2017年02月05日 40 阅读

如何求两个链表的第一个公共结点2015-10-12题目: 输入两个链表, 找出它们的第一个公共结点.计算链表的长度, 然后移动较长链表的指针, 使其到相同结点的距离的相同, 再同时移动两个链表的指针, 找到相同元素.时间复杂度: O（n）代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#includ...

Geeks面试题：Box Stacking Problem

2017年02月05日 38 阅读

Geeks面试题：Box Stacking Problem2015-10-14Dynamic Programming | Set 22 （Box Stacking Problem）You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h（i）, width w（i） and depth d（i） （all real numbers）. Y...

Geeks面试题：Closest Pair of Points

2017年02月05日 37 阅读

Geeks面试题：Closest Pair of Points2015-10-14Divide and Conquer | Set 2 （Closest Pair of Points）We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arise...

二叉搜索树与双向链表的C++实现

2017年02月05日 40 阅读

二叉搜索树与双向链表的C++实现2015-10-14题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点, 只能调整数中结点的指针的指向.方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.本程序包含算法原理, 测试程序, 及 输出.代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gc...

输入一个字符串并打印出该字符串中字符的所有排列

2017年02月05日 35 阅读

输入一个字符串并打印出该字符串中字符的所有排列2015-10-14题目: 输入一个字符串, 打印出该字符串中字符的所有排列.方法: 使用递归依次交换位置, 打印输出.代码:/* * main.cpp * *Created on: 2014.6.12 *Author: Spike *//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>void Permutation（char* str, char* begi...

线性表的链式表示

2017年02月05日 36 阅读

线性表的链式表示2015-10-16以下为操作链表的算法，该链表为动态单链表。链表以头指针为索引，头指针指向头节点，头节点指向首节点，以此类推，直到尾节点。头节点中不存放数据，只存放指向首节点的指针，设置头节点的目的是为了方便对链表的操作，如果不设置头节点，而是直接由头指针指向首节点，这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同，便要作为一种特殊情况来分析操作系统：ubuntu编译软件：gcc结果截图：源代码：#include...

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解

2017年02月05日 41 阅读

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解2015-10-16搜索引擎里的dictionary data通常存储着这些信息：索引词（term vocabulary）。文档频率（document frequency，即这个词在多少个文档里出现）。指向倒排表的指针（pointers to each postings list ）。那么，他是怎样的一个数据结构呢？一种非常naive的词典结构就是：其中，term的类型是char[20]，占20bytes，...

如何在遍历中使用iterator及reverse_iterator删除元素

2017年02月05日 40 阅读

如何在遍历中使用iterator及reverse_iterator删除元素2015-10-16众所周知，在使用迭代器遍历 STL 容器时，需要特别留意是否在循环中修改了迭代器而导致迭代器失效的情形。下面我来总结一下在对各种容器进行正向和反向遍历过程中删除元素时，正确更新迭代器的用法。本文完整源码：https://code.csdn.net/snippets/173595首先，要明白使用正向迭代器（iterator）进行反向遍历是错误的用法，要不干嘛要有反向...

解密QQ号的队列算法

2017年02月05日 39 阅读

解密QQ号的队列算法2015-10-18新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问QQ号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数再放到这串数的末尾，再将第5个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的...

快速排序算法

2017年02月05日 39 阅读

快速排序算法2015-10-18上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O（N2）。假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序则只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久，是不是很吓人。那有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢。假设...

冒泡排序算法

2017年02月05日 34 阅读

冒泡排序算法2015-10-18简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0~2100000000之间，那你则需要申请2100000001个变量，也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000之间每一个数出现的次数。即便只给你5个数进行排序（例如这5个数是1，1912345678，2100000000，180...

桶排序算法：最快最简单的排序算法

2017年02月05日 34 阅读

桶排序算法：最快最简单的排序算法2015-10-18在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。首先出场的我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学，这5个同...

编程算法：求1+2+...+n（构造函数） 代码（C++）

2017年02月05日 41 阅读

编程算法：求1+2+...+n（构造函数） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用构造函数, 循环求解, 使用数组构造多个类, 使用类的静态变量存储数据.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <stdio.h>#in...

编程算法：求1+2+...+n（函数继承） 代码（C++）

2017年02月05日 35 阅读

编程算法：求1+2+...+n（函数继承） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用函数继承, 通过递归调用, 每次递归值减1, 使用求反运算（！）, 即非0为0, 0为1.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <stdio...

编程算法：求1+2+...+n（函数指针） 代码（C++）

2017年02月05日 37 阅读

编程算法：求1+2+...+n（函数指针） 代码（C++）2015-10-20 未知 题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用函数指针求解, 通过递归调用, 每次递归值减1, 使用求反运算（！）, 即非0为0, 0为1.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <...

编程算法：求1+2+...+n（模板类） 代码（C++）

2017年02月05日 42 阅读

编程算法：求1+2+...+n（模板类） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用模板类求解, 输入模板参数, 进行递归调用, 每次递归值减1, 至模板参数为1时, 显示调用结束模板类.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <...

Dijkstra最短路算法

2017年02月05日 37 阅读

Dijkstra最短路算法2015-10-22上周我们介绍了神奇的只有五行的Floyd最短路算法，它可以方便的求得任意两点的最短路径，这称为“多源最短路”。本周来来介绍指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。与Floyd-Warshall算法一样这里仍然使用二维数组e来存储顶点之间边的关系，初始值如下。我们还需要用一个一维...