线性表之双向链表的实现
前言主要是模拟Java中的LinkList的实现。 LinkedList概述LinkedList是一种双向链表。 根据双向链表的特点,会有头节点和尾节点,并且节点之间是通过前驱指针和后继指针来维护关系的,而不是像数组那样通过位置下标来维护节点间关系的。所以既可以从头到尾遍历,又可以从尾到头遍历。 双向链表是包含两个指针的,pre指向前一个节点,next指向后一个节点,但是第一个节点head的pre指向null,最后一个节点的tail的next指向null。 LinkedList是一个继承于AbstractSequentialList,并实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实现了Deque接口,使得LinkedList类也具有队列的特性(addFirst(),removeLast()…),它可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。 12345public class LinkedList<E&g...
线性表之其它链表
前言介绍双向链表和循环链表 简介双向链表单链表的一个优点是结构简单,但是它也有一个缺点,即在单链表中只能通过一个结点的引用访问其后续结点,而无法直接访问其前驱结点,要在单链表中找到某个结点的前驱结点,必须从链表的首结点出发依次向后寻找,但是需要Ο(n)时间。为此我们可以扩展单链表的结点结构,使得通过一个结点的引用,不但能够访问其后续结点,也可以方便的访问其前驱结点。扩展单链表结点结构的方法是,在单链表结点结构中新增加一个域,该域用于指向结点的直接前驱结点。扩展后的结点结构是构成双向链表的结点结构,如图所示: 双向链表是通过上述定义的结点使用 pre 以及 next 域依次串联在一起而形成的。一个双向链表的结构如图所示: 在双向链表中同样需要完成数据元素的查找、插入、删除等操作。在双向链表中进行查找与在单链表中类似,只不过在双向链表中查找操作可以从链表的首结点开始,也可以从尾结点开始,但是需要的时间和在单链表中一样。 在使用双向链表实现链接表时,为使编程更加简洁,我们使用带两个哑元结点的双向链表来实现链接表。其中一个是头结点,另一个是尾结点,它们都不存放数据元素,头结点的p...
线性表之单链表的实现
前言今天主要是来模拟单链表的基本功能。 简介链表是一系列的存储数据元素的单元,通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为 结点(node) 一种最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点,称为单链表。 特点链表的第一个结点和最后一个结点,分别称为链表的 首结点和 尾结点。尾结点的特征是其 next 引用为空(null)。链表中每个结点的 next 引用都相当于一个指针,指向另一个结点,借助这些 next 引用,我们可以从链表的首结点移动到尾结点。在单链表中通常使用 head 引用来指向链表的首结点,由 head 引用可以完成对整个链表中所有节点的访问。 在单链表结构中还需要注意的一点是,由于每个结点的数据域都是一个 Object 类的对象,因此,每个数据元素并非真正如图中那样,而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。与数组类似...
线性表之顺序表的实现
前言今天主要是来模拟Java中ArrayList的基本功能。 List接口首先定义List接口 /** * 线性表接口 * * @ClassName List * @Description 线性表接口 * @Author HuangCanCan * @Date 2019/8/11 15:30 * @Version 1.0 **/ public interface List { /** * 返回线性表的大小,即数据元素的个数。 */ public int size(); /** * 返回线性表中索引为 index的数据元素 */ public Object get(int index); /** * 如果线性表为空返回 true,否则返回 false。 */ public boolean isEmpty(); /** * 判断线性表是否包含数据元素 e */ public boolean contains(Object e); /** ...
线性表
前言下面几节都来认识线性表,模拟Java中的顺序存储结构和链式存储结构的实现。 线性表(linear list)线性表是n个类型相同数据元素的有限序列,通常记作(a 0 , a 1 , …a i-1 , a i , a i+1 …,a n-1 )。 1.相同数据类型 在线性表的定义中,我们看到从a 0 到a n-1 的n个数据元素是具有相同属性的元素。比如说可以都是数字,例如(23, 14, 66, 5, 99);也可以是字符,例如(A, B, C, … Z);当然也可以是具有更复杂结构的数据元素,例如学生、商品、装备。相同数据类型意味着在内存中存储时,每个元素会占用相同的内存空间,便于后续的查询定位。 2.序列(顺序性) 在线性表的相邻数据元素之间存在着序偶关系,即a i-1 是a i 的直接前驱,则a i 是a i-1 的直接后续,同时a i 又是a i+1 的直接前驱,a i+1 是a i 的直接后续。唯一没有直接前驱的元素a 0 一端称为表头,唯一没有后续的元素a n-1 一端称为表尾。除了表头和表尾元素外,任何一个元素都有且仅有一个直接前驱和直接后继。 3.有限 线性表...
算法的基本概述
前言今天来看一哈算法的相关概念。 算法的基本概述算法(algorithm)算法是指令的集合,是为解决特定问题而规定的一系列操作。它是明确定义的可计算过程,以一个数据集合作为输入,并产生一个数据集合作为输出。一个算法通常来说具有以下五个特性: 输入:一个算法应以待解决的问题的信息作为输入。 输出:输入对应指令集处理后得到的信息。 可行性:算法是可行的,即算法中的每一条指令都是可以实现的,均能在有限的时间内完成。 有穷性:算法执行的指令个数是有限的,每个指令又是在有限时间内完成的,因此整个算法也是在有限时间内可以结束的。 确定性:算法对于特定的合法输入,其对应的输出是唯一的。即当算法从一个特定输入开始,多次执行同一指令集结果总是相同的。 简单的说,算法就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是算法的逻辑形式,后者是算法的代码形式。 举例:如何求0+1+2+3+...10000=? 算法1:依次相加 while do-while for 算法2:高斯解法:首尾相加*50 或着梯度算法:(上底+下底)*高/...
数据结构的基本概述
前言从今天开始,我们就来巩固一下数据结构和算法的基本知识。 数据结构的基本概述有哪些数据结构?线性表、栈、队列、(字符)串、数组、广义表、树、二叉树、图。重点是线性表、二叉树 什么是数据数据(data)是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据的含义非常广泛,除了通常的数值数据、字符、字符串是数据以外,声音、图像等一切可以输入计算机并能被处理的都是数据。例如:除了表示人的姓名、身高、体重等的字符、数字是数据,人的照片、指纹、三维模型、语音指令等也都是数据。 数据项数据项(data item)具有原子性,是不可分割的最小数据单位。如:描述学生相关信息的姓名、性别、学号等都是数据项;三维坐标中的每一维坐标值也是数据项。数据项具有原子性,是不可分割的最小单位。 数据元素数据元素(data element )是数据的基本单位,是数据集合的个体,通常由若干个数据项组成,在计算机程序中通常作为一个整体来进行处理。例如:一条描述一位学生的完整信息的数据记录就是一个数据元素;空间中一点的三维坐标也可以是一个数据元素。 数据对象数据对象(data object )是性质...
展开运算符与rest参数
前言这周在工作中遇到了vue.js中的对象展开运算符的语法,有点没搞懂。现在记录学习一下。这里主要学习一下,ES6的rest参数,展开运算符(对象展开运算符、数组展开运算符、函数展开运算符),感觉它们有点相似。 rest参数 (剩余参数)剩余参数的语法:允许我们将一个不定数量的参数表示为一个数组。 语法: function(a, b, ...theArgs) { // ... } 由于JavaScript函数允许接收任意个参数,于是我们就不得不用arguments来获取所有参数: function foo(a, b) { var i, rest = []; if (arguments.length > 2) { for (i = 2; i<arguments.length; i++) { rest.push(arguments[i]); } } console.log('a = ' + a); console.log('b = ' + b)...
try-with-resources机制
Java7提供了try-with-resources机制,其类似Python中的with语句,将实现了java.lang.AutoCloseable 接口的资源定义在 try 后面的小括号中,不管 try 块是正常结束还是异常结束,这个资源都会被自动关闭。 try 小括号里面的部分称为 try-with-resources 块。 Java 7 的编译器和运行环境支持新的 try-with-resources 语句,称为 ARM 块(Automatic Resource Management) ,自动资源管理。 使用try-with-resources机制的代码如下所示: public static String readFirstLineFromFile(String path) throws IOException { try (BufferedReader reader = new BufferedReader(new FileReader(path))) { return reader.readLine(); } } 在Java7之前,只能...
Git合并特定commits到另一个分支
前言这周遇到一个使用git有点特别的操作。如何从一个分支合并特定的commits到另一个分支。有时候只合并你需要的那些commits,不需要的commits就不合并进去了。平常都很少遇到这样的情况,所以查了一下资料,记录一下。 合并某个分支上的单个commit使用git log或查git log --graph --pretty=oneline --abbrev-commit 查看提交的信息,记住commit id. git checkout [branch-name] 切换到合并的分支 git cherry-pick <commit-id> 把某个commit id提交合并到当前分支 如: dd2e86 - 946992 -9143a9 - a6fd86 - 5a6057 [master] \ 76cada - 62ecb3 - b886a0 [feature] 比如,feature 分支上的commit 62ecb3 非常重要,它含有一个bug的修改,或其他人想访问的内容。无论什么原因,你现在只需要将62ecb3 合并到master,而不合并...