质数与合数及其应用

2016年07月27日 36 阅读

质数与合数及其应用2014-12-25质数与合数摘自维基百科：质数，又称素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。质因数分解 即 分解质因数 。每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数。分解质因数的算式的叫短除法。更多知识请...

1+2+3+...+n不能用while、for、if else等实现

2016年07月27日 38 阅读

1+2+3+...+n不能用while、for、if else等实现2014-12-25问题描述求 1+2+ … +n ，要求不能使用乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等关键字以及条件判断语句。实际意义不大，题目涉及的知识还是不错的！方法1用构造函数求解。#include <iostream>using namespace std; class Plus {public: P...

图的深度优先遍历：邻接表实现

2016年07月27日 36 阅读

图的深度优先遍历：邻接表实现2014-12-25这里用邻接表实现图的深度优先遍历，采用递归实现。#include<iostream>using namespace std;#define VERTEXNUM 5//结点数structedgenode{int to;int weight; // 边的权值edgenode *next;};struct vnode{int from;edgenode *first;};void createGraph...

梯度下降算法：Gradient Descent

2016年07月27日 34 阅读

梯度下降算法：Gradient Descent2014-12-25最近在搞论文，需要用梯度下降算法求解，所以重新整理分享在这里。主要包括梯度介绍、公式求导、学习速率选择、代码实现。梯度下降的性质：1.求得的解和选取的初始点有关2.可以保证找到局部最优解，因为梯度最终会减小为0，则步长与梯度的乘积会自动越来越小。梯度简介一个多元函数的在某点的梯度方向是函数值在该点增长最快的方向，即方向导数取最大值的方向。问题描述公式求导学习率选择假设要学习这么一个函数：那么...

一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决

2016年07月27日 37 阅读

一致性哈希算法 Consistent Hashing 探讨以及相应的新问题出现解决2014-12-25一、业务场景假如我们现在有12台Redis服务器（其它的什么东西也行），有很多User（用户）的数据数据从前端过来，然后往12台redis服务器上存储，在存储中就会出现一个问题，12台服务器，有可能其中几台Redis服务器上（简称集群A）存了很多的数据，然后另外几台Redis服务器（简称集群B）上存的数据很少，这样的话那 A 上的读写压力就会很大（当然，这...

大话数据结构一：线性表的顺序存储结构

2016年07月27日 33 阅读

大话数据结构一：线性表的顺序存储结构2014-12-281. 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。2. Java实现线性表的顺序存储结构：// 顺序存储结构public class SequenceList {private static final int DEFAULT_SIZE = 10; // 默认初始化数组大小private int size; // 当前数组大小private static Object...

大话数据结构二：线性表的链式存储结构（单链表）

2016年07月27日 32 阅读

大话数据结构二：线性表的链式存储结构（单链表）2014-12-281. 线性表的链式存储结构：指的是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着这些数据元素可以存在内存未被占用的任意位置。2. 结点：结点由存放数据元素的数据域和存放后继结点地址的指针域组成。1.）顺序存储结构中，每个数据元素只需要存数据元素的信息就可以了。2.）链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。3....

大话数据结构三：线性表的链式存储结构（静态链表）

2016年07月27日 38 阅读

大话数据结构三：线性表的链式存储结构（静态链表）2014-12-281. 静态链表：用数组描述的链表叫静态链表，通常为方便数据插入，我们会把数组建的大一些。2. 数组元素（node）：由两个数据域组成（data，cursor）。数据域data用来存放数据元素，也就是通常我们要处理的数据；而cursor相当于单链表中的指针，存放该元素的后继在数组中的下标。3. Java实现静态链表：// 静态链表class StaticLinkedList {private...

大话数据结构四：线性表的链式存储结构（单向循环链表）

2016年07月27日 37 阅读

大话数据结构四：线性表的链式存储结构（单向循环链表）2014-12-281. 单向循环链表：将单链表尾结点的指针端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单向循环链表。2. 单向循环链表和单链表实现的区别：1.）添加一个结点到单向循环链表末尾时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为null。2.）判断是否到达表尾时，单向循环链表可以判断该结点是否指向头结点，单链表只需要知道是否为null。3.Jav...

大话数据结构五：线性表的链式存储结构（双向链表）

2016年07月27日 39 阅读

大话数据结构五：线性表的链式存储结构（双向链表）2014-12-281. 双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域，那么在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。2. 单链表和双向链表比较：单链表：总是要从头到尾找结点，只能正遍历，不能反遍历。双向链表： 可以从头找到尾，也可以从尾找到头，即正反遍历都可以，可以有效提高算法的时间性能，但由于每个结点需要记录两份指针，所以在空间占用上略多一点，这就是通过空...

大话数据结构六：特殊的线性表（栈）

2016年07月27日 39 阅读

