介绍
先来个Helloword
:
public class Helloworld { public static void main (String[] args) { System.out.println("Hello world" ); } }
Java 的特点:
所有代码都必须在类里面
语句组用大括号,语句末用分号
变量使用前先声明
变量类型是确定的,且不可变(静态语言)
注意public
,private
等
函数参数需要声明类型,返回值也是
所有 Java 中的函数都是方法
确定变量类型的优点:
缺点:
类 class 的使用
假如有这样一个类:
public class Dog { public int weight; public Dog (int startingweight) { weight = startingweight; } public static void makeNoise_static () { System.out.println("bark" ); } public void makeNoise_non_static () { if (weight < 10 ) System.out.println("bark" ); else System.out.println("woof" ); } }
使用如下:
public class Doglauncher { public static void main (String[] args) { Dog smallDog; new Dog (20 ); smallDog = new Dog (5 ); Dog hugeDog = new Dog (150 ); } }
static 静态
static 方法用类名调用,如 Dog.makeNoise_static()
non-static 方法用实例化名称调用,如 smalldog.makeNoise_static()
static 方法不能访问实例化变量,如 makeNoise_non_static
中不能使用变量 weight
为什么要使用 static 方法?
对于Math
类来说,往往不需要实例化,如使用 x=Math.round(5.6)
比 Math m = new Math(); x = m.round(x);
更自然
可以同时拥有 static method 和 non-static method:
public static Dog maxDog (Dog d1, Dog d2) { if (d1.weight > d2.weight) { return d1; } return d2; }public Dog maxDog (Dog d2) { if (weight > d2.weight) { return this ; } return d2; }
静态变量:public static String name = "dog";
测试 Test
可以使用junit
:
public class Test { public static String stringMax (String a, String b) { if (a.compareTo(b) < 0 ) return b; return a; } public static void testStringMax () { String[] input = { "a" , "b" }; String expected = "a" ; String actual = stringMax(input[0 ], input[1 ]); org.junit.Assert.assertEquals(expected, actual); } public static void main (String[] args) { testStringMax(); } }
引用 Reference
public static void main (String[] args) { Dog a = new Dog (5 ); Dog b = a; b.weight = 10 ; System.out.println(a.weight); System.out.println(b.weight); }
输出均为 10,表示 b
只是 a
的一个引用,并不是复制了一份
SLList 单链表、嵌套类、哨兵 Sentinel 节点
public class SLList { private IntNode sentinel; private int size; private static class IntNode { int item; IntNode next; IntNode(int i, IntNode n) { item = i; next = n; } } public SLList () { sentinel = new IntNode (-1 , null ); size = 0 ; } public SLList (int x) { sentinel = new IntNode (-1 , null ); sentinel.next = new IntNode (x, null ); size = 1 ; } public void addFirst (int x) { sentinel.next = new IntNode (x, sentinel.next); size += 1 ; } public int getFirst () { return sentinel.next.item; } public void addLast (int x) { IntNode p = sentinel; while (p.next != null ) { p = p.next; } p.next = new IntNode (x, null ); size += 1 ; } public int size () { return size; } }
其中的不变量 invariants 有:
sentinel 总是指向一个 sentinel 节点
第一个节点永远是 sentinel
size 变量永远是元素总数
DLLists 双向链表、Array 数组、Generic 泛型
双向链表 DLLists
解决特殊情况的方法:
在链表末端也加入一个哨兵;
使用循环链表
泛型 Generic
在类名称后面添加 <Type_name>
,在把相应的类型名改为 Type_name
,但注意在声明时要指定类型名,如 SLList<String> L = new SLList<String>("hello");
声明或实例化时,使用引用类型:
int
→Integer
、double
→Double
、char
→Character
、boolean
→Boolean
、long
→Long
数组 Array
有以下几种实例化方法:
x = new int[3];
y = new int[]{1,2,3,4,5};
int []z = {7,8,9};
和类一样,x=y
表示 x
更改为 y
的引用,数组复制为:
System.arraycopy(b, 0, x, 3, 2)
从 b[0]
开始复制 2 个元素到 x[3]
及其后面
多维数组:int[][] matrix = new int[4][4];
AList
Alist
是用数组重设大小实现的快速访问其中某个元素的动态数组
public class AList <Item_type> { private Item_type[] items; private int size; public AList () { size = 0 ; items = (Item_type[]) new Object [100 ]; } private void resize (int capacity) { Item_type[] a = (Item_type[]) new Object [capacity]; System.arraycopy(items, 0 , a, 0 , size); items = a; } public void addLast (Item_type x) { if (size == items.length) resize(size * 2 ); items[size] = x; size += 1 ; } public Item_type removeLast () { Item_type x = getLast(); size -= 1 ; return x; } public Item_type deleteLast () { Item_type returnItem = getLast(); items[size - 1 ] = null ; size -= 1 ; return returnItem; } public Item_type getLast () { return items[size - 1 ]; } public Item_type get (int i) { return items[i]; } public int size () { return size; } }
继承 Inheritance
签名 signature 指函数名和参数等
覆盖 overriding 是说子类和父类有一样签名的方法
重载 overloading 是说有相同名字但不同签名的方法
public interface Animal { public void makenoise () ; }public class Pig implements Animal { @Override public void makenoise () { System.out.println("onik" ); } public void makenoise (Pig a) { System.out.println("oniks" ); } }
接口继承 Interface Inheritance 和 实现继承 Implement Inheritance
public interface List <Item_type> { public void addLast (Item_type x) ; public int size () ; public Item_type getFirst () ; public Item_type get (int i) ; default public void print () { for (int i = 0 ; i < size(); i++) { System.out.print(get(i) + " " ); } System.out.println(); } public static void main (String[] args) { List<Integer> L1 = new SLList <Integer>(); L1.addLast(10 ); L1.addLast(11 ); L1.addLast(12 ); L1.print(); List<Integer> L2 = new AList <Integer>(); L2.addLast(10 ); L2.addLast(11 ); L2.addLast(12 ); L2.print(); } }public class SLList <Item_type> implements List <Item_type> { @Override public void print () { IntNode p = sentinel.next; while (p != null ) { System.out.print(p.item + " " ); p = p.next; } System.out.println(); } }
实现继承破坏了封装 Encapsulation
静态类型 Static Type 和动态类型 Dynamic Type
静态类型 Static Type :变量声明时的类型,永不改变;
动态类型 Dynamic Type :运行时的类型,由实例化时和=
赋值时决定
代码在编译时使用静态类型,在运行时使用动态类型
public interface Animal { default void greet (Animal a) { print("hello animal" ); } default void sniff (Animal a) { print("sniff animal" ); } default void praise (Animal a) { print("cool animal" ); } }public class Dog implements Animal { @Override void sniff (Animal a) { print("dog sniff animal" ); } void praise (Dog a) { print("cool dog" ); } }
Animal a = new Dog();
Dog d = new Dog();
代码
编译的接口
运行
a.greet(d);
greet(Animal a)
"hello animal"
a.sniff(d);
sniff(Animal a)
"dog sniff animal"
d.praise(d);
praise(Dog a)
"cool dog"
a.praise(d);
praise(Animal a)
"cool animal"
Java 中已经有了list
,ArrayList
、LinkedList
等都是其一种实现形式
java.util.List<Integer> L = new java .util.ArrayList<>(); L.add(5 ); L.add(6 ); L.add(7 ); System.out.print(L);
延伸 Extend
public class RotatingSLList <Item_type> extends SLList <Item_type> { public void rotate () { Item_type oldBack = removeLast(); addFirst(oldBack); } public static void main (String[] args) { RotatingSLList<Integer> L = new RotatingSLList <>(); L.addLast(10 ); L.addLast(11 ); L.addLast(12 ); L.rotate(); L.print(); } }
其中RotatingSLList
拥有父类SLList
的所有成员,并增加了rotate
public class VengefulSLList <Item_type> extends SLList <Item_type> { private SLList<Item_type> deletedItems; public VengefulSLList () { deletedItems = new SLList <Item_type>(); } @Override public Item_type removeLast () { Item_type oldBack = super .removeLast(); deletedItems.addLast(oldBack); return oldBack; } }
Java 中每一个类型都是 Object 的子孙 descendant ,都有equal()
、toString()
等成员函数
高阶函数 Higher Order Function
可以使用一个类来实现:
public interface IntUnaryFunction { int apply (int x) ; }public class TenX implements IntUnaryFunction { public int apply (int x) { return 10 * x; } }public class HigherOrderFunction { public static int do_twice (IntUnaryFunction f, int x) { return f.apply(f.apply(x)); } public static void main (String[] args) { IntUnaryFunction tenX = new TenX (); System.out.print(do_twice(tenX, 2 )); } }
显性实现:
def print_larger (x, y, compare, stringify ): if compare(x, y): return stringify(x) return stringify(y)
子类型多态 Subtype Polymorphism 实现:
def print_larger (x, y ): if x.largerThan(x): return x.str () return y.str ()
类似的,在 Java 中,使用一个接口类来实现:
public interface Comparable <T> { public int compareTo (T obj) ; }public class Dog implements Comparable <Dog> { private String name; public int size; public Dog (String n, int s) { name = n; size = s; } public int compareTo (Dog other) { return size - other.size; } }public class Maximizer { public static Comparable max (Comparable[] items) { int maxDex = 0 ; for (int i = 0 ; i < items.length; i += 1 ) if (items[i].compareTo(items[maxDex]) > 0 ) maxDex = i; return items[maxDex]; } }public class DogLauncher { public static void main (String[] args) { Dog d1 = new Dog ("aaa" , 16 ); Dog d2 = new Dog ("ezsu" , 19 ); Dog d3 = new Dog ("iu" , 6 ); Dog[] dogs = new Dog [] { d1, d2, d3 }; Dog d = (Dog) Maximizer.max(dogs); System.out.println(d.size); } }
也可以使用内置的Comparator
:
import java.util.Comparator;public class Dog { public String name; private int size; public Dog (String n, int s) { name = n; size = s; } public int compareTo (Dog other) { return size - other.size; } private static class NameComparator implements Comparator <Dog> { public int compare (Dog a, Dog b) { return a.name.compareTo(b.name); } } public static Comparator<Dog> getNameComparator () { return new NameComparator (); } }public class DogLauncher { public static void main (String[] args) { Dog d1 = new Dog ("aaa" , 16 ); Dog d2 = new Dog ("ezsu" , 19 ); Comparator<Dog> nc = Dog.getNameComparator(); if (nc.compare(d1, d2) > 0 ) System.out.println(d1.name); else System.out.println(d2.name); } }
异常 Exceptions、迭代器 Iterators 和 特殊对象方法
Set<Integer> javaset = new HashSet <>(); javaset.add(256 ); javaset.add(42 ); javaset.add(378 );for (int i : javaset) System.out.println(i); Iterator<Integer> seer = javaset.iterator();while (seer.hasNext()) System.out.println(seer.next());
import java.util.Iterator;public class ArraySet <T> implements Iterable <T> { private T[] items; private int size; public ArraySet () { items = (T[]) new Object [100 ]; size = 0 ; } public static <T> ArraySet<T> of (T... stuff) { ArraySet<T> returnSet = new ArraySet <>(); for (T x : stuff) returnSet.add(x); return returnSet; } public boolean contains (T x) { for (int i = 0 ; i < size; i += 1 ) if (x.equals(items[i])) return true ; return false ; } public void add (T x) { if (x == null ) { throw new IllegalArgumentException ("无法添加null到ArraySet中" ); } if (contains(x)) return ; items[size] = x; size += 1 ; } public int size () { return size; } private class ArraySetIterator implements Iterator <T> { private int wizPos; public ArraySetIterator () { wizPos = 0 ; } public boolean hasNext () { return wizPos < size; } public T next () { T returnItem = items[wizPos]; wizPos += 1 ; return returnItem; } } public Iterator<T> iterator () { return new ArraySetIterator (); } @Override public String toString () { StringBuilder returnString = new StringBuilder ("{" ); for (int i = 0 ; i < size - 1 ; i += 1 ) { returnString.append(items[i].toString()); returnString.append(", " ); } returnString.append(items[size - 1 ].toString()); returnString.append("}" ); return returnString.toString(); } @Override public boolean equals (Object other) { if (other == null ) return false ; if (this == other) return true ; if (other.getClass() != getClass()) return false ; ArraySet<T> o = (ArraySet<T>) other; if (o.size != size) return false ; for (T item : this ) if (!o.contains(item)) return false ; return true ; } public static void main (String[] args) { ArraySet<Integer> s = new ArraySet <>(); s.add(256 ); s.add(42 ); s.add(378 ); ArraySet<Integer> s2 = ArraySet.of(378 , 42 , 256 ); s2.add(256 ); s2.add(42 ); s2.add(378 ); for (int i : s) System.out.println(i); System.out.println(s); System.out.println(s.equals(1 )); System.out.println(s.equals(s2)); } }
Project 2: Gitlet
这是我写过的最长的代码,总共 1153 行;这也是我看过的最长的英语文档,光是说明就有 14181 个词;这也是我收获最大的项目,在 CS61A 中,我所做的工作不过是在已经基本完成的项目代码上添加一些东西,而且这些东西的具体实现方法都已经有了详细的说明,那时,我就一直想知道自己什么时候才能独立完成像那样的项目,而在 CS61B 的这个 project 中,我做到了。
从对整个问题的一脸茫然,到摸索其中的基本原理,再到写设计文档时的混乱思绪,再到写代码时一行行地改进、一遍遍地调试,再到反复阅读要求考虑特殊情况和算法效率,最后完成对代码的优化。这一个 project 带给我的好处远远不止于此。
先附上成就感满满的满分截图:
![满分!][1]
类与数据结构
Main
程序的切入点,接收命令行的参数并相应地调用 Repository
中的函数,并检查参数是否能正确调用函数,该类仅仅起到检查参数并调用对应函数的效果
Repository
程序的主要部分,实现了命令行要求的功能、维护持久化、添加错误信息等
该类将所有对文件的具体逻辑阻隔到 Blob
中
public static final File CWD = new File(System.getProperty("user.dir"));
当前工作目录,对于其它的文件对象很有用
public static final File GITLET_DIR = join(CWD, ".gitlet");
隐藏的 .gitlet
目录,当前所有对文件的维护都是在此目录中进行的
public static final File LOCAL_GITLET_DIR = join(CWD, ".gitlet");
与前面的类似,但是在处理远程操作时,需要使用这个作为本地的工作目录
private static final Stage STAGE = new Stage();
暂存区的实例,用于维护其中的文件
这些域都是静态的,因为我不需要实例化 Repository
类,该类仅仅适用于存放函数
Blob
该类代表储存在文件中的每个 blob,因为每个 blob 都有一个独特的 sha1,就使用它来当作对象序列化的文件名称
static final File BLOBS_FOLDER = join(Repository.GITLET_DIR, "blobs");
序列化后的 blob 储存的位置,因为所有 blob 都存在同一个地方,所以是static
的
private final byte[] contents
blob 储存的内容
private final String blobId
blob 的 id,这些 id 是独特的
Commit
此类代表储存在文件中的每个 commit 信息,因为每个 commit 都有一个独特的 sha1,用其当作序列化的文件名称
static final File COMMIT_FOLDER = join(Repository.GITLET_DIR, "commits");
序列化后的 commit 储存的位置,因为所有 commit 都存在同一个地方,所以是static
的
private final String message
commit 信息
private final Date timestamp
commit 的时间
private final String commitId
commit 的 id,这些 id 是独特的
private final String firstParentId
commit 的第一个父亲的 id
private final String secondParentId
commit 第二个父亲的 id,只有 merge 后的 commit 有
private HashMap<String, String> blobs
commit 中储存的 blob 名字映射到 blobId,便于查找文件名对应的文件
Stage
用于维护 add
和 rm
等操作的暂存区
protected TreeMap<String, String> stagedFiles;
暂存的文件列表
protected TreeSet<String> removedFiles;
被移除的文件的文件名
public static final File STAGING_AREA = join(GITLET_DIR, "staging area");
暂存文件所在文件夹
public static final File STAGE_FILE = join(GITLET_DIR, "stage");
存放暂存文件信息的文件路径
Branch
维护对分支的添加、删除和持久化的类
protected static File HEADS_FOLDER = join(GITLET_DIR, "heads");
存放各 branch 的 HEADs 的文件夹
protected static File CURRENT_BRANCH = join(GITLET_DIR, "current branch");
存放当前 branch 名称的文件
这些域都是静态的,因为我不需要实例化 Branch
类,该类仅仅适用于存放函数
Remote
维护对远程仓库的添加、删除和持久化的类
public static final File REMOTE_FOLDER = join(LOCAL_GITLET_DIR, "remote");
存放远程 gitlet 路径的文件夹
这些域都是静态的,因为我不需要实例化 Remote
类,该类仅仅适用于存放函数
Utils
题目提供的类,包含了有用的序列化操作
static final int UID_LENGTH = 40
SHA-1 的 16 进制长度,用于检查是否合法
GitletException
通用化 gitlet 中的错误
算法
![merge操作的几种情况汇总][2]
merge
操作是公认的最为困难的操作了,情况非常复杂,分成几个部分
在查找 splitPoint
时,通过维护两个 commit 的所有祖先节点信息(包括 commitId 和同该 commit 的距离),搜索两者的祖先中共同的祖先,且其与两者的距离之和最小,则该祖先为最近公共祖先,即 splitPoint
,此算法满足时间复杂度要求
持久化
目录结构如下:
.gitlet <==== 所有持久化数据都存储在此
blobs <==== 所有的 blob 都存在这个目录
blobId1 <==== 每个单独的 blob 实例
blobId2
...
blobIdN
commits <==== 所有的 commit 都存在这个目录
commitId1 <==== 每个单独的 commit 实例
commitId2
...
commitIdN
heads <==== 所有的头指针都存在这个目录
master <==== 每个分支的 head 实例
staging area <==== 所有 add 操作添加还没有 commit 的 blob 都暂存在这个目录
blobId1 <==== 每个单独的 blob 实例
blobId2
...
blobIdN
remote <==== 所有的远程仓库的位置都记录在这个目录
init
Repository
类将会创建这些文件夹:.gitlet
、.commits
、.blobs
、heads
、remote
Commit
类将会创建第一个节点并序列化写入到名称为 commitId 的文件中
Branch
创建主分支文件,并将第一个 commit 的 commitId 写入到该文件中
创建当前分支文件,并将主分支名称写入到该分支文件中
add [file name]
如果该文件和当前 commit 中的文件相同:
若 staging area
中没有该文件,无事发生
若 staging area
中有该文件,删除该文件
若不同,则添加该文件到 staging area
中
commit [message]
将 staging area
中的文件移动到 blobs
中
创建一个新的 commit
将 commitId 写入到当前分支的文件中
rm [file name]
如果 staging area
中有该文件,则移除该文件
如果该文件存在于当前目录中,则删除该文件
checkout -- [file name]
和 checkout [commit id] -- [file name]
从 commit 处获取文件的 blob,并将该 blob 中的内容复制到指定文件中
checkout [branch name]
类似,但是恢复 commit 中的所有文件
branch [branch name]
Branch
类中创建该分支文件
将当前 commit 的 commitId 写入到该文件中
rm-branch [branch name]
Branch
类中删除该分支文件
reset [commit id]
类似于 checkout [branch name]
的操作,但多了一步向当前分支的文件中写入 commitId
merge [branch name]
情况很复杂,不再赘述
add-remote [remote name] [name of remote directory]/.gitlet
Remote
类创建 remote name 的文件,并将目录写入其中
rm-remote [remote name]
Remote
类删除 remote name 的文件
push [remote name] [remote branch name]
将本地 gitlet 的所有 commit 文件都复制到远程仓库所在目录中
向远程仓库的当前分支的文件中写入最新的 commitId
fetch [remote name] [remote branch name]
将远程 gitlet 的所有 commit 和 blob 文件都复制到本地仓库
新建名称为 [remote name]-[remote branch name]
的分支文件
向该文件中写入远程仓库的最新的 commitId
pull [remote name] [remote branch name]
同 fetch
+ merge
操作
[1]: /illustration/UCB CS61B:数据结构与算法/gitlet autograder.webp
[2]: /illustration/UCB CS61B:数据结构与算法/merge.webp