YongSir

专业程序员伪装者

algs002-《算法》4th笔记

基本的数据结构及其实现

本节的主要问题是：如何用java来实现基础数据结构：背包,队列,栈？

定容栈

首先从一个只能存储String的简单的定容栈的设计开始：

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
public class FixedCapacityStackOfStrings {
 private String[] a;
 private int N;

 public FixedCapacityStackOfStrings(int cap) {
  a = new String[cap];
 }

 public boolean isEmpty() {
  return N == 0;
 }

 public int size() {
  return N;
 }

 public void push(String item) {
  a[N++] = item;
 }

 public String pop() {
  return a[--N];
 }

//测试
// 输入：to be or not to - be - - that - - - is
public static void main(String[] args) {

    FixedCapacityStackOfStrings s = new FixedCapacityStackOfStrings(100);

    while(!StdIn.isEmpty()) {
        String item = StdIn.readString();

        if(!item.equals("-")) s.push(item);
        else if(!s.isEmpty()) StdOut.print(s.pop() + " ");
    }

    StdOut.println(" ---- " + s.size() + "left on stack");
}

}

  • 合情合理的使用了数组，push就是N+1，pop就是–N

在测试中直接new了一个100的数组，很明显是欠妥的,如果压栈数超过100不够用，不到100又会太过浪费，所以开始进化为“可变容量的栈”

定容栈 -> 可变容栈

基本思路：在push时，如果超过Max则扩充；如果不到则缩减Max
但是java的数组并不支持直接的扩充和缩减，所以这里需要在节点时刻创建新的数组，这里创建一个新方法，然后对push和pop方法进行更改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 将 N <= max 的栈，移动到一个大小为max的数组
private void resize(int max) {
	String[] temp = (String[]) new Object[max];
	for (int i = 0; I < N; i++) {
		temp[i] = a[i];
	}
	a = temp;
}

// 如果栈满，栈就增加一倍
public void push(String item) {
	if(N == a.length) resize(2 * N);
	a[N++] = item;
}

// 如果弹栈之后，发现装的太少，不超过当前栈的1/4，栈缩小一倍
public String  pop() {
	String item = a[--N];
	a[N] = nil;
	if(N > 0 && N == a.length / 4) resize(a.length / 2);
	return item;
}

这样就实现了栈的大小总处在最合适的大小，完成了从定容到变容自适应的进化

String栈 -> T栈

已经得到了一个自适应的String栈，但利用java的范型就能将其变为万能栈，只需要将String变为

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
// 范型化
public class FixedCapacityStackOfStrings<Item> {
// private String[] a;
 private Item[] a;
 private int N;

 public FixedCapacityStackOfStrings(int cap) {
 // a = new String[cap];
   a = (Item[]) new Object[cap];
}

 public boolean isEmpty() {
  return N == 0;
 }

 public int size() {
  return N;
 }

 public void push(Item item) {
  a[N++] = item;
 }

 public Item pop() {
  return a[--N];
 }

//测试
// 输入：to be or not to - be - - that - - - is
public static void main(String[] args) {

   FixedCapacityStackOfStrings s = new FixedCapacityStackOfStrings(100);

    while(!StdIn.isEmpty()) {
        String item = StdIn.readString();

        if(!item.equals("-")) s.push(item);
        else if(!s.isEmpty()) StdOut.print(s.pop() + " ");
    }

    StdOut.println(" ---- " + s.size() + "left on stack");
}

}

这样就完成了T栈的进化

=====================================

补充一个栈的具体使用：如计算(2 * (2 + 4) - (2 ＋ 1) ／ 2)这样的计算，是如何按顺序得到想要的结果的？

其实，早在60年代的计算机发展之初就有前辈利用2个栈简单的解决了这个问题：一个栈用来存运算符号，一个栈用来放数值，根据)来区隔，没遇到一个),运算符栈弹出运算符，数值栈弹出数值计算得到结果，再将结果入栈，如此就完成了包含括号优先级的计算

链表

链表: 一种由node链接的数据结构，每个node含有一个范型的元素，和一个可指向另一节点的引用

回忆在上面处理可变容栈时，由于使用的数组容量不能随意变更，为此我们专门设计了一个resize()方法，而链表能够随意增删节点的特性就是专门解决这样的问题

1
2
3
4
private class Node {
	Item item;
	Node next;
}

对于链表的学习，最好的方式就是可视化表达，留意一些特殊节点并熟练以下操作：表头节点，表尾节点，插入节点，删除节点，遍历量表，再引申到双向链表，环行链表等等，这些是我们实现各种高级算法的基础，会逐渐都接触到

链表实现栈(Stack)

先让我们把上次设计的栈改为使用链表而不是数组来实现

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
publci class StackDemo {
	private int N;	    // 链表长度
	private Node first; // 头节点

	private class Node {
		Item item;
		Node next;
	}

	public boolean isEmpty() {
		return first == null; // 或者 N == 0;
	}

	public int size() { return N; }

	// 就是在头节点前添加一个node
	public void push(Item item) {
		Node oldFirst ＝ first;
		first = new Node();
		first.item = item;
		fisrt.next = oldFirst;
		N++;
	}

	// pop就是删除首节点
	public Item pop() {
		Item item = first.item;
		first = first.next;
		N--;
		return item;
	}

	// iterator() 留待
	// 测试main根原来相似
}

  • 使用链表能保证栈的大小根链表分配的大小一致，不存在浪费和不够的问题

  • 只使用first节点就足够了，栈只有一个IO口，对于链表来说操作first节点是最容易的

链表实现队列(Quene)

然后链表来实现队列(Queue)，是再合适不过了，入列就是添加last节点，出列就是first节点删除，size，isEmpty等等根栈中的一致，就不再写了

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
public class QueueDemo {
	private int N;
	private Node first; // first节点
	private Node last;  // last节点
	private class Node {
		Item item;
		Node next;
	}

	...
	// 入列就是向last后添加node
	public void enquene(Item item) {
		Node oldLast = last;
		last = new Node();
		last.item = item;
		last.next = null;

	// 如果源链表为空，那么first和last节点是同一个节点
		if(isEmptyy()) {
			first = last;
		} else {
			oldLast.next = last;
		}
		N++;
	}

	// 出队就是删除first节点
	public Item dequeue() {
		Item item = first.item;
		first = first.next;

		// 如果对空队列出队，就让链表为空
		if(isEmpty()) {
			last = null;
		}
		N--;
		return item;
	}

	// itetator() 留待
	...
}
  • 队列的实现需要first和last两个节点
  • 注意队列只有一个元素时，first ＝ last
  • 注意队列为空就是 last ＝ null

链表实现背包(Bag)

背包其实最简单的集合，它只支持添加和查找，不支持删除
其实现也很简单基本跟栈相同，只用一个first节点就足够了，所以重点不在它的add上，而在于对其中元素的查找

在java中，使用的就是迭代(Iterator),允许你使用foreach()语句来遍历集合，那迭代到底是如何实现的呢
？

首先需要实现Iterator接口：引入import java.util.Iterator并implement Iterator<Item> 实现其所有方法

具体代码如：

1
public class BagDemo