日撸 Java 三百行（11-20天，线性数据结构）

第 11 天: 顺序表（一）

在《数据结构》中, 使用“抽象数据类型”来描述不同的数据结构. 在《面向对象程序设计》中, 用对象来存储数据及其上的操作. 我认为, 它们的本质都是相同的.
11.1 对象: 数据及其上操作的总和. 例如, 我是一个对象, 具有身高、体重、年龄、跑步速度等数据; 同时，我具有吃饭、睡觉、送快递等功能. 从计算机的发展来看, 第一阶段以操作 (函数) 为中心, 一个计算导弹轨迹的函数, 根据不同输入获得不同输出. 第二阶段以数据为中心, 即数据存放于数据库, 使用不同的算法来处理它. 第三阶段认为数据及其上的操作是统一不可分的, 这就到了面向对象.
11.2 类. 前面已经使用过 int i; 这类代码, int 就是类型, i 是一个具体的整数变量. 同理, 对象就是属于某种类的变量. 也可以用集合的方式来理解: 类是集合, 对象是其中的元素; int 是指所有整数的集合, i 是其中的一个元素.
11.3 包. 包并非程序设计必须的东西, 其作用仅仅是将类进行合理的组织. 但是, 在计算机界, 往往这种可有可无的东西才是最重要的. 如文档、注释、编码规范. 可有可无是针对程序的运行而言, 其核心是计算机; 而重要是针对程序的易读性、可维护性而言, 其核心是程序员.
11.4 常量用 final 修饰. 这里故意把 MAX_LENGTH 设置得比较少, 方便调拭后面的越界检查代码.
11.5 用 new 生成新的对象.
11.6 有一个成员变量叫做 length. 程序里还有用 length 表示一个整数数组的长度. 实际上, 同一个变量名可以被不同的类所使用, 例如: 人有体重, 西瓜也有重量. 由于限定了不同的类、不同的对象, 它们之间就不会有冲突. 张三的体重、李四的体重，有关联才奇怪了. 这段描述写出来怪怪的, 明明现实生活中就是如此. 但这也正是体现了面向对象的特点: 比面向过程的程序设计更贴合我们的人类认知, 也就更远离机器底层.
11.7 toString 这个方法很特殊, 它覆盖了 Object 类的相应方法. 可以看到, 在 println 里面使用 tempFirstList 里, 由于是用另一个字符串与其相加, 系统会自动调用 ().

package ;

/**
 * Sequential list.
 * 
 * @author Fan Min minfanphd@.
 */
public class SequentialList {

	/**
	 * The maximal length of the list. It is a constant.
	 */
	public static final int MAX_LENGTH = 10;

	/**
	 * The actual length not exceeding MAX_LENGTH. Attention: length is not only
	 * the member variable of Sequential list, but also the member variable of
	 * Array. In fact, a name can be the member variable of different classes.
	 */
	int length;

	/**
	 * The data stored in an array.
	 */
	int[] data;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public SequentialList() {
		length = 0;
		data = new int[MAX_LENGTH];
	}// Of the first constructor

	/**
	 *********************
	 * Construct a sequential list using an array.
	 * 
	 * @param paraArray
	 *            The given array. Its length should not exceed MAX_LENGTH. For
	 *            simplicity now we do not check it.
	 *********************
	 */
	public SequentialList(int[] paraArray) {
		data = new int[MAX_LENGTH];
		length = ;

		// Copy data.
		for (int i = 0; i < ; i++) {
			data[i] = paraArray[i];
		} // Of for i
	}// Of the second constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (length == 0) {
			return "empty";
		} // Of if

		for (int i = 0; i < length - 1; i++) {
			resultString += data[i] + ", ";
		} // Of for i

		resultString += data[length - 1];

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty.
	 *********************
	 */
	public void reset() {
		length = 0;
	}// Of reset

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int[] tempArray = { 1, 4, 6, 9 };
		SequentialList tempFirstList = new SequentialList(tempArray);
		("Initialized, the list is: " + ());
		("Again, the list is: " + tempFirstList);

		();
		("After reset, the list is: " + tempFirstList);
	}// Of main

}// Of class SequentialList

第 12 天: 顺序表（二）

