设计模式 | 创建者模式之单例模式
转载自:[5. 单例模式 — Graphic Design Patterns] 1. 模式动机 对于系统中的某些类来说,只有一个实例很重要,例如,一个系统中可以存在多个打印任务,但是只能有一个正在工作的任务;一个系统只能有一个窗口管理器或文件系统;一个系统只能有一个计时工具或ID(序号)生成器。 如何保证一个类只有一个实例并且这个实例易于被访问呢?定义一个全局变量可以确保对象随时都可以...
转载自:[5. 单例模式 — Graphic Design Patterns] 1. 模式动机 对于系统中的某些类来说,只有一个实例很重要,例如,一个系统中可以存在多个打印任务,但是只能有一个正在工作的任务;一个系统只能有一个窗口管理器或文件系统;一个系统只能有一个计时工具或ID(序号)生成器。 如何保证一个类只有一个实例并且这个实例易于被访问呢?定义一个全局变量可以确保对象随时都可以...
转载自:[3. 抽象工厂模式 1.模式动机 在工厂方法模式中具体工厂负责生产具体的产品,每一个具体工厂对应一种具体产品,工厂方法也具有唯一性,一般情况下,一个具体工厂中只有一个工厂方法或者一组重载的工厂方法。 但是有时候我们需要一个工厂可以提供多个产品对象,而不是单一的产品对象。 为了更清晰地理解工厂方法模式,需要先引入两个概念: 产品等级结构 :产品等级结...
转载自:[2. 工厂方法模式 1. 模式动机 现在对该系统进行修改,不再设计一个按钮工厂类来统一负责所有产品的创建,而是将具体按钮的创建过程交给专门的工厂子类去完成。 我们先定义一个抽象的按钮工厂类,再定义具体的工厂类来生成圆形按钮、矩形按钮、菱形按钮等,它们实现在抽象按钮工厂类中定义的方法。 这种抽象化的结果使这种结构可以在不修改具体工厂类的情况下引进新的产品,如果出现新的按钮类...
转载自:[1. 简单工厂模式 1. 模式动机 考虑一个简单的软件应用场景,一个软件系统可以提供多个外观不同的按钮(如圆形按钮、矩形按钮、菱形按钮等), 这些按钮都源自同一个基类. 不过在继承基类后不同的子类修改了部分属性从而使得它们可以呈现不同的外观,如果我们希望在使用这些按钮时,不需要知道这些具体按钮类的名字. 只需要知道表示该按钮类的一个参数并提供一个调用方便的方法,把该参数传入...
转载自 : 设计模式之六大原则(转载) - 海 子 - 博客园 前言: 设计模式(Design pattern) 是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。 使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 设计模式使代码编制真正工程化,设计模式是软件工程的基石,如同大厦的一块块砖石一样。 只有精通了设计模式,才敢说真正理解了软件工程。 ...
转载自:[看懂UML类图和时序图 — Graphic Design Patterns] 1-从一个示例开始: 请看以下这个类图,类之间的关系是我们需要关注的: 车的类图结构为<<abstract>>,表示车是一个抽象类; 它有两个继承类:小汽车和自行车;它们之间的关系为实现关系,使用带空心箭头的虚线表示; 小汽车为与SUV之间也是继承关系,它们...
转载自 UML建模中的时序图详解 - CSDN博客 1.时序图简介(Brief introduction) 时序图(Sequence Diagram) 是显示对象之间交互的图,这些对象是按时间顺序排列的。顺序图中显示的是参与交互的对象及其对象之间消息交互的顺序。时序图中包括的建模元素主要有:对象(Actor)、生命线(Lifeline)、控制焦点(Focus of control)、消息...
转载自:[深入理解JVM(5)——虚拟机类加载机制 - 王泽远的博客 Crow’s Blog](https://crowhawk.github.io/2017/08/21/jvm_5/) 虚拟机描述类的数据从 Class 文件加载到内存,并对数据进行校验,转换解析和初始化,最终形成可以被虚拟机直接使用的java类型。这就是虚拟机的类加载机制。 在上图中,...
1.概述: 我们都知道,在当前的Java中(1.0)之后,编译器讲源代码转成字节码,那么字节码如何被执行的呢? 这就涉及到了JVM的字节码执行引擎,执行引擎负责具体的代码调用及执行过程。就目前而言,所有的执行引擎的基本一致: 输入:字节码文件 处理:字节码解析 输出:执行结果。 物理机的执行引擎是由硬件实现的,和物理机的执行过程不同的是虚拟机的执行引擎由于自己实现的。 ...
1. 首先需要解决的问题:哪些对象已经死亡 1.1 引用计数算法 引用分析算法是这样的: 给每一个对象添加一个引用计数器, 每当有一个地方使用,计数器就加一; 任何时刻计数器为0的对象就是 不可能再被使用的。 缺点:难以解决对象之间的循环引用问题 1.2 可达性分析算法(商用程序语言的主流实现): 这个算法的基本思想就是通过一系列的”GC ROOTS”的对象作为起始点...
程序计数器 作用: 程序计数器是较小的内存空间,它可以当做是当前线程所执行的字节码的行号指示器。 字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令,分支,循环,跳转,异常处理,线程恢复等基础功能都需要依赖这个程序计数器来完成。 程序计数器的线程隔离性 java 虚拟机的多线程都是通过线程轮流切换并分配处理器执行时间的方式来实现的,在任...
转载自图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 归并排序是利用归并的思想实现的排序方式,该算法采用经典的分治策略。(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。 分而治之 可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭...
1. 简单选择排序 选择排序(Selection Sort)是一种简单直观的排序算法。 它的工作原理如下: 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 以此类推,直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。 选择排序...
思想: “快速排序”的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(`pivot`)。 (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。 (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。 举例来说,现在有一个数据集${85, 24, 63, 45,...
1. 直接插入排序: 每次从无序表中取出最后一个元素,把它插入到有序表的合适位置,使有序表仍然有序。 1. 详解: 从数组的第二个元素开始,将数组中的每一个元素按照(升序或者降序)规则插入到已排好序的数组中以达到排序的目的. 一般情况下将数组的第一个元素作为起始元素,从第二个元素开始依次插入。 由于要插入到的数组是已经排好序的,所以只要从右向左(或者从后向前)找到排序插入点插入元素...
1. 迪杰斯特拉(Dijkstra)算法: 1. 定义概览 Dijkstra(迪杰斯特拉) 算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。 主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。 问题描...
拓扑排序 1. 什么是拓扑排序: 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件: 每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图(DAG)才有拓扑排序,非DAG图没有...
转载自: [勿在浮沙筑高台] 连通图:在无向图中,若任意两个顶点$v_{i}$与$v_{j}$都有路径相通,则称该无向图为连通图。 强连通图:在有向图中,若任意两个顶点$v_{i}$与$v_{j}都有路径相通,则称该有向图为强连通图。 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。 生成树:一个连通图的生成树...
图的深度优先遍历(DFS) 深度优先搜索(depth-first search)是对先序遍历(preorder traversal)的推广。我们从某个顶点 v 开始处理 v,然后递归地遍历所有与 v 邻接的顶点。 实现思想: 在深度优先搜索中,对于最新发现的顶点,如果它还有以此为起点而未探测到的边,就沿此边继续探测下去,当节点 v 的所有边都已被探寻过,探索将回溯到发现节点 v...
概念: 图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。 无边图:若顶点$V_{i}$到$V_{j}$之间的边没有方向,则称这条边为无项边(Edge), 用序偶对$(V_{i},V_{j})$标示。 对于下图无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D}; 边...
介绍: 红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在对数时间内完成查找的数据结构。这个时候,红黑树站了出来。 红黑树是在普通二叉树上,对每个节点添加一个颜色属性形成的,同时整个红黑二叉树需要同时满足一下五条性质: 每个节点或者是...
转载自:B-树的详解 - CSDN博客 B 树: 1.背景 磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候...
背景: AVL(Adelson-Velskii和Landis发明者的首字母)树 是带有平衡条件的二叉查找树。 二叉查找树的性能分析: 在一颗左右子树高度平衡情况下,最优的时间复杂度为$O(log_{2}{n})$,这与这半查找相同; 在一个只有右子树的二叉树中,最差的时间复杂度会脱变为线性查找$O(n)$。 由于二叉查找树存在以上问题,所以AVL树通过旋转使自身始...
二叉查找树(Binary Search Tree),又被称为二叉搜索树。设x为二叉查找树中的一个结点,x节点包含关键字key,节点x的key值记为 $key[x]$。 如果y是x的左子树中的一个结点,则 $key[y] <= key[x]$; 如果y是x的右子树的一个结点,则 $key[y] >= key[x]$。 说明: 若任意节点的左子树不空,则左子树上所有结点...
概念: 二叉树的遍历分为以下三种: 先序遍历:遍历顺序规则为【根左右】 中序遍历:遍历顺序规则为【左根右】 后序遍历:遍历顺序规则为【左右根】 举个例子,看下图: 先序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 编程实现方式: 三种方法中,递归最为简单,栈次之,循环最为麻烦。递归的深度如果太大则会导致栈溢出;栈的方式需要额外的...
定义: 1. 节点的类型: 在非空二叉树中,第i层的结点总数最大为$2^{i}-1,i\ge1$(满树情况) 深度为h的二叉树最多有 $2^h-1, h\ge1$ 个结点,最少有$h$个结点 对于任意一棵二叉树,设其总结点数为$N$,如果其叶结点(度为0的结点)数为$N_0$,而度数为2的结点总数为$N_2$,则$N_0=N_2+1$,度为1的结点数$N_1=N-N_0-N...
转载自 : 树的三种存储结构 - CSDN博客 定义 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。 在任意一棵非空树中: 有且仅有一个特定的称为根(Root)的结点; 当n>1时,其余结点可分为m(m>O)个互不相交的有限集$T_1,T2,…,T_m$,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如图...
线性表是一种典型的线性结构。 线性表的顺序实现 顺序表是线性表的顺序存储结构,指的是用一组地址连续的存储单元依次存储线性表的数据元素. 顺序表具备如下两个基本特征: 顺序表中的所有元素所占的存储空间是连续的; 顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设顺序表的每个元素需占用$K$个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺...
栈: 栈是只能在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为栈底(BOTTOM)。 当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素,从而也是最先被移除(出栈)的元素;栈底元素总是最先被插入的元素,从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构 栈的基本运算有三种:入栈、出栈与读栈顶,时间复杂度都是O(...
串的存储表示和实现: 串是一种特殊的线性表,其存储表示和线性表类似但又不完全相同。串的存储方式取决于将要对串所进行的操作. 串在计算机中有3种表示方式: 定长顺序存储方式: 将串定义成字符数组,利用串名可以直接访问串值。用这种表示方式,串的存 储空间在编译时确定,其大小不能改变。 堆分配存储方式: 仍然用一组地址连续的存储单 元来依次存储串中的字符序列...
简要