分类:数据结构

数据结构(六)集合和映射

1、集合

集合(Set)最大的特点就是元素不重复;上篇博客中二分搜索树也是不重复的,这篇我们就用上节实现的二分搜索树来作为集合的底层;

我们先来定义一个集合的接口:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/1610:03 AM
 * @description
 */
public interface Set<E> {
    //添加元素
    void add(E e);
    //删除元素
    void remove(E e);
    //判断是否包含
    boolean contains(E e);
    //获得元素个数
    int getSize();
    //判断是否为空
    boolean isEmpty();
}

基于二分搜索树的集合实现:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/1610:25 AM
 * @description 以二分搜索树为底层的集合
 */

public class BSTSet<E extends Comparable<E>> implements Set<E> {

    private BST<E> bst;

    public BSTSet(){
        bst = new BST<>();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int getSize() {
        return bst.size();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty() ;
    }
}

基于链表实现集合:

链表在之前的博客中写了 数据结构(四)链表  

package com.wjy329;
/**
 * @description: 基于链表的集合实现
 * @create: 2018-10-16 10:58
 **/
public class LinkedListSet<E> implements Set<E>{

    private LinkedList<E> list;

    public LinkedListSet(){
        list = new LinkedList<>();
    }

    @Override
    public void add(E e) {
        if(!list.contains(e)){
            list.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        list.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return list.contains(e);
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

上面就是有关集合的一些实现,集合有有序集合和无序集合,有序集合中的元素具有顺序性,它是基于搜索树实现,而无序集合中的元素不具有顺序性,它基于哈希表实现;

2、映射

映射(Map)是存储(键,值)数据对的数据结构(Key,Value) ,可以根据键(Key),寻找值(Value),这里我们可以使用链表或者二分搜索树实现;

和上面一样,我们先定义一个映射的接口:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/162:43 PM
 * @description
 */
public interface Map<K,V> {
    //添加元素
    void add(K key,V value);
    //移除元素
    V remove(K key);
    //是否包含输入的key
    boolean contains(K key);
    //获取输入key的值
    V get(K key);
    //给key指定新的值
    void set(K key,V newValue);
    //获取有几个键值对
    int getSize();
    //判断是否为空
    boolean isEmpty();
}

链表为底层的映射:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/162:47 PM
 * @description 以链表为底层的映射类
 */


public class LinkedListMap<K,V> implements Map<K,V>{

    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key,V value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key){
            this(key,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString(){
            return key.toString()+" : "+value.toString();
        }

    }

    //虚拟头指针
    private Node dummyHead;
    private int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    private Node getNode(K key){
        Node cur = dummyHead.next;
        while (cur != null){
            if(cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if(node == null){
            dummyHead.next = new Node(key,value,dummyHead.next);
            size++;
        }else{
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while (pre.next != null){
            if(pre.next.key.equals(key)){
                break;
            }
            pre = pre.next;
        }

        if(pre.next != null){
            Node delNode = pre.next;
            pre.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(key);
        if(node ==null){
            throw new IllegalArgumentException(key + "doesn't exist");
        }
        node.value = newValue;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size ==0;
    }
}

二分搜索树为底层的映射:

package com.wjy329;/**
 * @Author wjy329
 * @Time 2018/10/163:17 PM
 * @description
 */

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public Node left,right;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){
        root = null;
        size = 0;
    }

    @Override
    public void add(K key,V value){
        root = add(root,key,value);
    }

    private Node add(Node node,K key,V value){
        if(node == null){
            size++;
            return new Node(key, value);
        }
        if(key.compareTo(node.key)<0){
            node.left = add(node.left,key,value);
        }else if(key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{
            node.value = value;
        }
        return node;
    }

    private Node getNode(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key) == 0){
            return node;
        }else if(key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        }else{
            return getNode(node.right,key);
        }
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node,K key){
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key) < 0){
            node.left = remove(node.left,key);
            return node;
        }else if(key.compareTo(node.key) > 0){
            node.right = remove(node.right,key);
            return node;
        }else{
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right =null;
            return successor;
        }
    }

    //返回最小的元素
    public V minimum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty!!!");
        }
        return minimum(root).value;
    }
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }
    //返回最大的元素
    public V maximum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty!!!");
        }
        return maximum(root).value;
    }
    private Node maximum(Node node){
        if(node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    //删除最小的元素
    public V removeMin(){
        V ret = minimum();
        root = removeMin(root);
        return ret;
    }
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left =  removeMin(node.left);
        return node;
    }

    //删除最大的元素
    public V removeMax(){
        V ret = maximum();
        root = removeMax(root);
        return ret;
    }
    private Node removeMax(Node node){
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right =  removeMax(node.right);
        return node;
    }


    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root,key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root,key);
        if(node == null){
            throw new IllegalArgumentException(key + "doesn't exist");
        }
        node.value = newValue;
    }

    @Override
    public int getSize() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }
}

