基础数据结构，动手写一遍
2018-10-25 本文已影响0人
啦啦哇哈哈
动态Array
从最基本的动态Array开始实现（实际上可以理解成自己动手实现了个ArrayList）总共实现下面这些方法：
底层还是使用数组，不过为了实现动态缩容扩容，我们包装了一些方法在里面：
- 字段
public class Array<E>{
//底层还是用数组实现
private E[] data;
//size记录data中真实存在的元素个数
private int size;
...
}
- 构造器
public Array() {
//默认实现给10个空间
this(10);
}
public Array(E[] data) {//这块是拷贝，不是让底层的data直接指向传入的参数
//这是Java不允许泛型数组，所以要Object数组强转
this.data = (E[])new Object[data.length];
for(int i = 0; i < data.length; i++) {
this.data[i] = data[i];
}
size = data.length;
}
public Array(int Capacity) {
//这是Java不允许泛型数组，所以要Object数组强转
data = (E[]) new Object[Capacity];
size = 0;
}
-
封装一个异常检查
用于下面各种方法中的Index或者findelement的检查，
private void checkIndexRange(int index) {
if (index < 0 || index >= data.length) {
throw new IllegalArgumentException();
}
}
-
扩容函数
我们的扩容策略会在下面add和remove中具体介绍，这里扩容函数就是New一个新容量的数组，然后把原数组的值复制进去就可以了。
private void resize(int newCapacity) {
E[] newArray = (E[]) new Object[newCapacity];
for(int i = 0; i < size; i++) {
newArray[i] = data[i];
}
data = newArray;
}
- 一系列get和判空以及contains和find和set
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public E get(int index) {
checkIndexRange(index);
return data[index];
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
public boolean contains(E element) {
for(int i = 0; i < size; i++) {
if (Objects.equals(data[i], element)) {
return true;
}
}
return false;
}
public int find(E element) {
for(int i = 0; i < size; i++) {
if (Objects.equals(data[i], element)) {
return i;
}
}
return -1;
}
public void set(int index, E element) {
checkIndexRange(index);
data[index] = element;
}
-
增加和扩容策略
我们在增加时候检查容量，采用最简单的扩容策略，在size等于最大容量时候，扩容为原来size的二倍。
public void add(int index, E element) {
checkIndexRange(index);
if (size == data.length) {
resize(2 * size);
}
for(int i = size; i > index; i--) {
data[i] = data[i-1];
}
data[index] = element;
size ++;
}
public void addFirst(E element) {
add(0, element);
}
public void addLast(E element) {
add(size, element);
}
-
删除和缩容策略
每次在删除元素时候检查size，缩容策略也很简单，最直白的策略就是size == data.length/2时候，又给缩回去，但是这样就会导致一种极端情况，如果数组的元素数目在data.length/2周围反复横跳add/remove，这样就会不停的缩容，扩容，改变容量的复杂度都是O(n)，这毫无疑问是一个负担。所以改变一下缩容的策略，在size== data.length/4时候去缩容到原来容量的一半。
public E remove(int index) {
checkIndexRange(index);
//先保存下来要删除（返回）的值
E ret = data[index];
//然后从index开始把后一个元素赋值给前一个
for(int i = index; i < size - 1; i++) {
data[i] = data[i+1];
}
//最后一个元素赋为Null
data[size - 1] = null;
//别忘了维护size
size --;
//size减小之后如果到了四分之一长度，那就缩容为原来容量的一半，但是同时要注意 data.length/2不是0
if (size == data.length/4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size);
}
public E removeElement(E element) {
int index = find(element);
return remove(index);
}
这样就基本完成了一个伪的ArrayList，集合框架的源码肯定写的更强一些，也考虑的更周到一些，后面在总结集合源码时候会进行分析。
PriorityQueue
首先基于上面实现的Array为底层，实现一个heap。
需要有下面的方法：
-
字段
就只有一个底层的Array，我们用Array直接来模拟堆这个二叉树。需要理解的基本概念是是个节点对应下标如果是i（从0开始），那么它的左孩子就是2 * i+1，右孩子就是2 * i+2，而它的父亲节点是(i - 1) / 2。如果下标从1开始会有不同结果，自行推导即可。
private Array<E> data;
-
构造器
先写两个，最后一个最后介绍。
public MaxHeap() {
this.data = new Array<>();
}
public MaxHeap(int Capacity) {
this.data = new Array<>(Capacity);
}
- 判空和长度以及获取左右孩子和父亲节点
public boolean isEmpty() {
return data.isEmpty();
}
public int size() {
return data.getSize();
}
private int parent(int index) {
return (index-1)/2;
}
private int leftChild(int index) {
return 2 * index + 1;
}
private int rightChild(int index) {
return 2 * index + 2;
}
-
最核心的shiftUp和shiftDown 都是
logn。
shiftUp，就是上浮，当新加入一个节点时候我们把一个值和它的父亲相比，如果它要比父亲节点的值更大，那么就交换节点，以此类推往上不断考察，直到父亲节点比他的值大为止。
shiftDown则反之，是下沉，这个方法在取出最大值，和Heapify的过程中要用到。是把当前节点和儿子节点相比，不过需要考察两个节点，我们要把当前节点和左右儿子中更大的那个交换，而如果当前节点比左右儿子都大，那就下沉结束了。
private void shiftDown(int index) {
while(leftChild(index)< size()) {
int j = leftChild(index);
//第一步找到左右孩子中更大的那一个
if(j + 1 < size() && data.get(j+1).compareTo(data.get(j))>0) {
j = rightChild(index);
}
//j现在代表的不管是左还是右，反正都是最大的
//如果当前节点比左右孩子更大的那个还要大，那就说明不再需要shiftDown了，不用再交换
if (data.get(index).compareTo(data.get(j))>0) {
break;
}
//如果上面的循环没有跳出去，那就说明肯定是孩子比他大的，不管左还是右，只管jjjjjj，交换一下即可
data.swap(index, j);
//再把指针挪到j上面
index = j;
}
}
private void shiftUp(int index) {
while(parent(index) >= 0 && data.get(index).compareTo(data.get(parent(index)))>0) {
data.swap(index, parent(index));
index = parent(index);
}
}
写的代码上来看，shiftUp会更加简单一些，毕竟只需要比较一个节点，shiftDown写的时候，就是找到儿子中最大的那一个，并记录下标，然后把当前节点和最大的那个比一下，这是比较优秀的写法。
- 添加节点
/*
* 添加过程是先在数组末尾添加新元素，
* 然后为了保持堆的特性，要对最后添加的新元素进
* 行shiftUp操作
*/
public void add(E e) {
data.addLast(e);
shiftUp(size() - 1);
}
- 拿出最大元素
/*
* 拿出最大元素之后依然要保持堆的特性，
*所以这里的方法是，先把最后一个节点值交换到第0位
*最大的位置，然后把最后一个位置删除掉，然后再对
*最大节点进行下沉操作维护堆的特性。
*/
public E extractMax() {
E max = findMax();
data.swap(0, size()-1);
data.removeLast();
shiftDown(0);
return max;
}
public E findMax() {
return data.getFirst();
}
-
第三个构造器——Heapify
最后我们再来谈一下第三个构造器的故事......从Heapify这个名字大概能猜到，我们这个构造器是把一个数组“堆化”，思想是把数组拷进来先放在“树”上，这时候它是按照原来数组的顺序依次放进去的，不是一个堆，我们从第一个非叶子节点开始到根节点依次shiftDown，就可以把这个数组变成一个堆。这个复杂度是O（n），暂时想不通，后面查找资料学习后来填坑。
//这个构造函数对应的过程叫Heapify
public MaxHeap(E[] array) {
//先把数组弄进来
data = new Array<>(array);
//从第一个非叶子节点开始 shiftDown
for(int i = parent(size() - 1); i >= 0; i--) {
shiftDown(i);
}
}
这里基本上这个堆的结构是实现了，我们在它之上包装上PriorityQueue的接口就好了。
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> maxHeap;
public PriorityQueue() {
maxHeap = new MaxHeap<>();
}
@Override
public int getSize() {
return maxHeap.size();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
@Override
public E dequeue() {
return maxHeap.extractMax();
}
@Override
public E getFront() {
return maxHeap.findMax();
}
}
Java的util包下面的PriorityQueue是个最小堆，不过可以通过构造器传入自定义的Comparator来决定这个PriorityQueue的判定标准。
BST
二分搜索树是在是再常见不过了。
首先需要定义一个节点类，我们这里放成内部类。
- 节点内部类
public class BinarySearchTree<E> {
class Node{
public Node left,right;
public E e;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
.....
}
-
字段
一个树根节点treeRoot，和一个节点数size。
private Node treeRoot;
private int size;
- 构造器
public BinarySearchTree() {
treeRoot = null;
size = 0;
}
- size()和判空
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
-
添加节点
我们对外提供一个public的void add(E e)方法，然后内部实现是一个返回值为Node的方法，它返回传入的root节点，并递归去找到需要添加的节点的位置，大于当前节点的值到右子树去找，小于当前节点的值到左子树去找。
public void add(E e) {
treeRoot = add(treeRoot, e);
}
private Node add(Node root, E e) {
if (root == null) {
size++;
return new Node(e);
}
if (root.e.compareTo(e) == 0) {
return root;
}
if (e.compareTo(root.e)>0) {
root.right = add(root.right, e);
}else {
root.left = add(root.left, e);
}
return root;
}
-
contains
和add的写法比较相似。递归去找e的位置。
public boolean contains(E e) {
return contains(treeRoot,e);
}
private boolean contains(Node root, E e) {
if (root == null) {
return false;
}
if (root.e.compareTo(e)==0) {
return true;
}
if (e.compareTo(root.e) > 0) {
return contains(root.right,e);
} else {
return contains(root.left, e);
}
}
-
先序、中序、后序和层序遍历（还有一种在剑指上看到的之字形遍历，都可以通过栈模拟一下）
先中后序遍历的递归实现。
public void preOrder() {
System.out.println("preOrder:");
preOrder(treeRoot);
}
private void preOrder(Node root) {
if (root == null) {
return ;
}
System.out.println(root.e);
preOrder(root.left);
preOrder(root.right);
}
public void inOrder() {
System.out.println("inOrder:");
inOrder(treeRoot);
}
private void inOrder(Node root) {
if (root == null) {
return ;
}
inOrder(root.left);
System.out.println(root.e);
inOrder(root.right);
}
public void postOrder() {
System.out.println("postOrder:");
postOrder(treeRoot);
}
private void postOrder(Node root) {
if (root == null) {
return ;
}
postOrder(root.left);
postOrder(root.right);
System.out.println(root.e);
}
下面是先序的非递归实现，我们是用一个Stack去模拟系统的栈，从树根入栈开始，取栈顶先加右再加左入栈，直到栈取空为止。
private void preOrderNotRecursively(Node root) {
if (root == null) {
return ;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
Node node = stack.pop();
System.out.println(node.e);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
然后再来层序遍历，这种依赖于队列来实现。从根节点入队开始，取出队首节点访问，先入左再入右。直到队空为止。
public void levelOrder() {
System.out.println("leverOrder:");
levelOrder(treeRoot);
}
private void levelOrder(Node root) {
if (root == null) {
return ;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
Node node = queue.poll();
System.out.println(node.e);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
接下来的一系列方法，都是为remove服务的，我们一步步来，bst中的remove方法确实要复杂于那些add操作。
- get最大和最小递归和非递归都写了
public E getMax() {
if (isEmpty()) {
throw new NullPointerException();
}
return getMax(treeRoot).e;
}
private Node getMax(Node root) {
if (root.right == null) {
return root;
}
return getMax(root.right);
}
private Node getMaxNotRecursively(Node root) {
if (root == null) {
return null;
}
while(root.right != null) {
root = root.right;
}
return root;
}
public E getMin() {
if (isEmpty()) {
throw new NullPointerException();
}
return getMin(treeRoot).e;
}
private Node getMin(Node root) {
if(root.left == null) {
return root;
}
return getMin(root.left);
}
private Node getMinNotRecursively(Node root) {
if (root == null) {
return null;
}
while(root.left != null) {
root = root.left;
}
return root;
}
- removeMax和removeMin
public E removeMax() {
E ret = getMax();
treeRoot = removeMax(treeRoot);
return ret;
}
/*
* 删除以root为根的子树的最大节点
* 返回删除最大节点后的子树的根
* 删除的过程是用该节点的左孩子直接代替它
*/
private Node removeMax(Node root) {
if (root.right == null) {
Node leftNode = root.left;
root.left = null;
return leftNode;
}
root.right = removeMax(root.right);
return root;
}
public E removeMin() {
E ret = getMin();
treeRoot = removeMin(treeRoot);
return ret;
}
/*
* 删除以root为根的子树中的最小节点
* 返回删除最小节点后的子树的根
* 删除的过程是一直往左走，找到最左节点，用该节点的右孩子代替它
*/
private Node removeMin(Node root) {
if (root.left == null) {
Node rightNode = root.right;
root.right = null;
return rightNode;
}
root.left = removeMin(root.left);
return root;
}
-
removeNode删除任意一个节点
我们上面做的所有工作都是为了它。
/*
* 删除以root为根节点的子树中值为e的节点
* 返回删除目的节点后的子树的根
* 删除的过程就是根据e的值和当前节点的值的比较结果
* 向左或者向右去走，直到找到目的节点
* 这时候有三种情况。
* 1.左子树为空，那就直接用它的右孩子去代替这个节点
* 2.右子树为空，那就直接用它的左孩子去代替这个节点
* 3.左右子树都不为空，我们找它的后继节点successor，
* 也就是右子树中的最小节点，用这个节点来代替它（或者找
* 前驱节点，左子树中的最大节点，用这个节点来代替它）,还要
* 记的把后继（前驱）节点删除掉。
*/
private Node removeNode(Node root, E e) {
if (root == null) {
return null;
}
if (e.compareTo(root.e)>0) {
root.right = removeNode(root.right,e);
return root;
}
if (e.compareTo(root.e)<0) {
root.left = removeNode(root.left, e);
return root;
}
if (root.left == null) {
Node rightNode = root.right;
root.right = null;
size--;
return rightNode;
}
if (root.right == null) {
Node leftNode = root.left;
root.left = null;
size--;
return leftNode;
}
//左右子树都不为空,找到后继节点——右子树中的最小值
Node successor = getMin(root.right);
successor.right = removeMin(root.right);
successor.left = root.left;
root.left = null;
root.right = null;
return successor;
}
