Java 08 | 数据结构 - 单向链表 Singly Linked List

链表 Linked List 前面有介绍以array为基础搭建的列表,支持自动扩容, 各种插入,删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互,用户更直观地知道自己是在调用链表。如果直接与node类交互,用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用,所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法....

2017-01-12 · 2 min · Cong Chan

Java 07 | 数据结构 - 用数组构建数据列表 list

列表 List 前面说到Java的数组无法更改长度,那么也就无法实现插入或者删除数组成员。Java提供了功能更丰富的数据结构 - 列表(list)。所谓列表,即有序的集合(序列),用户可以精确地控制每个元素插入到列表中的哪个位置。用户可以通过整数索引(列表中的位置)来访问元素,并搜索列表中的元素(详细可进一步参考oracle官网)。 这里我们尝试以java的array为基础实现一个列表,目标是实现自动扩容 (Java中的ArrayList不仅仅有自动扩容, 也继承了[List]的其他功能)。在探索的过程中, 可以顺带学习很多相关的内容. 使用自上而下的设计思想搭建一个框架: 先写出最基础的部分, 也就是一个构造器,前面学过了整数数组,我们直接拿来用 /** Array based list. */ // index 0 1 2 3 4 5 6 7 // items: [6 9 -1 2 0 0 0 0 ...] // size: 5 public class AList { private int[] items; private int size; /** 构造一个初始容量100的数组,初始有效数据成员为0. */ public AList() { items = new int[100]; size = 0; } /** 下面添加其他方法 */ } 然后思考我们需要什么功能,把功能需求转化为实例方法instance method的形式,先把方法的外壳描绘出来,注释上该方法的功能(目的),输入值,返回值是什么之类的。具体的功能实现可以先空着,之后一步步丰富。...

2016-12-29 · 2 min · Cong Chan

Java 06 | 数据结构 - array 数组

数组(Array) 数组是一种特殊的对象,有一个固定的数组长度参数N,由一连串(N个)连续的带编号的内存块组成,每个都是相同的类型(不像Python可以包含不同类型),索引从0到N-1编号。A[i]获得数组A的第i个元素。这与普通的类实例不同,类实例有具体变量名命名的内存块。 数组实例化,包含对象的数组 Array Instantiation, Arrays of Objects 要创建最简单的整数数组, 有三种方式: x = new int [3]; //创建一个指定长度的数组,并用默认值(0)填充每个内存块。 y = new int [] {1,2,3,4,5}; //创建一个合适大小的数组,以容纳指定的初始值 int [] z = {9,10,11,12,13}; //省略了new,只能结合变量声明使用。 创建一组实例化对象: public class DogArrayDemo { public static void main(String[] args) { /* Create an array of two dogs. */ Dog[] dogs = new Dog[2]; dogs[0] = new Dog(8); dogs[1] = new Dog(20); /* Yipping will result, since dogs[0] has weight 8. */ dogs[0]....

2016-12-27 · 1 min · Cong Chan

Java 05 | 数据类型