数据结构(五)二分搜索树

1、二叉树

image.png 

如上图所示就是二叉树,如同链表一样,是动态的数据结构;

class Node{
    E e;
    Node left;
    Node right;
}
  • 二叉树具有唯一的根节点

  • 二叉树每个节点最多有两个孩子

  • 二叉树每个节点最多有一个父亲

  • 二叉树具有天然的递归结构

            (1)每个节点的左子树也是二叉树

            (2)每个节点的右子树也是二叉树

2、二分搜索树

  • 二分搜索树是二叉树

  • 二分搜索树每个节点的值:

        (1)大于其左子树的所有节点的值

        (2)小于其右子树的所有节点的值

  • 每一棵子树也是二分搜索树

  • 存储的元素必须具有可比较性

下面我们来看二分搜索树的代码表现形式:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/152:02 PM
 * @description
 */

//继承Comparable使元素具有可比较性
public class BST<E extends Comparable<E>>{
    //节点类
    private class Node{
        //元素的值
        public E e;
        //左右节点
        public Node left,right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }
    //根节点
    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

3、二分搜索树添加新元素

我们设计的二分搜索树不包含重复元素;直接上代码;

//向二分搜索树中添加元素
public void add(E e){
   root = add(root,e);
}

private Node add(Node node,E e){
    if(node == null){
        size++;
        return new Node(e);
    }
    if(e.compareTo(node.e)<0){
        node.left = add(node.left,e);
    }else if(e.compareTo(node.e)>0){
        node.right = add(node.right,e);
    }
    return node;
}

上面的方式是一个递归的方式,我们来分析一下:

我们看私有的add()方法,首先我们判断节点是否为空,如果为空的话,直接new一个新的值为e的节点即可,如果不为空的话,需要我们比较值来添加,我们之前也学习了二叉搜索树的特点,那就是左子树小于父节点,右子树大于父节点,所以我们用传进来的e和父节点的值比较,如果比父节点的值小,就需要查入到左子树,此时,需要判断左子树是否为空,左子树为空直接new,左子树不为空需要再次判断大小插入,这是一个递归的过程,所以我们有了node.left = add(node.left,e),右子树也是一样的道理;

4、查询元素

//查询元素
public boolean contains(E e){
    return contains(root,e);
}

private boolean contains(Node node,E e){
    if(node == null){
        return false;
    }
    if(e.compareTo(node.e) == 0){
        return true;
    }else if(e.compareTo(node.e) < 0){
        return contains(node.left,e);
    }else{
        return contains(node.right,e);
    }
}

上面的查询算法也是递归的操作,结合上面的理解即可;

5、遍历

5.1 前序遍历

前序遍历,也叫先序遍历、先根遍历,即先访问根节点然后遍历左子树,在遍历右子树。

//前序遍历
public void preOrder(){
    preOrder(root);
}
private void preOrder(Node node ){
    if(node == null){
        return;
    }
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

5.2 中序遍历

中序遍历,先遍历左子树,然后访问根节点,最后遍历右子树。

//中序遍历
public void inOrder(){
    inOrder(root);
}
private void inOrder(Node node ){
    if(node == null){
        return;
    }
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
}

中序遍历的结果是顺序的。

5.3 后序遍历

后序遍历,先遍历左子树,再遍历右子树,最后访问根节点。

//后序遍历
public void postOrder(){
    postOrder(root);
}
private void postOrder(Node node ){
    if(node == null){
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
}

5.4 层序遍历

思路:应用了队列,根节点先入队,然后出队,出队完成后,再将左右子树的根节点分别入队,然后左节点出队,出队时候,再将左右节点入队,以此类推……

//层次遍历
public void levelOrder(){
    Queue<Node> q = new LinkedList<Node>();
    q.add(root);
    while (!q.isEmpty()){
        Node cur = q.remove();
        System.out.println(cur.e);
        if(cur.left != null){
            q.add(cur.left);
        }
        if(cur.right != null){
            q.add(cur.right);
        }
    }
}

意义:更快的找到问题的解;算法设计-最短路径;图中的深度优先遍历和广度优先遍历;

6、删除节点

6.1 获取最小值和最大值

//返回最小的元素
public E minimum(){
    if(size == 0){
        throw new IllegalArgumentException("BST is empty!!!");
    }
    return minimum(root).e;
}
private Node minimum(Node node){
    if(node.left == null){
        return node;
    }
    return minimum(node.left);
}
//返回最大的元素
public E maximum(){
    if(size == 0){
        throw new IllegalArgumentException("BST is empty!!!");
    }
    return maximum(root).e;
}
private Node maximum(Node node){
    if(node.right == null){
        return node;
    }
    return maximum(node.right);
}

6.2 删除最小值和最大值

思路:由之前所学,我们知道最小的元素就是不停的访问左子树中的左节点,如果正好是叶子节点,那么我们删除即可;如果该节点还有右子树,那么我们将右子树的父节点作为该节点的父节点的新的左子树即可;删除最大的元素正好相反,即不停的访问右子树的右节点,如果正好是叶子节点,删除即可;如果该节点还有左子树,那么我们将左子树的父节点作为该节点的父节点的新的右子树即可。

//删除最小的元素
public E removeMin(){
    E ret = minimum();
    root = removeMin(root);
    return ret;
}
private Node removeMin(Node node){
    if(node.left == null){
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }
    node.left =  removeMin(node.left);
    return node;
}

//删除最大的元素
public E removeMax(){
    E ret = maximum();
    root = removeMax(root);
    return ret;
}
private Node removeMax(Node node){
    if(node.right == null){
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    node.right =  removeMax(node.right);
    return node;
}

6.3 删除任意的元素

思路:删除任意元素时,需要我们进行判断,如果删除的元素没有左子树,那么删除后将它的右子树作为它的替代即可;如果删除的元素没有右子树,那么删除后将它的左子树作为它的替代即可;如果该元素同时有左右子树,那么找到它右子树中最小的元素来代替它,它的左子树作为新节点的左子树即可,新节点的右子树是原右子树删除新节点的树;

//删除元素e
public void remove(E e){
    root = remove(root,e);
}
private Node remove(Node node,E e){
    if(node == null){
        return null;
    }
    if(e.compareTo(node.e) < 0){
        node.left = remove(node.left,e);
        return node;
    }else if(e.compareTo(node.e) > 0){
        node.right = remove(node.right,e);
        return node;
    }else{
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        successor.left = node.left;
        node.left = node.right =null;
        return successor;
    }
}

数据结构(四)链表

之前我们学习了动态数组、栈、队列,这些底层依托的是静态数组,并没有实现真正的动态,今天我们学习的这个数据结构是真正的自己实现了动态的特性,那就是链表;

链表的数据存储在节点中,首先我们看节点的定义

class Node{
    E e;
    Node next;
}

从上面我们可以看出,链表中还有一个next的节点类型的对象,它是干嘛的呢,如果一个节点的next是null,那么就说明此节点是链表的最后一个节点。

优点:真正的动态,不需要处理固定容量的问题

缺点:丧失了随机访问的能力

下面我们先定义节点

package com.wjy329;
/**
 * @author: wjy329
 * @create: 2018-10-09 15:58
 **/
public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null );
        }

        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }
}

