长齐克斯-CSDN博客

原创跳表JAVA实现

1.跳表的定义跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。SkipList(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。SkipList让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。在Java的API中已经有了实现：分别是:Conc

2021-05-21 19:58:14 968 3

原创编译原理词法分析JAVA实现

实验要求要求：阐述词法分析系统所要完成的功能词法分析程序的主要任务是将源程序根据单词进行切分，输出相应的token序列。具体地，本程序完成的功能如下：基本功能：能够识别以下内容：1.标识符：（由大小写字母、数字以及下划线组成，但必须以字母或者下划线开头）2.关键字：（①类型关键字：整型、浮点型、布尔型、记录型；②分支结构中的if和else；③循环结构中的do和while；④过程声明和调用中的关键字）3.运算符：（①算术运算符；②关系运算符；③逻辑运算）4.界符：（①用于赋值语句

2021-04-17 22:07:43 2656 1

原创 Maven 中dependencyManagement 和dependencies 的区别

dependencyManagementMaven 使用dependencyManagement 元素来提供了一种管理依赖版本号的方式。通常会在一个组织或者项目的最顶层的父POM 中看到dependencyManagement 元素。使用pom.xml 中的dependencyManagement 元素能让所有在子项目中引用一个依赖而不用显式的列出版本号。Maven 会沿着父子层次向上走，直到找到一个拥有dependencyManagement 元素的项目，然后它就会使用这个dependencyMan

2021-04-05 13:23:11 408

原创模板模式

基本介绍模板方法模式（Template Method Pattern），又叫模板模式(Template Pattern)，在一个抽象类公开定义了执行它的方法的模板。它的子类可以按需要重写方法实现，但调用将以抽象类中定义的方式进行。简单说，模板方法模式定义一个操作中的算法的骨架，而将一些步骤延迟到子类中，使得子类以不改变一个算法的结构，就可以重定义该算法的某些特定步骤这种类型的设计模式属于行为型模式。优点：封装不变部分，扩展可变部分。提取公共代码，便于维护。行为由父类控制，子类实现。

2021-03-17 20:19:20 193

原创代理模式（静态，动态，Cglib）

代理模式的基本介绍代理模式：为一个对象提供一个替身，以控制对这个对象的访问。即通过代理对象访问目标对象.这样做的好处是:可以在目标对象实现的基础上,增强额外的功能操作,即扩展目标对象的功能。被代理的对象可以是远程对象、创建开销大的对象或需要安全控制的对象代理模式有不同的形式, 主要有三种静态代理、动态代理 (JDK代理、接口代理)和 Cglib代理 (可以在内存动态的创建对象，而不需要实现接口，他是属于动态代理的范畴) 。代理模式示意图静态代理模式静态代理在使用时,需要定义接口或者父类

2021-03-17 19:25:41 217

原创享元模式

基本介绍享元模式（Flyweight Pattern）也叫蝇量模式: 运用共享技术有效地支持大量细粒度的对象常用于系统底层开发，解决系统的性能问题。像数据库连接池，里面都是创建好的连接对象，在这些连接对象中有我们需要的则直接拿来用，避免重新创建，如果没有我们需要的，则创建一个享元模式能够解决重复对象的内存浪费的问题，当系统中有大量相似对象，需要缓冲池时。不需总是创建新对象，可以从缓冲池里拿。这样可以降低系统内存，同时提高效率享元模式经典的应用场景就是池技术了，String常量池、数据库连接池、

2021-03-17 15:40:21 210

原创外观模式

基本介绍外观模式（Facade），也叫“过程模式：外观模式为子系统中的一组接口提供一个一致的界面，此模式定义了一个高层接口，这个接口使得这一子系统更加容易使用外观模式通过定义一个一致的接口，用以屏蔽内部子系统的细节，使得调用端只需跟这个接口发生调用，而无需关心这个子系统的内部细节外观模式可以理解为转换一群接口，客户只要调用一个接口，而不用调用多个接口才能达到目的。比如：在pc上安装软件的时候经常有一键安装选项（省去选择安装目录、安装的组件等等），还有就是手机的重启功能（把关机和启动合为一个操作）。

2021-03-17 11:32:12 120

原创组合模式

基本介绍组合模式（Composite Pattern），又叫部分整体模式，它创建了对象组的树形结构，将对象组合成树状结构以表示“整体-部分”的层次关系。组合模式依据树形结构来组合对象，用来表示部分以及整体层次。这种类型的设计模式属于结构型模式。组合模式使得用户对单个对象和组合对象的访问具有一致性，即：组合能让客户以一致的方式处理个别对象以及组合对象意图：将对象组合成树形结构以表示"部分-整体"的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。主要解决：它在我们树型结构的问题中

2021-03-17 10:59:14 121

原创装饰器模式

装饰器模式（Decorator Pattern）允许向一个现有的对象添加新的功能，同时又不改变其结构。这种类型的设计模式属于结构型模式，它是作为现有的类的一个包装。这种模式创建了一个装饰类，用来包装原有的类，并在保持类方法签名完整性的前提下，提供了额外的功能。意图：动态地给一个对象添加一些额外的职责。就增加功能来说，装饰器模式相比生成子类更为灵活。主要解决：一般的，我们为了扩展一个类经常使用继承方式实现，由于继承为类引入静态特征，并且随着扩展功能的增多，子类会很膨胀。优点：装饰类和被装饰

2021-03-17 10:04:32 116

原创桥接模式

基本介绍桥接模式(Bridge模式)是指：将实现与抽象放在两个不同的类层次中，使两个层次可以独立改变。是一种结构型设计模式Bridge模式基于类的最小设计原则，通过使用封装、聚合及继承等行为让不同的类承担不同的职责。它的主要特点是把抽象(Abstraction)与行为实现(Implementation)分离开来，从而可以保持各部分的独立性以及应对他们的功能扩展优点： 1、抽象和实现的分离。 2、优秀的扩展能力。 3、实现细节对客户透明。缺点：桥接模式的引入会增加系统的理解与设计难度，由于

2021-03-17 01:00:49 538

原创原型模式

基本介绍原型模式(Prototype模式)是指：用原型实例指定创建对象的种类，并且通过拷贝这些原型，创建新的对象原型模式是一种创建型设计模式，允许一个对象再创建另外一个可定制的对象，无需知道如何创建的细节工作原理是:通过将一个原型对象传给那个要发动创建的对象，这个要发动创建的对象通过请求原型对象拷贝它们自己来实施创建，即对象.clone()这种模式是实现了一个原型接口，该接口用于创建当前对象的克隆。当直接创建对象的代价比较大时，则采用这种模式。例如，一个对象需要在一个高代价的数据库操作之后被

2021-03-15 21:17:03 110 1

原创 JAVA深拷贝实现方式

浅拷贝的介绍对于数据类型是基本数据类型的成员变量，浅拷贝会直接进行值传递，也就是将该属性值复制一份给新的对象。对于数据类型是引用数据类型的成员变量，比如说成员变量是某个数组、某个类的对象等，那么浅拷贝会进行引用传递，也就是只是将该成员变量的引用值（内存地址）复制一份给新的对象。因为实际上两个对象的该成员变量都指向同一个实例。在这种情况下，在一个对象中修改该成员变量会影响到另一个对象的该成员变量值浅拷贝是使用默认的 clone()方法来实现深拷贝基本介绍复制对象的所有基本数据类型

2021-03-15 21:02:21 2952

原创 Java Servlet 小结

什么是 ServletServlet 是 JavaEE 规范之一。规范就是接口Servlet 就 JavaWeb 三大组件之一。三大组件分别是：Servlet 程序、Filter 过滤器、Listener 监听器。Servlet 是运行在服务器上的一个 java 小程序，它可以接收客户端发送过来的请求，并响应数据给客户端。手动实现 Servlet 程序1、编写一个类去实现 Servlet 接口2、实现 service 方法，处理请求，并响应数据3、到 web.xml 中去配置 servle

2021-03-01 11:32:57 146

原创 Java面向对象基础总结

基础知识面向过程(POP) 与面向对象(OOP)二者都是一种思想，面向对象是相对于面向过程而言的。面向过程，强调的是功能行为，以函数为最小单位，考虑怎么做。面向对象，将功能封装进对象，强调具备了功能的对象，以类/对象为最小单位，考虑谁来做。面向对象更加强调运用人类在日常的思维逻辑中采用的思想方法与原则，如抽象、分类、继承、聚合、多态等bJavaBeanJavaBean是一种Java语言写成的可重用组件。所谓javaBean，是指符合如下标准的Java类：类是公共的有一个无参的公共的

2021-02-28 14:42:14 933

原创 Java IO流详解

File类的使用java.io.File类：文件和文件目录路径的抽象表示形式，与平台无关File 能新建、删除、重命名文件和目录，但 File 不能访问文件内容本身。如果需要访问文件内容本身，则需要使用输入/输出流。想要在Java程序中表示一个真实存在的文件或目录，那么必须有一个File对象，但是Java程序中的一个File对象，可能没有一个真实存在的文件或目录。File对象可以作为参数传递给流的构造器File 类的使用：常用构造器public File(String pathna

2021-02-26 15:55:18 308

原创 JAVA集合框架总结

Java 集合框架概述一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而Java 集合就像一种容器，可以动态地把多个对象的引用放入容器中。数组在内存存储方面的特点：数组初始化以后，长度就确定了。数组声明的类型，就决定了进行元素初始化时的类型数组在存储数据方面的弊端：数组初始化以后，长度就不可变了，不便于扩展数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接

2021-02-23 14:11:29 1891 4

原创图的深度优先搜索与广度优先搜索(JAVA）

图的存储结构一、邻接矩阵 (Adjacency Matrix)表示(数组表示法)基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：无向图的邻接矩阵：存储结构特点：主对角线为 0 且一定是对称矩阵；有向图的邻接矩阵：假设图G有n个顶点e条边，则该图的存储需求为O(n+n^2) = O(n^2) ，与边的条数e无关。存储结构的建立----算法实现的步骤：确定图

2021-02-09 23:55:12 12189 1

原创 AVL树

AVL树的性质AVL树(Balanced Binary Tree or Height-Balanced Tree)AVL树或者是空二叉树，或者是具有如下性质的BST：根结点的左、右子树高度之差的绝对值不超过1且根结点左子树和右子树仍然是AVL树。结点的平衡因子BF（Balanced Factor）一个结点的左子树与右子树的高度之差。AVL树中的任意结点的BF只可能是-1，0和1。AVL树的ASL可保持在O(log2n)在AVL树在结点高度上采用相对平衡的策略，使其平均性能接近于B

2021-02-09 00:27:38 19290 1

原创二叉排序树(BST)

BST结构特点任意一个结点的关键字，都大于(小于)其左(右)子树中任意结点的关键字，因此各结点的关键字互不相同按中序遍历二叉查找树所得的中序序列是一个递增的有序序列，因此，二叉查找树可以把无序序列变为有序序列。同一个数据集合，可按关键字表示成不同的二叉查找树，即同一数据集合的二叉查找树不唯一；但中序序列相同。若它的左子树不空，则左子树上所有结点的关键字的值都小于根结点关键字的值；若它的右子树不空，则右子树上所有结点的关键字的值都大于根结点关键字的值；它的左、右子树本身又是一个二叉查找树。

2021-02-08 12:51:24 13091 1

原创哈夫曼树与哈夫曼编码(java实现)

二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。记为：举例：给定4个叶子结点，其权值分别为{2，3，4，7}，可以构造出形状不同的二叉树哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树，称为哈夫曼树，亦称最优二叉树。哈夫曼树的特点：权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。（构造哈夫曼树的核心思想）只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。n个

2021-02-04 00:17:20 1824 2

原创线索二叉树

二叉树的线索链表存储结构二叉链表的空间利用情况：在n（n≥1）个结点的二叉树左右链表示中，只有n-1个指向子树的指针，却有n+1个空指针域。如何利用空指针域解决上述问题？若结点p有左孩子，则p->lchild指向其左孩子结点，否则令其指向其（先序、中序、后序、层序）前驱；若结点p有右孩子，则p->rchild指向其右孩子结点，否则令其指向其（先序、中序、后序、层序）后继；如何区分指针是指向其左/右孩子的指针还是指向某种遍历的前驱/后继？在每个结点中增加两个标志位，以区分该结点的

2021-02-03 16:25:18 725

原创二叉树的顺序存储结构

完全二叉树的顺序存储结构的性质：若i = 1, 则 i 是根结点，无父结点；若i > 1, 则 i 的父结点为 i/2 ,向下取整若 2i <= n, 则 i 有左儿子且为 2i；否则，i 无左儿子。若 2i+1 <= n, 则 i 有右儿子且为2i+1；否则，i 无右儿子若 i 为偶数, 且 i < n , 则有右兄弟，且为 i + 1。若 i 为奇数, 且 i < n && i != 1, 则其左兄弟，且为 i-1完全二叉树的顺序存储结构

2021-02-03 14:24:03 6244

原创二叉树的前序中序和后序遍历

遍历的定义根据某种策略，按照一定的次序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。这个过程称为二叉树的遍历。遍历的结果是二叉树结点的线性序列。非线性结构线性化。策略：左孩子结点一定要在右孩子结点之前访问先序（根）遍历二叉树若二叉树为空，则返回；否则，①访问根结点；②先序遍历根结点的左子树;③先序遍历根结点的右子树;所得到的线性序列分别称为先序（根）序列。先序遍历序列为：A B D G C E F中序（根）遍历二叉树若二叉树为空，则返回；否则，①中序遍历根结

2021-02-03 13:26:03 425

原创散列技术

散列技术的基本思想把记录（元素）的存储位置和该记录的关键字的值之间建立一种映射关系。关键字的值在这种映射关系下的像，就是相应记录在表中的存储位置。散列技术在理想情况下，无需任何比较就可以找到待查的关键字，其查找的期望时间为O(1)。散列技术的相关概念散列函数：设 U 表示所有可能出现的关键字集合，K表示实际出现（实际存储）的关键字集合，即K 属于U，F[B – 1]是一个数组，其中B =O( | K| )。则，从 U 到表F[ B – 1]下标集合上的一个映射 h：U－>{ 0, 1, 2,

2021-01-30 16:46:00 1736

原创常见查找算法

二分查找二分查找：请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。二分查找的思路分析首先确定该数组的中间的下标mid = (left + right) / 2然后让需要查找的数 findVal 和 arr[mid] 比较2.1 findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找2.2 findVal < arr[m

2021-01-29 16:36:23 298

原创八大排序算法

冒泡排序基本思想冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。显然，处理1遍之后，“最轻”的记录就浮到了最高位置；处理2遍之后，“次轻”的记录就浮到了次高位置。在作第二遍处理时，由于最高位置上的记录已是“最轻”的，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的记录的关键字，因为经过前面i-1遍的处理，它们已正确地排好序。平均情

2021-01-26 14:53:37 380

原创递归求解八皇后问题

递归需要遵守的重要规则执行一个方法时，就创建一个新的受保护的独立空间(栈空间)方法的局部变量是独立的，不会相互影响, 比如n变量如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。八皇后问题介绍八皇后问题，是一个古老而著名的问题，是回溯算法的典

2021-01-25 15:32:25 158

原创中缀表达式转后缀并求解计算

中缀表达式转换为后缀表达式具体步骤如下:初始化两个栈：运算符栈s1和储存中间结果的栈s2；从左至右扫描中缀表达式；遇到操作数时，将其压s2；遇到运算符时，比较其与s1栈顶运算符的优先级：4.1 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；4.2否则，若优先级比栈顶运算符的高，也将运算符压入s1；4.3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；遇到括号时：5.1 如果是左括号“(”，则直接压入s15.2如果是右括号“

2021-01-24 15:12:23 483 1

原创使用栈完成算术表达式的计算

实现思路需要两个栈来分别存储我们的操作符和数字通过一个 index 值（索引），来遍历我们的表达式如果我们发现是一个数字, 就直接入数栈如果发现扫描到是一个符号, 就分如下情况3.1 如果发现当前的符号栈为空，就直接入栈3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.

2021-01-24 13:23:04 1047

原创栈的原理与实现（数组模拟与链表模拟）

栈的定义栈的英文为(stack)栈是一个先入后出(FILO-First In Last Out)的有序列表。栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除栈的特性：后进先出栈的应用场景：子程序的调用：在跳往子程序前，会先

2021-01-24 01:22:47 148

原创单向循环链表与约瑟夫问题求解

单向环形链表将单链表中中断结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾详解的单链表称为单循环链表，简称循环链表；示意图：注意：　　①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。　　②在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算

2021-01-23 17:59:24 261

原创双向链表的实现与常见操作

双向链表：在单链表的各结点中再设置一个指向其前驱结点的指针域示例:结点结构：优点：双向链表的主要优点是对于任意给的结点，都可以很轻易的获取其前结点和后结点实现双向查找（单链表不易做到）表中的位置i 可以用指示含有第i 个结点的指针表示。缺点：空间开销大，每个结点需要保存next和prev两个属性，因此需要更多的空间开销，同时结点的插入与删除操作也将更加耗时，因为需要操作更多的指向操作。插入操作图解：删除操作图解：代码实现：定义一个双向链表结构如下：/ 定义HeroNode

2021-01-23 12:45:17 520

原创单向链表的实现与常见操作

单链表的定义:一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个单向链接式存储结构，简称单向链表或单链表。(a1, a2 ,a3, a4)的存储示意图：存储结构特点：逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；需要额外空间存储元素之间的关系非随机访问存取结构（顺序访问）逻辑结构示意图：先定义一个测试链表结构如下：英雄节点：class HeroNode { public int no; pu

2021-01-23 10:57:15 441

原创数组实现循环队列

循环队列在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。可以解决假溢出问题。从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。顺序队列的假溢出：当元素被插

2021-01-22 22:18:30 2698

空空如也

空空如也