课程大纲

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混合调用

public static Dog maxDog(Dog d1, Dog d2) {
	if (d1.weightInPounds > d2.weightInPounds) {
   		return d1;
	}
	return d2;
}

String[] args(命令行参数)

例如：

/**打印命令行参数的第零个*/
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

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(单向列表)

改进前

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

改进后

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);
    }
}

改进步骤

Methods		Non-Obvious Improvements
addFirst(int x)	#1	Rebranding: IntList → IntNode
getFirst	#2	Bureaucracy: SLList
size	#3	Access Control: public → private
addLast(int x)	#4	Nested Class: Bringing IntNode into SLList
	#5	Caching: Saving size as an int.
	#6	Generalizing: 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.

泛型使用的法则

类编写

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

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(二维数组)

声明

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}};;

练习

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.

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;
  }
}

public int removeLast() {
  int returnItem = items[size - 1];
  items[size - 1] = 0;
  size -= 1;  	
  return returnItem;
}

resizing

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的次数）

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.

泛型数组列表

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 方法

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.