数据类型 数据类型是程序设计语言描述事物、对象的方法。Java数据类型分为基本类型(内置类型)和引用类型(扩展类型)两大类。基本类型就是Java语言本身提供的基本数据类型,比如,整型数,浮点数,字符,布尔值等等。而引用类型则是Java语言根据基本类型扩展出的其他类型,Java要求所有的引用扩展类型都必须包括在类定义里面,这就是Java为什么是面向对象编程语言的原因… 上面的定义有点抽象,要理解数据类型,需要先理解一个问题: 神秘的海象问题 尝试预测下面的代码运行时会发生什么。b的变化是否会影响a?提示:类似Python。 Walrus a = new Walrus(1000, 8.3); Walrus b; b = a; b.weight = 5; System.out.println(a); System.out.println(b); 同样尝试预测下面的代码运行时会发生什么。x的改变是否影响y? int x = 5; int y; y = x; x = 2; System.out.println("x is: " + x); System.out.println("y is: " + y); 答案是b的变化会影响a, 但x的改变不影响y,具体见可视化过程. 这里的差别虽然微妙, 但其背后的原理对于数据结构的效率来说是非常重要的,对这个问题的深入理解也将引导我们写出更安全,更可靠的代码。 基本类型 Primative Types 计算机中的所有信息都以一系列1和0的形式存储在内存中,这些二进制的0和1就是比特位(bits)。比如72和“H”在内存一般以01001000的形式存储,对他们的形式是一样的。一个引申问题就是:Java代码如何解释01001000,怎么知道应该解释为72还是“H”? 通过类型types,预先定义好类型即可, 以下代码 char x = 'H'; int y = x; System.out.println(x); System.out.println(y); 会分别得到“H”和72. 在这种情况下,x和y变量都包含几乎相同的bits,但是Java解释器在输出时对它们进行了不同的处理。 Java有8种基本类型:byte,short,int,long,float,double,boolean和char。 变量声明 Declaring Variables...

2016-12-26 · 2 min · Cong Chan

Java 04 | 类 class - 03 嵌套类

