日撸代码300行の学习笔记2：线性数据结构
- 前言
- day11 顺序表
- day12 链表
- day13 ArrayList的学习
- day14 LinkedList的学习
- day15 栈
- day16 栈：括号匹配
- day17 栈：递归
- day18 链队列
- day19 循环队列
- day20 字符串匹配
前言
本文是关于日撸代码300行 link的学习笔记。
打个1折，每日代码30行。
本文对所学习的代码根据自己的理解有所调整。
本文的代码只是个人笔记，有些笔记比较跳跃。
仿敲优秀代码果然是最快的编程学习方式。
day11 顺序表
在《数据结构》中，使用“抽象数据类型”来描述不同的数据结构；在《面向对象程序设计》中，用对象来存储数据及其上的操作；它们的本质是共通的。
对象：数据及其上操作的总和。
从计算机的发展来看，第一阶段以操作 (函数) 为中心，比如一个计算导弹轨迹的函数，根据不同输入获得不同输出。第二阶段以数据为中心，即数据存放于数据库，使用不同的算法来处理它。第三阶段认为数据及其上的操作是统一不可分的，这就到了面向对象。
包 并非程序设计必须的东西，其作用仅仅是将类进行合理的组织。但在计算机界，往往这种 可有可无 的东西才是最重要的，比如如文档、注释、编码规范。可有可无 是针对程序的运行而言，其核心是计算机；而重要是针对程序的易读性、可维护性而言，其核心是程序员。
啰嗦一下基础知识：数组的初始化，1静态初始化：int[] a={1,2,3}。2动态初始化： int[] b=new int[2]; b[0]=1; b[2]=2;。3默认初始化。八种基本数据类型的数组的默认初始化的各元素值：
byte[] 0；int[] 0；short[] 0；long[] 0；double[] 0.0；float[] 0.0；boolean[] false；char[] ‘\u0000’，\u0000是Unicode中的一个占位符，char[]的默认值可以理解为一个空格。
单独提一句，对于String[]，数组的每个元素是String类的对象，即每个元素也是对数据的引用（数组变量肯定是引用，即对真实数据的管理者，如String[] a = new String[3]，int[] b = new int[3]，则a、b分别引用了String数组、int数组，但a[i]是引用了某字符串，而b[i]就是某个int），所以默认初始化不是 “”，而是 null。
再啰嗦一句，数组变量间的比较是判断是否管理着同一数组，而不是判断数组内元素值是否相等，如int[] a ={1,2,3}；int[] b ={1,2,3}；System.out.println(a==b)；结果是false。数组变量的赋值只能赋予管理/引用权限，不能复制一个值相等的全新数组。
因此复制数组，需要遍历“源数组”将每个元素逐一复制给“目的数组”。
同样的，若要判断两个数组的元素是否相等，不能直接对数组变量进行“ == ”判断，而是写循环对所有元素逐个判断。
本小节将原作者前两部分融合为一节，给出完整的顺序表。该顺序表是用数组来实现的，即给出一个固定大小的数组，用该数组的一部分来表示我们需要的线性表。该节的SequentialList类重写了toString方法方便进行测试，并给出了线性表的如下基础功能：
- 构造初始化。包括2种，一种是默认初始化，一种是根据作为参数的给定数组完成初始化；
- 重置线性表，将实际数组长度重置为0；
- 查找给定元素所处的位置，找不到就返回 -1；
- 在给定位置增加元素。如果线性表已满，或位置不在已有位置范围之内，就拒绝增加。但注意，该位置可以是在最后一个元素之后的一个；
- 删除定定位置的元素。注意要处理给定位置不合法的情况，该位置必须是已经有数据的。
下面给出框架：
public class SequentialList {
private static final int MAX_LENGTH = 10;
private int length;
private int[] data;
public SequentialList();
public SequentialList(int[] paraArray);
public void reset();
public int locate(int paraValue);
public boolean insert(int paraPosition, int paraValue);
public boolean delete(int paraPosition);
public String toString();
} // of class SequentialList
PS：
method所依赖的数据既包括参数列表中给出的，也依赖于对象的成员变量。因此，面向对象所涉及的参数列表要短些。例如，locate方法就有效利用了 length 和 data 这两个成员变量。
for ( int i = 10; i > 10; i-- ) {…}或for ( int i = length; i < paraLength; i++ ) {…}在paraLength=length时，这样的代码不会报错，也不会运行。
package dataStructure;
/**
* Sequential list. Name and comments follow the author's style strictly.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
public class SequentialList {
/**
* The maximal length of the list. It is a constant.
*/
private 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.
*/
private int length;
/**
* The data stored in an array.
*/
private 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 = paraArray.length;
// Copy data.
for (int i = 0; i < paraArray.length; i++) {
data[i] = paraArray[i];
} // Of for i
} // Of the second constructor
/**
*********************
* Override the method<toString()> 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
/**
*********************
* 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;
for (int i = 0; i < length; i++) {
if (data[i] == paraValue) {
tempPosition = i;
break;
} // Of if
} // Of for i
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) {
if (length == MAX_LENGTH) {
System.out.println("List is full.");
return false;
} // Of if
if ((paraPosition < 0) || (paraPosition > length)) {
System.out.println("The position " + paraPosition + " is out of bounds.");
return false;
} // Of if
// From tail to head.
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 the specified position.
*
* @param paraPosition The given position.
* @return Success or not.
*********************
*/
public boolean delete(int paraPosition) {
if ((paraPosition < 0) || (paraPosition >= length)) {
System.out.println("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 = { 6, 7, 4, 9 };
SequentialList tempFirstList = new SequentialList(tempArray);
System.out.println("After being initialized, the list is: " + tempFirstList.toString());
System.out.println("Without the toString() method, the list also is: " + tempFirstList);
int tempValue = 4;
int tempPosition = tempFirstList.locate(tempValue);
System.out.println("The position of " + tempValue + " is " + tempPosition);
tempValue = 5;
tempPosition = tempFirstList.locate(tempValue);
System.out.println("The position of " + tempValue + " is " + tempPosition + "\n");
tempPosition = 2;
tempValue = 8;
tempFirstList.insert(tempPosition, tempValue);
System.out.println(
"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);
tempPosition = 8;
tempValue = 10;
tempFirstList.insert(tempPosition, tempValue);
System.out.println(
"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);
tempPosition = 3;
tempFirstList.delete(tempPosition);
System.out
.println("After deleting data at position " + tempPosition + ", the list is: " + tempFirstList + "\n");
for (int i = 0; i < 8; i++) {
if (tempFirstList.insert(i, i)) {
System.out.println("After inserting " + i + " to position " + i + ", the list is: " + tempFirstList);
} else {
System.out.println("\t So that we cannot insert "+i+" to position "+i+".");
} // of if
} // Of for i
tempFirstList.reset();
System.out.println("After the reset() method, the list is: " + tempFirstList);
} // of main
} // of class SequentialList
结果：
After being initialized, the list is: 6, 7, 4, 9
Without the toString() method, the list also is: 6, 7, 4, 9
The position of 4 is 2
The position of 5 is -1
After inserting 8 to position 2, the list is: 6, 7, 8, 4, 9
The position 8 is out of bounds.
After inserting 10 to position 8, the list is: 6, 7, 8, 4, 9
After deleting data at position 3, the list is: 6, 7, 8, 9
After inserting 0 to position 0, the list is: 0, 6, 7, 8, 9
After inserting 1 to position 1, the list is: 0, 1, 6, 7, 8, 9
After inserting 2 to position 2, the list is: 0, 1, 2, 6, 7, 8, 9
After inserting 3 to position 3, the list is: 0, 1, 2, 3, 6, 7, 8, 9
After inserting 4 to position 4, the list is: 0, 1, 2, 3, 4, 6, 7, 8, 9
After inserting 5 to position 5, the list is: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
List is full.
So that we cannot insert 6 to position 6.
List is full.
So that we cannot insert 7 to position 7.
After the reset() method, the list is: empty.
day12 链表
支持与顺序表相同的操作：初始化、插入、删除等。
为节点建一个类。
引用与指针的异同：前者只能使用；后者可以支持 p++ 危险操作。
引用数据类型的赋值，都不会产生新的对象空间。
链表与线性表在插入、删除时的不同：链表不再移动元素，只改变引用 (指针)。
注意，这里的命名和java.util包的命名一样，都是LinkedList，但都能运行，也即不同包可以包含同名的类文件。这里只是关于int的单链表，更一般的是关于<AnyType>的双链表。
注意这段代码的for循环和while的两种实现形式：
public int indexOf(int paraValue) {
int tempPosition = 0;
// Node tempNodeAtPosition = header.next;
// while (tempNodeAtPosition != tail) {
// if (tempNodeAtPosition.data == paraValue) {
// return tempPosition;
// } // Of if
// tempNodeAtPosition = tempNodeAtPosition.next;
// tempPosition++;
// } // Of while
for (Node temp = header.next; temp != tail; temp = temp.next) {
if (temp.data == paraValue) {
return tempPosition;
} // Of if
tempPosition++;
} // of for temp
tempPosition = -1;
return tempPosition;
}// Of indexOf
框架如下：
package dataStructure;
import dataStructure.LinkedList;
/**
* Linked list. Name and comments follow the author's style strictly.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
public class LinkedList {
private class Node {
public int data;
public Node next;
public Node(int paraValue) {}// Of Node's constructor
}// Of class Node
private int theSize;
private Node header;
private Node tail;
public LinkedList() {} // Of the constructor
private void doClear() {} // of doClear
public String toString() {} // Of toString
public void reset() {} // Of reset
public int indexOf(int paraValue) {}// Of indexOf
public boolean add(int paraPosition, int paraValue) {}// Of add
private Node getNodeBeforePosition(int paraPosition, int lower, int upper) {} // of getNodeBeforePosition
private boolean addAfter(Node paraNode, int paraValue) {} // of addAfter
public boolean delete(int paraPosition) {}// Of delete
private boolean deleteAfter(Node paraNode) {} // of delete
}// Of class LinkedList
完整代码：
package dataStructure;
import dataStructure.LinkedList;
/**
* Linked list. Name and comments follow the author's style strictly.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
public class LinkedList {
private class Node {
public int data;
public Node next;
public Node(int paraValue) {
data = paraValue;
next = null;
}// Of Node's constructor
}// Of class Node
private int theSize;
private Node header;
private Node tail;
public LinkedList() {
doClear();
} // Of the constructor
private void doClear() {
header = new Node(0);
tail = new Node(0);
header.next = tail;
theSize = 0;
} // of doClear
public String toString() {
if (header.next == tail) {
return "empty.";
} // Of if
String resultString = "{ ";
Node tempNodeAtPosition = header.next;
while (tempNodeAtPosition != tail) {
resultString += tempNodeAtPosition.data + " ";
tempNodeAtPosition = tempNodeAtPosition.next;
} // Of while
resultString += "}";
return resultString;
} // Of toString
public void reset() {
doClear();
} // Of reset
/**
*********************
* indexOf 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 = 0;
Node tempNodeAtPosition = header.next;
while (tempNodeAtPosition != tail) {
if (tempNodeAtPosition.data == paraValue) {
return tempPosition;
} // Of if
tempNodeAtPosition = tempNodeAtPosition.next;
tempPosition++;
} // Of while
tempPosition = -1;
return tempPosition;
}// Of indexOf
/**
*********************
* add a value at the specified position.
*
* @param paraPosition The given position.
* @param paraValue The given value.
* @return Success or not.
*********************
*/
public boolean add(int paraPosition, int paraValue) {
Node tempNodeBefore = getNodeBeforePosition(paraPosition, 0, theSize);
return addAfter(tempNodeBefore , paraValue);
}// Of add
private Node getNodeBeforePosition(int paraPosition, int lower, int upper) {
if (paraPosition< lower || paraPosition > upper) {
System.out.println("The position " + paraPosition + " is illegal.");
return null;
} // Of if
// tempNodeBeforePosition.next is the Node at the specified position.
Node tempNodeBeforePosition = header;
for (int i = 0; i < paraPosition; i++) {
tempNodeBeforePosition = tempNodeBeforePosition.next;
} // Of for i
return tempNodeBeforePosition;
} // of getNodeBeforePosition
/**
*********************
* Add a value after the specified Node.
*
* @param paraNode The given Node before the Node to be added.
* @return Success or not.
*********************
*/
private boolean addAfter(Node paraNode, int paraValue) {
if (paraNode == null) {
return false;
} else {
Node tempNewNode = new Node(paraValue);
tempNewNode.next = paraNode.next;
paraNode.next = tempNewNode;
theSize++;
return true;
} // of if-else
} // of addAfter
/**
*********************
* Delete a value at the specified position.
*
* @param paraPosition The given position.
* @return Success or not.
*********************
*/
public boolean delete(int paraPosition) {
if (header.next == tail) {
System.out.println("Cannot delete element from an empty list.");
return false;
} // Of if
Node tempNodeBefore = getNodeBeforePosition(paraPosition, 0, theSize-1);
return deleteAfter(tempNodeBefore);
}// Of delete
/**
*********************
* Delete a value after the specified Node.
*
* @param paraNode The given Node before the Node to be deleted.
* @return Success or not.
*********************
*/
private boolean deleteAfter(Node paraNode) {
if (paraNode == null) {
return false;
} else {
paraNode.next = paraNode.next.next;
theSize--;
return true;
} // of if-else
} // of delete
public static void main(String args[]) {
LinkedList tempFirstList = new LinkedList();
System.out.println("Initialized, the list is: " + tempFirstList.toString());
for (int i = 0; i < 5; i++) {
tempFirstList.add(0, 4 - i);
} // Of for i
System.out.println("Add 0 1 2 3 4 successively, the list is: " + tempFirstList.toString());
System.out.println("Add 9 to position 6 could be: " + tempFirstList.add(6, 9) + ", and the List is "
+ tempFirstList.toString());
System.out.println("Add 9 to position 5 could be: " + tempFirstList.add(5, 9) + ", and the List is "
+ tempFirstList.toString());
System.out.println();
System.out.println("Delete the element at position 6 could be: " + tempFirstList.delete(6) + ", and the List is "
+ tempFirstList.toString());
System.out.println("Delete the element at position 0 could be: " + tempFirstList.delete(0) + ", and the List is "
+ tempFirstList.toString());
System.out.println("Delete the element at position 4 could be: " + tempFirstList.delete(4) + ", and the List is "
+ tempFirstList.toString());
System.out.println();
System.out.println("Delete the element in position 0 for 5 times, the lists in sequence are: ");
for (int i = 0; i < 5; i++) {
tempFirstList.delete(0);
System.out.println(tempFirstList);
} // Of for i
}// Of main
}// Of class LinkedList
结果：
Initialized, the list is: empty.
Add 0 1 2 3 4 successively, the list is: { 0 1 2 3 4 }
The position 6 is illegal.
Add 9 to position 6 could be: false, and the List is { 0 1 2 3 4 }
Add 9 to position 5 could be: true, and the List is { 0 1 2 3 4 9 }
The position 6 is illegal.
Delete the element at position 6 could be: false, and the List is { 0 1 2 3 4 9 }
Delete the element at position 0 could be: true, and the List is { 1 2 3 4 9 }
Delete the element at position 4 could be: true, and the List is { 1 2 3 4 }
Delete the element in position 0 for 5 times, the lists in sequence are:
{ 2 3 4 }
{ 3 4 }
{ 4 }
empty.
Cannot delete element from an empty list.
empty.
day13 ArrayList的学习
本小节和下一小节参看了《数据结构与算法分析(Mark Allen Weiss 第3版)》和java.util的ArrayList和LinkedList的代码，然后用自己的理解对ArrayList和LinkedList进行梳理。
这两节显然不是一天能看完的……
详见：
关于ArrayList的梳理。
day14 LinkedList的学习
详见：
关于LinkedList的梳理。
day15 栈
这里是用数组实现的关于char的栈。自然还可以链表实现，同时更一般的是关于任意类型的栈。此外还可以添加一个peek()方法，查看顶端元素但不弹出，这样pop()方法在实现时也可以先调用peek()方法。
基础代码如下：
package dataStructure;
/**
* Char Stack. Name and comments follow the author's style strictly.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
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
/**
*********************
* Pushes an item onto the top of this stack.
*
* @param paraChar The given char.
* @return Success or not.
*********************
*/
public boolean push(char paraChar) {
if (depth == MAX_DEPTH) {
System.out.print("Stack is full.");
return false;
} // Of if
data[depth] = paraChar;
depth++;
return true;
} // Of push
/**
*********************
* Looks at the char at the top of this stack without removing it from the
* stack.
*
* @return the object at the top of this stack.
*********************
*/
public char peek() {
if (depth == 0) {
System.out.print("Nothing to pop. ");
return '\0';
} // of if
return data[depth - 1];
} // of peek
/**
*********************
* Removes the char at the top of this stack and returns that char as the value
* of this function.
*
* @return the char removed from the stack.
*********************
*/
public char pop() {
char resultChar = peek();
if (depth > 0) {
depth--;
} // of if
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++) {
tempStack.push(ch);
System.out.println("The current stack is: " + tempStack);
} // Of for ch
System.out.println();
char tempChar;
for (int i = 0; i < 12; i++) {
tempChar = tempStack.pop();
System.out.print("Poped: " + tempChar);
System.out.println(" The current stack is: " + tempStack);
} // Of for i
} // of main
} // of class CharStack
结果：
The current stack is: a
The current stack is: ab
The current stack is: abc
The current stack is: abcd
The current stack is: abcde
The current stack is: abcdef
The current stack is: abcdefg
The current stack is: abcdefgh
The current stack is: abcdefghi
The current stack is: abcdefghij
Stack is full.The current stack is: abcdefghij
Stack is full.The current stack is: abcdefghij
Poped: j The current stack is: abcdefghi
Poped: i The current stack is: abcdefgh
Poped: h The current stack is: abcdefg
Poped: g The current stack is: abcdef
Poped: f The current stack is: abcde
Poped: e The current stack is: abcd
Poped: d The current stack is: abc
Poped: c The current stack is: ab
Poped: b The current stack is: a
Poped: a The current stack is:
Nothing to pop. Poped: The current stack is:
Nothing to pop. Poped: The current stack is:
day16 栈：括号匹配
任务描述：检查一个字符串的括号是否匹配。匹配是指每个左括号有一个同类型的右括号与之对应，且左括号不可以出现在右括号右边。可以修改测试字符串，检查不同情况下的运行。
仅在上一节的代码基础上增加了一个 bracketMatching 方法，以及 main 中的相应调拭语句。
除了关注的括号，其它字符不起任何作用。一旦发现不匹配，就直接返回。
栈是操作系统的核心数据结构。因为对于计算机而言，如何降低时间、空间复杂度才是王道。栈是操作系统提供的功能，有系统支持，自然快速高效，但是缺点是存储的空间不够大；而堆是关于申请内存和释放内存的函数的事，由程序自己控制，这里速度就会较栈慢些。
代码如下，新建一个类专门测试括号匹配，通过switch case实现：
package dataStructure;
/**
1. Check if the brackets match.
2.
3. @author Fan Min minfanphd@163.com.
4. @learner CatInCoffee.
*/
public class BracketMatching {
/**
*********************
* 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();
tempStack.push('#');
char tempChar;
char tempPopedChar;
// Step 2. Process the string. For a string, length() is a method
// instead of a member variable.
for (int i = 0; i < paraString.length(); i++) {
tempChar = paraString.charAt(i);
switch (tempChar) {
case '(':
case '[':
case '{':
tempStack.push(tempChar);
break;
case ')':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '(') {
return false;
} // Of if
break;
case ']':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '[') {
return false;
} // Of if
break;
case '}':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '{') {
return false;
} // Of if
break;
default:
// Do nothing.
}// Of switch
} // Of for i
tempPopedChar = tempStack.pop();
if (tempPopedChar != '#') {
return false;
} // Of if
return true;
}// Of bracketMatching
public static void main(String[] args) {
boolean tempMatch;
String tempExpression;
tempExpression = "[2 + (1 - 3)] * 4";
tempMatch = bracketMatching(tempExpression);
System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
tempExpression = "(a [b} c)";
tempMatch = bracketMatching(tempExpression);
System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
tempExpression = "(a)[b]{(c)d}";
tempMatch = bracketMatching(tempExpression);
System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
tempExpression = "{(}[)]";
tempMatch = bracketMatching(tempExpression);
System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
tempExpression = "{1024^2 / [(511 +1)^3 × 512 ]} = ?";
tempMatch = bracketMatching(tempExpression);
System.out.println("Is the expression " + tempExpression + " bracket matching? " + tempMatch);
} // of main
} // of class BracketMatching
结果：
Is the expression [2 + (1 - 3)] * 4 bracket matching? true
Is the expression (a [b} c) bracket matching? false
Is the expression (a)[b]{(c)d} bracket matching? true
Is the expression {(}[)] bracket matching? false
Is the expression {1024^2 / [(511 +1)^3 × 512 ]} = ? bracket matching? true
day17 栈：递归
系统会为递归建栈。例如, 累加程序, 空间复杂度是
O
(
n
)
O(n)
O(n)（注意是空间，即储存，时间复杂度更复杂），因为只有运行到 paraN = 1 时, 才会弹栈。
递归显然不是循环推理，在数值计算上就是高中数学里的递推公式，但递归远不止用于数值的相关计算。这里只是简单的说明下递归，递归需要：
- 基础情形，即总有无需递归就能给出的情况。【必须】
- 不断推进。【必须】
- 假设每步递归都能运行。【基础假设，意味着我们不必追踪大量的、复杂的递归调用，默认计算机能处理这些复杂细节】
- 合成收益法则（compound interest rule）：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。【优秀设计原则，不满足能运行，但空间和时间消耗都会大幅提高】
下面的例子是最浅显的递归，但并不是设计良好的递归。
以Fibonacci数列为例，假设计算 f(5)，那么需要计算 f(3)和f(4)，f(4)又需要计算 f(2)和f(3)，f(3)显然重复计算了。实际上里面重复计算的非常多，每条分支都需要一直分到基准情形，然后再算回来。用递归实现Fibonacci数列的时间复杂度是
O
(
1.61
8
n
)
O(1.618^n)
O(1.618n)（证明略。简单的说，设计算f(N)的时间为
T
n
T_n
Tn，那么
T
n
=
T
n
−
1
+
T
n
−
2
T_n=T_{n-1}+T_{n-2}
Tn=Tn−1+Tn−2，前两次为常数时间，也即相当于求Fibonacci数列，高中数学可求），可以看到时间复杂度是指数级的。
package dataStructure;
/**
* Recursion. A method can (directly or indirectly) invoke itself. The system
* automatically creates a stack for it.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
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
public static void main(String[] args) {
int tempValue = 5;
System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));
tempValue = -2;
System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));
for (int i = 0; i <= 5; i++) {
System.out.println("Fibonacci " + i + ": " + fibonacci(i));
} // Of for i
} // of main
}// of class Recursion
结果：
0 sum to 5 = 15
0 sum to -2 = 0
Fibonacci 0: 0
Fibonacci 1: 1
Fibonacci 2: 1
Fibonacci 3: 2
Fibonacci 4: 3
Fibonacci 5: 5
day18 链队列
入队仅操作尾部，出队仅操作头部。
header和tail是The index to calculate the header and the tail。原因：header和tail会一直加下去，不是真实的index，而是通过%模运算得到真实的index。
也即，data[head];应该是data[head % TOTAL_SPACE];。否则，会出现ArrayIndexOutOf-BoundsException的异常。
换个角度，在java中，整数的a%b=a-a/b*b，是2次乘法1次加法，或许可以保持int resultValue = data[head];不变，而是在header++;后加一个判断if (header == TOTAL_SPACE) {header = 0;}，即通过一个额外的判断来实现循环，取消掉所有的%模运算，在tail部分同理，不过注意toString的实现需要调整代码（header可能大于tail）。当然，节约的计算量微乎其微，且没有模运算看起来巧妙，不过代码的可阅读性增强了，同时有意识地控制了模运算的次数。
package dataStructure;
/** about class author ...
*/
public class LinkedQueue {
private static class Node {
int data;
Node next;
public Node(int paraValue) {
data = paraValue;
next = null;
}// Of the constructor
}// Of class Node
Node header;
Node tail;
public LinkedQueue() {
doConstruct();
}// Of the first constructor
private void doConstruct() {
header = new Node(-1);
tail = header;
} // of doConstruct()
public void enqueue(int paraValue) {
Node tempNode = new Node(paraValue);
tail.next = tempNode;
tail = tempNode;
}// Of enqueue
public int dequeue() {
// if (header.next == null) {
if (header == tail) {
System.out.println("No element in the queue");
return -1;
} // Of if
int resultValue = header.next.data;
header.next = header.next.next;
if (header.next == null) {
doConstruct();
} // of if
return resultValue;
}// Of dequeue
public String toString() {
String resultString = "{ ";
if (header == tail) {
// if (header.next == null) {
return "empty";
} // Of if
// Node tempNode = header.next;
// while (tempNode != null) {
// resultString += tempNode.data + ", ";
// tempNode = tempNode.next;
// } // Of while
for (Node tempNode = header.next; tempNode != null; tempNode = tempNode.next) {
resultString += tempNode.data + " ";
} // of for tempNode
resultString += "}";
return resultString;
}// Of toString
public static void main(String args[]) {
LinkedQueue tempQueue = new LinkedQueue();
System.out.println("Initialized, the list is: " + tempQueue.toString());
for (int i = 0; i < 5; i++) {
tempQueue.enqueue(i + 1);
} // Of for i
System.out.println("Enqueued 1 to 5 successively, the queue is: " + tempQueue);
tempQueue.dequeue();
System.out.println("Dequeued, the queue is: " + tempQueue);
System.out.println();
int tempValue;
for (int i = 0; i < 5; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue);
} // Of for i
for (int i = 1; i < 4; i++) {
tempQueue.enqueue(i*10);
System.out.println("Enqueued" + i*10 + ", the queue is: " + tempQueue);
} // Of for i
} // Of main
} // Of class LinkedQueue
结果：
Initialized, the list is: empty
Enqueued 1 to 5 successively, the queue is: { 1 2 3 4 5 }
Dequeued, the queue is: { 2 3 4 5 }
Looped delete 2, the new queue is: { 3 4 5 }
Looped delete 3, the new queue is: { 4 5 }
Looped delete 4, the new queue is: { 5 }
Looped delete 5, the new queue is: empty
No element in the queue
Looped delete -1, the new queue is: empty
Enqueued10, the queue is: { 10 }
Enqueued20, the queue is: { 10 20 }
Enqueued30, the queue is: { 10 20 30 }
day19 循环队列
核心是利用求余运算%完成达成循环的判断。
保留一个空节点，用于判断。传统方法是header、tail一直增加，然后模运算到相应节点，也可以加一个判断来控制代码中的模运算。
后面将这里的代码改写为关于任意类型的泛型类CircleQueue<AnyType>，并应用在字符队列上。
package dataStructure;
/**
* Circle int queue.
*
* @author Fan Min minfanphd@163.com.
* @learner CatInCoffee.
*/
public class CircleIntQueue {
/**
* The total space. One space should never be used.
*/
public static final int TOTAL_SPACE = 10;
int[] data;
/**
* The index of the header and the tail.
*/
int header;
int tail;
/**
*******************
* The constructor
*******************
*/
public CircleIntQueue() {
data = new int[TOTAL_SPACE];
header = 0;
tail = 0;
} // Of the constructor
/**
*********************
* Enqueue.
*
* @param paraValue The value of the new node.
*********************
*/
public void enqueue(int paraValue) {
if ((tail + 1) % TOTAL_SPACE == header) {
System.out.println("The queue is full.");
return;
} // Of if
data[tail] = paraValue;
tail++;
if (tail == TOTAL_SPACE) {
tail = 0;
} // of if
} // Of enqueue
/**
*********************
* Dequeue.
*
* @return The value at the header.
*********************
*/
public int dequeue() {
if (header == tail) {
System.out.println("There is no element in the queue.");
return -1;
} // Of if
int resultValue = data[header];
header++;
if (header == TOTAL_SPACE) {
header = 0;
} // of if
return resultValue;
} // Of dequeue
/**
*********************
* Overrides the method claimed in Object, the superclass of any class.
*********************
*/
public String toString() {
String resultString = "{ ";
if (header == tail) {
return "empty.";
} else if (header < tail) {
for (int i = header; i < tail; i++) {
resultString += data[i] + " ";
} // Of for i
} else {
for (int i = header; i < TOTAL_SPACE; i++) {
resultString += data[i] + " ";
} // Of for i
for (int j = 0; j < tail; j++) {
resultString += data[j] + " ";
} // Of for j
// for (int k = header; k < tail + TOTAL_SPACE; k++) {
// resultString += data[k % TOTAL_SPACE] + " ";
// } // Of for k
} // of if-elseIf-if
resultString += "}";
return resultString;
} // Of toString
/**
*********************
* The entrance of the program.
*
* @param args Not used now.
*********************
*/
public static void main(String args[]) {
CircleIntQueue tempQueue = new CircleIntQueue();
System.out.println("Initialized, the list is: " + tempQueue);
for (int i = 0; i < 5; i++) {
tempQueue.enqueue(i);
} // Of for i
System.out.println("Enqueue, the queue is: " + tempQueue);
int tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue);
tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue);
System.out.println();
for (int i = 0; i < 7; i++) {
tempQueue.enqueue(i + 5);
System.out.println("Enqueue, the queue is: " + tempQueue);
} // Of for i
System.out.println();
for (int i = 0; i < 9; i++) {
tempQueue.dequeue();
} // Of for i
System.out.println("Dequeue 9 elements , and the queue is: " + tempQueue);
System.out.println();
tempQueue.dequeue();
System.out.println("Dequeue, the queue is: " + tempQueue);
tempQueue.enqueue(10);
System.out.println("Enqueue, the queue is: " + tempQueue);
} // Of main
} // Of CircleIntQueue
结果：
Initialized, the list is: empty.
Enqueue, the queue is: { 0 1 2 3 4 }
Dequeue 0, the queue is: { 1 2 3 4 }
Dequeue 1, the queue is: { 2 3 4 }
Enqueue, the queue is: { 2 3 4 5 }
Enqueue, the queue is: { 2 3 4 5 6 }
Enqueue, the queue is: { 2 3 4 5 6 7 }
Enqueue, the queue is: { 2 3 4 5 6 7 8 }
Enqueue, the queue is: { 2 3 4 5 6 7 8 9 }
Enqueue, the queue is: { 2 3 4 5 6 7 8 9 10 }
The queue is full.
Enqueue, the queue is: { 2 3 4 5 6 7 8 9 10 }
Dequeue 9 elements , and the queue is: empty.
There is no element in the queue.
Dequeue, the queue is: empty.
Enqueue, the queue is: { 10 }
改写为泛型类CircleQueue，并用字符队列来测试。
package dataStructure;
public class CircleQueue<T> {
public static final int TOTAL_SPACE = 6;
private T[] data;
// The index of the header and the tail.
private int header;
private int tail;
public CircleQueue() {
data = (T[]) (new Object[TOTAL_SPACE]);
header = 0;
tail = 0;
} // Of the constructor
public void enqueue(T paraValue) {
if ((tail + 1) % TOTAL_SPACE == header) {
System.out.println("The queue is full.");
return;
} // Of if
data[tail] = paraValue;
tail++;
if (tail == TOTAL_SPACE) {
tail = 0;
} // of if
} // Of enqueue
public T dequeue() {
if (header == tail) {
System.out.println("There is no element in the queue.");
return null;
} // Of if
T resultValue = data[header];
header++;
if (header == TOTAL_SPACE) {
header = 0;
} // of if
return resultValue;
} // Of dequeue
public String toString() {
String resultString = "{ ";
if (header == tail) {
return "empty.";
} else if (header < tail) {
for (int i = header; i < tail; i++) {
resultString += data[i] + " ";
} // Of for i
} else {
for (int i = header; i < TOTAL_SPACE; i++) {
resultString += data[i] + " ";
} // Of for i
for (int j = 0; j < tail; j++) {
resultString += data[j] + " ";
} // Of for j
// for (int k = header; k < tail + TOTAL_SPACE; k++) {
// resultString += data[k % TOTAL_SPACE] + " ";
// } // Of for k
} // of if-elseIf-if
resultString += "}";
return resultString;
} // Of toString
public static void main(String args[]) {
CircleQueue<Character> tempQueue = new CircleQueue<>();
System.out.println("Initialized, the TOTAL_SPACE is: " + TOTAL_SPACE + " , and the list is: " + tempQueue);
for (char i = '0'; i < '4'; i++) {
tempQueue.enqueue(i);
} // Of for i
System.out.println("Enqueue, the queue is: " + tempQueue);
Character tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue);
for (char i = 'a'; i < 'd'; i++) {
tempQueue.enqueue(i);
System.out.println("Enqueue, the queue is: " + tempQueue);
} // Of for i
System.out.println();
for (int i = 0; i < 6; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue);
} // Of for i
System.out.println();
for (char i = 'A'; i <= 'F'; i++) {
tempQueue.enqueue(i);
System.out.println("Enqueue, the queue is: " + tempQueue);
} // Of for i
} // Of main
} // Of CircleQueue<T>
结果：
Initialized, the TOTAL_SPACE is: 6 , and the list is: empty.
Enqueue, the queue is: { 0 1 2 3 }
Dequeue 0, the queue is: { 1 2 3 }
Enqueue, the queue is: { 1 2 3 a }
Enqueue, the queue is: { 1 2 3 a b }
The queue is full.
Enqueue, the queue is: { 1 2 3 a b }
Dequeue 1, the queue is: { 2 3 a b }
Dequeue 2, the queue is: { 3 a b }
Dequeue 3, the queue is: { a b }
Dequeue a, the queue is: { b }
Dequeue b, the queue is: empty.
There is no element in the queue.
Dequeue null, the queue is: empty.
Enqueue, the queue is: { A }
Enqueue, the queue is: { A B }
Enqueue, the queue is: { A B C }
Enqueue, the queue is: { A B C D }
Enqueue, the queue is: { A B C D E }
The queue is full.
Enqueue, the queue is: { A B C D E }
day20 字符串匹配
打印引号方式：\"
package dataStructure;
/** about class author ...
*/
public class MyString {
public static final int MAX_LENGTH = 10;
private int length;
private char[] data;
public MyString() {
doConstruct();
} // Of the first constructor
private void doConstruct() {
length = 0;
data = new char[MAX_LENGTH];
} // of doConstruct()
public MyString(String paraString) {
if (paraString.length() > MAX_LENGTH) {
System.out.println("The String <" + paraString + "> cannot be initialized.");
doConstruct();
return;
} // of if
data = new char[MAX_LENGTH];
length = paraString.length();
for (int i = 0; i < length; i++) {
data[i] = paraString.charAt(i);
} // Of for i
} // Of the second constructor
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 - paraMyString.length + 1; i++) {
// Initialize.
tempMatch = true;
for (int j = 0; j < paraMyString.length; j++) {
if (data[i + j] != paraMyString.data[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) {
System.out.print("The bound is exceeded. \t");
return null;
} // Of if
MyString resultMyString = new MyString();
resultMyString.length = paraLength;
for (int i = 0; i < paraLength; i++) {
resultMyString.data[i] = data[paraStartPosition + i];
} // Of for i
return resultMyString;
} // Of substring
public static void main(String args[]) {
MyString tempFirstString = new MyString("I like ik....");
tempFirstString = new MyString("I like iki");
MyString tempSecondString = new MyString("ik");
int tempPosition = tempFirstString.locate(tempSecondString);
System.out.println(
"The position of \"" + tempSecondString + "\" in \"" + tempFirstString + "\" is: " + tempPosition);
MyString tempThirdString = new MyString("ki");
tempPosition = tempFirstString.locate(tempThirdString);
System.out.println(
"The position of \"" + tempThirdString + "\" in \"" + tempFirstString + "\" is: " + tempPosition);
tempThirdString = new MyString("love");
tempPosition = tempFirstString.locate(tempThirdString);
System.out.println(
"The position of \"" + tempThirdString + "\" in \"" + tempFirstString + "\" is: " + tempPosition);
tempThirdString = tempFirstString.substring(1, 2);
System.out.println("The substring is: \"" + tempThirdString + "\"");
tempThirdString = tempFirstString.substring(5, 5);
System.out.println("The substring is: \"" + tempThirdString + "\"");
tempThirdString = tempFirstString.substring(5, 6);
System.out.println("The substring is: \"" + tempThirdString + "\"");
} // Of main
} // Of class MyString
结果：
The String <I like ik....> cannot be initialized.
The position of "ik" in "I like iki" is: 3
The position of "ki" in "I like iki" is: 8
The position of "love" in "I like iki" is: -1
The substring is: " l"
The substring is: "e iki"
The bound is exceeded. The substring is: "null"