节点有了之后那就开始定义链表

package com.wjy329;
/**
 * @description:
 *
 * @author: wjy329
 * @param:
 * @return:
 * @create: 2018-10-09 15:58
 **/
public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null );
        }

        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node head;
    private int size;
    public LinkedList(){
        head = null;
        size = 0;
    }
    //获取链表中的元素个数
    public int getSize(){
        return size;
    }
    //返回列表是否为空
    public boolean isEmpty(){
         return size ==0;
    }
}

上面就是链表的定义,接下来我们就要逐步的完善它,实现各种相关功能。

在链表头添加元素:

//在链表头添加新的元素
    public void addFirst(E e){
        Node node = new Node(e);
        node.next = head;
        head = node;
        // 下面这一行代码也可以解决添加头的问题
//      head = new Node(e,head);
        size++;
    }

上面代码写了两种方式,第一种方式代码多,但是比较直观,很容易就看明白了,第二种方式代码少,但是不容易理解,这里详细说一下第二种方式,第二种利用了节点的构造函数,新建一个节点,新的节点值为传入的e,而next指向head节点,这就意味着该节点的下一个节点就是此时的head节点,然后我们把此时的节点再作为头节点即可。

在链表中间添加元素:

image.png

我们先看上图,要在索引为2的节点前插入节点,我们先需要将新的节点的next指向此时的2节点,然后1节点的next指向插入的节点即可,代码表示为: node.next = prev.next  prev.next = node; 