嵌套类 我们经常需要在某个类A中使用另一个类B,如果设计时我们知道类B只有在类A中有被使用的可能性, 那么我们可以把类B定义在类A中, 作为类A的嵌套类, 类A就称之为外部类. 这样做可以隐藏类名,减少全局的标识符,从而限制用户能否使用该类建立对象。这样可以提高类的抽象能力,并且强调了两个类(外围类和嵌套类)之间的主从关系。 A nested class is any class whose declaration occurs within the body of another class or interface. A top level class is a class that is not a nested class. 嵌套类分为两类:静态和非静态。声明为static的嵌套类简称为静态嵌套类。非静态嵌套类称为内部类(inner class)。 class OuterClass { ... static class StaticNestedClass { ... } class InnerClass { ... } } 作为OuterClass的成员,嵌套类可以声明为private,public,protected或package private。外部类只能声明为public或package private。更多详情参考官网. 内部类 内部类可以直接访问外部类的方法和变量(即使是private的也可以)。如果从外部类程序代码中初始化内部类, 此内部对象会绑在该外部对象上. 一个内部类的实例作为成员存在于所属外部类的实例中。 public class Outer { private int outVar; class Inner { public int inVar; void go() { outVar += inVar; } } Inner myInner = new Inner(); public void do() { myInner....

2016-12-25 · 1 min · Cong Chan

Java 04 | 类 class - 02 类与实例

Class 类的方法和变量细分为静态的和非静态的. 静态就是可以被类调用,所以静态方法/变量也称之为类方法/变量;非静态只能由实例调用,所以也称之为实例方法/变量。 静态变量 类变量 Class Variables 有static声明(静态变量). 静态变量一般是类本身固有的属性, 被该类所有实例共享。例如,我们可能需要用狗类的另一种生物学的统称“犬科”来作为类的说明, 这个时候可以用public static String binomen = "犬科";,这个变量理论上是由类来访问的。静态方法也类似. 以下代码定义了一个类来模拟狗,包含一个类变量作为这个类的说明,一个类方法用于发出叫声: public class Dog { public static String instruction = "狗类实例"; //类变量, 说明 public static void makeNoise() { System.out.println("汪!"); } } 这里没有定义main(), 在这种情况下如何直接运行这个类(java Dog), 程序是会报错的 错误: 在类 Dog 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args) 否则 JavaFX 应用程序类必须扩展javafx.application.Application. 你可以选择在里面添加一个main()方法. 但这次我们选择不定义具体的main(). 具体要如何运行, 我们可以另写一个类定义一个main()方法来调用这个类. public class DogLauncher { public static void main(String[] args) { Dog....

2016-12-24 · 2 min · Cong Chan

Java 04 | 类 class - 01 变量和方法

Class Java的语法是为了更容易地模拟真实世界而设计的. 比如用程序实现一只狗, 可以用定义一个类class来描述它. 类class里面包括变量Variable,方法method(可以理解为Python的函数function)。变量可以储存数据,方法可以处理数据。变量必须在类中声明(即不能离开类独立存在),不像Python或Matlab这样的语言可以在运行时添加新的变量。 构造对象的过程: 声明(declaration)引用变量: Dog smalldog; 创建对象:实例化 new Dog(20), 如果没有把它作为值赋给一个类声明变量, 那么这个实例化的值会被垃圾回收. 连接对象和引用:赋值对象给引用Dog smalldog = new Dog(5) 创建对象这一步,调用了Dog(), 不是普通的方法, 而是类的构造函数 Constructors. 构造函数 构造函数在初始化一个对象时执行, 构造函数与类名同名且没有返回类型, 而且可以带参数: /** 注意:构造函数与class类同名 但没有返回类型 */ public Dog(int w) { weight = w; } 然后在DogLauncher里实例化一只狗时, 直接Dog d = new Dog(20);即可. 在以上代码的基础上, 后续当我们想使用new和参数创建一只狗时,可以随时调用public Dog(int w)构造函数。对于熟悉Python的人来说,你可以理解java的构造函数为Python的__init__。 Java可以有与类同名的方法,只是要指明返回类型。 构造函数无法被继承 如果类有一个以上的构造函数,则参数一定要不一样,包括参数顺序和类型 构造函数链 执行new指令会启动构造函数的连锁反应(Constructor Chaining), 首先会执行其父类的构造函数, 依此类推连锁反应到Object类为止. 就算是抽象类, 也会有构造函数, 虽然不能被直接实例化, 但也会被唤醒. 理论上,每个类的构造函数需要先调用其父类的构造函数super(),依次入栈 public class Duck extends Animal { int size; public Duck(int newSize) { super(); // 调用父类构造函数, 且必须是在函数中的第一行 size = newSize; } } 如果明确写了super();, 则必须位于构造函数第一行....

2016-12-23 · 1 min · Cong Chan

Inf Course Note - Parallel Programming Language and Systems

爱丁堡大学信息学院课程笔记 Parallel Programming Language and Systems, Informatics, University of Edinburgh Reference: http://www.inf.ed.ac.uk/teaching/courses/ppls/ CMU 15213: Introduction to Computer Systems (ICS) Computer Systems: A Programmer’s Perspective A Comprehensive MPI Tutorial Resource A chapter on MPI from Ian Foster’s online Book Designing and Building Parallel Programs Introduction to parallel computer architecture Covering some of the nasty issues presented by the shared memory model, including weak consistency models and false sharing in the cache, and some architectural issues for the multicomputer model....

63 min · Cong Chan

Inf Course Note - Software Architecture, Process, and Management

爱丁堡大学信息学院课程笔记 Software Architecture, Process, and Management, Informatics, University of Edinburgh Reference: microsoft IBM Software Architecture in Practice (3rd edition), Bass, Clements, and Kazman What is Software Architecture? Software architecture is often described as the organization or structure of a system, where the system represents a collection of components that accomplish a specific function or set of functions. grouping components into areas of concern (layers): For example, the UI, business processing, and data access....

45 min · Cong Chan

Inf Course Note - Software Testing

爱丁堡大学信息学院课程笔记 Software Testing, Informatics, University of Edinburgh Reference: http://www.inf.ed.ac.uk/teaching/courses/st/2017-18/index.html Pezze and Young, Software Testing and Analysis: Process, Principles and Techniques, Wiley, 2007. Why Software Testing? 1, 软件的漏洞, 错误和失效 Software Faults, Errors & Failures The problem start with Faults, Fault(BUG): latent error, mistakes in programming. e.g add(x, y) = x * y. With the Faults in programs, if and only if executing add(x, y) = x * y, the fault being activated, and generate an Errors....

49 min · Cong Chan