5、链表
在第二章中，我们可以看到数组作为数据存储结构有一定缺陷。在无序数组中，搜索效率是低效的；而在有序数组中，插入效率又很低；不管在哪一种数组中删除效率都很低。况且一个数组创建后，它的大小是不可以改变的。
在本章中，我们将看到新的一种数据存储结构，它可以解决上面的问题。这种数据存储结构就是链表。链表可能是继数组之后第二种使用最广泛的通用存储结构。
链表机制灵活，用途广泛，它适用于的数据库。它也可以取代数组，作为其他存储结构的基础，例如栈、队列。除非需要频繁的通过下标访问各个数据，否则在很多使用数组的地方都可以使用链表来代替。
链表虽不能解决数据存储的所有问题，但是它确实用途广泛，在概念上也比其他的常用结构（例如树）简单。随着问题的深入，我们将探讨链表的优点和缺点。
在本章中我们将学习单链表、双端链表、有序链表、双向链表和有迭代器的链表（迭代器是用来随机访问链表元素的一种方法）。还会实践一下抽象数据类型（ADT）的思想：如果用ADT描述栈和队列，以及如果使用链表代替数组来实现栈和队列。
5.1 链节点
public class Link {
public int iData;
public double dData;
public Link next;
}
引用和基本类型
在Link的类定义中定义一个Link类型的域，这看起来很奇怪。编译器怎样才能不混淆呢？编译器在不知道一个Link对象占用多大空间的情况下，如何能知道一个包含了相同对象的Link对象占用多大空间呢？
在Java语言中，这个问题的答案是Link对象并没还有真正包含另一个Link对象，尽管看起来好像包含了。类型为Link的next字段仅仅是对另外的一个Link对象的"引用"，而不是一个对象。
一个引用是一个对某个对象的参照数值，它是一个计算机内存中的对象地址，然后不需要知道对象的具体值；只要把它当成一个奇妙的数，它会告诉你对象在哪里。在给定的计算机/操作系统中，所有的引用，不管它指向谁，大小都是一样的。因此，对编译器来说，知道这个字段的大小并由此构造出整个Link对象，是没有任何问题的。
注意，在Java语言中，例如int和double等简单类型的存储与对象的存储是完全不同的。含有简单类型的字段不是引用，而是实实在在的数值。
5.2 LinkList专题Applet
略
5.3 单链表
Link类
public class Link {
public int iData;
public double dData;
public Link next;
public Link(int id, double dd) {
iData = id;
dData = dd;
}
public void displayLink() {
System.out.print("{" + iData + ", " + dData + "}");
}
}
LinkList类
public class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
}
insertFirst()方法
public void insertFirst(int id, double dd) {
Link newLink = new Link(id ,dd);
newLink.next = first;
first = newLink;
}
deleteFirst()方法
public Link deleteFirst() {
Link temp = first;
first = first.next;
return temp;
}
在C++和类似的语言中，在从链表中取下一个链节点后，需要考虑如何删除这个链节点。它仍然在某个地方，但是现在没有任何东西指向它，将如何处理它呢？在Java语言中，垃圾收集进程将在未来的某个时刻销毁它，现在这个不是程序员操心的工作。
注意，deleteFirst()方法假定链表是不为空的。调用它之前，程序应该首先调用isEmpty()方法核实这一点。
displayList()方法
public void displayList() {
System.out.print("List (first-->last):");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
LinkList代码清单
public class Link {
public int iData;
public double dData;
public Link next;
public Link(int id, double dd) {
iData = id;
dData = dd;
}
public void displayLink() {
System.out.print("{" + iData + ", " + dData + "}");
}
}
public class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int id, double dd) {
Link newLink = new Link(id ,dd);
newLink.next = first;
first = newLink;
}
public Link deleteFirst() {
Link temp = first;
first = first.next;
return temp;
}
public void displayList() {
System.out.print("List (first-->last):");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
}
public class LinkListApp {
public static void main(String[] args) {
LinkList theList = new LinkList();
theList.insertFirst(22, 2.99);
theList.insertFirst(44, 4.99);
theList.insertFirst(66, 6.99);
theList.insertFirst(88, 8.99);
theList.displayList();
while (!theList.isEmpty()) {
Link alink = theList.deleteFirst();
System.out.print("Deleted ");
alink.displayLink();
System.out.println("");
}
theList.displayList();
}
}
运行结果：
List (first-->last):{88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}
Deleted {88, 8.99}
Deleted {66, 6.99}
Deleted {44, 4.99}
Deleted {22, 2.99}
List (first-->last):
Process finished with exit code 0
5.4 查找和删除指定的链节点
下一个示例程序增加了两个方法，一个是在链表中查找包含关键字的链节点，另一个是删除包含关键字的链节点。
LinkList2代码清单
public class Link {
public int iData;
public double dData;
public Link next;
public Link(int id, double dd) {
iData = id;
dData = dd;
}
public void displayLink() {
System.out.print("{" + iData + ", " + dData + "} ");
}
}
public class LinkList2 {
private Link first;
public LinkList2() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int id, double dd) {
Link newLink = new Link(id ,dd);
newLink.next = first;
first = newLink;
}
public Link deleteFirst() {
Link temp = first;
first = first.next;
return temp;
}
public void displayList() {
System.out.print("List (first-->last):");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
public Link find(int key) {
Link current = first;
while (current.iData != key) {
if (current.next == null) {
return null;
} else {
current = current.next;
}
}
return current;
}
public Link delete(int key) {
Link current = first;
Link previous = first;
while (current.iData != key) {
if (current.next == null) {
return null;
} else {
previous = current;
current = current.next;
}
}
if (current == first) {
first = first.next;
} else {
previous.next = current.next;
}
return current;
}
}
public class LinkList2App {
public static void main(String[] args) {
LinkList2 theList = new LinkList2();
theList.insertFirst(22, 2.99);
theList.insertFirst(44, 4.99);
theList.insertFirst(66, 6.99);
theList.insertFirst(88, 8.99);
theList.displayList();
Link f = theList.find(44);
if (f != null) {
System.out.println("Found link with key " + f.iData);
} else {
System.out.println("Can't found link");
}
Link d = theList.delete(66);
if (d != null) {
System.out.println("Deleted link with key " + d.iData);
} else {
System.out.println("Can't delete link");
}
theList.displayList();
}
}
运行结果：
List (first-->last):{88, 8.99} {66, 6.99} {44, 4.99} {22, 2.99}
Found link with key 44
Deleted link with key 66
List (first-->last):{88, 8.99} {44, 4.99} {22, 2.99}
Process finished with exit code 0
5.5 双端链表
双端链表和传统的链表非常相似，但是它有一个新增的特性：即对最后一个链节点的引用，就像对第一个链节点的引用一样。图5.9显示了这么一个链表。
对最后一个链节点允许像表头一样，在表尾直接插入一个链节点。当然，仍然可以在单链表的表尾插入一个链节点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。
像访问表头一样访问表尾的特性，使双端链表更适合于一些普通的链表不方便操作的场合，队列的实现就是这么一个情况；在下一节将看到这个机制如何运作。
双端链表FirstLastList代码清单
public class Link {
public long dData;
public Link next;
public Link(long d) {
dData = d;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class FirstLastList {
private Link first;
private Link last;
public FirstLastList() {
first = null;
last = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
last = newLink;
}
newLink.next = first;
first = newLink;
}
public void insertLast(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
first = newLink;
} else {
last.next = newLink;
}
last = newLink;
}
public long deleteFirst() {
long temp = first.dData;
if (first.next == null) {
last = null;
}
first = first.next;
return temp;
}
public void displayList() {
System.out.print("List (first-->last): ");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
public class FirstLastApp {
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
theList.displayList();
theList.deleteFirst();
theList.deleteFirst();
theList.displayList();
}
}
运行结果：
List (first-->last): 66 44 22 11 33 55
List (first-->last): 22 11 33 55
Process finished with exit code 0
注意在表头的重复插入操作会颠倒链节点进入的顺序，而在表尾的重复插入则保持链节点进入的顺序。
这个类有一个新的方法insertLast()，这个方法在表尾插入一个新的链节点。这个过程需要首先改变last.next，使其指向新生成的链节点，然后改变last，使其指向新的链节点，如图5.10所示。
不幸的是，用双端链表也不能有助于解决删除最后一个链节点，因为没有一个引用指向倒数第二个链节点。如果最后一个链节点被删除，倒数第二个链节点的next字段应该变成null值。为了方便删除最后一个链节点，需要一个双向链表，马上将会讨论到它。（当然，可以遍历整个链表找到最后一个链节点，但是那样的效率不是很高。）
5.6 链表的效率
在表头的插入很删除都很快。进需要改变一两个引用的值，所以花费是O(1)的时间。
平均起来，查找、删除和在指定链节点后面插入都需要搜索链表中一半链节点。需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链节点时，链表不需要移动任何东西。增加的效率是很显著的，特别是当复制的时间远远大于比较时间的时候。
当然，链表比数组优越的另外一个重要方面是链表需要多少内存就可以使用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。向量是一种可扩展的数组，它可以通过可变长度解决这个问题，但是它只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量）。这个解决方法在内存使用效率上来说还是要比链表低。
5.7 抽象数据类型
在本节，将会转换角度，讨论一个比链表更加广泛的话题：抽象数据类型(ADT)。什么是ADT?简单来说，它是一种考虑数据结构的方式：着重在于它做了什么，而忽略它是怎么做的。
栈和队列都是ADT的例子。前面已经看到栈和队列都可以用数组来实现。在继续ADT的讨论之前，先看一下如何用链表实现栈和队列。这个讨论将展示栈和队列的"抽象"特性：即如何脱离具体的实现来考虑栈和队列。
用链表实现的栈
public class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
newLink.next = first;
first = newLink;
}
public long deleteFirst() {
long temp = first.dData;
first = first.next;
return temp;
}
public void displayList() {
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
public class LinkStack {
private LinkList theList;
public LinkStack() {
theList = new LinkList();
}
public void push(long j) {
theList.insertFirst(j);
}
public long pop() {
return theList.deleteFirst();
}
public boolean isEmpty() {
return theList.isEmpty();
}
public void displayStack() {
System.out.print("Stack (top-->bottom): ");
theList.displayList();
}
}
public class LinkStackApp {
public static void main(String[] args) {
LinkStack theStack = new LinkStack();
theStack.push(20);
theStack.push(40);
theStack.displayStack();
theStack.push(60);
theStack.push(80);
theStack.displayStack();
theStack.pop();
theStack.pop();
theStack.displayStack();
}
}
运行结果：
Stack (top-->bottom): 40 20
Stack (top-->bottom): 80 60 40 20
Stack (top-->bottom): 40 20
Process finished with exit code 0
注意整个程序的组织。LinkStackApp类中的main()方法只能LinkStack类有关。LinkStack类只和LinkList有关。main()方法和LinkList类是不通信的。
用链表实现的队列
public class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class FirstLastList {
private Link first;
private Link last;
public FirstLastList() {
first = null;
last = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
last = newLink;
}
newLink.next = first;
first = newLink;
}
public void insertLast(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
first = newLink;
} else {
last.next = newLink;
}
last = newLink;
}
public long deleteFirst() {
long temp = first.dData;
if (first.next == null) {
last = null;
}
first = first.next;
return temp;
}
public void displayList() {
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
public class LinkQueue {
private FirstLastList theList;
public LinkQueue() {
theList = new FirstLastList();
}
public boolean isEmpty() {
return theList.isEmpty();
}
public void insert(long j) {
theList.insertLast(j);
}
public long remove() {
return theList.deleteFirst();
}
public void displayQueue() {
System.out.print("Queue (front-->rear): ");
theList.displayList();
}
}
public class LinkQueueApp {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.insert(20);
theQueue.insert(40);
theQueue.displayQueue();
theQueue.insert(60);
theQueue.insert(80);
theQueue.displayQueue();
theQueue.remove();
theQueue.remove();
theQueue.displayQueue();
}
}
运行结果：
Queue (front-->rear): 20 40
Queue (front-->rear): 20 40 60 80
Queue (front-->rear): 60 80
Process finished with exit code 0
LinkStack.java和LinkQueue.java程序强调栈和队列是概念上的实体，独立于它们的具体实现。用数组或者链表实现都是一样的。栈的重要性在于它的push()操作和pop()操作，以及如何使用它们；而不是实现这些操作的内在机制。
什么时候应该使用链表而不是数组来实现栈或者队列呢？这一点取决于是否能精准预测栈或者队列需要容纳的数据量。如果这点不清楚，链表就比数组表现出更好的适用性。两者都很快，所以速度可能不是考虑的重点。
数据类型和抽象
略
作为设计工具的ADT
ADT的概念在软件设计过程中也是有用的。只有在完整定义了ADT后，才应该考虑细节问题，例如如何表示数据，如何编码使方法可以存取数据等等。
通过从ADT规范中剔除实现的细节，可以简化设计过程。在未来的某个时刻，易于修改实现。如果用户只接触ADT接口，应该可以在不"干扰"用户代码的情况下修改接口的实现。
当然，一旦设计好ADT，必须仔细选择内部的数据结构，以使规定的操作的效率尽可能的高。例如，如果需要随机存取元素N，那么链表就不够友好，因为对于链表来说，随机访问不是一个高效的操作。选择数组会得到较好的效果。
5.8 有序链表
在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常是只限于删除在链表的头部的最小（或者最大）的链节点。不过，有时也用find()方法和delete()方法在整个链表中搜索某一特定点。
一般，在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动)，另外链表可以扩展到全部有效使用内存，而数组只能局限于一个固定的大小中。但是，有序链表实现起来比有序数组更苦难一些。
在有序链表中插入一个数据项的Java代码
public class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class SortedList {
private Link first;
public SortedList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insert(long key) {
Link newLink = new Link(key);
Link previous = null;
Link current = first;
while (current != null && key > current.dData) {
previous = current;
current = current.next;
}
if (previous == null) {
first = newLink;
} else {
previous.next = newLink;
}
newLink.next = current;
}
public Link remove() {
Link temp = first;
first = first.next;
return temp;
}
public void displayList() {
System.out.print("List (first-->last): ");
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
public class SortedListApp {
public static void main(String[] args) {
SortedList theSortedList = new SortedList();
theSortedList.insert(20);
theSortedList.insert(40);
theSortedList.displayList();
theSortedList.insert(10);
theSortedList.insert(30);
theSortedList.insert(50);
theSortedList.displayList();
theSortedList.remove();
theSortedList.displayList();
}
}
运行结果：
List (first-->last): 20 40
List (first-->last): 10 20 30 40 50
List (first-->last): 20 30 40 50
Process finished with exit code 0
有序链表的效率
在有序链表插入和删除某一项最多需要O(N)次比较(平均N/2),因为必须沿着链表上一步一步走才能找到正确的位置。然后，可以在O(1)的时间内找到或者删除最小值，因为它总在表头。如果一个应用频繁的存取最小项，且不需要快速的插入，那么有序链表是一个有效的方案选择，例如，优先级队列可以用有序链表来实现。
表插入效率
有序链表可以用于一种高效的排序机制。假设有一个无序数组，如果从这个数组取出数据，然后一个一个地插入有序链表中，它们自动按照顺序排列。把它们从有序链表中删除，重新放入数组，那么数组就会排好序了。
这种排序方式总体上比在数组中用常用的插入排序效率更高一些，因为这种方式进行的复制次数少一些，用数组插入排序算法在第三章简单排序中有所描述。它仍然是一个时间级为O(N2)的过程，因为在有序链表中插入一个新的链节点，平均要与一半已存在的数据进行比较，如果插入N个数据项，就进行了N2/4次比较。每一个链节点只进行了两次复制：一次从数组到链表，一次从链表到数组。在数组中进行插入排序需要N^2次移动，相比之下，2*N次移动更好。
表插入排序的Java代码
public class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
}
public class SortedList {
private Link first;
public SortedList() {
first = null;
}
public SortedList(Link[] linkArr) {
first = null;
for (int j = 0 ; j < linkArr.length ; j ++) {
insert(linkArr[j]);
}
}
public void insert(Link k) {
Link previous = null;
Link current = first;
while (current != null && k.dData > current.dData) {
previous = current;
current = current.next;
}
if (previous == null) {
first = k;
} else {
previous.next = k;
}
k.next = current;
}
public Link remove() {
Link temp = first;
first = first.next;
return temp;
}
}
public class ListInsertionSortApp {
public static void main(String[] args) {
int size = 10;
Link[] linkArray = new Link[size];
for (int j = 0 ; j < size; j ++) {
int n = (int) (Math.random()*99);
Link newLink = new Link(n);
linkArray[j] = newLink;
}
System.out.print("Unsorted array :");
for (int j = 0 ; j < size; j ++) {
System.out.print(linkArray[j].dData + " ");
}
System.out.println();
SortedList theSortedList = new SortedList(linkArray);
for (int j = 0 ; j < size; j ++) {
linkArray[j] = theSortedList.remove();
}
System.out.print("Sorted array :");
for (int j = 0 ; j < size; j ++) {
System.out.print(linkArray[j].dData + " ");
}
System.out.println("");
}
}
运行结果：
Unsorted array :44 65 34 32 74 35 36 33 67 58
Sorted array :32 33 34 35 36 44 58 65 67 74
Process finished with exit code 0
和基于数组的插入排序相比，表插入排序有一个缺点，那就是它要开辟差不多两倍的空间：数组和链表必须同时在内存中存在。但是如果有现成的有序链表可用，那么用表插入排序对不太大的数组排序是比较便利的。
5.9 双向链表
双向链表有什么优点呢？传统链的一个潜在问题是沿链表的反向遍历是困难的。用这样一个语句current=current.next可以很方便达到下一个链结点，然后没有对应的方法回到前一个链结点。根据应用的不同，这个限制可能会引起问题。
双向链表提供了这个能力。既允许向前遍历，也允许向后遍历整个链表。其中秘密在于每个链结点有两个指向其他链结点的引用，而不是一个。第一个像普通链表一样指向下一个链结点。第二个指向前一个链结点。图5.13展示了这种链表。
双向链表的Java代码
public class Link {
public long dData;
public Link next;
public Link previous;
public Link(long d) {
dData = d;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class DoubleLinkList {
private Link first;
private Link last;
public DoubleLinkList() {
first = null;
last = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
last = newLink;
} else {
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}
public void insertLast(long dd) {
Link newLink = new Link(dd);
if (isEmpty()) {
first = newLink;
} else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
public Link deleteFirst() {
Link temp = first;
if (first.next == null) {
last = null;
} else {
first.next.previous = null;
}
first = first.next;
return temp;
}
public Link deleteLast() {
Link temp = last;
if (first.next == null) {
first = null;
} else {
last.previous.next = null;
}
last = last.previous;
return temp;
}
public boolean insertAfter(long key, long dd) {
Link current = first;
while (current.dData != key) {
current = current.next;
if (current == null) {
return false;
}
}
Link newLink = new Link(dd);
if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}
public Link deleteKey(long key) {
Link current = first;
while (current.dData != key) {
current = current.next;
if (current == null) {
return null;
}
}
if (current == first) {
first = current.next;
} else {
current.previous.next = current.next;
}
if (current == last) {
last = current.previous;
}
current.next.previous = current.previous;
return current;
}
public void displayForward() {
System.out.print("List(first-->last): ");
Link current = first;
while (current != null) {
current.displayLink();;
current = current.next;
}
System.out.println("");
}
public void displayBackward() {
System.out.print("List(last-->first): ");
Link current = last;
while (current != null) {
current.displayLink();
current = current.previous;
}
System.out.println("");
}
}
public class DoubleLinkedApp {
public static void main(String[] args) {
DoubleLinkList theList = new DoubleLinkList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
theList.displayForward();
theList.displayBackward();
theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
theList.displayForward();
theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
theList.displayForward();
}
}
运行结果
List(first-->last): 66 44 22 11 33 55
List(last-->first): 55 33 11 22 44 66
List(first-->last): 44 22 33
List(first-->last): 44 22 77 33 88
Process finished with exit code 0
基于双向链表的双端队列
以前的章节已经提及，双向链表可以用来作为双端队列的基础。在双端队列中，可以从任何一头插入和删除，双向链表提供了这个能力。
5.10 迭代器
迭代器总是指向链表中的一些链结点。它同链表相关联，但并不等同于链表或是链结点。图5.17显示了指向链表的链结点的两个迭代器
迭代器的其他特性
前面已经看到在几个程序中都使用过previous字段，它使某些操作的执行变得简单，例如从任意位置删除一个链结点。这样的字段在迭代器中也是有用的。
而且，迭代器可能需要改变first字段的值-例如，如果在表头插入和删除一个数据项。如果迭代器是一个单独的类对象，它怎么能访问first这样的私有数据字段呢？一种解决办法是链表创建迭代器时，传递一个引用给迭代器。这个引用存储在迭代器的一个字段中。
链表必须提供公有办法，允许迭代器改变first的值。LinkList类中的这些方法是getFirst()和setFirst()。（这种方法的缺点是允许任何人修改first，这就引入了危险的因素。）
这里有一个修正的(尽管不是完整的)迭代器，这个类引入了一些其他字段，已经reset()方法和nextLink()方法:
public class ListIterator {
private Link current;
private Link previous;
private LinkList ourList;
public ListIterator(LinkList list) {
ourList = list;
reset();
}
public void reset() {
current = ourList.getFirst();
previous = null;
}
public void nextLink() {
previous = current;
current = current.next;
}
}
迭代器的方法
新加的方法让迭代器变得更灵活，更强大。过去在类中实现所有于链表进行迭代有关的操作，例如insertAfter()，现在更自然地由迭代器来实现。例如迭代器包含下面一些方法:
- reset()--把迭代器设在表头
- nextLink()--把迭代器移动到下一个链结点
- getCurrent()--返回迭代器指向的链结点
- andEnd()--如果迭代器到达表尾，返回true
- insertAfter()--在迭代器后面插入一个新的链节点
- insertBefore()--在迭代器前面插入一个新的链结点
- deleteCurrent()--删除迭代器所指链结点
InterIterator.java程序包含一个交互界面，它允许使用者直接控制迭代器。启动程序后，可以通过键入正确的字母执行下面的操作：
- s(Show)--显示链表的内容
- r(Reset)--把迭代器复位并设在表头
- n(Next)--到下一个链结点
- g(Get)--得到当前链结点的内容
- b(InsertBefore)--在当前链结点前插入新链结点
- a(InsertAfter)--在当前链结点后插入新链结点
- d(Delete)--删除当前链结点
InterIterator的java代码
public class Link {
public long dData;
public Link next;
public Link(long dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
public class LinkList {
private Link first;
public LinkList() {
first = null;
}
public Link getFirst() {
return first;
}
public void setFirst(Link f) {
first = f;
}
public boolean isEmpty() {
return (first == null);
}
public ListIterator getIterator() {
return new ListIterator(this);
}
public void displayList() {
Link current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
public class ListIterator {
private Link current;
private Link previous;
private LinkList ourList;
public ListIterator(LinkList list) {
ourList = list;
reset();
}
public void reset() {
current = ourList.getFirst();
previous = null;
}
public void nextLink() {
previous = current;
current = current.next;
}
public boolean atEnd() {
return (current.next == null);
}
public Link getCurrent() {
return current;
}
public void insertAfter(long dd) {
Link newLink = new Link(dd);
if (ourList.isEmpty()) {
ourList.setFirst(newLink);
current = newLink;
} else {
newLink.next = current.next;
current.next = newLink;
nextLink();
}
}
public void insertBefore(long dd) {
Link newLink = new Link(dd);
if (previous == null) {
newLink.next = ourList.getFirst();
ourList.setFirst(newLink);
reset();
} else {
newLink.next = previous.next;
previous.next = newLink;
current = newLink;
}
}
public long deleteCurrent() {
long value = current.dData;
if (previous == null) {
ourList.setFirst(current.next);
reset();
} else {
previous.next = current.next;
if (atEnd()) {
reset();
} else {
current = current.next;
}
}
return value;
}
}
public class InterIterApp {
public static void main(String[] args) throws IOException {
LinkList theList = new LinkList();
ListIterator iter1 = theList.getIterator();
long value;
iter1.insertAfter(20);
iter1.insertAfter(40);
iter1.insertAfter(80);
iter1.insertBefore(60);
while (true) {
System.out.print("Enter first letter of show, reset, next, get, before, after, delete: ");
System.out.flush();
String choice = getString();
if ("".equals(choice)) {
break;
}
switch (choice) {
case "s" :
if (!theList.isEmpty()) {
theList.displayList();
} else {
System.out.println("List is empty");
}
break;
case "r":
iter1.reset();
break;
case "n" :
if (!theList.isEmpty() && !iter1.atEnd()) {
iter1.nextLink();
} else {
System.out.println("Can't go to next Link");
}
break;
case "g":
if (!theList.isEmpty()) {
value = iter1.getCurrent().dData;
System.out.println("Returned " + value);
} else {
System.out.println("List is empty");
}
break;
case "b":
System.out.print("Enter value to insert: ");
System.out.flush();
value = getInt();
iter1.insertBefore(value);
break;
case "a":
System.out.print("Enter value to insert: ");
System.out.flush();
value = getInt();
iter1.insertAfter(value);
break;
case "d":
if (!theList.isEmpty()) {
value = iter1.deleteCurrent();
System.out.println("Deleted " + value);
} else {
System.out.println("List is empty");
}
break;
default:
System.out.println("Invalid entry");
}
}
}
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
}
运行结果
Enter first letter of show, reset, next, get, before, after, delete: s
20 40 60 80
Enter first letter of show, reset, next, get, before, after, delete: g
Returned 60
Enter first letter of show, reset, next, get, before, after, delete: r
Enter first letter of show, reset, next, get, before, after, delete: n
Enter first letter of show, reset, next, get, before, after, delete: n
Enter first letter of show, reset, next, get, before, after, delete: g
Returned 60
Enter first letter of show, reset, next, get, before, after, delete: b
Enter value to insert: 100
Enter first letter of show, reset, next, get, before, after, delete: a
Enter value to insert: 7
Enter first letter of show, reset, next, get, before, after, delete: s
20 40 100 7 60 80
Enter first letter of show, reset, next, get, before, after, delete: d
Deleted 7
Enter first letter of show, reset, next, get, before, after, delete: s
20 40 100 60 80
Enter first letter of show, reset, next, get, before, after, delete:
Process finished with exit code 0
迭代器指向哪里
迭代器类的一个设计问题是决定在不同的操作后，迭代器应该指向哪里。
当用deleteCurrent()删除一项后，迭代器应该放在下一个链结点，前一个链结点，还是表头呢？把迭代器保持在被删除链结点附近是方便的，因为类的用户将在那里执行其他操作。然而，不能把它移动到前一个链结点，因为无法把链表的previous字段置成前一项。（要完成这个任务，需要一个双向链表。）解决办法是把迭代器移动到被删除链结点的下一个链结点。如果恰巧删除链表的最后一个数据项，迭代器复位指向表头。
atEnd()方法
还有关于atEnd()方法的最后一个问题。有两种做法：当迭代器指向链表最后一个有效链结点时，它返回true，或者当迭代器指向最后一个链结点的"下一个"时(这时，它不是指向一个有效的链结点)，它返回true。
迭代器在单链表中不能倒退，所以这里还是采用第一种方法，用这种方法迭代器总是指向一个有效的链结点。在写这种遍历链表的循环时要格外小心。
5.11 小结
- 链表包含一个linkedList对象和许多Link对象。
- linkedList对象包含一个引用，这个引用通常叫做first，它指向链表的第一个链结点。
- 每个Link对象包含数据和一个引用，通常叫做next，它指向链表的下一个链结点。
- next字段为null值意味着链表的结尾。
- 在表头插入链结点需要把新的链结点的next字段指向原来的第一个链结点，然后把first指向新链结点。
- 在表头删除链结点要把first指向first.next。
- 为了遍历链表，从first开始，然后从一个链结点到下一个链结点，方法是用每个链结点的next字段找到下一个链结点。
- 通过遍历链表可以找到拥有特定值的链结点。一旦找到，可以显示、删除或其他方式操作该链结点。
- 新链结点可以插入某个特定值的链结点的前面或者后面，首先要先遍历找到这个链结点。
- 双端链表在链表中维护一个指向最后一个链结点的引用，它通常和first一样，叫做last。
- 双端链表允许在表尾插入数据项。
- 抽象数据类型是一种数据存储类，不涉及它的实现。
- 栈和队列是ADT。它们既可以用数据实现，也可以用链表实现。
- 有序链表中，链结点按照关键值升序（有时候是降序）排列。
- 在有序链表中插入需要O(N)时间，因为必须找到正确的插入点。最小值链结点的删除需要O(1)的时间。
- 双向链表中，每个链结点包含对前一个链结点的引用，同时有对后一个链结点的引用。
- 双向链表允许反向遍历，并可以从表尾删除。
- 迭代器是一个引用，它被封装在类对象中，这个引用指向相关联的链表中链结点。
- 迭代器方法允许使用者沿链表移动迭代器，并访问当前指示的链结点。
- 能用迭代器遍历链表，在选定链结点（或所有链结点）上执行某些操作。
6、递归
递归是一种方法（函数）调用自己的编程技术。这听起来有点奇怪，或者甚至像是一个灾难性的错误。但是，递归在编程中确是最有趣的，又是惊人高效的技术之一。在第一次遇到递归时，它似乎让人觉得难以置信。然而，递归不仅可以解决特定的问题，而且它也为解决很多问题提供了一个独特的概念上的框架。
在这一章中，将研究许多例子，以此来说明递归可以应用在多种情况下。首先将计算三角数字和阶乘，生成变位字，执行一个递归的二分查找，然后解决汉诺塔问题，最后将研究一种被称为归并排序的排序技术。
同时还会讨论递归方法的优势和劣势，并且将说明一个递归的方法如何被转化成一个基于栈的非递归方法。
6.1 三角数字
据说毕达哥拉斯理论家，又称一群在毕达哥拉斯领导下的古希腊的数学家，发现了数字在序列1,3,6，10，15,21，...中一种奇特的联系。
这个数列中的第n项是由第n-1项加n得到的。这个序列中的数字被称为三角数字。
使用循环查找第n项
int triangle(int n) {
int total = 0;
while (n > 0) {
total += n;
n--;
}
return total;
}
使用递归查找第n项
int triangle(int n) {
return (triangle(n-1) + n);
}
其实方法调用就是把控制转移到方法开始。这种控制的转移既可以发生在方法的外部，也可以发生在方法的内部。
为了防止无限重复调用自身的过程，在序列中第一个找到三角数字的人，也就是当n等于1时，他肯定知道结果是1，可以给triangle增加一个条件来表示：
int triangle(int n) {
if (n == 1) {
return 1;
} else {
return (triangle(n-1) + n);
}
}
导致递归方法返回而没有再一次进行递归调用，此时我们称为基值情况。每一个递归方法都有一个基值（终止）条件，以防止无限递归下去，以及由此引发的程序崩溃。这一点是至关重要的。
递归方法的特征
- 调用自身
- 当它调用自身的时候，它这样做是为了解决更小的问题。
- 存在某个足够简单的问题的层次，在这一层算法不需要调用自己就可以直接解答，且返回结果。
递归方法有效率吗
调用一个方法会有一定的额外开销。控制必须从这个调用的位置转移到这个方法的开始处。除此之外，传递给这个方法的参数以及返回的地址都要被压入一个内部的栈里，为的是这个方法可以访问参数值和知道返回到哪里。
就triangle()这个方法来讲，因为有上述开销而造成的结果，可能while循环方法执行的速度比递归方法快。在此题中，递归的代价也许不算太大。但是如果由于递归方法的存在，造成太大规模的方法调用的话，可能会考虑消除递归。在这一章的最后将会详谈一些这方面的问题。
另外一个低效性反映在系统内存空间存储所有的参数以及返回值，如果有大量的数据需要存储，这就会引起栈溢出的问题。
人们常常采用递归，是因为它从概念上简化了问题，而不是因为它本质上更有效率。
数学归纳法
递归就是程序设计中的的数学归纳法。数学归纳法是一种通过自身的语汇定义事物自己的方法。（语汇也被用于描述证明原理的相关方法。）
6.2 阶乘
略
6.3 变位字
假设想要列出一个指定单词的所有变位字，也就是列出该词的全排列（不管这些排列是否是真正的英语单词），它们都是由原来这个单词的字母组成。我们称这个工作是变位一个单词或称全排列一个单词。比如，全排列cat，会产生cat、cta、atc、act、tca、tac。
AnagramApp代码
public class AnagramApp {
public static int size;
public static int count;
public static char[] arrChar = new char[100];
public static void main(String[] args) throws IOException {
System.out.print("Enter a word: ");
String input = getString();
size = input.length();
count = 0;
for (int j = 0 ; j < size; j ++) {
arrChar[j] = input.charAt(j);
}
doAnagram(size);
}
public static void doAnagram(int newSize) {
if (newSize == 1) {
return;
}
for (int j = 0 ; j < newSize ; j++ ) {
doAnagram(newSize - 1);
if (newSize == 2) {
displayWord();
}
rotate(newSize);
}
}
public static void rotate(int newSize) {
int j;
int position = size - newSize;
char temp = arrChar[position];
for (j = position + 1 ; j < size ; j ++) {
arrChar[j-1] = arrChar[j];
}
arrChar[j-1] = temp;
}
public static void displayWord() {
if (count < 99) {
System.out.print(" ");
}
if (count < 9) {
System.out.print(" ");
}
System.out.print(++count + " ");
for (int j = 0 ; j < size; j++) {
System.out.print(arrChar[j]);
}
System.out.print(" ");
System.out.flush();
if (count % 6 == 0) {
System.out.println("");
}
}
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
运行结果：
Enter a word: cats
1 cats 2 cast 3 ctsa 4 ctas 5 csat 6 csta
7 atsc 8 atcs 9 asct 10 astc 11 acts 12 acst
13 tsca 14 tsac 15 tcas 16 tcsa 17 tasc 18 tacs
19 scat 20 scta 21 satc 22 sact 23 stca 24 stac
Process finished with exit code 0
6.4 递归的二分查找
递归取代循环
public class OrderArray {
private long[] a;
private int nElems;
public OrderArray(int max) {
a = new long[max];
nElems = 0;
}
public int size() {
return nElems;
}
public int find(long searchKey) {
return recFind(searchKey, 0 ,nElems - 1);
}
private int recFind(long searchKey, int lowerBound, int upperBound) {
int curIn;
curIn = (lowerBound + upperBound) / 2;
if (a[curIn] == searchKey) {
return curIn;
}else if (lowerBound > upperBound) {
return nElems;
} else {
if (a[curIn] < searchKey) {
return recFind(searchKey, curIn + 1, upperBound);
} else {
return recFind(searchKey, lowerBound, curIn - 1);
}
}
}
public void insert(long value) {
int j;
for (j = 0 ; j < nElems ; j++) {
if (a[j] > value) {
break;
}
}
for (int k = nElems; k > j ; k--) {
a[k] = a[k-1];
}
a[j] = value;
nElems++;
}
public void display() {
for (int j = 0 ; j < nElems ; j++) {
System.out.print(a[j] + " ");
}
System.out.println("");
}
}
public class BinarySearchApp {
public static void main(String[] args) {
int maxSize = 100;
OrderArray arr;
arr = new OrderArray(maxSize);
arr.insert(72);
arr.insert(90);
arr.insert(45);
arr.insert(126);
arr.insert(54);
arr.insert(99);
arr.insert(144);
arr.insert(27);
arr.insert(135);
arr.insert(81);
arr.insert(18);
arr.insert(108);
arr.insert(9);
arr.insert(117);
arr.insert(63);
arr.insert(36);
arr.display();
int searchKey = 27;
int index = arr.find(searchKey);
if (index != arr.size()) {
System.out.println("Found " + searchKey + " in index " + index);
} else {
System.out.println("Can't find " + searchKey);
}
}
}
运行结果
9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144
Found 27 in index 2
Process finished with exit code 0
递归的二分查找和非递归的二分查找有同样的大O效率:O(log^N)。递归的二分查找更为简洁一些，但是它的速度可能会慢一点。
分治算法
递归的二分查找是分治算法的一个例子。把一个大问题分成两个相对来说更小的问题，并且分别解决每一个小问题。对每一个小问题的解决方式是一样的:把每个小问题分成两个更小的问题并且解决它们。这个过程一直持下去直到达到易于求解的基值情况，就不用再继续分了。
分治算法常常是一个方法，在这个方法中有两个对自身的递归调用，分别对应于问题的两个部分。在二分查找中，就有两个这样的调用，只不过只有一个执行了。(调用哪一个取决于关键字的值。)在这一章中，后面将会遇到归并排序，它是真正执行了两个递归调用（对分成两半的数据分别进行排序）。
6.5 汉诺塔问题
汉诺顿问题是由很多放置在三个塔座上的盘子组成的一个古老的难题，如图6.10所示。
所有盘子的直径是不同的，并且盘子中央都有一个洞以使它们刚好可以放到塔座上。所有的盘子刚开始都放在塔座A上。这个难题的目标是将所有的盘子都从塔座A移动到塔座C上。每次只能移动一个盘子，并且任何一个盘子都不可以放在比自己小的盘子之上。
移动的子树
在塔座A上盘子初始的树形(或金字塔形)排列称为一棵树。(这种树与本书其他地方提到的作为数据存储结构的树无关。)生成盘子的较小的树形堆是问题解决过程中的一步。这些所含盘子数小于盘子总数的较小的树称为子树。举例来说，如果要移动4个盘子，会发现中间的一个状态是有3个盘子的子树在塔座B上，如果6.12所示。
这些子树在这个难题的解决过程中会形成多次。子树形成多次是因为一颗子树的形式是把一个更大的盘子从一个塔座上转移到另一个塔座的唯一方法：所有的小盘子都必须先放置到一个中介的塔座上，在这个中介的塔座上自然会形成一颗子树。
当手动解决这个难题的时候，有一个经验法则，可以提供帮助。如果试图要移动的子树含有奇数个盘子，开始时直接把最顶端的盘子移动到想要把这颗子树移动到的那个塔座上。如果试图要移动一颗含有偶数个盘子的子树，那么开始时要把最顶端的盘子移动到中介塔座上。
递归的算法
用子树的概念可以递归的表示出汉诺塔难题的解决办法。假设想要把所有的盘子从源塔座上(称为S)移动到目标塔座上(称为D)。有一个可以使用的中介塔座(称为I)。假定在塔座S上有n个盘子。算法如下：
1.从塔座S移动包含上面n-1个盘子的子树到塔座I上。
2.从塔座S移动剩余的盘子(最大的盘子)到塔座D上。
3.从塔座I移动子树到塔座D上。
当开始的时候，源塔座是A，中介塔座是B，目标塔座是C。图6.13显示了这种情况的三个步骤。
towers.java程序
public class TowersApp {
public static int nDisks = 3;
public static void main(String[] args) {
doTowers(nDisks, 'A', 'B', 'C');
}
private static void doTowers(int topN, char from, char inter, char to) {
if (topN == 1) {
System.out.println("Disk 1 from " + from + " to " + to);
} else {
doTowers(topN-1, from, to, inter);
System.out.println("Disk " + topN + " from " + from + " to " + to);
doTowers(topN-1 , inter, from ,to);
}
}
}
运行结果
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
Process finished with exit code 0
6.6 归并排序
最后一个递归的例子是归并排序。归并排序比在第三章"简单排序"中看到的排序方法要有效很多，至少在速度上是这样的。冒泡排序、插入排序和选择排序需要O(N2)的时间，而归并排序只需要O(N*logN)。如果N(被排序的数据项的数目)是10000，那么N2就是100000000，而NlogN只是40000。如果为这么多数据项排序用归并排序的话需要40s，那么用插入排序则会需要将近28个小时。
归并排序也相当容易实现。归并排序在概念上比下一章中看到的快速排序和希尔排序都要容易理解。
归并排序的一个缺点是它需要在寄存器中有另一个大小等于被排序的数据项的数组。如果初始数组几乎占满整个寄存器，那么归并排序将不能工作。但是有足够的空间，归并排序会是一个很好的选择。
归并两个有序的数组
归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个数组C，数组C包含数组A和B的所有数据项，并且使他们有序的排列在数组C中。首先考察归并的过程；然后看它是如何在排序中使用的。
表6.3显示了必要的比较，由此来决定要复制那个数据项。
清单6.5
public class MergeApp {
public static void main(String[] args) {
int[] arrayA = {23, 47, 81, 95};
int[] arrayB = {7, 14, 39, 55, 62, 74};
int[] arrayC = new int[arrayA.length + arrayB.length];
merge(arrayA, arrayB, arrayC);
display(arrayC);
}
public static void merge(int[] arrayA, int[] arrayB, int[] arrayC) {
int sizeA = arrayA.length;
int sizeB = arrayB.length;
int aDex = 0, bDex = 0, cDex = 0;
while (aDex < sizeA && bDex < sizeB) {
if (arrayA[aDex] < arrayB[bDex]) {
arrayC[cDex++] = arrayA[aDex++];
} else {
arrayC[cDex++] = arrayB[bDex++];
}
}
while (aDex < sizeA) {
arrayC[cDex++] = arrayA[aDex++];
}
while (bDex < sizeB) {
arrayC[cDex++] = arrayB[bDex++];
}
}
public static void display(int[] theArray) {
int size = theArray.length;
for (int j = 0; j < size ; j ++) {
System.out.print(theArray[j] + " ");
}
System.out.println("");
}
}
运行结果
7 14 23 39 47 55 62 74 81 95
Process finished with exit code 0
通过归并进行排序
归并排序的思想是把一个数组分成两半，排序每一半，然后用merge()方法把数据的两半归并成一个有序的数组。如果为每一部分排序呢?这一章讲述的是递归，所以大概已经有答案了:把每一半都分成两个四份之一，对每个四分之一部分排序，然后将它们归并成一个有序的一半。
类似的，每一对八分之一部分归并成一个有序的四份之一部分，每一对十六分之一部分归并成一个有序的八分之一部分，以此类推，反复分割数组，直到得到的子数组只含有一个数据项。这就是基值条件：设定只有一个数据项的数组是有序的。
清单6.6
public class DArray {
private long[] theArray;
private int nElems;
public DArray(int max) {
theArray = new long[max];
nElems = 0;
}
public void insert(long value) {
theArray[nElems] = value;
nElems++;
}
public void display() {
for (int j = 0; j < nElems ; j ++) {
System.out.print(theArray[j] + " ");
}
System.out.println("");
}
public void mergeSort() {
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0 , nElems - 1);
}
private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound) {
return;
}
int mid = (lowerBound + upperBound) / 2;
recMergeSort(workSpace, lowerBound, mid);
recMergeSort(workSpace, mid + 1, upperBound);
merge(workSpace, lowerBound, mid+1 , upperBound);
}
private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
int j = 0;
int lowBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowBound + 1;
while (lowPtr <= mid && highPtr <= upperBound) {
if (theArray[lowPtr] < theArray[highPtr]) {
workSpace[j++] = theArray[lowPtr++];
} else {
workSpace[j++] = theArray[highPtr++];
}
}
while (lowPtr <= mid) {
workSpace[j++] = theArray[lowPtr++];
}
while (highPtr <= upperBound) {
workSpace[j++] = theArray[highPtr++];
}
System.out.println("----------------");
for (int i = 0 ; i < workSpace.length ; i ++) {
System.out.print(workSpace[i] + " ");
}
System.out.println("");
for (j = 0 ; j < n ; j ++) {
theArray[lowBound + j] = workSpace[j];
}
}
}
public class MergeSortApp {
public static void main(String[] args) {
int maxSize = 100;
DArray arr;
arr = new DArray(maxSize);
arr.insert(64);
arr.insert(21);
arr.insert(33);
arr.insert(70);
arr.insert(12);
arr.insert(85);
arr.insert(44);
arr.insert(3);
arr.insert(99);
arr.insert(0);
arr.insert(108);
arr.insert(36);
arr.display();
arr.mergeSort();
arr.display();
}
}
运行结果
64 21 33 70 12 85 44 3 99 0 108 36
----------------
21 64 0 0 0 0 0 0 0 0 0 0
----------------
21 33 64 0 0 0 0 0 0 0 0 0
----------------
12 70 64 0 0 0 0 0 0 0 0 0
----------------
12 70 85 0 0 0 0 0 0 0 0 0
----------------
12 21 33 64 70 85 0 0 0 0 0 0
----------------
3 44 33 64 70 85 0 0 0 0 0 0
----------------
3 44 99 64 70 85 0 0 0 0 0 0
----------------
0 108 99 64 70 85 0 0 0 0 0 0
----------------
0 36 108 64 70 85 0 0 0 0 0 0
----------------
0 3 36 44 99 108 0 0 0 0 0 0
----------------
0 3 12 21 33 36 44 64 70 85 99 108
0 3 12 21 33 36 44 64 70 85 99 108
Process finished with exit code 0
归并排序的效率
正如前面提到的那样,归并排序的运行时间是O(Nlog^N)。如何知道这个时间呢?首选看这个算法执行的过程中，如何计算一个数据项被复制的次数和比较的次数。假设复制和比较是最费时的操作,递归的调用和返回不增加额外开销。
复制的次数
考虑图6.15。首行下面的每一个单元都代表了从数组复制到工作空间的一个数据项。
把图6.15所有单元加在一起(7个标数字的步骤)表明了需要24次复制来给8个数据项排序。Log28=3,所以8log28=24。这说明，对于有8个数据项的情况，复制的次数与Nlog^N成正比。
另一个用来计算复制次数的方法是，排序8个数据项需要有3层，每一层包含8次复制。一层意味着所有元素都复制到相同大小的子数组中。所以也就是3*8或者说有24次复制。
表6.4概略表明了这个信息。
实际上，这些数据项不仅被复制到数组workspace中，并且也会被复制回原数组中。这会使复制的次数增加一倍，正如在复制次数一栏中显示的一样。表6.4最后一栏表明了比较次数。
比较的次数
在归并排序算法中，比较的次数总是比复制的次数稍微少一些的。那么少多少呢？假设数据项的个数是2的乘方，对于每一个独立的归并操作，比较的最大次数总是比正在归并的数据项少一，并且比较的最小次数是正在归并的数据项的一半。可以在图6.18中看到这为什么是正确的，这个图表明了试图归并各有四个数据项的两个数组时的两种可能性。
重新来看图6.15，可以看到为8个数据项进行排序，需要有7次归并操作。正在被归并的数据项个数已经相应的比较次数如表6.5所示。
6.7 消除递归
有一些算法趋向于递归的方法，另一些算法则不是。正如前面看到的 那样，递归的方法可以用一个简单的循环来实现，那样效率更高。但是各种分治算法，比如归并排序的递归函数，能工作得非常好。
一个算法作为一个递归的方法通常从概念上很容易理解，但是，在实际的运用中证明递归算法的效率不太高。在这种情况下，把递归的算法转换成非递归的算法是非常有用的。这种转换经常会用到栈。
6.8 小结
- 一个递归方法每次用不同的参数值反复调用自己。
- 某种参数值使递归的方法返回，而不再调用自身。这称为基值情况。
- 当递归方法返回时，递归过程通过逐渐完成各层方法实例的未执行部分，而从最内层返回到最外层的原始调用处。
- 三角数字和阶乘都可以通过递归的方法或简单的循环来实现。
- 一个单词的全排列（它的n个字母的所有可能排列）可以通过反复地轮换它的字母以及全排列它最右边的n-1个字母来递归得到。
- 二分查找可以通过检查查找关键字在有序序列的哪一半，然后在这一半做相同的事情，这些都可以用递归实现。
- 汉诺塔难题可以用递归来解决：把除了最底端盘子外的所有盘子形成的子树移动到一个中介塔座上，然后把最底端的盘子移动到目标塔座上，最终把那个子树移动到目标塔座上。
- 归并两个有序的数组意思是创建第三个数组，这个数组按顺序存储从这两个有序数组中取到的所有数据项。
- 在归并排序中，一个大数组的单个数据项的子数组归并为两个数据项的子数组，然后两个数据项的子数组归并为四个数据项的子数组，如此下去直到所有的数组数据项有序。
- 归并排序需要O(N*log^N)时间。
- 归并排序需要一个大小等于原来数组的工作空间。
- 对于三角数字、阶乘、单词字母全排列以及二分查找，它们的递归的方法只包含一次对自身的调用。（在二分查找的代码中显示有两次，但是在任何给定代码的运行中只有一次自身的调用执行了。）
- 对于汉诺顿和归并排序问题，它们的递归方法包含两次递归调用。
- 任何可以用递归完成的操作都可以用栈来实现。
- 递归的方法可能效率低。如果是这样的话，有时可以用一个简单的循环或者是一个基于栈的方法来替代它。