接下来我们看第三行图,这个表示了错误的顺序,先将1节点的后驱节点指向要插入的节点,然后再将插入节点的后驱指向1节点的后驱,这时我们发现1节点的后驱节点指向的是要插入的节点,就已经出现错误了,所以要注意插入的顺序

下面看具体代码:

//在链表的index位置处添加新的元素
public void add(int index,E e){
    if(index < 0 || index > size){
        throw new IllegalArgumentException("添加失败,非法的位置");
    }
    if(index == 0){
        addFirst(e);
    }else {
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }
}
//在链表末尾处添加元素
public void addLast(E e){
    add(size,e);
}

链表虚拟头节点:

上面的代码我们还需判断是否为头节点,为了方便添加并且统一代码,我们需要给列表设置一个虚拟的头节点,头节点仅仅是为了方便指向位置,节点内容为空。修改完成后的代码如下:

package com.wjy329;
/**
 * @author: wjy329
 * @create: 2018-10-09 15:58
 **/
public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null );
        }

        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;
    public LinkedList(){
        dummyHead = new Node(null,null);
        size = 0;
    }
    //获取链表中的元素个数
    public int getSize(){
        return size;
    }
    //返回列表是否为空
    public boolean isEmpty(){
         return size ==0;
    }
    //在链表头添加新的元素
    public void addFirst(E e){
       add(0,e);
    }
    //在链表的index位置处添加新的元素
    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加失败,非法的位置");
        }
        Node prev = dummyHead;
        for(int i = 0;i < index;i++){
            prev = prev.next;
        }
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;

    }
    //在链表末尾处添加元素
    public void addLast(E e){
        add(size,e);
    }
}

链表的操作:

下面有些操作并不是链表常使用的操作,仅仅作为练习使用。

查找:

//获取链表第index个位置的元素
public E get(int index){
    if(index < 0 || index > size){
        throw new IllegalArgumentException("非法的位置");
    }
    Node cur = dummyHead.next;
    for(int i = 0;i < index;i++){
        cur = cur.next;
    }
    return cur.e;
}
//获取链表的第一个元素
public E getFirst(){
    return get(0);
}
//获取链表的最后一个元素
public E getLast(){
    return get(size - 1);
}

更新:

//修改第index位置的元素
public void set(int index,E e){
    if(index < 0 || index > size){
        throw new IllegalArgumentException("非法的位置");
    }
    Node cur = dummyHead.next;
    for(int i = 0;i < index;i++){
        cur = cur.next;
    }
    cur.e = e;
}

判断是否存在:

//查找链表中是否存在e
public boolean contains(E e){
    Node cur = dummyHead.next;
    while (cur != null){
        if(cur.e.equals(e)){
            return true;
        }
        cur = cur.next;
    }
    return false;
}

删除:

//删除index位置的元素
public E remove(int index){
    if(index < 0 || index > size){
        throw new IllegalArgumentException("非法的位置");
    }
    Node prev = dummyHead;
    for(int i = 0;i < index;i++){
        prev = prev.next;
    }
    Node retNode = prev.next;
    prev.next = retNode.next;
    retNode.next = null;
    size--;
    return retNode.e;
}


// 从链表中删除元素e
public void removeElement(E e){

    Node prev = dummyHead;
    while(prev.next != null){
        if(prev.next.e.equals(e))
            break;
        prev = prev.next;
    }

    if(prev.next != null){
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
    }
}

