【学习笔记】递归与链表

数据结构和算法分析（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
	}
}

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

  1. 用较大的数除以较小的数，取余数。
  2. 用较小的数替代较大的数，用余数替代较小的数。
  3. 重复上述步骤，直到余数为 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中即可。