课程大纲

Phase 1: Programming Intensive Introduction to Java.

Weeks 1-4.
One browser-based programming HW (this HW0 is optional).
Three labs to introduce you to various tools (starting this week).
Two projects (proj0 and proj1).

Phase 2: Advanced Programming

Weeks 5-7.
One small HW (HW1).
One large project, due ~3/5.
New: You design your own explorable world (within some constraints).
Labs to support large project.

Phase 3: Data Structures and Algorithms

Weeks 8-14
Incredibly important and foundational material: Expect an CS job interview to lean heavily on this part of the course.
Labs: Implement a data structure or algorithm.
Each lab ends with a TA led discussion of best implementation.
Six HWs: Apply a data structure or algorithm toward a real world problem.
Two released during RRR week. Can be used to makeup missed homeworks earlier, or for practice.
One very challenging data structure/algorithms project (but not as big as project 2).

See calendar at http://datastructur.es for more.

static 和 non-static

静态和实例方法:

静态方法只能使用静态变量,同时可以直接通过类名来调动(不推荐通过对象)
实例方法可以调动实例变量,同时只能通过对象来调动

静态和实例变量:

静态变量为所有该类的对象共用,实例变量不会互相影响

static 和 non-static混合调用

1
2
3
4
5
6
public static Dog maxDog(Dog d1, Dog d2) {
if (d1.weightInPounds > d2.weightInPounds) {
return d1;
}
return d2;
}

String[] args(命令行参数)

例如:

1
2
3
4
5
6
/**打印命令行参数的第零个*/
public class ArgsDemo {
public static void main(String[] args) {
System.out.println(args[0]);
}
}

命令行:
其中java ArgsDemo是用于运行已编译好的class文件,后面的内容是命令行参数,以空格分隔。第零个是these。

1
2
$ java ArgsDemo these are command line arguments
these

Library

Library Documentation Example

aZdYsP.png

Declaring a Variable

声明一个int变量,生成32位的box
声明一个double变量,生成64位的box

Types

There are 8 primitive types in Java:
byte, short, int, long, float, double, boolean, char

Everything else, including arrays, is a reference type.
当声明一个reference type变量
These bits can be either set to:

  • Null (all zeros).
  • The 64 bit “address” of a specific instance of that class (returned by new).

The golden rule:
b = a copies the bits from a into b.
Passing parameters copies the bits.

Declaration and Instantiation of Arrays

int[] x = new int[]{0, 1, 2, 95, 4};

SLList(单向列表)

改进前

1
2
3
4
5
6
7
8
public class IntList {
public int first;
public IntList rest;

public IntList(int f, IntList r) {
first = f;
rest = r;
}

改进后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class SLList {
public static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}

private IntNode sentinel;
private int size;

public SLList() {
sentinel = new (63, null)
size = 0;
}

public SLList(int x) {
sentinel = new IntNode(63, 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 int size() {
return size;
}

public void addLast(int x) {
size += 1;
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}



改进步骤

MethodsNon-Obvious Improvements
addFirst(int x)#1Rebranding: IntList → IntNode
getFirst#2Bureaucracy: SLList
size#3Access Control: public → private
addLast(int x)#4Nested Class: Bringing IntNode into SLList
#5Caching: Saving size as an int.
#6Generalizing: Adding a sentinel node to allow representation of the empty list.

第六步-哨兵节点

使SLList有一个哨兵节点,而哨兵节点可以指向null或者第一个节点

作用

防止当列表为空时,无法用first.method()调用方法

缺陷

Inserting at the back of an SLList is much slower than the front.

DLList(双向列表)

改进一

增加last,指向最后一个节点

缺陷

对于倒数第二个节点来说还要重新遍历一遍

改进二

使所有节点变成双向的

改进三

方案一

增加一个指向last哨兵节点在开始时和指向first的哨兵节点互相指向
原因:last参数可能指向将要指向first的哨兵节点

方案二

使最后一个节点重新指向将要指向first节点的哨兵节点

Generic Lists (加入泛型)

ALList和DLList的缺陷

One issue with our list classes: They only supports integers.

泛型使用的法则

类编写

类名之后使用<>指定一次通用类型名

1
2
3
4
5
6
7
8
9
10
11
12
public class DLList<T> {
private IntNode sentinel;
private int size;

public class IntNode {
public IntNode prev;
public T item;
public IntNode next;
...
}
...
}

声明时使用

在声明时在<>中指定一次特定的所需类型,并在实例化时使用空的<>

1
2
DLList<String> d2 = new DLList<>("hello");
d2.addLast("world");

实例化一个普通的基本类型

使用Integer,Double,Character,Boolean,Long,Short,Byte,或Float。

Arrays

Three valid notations:
x = new int[3];
y = new int[]{1, 2, 3, 4, 5};
int[] z = {9, 10, 11, 12, 13};

Two ways to copy arrays

  • Item by item using a loop.
  • Using System.arraycopy(b, 0, x, 3, 2) Takes 5 parameters:
    • Source array
    • Start position in source
    • Target array
    • Start position in target
    • Number to copy

2D arrays(二维数组)

声明

1
2
3
4
int[][] x = new int[3][];
\\这将为x创建一个64bits的内存盒用于存储地址,和三个64bits的内存盒用于存储指向下一层数组(长度未确定)的地址。
int[][] y = new int [][]{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}};;
int[][] z = {{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}};;

练习

1
2
3
4
5
6
7
8
9
int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];

pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];

总结

int[][] x = new int[n][];
声明一个叫x的数组,数组的size为n,每个位置可以指向一个int数组

注意

数组中所存贮的数据类型必须一致

Naive Array Lists(数组列表)

使用数组列表需要注意的事项

  • he position of the next item to be inserted is always size.
  • size is always the number of items in the AList.
  • The last item in the list is always in position size - 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class AList {
private int[] items;
private int size;

public AList() {
items = new int[100]; size = 0;
}

public void addLast(int x) {
items[size] = x;
size += 1;
}

public int getLast() {
return items[size - 1];
}

public int get(int i) {
return items[i];
}

public int size() {
return size;
}
}
1
2
3
4
5
6
7
public int removeLast() {
int returnItem = items[size - 1];
items[size - 1] = 0;
size -= 1;
return returnItem;
}

resizing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}

public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}

改进使得节省内存(减少resize的次数)

1
2
3
4
5
6
7
public void addLast(int x) {
if (size == items.length) {
resize(size * RFACTOR);
}
items[size] = x;
size += 1;
}

改进-优化内存

  • Define the “usage ratio” R = size / items.length;
  • Typical solution: Half array size when R < 0.25.

泛型数组列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class AList<Glorp> {
private Glorp[] items;
private int size;

public AList() {
items = (Glorp []) new Object[8];
size = 0;
}

private void resize(int cap) {
Glorp[] a = (Glorp []) new Object[cap];
System.arraycopy(items, 0,
a, 0, size);
items = a;
}

public Glorp get(int i) {
return items[i];
}
...

deleteback 方法

1
2
3
4
5
6
public Glorp deleteBack() {
Glorp returnItem = getBack();
items[size - 1] = null;
size -= 1;
return returnItem;
}

注意:
Java only destroys unwanted objects when the last reference has been lost.

  • 新名词:loiter
    • Keeping references to unneeded objects is sometimes called loitering.
    • Save memory. Don’t loiter.