关于链表的实现就写到这里,当然我们可以用链表来实现栈和队列,以后有时间再写吧。

数据结构(三)栈和队列

栈是一种线性结构,相比数组,栈对应的操作是数组的子集,栈只能从一端添加元素,也只能从一端取出元素,这一端称为栈顶。栈是一种后进先出的数据结构,从下图我们可以看出,先入栈的元素在栈底,得等到它之后的所有元素都出去,它才能出栈,反而最后入栈的元素可以先出栈。

1538361372515527.png

栈的应用:

  • 撤销操作

  • 程序调用的系统栈

栈的实现:

栈的实现很简单,我们需要实现5个操作即可,void push(E)-入栈操作、E pop()-出栈操作、E peek()-查看栈顶元素、int getSize()-查看栈里一共有多少元素、boolean isEmpty()-判断栈是否为空;  下面栈代码的实现用了上篇文章中写的数组,为了获取栈顶元素,我们需要在上篇数组的代码中添加两个方法,获取数组最后一个元素(即栈顶)和第一个元素(栈底),具体方法如下:

//获取数组最后一个元素
public E getLast(){
    return get(size -1);
}
//获取数组第一个元素
public E getFirst(){
    return get(0);
}

我们先来一个栈的接口,最后实现栈:

Stack.java:

package com.wjy329;

/**
 * @Author wjy329
 * @Time 2018/10/19:27 PM
 * @description
 */
public interface Stack<E> {
    //获取栈中元素个数
    int getSize();
    //判断栈是否为空
    boolean isEmpty();
    //入栈
    void push(E e);
    //出栈
    E pop();
    //查看栈顶元素
    E peek();
}

ArrayStack.java:

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/19:30 PM
 * @description
 */

public class ArrayStack<E> implements Stack<E>{

    Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.delLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for(int i=0;i < array.getSize();i++){
            res.append(array.get(i));
            if(i != array.getSize()-1){
                res.append(",");
            }
        }
        res.append("] top");
        return res.toString();
    }
}

文章一开始就说了两个栈的应用,在我们面试中,经常用到的栈的应有就有一个是括号的匹配,下面给出代码:

package com.wjy329;

import java.util.Stack;

/**
 * @Author wjy329
 * @Time 2018/10/110:07 PM
 * @description
 */

public class Solution {
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for(int i=0;i < s.length();i++){
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else {
                if(stack.isEmpty()){
                    return false;
                }
                char topChar = stack.pop();
                if(c == ')' && topChar != '('){
                    return false;
                }
                if(c == ']' && topChar != '['){
                    return false;
                }
                if(c == '}' && topChar != '{'){
                    return false;
                }

            }
        }
        return stack.isEmpty();
    }
}

括号匹配的思路也很简单:就是将给定的字符串依次取出如果是左括号则入栈,右括号则对括号进行匹配。

队列

队列也是一种线性结构,相比数组,栈对应的操作是数组的子集,只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。队列是一种先进先出的数据结构。

image.png

队列的实现:

和栈的实现类似,同样我们需要5个方法,void enqueue(E)-入队、E dequeue()-出队、E getFront()-查看队首元素、int getSize()-查看队列中的元素个数、boolean isEmpty()-判断队列是否为空;

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/110:44 PM
 * @description
 */

