2021年秋第五周周报内容
1. 递归
递归, 就是在运行的过程中调用自己.
举个例子, 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事. 故事是什么呢? "从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事. 故事是什么呢？'从前有座山，山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事. 故事是什么呢?...' ''
构成递归需具备的条件:
1. 子问题须与原始问题为同样的事, 且更为简单;
2. 不能无限制地调用本身, 须有个出口, 化简为非递归状况处理.
package datastructure;
public class Recursion {
public static int fibonacci(int paraIndex) {
if(paraIndex <= 0) {
return 0;
}// Of if
if(paraIndex == 1) {
return 1;
}// Of if
return fibonacci(paraIndex - 1) + fibonacci(paraIndex - 2);
}// Of fibonacci
public static int calFactorial(int paraValue) {
// Negative numbers have no factorial.
if(paraValue < 0) {
return -1;
}// Of if
if(paraValue == 0) {
return 1;
}// Of if
return paraValue * calFactorial(paraValue - 1);
}// Of calFactorial
public static void main(String[] args) {
int tempValue = 0;
int tempFactorial = calFactorial(tempValue);
System.out.println("The factorial of " + tempValue + " is " + tempFactorial);
tempValue = 1;
tempFactorial = calFactorial(tempValue);
System.out.println("The factorial of " + tempValue + " is " + tempFactorial);
tempValue = 5;
tempFactorial = calFactorial(tempValue);
System.out.println("The factorial of " + tempValue + " is " + tempFactorial);
int tempFabonacci;
for(int i = 0; i < 5; i++) {
tempFabonacci = fibonacci(i);
System.out.println("Fibonacci " + i + ": " + tempFabonacci);
}// Of for i
}// Of main
}// Of class Recursion
运行, 输出:
The factorial of 0 is 1 The factorial of 1 is 1 The factorial of 5 is 120 Fibonacci 0: 0 Fibonacci 1: 1 Fibonacci 2: 1 Fibonacci 3: 2 Fibonacci 4: 32. 队列
和栈一样, 队列是一种操作受限制的线性表. 进行插入操作的端称为队尾, 进行删除操作的端称为队头. 特点是"先进先出".
package datastructure;
public class Queue {
// The maximal length of the queue.
public static final int MAX_LENGTH = 10;
// The actual length of the queue.
int length;
//The data;
int[] data;
public Queue() {
length = 0;
data = new int[MAX_LENGTH];
}//
public boolean enqueue(int paraValue) {
if(length == MAX_LENGTH) {
System.out.println("The queue is full, enqueue fail");
return false;
}// Of if
data[length] = paraValue;
length++;
return true;
}// Of enqueue
public int dequeue() {
int resultValue = -1;
if(length == 0 ) {
System.out.println("The queue is empty, dequeue");
return resultValue;
}// Of if
resultValue = data[0];
for(int i = 0; i < length-1; i++) {
data[i] = data[i+1];
}// Of for i
length--;
return resultValue;
}// Of dequeue
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
}// Of class queue
测试:
package testdemo;
import datastructure.Queue;
public class test5 {
public static void main(String[] args) {
Queue tempQueue = new Queue();
for(int i = 0; i < 5; i++) {
tempQueue.enqueue(i);
System.out.println("Enqueued, the queue is: " + tempQueue.toString());
}// Of for i
int tempValue;
for(int i = 0; i < 7; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Dnqueued, the queue is: " + tempQueue);
System.out.println("The dequeue value is: "+ tempValue);
}// Of for i
}// Of main
}// Of class test5
输出:
Enqueued, the queue is: 0 Enqueued, the queue is: 0, 1 Enqueued, the queue is: 0, 1, 2 Enqueued, the queue is: 0, 1, 2, 3 Enqueued, the queue is: 0, 1, 2, 3, 4 Dnqueued, the queue is: 1, 2, 3, 4 The dequeue value is: 0 Dnqueued, the queue is: 2, 3, 4 The dequeue value is: 1 Dnqueued, the queue is: 3, 4 The dequeue value is: 2 Dnqueued, the queue is: 4 The dequeue value is: 3 Dnqueued, the queue is: empty The dequeue value is: 4 The queue is empty, dequeue Dnqueued, the queue is: empty The dequeue value is: -1 The queue is empty, dequeue Dnqueued, the queue is: empty The dequeue value is: -1
3. 链式队列
链式队列是基于单链表的存储表示实现的队列.
相比简单队列, 它不存在因队满而产生溢出的情况.
package datastructure;
public class linkedQueue {
// The inner class.
class Node{
// The data;
int data;
// The reference to the next node.
Node next;
public Node(int paraValue){
data = paraValue;
next = null;
}// Of the node constructor
}// Of class Node
public linkedQueue() {
header = new Node(0);
tail = header;
}// Of linkedQueue
// The header node.
Node header;
// The tail of the queue.
Node tail;
public void reset() {
header.next = null;
}
public void enqueue(int tempValue) {
Node tempNode = new Node(tempValue);
tail.next = tempNode;
tail = tempNode;
}// Of enqueue
public int dequeue() {
int resultValue = -1;
if(header == tail) {
System.out.println("The queue is empty, dequeue fail");
return resultValue;
}// Of if
resultValue = header.next.data;
header.next = header.next.next;
if(header.next == null) {
tail = header;
}// Of if
return resultValue;
}// Of dequeue
public String toString() {
String resultString = "";
if(header.next == null) {
return "empty";
}// Of if
Node tempNode = header.next;
while(tempNode.next != null) {
resultString += tempNode.data + ", ";
tempNode = tempNode.next;
}// Of while
resultString += tempNode.data;
return resultString;
}// Of toString
public int length() {
int resultLength = 0;
Node tempNode = header;
while(tempNode.next != null) {
resultLength ++;
tempNode = tempNode.next;
}
return resultLength;
}// Of length
}// Of class linkedList
测试:
package testdemo;
import datastructure.linkedQueue;
public class test6 {
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("Enqueue, the queue is: " + tempQueue.toString());
System.out.println("The length of the queue is: " + tempQueue.length());
tempQueue.dequeue();
System.out.println("Dequeue, the queue is: " + tempQueue.toString());
int tempValue;
for (int i = 0; i < 5; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Looped delete " + tempValue + ", the new queue is: " + tempQueue.toString());
} // Of for i
for (int i = 0; i < 3; i++) {
tempQueue.enqueue(i + 10);
} // Of for i
System.out.println("Enqueue, the queue is: " + tempQueue.toString());
}// Of main
}// Of class test6
输出:
Initialized, the list is: empty Enqueue, the queue is: 1, 2, 3, 4, 5 The length of the queue is: 5 Dequeue, 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 The queue is empty, dequeue fail Looped delete -1, the new queue is: empty Enqueue, the queue is: 10, 11, 124. 循环队列
循环队列是把简单队列首尾相连, 把存储队列元素的表从逻辑上看成一个环, 成为循环队列.
利用front和rea 分别表示队首和队尾的位置.
当队列为空时,有front=rear, 而当所有队列空间全占满时, 也有front=rear. 为了区别这两种情况, 规定循环队列最多只能有MaxSize-1个队列元素, 当循环队列中只剩下一个空存储单元时, 队列就已经满了. 因此, 队列判空的条件是front=rear, 而队列判满的条件是front=（rear+1)%MaxSize.
package datastructure;
public class CircularQueue {
// The total space of the circular queue. But the actual sapce will be one less.
public static int MAX_SIZE = 10;
// The data.
int[] data;
// The index of the head of the queue.
int front;
// The index of the tail of the queue.
int rear;
public CircularQueue() {
data = new int[MAX_SIZE];
// data = new char[TOTAL_SPACE];
front = 0;
rear = 0;
}// Of the constructor
public Boolean enqueue(int paraValue) {
if(front == (rear + 1) % MAX_SIZE) {
return false;
}// Of if
data[rear % MAX_SIZE] = paraValue;
rear++;
return true;
}// Of enqueue
public int dequeue() {
int resultValue = -1;
if(front == rear) {
return resultValue;
}// Of if
resultValue = data[front % MAX_SIZE];
front++;
return resultValue;
}// Of dequeue
public int length() {
int resultLength = (rear - front + MAX_SIZE) % MAX_SIZE;
return resultLength;
}// Of length
public String toString() {
String resultString = "";
if(front == rear) {
return "empty";
}// Of if
for(int i = front; i < rear - 1; i++) {
resultString += data[i % MAX_SIZE] + ", ";
}// Of for i
resultString += data[(rear-1) % MAX_SIZE];
return resultString;
}// Of toString
}// Of class CircularQueue
测试:
package testdemo;
import datastructure.CircularQueue;
public class test7 {
public static void main(String args[]) {
CircularQueue tempQueue = new CircularQueue();
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("Enqueue, the queue is: " + tempQueue.toString());
System.out.println("The length of eh queue is: " + tempQueue.length());
int tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());
for (int i = 0; i < 6; i++) {
tempQueue.enqueue(i + 10);
System.out.println("Enqueue, the queue is: " + tempQueue.toString());
} // Of for i
for (int i = 0; i < 3; i++) {
tempValue = tempQueue.dequeue();
System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());
} // Of for i
for (int i = 0; i < 6; i++) {
tempQueue.enqueue(i + 100);
System.out.println("Enqueue, the queue is: " + tempQueue.toString());
} // Of for i
}// Of main
}
输出:
Initialized, the list is: empty Enqueue, the queue is: 1, 2, 3, 4, 5 The length of eh queue is: 5 Dequeue 1, the queue is: 2, 3, 4, 5 Enqueue, the queue is: 2, 3, 4, 5, 10 Enqueue, the queue is: 2, 3, 4, 5, 10, 11 Enqueue, the queue is: 2, 3, 4, 5, 10, 11, 12 Enqueue, the queue is: 2, 3, 4, 5, 10, 11, 12, 13 Enqueue, the queue is: 2, 3, 4, 5, 10, 11, 12, 13, 14 Enqueue, the queue is: 2, 3, 4, 5, 10, 11, 12, 13, 14 Dequeue 2, the queue is: 3, 4, 5, 10, 11, 12, 13, 14 Dequeue 3, the queue is: 4, 5, 10, 11, 12, 13, 14 Dequeue 4, the queue is: 5, 10, 11, 12, 13, 14 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100, 101 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100, 101, 102 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100, 101, 102 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100, 101, 102 Enqueue, the queue is: 5, 10, 11, 12, 13, 14, 100, 101, 1025. 字符串匹配
任务描述: 复现String类中的部分功能.
indexOf: 从主串中找子串的位置.
substring: 从主串截取子串.
concat: 连接两个字符串.
package datastructure;
public class MyString {
// The maxtial length of the string.
public static final int MAX_LENGTH = 100;
// The data.
char[] data;
// The actual of the string.
int length;
public MyString(String paraString){
length = paraString.length();
data = new char[MAX_LENGTH];
for(int i = 0; i < length; i++) {
data[i] = paraString.charAt(i);
}// Of for i
}// Of one constructor
public MyString(){
length = 0;
data = new char[MAX_LENGTH];
}// Of another constructor
public String toString() {
String resultString = "";
for(int i = 0; i < length; i++) {
resultString += data[i];
}// Of for i
return resultString;
}// Of toString
public int indexOf(MyString paraMystring) {
boolean tempMatch;
for(int i = 0; i < length - paraMystring.length + 1; i++) {
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 == true) {
return i;
}// Of if
}// Of for i
return -1;
}
public MyString substring(int paraStartindex, int paraLength) {
MyString resultMystring = new MyString();
if(paraStartindex + paraLength > length) {
System.out.println("The length is out of bounds.");
return null;
}// Of if
resultMystring.length = paraLength;
for(int i = 0; i < paraLength; i++) {
resultMystring.data[i] = data[paraStartindex + i];
}// Of for i
return resultMystring;
}// Of substring
public void concat(MyString paraString) {
if(paraString.length + length > MAX_LENGTH) {
System.out.println("The length is out of bounds");
}
for(int i = 0; i < paraString.length; i++) {
data[length + i] = paraString.data[i];
}// Of for i
data[length + paraString.length] = ' ';
length += paraString.length;
}// Of concat
}// Of class MyString
测试:
package testdemo;
import datastructure.MyString;
public class test8 {
public static void main(String[] args) {
MyString tempFirstString = new MyString("I like ik.");
MyString tempSecondString = new MyString("ik");
int tempPosition = tempFirstString.indexOf(tempSecondString);
System.out.println("The position of "" + tempSecondString + "" in "" + tempFirstString
+ "" is: " + tempPosition);
MyString tempThirdString = new MyString("ki");
tempPosition = tempFirstString.indexOf(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 + """);
MyString tempFourthString = new MyString("Welcome to join ");
System.out.println("The one string is :" + tempFourthString);
MyString tempFivthString = new MyString("our smale lab.");
System.out.println("The another string is :" + tempFivthString);
tempFourthString.concat(tempFivthString);
System.out.println("Concated, the string is : " + tempFourthString);
}// Of main
}// Of class test8
输出:
The position of "ik" in "I like ik." is: 3 The position of "ki" in "I like ik." is: -1 The substring is: " l" The substring is: "e ik." The length is out of bounds. The substring is: "null" The one string is :Welcome to join The another string is :our smale lab. Concated, the string is : Welcome to join our smale lab.6. 小结
Q1.面向对象与面向过程相比, 有哪些优势?
在我看来, 面向对象使得编程结构更加清晰, 并且容易修改和维护.
就拿吃饭来举个例. 你想吃蛋炒饭, 面向过程就好比你自己制作, 煮饭, 煎蛋, 加佐料, 炒等一系列操作都需要你自己来; 面向对象就相当于你直接去饭店买. 你如果想吃另外的, 按第一个选择, 你就要改变你的制作方法.
Q2.比较线性表和链接的异同.
同: 都为线性结构; 都可以顺序存取.
不同: 前者的存储空间固定, 后者不固定.
Q3.分析链队列与循环队列的优缺点.
链式队列动态开辟存储空间, 不会出现队满的情况, 当多了一个指针域(引用), 会多一些空间上的开销.
循环队列能够重复使用开辟后的空间, 利用率高, 但是还是会出现队满的情况.
Q4. 对于原帖中第 18 天建立的两个队列, 其区别仅在于基础数据不同, 一个是 int, 一个是 char. 按这种思路, 对于不同的基础数据类型, 都需要重写一个类, 这样合理吗? 你想怎么样?
我觉得不合理, 我觉得用char定义就可以了. 毕竟char数组里面是可以存储数字的, 只需要强制类型转换就可以了.
// type int to type char int number = 9; char cNumber= (char) (number + '0');
