2018-07-05-数据结构与算法(JAVA)

2018-10-25  本文已影响0人  ohcomeyes

简述

在编程过程中，通常会遇到的一个问题就是，性能瓶颈。很多时候考虑的都是怎么去做横向扩展，但偏偏忽略掉了最基本的问题就是系统是否真的已经达到了瓶颈？
性能瓶颈通常的表象是资源消耗过多外部处理系统的性能不足；或者资源消耗不多但程序的响应速度却仍达不到要求。
而调优的方式就是
寻找过度消耗资源的代码 和 寻找未充分使用资源但程序执行慢的原因和代码。
基础决定高度
就拿汽车来比较，通常不懂变速箱、发动机的原理但也是能开车，同样一个不懂数据结构和算法的人也能编程。很多人觉得基本的数据结构及操作已经在高级语言中封装,都可以直接调用库函数，那么到底有没有必要好好学习数据结构？

数据结构+算法＝程序

通常在程序中，遇到一个实际问题，充分利用数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效实现，这才是提高程序性能的主要方式。

如果没有具备这块相应的知识，怎么完成上述的实现？如果脱离了原有的调用，怎么完成程序的高效实现？而所有的应用实现都依赖于基础，基础就是数据结构和算法。了解这块，才能做到无惧任何技术的演变。所有说基础决定高度！

基本的概念

数据结构表示数据在计算机中的存储和组织形式，主要描述数据元素之间和位置关系等。选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。

数据结构的三种层次：

  1. 逻辑结构--抽象层： 主要描述的是数据元素之间的逻辑关系
数据结构图
  1. 物理结构--存储层： 主要描述的是数据元素之间的位置关系
  1. 运算结构--实现层： 主要描述的是如何实现数据结构

[图片上传失败...(image-baf471-1540434935926)]
每种逻辑结构采用何种物理结构来实现，并没有具体的规定。当一个结构，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；

数据结构比较

数据结构比较1
数据结构比较2

常用的数据结构：

常用的数据结构

数据结构选择：

image

O符号

O在算法当中表述的是时间复杂度，它在分析算法复杂性的方面非常有用。常见的有：

  1. O(1)：最低的复杂度，无论数据量大小，耗时都不变，都可以在一次计算后获得。哈希算法就是典型的O(1)
  2. O(n)：线性，n表示数据的量，当量增大，耗时也增大，常见有遍历算法
  3. O(n²)：平方，表示耗时是n的平方倍，当看到循环嵌循环的时候，基本上这个算法就是平方级的，如：冒泡排序等
  4. O(log n)：对数，通常ax=n,那么数x叫做以a为底n的对数,也就是x=logan，这里是a通常是2，如：数量增大8倍，耗时只增加了3倍，二分查找就是对数级的算法，每次剔除一半
  5. O(n log n)：线性对数，就是n乘以log n,按照上面说的数据增大8倍，耗时就是8*3=24倍，归并排序就是线性对数级的算法

Array

在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。

//只声明了类型和长度
数据类型 []  数组名称 = new 数据类型[数组长度];
//声明了类型，初始化赋值，大小由元素个数决定
数据类型 [] 数组名称 = {数组元素1，数组元素2，......}

大小固定，不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢

数组
模拟实现 
public class Array {
    private int[] intArray;

    private int elems;

    private int length;

    public Array(int max) {
        length = max;
        intArray = new int[max];
        elems = 0;
    }

    /**
     * 添加
     * @param value
     */
    public void add(int value){
        if(elems == length){
            System.out.println("error");
            return;
        }
        intArray[elems] = value;
        elems++;
    }


    /**
     * 查找
     * @param searchKey
     * @return
     */
    public int find(int searchKey){
        int i;
        for(i = 0; i < elems; i++){
            if(intArray[i] == searchKey)
                break;
        }
        if(i == elems){
            return -1;
        }
        return i;
    }