今天的代码直接在昨天的基础上增加. 只贴出新的部分.
12.1 查找给定元素所处的位置. 找不到就返回 -1.
12.2 在给定位置增加元素. 如果线性表已满, 或位置不在已有位置范围之内, 就拒绝增加. 该位置可以是在最后一个元素之后一个.
12.3 删除定定位置的元素. 要处理给定位置不合法的情况. 该位置必须是已经有数据的.
12.4 函数要求同样的输入参数获得同样的输出结果, 但方法所依赖的数据既包括参数列表中给出的，也依赖于对象的成员变量. 因此, 面向对象所涉及的参数列表要短些. 例如, locate 方法就有效利用了 length 和 data 这两个成员变量.

   /**
    *********************
    * Find the index of the given value. If it appears in multiple positions,
    * simply return the first one.
    * 
    * @param paraValue The given value.
    * @return The position. -1 for not found.
    *********************
    */
   public int indexOf(int paraValue) {
   	int tempPosition = -1;

   	for (int i = 0; i < length; i++) {
   		if (data[i] == paraValue) {
   			tempPosition = i;
   			break;
   		} // Of if
   	} // Of for i

   	return tempPosition;
   }// Of indexOf

   /**
    *********************
    * Insert a value to a position. If the list is already full, do nothing.
    * 
    * @param paraPosition The given position.
    * @param paraValue    The given value.
    * @return Success or not.
    *********************
    */
   public boolean insert(int paraPosition, int paraValue) {
   	if (length == MAX_LENGTH) {
   		("List full.");
   		return false;
   	} // Of if

   	if ((paraPosition < 0) || (paraPosition > length)) {
   		("The position " + paraPosition + " is out of bounds.");
   		return false;
   	} // Of if

   	// From tail to head. The last one is moved to a new position. Because length < MAX_LENGTH, no exceeding occurs.
   	for (int i = length; i > paraPosition; i--) {
   		data[i] = data[i - 1];
   	} // Of for i

   	data[paraPosition] = paraValue;
   	length++;

   	return true;
   }// Of insert

   /**
    *********************
    * Delete a value at a position.
    * 
    * @param paraPosition The given position.
    * @return Success or not.
    *********************
    */
   public boolean delete(int paraPosition) {
   	if ((paraPosition < 0) || (paraPosition >= length)) {
   		("The position " + paraPosition + " is out of bounds.");
   		return false;
   	} // Of if

   	// From head to tail.
   	for (int i = paraPosition; i < length - 1; i++) {
   		data[i] = data[i + 1];
   	} // Of for i

   	length--;

   	return true;
   }// Of delete

   /**
    *********************
    * The entrance of the program.
    * 
    * @param args Not used now.
    *********************
    */
   public static void main(String args[]) {
   	int[] tempArray = { 1, 4, 6, 9 };
   	SequentialList tempFirstList = new SequentialList(tempArray);
   	("After initialization, the list is: " + ());
   	("Again, the list is: " + tempFirstList);

   	int tempValue = 4;
   	int tempPosition = (tempValue);
   	("The position of " + tempValue + " is " + tempPosition);

   	tempValue = 5;
   	tempPosition = (tempValue);
   	("The position of " + tempValue + " is " + tempPosition);

   	tempPosition = 2;
   	tempValue = 5;
   	(tempPosition, tempValue);
   	(
   			"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);

   	tempPosition = 8;
   	tempValue = 10;
   	(tempPosition, tempValue);
   	(
   			"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);

   	tempPosition = 3;
   	(tempPosition);
   	("After deleting data at position " + tempPosition + ", the list is: " + tempFirstList);

   	for (int i = 0; i < 8; i++) {
   		(i, i);
   		("After inserting " + i + " to position " + i + ", the list is: " + tempFirstList);
   	} // Of for i

   	();
   	("After reset, the list is: " + tempFirstList);
   }// Of main

第 13 天: 链表

13.1 支持与顺序表相同的操作: 初始化、插入、删除等.
13.2 为节点建一个类.
13.3 引用与指针的异同. 前者只能使用; 后者可以支持 p ++ 危险操作.
13.4 引用数据类型的赋值, 都不会产生新的对象空间.
13.5 链表与线性表在插入、删除时的不同: 前者不移动元素, 只改变引用 (指针).
13.6 今天的代码稍微多一点, 不过有昨天的铺垫, 还好.
13.7 第一个版本中, 128 和 164 行的 if 语句中都少了一个 .next, 导致对最后一个位置的检查出错 (空指针异常). 本 bug 由许嘉欣同学找到并修复.

package datastructure;

/**
 * Linked list.
 * 
 * @author Fan Min minfanphd@.
 */

public class LinkedList {

	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor
		 * 
		 * @param paraValue
		 *            The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

	/**
	 * The header node. The data is never used.
	 */
	Node header;

	/**
	 *********************
	 * Construct an empty linked list.
	 *********************
	 */
	public LinkedList() {
		header = new Node(0);
		// = null; //Redundant
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if ( == null) {
			return "empty";
		} // Of if

		Node tempNode = ;
		while (tempNode != null) {
			resultString +=  + ", ";
			tempNode = ;
		} // Of while

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty. Free the space through garbage collection.
	 *********************
	 */
	public void reset() {
		 = null;
	}// Of reset

	/**
	 *********************
	 * Locate the given value. If it appears in multiple positions, simply
	 * return the first one.
	 * 
	 * @param paraValue
	 *            The given value.
	 * @return The position. -1 for not found.
	 *********************
	 */
	public int locate(int paraValue) {
		int tempPosition = -1;

		Node tempNode = ;
		int tempCurrentPosition = 0;
		while (tempNode != null) {
			if ( == paraValue) {
				tempPosition = tempCurrentPosition;
				break;
			} // Of if

			tempNode = ;
			tempCurrentPosition++;
		} // Of while

		return tempPosition;
	}// Of locate

	/**
	 *********************
	 * Insert a value to a position. If the list is already full, do nothing.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @param paraValue
	 *            The given value.
	 * @return Success or not.
	 *********************
	 */
	public boolean insert(int paraPosition, int paraValue) {
		Node tempNode = header;
		Node tempNewNode;

		for (int i = 0; i < paraPosition; i++) {
			if ( == null) {
				("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = ;
		} // Of for i

		// Construct a new node.
		tempNewNode = new Node(paraValue);

		// Now link them.
		 = ;
		 = tempNewNode;

		return true;
	}// Of insert

	/**
	 *********************
	 * Delete a value at a position.
	 * 
	 * @param paraPosition
	 *            The given position.
	 * @return Success or not.
	 *********************
	 */
	public boolean delete(int paraPosition) {
		if ( == null) {
			("Cannot delete element from an empty list.");
			return false;
		} // Of if

		Node tempNode = header;

		for (int i = 0; i < paraPosition; i++) {
			if ( == null) {
				("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = ;
		} // Of for i

		 = ;

		return true;
	}// Of delete

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedList tempFirstList = new LinkedList();
		("Initialized, the list is: " + ());

		for (int i = 0; i < 5; i++) {
			(0, i);
		} // Of for i
		("Inserted, the list is: " + ());

		(6, 9);

		(4);

		(2);
		("Deleted, the list is: " + ());

		(0);
		("Deleted, the list is: " + ());

		for (int i = 0; i < 5; i++) {
			(0);
			("Looped delete, the list is: " + ());
		} // Of for i
	}// Of main
}// Of class LinkedList

第 14 天: 栈

14.1 push 和 pop 均只能在栈顶操作.
14.2 没有循环, 时间复杂度为 $O (1)$ .

package ;

/**
 * Char stack. I do not use Stack because it is already defined in Java.
 * 
 * @author Fan Min minfanphd@.
 */
public class CharStack {
	/**
	 * The depth.
	 */
	public static final int MAX_DEPTH = 10;

	/**
	 * The actual depth.
	 */
	int depth;

	/**
	 * The data
	 */
	char[] data;

	/**
	 *********************
	 * Construct an empty char stack.
	 *********************
	 */
	public CharStack() {
		depth = 0;
		data = new char[MAX_DEPTH];
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";
		for (int i = 0; i < depth; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Push an element.
	 * 
	 * @param paraChar The given char.
	 * @return Success or not.
	 *********************
	 */
	public boolean push(char paraChar) {
		if (depth == MAX_DEPTH) {
			("Stack full.");
			return false;
		} // Of if

		data[depth] = paraChar;
		depth++;

		return true;
	}// Of push

	/**
	 *********************
	 * Pop an element.
	 * 
	 * @return The popped char.
	 *********************
	 */
	public char pop() {
		if (depth == 0) {
			("Nothing to pop.");
			return '\0';
		} // Of if

		char resultChar = data[depth - 1];
		depth--;

		return resultChar;
	}// Of pop

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CharStack tempStack = new CharStack();

		for (char ch = 'a'; ch < 'm'; ch++) {
			(ch);
			("The current stack is: " + tempStack);
		} // Of for ch

		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = ();
			("Poped: " + tempChar);
			("The current stack is: " + tempStack);
		} // Of for i
	}// Of main
}// Of CharStack

第 15 天: 栈的应用（括号匹配）

任务描述: 检查一个字符串的括号是否匹配. 所谓匹配, 是指每个左括号有相应的一个右括号与之对应, 且左括号不可以出现在右括号右边. 可以修改测试字符串, 检查不同情况下的运行.
15.1 仅在昨天的代码基础上增加了一个 bracketMatching 方法, 以及 main 中的相应调拭语句.
15.2 操作系统的核心数据结构. 对于计算机而言, 如何降低时间、空间复杂度才是王道.
15.3 除了关注的括号, 其它字符不起任何作用.
15.4 一旦发现不匹配, 就直接返回, 不用罗嗦.

	/**
	 *********************
	 * Is the bracket matching?
	 * 
	 * @param paraString
	 *            The given expression.
	 * @return Match or not.
	 *********************
	 */
	public static boolean bracketMatching(String paraString) {
		// Step 1. Initialize the stack through pushing a '#' at the bottom.
		CharStack tempStack = new CharStack();
		('#');
		char tempChar, tempPopedChar;

		// Step 2. Process the string. For a string, length() is a method
		// instead of a member variable.
		for (int i = 0; i < (); i++) {
			tempChar = (i);

			switch (tempChar) {
			case '(':
			case '[':
			case '{':
				(tempChar);
				break;
			case ')':
				tempPopedChar = ();
				if (tempPopedChar != '(') {
					return false;
				} // Of if
				break;
			case ']':
				tempPopedChar = ();
				if (tempPopedChar != '[') {
					return false;
				} // Of if
				break;
			case '}':
				tempPopedChar = ();
				if (tempPopedChar != '{') {
					return false;
				} // Of if
				break;
			default:
				// Do nothing.
			}// Of switch
		} // Of for

		tempPopedChar = ();
		if (tempPopedChar != '#') {
			return false;
		} // Of if

		return true;
	}// Of bracketMatching

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CharStack tempStack = new CharStack();

		for (char ch = 'a'; ch < 'm'; ch++) {
			(ch);
			("The current stack is: " + tempStack);
		} // Of for i

		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = ();
			("Poped: " + tempChar);
			("The current stack is: " + tempStack);
		} // Of for i

		boolean tempMatch;
		String tempExpression = "[2 + (1 - 3)] * 4";
		tempMatch = bracketMatching(tempExpression);
		
				.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "( )  )";
		tempMatch = bracketMatching(tempExpression);
		
				.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "()()(())";
		tempMatch = bracketMatching(tempExpression);
		
				.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = "({}[])";
		tempMatch = bracketMatching(tempExpression);
		
				.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);

		tempExpression = ")(";
		tempMatch = bracketMatching(tempExpression);
		
				.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
	}// Of main

第 16 天: 递归

16.1 递归这个东东, 能理解的同学秒懂, 理解不了的就简直没任何办法.
16.2 数学式子写出来了, 直接翻译成程序, 简单方便.
16.3 系统会为递归建栈, 这个需要理解一下. 例如, 累加程序, 空间复杂度是 $O (n)$ , 因为只有运行到 paraN = 1 时, 才会弹栈.
16.4 Hanoi 问题虽然很有名, 但它更多的是对形参/实参的理解, 所以不写在这里给读者添堵. 再说了, 那种极端的例子也不具有代表性.

package datastructure;

/**
 * Recursion. A method can (directly or indirectly) invoke itself. The system
 * automatically creates a stack for it.
 * 
 * @author Fan Min minfanphd@.
 */
public class Recursion {
	/**
	 *********************
	 * Sum to N. No loop, however a stack is used.
	 * 
	 * @param paraN
	 *            The given value.
	 * @return The sum.
	 *********************
	 */
	public static int sumToN(int paraN) {
		if (paraN <= 0) {
			//Basis.
			return 0;
		} // Of if

		return sumToN(paraN - 1) + paraN;
	}// Of sumToN

	/**
	 *********************
	 * Fibonacci sequence.
	 * 
	 * @param paraN
	 *            The given value.
	 * @return The sum.
	 *********************
	 */
	public static int fibonacci(int paraN) {
		if (paraN <= 0) {
			//Negative values are invalid. Index 0 corresponds to the first element 0.
			return 0;
		} if (paraN == 1) {
			//Basis.
			return 1;
		}//Of if
		
		return fibonacci(paraN - 1) + fibonacci(paraN - 2);
	}//Of fibonacci
	
	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int tempValue = 5;
		("0 sum to " + tempValue + " = " + sumToN(tempValue));
		tempValue = -1;
		("0 sum to " + tempValue + " = " + sumToN(tempValue));
		
		for(int i = 0; i < 10; i ++) {
			("Fibonacci " + i + ": " + fibonacci(i));
		}//Of for i
	}// Of main
}// Of class Recursion

第 17 天: 链队列

17.1 链队列比较容易写.
17.2 Node 类以前是 LinkdedList 的内嵌类, 这里重写了一遍. 访问控制的事情以后再说.
17.3 为方便操作, 空队列也需要一个节点. 这和以前的链表同理. 头节点的引用 (指针) 称为 header.
17.4 入队仅操作尾部, 出队仅操作头部.

package ;

/**
 * Linked queue.
 * 
 * @author Fan Min minfanphd@.
 */
public class LinkedQueue {

	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor.
		 * 
		 * @param paraValue The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

	/**
	 * The header of the queue.
	 */
	Node header;

	/**
	 * The tail of the queue.
	 */
	Node tail;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public LinkedQueue() {
		header = new Node(-1);
		//  = null;

		tail = header;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(int paraValue) {
		Node tempNode = new Node(paraValue);
		 = tempNode;
		tail = tempNode;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the header.
	 *********************
	 */
	public int dequeue() {
		if (header == tail) {
			("No element in the queue");
			return -1;
		} // Of if

		int resultValue = ;

		 = ;

		// The queue becomes empty.
		if ( == null) {
			tail = header;
		} // Of if

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if ( == null) {
			return "empty";
		} // Of if

		Node tempNode = ;
		while (tempNode != null) {
			resultString +=  + ", ";
			tempNode = ;
		} // Of while

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedQueue tempQueue = new LinkedQueue();
		("Initialized, the list is: " + ());

		for (int i = 0; i < 5; i++) {
			(i + 1);
		} // Of for i
		("Enqueue, the queue is: " + ());

		();
		("Dequeue, the queue is: " + ());

		int tempValue;
		for (int i = 0; i < 5; i++) {
			tempValue = ();
			("Looped delete " + tempValue + ", the new queue is: " + ());
		} // Of for i

		for (int i = 0; i < 3; i++) {
			(i + 10);
		} // Of for i
		("Enqueue, the queue is: " + ());
	}// Of main
}// Of class LinkedQueue

第 18 天: 循环队列

18.1 整除的作用.
18.2 想像操场跑道里放一队人, 循环的感觉就出来了.
18.3 为了区分空队列与满队列, 需要留一个空间. 相当于不允许首尾相连. 还是画个图吧, 否则容易进坑.
18.4 用链式结构, 空间的分配与回收由系统做, 用循环队列, 则是自己把控. 想像自己写的是操作系统, 从这个代码可以感受下内存的管理.

package ;

/**
 * Circle int queue.
 * 
 * @author Fan Min minfanphd@.
 */
public class CircleIntQueue {

	/**
	 * The total space. One space can never be used.
	 */
	public static final int TOTAL_SPACE = 10;

	/**
	 * The data.
	 */
	int[] data;

	/**
	 * The index for calculating the head. The actual head is head % TOTAL_SPACE.
	 */
	int head;

	/**
	 * The index for calculating the tail.
	 */
	int tail;

	/**
	 ******************* 
	 * The constructor
	 ******************* 
	 */
	public CircleIntQueue() {
		data = new int[TOTAL_SPACE];
		head = 0;
		tail = 0;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(int paraValue) {
		if ((tail + 1) % TOTAL_SPACE == head) {
			("Queue full.");
			return;
		} // Of if

		data[tail % TOTAL_SPACE] = paraValue;
		tail++;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the head.
	 *********************
	 */
	public int dequeue() {
		if (head == tail) {
			("No element in the queue");
			return -1;
		} // Of if

		int resultValue = data[head % TOTAL_SPACE];

		head++;

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (head == tail) {
			return "empty";
		} // Of if

		for (int i = head; i < tail; i++) {
			resultString += data[i % TOTAL_SPACE] + ", ";
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CircleIntQueue tempQueue = new CircleIntQueue();
		("Initialized, the list is: " + ());

		for (int i = 0; i < 5; i++) {
			(i + 1);
		} // Of for i
		("Enqueue, the queue is: " + ());

		int tempValue = ();
		("Dequeue " + tempValue + ", the queue is: " + ());

		for (int i = 0; i < 6; i++) {
			(i + 10);
			("Enqueue, the queue is: " + ());
		} // Of for i

		for (int i = 0; i < 3; i++) {
			tempValue = ();
			("Dequeue " + tempValue + ", the queue is: " + ());
		} // Of for i

		for (int i = 0; i < 6; i++) {
			(i + 100);
			("Enqueue, the queue is: " + ());
		} // Of for i
	}// Of main

}// Of CircleIntQueue

由于后面还要用到字符队列, 就把上面这个程序中的 int 改成 char, 并作相应调整, 获得如下程序.

package ;

/**
 * Circle queue.
 * 
 * @author Fan Min minfanphd@.
 */
public class CircleCharQueue {

	/**
	 * The total space. One space can never be used.
	 */
	public static final int TOTAL_SPACE = 10;

	/**
	 * The data.
	 */
	char[] data;

	/**
	 * The index for calculating the head. The actual head is head % TOTAL_SPACE.
	 */
	int head;

	/**
	 * The index for calculating the tail.
	 */
	int tail;

	/**
	 ******************* 
	 * The constructor
	 ******************* 
	 */
	public CircleCharQueue() {
		data = new char[TOTAL_SPACE];
		head = 0;
		tail = 0;
	}// Of the first constructor

	/**
	 *********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 *********************
	 */
	public void enqueue(char paraValue) {
		if ((tail + 1) % TOTAL_SPACE == head) {
			("Queue full.");
			return;
		} // Of if

		data[tail % TOTAL_SPACE] = paraValue;
		tail++;
	}// Of enqueue

	/**
	 *********************
	 * Dequeue.
	 * 
	 * @return The value at the head.
	 *********************
	 */
	public char dequeue() {
		if (head == tail) {
			("No element in the queue");
			return '\0';
		} // Of if

		char resultValue = data[head % TOTAL_SPACE];

		head++;

		return resultValue;
	}// Of dequeue

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		if (head == tail) {
			return "empty";
		} // Of if

		for (int i = head; i < tail; i++) {
			resultString += data[i % TOTAL_SPACE] + ", ";
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CircleCharQueue tempQueue = new CircleCharQueue();
		("Initialized, the list is: " + ());

		for (char i = '0'; i < '5'; i++) {
			(i);
		} // Of for i
		("Enqueue, the queue is: " + ());

		char tempValue = ();
		("Dequeue " + tempValue + ", the queue is: " + ());

		for (char i = 'a'; i < 'f'; i++) {
			(i);
			("Enqueue, the queue is: " + ());
		} // Of for i

		for (int i = 0; i < 3; i++) {
			tempValue = ();
			("Dequeue " + tempValue + ", the queue is: " + ());
		} // Of for i

		for (char i = 'A'; i < 'F'; i++) {
			(i);
			("Enqueue, the queue is: " + ());
		} // Of for i
	}// Of main

}// Of CircleCharQueue

第 19 天: 字符串匹配

19.1 String 是 Java 常用的类, 这里重新实现下部分功能.
19.2 转义符 , 有了它才能正常打印引号.
19.3 简单的越界检查.

package datastructure;

/**
 * My string. String is a class provided by the language, so I use another name.
 * It is essentially a sequential list with char type elements.
 * 
 * @author Fan Min minfanphd@.
 */

public class MyString {
	/**
	 * The maximal length.
	 */
	public static final int MAX_LENGTH = 10;

	/**
	 * The actual length.
	 */
	int length;

	/**
	 * The data.
	 */
	char[] data;

	/**
	 *********************
	 * Construct an empty char array.
	 *********************
	 */
	public MyString() {
		length = 0;
		data = new char[MAX_LENGTH];
	}// Of the first constructor

	/**
	 *********************
	 * Construct using a system defined string.
	 * 
	 * @param paraString
	 *            The given string. Its length should not exceed MAX_LENGTH - 1.
	 *********************
	 */
	public MyString(String paraString) {
		data = new char[MAX_LENGTH];
		length = ();

		// Copy data.
		for (int i = 0; i < length; i++) {
			data[i] = (i);
		} // Of for i
	}// Of the second constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "";

		for (int i = 0; i < length; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Locate the position of a substring.
	 * 
	 * @param paraString
	 *            The given substring.
	 * @return The first position. -1 for no matching.
	 *********************
	 */
	public int locate(MyString paraMyString) {
		boolean tempMatch = false;
		for (int i = 0; i < length -  + 1; i++) {
			// Initialize.
			tempMatch = true;
			for (int j = 0; j < ; j++) {
				if (data[i + j] != [j]) {
					tempMatch = false;
					break;
				} // Of if
			} // Of for j

			if (tempMatch) {
				return i;
			} // Of if
		} // Of for i
		return -1;
	}// Of locate

	/**
	 *********************
	 * Get a substring
	 * 
	 * @param paraString
	 *            The given substring.
	 * @param paraStartPosition
	 *            The start position in the original string.
	 * @param paraLength
	 *            The length of the new string.
	 * @return The first position. -1 for no matching.
	 *********************
	 */
	public MyString substring(int paraStartPosition, int paraLength) {
		if (paraStartPosition + paraLength > length) {
			("The bound is exceeded.");
			return null;
		} // Of if

		MyString resultMyString = new MyString();
		 = paraLength;
		for (int i = 0; i < paraLength; i++) {
			[i] = data[paraStartPosition + i];
		} // Of for i

		return resultMyString;
	}// Of substring

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		MyString tempFirstString = new MyString("I like ik.");
		MyString tempSecondString = new MyString("ik");
		int tempPosition = (tempSecondString);
		("The position of \"" + tempSecondString + "\" in \"" + tempFirstString
				+ "\" is: " + tempPosition);

		MyString tempThirdString = new MyString("ki");
		tempPosition = (tempThirdString);
		("The position of \"" + tempThirdString + "\" in \"" + tempFirstString
				+ "\" is: " + tempPosition);

		tempThirdString = (1, 2);
		("The substring is: \"" + tempThirdString + "\"");

		tempThirdString = (5, 5);
		("The substring is: \"" + tempThirdString + "\"");

		tempThirdString = (5, 6);
		("The substring is: \"" + tempThirdString + "\"");
	}// Of main
}// Of class MyString

第 20 天: 小结

实在想不出如何布置任务, 我来出几道题吧. 不用去查阅别人的观点, 根据这几天写程序的来体会来回答.

面向对象与面向过程相比, 有哪些优势? 注: 第 1 - 10 天的程序, 就是面向过程的.
比较顺序表和链表的异同.
分析顺序表和链表的优缺点.
分析调拭程序常见的问题及解决方案.
分析链队列与循环队列的优缺点.
第 18 天建立的两个队列, 其区别仅在于基础数据不同, 一个是 int, 一个是 char. 按这种思路, 对于不同的基础数据类型, 都需要重写一个类, 这样合理吗? 你想怎么样?

秒客网