【学习笔记】递归与链表 | 学习笔记 / 代码学习

数据结构和算法分析（Data Structures and Algorithm Analysis） 的第一节课是回顾之前所学的递归（Recursion），作为导入课的同时还可以简单复习一下 java（这门课所使用语言）。因此第一周的课程和 lab 不算难，以下是 Lab 的具体细节。

Lab 1

题目 1

Read in a positive number and compute its factorial using recursion.
Note that your class should be named “T1”， and should contain
- a main function, which does IO
- and a recursive function, public static int factR(int n), which computes the factorial
You may build you recursion as follows.
- Step, if n>1: factR(n) = n * factR(n-1)
- Base, if n<=1: factR(1) = 1

简单来说就是读入一个正整数并使用递归计算其阶乘，值得注意的是虽然题目说的是正整数，但如果输入负数和零也要进行处理。老师已经给了主要结构：

import java.util.Scanner;
public class T1 {
	public static int factR(int n) {
		/*YOUR CODE HERE*/
	}

	public static void main(String[] args) {
		/*YOUR CODE HERE*/

	    System.out.println(factR(n)); //n is the input from keyboard
	}
}

即当给的数小于等于 1 时返回 1（0 的阶乘为 1），否则就按照阶乘的运算方式递归即可。如下:

import java.util.Scanner;
public class T1 {
	public static int factR(int n) {
		if (n <= 1)
			return 1;
		else
			return n * factR(n - 1);
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		System.out.println(factR(n)); 
		scan.close();
	}
}

不是没有注释，而是因为我写的不严谨。索性全删了，以后不再赘述。

题目 2

Read in and compute the greatest common divisor (GCD) of two natural numbers using recursion.
GCD(x, y) is the greatest natural number which divides both x and y
- GCD(6, 5) = 1
- GCD(6, 9) = 3
- GCD(6, 0) = 6
Note that your class should be named “T2” and should contain
- a main function, which does IO
- and a recursive function, public static int GCD(int x, int y), which computes the GCD of x and y.

老师给的模板：

import java.util.Scanner;
public class T2 {
	public static int GCD(int x, int y) {
		/*YOUR CODE HERE*/
	}

	public static void main(String[] args) {
		/*YOUR CODE HERE*/
	    System.out.println(GCD(x, y)); // x, y are the inputs from keyboard
	}
}

这个题目就很有意思了，计算两个自然数的最大公约数。通常最经典的方法便是欧几里得算法，其步骤为：

用较大的数除以较小的数，取余数。
用较小的数替代较大的数，用余数替代较小的数。
重复上述步骤，直到余数为 0，此时较小的数即为最大公约数。

正常输入的数一大一小，但大数在前面还是小的数在前面就是一个问题。这里引用朋友的方法，我觉得十分巧妙，无论大数在前面还是小的数在前面都能完美解决:

import java.util.Scanner;

public class T2 {
	public static int GCD(int x, int y) {
		if (y == 0)
			return x;
		else {
			return GCD(y, x % y);
		} 
	}

	public static void main(String[] args) {
		Scanner scan1 = new Scanner(System.in);
		Scanner scan2 = new Scanner(System.in);
		int x = scan1.nextInt();
		int y = scan2.nextInt();
		System.out.println(GCD(x, y)); 
		scan1.close();
		scan2.close();
	}
}

题目 3

Output the reverse-order form of an integer. Recursion should be used, and your input should be a positive integer.
For example:
- Input: 2783; output: 3872
- Input: 598; output: 895
- Input: 3; output: 3
Note that your class should be named “EX1” and should contain
- a main function, which does IO
- and a recursive function, public static int reverseForm(int n).

老师给的结构：

import java.util.Scanner;
public class EX1 {
	
	public static int reverseForm(int n) {
		/*YOUR CODE HERE*/
	}
	public static void main(String[] args) {
		/*YOUR CODE HERE*/
		
		System.out.println(reverseForm(n)); //n is the input from keyboard
	}
}

这道题就其实也不算难，要求输出一个整数的逆序形式。比如输入是 123456，那么要求输出就是 654321。其实我之前再 LeetCode 上见过，印象里学 C 的时候老师好像也提到过，不过好像每次都没做出来。。。属于是它认识我我不认识它了 QAQ。

正常思路就是将这个数取 10 的余，得到的数即输出的最高位，将它每次递归都乘 10，以此类推。