    /**
     * 删除
     * @param value
     * @return
     */
    public boolean delete(int value){
        int i = find(value);
        if(i == -1){
            return false;
        }
        for (int j = i; j < elems-1; j++) {
            //后面的数据往前移
            intArray[j] = intArray[j + 1];
        }
        elems--;
        return true;
    }

    /**
     * 更新
     * @param oldValue
     * @param newValue
     * @return
     */
    public boolean update(int oldValue,int newValue){
        int i = find(oldValue);
        if(i == -1){
            return false;
        }
        intArray[i] = newValue;
        return true;
    }

    /**
     * 显示所有
     */
    public void display(){
        for(int i = 0 ; i < elems ; i++){
            System.out.print(intArray[i]+" ");
        }
        System.out.print("\n");
    }


    /**
     * 冒泡排序
     * 每趟冒出一个最大数/最小数
     * 每次运行数量：总数量-运行的趟数(已冒出)
     */
    public void bubbleSort(){
        for(int i = 0; i < elems-1; i++){//排序趟数  n-1次就行了
            System.out.println("第"+(i+1)+"趟：");
            for(int j = 0; j < elems-i-1; j++){//每趟次数 (n-i) -1是防止下标越界，后面赋值用到了+1
                if(intArray[j] > intArray[j+1]){ //控制按大冒泡还是按小冒泡
                    int temp = intArray[j];
                    intArray[j] =  intArray[j+1];
                    intArray[j+1] = temp;
                }
                display();
            }
        }
    }

    /***
     * 选择排序
     * 每趟选择一个最大数/最小数
     * 每次运行数量：总数量-运行的趟数(已选出)
     */
    public void selectSort(){
        for(int i = 0; i < elems-1; i++) {//排序趟数  n-1次就行了
            int min = i;
            for(int j = i+1; j < elems; j++){ //排序次数 每趟选择一个数出来，-1次
                if(intArray[j] < intArray[min]){
                    min = j;
                }
            }
            if(i != min ){
                int temp = intArray[i];
                intArray[i] = intArray[min];
                intArray[min] = temp;
            }
            display();
        }
    }

    /**
     * 插入排序
     * 每趟选择一个待插入的数
     * 每次运行把待插入的数放在比它大/小后面
     */
    public void insertSort(){
        int j;
        for(int i = 1; i < elems; i++){
            int temp = intArray[i];
            j = i;
            while (j > 0 && temp < intArray[j-1]){
                intArray[j] = intArray[j-1];
                j--;
            }
            intArray[j] = temp;
        }
        display();
    }

    public static void main(String[] args) {
        Array array = new Array(10);
        array.add(6);
        array.add(3);
        array.add(8);
        array.add(2);
        array.add(11);
        array.add(5);
        array.add(7);
        array.add(4);
        array.add(9);
        array.add(10);
//        array.bubbleSort();
//        array.selectSort();
        array.insertSort();
//        array.display();
//        System.out.println(array.find(4));
//        System.out.println(array.delete(1));
//        array.display();
//        System.out.println(array.update(2,6));
//        array.display();
    }
}

Stack

Stack()
栈
模拟实现 
public class Stack {
    //小贴士：通常可以利用栈实现字符串逆序，还可以利用栈判断分隔符是否匹配，如<a[b{c}]>，可以正进反出，栈为空则成功。

    /**基于数组实现的顺序栈，连续存储的线性实现，需要初始化容量**/
    //固定数据类型
    //private int[] array;
    //动态数据类型
    private Object[] objArray;

    private int maxSize;

    private int top;

    public Stack() {
    }

    public Stack(int maxSize) {
        if(maxSize > 0){
            objArray = new Object[maxSize];
            this.maxSize = maxSize;
            top = -1;
        }else{
            throw new RuntimeException("初始化大小错误：maxSize=" + maxSize);
        }
    }

    /**
     * 入栈
     * @param obj
     */
    public void objPush(Object obj){
        //扩容
        grow();
        //++在前表示先运算再赋值，优先级高，在后表示先赋值再运算，优先级低
        objArray[++top] = obj;
    }

