【练习6-1(Queue.java)】改进Queue类
可使用private修饰符对第5章的练习5-2开发的Queue类进行一项非常重要的改进。在那个版本中，Queue类的所有成员都使用默认访问设置，实际上相当于是公有的。这意味着使用Queue的程序可以直接访问它包含的数组，这样就可能不按顺序任意访问数组中的元素。因为队列的关键就是提供一个先进先出的列表，不按顺序访问是不被允许的。而且这样一来，一些恶意的编程人员就可以改动存储在putloc和getloc索引中的值，从而破坏队列。幸运的是，通过应用private修饰符可以轻松地解决这类问题。
package javaone.a.beginners.guide.chaptersix;// An improved queue class for characters.
class Queue{// these members are now privateprivate char q[]; // this array holds the queueprivate int putloc, getloc; // the put and get indicesQueue(int size){q = new char[size]; // allocates memory for queueputloc = getloc = 0;}// put a character into the queuevoid put(char ch){if(putloc == q.length){System.out.println(" - Queue is full.");return;}q[putloc++] = ch;}// get a character from the queue.char get(){if(getloc == putloc){System.out.println(" - Queue is empty.");return (char) 0;}return q[getloc++];}
}public class ChapterSixProgramOne {public static void main(String[] args) {Queue test = new Queue(10);
// test.q[0] = 99; // wrong!
// test.putloc = -100; // won't work!}}
【练习6-2(QDemoTwo.java)】重载Queue构造函数
本例将通过为Queue类提供两个附加的构造函数来增强其功能。第一个构造函数将从另一个队列构造出一个新队列。第二个构造函数将构造一个队列，并为其赋初始值。如下所示，添加这些构造函数将增强Queue潜在的实用性。
package javaone.a.beginners.guide.chaptersix;// A queue class for characters.
class QueueOne{private char q[]; // this array holds the queueprivate int putloc, getloc; // the put and get indices// Construct an empty Queue given its size.QueueOne(int size){q = new char[size]; // allocates memory for queueputloc = getloc = 0;}// Construct a Queue from a QueueQueueOne(QueueOne ob){putloc = ob.putloc;getloc = ob.getloc;q = new char[ob.q.length];// copy elementsfor (int i = getloc; i < putloc; i++) {q[i] = ob.q[i];}}// Construct a Queue with initial values.QueueOne(char a[]){putloc = 0;getloc = 0;q = new char[a.length];for (int i = 0; i < a.length; i++) {put(a[i]);}}// put a character into the queuevoid put(char ch){if(putloc == q.length){System.out.println(" - Queue is full.");return;}q[putloc++] = ch;}// get a character from the queue.char get(){if(getloc == putloc){System.out.println(" - Queue is empty.");return (char) 0;}return q[getloc++];}
}// Demonstrate the Queue class.
public class ChapterSixProgramTwo {public static void main(String[] args) {// construct 10-element empty queueQueueOne qOne = new QueueOne(10);char name[] = {'T', 'o', 'm'};// construct queue from arrayQueueOne qTwo = new QueueOne(name);char ch;int i;// put some characters into qOnefor (i = 0; i < 10; i++) {qOne.put((char) ('A' + i));}// construct queue from another queueQueueOne qThree = new QueueOne(qOne);// Show the queues.System.out.print("Contents of qOne: ");for (i = 0; i < 10; i++) {ch = qOne.get();System.out.print(ch);}System.out.println("\n");System.out.print("Contents of qTwo: ");for (i = 0; i < 3; i++) {ch = qTwo.get();System.out.print(ch);}System.out.println("\n");System.out.print("Contents of qThree: ");for (i = 0; i < 10; i++) {ch = qThree.get();System.out.print(ch);}}}
【练习6-3(QSDemo.java)】快速排序
第5章中介绍了名为冒泡排序的简单排序方法。那时就提到除此之外，还存在更好的排序方法。下面要开发的就是最好的排序方法之一：快速排序(quick sort)。快速排序是由C.A.R.Hoare发明并命名的，它是目前最好的通用排序算法，因为实现快速排序的最好方法就是使用递归，所以第5章没有介绍它。这里将开发一个对字符数组进行排序的程序，但是其逻辑适用于任何类型对象的排序。
快速排序建立在分割的思想上。基本过程是选择一个称为比较字(comparand)的值，然后把数组分割为两部分。大于等于分割值的元素放在一边，小于该值的元素放在另一边。然后对分开的部分再进行分割，直到数组排序完成。
选择比较字的方法有两种：既可以随机选择，也可以选择数组的一个小的集合的平均值。为优化排序，应该选择正好位于数值范围中间的值。然而对于绝大多数数据集合而言，这并不容易。最差的情况下就是选择的值位于一端。然而，即使在这种情况下，快速排序依然可以正确执行。我们开发的快速排序以数组的中间元素作为比较字。
package javaone.a.beginners.guide.chaptersix;// Try This 6-3: A simple version of the Quicksort
class Quicksort{// Set up a call to the actual Quicksort method.static void qsort(char items[]){qs(items, 0, items.length - 1);}// A recursive version of Quicksort for characters.private static void qs(char items[], int left, int right){int i, j;char x, y;i = left;j = right;x = items[(left + right) / 2];do{while((items[i] < x) && (i < right)){i++;}while((items[j] > x) && (j > left)){j--;}if(i <= j){y = items[i];items[i] = items[j];items[j] = y;i++;j--;}}while (i <= j);if(left < j){qs(items, left, j);}if(i < right){qs(items, i, right);}}}public class ChapterSixProgramThree {public static void main(String[] args) {char a[] = {'d', 'x', 'a', 'r', 'p', 'j', 'i'};System.out.print("Original array: ");for(int i = 0; i < a.length; i++){System.out.print(a[i]);}System.out.println();// now, sort the arrayQuicksort.qsort(a);System.out.print("Sorted array: ");for(int i = 0; i < a.length; i++){System.out.print(a[i]);}}}
6.10 自测题
1. 如果已经给定这样的一段代码：
class X{
private int count;
那么下面的代码段正确吗?
class Y{
public static void main(String[] args) {
X ob = new X();
ob.count = 10;
答案：不正确，不能在类的外部访问private成员变量。
2. 访问修饰符必须位于成员声明的_______。
答案：置于成员声明之前。
3. 堆栈是队列的补充。它使用先进后出访问方式，与一堆盘子十分相似。第一个放在桌上的盘子是最后一个使用的。创建一个名为Stack的堆栈类来存储字符。将访问堆栈的方法命名为push()和pop()。创建堆栈时允许用户指定堆栈的大小。让Stack类的其他成员保持为私有的（提示：可以把Queue类用作一个模型，仅改变它的数据访问方式就可以了）。
package javaone.a.beginners.guide.chaptersix;// A stack class for characters.
class Stack{private char stck[]; // this array holds the stackprivate int tos; // top of stack// Construct an empty Stack given its size.Stack(int size){stck = new char[size]; // allocate memory for stacktos = 0;}// Construct a Stack form a StackStack(Stack ob){tos = ob.tos;stck = new char[ob.stck.length];// copy elementsfor (int i = 0; i < tos; i++) {stck[i] = ob.stck[i];}}// Construct a stack with initial values.Stack(char a[]){stck = new char[a.length];for (int i = 0; i < a.length; i++) {push(a[i]);}}// Push characters onto the stack.void push(char ch){if(tos == stck.length){System.out.println(" -- Stack is full.");return;}stck[tos] = ch;tos++;}// Pop a character from the stack.char pop(){if(tos == 0){System.out.println(" -- Stack is empty.");return (char) 0;}tos--;return stck[tos];}
}// Demonstrate the Stack class.
public class ChapterSixExerciseThree {public static void main(String[] args) {// construct 10-element empty stackStack stkOne = new Stack(10);char name[] = {'T', 'o', 'm'};// construct stack from arrayStack stkTwo = new Stack(name);char ch;int i;// put some characters into stkOnefor(i = 0; i < 10; i++){stkOne.push((char) ('A' + i));}// construct stack from another stackStack stkThree = new Stack(stkOne);// show the stacks.System.out.print("Contents of stkOne: ");for (i = 0; i < 10; i++) {ch = stkOne.pop();System.out.print(ch);}System.out.println();System.out.print("Contents of stkTwo: ");for (i = 0; i < 3; i++) {ch = stkTwo.pop();System.out.print(ch);}System.out.println();System.out.print("Contents of stkThree: ");for (i = 0; i < 10; i++) {ch = stkThree.pop();System.out.print(ch);}}}
4. 已知下面的类：
class Test{
int a;
Test(int i) { a = i; }
}
编写一个名为swap()的方法来交换两个Test对象引用所引用对象的内容。
package javaone.a.beginners.guide.chaptersix;class TestTwo{int a;TestTwo(int i){a = i;}
}
public class ChapterSixExerciseFour {public static void main(String[] args) {TestTwo obOne = new TestTwo(1);TestTwo obTwo = new TestTwo(2);System.out.println("Before swap: " + obOne.a + " "+ obTwo.a);swap(obOne, obTwo);System.out.println("After swap: " + obOne.a + " "+ obTwo.a);}static void swap(TestTwo obOne, TestTwo obTwo){int temp = obOne.a;obOne.a = obTwo.a;obTwo.a = temp;}
}
5. 下面的代码段正确吗?
class X{
int meth(int a, int b){...}
String meth(int a, int b){...}
答案： 不正确，重载的方法虽然可以具有不同的返回类型，但它们不参与重载解析。重载方法必须具有不同的形参列表。
6. 编写一个递归方法来反向显示字符串的内容。
package javaone.a.beginners.guide.chaptersix;class Backwards{String str;Backwards(String s){str = s;}void backward(int idx){if(idx != str.length()-1){backward(idx+1);}System.out.print(str.charAt(idx));}
}
public class ChapterSixExerciseSix {public static void main(String[] args) {Backwards b = new Backwards("This is a test");b.backward(0);}}
7. 如果一个类的所有对象都需要共享同一个变量，必须怎样声明该变量?
答案：共享变量被声明为static。
8. 为什么使用static代码块。
答案：在创建任何对象之前，static代码块用来执行任何与类相关的初始化操作。
9. 什么是内部类?
答案：内部类是非静态的嵌套类。嵌套类不是独立于包含它的类而存在的。因此，嵌套类的作用域就局限在它的外层类。
10. 为使一个成员只被同一个类中的其他成员访问，应该使用什么访问修饰符?
答案: private。
11. 方法名加上它的形参列表组成了方法的________。
答案：签名。
12. 向一个方法传递int变量是通过使用________调用。
答案： 传值方式。
13. 创建一个varargs方法sum()，对传递给它的int值求和。让该方法返回结果。演示其用法。
package javaone.a.beginners.guide.chaptersix;class SumIt{int sum(int ... n){int result = 0;for (int i = 0; i < n.length; i++) {result += n[i];}return result;}
}public class ChapterSixExerciseThirteen {public static void main(String[] args) {SumIt siObj = new SumIt();int total = siObj.sum(1,2,3);System.out.println("Sum is " + total);total = siObj.sum(1,2,3,4,5);System.out.println("Sum is " + total);}}
14. varargs方法可以重载吗?
答案： 可以重载。
15. 提供一个重载的varargs方法导致歧义的例子。
