【练习5-1(Bubble.java)】排序数组
因为一维数组把数据组织到一个可索引的线性列表中，所以这是进行排序的完美数据结构。这个练习将学习一种简单方法对数组进行排序。如你所知，排序算法有几种不同的方法。这里只指出三种：快速排序、shaker排序和shell排序。然而，众所周知，最简单、最易理解的方法是冒泡排序(Bubble)排序法。尽管冒泡排序效率不高（事实上，它的性能对于大型数组的排序是难以接受的）,但在一些小的数组排序中可以使用。
package javaone.a.beginners.guide.chapterfive;
/*
Try this 5-1
Demonstrate the Bubble sort.
*/
public class ChapterFiveProgramOne {
public static void main(String[] args) {
int nums[] = {99, -10, 100123, 18, -978, 5623, 463, -9, 287, 49};
int a, b, t;
int size;
size = 10; // number of elements to sort
// display original array
System.out.print("Original array is: ");
for (int i = 0; i < size; i++) {
System.out.print(" " + nums[i]);
}
System.out.println();
// This is the Bubble sort.
for(a=1; a < size; a++) {
for(b=size-1; b >= a; b--) {
if(nums[b-1] > nums[b]) { // if out of order
// exchange elements
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
}
}
// display sorted array
System.out.print("Sorted array is: ");
for(int i=0; i<size; i++) {
System.out.print(" " + nums[i]);
}
System.out.println();
}
}
【练习5-2(QDemo.java)】Queue类
如你所知，数据结构是组织数据的一种方法，最简单的数据结构就是数组，它是一个支持随机访问元素的线性表。数组常用作其他更复杂结构（如堆栈和队列）的基础。堆栈(stack)是一个元素访问顺序为先进后出(FILO)的列表，队列(queue)是一个元素访问顺序为先进先出的列表。因此，堆栈就像桌上的一堆盘子，第一个放下的盘子最后才用。而队列就像银行里的一队人，队中的第一个人最早享受服务。
像堆栈和队列这样的数据结构令人着迷的地方是它们把信息的储存与访问信息的方法结合了起来。因此，堆栈和队列可以作为一种数据引擎，其中数据结构本身提供了存储和检索的功能，无须通过程序手动完成。很明显，这样的结合对类而言是绝好的选择，在本练习中，将创建一个简单的队列类。
一般而言，队列支持两个基本操作：put和get。每一个put操作都会把一个新元素放在队列末尾。灭一个get操作都会检索队列前端的元素。队列操作是消耗型的：一旦一个元素被检索后，它就不能再次被检索了。在没有可用的空间来存储新的元素时队列为满，在所有元素都删除后队列为空。
最后一点:队列有两种基本类型——循环队列或非循环队列。循环队列可以重新使用已经删除掉元素的空间。非循环队列则不能重用这些位置，最终会用完所有的空间。为简单起见，本例创建的是一个非循环队列，但是只需要做一些简单的思考与努力，就可以轻松地把它转换为一个循环队列。
package javaone.a.beginners.guide.chapterfive;
/*
Try This 5-2
A queue class for characters.
*/
class Queue{
char q[]; // this array holds the queue
int putloc, getloc; // the put and get indices
Queue(int size){
q = new char[size]; // allocates memory for queue
putloc = getloc = 0;
}
// put a character into the queue
void put(char ch){
if(putloc == q.length){
System.out.println(" - Queue is full.");
return;
}
q[putloc++] = ch;
}
// get a character from the queuq
char get(){
if(getloc == putloc){
System.out.println(" - Queue is empty.");
return (char) 0;
}
return q[getloc++];
}
}
// Demonstrate the Queue class.
public class ChapterFiveProgramTwo {
public static void main(String[] args) {
Queue bigQ = new Queue(100);
Queue smallQ = new Queue(4);
char ch;
int i;
System.out.println("Using bigQ to store the alphabet.");
// put some numbers into bigQ
for(i = 0; i < 26; i++){
bigQ.put((char) ('A' + i));
}
// retrieve and display elements from bigQ
System.out.print("Contents of bigQ: ");
for(i = 0; i < 26; i++){
ch = bigQ.get();
if(ch != (char) 0)
System.out.print(ch);
}
System.out.println("\n");
System.out.println("Using smallQ to generate errors.");
// Now, use smallQ to generate some errors
for(i = 0; i < 5; i++){
System.out.print("Attempting to store " + (char) ('Z' - i));
smallQ.put((char) ('Z' - i));
System.out.println();
}
System.out.println();
System.out.print("Contents of smallQ: ");
// more errors on smallQ
for(i = 0; i < 5; i++){
ch = smallQ.get();
if(ch != (char) 0)
System.out.print(ch);
}
}
}
【练习5-3(ShowBitsDemo.java)】ShowBits类
本练习创建了一个名为ShowBits的类，它可以用二进制形式显示任何整数的二进制值。这样的类在程序设计中十分有用。例如，如果正在调试设备驱动代码，那么对二进制的数据流进行监视通常是很有益的。
package javaone.a.beginners.guide.chapterfive;
/*
Try This 5-3
A class that display the binary representarion of a value.
*/
class ShowBits{
int numbits;
ShowBits(int n){
numbits = n;
}
void show(long val){
long mask = 1;
// left-shift a 1 into the proper position
mask <<= numbits-1;
int spacer = 0;
for(; mask != 0; mask >>>= 1){
if((val & mask) != 0){
System.out.print("1");
}else{
System.out.print("0");
}
spacer++;
if((spacer % 8) == 0){
System.out.print(" ");
spacer = 0;
}
}
System.out.println();
}
}
// Demonstrate ShowBits
public class ChapterFiveExampleTwentyEight {
public static void main(String[] args) {
ShowBits b = new ShowBits(8);
ShowBits i = new ShowBits(32);
ShowBits li = new ShowBits(64);
System.out.println("123 in binary: ");
b.show(123);
System.out.println("\n87987 in binary: ");
i.show(87987);
System.out.println("\n237658768 in binary: ");
li.show(237658768);
// you can also show low-order bits of any integer
System.out.println("\nLow order 8 bits of 87987 in binary: ");
b.show(87987);
}
}
5.12 自测题
1. 写出两种声明包含12个double类型的值的一维数组的方式。
答案：
double x[] = new double[12];
double[] x = new double[12];
2. 说明如何把一维整数数组初始化为值1~5.。
答案：
int x[] = {1, 2, 3, 4, 5};
3. 编写一个使用数组来查找10个double值的平均数的程序，10个值任选。
package javaone.a.beginners.guide.chapterfive;
public class ChapterFiveExerciseThree {
public static void main(String[] args) {
double nums[] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.1 };
double sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
System.out.println("Average: " + sum / nums.length);
}
}
4. 修改练习5-1中的排序，使其对一个字符串数组进行排序。请证实其可以运行。
package javaone.a.beginners.guide.chapterfive;
// Demonstrate the Bubble sort with strings.
public class ChapterFiveExerciseFour {
public static void main(String[] args) {
String strs[] = { "this", "is", "a", "test", "of", "a", "string", "sort" };
int a, b;
String t;
int size;
size = strs.length; // number of elements to sort
// display original array
System.out.print("Original array is: ");
for (int i = 0; i < size; i++) {
System.out.print(" " + strs[i]);
}
System.out.println();
// This is bubble sort for strings.
for(a=1;a<size;a++) {
for(b=size-1;b>=a;b--){
if(strs[b-1].compareTo(strs[b]) > 0){ // if out of order
// exchange elements
t = strs[b-1];
strs[b-1] = strs[b];
strs[b] = t;
}
}
}
// display sorted array
System.out.print("Sort array is: ");
for (int i = 0; i < size; i++) {
System.out.print(" " + strs[i]);
}
System.out.println();
}
}
5. String类的indexOf()和lastIndexOf()方法之间的不同之处是什么?
答案： indexOf()方法找到第一次出现的指定子串；lastIndexOf()方法找到最后一次出现的指定子串。
6. 所有字符串都是String类型的对象，请写出如何在字符串字面值"I like Java"上调用length()和chaAt()方法。
答案：
package javaone.a.beginners.guide.chapterfive;
public class ChapterFiveExerciseSix {
public static void main(String[] args) {
System.out.println("I like Java".length());
System.out.println("I like Java".charAt(0));
}
}
7. 扩展Encode加密类，修改它以使其使用包含8个字符的字符串作为密钥。
package javaone.a.beginners.guide.chapterfive;
// An improved XOR cipher.
public class ChapterFiveExerciseSeven {
public static void main(String[] args) {
String msg = "This is a test";
String encmsg = "";
String decmsg = "";
String key = "abcdefgi";
int j;
System.out.print("Original message: ");
System.out.println(msg);
// encode the message
j = 0;
for (int i = 0; i < msg.length(); i++) {
encmsg = encmsg + (char) (msg.charAt(i) ^ key.charAt(j));
j++;
if(j==8){
j = 0;
}
}
System.out.print("Encoded message: ");
System.out.println(encmsg);
// decode the message
j = 0;
for (int i = 0; i < msg.length(); i++) {
decmsg = decmsg + (char) (encmsg.charAt(i) ^ key.charAt(j));
j++;
if(j==8){
j = 0;
}
}
System.out.print("Decoded message: ");
System.out.println(decmsg);
}
}
8. 位运算可以应用于double类型吗?
答案：不能，位运算符可以运用于long、int、short、char或byte类型，不能用于boolean、float、double或类类型。
9. 请用?运算符来重写下面的代码:
if(x<0) y = 10;
else y = 20;
答案：x < 0 ? 10 : 20;
10. 在下面的代码段中，&是位运算符还是逻辑运算符呢?请给出你的理由。
boolean a, b;
//...
if(a & b) ...
答案：是逻辑运算符，因为操作数是boolean类型。
11. 溢出数组边界是错误吗?用负值编制数组索引正确吗?
答案：溢出数组边界是错误的，用负值编制数组索引也是错误的，所有数组索引都从0开始。
12. 什么是无符号右移运算符?
答案：>>>，如果右移时，不想保持符号位，可使用无符号右移(>>>)，它总是在左端补一个0。出于这个原因，>>>也称为充零右移。在移动不代表整数的二进制位(如状态码)时可以使用无符号右移。
13. 重写本章前面的MinMax类，以便使用for-each形式的for循环。
package javaone.a.beginners.guide.chapterfive;
// Find the minimum and maximum values in an array
public class ChapterFiveExerciseThirteen {
public static void main(String[] args) {
int nums[] = new int[10];
int min, max;
nums[0] = 9;
nums[1] = -10;
nums[2] = 100123;
nums[3] = 18;
nums[4] = -978;
nums[5] = 5623;
nums[6] = 463;
nums[7] = -9;
nums[8] = 278;
nums[9] = 49;
min = max = nums[0];
for(int v : nums){
if(v < min) min = v;
if(v > max) max = v;
}
System.out.println("min and max: " + min + " " + max);
}
}
14. 练习5-1提供的Bubble类中执行排序的for循环能够转换为for-each形式的for循环吗?如果不能，为什么?
答案： 不可以，进行排序的Bubble类中的for循环不能转换成for-each循环。对于外层循环，循环计数器的当前值会在内层循环中用到。而对于内层循环，顺序不正确的值需要被交换，这意味着需要使用赋值操作。使用for-each循环时，不能对底层的数组进行赋值。
15. 可以使用String控制switch语句吗?
答案： 从JDK 7开始，答案是肯定的。