    /**
     * 出栈
     * @return
     */
    public Object objPop(){
        Object obj = peekTop();
        //声明原顶栈可以回收空间(GC)
        objArray[top--] = null;
        return obj;
    }

    /**
     * 查看栈顶
     * @return
     */
    public Object peekTop(){
        if(top != -1){
            return objArray[top];
        }else{
            throw new RuntimeException("stack is null");
        }
    }

    /**
     * 动态扩容
     */
    public void grow(){
        // << 左移运算符，1表示乘以2的1次方
        if(top == maxSize-1){
            maxSize = maxSize<<1;
            objArray = Arrays.copyOf(objArray,maxSize);
        }
    }



    /**基于链式存储，不连续存储的非线性实现**/
    private class Node<Object>{
        private Object data;

        private Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node nodeTop;

    private int size;

    public void nodePush(Object obj){
        //栈顶指向新元素，新元素的next指向原栈顶元素
        nodeTop = new Node(obj,nodeTop);
        size++;
    }

    public Object nodePop(){
        Node old = nodeTop;
        //声明原顶栈可以回收空间(GC)
        old.next = null;
        //栈顶指向下一个元素
        nodeTop = nodeTop.next;
        size--;
        return old.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");
        for(Node<Object> node = nodeTop; node != null; node = node.next){
            sb.append(node.data.toString() + " ");
        }
        return sb.toString()+"]";
    }

    public static void main(String[] args) {
//        Stack stack = new Stack(1);
//        stack.objPush("abc");
//        stack.objPush(123);
//        stack.objPush("de");
//        stack.objPush("cd");
//        stack.objPush("er");
//        stack.objPush("hello");
//        stack.objPush(666);
//        stack.objPush(545);
//        stack.objPush("word");
//        while (stack.top != -1){
//            System.out.println(stack.objPop());
//        }
//        System.out.println(stack.peekTop());
        Stack stack = new Stack();
        stack.nodePush("111");
        stack.nodePush("222");
        stack.nodePush("aaa");
        stack.nodePush("bbb");
        System.out.println(stack);
        while (stack.size > 1)
        System.out.println(stack.nodePop());
        System.out.println(stack);
    }
}

Queue

public class Queue {
    /***
     * 1.单向队列（Queue）：只能在一端插入数据，另一端删除数据。
     * 2.双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
     *
     *  与栈不同的是，队列中的数据不总是从数组的0下标开始的
     *  选择的做法是移动队头和队尾的指针。
     *  为了避免队列不满却不能插入新的数据，我们可以让队尾指针绕回到数组开始的位置，这也称为“循环队列”。
     * */
    // 单向循环队列，顺序存储结构实现
    private Object[] objQueue;
    //队列大小
    private int maxSize;
    //顶部
    private int top;
    //底部
    private int bottom;
    //实际元素
    private int item;

    public Queue(int size) {
        maxSize = size;
        objQueue = new Object[maxSize];
        top = 0;
        bottom = -1;
        item = 0;
    }

    /**
     * 入队
     * @param obj
     */
    public void add(Object obj){
        if(item == maxSize){
            throw new RuntimeException(obj+" add error, queue is full");
        }
        //循环队列，首尾结合，下标控制队首和队尾位置
        if(bottom == maxSize-1){
            bottom = -1;
        }
        objQueue[++bottom] = obj;
        item++;
    }

    /**
     * 出对
     * @return
     */
    public Object out(){
        if(item == 0){
            throw new RuntimeException("queue is null");
        }
        Object obj = objQueue[top];
        //声明原顶栈可以回收空间(GC)
        objQueue[top] = null;
        top++;
        //重置下标
        if(top == maxSize){
            top = 0;
        }
        item--;
        return obj;
    }

    //链式存储结构实现
    private class NodeQueue<Object>{
        private Object data;

        private NodeQueue next;

        public NodeQueue(Object data, NodeQueue next) {
            this.data = data;
            this.next = next;
        }
    }
    //队列头 出
    private NodeQueue queueTop;
    //队列尾 进
    private NodeQueue queueBottom;
    //队列大小
    private int size;