大话数据结构六：特殊的线性表（栈）2014-12-301. 什么是栈？栈（stack）是限定仅在表尾进行插入和删除操作的线性表。2. 栈的特点：1.） 栈又称为后进先出（Last In First out）的线性表，栈元素具有线性关系，即前驱后继关系。2.） 栈的特殊之处在于：它的栈底是固定的，只允许在栈顶进行插入和删除操作。3. 栈的顺序存储结构（Java数组实现）：// 栈的数组实现, 底层使用数组:public class ArrayStack<...

大话数据结构七：两栈共享存储空间（双向栈）

2016年07月27日 33 阅读

大话数据结构七：两栈共享存储空间（双向栈）2014-12-301. 为什么要使用双向栈？通过上一篇博客 - 特殊的线性表（栈），不难知道栈的顺序存储（数组实现）性能相对较好，因为它不存在插入和删除时移动元素的问题，但是它有一点缺陷：要事先确定数组存储容量的大小，万一不够，就需要扩充数组容量。这时双向栈就派上用场了，它可以最大限度的利用事先开辟的存储空间。2. 双向栈有什么特点？数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一...

大话数据结构八：队列的顺序存储结构（循环队列）

2016年07月27日 38 阅读

大话数据结构八：队列的顺序存储结构（循环队列）2014-12-301. 什么是队列？队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。2. 队列的特点:队列是一种先进先出（First In First out）的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。3. 队列顺序存储有什么不足？使用数组实现的顺序存储，当做出队列操作时，所有的元素都需要向前移动一位，性能很低。4. 什么是循环队列？队列头尾相接的顺序存储结构称为...

大话数据结构九：队列的链式存储结构（链队列）

2016年07月27日 35 阅读

大话数据结构九：队列的链式存储结构（链队列）2014-12-301. 链队列的特点：链队列其实就是单链表，只不过它是先进先出的单链表，为了实现方便，程序中设置了队头（front），队尾（rear）两个指针。2. Java使用链表实现队列://结点类，包含结点的数据和指向下一个节点的引用public class Node<E> {private E data; // 数据域private Node<E> next; // 指针域保存着...

大话数据结构十：字符串的模式匹配（BF算法）

2016年07月27日 39 阅读

大话数据结构十：字符串的模式匹配（BF算法）2014-12-301. BF算法简介：BF（Brute Force）算法是普通的模式匹配算法，又称为朴素匹配算法或蛮力算法，该算法最大缺点就是字符匹配失败指针就要回溯，所以性能很低。2. BF算法思想:BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。3...

大话数据结构十一：字符串的模式匹配（KMP算法）

2016年07月27日 38 阅读

大话数据结构十一：字符串的模式匹配（KMP算法）2014-12-301. KMP算法简介：kmp算法是一种改进的字符串匹配算法，相比朴素算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被称为"部分匹配值表"（Particial match table），这种设计是KMP算法最精妙之处。2. KMP算法分析：下面以阮一峰老师博客中的一篇文章来分析KMP算...

大话数据结构十二：字符串的模式匹配（BM算法）

2016年07月27日 34 阅读

大话数据结构十二：字符串的模式匹配（BM算法）2014-12-301. BM算法简介：KMP算法其实并不是效率最高的字符串匹配算法，实际应用的并不多，各种文本编辑器的“查找”功能大多采用的是BM算法（Boyer Moore）。BM算法效率更高，更容易理解。2. BM算法分析：（1） 假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。（2） 首先，&q...

大话数据结构十三：二叉树的链式存储结构（二叉链表）

2016年07月27日 35 阅读

大话数据结构十三：二叉树的链式存储结构（二叉链表）2014-12-301. 关于树① 树的度 — 也即是宽度，简单地说，就是结点的分支数。② 树的深度 — 组成该树各结点的最大层次。③ 森林 — 指若干棵互不相交的树的集合。④ 有序树 — 指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。2. 二叉树的特点i、每个结点最多有两颗子树ii、左子树和右子树是有顺序的，次...

大话数据结构十四：二叉树的顺序存储结构（数组实现）

2016年07月27日 36 阅读

大话数据结构十四：二叉树的顺序存储结构（数组实现）2014-12-301. 顺序存储结构：二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。2. 完全二叉树：完全二叉树由于其结构上的特点，通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号，就得到结点的一个线性系列。如下图：完全二叉树除最下面一层外，各层都被结点充满了，每一层结点的个数恰好是上一层结点个数的2倍，因此通过一个结点的编号就可以推知它的双亲结点及左，右孩子结点的编号：...

大话数据结构十五：线索二叉树

2016年07月27日 36 阅读

大话数据结构十五：线索二叉树2014-12-301. 什么是线索二叉树？n个结点的二叉链表中含有（2n-（n-1）=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。2. 为什么要加线索？① 很多空指针域没有存储任何事物，对内存资源是一种浪费。② 二叉链表中，我们只能知道每个结点指向其左右孩子结点...