8.链队列
8.1定义
链队列：使用链式存储的队列，使用不带头结点head的单链表。
- front结点：队首元素
- rear结点：队尾元素
8.2链队列类
public class LinkQueue { private Node front; //队首（出队/删除） private Node rear; //队尾（入队/插入） }
8.4算法：链队列入队
分析：
非空
public void offer(Object x) { Node p = new Node(x); if(front == null) { //空 front = rear = p; //front = p; //rear = p; } else { //非空 rear.next = p; //1.尾指针的指针域指向新结点 rear = p; //2.尾指针指向队尾 } }
8.5算法：链队列出队
分析：空队列、一个元素、很多元素
- 很多元素
一个元素：需要额外的处理队尾，将其设置成null
空队列：返回null即可
public Object poll() { if(front != null) { //非空 Node p = front; //记录队首元素 front = front.next; //队首移动到下一个 if(p == rear) { //只有一个元素时，队首和队尾相同 rear = null; //队首已经是null，队尾也应该是null } return p.data; //返回之前队首元素的数据 } else { //空 return null; } }
9.优先级队列
9.1定义
优先级队列：就是一种带优先级的队列，也就是内部需要根据关键字的值进行排序的队列。
与普通队列基本操作一致，队首删除。
区别：进行==插入==操作时，不在是队尾，对队伍中找到合适的位置。
优先级队列也可以使用两种存取方式，但常用链式存储。
默认队列
插入操作：数字小的优先级越高
9.2优先级队列相关类
数据对象：数据元素的值、结点的优先级
/* { elem: a, priority: 1} */ public class PriorityData { public Object elem; //数据元素的值 public int priority; //结点的优先级 }
队列对象
public class PriorityQueue { private Node front; //队首 private Node rear; //队尾 }
数据之间关系
node.next //指针域
node.data //数据域，存放的数据类型是 PriorityData
9.3算法：优先级队列入队
- 需求：数字越==小==优先级越高。
- 分析：
- 前提：从队首进入，依次进行比较
- 情况1：队首插入（p如果指向队首front，表示新结点优先级的数字小）
情况2：队尾插入 （q为null 或 p等于队尾rear）
情况3：剩余的中间
public void offer(PriorityData x) { Node s = new Node(x); //构建新结点 // 如果空 if(front == null) { //空 front = rear = s; } else { //非空 // 1) 移动：按照优先级进行移动，优先级大就需要继续移动 Node p = front; //用于记录前驱（之前的） Node q = front; //用于记录下一个 while( q != null && (x.priority >= q.data.priority )) { p = q; //记录前驱 q = p.next; } // 2) 插入 if(q==front) { // 2.1 队首 s.next = front; //新结点s指向队首front front = s; //队首指针，指向队列的开始 } else if (q == null) { // 2.2 队尾 rear.next = s; //队尾指针域next,指向新结点 rear = s; //队尾指针，指向队尾 } else { // 2.3 中间 p.next = s; s.next = q; } } }
10.递归
10.1定义
- 程序调用自身的编程技巧称为递归（ recursion），由两部分组成：递推、回归。
- 递推：方法依次调用，没有返回。
- 回归：程序准备依次返回。
10.2算法：1-n和
package recursion; public class TestSum { public static void main(String[] args) { System.out.println(sum(10)); } /** * 求1-n的和 * @param n * @return */ private static int sum(int n) { if(n == 1) { return 1; } return n + sum(n-1); } }
10.3算法：n!
package recursion; public class TestFactorial { public static void main(String[] args) { System.out.println(factorial(4)); } private static int factorial(int n) { if(n == 1) { return 1; } return n * factorial(n-1); } }
10.4算法：斐波那契数
- 定义
0、1、1、2、3、5、8、13、21、34 .... n
固定值
f(0) = 0
f(1) = 1
后面的每一项都是前两项的和
f(2) = f(0) + f(1)
f(n) = f(n-1) + f(n-2)
算法
package recursion; public class TestFibonacci { public static void main(String[] args) { // 斐波那契数列 for(int i = 0 ; i <= 10 ; i ++) { System.out.print(fibonacci(i) + "、"); } } /** * 计算斐波那契数列的第n项 * f(0) = 0 * f(1) = 1 * ... * f(n) = f(n-1) + f(n-2) * @param n * @return */ private static int fibonacci(int n) { if(n == 0) { return 0; } if(n == 1) { return 1; } return fibonacci(n-1) + fibonacci(n-2); } }