    public Queue() {
        queueTop = null;
        queueBottom = null;
        size = 0;
    }

    /**
     * 入队
     * @param obj
     */
    public void addNodeQueue(Object obj){
        if(size == 0){
            queueTop = new NodeQueue(obj,null);
            //指向同一存储地址
            queueBottom = queueTop;
        }else{
            NodeQueue<Object> nodeQueue = new NodeQueue(obj,null);
            //让尾节点的next指向新增的节点
            queueBottom.next = nodeQueue;
            //以新节点作为尾节点
            queueBottom = nodeQueue;
        }
        size ++;
    }

    /**
     * 出队
     * @return
     */
    public Object removeNodeQueue(){
        if(size == 0){
            throw new RuntimeException("queue is null");
        }
        NodeQueue nodeQueue = queueTop;
        queueTop = queueTop.next;
        //声明原队列头next可以回收空间(GC)
        nodeQueue.next = null;
        size--;
        return nodeQueue.data;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{ ");
        for(NodeQueue nodeQueue = queueTop ; nodeQueue != null ; nodeQueue = nodeQueue.next){
            sb.append(nodeQueue.data.toString()+" ");
        }
        return sb.toString()+"}";
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.addNodeQueue("123");
        queue.addNodeQueue("abc");
        queue.addNodeQueue("ddd");
        System.out.println(queue);
        queue.removeNodeQueue();
        System.out.println(queue);
        queue.removeNodeQueue();
        queue.removeNodeQueue();
        System.out.println(queue);
    }
}

Linked List

public class LinkedList {
    /***
     * 链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）
     */
    private Node head; //链表头
    private Node tail; //链表尾
    private int size; //节点数

    /**
     * 双端链表
     */
    public class Node{
        private Object data;
        private Node prev; //上一个
        private Node next; //下一个

        public Node(Object data) {
            this.data = data;
        }
    }

    public LinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头添加数据
     * @param object
     */
    public void addHead(Object object){
        Node node = new Node(object);
        if(size == 0){
            head = node;
            tail = node;
            size++;
        }else{
            head.prev = node;
            node.next = head;
            head = node;
            size++;
        }
    }

    /**
     * 删除头
     */
    public void deleteHead(){
        //头部指向下一个，prev值为null则说明是链表的头部
        if(size != 0){
            head.prev = null;
            head = head.next;
            size--;
        }
    }


    /**
     *向链表尾添加数据
     * @param object
     */
    public void addTail(Object object){
        Node node = new Node(object);
        if(size == 0){
            head = node;
            tail = node;
            size++;
        }else{
            node.prev = tail;
            tail.next = node;
            tail = node;
            size++;
        }
    }

    /**
     * 删除尾部
     */
    public void deleteTail(){
        //尾部指向上一个，next值为null则说明是链表的尾部
        if(size != 0){
            tail.next = null;
            tail = tail.prev;
            size--;
        }
    }

    /**
     * 显示数据
     */
    public void display(){
        Node node = head;
        while (size > 0){
            System.out.print("["+node.data+"->");
            node = node.next;
            size--;
        }
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addHead("123");
//        linkedList.addHead("abc");
//        linkedList.addHead("%$$");
//        linkedList.addTail("+_+");
//        linkedList.addTail("hello");
        linkedList.addTail("word");
        linkedList.deleteHead();
        linkedList.deleteTail();
        linkedList.display();
    }
}

Binary Tree

二叉树(由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成)
二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构。

Heap

Hashing

Alt text

Graph

Alt text

算法

排序

快速排序

Alt text

归并排序

桶排序

Alt text

基数排序

图算法

深度优先搜索

image

广度优先搜索

image

拓扑排序

Dijkstra 算法

image

Bellman-Ford 算法

image

Floyd-Warshall 算法

Prim 算法

image

Kruskal 算法

image

位运算

结语

未完待续......。
个人博客~
简书~

上一篇 下一篇

猜你喜欢

热点阅读