白话经典算法系列之四 直接选择排序及交换二个数据的正确实现 直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。 设数组为a[0…n-1]。 1. 初始时,数组全为无序区为a[0..n-1]。令i=0 2. 在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区... 2012年10月24日 白话算法 暂无评论 喜欢 0 阅读 66 次 阅读全文
二分法求方程的近似解 二分法求方程的近似解 用实例来解答,比如求 Y^3+Y-10=0的在区间Y[0,3]之间的根,先将Y=0代入方程左边,左边=-10,将Y=3代入左边,左边=20,这样已经创造出了一正一负,在0-3之间必有解,找中点.Y=1.5代入,如果是正,就保留负的那一头,如果是负就保留正的那一头,然后重复这一过程,不断找中点,只到等式左边接近或等于零,就解得了近似根或准确根. //例1:用二分法求方程x^3+4x-10=0在区间[1,2]内的根(精确到0.00001) ... 2012年10月17日 分治 暂无评论 喜欢 4 阅读 3,839 次 阅读全文
树(普通树) 数据结构树的代码实现,代码参考数据结构使用教程(第二版): [cpp]struct GTreeNode { ElemType data; GTreeNode *t[k]; //k叉树 } void CreateGTree(GTreeNode *>,char *a)//广义表构造普通树 { const int MS=10; //定义符号常量指定栈空间的大小 GTreeNode *s[MS]; //s数组作为存储树中结点指针的栈使用 int d[MS]; //d数组作为储存孩子结点链接到双亲节点 ... 2012年10月06日 数据结构 暂无评论 喜欢 0 阅读 218 次 阅读全文
贪心算法(一) 描述 进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。 输入 第一行输... 2012年09月25日 贪心 暂无评论 喜欢 1 阅读 295 次 阅读全文
背包问题(贪心) 贪心算法关键:找出最优量度 利用一道ACM的题目,熟练贪心: 描述 现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。 输入 第一行输入一个正整数n(1<=n<=5),表示有n组测试数据; 随后有n测试数据,每组测试数据的... 2012年09月24日 贪心 暂无评论 喜欢 0 阅读 173 次 阅读全文
二叉树 二叉树抽象数据类型|二叉树实现代码|二叉树C/C++实现代码! 二叉树 其广义表为:A(B(C),D(E(F,G),H(,I))) [cpp] /*算法参考《数据结构实用》教程第二版*/ /*根据广义表建立二叉树*/ struct BTreeNode { ElemType data; BTreeNode *left; BTreeNode *right; }; void InitBTree(BTreeNode *&BT) //初始化二叉树 { BT=NULL; } void CreateBTree(BTreeNode *&BT,char *a) //建立二叉树 { const int Maxs... 2012年09月23日 数据结构 暂无评论 喜欢 0 阅读 205 次 阅读全文
二分检索(分治) 分治二分检索 基本思路:1 ,2 ,3 ,4 ,5,6 ,7,8,9在这9个元素中(有序数组),请检索元素5,是否在这9个元素中,如果利用普通的循环的话如果这堆元素有很大,比如说10000000个元素,计算机肯定会超时!利用分治的思想可以很好的解决这个问题! 示例: 6个元素数组(23 34 46 768 343 343),检索给出的4个数(2 4 23 343)是否在数组中,是的话输出YES,否则NO [cpp] #include <iostream> #include <algorit... 2012年09月21日 分治 暂无评论 喜欢 2 阅读 92 次 阅读全文
白话经典算法系列之三 希尔排序的实现 资料来源于互联网,版权为:MoreWindows! 希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直... 2012年09月21日 白话算法 暂无评论 喜欢 0 阅读 106 次 阅读全文
白话经典算法系列之二 直接插入排序的三种实现 直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。简单来说就是:取出一个元素,寻找插入位置! 设数组为a[n]。 1.初始时,a[0]看成有序区,无序区为a[1..n-1]。 2.i=1循环到i=n-1,将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。排序完成。 代码如下:(由小到大排序) [cpp] void Insertso... 2012年09月21日 白话算法 暂无评论 喜欢 0 阅读 35 次 阅读全文
快速排序(分治) 注:本站的大多数算法为本人手打,如果该算法有错误,或阅者有更好的代码优化建议,请评论!将立即修改! 分治快速排序 由著名的计算机科学家霍尔给出的快速分类算法,不同于归并,取一个元素值作为划分值,元素小的直接靠前,元素大的直接靠后。强于归并。 时间复杂度 事实上,在快速算法中最坏的情况下,划分元素总是最大或最小的元素,快排算法中会退化成冒泡,即:O(n^2),但我们考虑的是平均复杂度O(nlo... 2012年09月21日 分治 暂无评论 喜欢 2 阅读 138 次 阅读全文