public class ArrayQueue<E> implements Queue<E>{

    Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }


    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.delFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("[");
        for(int i=0;i < array.getSize();i++){
            res.append(array.get(i));
            if(i != array.getSize()-1){
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

循环队列:

上述数组队列当进行删除队首元素时,其后面的元素需要往前移,时间复杂度为O(n),循环队列不需要往前移动,当后面空间满时,可以往前在寻找空间,循环队列可以通过(tail+1)%c == front 来判断队列是否已满。tail-队尾、c-队列容量、front-队首;

package com.wjy329;
/**
 * @Author wjy329
 * @Time 2018/10/29:12 AM
 * @description
 */

public class LoopQueue<E> implements Queue<E>{

    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail+1)%data.length;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for(int i = 0;i < size;i++){
            newData[i] =data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw  new IllegalArgumentException("队列为空,不能出队");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1)%data.length;
        size--;
        if(size == getCapacity()/4 && getCapacity()/2 != 0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw  new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("[");
        for(int i=front;i != tail;i = (i + 1)%data.length){
            res.append(data[i]);
            if((i + 1)%data.length != tail){
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

}

数据结构(二)数组

从这篇开始就研究数组这个最基本的数据结构。

数组基础:

把数据码成一排进行存放

image.png

如上图所示,数组应该有一个自己的名字用来和其他数组区分,数组的索引是从0开始的,也就是想取到数组中的第三个数字,那么得取索引为2的值,即arr[2];

接下来说一下Java中的数组,Java数组中的每一个元素需要我们存放相同类型的元素,下面我们来演示一下Java数组的基本操作。

Java数组:

package com.wjy329;

public class Main {

    public static void main(String[] args) {
        //初始化一个int数组
       int[] scores = new int[10];
        //结果输出为: 0 0  0  0 0 。。。
        //默认的值都为0
       for(int i : scores){
           System.out.println(i);
        }
        //给数组赋值为数组的索引
        //打印结果:0 1 2 3 4 5 。。。
        for(int j=0;j < scores.length;j++){
           scores[j] = j;
            System.out.println(scores[j]);
        }
        
    }
}

当然,上面是最简单的Java数组的操作;

数组最大的优点是快速查询,可以直接根据索引查找,所以数组最好应用于“索引有语意”的情况。

Java为我们提供的数组不能进行添加和删除操作,下面我们来自己做一个我们自己的数组来实现此类功能;

封装我们自己的数组:

开始的时候,我们只需要简单的声明以及写出每个方法即可,最后我会将完整的封装的数组代码写上。

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array {
    private int[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = new int[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
}

以上就是自定义数组的初始化和一些简单获取数组容量和元素个数的方法;我们对数组需要进行等操作,所以下面我们也将一一实现。

增:

//向所有元素后添加一个元素
public void addLast(int e){
    if(size == data.length){
        throw new IllegalArgumentException("添加元素失败,数组容量已满");
    }
    data[size] = e;
    size ++;
    //复用添加方法
    //add(size,e);
}
//在所有元素前添加一个元素e
public void addFirst(int e){
    add(0,e);
}

//在第index位置插入一个新元素e
public void add(int index,int e){
    if(size == data.length){
        throw new IllegalArgumentException("添加元素失败,数组容量已满");
    }
    if(index < 0 || index > size){
        throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
    }
    for(int i = size - 1;i >= index;i --){
        data[i + 1] = data[i];
    }
    data[index]=e;
    size++;
}

代码很好理解,我主要的说在指定位置添加元素方法,我们从后往前依次向后移一位,直到指定位置停止;size-1 为最后一个数的索引值,然后将其后移一位,接下来再后移其他位置的数据;

删:

//从数组中删除index位置的元素,返回删除的元素
public int remove(int index){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
    int del = data[index];
    for(int i = index + 1;i < size;i++){
        data[i-1] = data[i];
    }
    size--;
    return del;
}

上面是删除指定位置元素,删除的思路就是指定位置后的元素都向前移一位即可;下面是删除指定元素,需要用到后面的查找方法,查找到元素的索引,然后删除。

//删除数组中指定的元素
public void delElement(int e){
    int index = find(e);
    if(index != -1){
        remove(index);
    }
}

查、

//获取指定位置的元素
 int get(int index){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
    return data[index];
}
//将index位置的元素换为e
void set(int index,int e){
    if(index < 0 || index >= size){
        throw new IllegalArgumentException("非法索引");
    }
     data[index] = e;
}

//查找数组中是否存在元素e
public boolean contains(int e){
    for(int i=0;i < size; i++){
        if(data[i] == e){
            return true;
        }
    }
    return false;
}

//查找数组中元素e所在的索引,如果不存在元素e,返回-1
public int find(int e){
    for(int i=0;i < size; i++){
        if(data[i] == e){
            return i;
        }
    }
    return -1 ;
}

 上面就是基本的思路,当然其中有些不足,比如相同元素的查找和删除等,上面的代码只会查找一个或者删除一个,并不会全部删除,这是因为主要演示的是思路和逻辑,会了上面的,后面的设计也就会显得轻车熟路了。

下面给上封装数组的完整代码:

Array.java:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array {
    private int[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = new int[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(int e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(int e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,int e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }
    //获取指定位置的元素
     int get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    void set(int index,int e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(int e){
        for(int i=0;i < size; i++){
            if(data[i] == e){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(int e){
        for(int i=0;i < size; i++){
            if(data[i] == e){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public int remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        int del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        return del;
    }
    //删除数组中的第一个元素
    public int delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public int delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(int e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

上面仅仅是对int型数组的探索,为了让我们自定义的数组适合任意类型,我们将其定义为范型数组,下面直接给出代码:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array<E> {
    private E[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(E e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }
    //获取指定位置的元素
     public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        E del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        return del;
    }
    //删除数组中的第一个元素
    public E delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public E delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

动态数组:

我们使用上面的代码一段时间后发现,这个TM的还是静态数组啊,还是指定的大小没法扩充啊,还是毫无卵用啊。。。别急,接下来,我们就添加几行代码使其动态的扩展。

动态的思路也是很简单的,当我们添加元素时,如果发现已经满了,那么我们再新建一个比之前更大的数组(假设为2倍),然后将其值都赋值给新的数组,这样实现了添加的扩容;当我们删除到一定量的时候,我们发现太多的空间被浪费了,那么我们将其按照一定的比例缩小数组(当数组内元素个数为当前容量的一半时,我们就缩减为一半),以此来保证数组的空间合理性。

扩容的方法代码:

private void resize(int newCapacity) {
    E[] newData = (E[])new Object[newCapacity];
    for(int i= 0;i < size;i++){
        newData[i] = data[i];
    }
    data = newData;
}

最终代码:

package com.wjy329;
/**
 * @description: 自定义数组
 * @author: wjy329
 * @create: 2018-09-30 17:04
 **/
public class Array<E> {
    private E[] data;
    private int size;

    //构造函数,传入数组容量,size为数组中的元素个数
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size= 0;
    }
    //无参数的构造函数,数组容量为10
    public Array(){
        this(10);
    }
    //获取数组中的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //向所有元素后添加一个元素
    public void addLast(E e){
        if(size == data.length){
            throw new IllegalArgumentException("添加元素失败,数组容量已满");
        }
        data[size] = e;
        size ++;
        //复用添加方法
        //add(size,e);
    }
    //在所有元素前添加一个元素e
    public void addFirst(E e){
        add(0,e);
    }

    //在第index位置插入一个新元素e
    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("添加元素失败,插入位置过大或为负数");
        }
        if(size == data.length){
            resize(2 * data.length);
        }

        for(int i = size - 1;i >= index;i --){
            data[i + 1] = data[i];
        }
        data[index]=e;
        size++;
    }

    //获取指定位置的元素
     public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        return data[index];
    }
    //将index位置的元素换为e
    public void set(int index,E e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
         data[index] = e;
    }

    //查找数组中是否存在元素e
    public boolean contains(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引,如果不存在元素e,返回-1
    public int find(E e){
        for(int i=0;i < size; i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1 ;
    }

    //从数组中删除index位置的元素,返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("非法索引");
        }
        E del = data[index];
        for(int i = index + 1;i < size;i++){
            data[i-1] = data[i];
        }
        size--;
        if(size == data.length/2){
            resize(data.length/2);
        }

        return del;
    }
    //删除数组中的第一个元素
    public E delFirst(){
        return remove(0);
    }
    //删除数组中的最后一个元素
    public E delLast(){
        return remove(size -1);
    }
    //删除数组中指定的元素
    public void delElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array:size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for(int i=0;i < size;i++){
            res.append(data[i]);
            if(i != size - 1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i= 0;i < size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}

数据结构(一)初识

数据结构我们可能并不陌生,科班的同学应该都接触过这门课程,由于当初年少无知,认为数据结构不是那么重要,导致后来失去了很多机会,所以接下来我要系统的学习一下数据结构,也希望正在大学的朋友们不要轻视这门课程。

数据结构研究的是数据如何在计算机进行组织和存储,使得我们可以高效的获取数据或者修改数据。总的来说,数据结构可以分为三种:线性结构、树结构、图结构;

线性结构:数组、栈、队列、链表、哈希表…

树结构:二叉树、二叉搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树…

图结构:邻接矩阵、邻接表 

=====================================================

数据结构(二)数组

数据结构(三)栈和队列

数据结构(四)链表

目录待更新