一、Java数据结构-循环链表的设计与实现
第1关 单循环链表的实现—链表的添加、遍历
package step1;
/**
* Created by sykus on 2018/1/15.
*/
public class MyCircleLinkedList {
private Node head;//头结点, 不存数据
private Node tail;//尾结点, 指向链表的最后一个节点
private int size;
public MyCircleLinkedList() {
head = new Node(Integer.MIN_VALUE, null);
head.next = head;
tail = head;
size = 0;
}
/**
* 添加到链表尾部
*
* @param item
*/
public void add(int item) {
/********** Begin *********/
Node node = new Node(item, tail.next);
tail.next = node;
tail = node;
++size;
/********** End *********/
}
/**
* 遍历链表并输出元素
*/
public void output() {
/********** Begin *********/
Node p = head;
while (p.next != head) {
p = p.next;
System.out.println(p.item);
}
/********** End *********/
}
public boolean isEmpty() {
return head.next == head;
}
public int size() {
return size;
}
//结点内部类
private static class Node {
int item;
Node next;
Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
第2关 单循环链表的实现—链表的删除
package step2;
/**
* Created by sykus on 2018/1/15.
*/
public class MyCircleLinkedList {
private Node head;//头结点, 不存数据
private Node tail;//尾结点, 指向链表的最后一个节点
private int size;
public MyCircleLinkedList() {
head = new Node(Integer.MIN_VALUE, null);
head.next = head;
tail = head;
size = 0;
}
/**
* 添加到链表尾部
*
* @param item
*/
public void add(int item) {
Node node = new Node(item, tail.next);
tail.next = node;
tail = node;
++size;
}
/**
* 遍历链表并输出元素
*/
public void output() {
Node p = head;
while (p.next != head) {
p = p.next;
System.out.println(p.item);
}
}
/**
* 删除从头结点开始的第index个结点
* index从0开始
*
* @param index
* @return
*/
public int remove(int index) {
checkPosIndex(index);
/********** Begin *********/
Node f = head;
while ((index--) > 0) {
f = f.next;
}
Node del = f.next;
if (del == tail) {
//要删除的是尾结点
tail = f;//使tail依然指向末尾结点
}
f.next = del.next;
del.next = null;
int oldVal = del.item;
del = null;
--size;
return oldVal;
/********** End *********/
}
public boolean isEmpty() {
return head.next == head;
}
public int size() {
return size;
}
private void checkPosIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
//结点内部类
private static class Node {
int item;
Node next;
Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
第3关 双向循环链表的实现—链表的插入
package step3;
/**
* Created by sykus on 2018/1/15.
*/
public class MyDoubleLinkedList {
private Node head;//头结点
private Node tail;//指向链表的尾结点
private int size;
public MyDoubleLinkedList() {
head = new Node(null, Integer.MIN_VALUE, null);
head.next = head.prev = head;
tail = head;
size = 0;
}
/**
* 添加元素到表尾
*
* @param item
*/
public void add(int item) {
/********** Begin *********/
Node newNode = new Node(null, item, null);
tail.next = newNode;
newNode.prev = tail;
newNode.next = head;
head.prev = newNode;
tail = newNode;
++size;
/********** End *********/
}
/**
* 打印双向链表
*
* @param flag true从左向右顺序打印, false从右向左顺序打印
*/
public void printList(boolean flag) {
Node f = head;
if (flag) {
//向右
while (f.next != head) {
f = f.next;
System.out.print(f.item + " ");
}
} else {
//向左
while (f.prev != head) {
f = f.prev;
System.out.print(f.item + " ");
}
}
}
public int size() {
return size;
}
//结点内部类
private static class Node {
int item;
Node next;//直接后继引用
Node prev;//直接前驱引用
Node(Node prev, int item, Node next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
}
第4关：双向循环链表的实现—链表的删除
package step4;
/**
* Created by sykus on 2018/1/15.
*/
public class MyDoubleLinkedList {
private Node head;//头结点
private Node tail;//指向链表的尾结点
private int size;
public MyDoubleLinkedList() {
head = new Node(null, Integer.MIN_VALUE, null);
head.next = head.prev = head;
tail = head;
size = 0;
}
/**
* 添加元素到表尾
*
* @param item
*/
public void add(int item) {
Node newNode = new Node(null, item, null);
tail.next = newNode;
newNode.prev = tail;
newNode.next = head;
head.prev = newNode;
tail = newNode;
++size;
}
/**
* 删除指定位置index出的结点，并返回其值
*
* @param index
* @return
*/
public int remove(int index) {
checkPosIndex(index);//
/********** Begin *********/
Node p = head.next;
while ((index--) > 0) {
p = p.next;
}
if (p == tail) {
tail = p.prev;
}
p.prev.next = p.next;
p.next.prev = p.prev;
int val = p.item;
p = null;
--size;
return val;
/********** End *********/
}
/**
* 打印双向链表
*
* @param flag true从左向右顺序打印, false从右向左顺序打印
*/
public void printList(boolean flag) {
Node f = head;
if (flag) {
//向右
while (f.next != head) {
f = f.next;
System.out.print(f.item + " ");
}
} else {
//向左
while (f.prev != head) {
f = f.prev;
System.out.print(f.item + " ");
}
}
}
public int size() {
return size;
}
private void checkPosIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
//结点内部类
private static class Node {
int item;
Node next;//直接后继引用
Node prev;//直接前驱引用
Node(Node prev, int item, Node next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
}
二、Java数据结构-线性表的设计与实现
第1关：顺序表的实现之增删功能
package step1;
/**
* Created by zengpeng on 2017/12/25.
*/
public class MyArrayList {
private int[] elements;//元素
private int size;//List中当前的元素个数
public MyArrayList() {
this(1);//List默认大小为1
}
/**
* 按指定大小capacity构造List
*
* @param capacity List初始化时的大小
*/
public MyArrayList(int capacity) {
elements = new int[capacity];
size = 0;
}
/**
* 返回List中元素的个数
*
* @return
*/
public int size() {
return size;
}
/**
* 添加一个元素到末尾
*
* @param item
*/
public void Add(int item) {
int len = elements.length;
if (size == len - 1) {
resize(2 * len);
}
/********** Begin *********/
elements[size++] = item;
/********** End *********/
}
/**
* 添加一个元素到指定位置index
*
* @param index
* @param item
*/
public void Add(int index, int item) {
validateRangeForAdd(index);
int len = elements.length;
if (size == len - 1) {
resize(2 * len);
}
/********** Begin *********/
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = item;
size++;
/********** End *********/
}
/**
* 删除指定位置index的元素,并返回被删除的元素
*
* @param index
* @return
*/
public int remove(int index) {
validateRange(index);
/********** Begin *********/
int oldVal=elements[index];
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
--size;
return oldVal;
/********** End *********/
}
/**
* 校验索引范围
*
* @param index
*/
private void validateRange(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
}
}
/**
* 校验索引范围
*
* @param index
*/
private void validateRangeForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
}
/**
* 动态扩展数组大小
*
* @param capacity
*/
private void resize(int capacity) {
assert capacity > size;
int[] tmp = new int[capacity];
for (int i = 0; i < size; i++) {
tmp[i] = elements[i];
}
elements = tmp;
}
}
第2关： 顺序表的实现之查询功能
package step2;
/**
* Created by zengpeng on 2017/12/25.
*/
public class MyArrayList {
private int[] elements;//元素
private int size;//List中当前的元素个数
public MyArrayList() {
this(1);//List默认大小为1
}
/**
* 按指定大小capacity构造List
*
* @param capacity List初始化时的大小
*/
public MyArrayList(int capacity) {
elements = new int[capacity];
size = 0;
}
/**
* 返回List中元素的个数
*
* @return
*/
public int size() {
return size;
}
/**
* 添加一个元素到末尾
*
* @param item
*/
public void Add(int item) {
int len = elements.length;
if (size == len - 1) {
resize(2 * len);
}
elements[size++] = item;
}
/**
* 添加一个元素到指定位置index
*
* @param index
* @param item
*/
public void Add(int index, int item) {
validateRangeForAdd(index);
int len = elements.length;
if (size == len - 1) {
resize(2 * len);
}
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = item;
size++;
}
/**
* 删除指定位置index的元素,并返回被删除的元素
*
* @param index
* @return 被删除的元素
*/
public int remove(int index) {
validateRange(index);
int oldVal = elements[index];
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
--size;
return oldVal;
}
/**
* 返回表中下标为index的元素
* @param index 下标
* @return
*/
public int get(int index) {
validateRange(index);
/********** Begin *********/
return elements[index];
/********** End *********/
}
/**
* 校验索引范围
*
* @param index
*/
private void validateRange(int index) {
if (index >= size || index < 0) {
throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
}
}
/**
* 校验索引范围
*
* @param index
*/
private void validateRangeForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
}
/**
* 动态扩展数组大小
*
* @param capacity
*/
private void resize(int capacity) {
assert capacity > size;
int[] tmp = new int[capacity];
for (int i = 0; i < size; i++) {
tmp[i] = elements[i];
}
elements = tmp;
}
}
第3关：单链表的实现之增删功能
package step3;
/**
* Created by zengpeng on 2017/12/25.
*/
public class MyLinkedList {
private Node first;//头结点，不存数据
private Node last;//指向链表的最后一个节点
private int size;
public MyLinkedList() {
size = 0;
first = new Node(0, null);
last = null;
}
/**
* 添加到链表尾部
*
* @param item
*/
public void add(int item) {
/********** Begin *********/
final Node l = last;
final Node node = new Node(item, null);
last = node;
if (first.next == null) {
//首次添加
first.next = node;
} else {
l.next = node;
}
++size;
/********** End *********/
}
/**
* 添加数据item到指定位置index
* index从0开始
* @param index
* @param item
*/
public void add(int index, int item) {
checkPosIndex(index);
/********** Begin *********/
int n = index;
Node l = first;
while ((n--) > 0) {
l = l.next;
}
final Node node = new Node(item, null);
if (null == first.next) {
//首次添加
last = node;
}
node.next = l.next;
l.next = node;
++size;
/********** End *********/
}
/**
* 删除指定位置index处的元素并返回, index从0开始
* @param index
* @return
*/
public int remove(int index) {
checkPosIndex(index);
/********** Begin *********/
Node f = first;
while ((index--) > 0) {
f = f.next;
}
Node del = f.next;
if (del == last) {
//删除最后一个元素
last = f;
}
f.next = del.next;
del.next = null;
int oldVal = del.item;
del = null;
--size;
return oldVal;
/********** End *********/
}
public int size() {
return size;
}
private void checkPosIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
//结点内部类
private static class Node {
int item;
Node next;
Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
第4关：单链表的实现之查询功能
package step4;
/**
* Created by zengpeng on 2017/12/25.
*/
public class MyLinkedList {
private Node first;//头结点，不存数据
private Node last;//指向链表的最后一个节点
private int size;
public MyLinkedList() {
size = 0;
first = new Node(0, null);
last = null;
}
/**
* 添加到链表尾部
*
* @param item
*/
public void add(int item) {
final Node l = last;
final Node node = new Node(item, null);
last = node;
if (first.next == null) {
//首次添加
first.next = node;
} else {
l.next = node;
}
++size;
}
/**
* 添加数据item到指定位置index
* index从0开始
* @param index
* @param item
*/
public void add(int index, int item) {
checkPosIndex(index);
int n = index;
Node l = first;
while ((n--) > 0) {
l = l.next;
}
final Node node = new Node(item, null);
if (null == first.next) {
//首次添加
last = node;
}
node.next = l.next;
l.next = node;
++size;
}
/**
* 删除指定位置index处的元素并返回, index从0开始
* @param index
* @return
*/
public int remove(int index) {
checkPosIndex(index);
Node f = first;
while ((index--) > 0) {
f = f.next;
}
Node del = f.next;
if (del == last) {
//删除最后一个元素
last = f;
}
f.next = del.next;
del.next = null;
int oldVal = del.item;
del = null;
--size;
return oldVal;
}
/**
* 获取链表中第index个元素
* @param index
* @return
*/
public int get(int index) {
checkPosIndex(index);
/********** Begin *********/
Node f = first.next;
while ((index--) > 0) {
f = f.next;
}
int val = f.item;
return val;
/********** End *********/
}
public int size() {
return size;
}
private void checkPosIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
//结点内部类
private static class Node {
int item;
Node next;
Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
三、Java 数据结构之栈、队列
第1关：实现基于数组的栈
package step1;
import java.util.NoSuchElementException;
/**
* Created by sykus on 2018/1/26.
*/
public class MyStack<T> {
private T[] S;
private int top;//栈顶元素下标，初始为-1
public MyStack() {
this(1);
}
public MyStack(int capacity) {
S = (T[]) new Object[capacity];
top = -1;
}
/**
* 入栈操作，把item压入栈中
*
* @param item
*/
public void push(T item) {
int len = S.length;
if (top == len - 1) {
resize(2 * len);
}
/********** Begin *********/
S[++top] = item;
/********** End *********/
}
/**
* 返回栈顶元素并从栈中移除
*
* @return
*/
public T pop() {
if (isEmpty()) {
throw new NoSuchElementException("栈为空！");
}
/********** Begin *********/
T val = S[top--];
return val;
/********** End *********/
}
/**
* 判断栈是否为空
*
* @return
*/
public boolean isEmpty() {
if (top < 0)
return true;
else
return false;
}
/**
* 动态扩展数组大小
*
* @param capacity
*/
private void resize(int capacity) {
assert capacity > top;
T[] tmp = (T[]) new Object[capacity];
for (int i = 0; i <= top; i++) {
tmp[i] = S[i];
}
S = tmp;
}
}
第2关：实现基于链表的栈
package step2;
import java.util.NoSuchElementException;
/**
* Created by sykus on 2017/12/29.
*/
public class MyStack<E> {
private Node<E> head;//头结点
private Node<E> top;//栈顶
private int size;//栈中元素个数
public MyStack() {
head = new Node<E>();
head.next = null;
top = null;//栈顶初始化为null
size = 0;
}
/**
* 把item压入栈中
*
* @param item
*/
public void push(E item) {
/********** Begin *********/
Node<E> newNode = new Node<E>();
newNode.item = item;
newNode.next = head.next;
head.next = newNode;
top = newNode;
++size;
/********** End *********/
}
/**
* 返回它栈顶元素并删除
*/
public E pop() {
if (isEmpty())
throw new NoSuchElementException("栈为空！");
/********** Begin *********/
Node<E> node = top;
top = top.next;
head.next = top;
node.next = null;
--size;
return node.item;
/********** End *********/
}
/**
* 返回栈中元素个数
*
* @return
*/
public int size() {
return size;
}
/**
* 判断一个栈是否为空
*
* @return
*/
public boolean isEmpty() {
return (null == head);
}
//链表结点内部类
private static class Node<E> {
private E item;
private Node<E> next;
}
}
第3关：基于数组的队列
package step3;
/**
* Created by zengpeng on 2018/1/30.
*/
public class MyQueue<T> {
private T[] Q;
private int head;
private int tail;
private int size;
public MyQueue() {
this(1);
}
public MyQueue(int capacity) {
Q = (T[]) new Object[capacity];
size = 0;
head = tail = 0;
}
/**
* 入队操作
*
* @param item
*/
public void enqueue(T item) {
/********** Begin *********/
Q[tail] = item;
tail = (tail + 1) % Q.length;
++size;
/********** End *********/
}
/**
* 出队操作
*
* @return
*/
public T dequeue() {
/********** Begin *********/
T val = Q[head];
head = (head + 1) % Q.length;
--size;
return val;
/********** End *********/
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty() {
return (head == tail) && (size < Q.length);
}
public int size() {
return size;
}
}
第4关：基于链表的队列
package step4;
import java.util.NoSuchElementException;
/**
* Created by sykus on 2017/12/29.
*/
public class MyQueue<T> {
private Node<T> head;// 头结点，不存数据
private Node<T> front;//指向队头结点
private Node<T> tail;//指向队尾结点
private int size;
public MyQueue() {
head = new Node<T>();
front = tail = null;
size = 0;
}
/**
* 入队
*
* @param item
*/
public void enqueue(T item) {
/********** Begin *********/
Node<T> oldTail = tail;
Node<T> newNode = new Node<T>();
newNode.item = item;
newNode.next = null;
if (null == front) {
//空队列
head.next = newNode;
front = newNode;
} else {
oldTail.next = newNode;
}
tail = newNode;
++size;
/********** End *********/
}
/**
* 出队
*
* @return
*/
public T dequeue() {
if (isEmpty())
throw new NoSuchElementException("队列为空！");
/********** Begin *********/
T val = front.item;
head.next = front.next;
front.next = null;
front = head.next;//此时队头为后继结点
--size;
if (null == head.next) {
//出队的是队列中的最后一个元素
front = tail = null;
}
return val;
/********** End *********/
}
/**
* 返回队列中元素数量
*
* @return
*/
public int size() {
return size;
}
/**
* 判断一个队列是否为空
*
* @return
*/
public boolean isEmpty() {
return (front == null);
}
/**
* 链表结点内部类
*/
private static class Node<E> {
private E item;
private Node<E> next;
}
}
四、Java 数据结构之二叉搜索树
第1关：二叉搜索树的介绍与构建
package step1;
/**
* Created by zengpeng on 2018/3/3.
*/
public class BSTree {
private TreeNode root;//根结点
public BSTree() {
root = null;
}
/**
* 向树root中插入key
*
* @param key 要插入的值
*/
public void insert(int key) {
/********** Begin *********/
TreeNode x = root;
TreeNode p = null;//始终指向x的父结点
while (x != null) {
p = x;
if (key < x.item) {
x = x.leftChild;
} else {
x = x.rightChild;
}
}
if (null == p) {
//空树
root = new TreeNode(key);
} else if (key < p.item) {
p.leftChild = new TreeNode(key);
} else {
p.rightChild = new TreeNode(key);
}
/********** End *********/
}
/**
* 前序遍历
*/
public void preOrder() {
preOrder(root);
}
/**
* 中序遍历
*/
public void inOrder() {
inOrder(root);
}
/**
* 后序遍历
*/
public void postOrder(){
postOrder(root);
}
private void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.item + " ");
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
private void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.leftChild);
System.out.print(node.item + " ");
inOrder(node.rightChild);
}
}
private void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.item + " ");
}
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
第2关：二叉搜索树的删除
package step2;
/**
* Created by zengpeng on 2018/3/14.
*/
public class BSTree {
private TreeNode root;//根结点
public BSTree() {
root = null;
}
/**
* 向树root中插入a
*
* @param key 要插入的值
*/
public void insert(int key) {
TreeNode x = root;
TreeNode p = null;//始终指向x的父结点
while (x != null) {
p = x;
if (key < x.item) {
x = x.leftChild;
} else {
x = x.rightChild;
}
}
if (null == p) {
//空树
root = new TreeNode(key);
} else if (key < p.item) {
p.leftChild = new TreeNode(key);
} else {
p.rightChild = new TreeNode(key);
}
}
/**
* 在树root中删除结点key
*
* @param key
* @return
*/
public void delete(int key) {
root = delete(root, key);
}
private TreeNode delete(TreeNode x, int key) {
/********** Begin *********/
if (x == null) {
return null;
}
if (key < x.item) {
x.leftChild = delete(x.leftChild, key);
} else if (key > x.item) {
x.rightChild = delete(x.rightChild, key);
} else {
if (x.leftChild == null) return x.rightChild;
if (x.rightChild == null) return x.leftChild;
TreeNode t = x;
x = min(t.rightChild);
x.rightChild = deleteMin(t.rightChild);
x.leftChild = t.leftChild;
}
return x;
/********** End *********/
}
/**
* 删除树x中的最小结点
*
* @param x
* @return
*/
private TreeNode deleteMin(TreeNode x) {
if (x.leftChild == null) return x.rightChild;
x.leftChild = deleteMin(x.leftChild);
return x;
}
/**
* 查找树x中的最小结点
*
* @param x
* @return
*/
private TreeNode min(TreeNode x) {
TreeNode p = x;
while (p.leftChild != null) {
p = p.leftChild;
}
return p;
}
public void preOrder() {
preOrder(root);
}
private void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.item + " ");
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
public void inOrder() {
inOrder(root);
}
private void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.leftChild);
System.out.print(node.item + " ");
inOrder(node.rightChild);
}
}
public void postOrder() {
postOrder(root);
}
private void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.item + " ");
}
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
第3关：二叉搜索树的查找
package step3;
/**
* Created by zengpeng on 2018/3/14.
*/
public class BSTree {
private TreeNode root;//根结点
public BSTree() {
root = null;
}
/**
* 向树root中插入a
*
* @param key 要插入的值
*/
public void insert(int key) {
TreeNode x = root;
TreeNode p = null;//始终指向x的父结点
while (x != null) {
p = x;
if (key < x.item) {
x = x.leftChild;
} else {
x = x.rightChild;
}
}
if (null == p) {
//空树
root = new TreeNode(key);
} else if (key < p.item) {
p.leftChild = new TreeNode(key);
} else {
p.rightChild = new TreeNode(key);
}
}
/**
* 判断树root中是否包含key，包含则返回true，不包含返回false
*
* @param key
* @return
*/
public boolean search(int key) {
/********** Begin *********/
TreeNode p = root;
while (p != null && key != p.item) {
if (key < p.item) {
p = p.leftChild;
} else {
p = p.rightChild;
}
}
if (p == null) {
return false;
} else {
return true;
}
/********** End *********/
}
/**
* 在树root中删除结点key
*
* @param key
* @return
*/
public void delete(int key) {
root = delete(root, key);
}
private TreeNode delete(TreeNode x, int key) {
if (x == null) {
return null;
}
if (key < x.item) {
x.leftChild = delete(x.leftChild, key);
} else if (key > x.item) {
x.rightChild = delete(x.rightChild, key);
} else {
if (x.leftChild == null) return x.rightChild;
if (x.rightChild == null) return x.leftChild;
TreeNode t = x;
x = min(t.rightChild);
x.rightChild = deleteMin(t.rightChild);
x.leftChild = t.leftChild;
}
return x;
}
/**
* 删除树x中的最小结点
* @param x
* @return
*/
private TreeNode deleteMin(TreeNode x) {
if (x.leftChild == null) return x.rightChild;
x.leftChild = deleteMin(x.leftChild);
return x;
}
/**
* 查找树x中的最小结点
*
* @param x
* @return
*/
private TreeNode min(TreeNode x) {
TreeNode p = x;
while (p.leftChild != null) {
p = p.leftChild;
}
return p;
}
public void preOrder() {
preOrder(root);
}
public void inOrder() {
inOrder(root);
}
public void postOrder() {
postOrder(root);
}
private void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.item + " ");
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
private void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.leftChild);
System.out.print(node.item + " ");
inOrder(node.rightChild);
}
}
private void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.item + " ");
}
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
五、Java 数据结构之二叉树
第1关：二叉树的实现之前序遍历
package step1;
/**
* Created by zengpeng on 2018/2/9.
*/
public class BinaryTree {
private TreeNode root;//根节点
public BinaryTree() {
root = null;
}
public void preOrder(TreeNode root) {
/********** Begin *********/
if (root == null) {
return;
}
System.out.println(root.item);
preOrder(root.leftChild);
preOrder(root.rightChild);
/********** End *********/
}
/**
* 以数组arr从左至右构建二叉树
*
* @param arr
* @param n
* @return
*/
public TreeNode createTree(int arr[]) {
TreeNode tmp[] = new TreeNode[arr.length + 1];
for (int k = 1; k <= arr.length; k++) {
TreeNode node = new TreeNode(arr[k - 1]);
tmp[k] = node;
if (k == 1) {
root = node;
} else {
int j = k / 2;
if (k % 2 == 0) {
tmp[j].leftChild = node;
} else {
tmp[j].rightChild = node;
}
}
}
return root;
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
第2关：二叉树的实现之中序遍历
package step2;
/**
* Created by zengpeng on 2018/2/12.
*/
public class BinaryTree {
private TreeNode root;//根节点
public BinaryTree() {
root = null;
}
public void inOrder(TreeNode root) {
/********** Begin *********/
if (root == null) {
return;
}
inOrder(root.leftChild);
System.out.println(root.item);
inOrder(root.rightChild);
/********** End *********/
}
/**
* 根据二叉树的性质，以数组arr从左至右构建一颗满二叉树
*
* @param arr
* @param n
* @return
*/
public TreeNode createTree(int arr[]) {
TreeNode tmp[] = new TreeNode[arr.length + 1];
for (int k = 1; k <= arr.length; k++) {
TreeNode node = new TreeNode(arr[k - 1]);
tmp[k] = node;
if (k == 1) {
root = node;
} else {
int j = k / 2;
if (k % 2 == 0) {
tmp[j].leftChild = node;
} else {
tmp[j].rightChild = node;
}
}
}
return root;
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
第3关 二叉树的实现之后序遍历
package step3;
/**
* Created by zengpeng on 2018/2/12.
*/
public class BinaryTree {
private TreeNode root;//根节点
public BinaryTree() {
root = null;
}
public void postOrder(TreeNode root) {
/********** Begin *********/
if (root == null) {
return;
}
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.println(root.item);
/********** End *********/
}
/**
* 根据二叉树的性质，以数组arr从左至右构建一颗满二叉树
*
* @param arr
* @param n
* @return
*/
public TreeNode createTree(int arr[]) {
TreeNode tmp[] = new TreeNode[arr.length + 1];
for (int k = 1; k <= arr.length; k++) {
TreeNode node = new TreeNode(arr[k - 1]);
tmp[k] = node;
if (k == 1) {
root = node;
} else {
int j = k / 2;
if (k % 2 == 0) {
tmp[j].leftChild = node;
} else {
tmp[j].rightChild = node;
}
}
}
return root;
}
public static class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private int item;
public TreeNode(int item) {
this(null, null, item);
}
public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.item = item;
}
}
}
六、Java 数据结构之排序
第1关：选择排序
package step1;
/**
* Created by sykus on 2018/3/20.
*/
public class SelectionSort {
/**
* 选择排序
*
* @param arr
*/
public static void sort(int arr[]) {
/********** Begin *********/
for (int i = 0; i < arr.length-1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
print(arr);
}
/********** End *********/
}
private static void print(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
第2关 插入排序
package step2;
/**
* Created by sykus on 2018/3/20.
*/
public class InsertionSort {
public static void sort(int arr[]) {
/********** Begin *********/
for (int i = 1; i < arr.length; i++) {
int j = i;
int tmp = arr[j];
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
print(arr);
}
/********** End *********/
}
private static void print(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
第3关 归并排序
package step3;
/**
* Created by sykus on 2018/3/20.
*/
public class MergeSort {
/**
* lo, hi都是指下标
*/
public static void sort(int arr[], int lo, int hi) {
if (lo < hi) {
int mid = (lo + hi) / 2;
sort(arr, lo, mid);
sort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
print(arr);
}
}
private static void merge(int arr[], int p, int q, int r) {
/********** Begin *********/
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1 + 1];
int R[] = new int[n2 + 1];
for (int i = 0; i < n1; i++) {
L[i] = arr[p + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[q + j + 1];
}
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for (int k = p; k <= r; k++) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
}
/********** End *********/
}
private static void print(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
第4关 快速排序
package step4;
/**
* Created by sykus on 2018/3/20.
*/
public class QuickSort {
public void sort(int arr[], int low, int high) {
/********** Begin *********/
int i = low;
int j = high + 1;
int povit = arr[low];
while (i < j) {
while (j > low && arr[--j] >= povit) ;
while (i < high && arr[++i] <= povit) ;
if (i>=j)break;
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
print(arr);
}
int temp = arr[j];
arr[j] = arr[low];
arr[low] = temp;
print(arr);
if (i > low) sort(arr, low, j - 1);
if (j < high) sort(arr, j + 1, high);
/********** End *********/
}
private static void print(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
第5关 堆排序
package step5;
/**
* Created by sykus on 2018/3/20.
*/
public class HeapSort {
public static void sort(int arr[]) {
/********** Begin *********/
int n = arr.length;
for (int k = n / 2; k >= 1; k--) {
int l = k;
while (2 * l <= n) {
int j = 2 * l;
if (j < n && arr[j - 1] < arr[j + 1 - 1]) j++;
if (arr[l - 1] > arr[j - 1]) break;
int tmp = arr[l - 1];
arr[l - 1] = arr[j - 1];
arr[j - 1] = tmp;
l = j;
}
}
while (n > 1) {
int tmp = arr[0];
arr[0] = arr[n - 1];
arr[n - 1] = tmp;
int k = 1;
n--;
while (2 * k <= n) {
int j = 2 * k;
if (j < n && arr[j - 1] < arr[j]) j++;
if (arr[k - 1] > arr[j - 1]) break;
tmp = arr[k - 1];
arr[k - 1] = arr[j - 1];
arr[j - 1] = tmp;
k = j;
}
print(arr);
}
/********** End *********/
}
private static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
七、Java 数据结构之图
第1关 图的表示
package step1;
import java.util.ArrayList;
public class Graph {
private int V;//顶点数
private int E;//边数
private ArrayList<Integer>[] adj;//邻接表
public Graph(int v) {
if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
V = v;
E = 0;
adj = new ArrayList[V + 1];
for (int i = 0; i <= this.V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
/********** Begin *********/
adj[v].add(w);
adj[w].add(v);
E++;
/********** End *********/
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " 个顶点, " + E + " 条边\n");
for (int v = 1; v <= V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append("\n");
}
return s.toString();
}
}
第2关 深度优先搜索
package step2;
import java.util.ArrayList;
public class DFSGraph {
private boolean[] marked;
private int V;//顶点数
private int E;//边数
private ArrayList<Integer>[] adj;//邻接表
public DFSGraph(int v) {
if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
V = v;
E = 0;
adj = new ArrayList[V + 1];
marked = new boolean[V + 1];
for (int i = 0; i <= this.V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public void DFS(int v) {
/********** Begin *********/
marked[v] = true;
System.out.print(v + " ");
for (int w : adj[v]) {
if (!marked[w]) {
DFS(w);
}
}
/********** End *********/
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " 个顶点, " + E + " 条边\n");
for (int v = 1; v <= V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append("\n");
}
return s.toString();
}
}
第3关 广度优先搜索
package step3;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BFSGraph {
private int V;//顶点数
private int E;//边数
private boolean[] marked;
private ArrayList<Integer>[] adj;//邻接表
public BFSGraph(int v) {
if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
V = v;
E = 0;
adj = new ArrayList[V + 1];
marked = new boolean[V + 1];
for (int i = 0; i <= this.V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public void BFS(int s) {
/********** Begin *********/
Queue<Integer> que = new LinkedList<>();
que.offer(s);
marked[s] = true;
while (!que.isEmpty()) {
int v = que.poll();
System.out.print(v + " ");
for (int w : adj[v]) {
if (!marked[w]) {
que.offer(w);
marked[w] = true;
}
}
}
/********** End *********/
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " 个顶点, " + E + " 条边\n");
for (int v = 1; v <= V; v++) {
s.append(v + ": ");
for (int w : adj[v]) {
s.append(w + " ");
}
s.append("\n");
}
return s.toString();
}
}
第4关 单源最短路径
package step4;
import java.util.*;
public class ShortestPath {
private int V;//顶点数
private int E;//边数
private int[] dist;
private ArrayList<Integer>[] adj;//邻接表
private int[][] weight;//权重
public ShortestPath(int v, int e) {
V = v;
E = e;
dist = new int[V + 1];
adj = new ArrayList[V + 1];
weight = new int[V + 1][V + 1];
for (int i = 0; i <= this.V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int u, int v, int w) {
adj[u].add(v);
adj[v].add(u);
weight[u][v] = weight[v][u] = w;
}
public int[] Paths(int source) {
/********** Begin *********/
Queue<Integer> Q = new LinkedList<Integer>();
dist[source] = 0;
for (int i = 1; i <= V; i++) {
if (i != source) {
dist[i] = Integer.MAX_VALUE;
}
Q.offer(i);
}
while (!Q.isEmpty()) {
int minV = Integer.MAX_VALUE;
int v = source;
for (int i = 0; i < Q.size(); i++) {
int index = ((LinkedList<Integer>) Q).get(i);
if (dist[index] < minV) {
minV = dist[index];
v = index;
}
}
Q.poll();
Q.remove(v);
for (int u : adj[v]) {
int alt = dist[v] + weight[v][u];
if (alt < dist[u]) {
dist[u] = alt;
}
}
}
return dist;
/********** End *********/
}
/**
* 打印源点到所有顶点的距离，INF为无穷大
*
* @param dist
*/
public void print(int[] dist) {
for (int i = 1; i <= V; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i] + " ");
}
}
}
}
最后的图的代码来只班级内同学的支持！！
文章浏览阅读1.3k次。# -*- coding: utf-8 -*-"""@File : 200113_等比例调整图像分辨率大小.py@Time : 2020/1/13 13:38@Author : Dontla@Email : [email protected]@Software: PyCharm"""import cv2def img_resize(image):height, width = image...._opencv小图等比例缩放
文章浏览阅读42次。对于这些调制技术的误码率（BER）研究是非常重要的，因为它们可以帮助我们了解在不同信道条件下系统的性能表现。通过以上步骤，您可以进行OFDM、OOK、PPM和QAM的误码率仿真研究，并绘制它们的误码率曲线，以便更好地了解它们在不同信道条件下的性能特点。针对这些调制技术的BER研究是非常重要的，可以帮助我们更好地了解这些技术在不同信道条件下的性能表现，从而指导系统设计和优化。6. 分析结果：根据误码率曲线的比较，分析每种调制方案在不同信噪比条件下的性能，包括其容忍的信道条件和适用的应用场景。_ber仿真
文章浏览阅读2.5w次，点赞3次，收藏3次。1、场景照抄官方的实例，绑定了 myData.Age 这个值。实际选择某个日期后，从 vuetool（开发工具）看，值已经更新了，但视图未更新。2、尝试绑定另一个值： myData，可以正常的触发 @change 方法。可能是：值绑定到子对象时，组件没有侦测到。3、解决使用 @blur 代替 @change 方法。再判断下 “值有没有更新” 即可。如有更好的方法，欢迎评论！..._el-date-picker @change不触发
文章浏览阅读1.5k次，点赞2次，收藏8次。Projectlnliersclass pcl: : Projectlnliers< PointT >类 Projectlnliers 使用一个模型和一组的内点的索引，将内点投影到模型形成新的一个独立点云。关键成员函数 void setModelType(int model) 通过用户给定的参数设置使用的模型类型 ，参数 Model 为模型类型（见 mo..._projectinliers
文章浏览阅读2.4k次。“System.BadImageFormatException”类型的未经处理的异常在 xxxx.exe 中发生其他信息: 未能加载文件或程序集“xxxxxxx, Version=xxxxxx,xxxxxxx”或它的某一个依赖项。试图加载格式不正确的程序。此原因是由于 ” 目标程序的目标平台与 依赖项的目标编译平台不一致导致，把所有的项目都修改到同一目标平台下（X86、X64或AnyCPU）进行编译，一般即可解决问题“。若果以上方式不能解决，可采用如下方式：右键选择配置管理器，在这里修改平台。_“system.badimageformatexception”类型的未经处理的异常在 未知模块。 中发生
文章浏览阅读2.4k次。记录一下碰到的问题：1.Assetbundle加载问题： 原PC打包后的AssetBundle导入安卓工程后，加载会出问题。同时工程打包APK时,StreamingAssets中不能有中文。解决方案： （1）.加入PinYinConvert类，用于将中文转换为拼音（多音字可能会出错，例如空调转换为KongDiao||阿拉伯数字不支持，如Ⅰ、Ⅱ、Ⅲ、Ⅳ(IIII)、Ⅴ、Ⅵ、Ⅶ、Ⅷ、Ⅸ、Ⅹ..._电脑软件移植安卓
文章浏览阅读2.4k次。话不多说参考书籍 汪文君补充知识：start是异步，run是同步，start的执行会经过JNI方法然后被任务执行调度器告知给系统内核分配时间片进行创建线程并执行，而直接调用run不经过本地方法就是普通对象执行实例方法。什么是线程？1.现在几乎百分之百的操作系统都支持多任务的执行，对计算机来说每一个人物就是一个进程（Process）,在每一个进程内部至少要有一个线程实在运行中，有时线..._start 是同步还是异步
文章浏览阅读5.3k次，点赞9次，收藏34次。我主要用了层次选择器和属性选择器可以随意选择，方便简单为主大体CSS格式 大家自行构造网页主体<body> <div class='main' > <div class='left'> <img src="images/pic.gif" /> <br/><br/> <img src="images/col.gif" alt="收藏本片"/&_单击标题“非缘勿扰”,元素中有id属性的的文本(主演、导演、标签、剧情
文章浏览阅读2.2k次。完整的解决思路_no module named 'win32com
文章浏览阅读901次，点赞20次，收藏23次。浏览器是每台电脑的必装软件，去浏览器搜索资源和信息已经成为我们的日常，我媳妇儿原本也以为浏览器就是上网冲浪而已，哪有那么强大，但经过我的演示之后她惊呆了，直接给我竖起大拇指道：“原来浏览器还能这么用？大开眼界！今天来给大家介绍几款实用的浏览器插件，学会之后让你的浏览器“活过来”！_浏览器插件助手
文章浏览阅读101次。NumPy是Python中最常用的科学数学计算库之一，它提供了高效的多维数组对象以及对这些数组进行操作的函数NumPy的核心是ndarray（N-dimensional array）对象，它是一个用于存储同类型数据的多维数组Numpy通常与SciPy（Scientific Python）和 Matplotlib（绘图库）一起使用，用于替代MatLabSciPy是一个开源的Python算法库和数学工具包；Matplotlib是Python语言及其Numpy的可视化操作界面'''_数学中常用的环境有numpy
文章浏览阅读1.1w次。docker in docker说白了，就是在docker容器内启动一个docker daemon，对外提供服务。优点在于：镜像和容器都在一个隔离的环境，保持操作者的干净环境。想到了再补充 ：）一：低版本启动及访问启动1.12.6-dinddocker run --privileged -d --name mydocker docker:1.12.6-dind在其他容器访问d..._dind