基本数据结构(第二部分)（链队列循环队列的实现）

基本数据结构(第二部分)（链队列循环队列的实现）

2021.12.30

一：递归:(只是说一下，不作为正式内容)

递归的关键部分是核心计算加上边界条件

比如要计算斐波那契数列，可以使用迭代计算出来(保存数值和计算)。也可以用递归，设定边界值为1，从5开始，要计算5那里的值，就必须知道3和4位置的值，要知道3和4位置的值，就必须知道1 2 和 2 3位置的值，依此类推，在计算出所有基本的值过后，最后再顺推回去就可以知道5位置的值了。

package basic;

public class Recursion {

	public int ssum(int n) {
		int i = n;
		if(i == 0) {
			return 0;
		}
		return ssum(n-1)+n;
	}//简单求和
	
	public int ssum2(int n) {
		if(n==1) return 1;
		if(n==0) return 0;
		return ssum2(n-1)+ssum2(n-2);//核心思想就是数列前两项之和等于第三项。
		
	}//斐波那契数列求和
	
	public static void main(String[] args) {
		Recursion re = new Recursion();
		System.out.println(re.ssum(5));//创建对象调用ssum
		System.out.println(re.ssum2(5));
	}

}

15
5

2021.12.31

二: 链队列的实现:
Node 类以前是 linkdedList 的内嵌类, 这里重写了一遍. 访问控制的事情以后再说.
为方便 *** 作, 空队列也需要一个节点. 这和以前的链表同理. 头节点的引用 (指针) 称为 header.
入队仅 *** 作尾部, 出队仅 *** 作头部.

队列特点 : 先入先出，后入后出。
 

在完成时所遇到的问题，要保证start和head指向同一个地址，以后在进行 *** 作时不至于出错。做完之后我发现根本不需要多余的head节点。只需要start和end移动就行。添加元素时end移动，删除元素时start移动。

package basic;

public class linkedQueue {
//	Node2 start = new Node2();
//	Node2 end = new Node2();
//	Node2 head = new Node2();//地址是不同的。
	Node2 start;
	Node2 end;
	Node2 head;
	public linkedQueue(){
		head = new Node2();
		end = head;
		start = head;//和第一次有些不一样。这里要全部放在一个地址上才行。
	}
	
	public void Add(int elem){
		Node2 newnode = new Node2(elem);
		newnode.next = end.next;
		end.next = newnode;
		end = newnode;
	}//添加队列元素,end向后推移

	public int delete() {
		Node2 temp = new Node2();
		temp = start.next;
		if(start.next==null) {
			return -10086;
		}
		start = start.next;
		return temp.elem;
	}//删除队列元素
	
	public int length() {
		int length = 0;
		Node2 temp = start.next;
		while(temp!=end.next) {
			length++;
			temp = temp.next;
		}
		return length;
	}//获得链队列长度
	
	public void ShowQueue() {
		if(start.next==null) {
			System.out.println("当前没有元素!");
			return;
		}
		Node2 temp = start.next;
		System.out.print("列表元素:");
		while(temp!=end.next) {
			System.out.print(temp.elem+" ");
			temp = temp.next;
		}
		System.out.println("");
	}
	
	public static void main(String[] args) {
		linkedQueue link = new linkedQueue();
		System.out.println(link.length());
		link.Add(1);
		link.Add(2);
		link.Add(3);
		System.out.println(link.length());
		link.ShowQueue();
		link.delete();
		link.delete();
		link.delete();
		link.ShowQueue();
	}

}

class Node2{
	int elem;
	Node2 next;
	public Node2() {
		elem = 0;
		next = null;
	}
	public Node2(int i) {
		elem = i;
		next = null;
	}
	
}

0
3
列表元素:1 2 3 
当前没有元素!

三:循环队列的实现:

1:在打印循环队列时，注意不要将本来的start和end的数值改变了，要重新设置布局变量来帮助打印队列(我这里就设置的是start2和end2)。

2:循环队列可能会造成假溢出的情况(即end==start时可能为满或者为空，需要设置条件进行判断)，在这里的循环队列判断满时，我牺牲了一个数组位用来判满，剩下的情况就是判空了，即end==start是为空的情况。

3:个人觉得麻烦的是在添加删除数据时，如果前面的条件不写好的话，极其容易导致数组指针越界的错误。比如向后推移不单单是end++了，需要改进成（end+1）%MAX_SIZE让其一直在队列的数组当中。

以下是循环队列代码:

package basic;

public class CircleIntQueue {
	public static final int MAX_SIZE = 6;// 数组设置小一点方便测试,这里最多存储5个数
	int[] data;
	int start, end;

	public CircleIntQueue() {
		data = new int[MAX_SIZE];
		start = 0;
		end = 0;// 设置队列的前后,start删，end添
	}

	public void push(int elem) {
		if ((end + 1) % MAX_SIZE == start) {
			System.out.println("队列已满,插入失败!");
			return;
		} // 判满,照这样的话要牺牲一个位不能添加进元素
		data[end] = elem;
		end = (end + 1) % MAX_SIZE;
	}// 入队列
		// 0 1 2 3 4

	public int pop() {
		if (end == start) {
			System.out.println("队列为空，删除失败!");// 不会是添加时的情况，因为添加时的情况已经单独讨论了。
			return -10086;
		}
		int temp = data[start];
		start = (start + 1) % MAX_SIZE;
		return temp;
	}// 出队列

	public int length() {
		if (end >= start) {
			return end - start;
		} else if (end < start) {
			return end - start + MAX_SIZE;
		}
		return -1;
	}

	public void Show() {
		if (end == start) {
			System.out.println("队列无元素!");
		}
		System.out.print("队列元素如下：");
		int end2 = end;
		int start2 = start;
		while (end2 != start2) {
			System.out.print(data[start2] + " ");
			start2 = (start2 + 1) % MAX_SIZE;
		}
		System.out.println("");
	}

	public static void main(String[] args) {
		CircleIntQueue cir = new CircleIntQueue();
		System.out.println(cir.length());
		cir.push(1);
		cir.push(2);
		cir.push(3);
		cir.push(4);
		cir.push(5);
//		cir.push(10);
		cir.Show();
		System.out.println("元素个数:" + cir.length());
		cir.pop();
		cir.pop();
		cir.pop();
		System.out.println("元素个数:" + cir.length());
		cir.pop();
		cir.pop();
		System.out.println("元素个数:" + cir.length());
		cir.Show();
		cir.push(4);
		System.out.println("元素个数:" + cir.length());
		cir.push(10);
		System.out.println("元素个数:" + cir.length());
		cir.Show();
	}

}

0
队列元素如下：1 2 3 4 5 
元素个数:5
元素个数:2
元素个数:0
队列无元素!
队列元素如下：
元素个数:1
元素个数:2
队列元素如下：4 10 

插一条最近背单词情况:

 今日完毕

2022.1.1