我自己写的话出现了很多问题，比如输入的数可能是不同位数，因此递归次数就成了一个比较难解决的问题。

中间问同学的思路得知他们是先得到所给数的位数，即用数学方法中的 log10，取到位数后再进行递归。不过我觉得还是很麻烦，加上当时已经筋疲力尽了，通过 ai 果然得到了更好的方法：

import java.util.Scanner;
public class EX1 {
	public static int reverseForm(int n) {
		if (n < 10) {
			return n;
		} else {
			int i = n % 10;
			int all = n / 10; 
			int digits = (int) Math.log10(all) + 1;
			return i * (int) Math.pow(10, digits) + reverseForm(all);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); 
		System.out.println(reverseForm(n));
		scanner.close();
	}
}

可以看到定义三个整数，i 作为新的最大位数，all 作为下次递归的数据，digits 为数据位数吗，最后返回对应位数的对应 10 次放即可。

题目 4

Output the binary form of a decimal integer. Recursion should be used, and your input should be a String.
For example:
- Input: 27; output: 11011
- Input: 33; output: 100001
- Input: 3; output: 11
Note that your class should be named “EX2” and should contain
- a main function, which does IO
- and a recursive function, public static String binaryForm(int n).

老师给的代码如下

/*Add some comments by yourself*/
import java.util.Scanner;
public class EX2 {
	public static String binaryForm(int n) {
		/*YOUR CODE HERE*/
	}

	public static void main(String[] args) {
	    /*YOUR CODE HERE*/
	    System.out.println(binaryForm(n)); //n is the input from keyboard
	}

}

也就是将一个十进制整数变成二进制形式。还是比较简单的：

import java.util.Scanner;
public class EX2 {
	public static String binaryForm(int n) {
		String a = "";
		if (n == 0)
			return "0";
		if (n == 1)
			return "1";
		if (n % 2 == 0) {// case 1
			a = "0";
			return binaryForm(n / 2) + a;
		} else if (n % 2 == 1) {
			a = "1";
			return binaryForm(n / 2) + a;
		}
		return a;
	}

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		System.out.println(binaryForm(n)); 
		scan.close();
	}
}

Lab0 到这里就结束了。下面是第二周课的细节

Class 1

所讲内容

（Linked List）

作用： 链表一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。不管是 RTOS 还是 Linux 等使用非常广泛，所以必须要搞懂链表，链表分为单向链表和双向链表，单向链表很少用，使用最多的还是双向链表。

定义： 链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

结构：

链表由一系列节点（链表中每一个元素称为节点）组成，每个节点包括两个部分：
- 存储数据元素的数据域
- 存储下一个节点地址的指针域
- 首个节点的地址必须被存储

这样，链表的结构使其能够建立起各节点之间的线性关系。

老师上课讲的英文我也听不太懂，接下来就是 Lab 时间

Lab 2

首先看下题目：

Given Node.java, complete List.java with
- all the complete functions defined
- a main function has been given for the class which tests 5 functions:
  - isEmpty
  - insertNode
  - findNode
  - removeNode
  - displayList Submit List.java to iSpace. 也就是通过 Node.java 里面所写的内容，用在 List.java 中，实现 5 个基本功能：1.判断链表是否为空，2.插入节点，3.寻找节点，4.移除节点，5.展示链表。

UML 图

老师给的模板如下：

List.java

public class List {
	/*YOUR CODE HERE*/
	
	public static void main(String[] args) {
		List myList  = new List();
		System.out.println(myList.isEmpty());
		myList.insertNode(0, 1);
		System.out.println("Data of head: " + myList.head.getData());
		myList.displayList();
		myList.insertNode(1, 2);
		myList.displayList();
		myList.insertNode(0, 3);
		myList.displayList();
		myList.insertNode(4, 4);
		myList.displayList();
		myList.insertNode(-4, 5);
		myList.displayList();
		System.out.println(myList.findNode(2).getData());
		myList.removeNode(1);
		myList.displayList();
		myList.removeNode(4);
		myList.displayList();
	}

}

Node.java

public class Node {
	private double data;
	private Node next;
	
	public Node(double data) {
		this.data = data;
		this.next = null;
	}
	
	public double getData() {
		return this.data;
	}
	
	public Node getNext() {
		return this.next;
	}
	
	public void setNext(Node next) {
		this.next = next;
	}
}

创建和初始化链表

