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.Iteratorimplement Iterator<Item> 实现其所有方法

具体代码如:

1
public class BagDemo