先观察 Node.java 里面的参数，是通过类（class）来实现链表的节点，这也是最优的实现方法。可以看到 Node 中 data 是链表节点的数据域，next 是指针域。因为指针域指向链表下一个节点，因此它的数据类型与当前节点一样还是 Node。

接下来就是这个类的构造方法，只需要给它的数据域赋值即可。下面的三个方法是为了满足封装需求而设立的。接下来返回 List.java 研究如何插入节点。根据 UML 图写 get/set 方法就不再说了。

判断节点是否为空

这个相对容易，只需判断头节点（head）是否为空即可

public boolean isEmpty() {
	if (head == null) {
		return true;
	} else {
		return false;
	}
}

插入节点

插入节点需要将前一个指针域的值赋到该节点的地址，而前面提到节点是通过类来表示，因此将插入节点这个类赋到前一个节点。

插入节点方法 insertNode 中传入两个参数，第一个是插入位置（index），第二个是数据。首先判断 index 是否小于 0，返回 null。接着定义一个变量 currIndex（当前索引）初始化为 1，一个变量 currNode（当前节点）初始化为链表的头节点。

接下来尝试定位插入节点的位置，使用 while 循环遍历节点，只要当前节点不为 null，且索引位置比当前位置数大就一直循环，每次循环让当前节点等于下一个节点的地址（使用 Node.java 中的 getNext 方法），同时让当前索引数加 1。

然后创建一个新节点，其数据域为 x（Node 构造方法）。

最后插入这个新节点，判断 index 是否等于 0，0 即为该链表的头节点，使用 setNext 方法，参数即为 head 头节点，让它等于新节点的指针域，让新节点成为头节点；如果不为 0，参数为下一节点的地址，让新节点的指针域为当前节点的指针域，设置当前节点的指针域为新节点即可。代码如下

public Node insertNode(int index, double x) {
	if(index < 0)
		return null;
	int currIndex = 1;
	Node currNode = this.head;
	while(currNode != null && index > currIndex) {
		currNode = currNode.getNext();
		currIndex ++;
	}		
	if(index > 0 && currNode == null)
		return null;
	
	Node newNode = new Node(x);
	if(index == 0) {
		newNode.setNext(this.head);
		this.head = newNode;
	}
	else {
		newNode.setNext(currNode.getNext());
		currNode.setNext(newNode);
	}
	return newNode;
}

寻找节点

这个也比较容易，findNode 会给你一个数据 x，让你从链表中找到一个数据域与其相同的节点。

只需要定义节点变量 currNode 等于头节点，当该节点不为空就一直遍历，再在其中加入判断看它是否与所给数据相同即可：相同就返回，不相同返回就当前节点的指针域。

public Node findNode(double x) {
	Node currNode = head;
	while (currNode != null)		
		if (currNode.getData() == x)
			return currNode;
		else
			currNode = currNode.getNext();
	return currNode;
}

删除节点

这个其实只需要将前节点指针域赋到后面节点的地址，中间的节点会被垃圾收集器（Garbage Collection） 自动回收并不再使用对象所占用的资源。

只是这样会出现特殊情况，即移除节点可能为当前链表的最后节点，因此需设置节点类型变量 lastNode，使其初始化为空。

依旧定义变量 currNode，依旧相同 while 循环。可以使用嵌套 if 语句：在当前节点不为空的情况下，如果当前节点数据等于所给数据 x，那么使头节点等于当前节点的下一节点，否则使 lastNode 的指针域等于当前节点的指针域。

如果当前节点为空，则使 lastNode 等于 currNode，让currNode 等于下个节点的地址，代码如下

public Node removeNode(double x) {
	Node currNode = head;
	Node lastNode = null;
	while (currNode != null) {
		if (currNode.getData() == x) {
			if (lastNode == null) {
				head = currNode.getNext();
			} else {
				lastNode.setNext(currNode.getNext());
			}
			return currNode;
		} else {
			lastNode=currNode;
			currNode = currNode.getNext();				
		}
	}
	return null;
}

展示节点

这个只需要按照 sample 写就好

依旧定义 currNode，依旧 while 循环，只要节点不为空就一直打印 “->” 最后把换行打出来即可

public void displayList() {
	Node currNode = head; 
	while (currNode != null) { 
		System.out.print(currNode.getData());
		if (currNode.getNext() != null)
			System.out.print(" -> ");
		currNode = currNode.getNext(); 
	}
	System.out.println();//c4
}

将上述代码添加到 List.java 中即可。