算法与数据结构（1）

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

逻辑结构： 集合结构， 线性结构，树形结构，图形结构。
存储结构： 表，堆栈，队列，数组，树，二叉树，图。

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

常用算法：
▪ 递推法
▪ 递归法
▪ 穷举法
▪ 贪心算法
▪ 分治法
▪ 动态规划法
▪ 迭代法
▪ 分支界限法

时间复杂度 空间复杂度

程序的质量=空间复杂度+时间复杂度+应用场景（重要）

问题：交换两个数的值？
int a = 5;
int b = 6;
// 1. 可读性最好的
int t=a;a=b;b=t;
// 2. 加减法运算
a=a+b;// a=11 b=6
b=a-b;// a=11 b=5
a=a-b;// a=6 b=5
// 3 .位运算 性能最优（没有可读性） 无人机 跑步
a = a ^ b;
b = a ^ b;；
a = a ^ b;
System.out.println("a=" + a + "--- b=" + b);

线性表：
顺序存储结构：
顺序表

链式存储：

节点 ： 数据域 指针域

MessageQueue 中message 插入过程

微信图片_20201201210628.png 微信图片_20201201210636.png 微信图片_20201201210640.png 微信图片_20201201210645.png 微信图片_20201201211241.png 微信图片_20201201211246.png radixSort.png

单链表 运用 极速排序 麻将牌排序：

微信图片_20201201213635.png 微信图片_20201201213639.png 微信图片_20201201213643.png 微信图片_20201201222529.png

/**

• Created by Jett on 2018/11/28.
  */

public class LinkedList<E> {
/**
* 结点
*/
private static class Node<E> {
E item;
Node<E> prev;
Node<E> next;

    public Node(Node<E> prev, E item, Node<E> next) {
        this.item = item;
        this.prev = prev;
        this.next = next;
    }
}

public LinkedList() {

}

//头节点
Node<E> first;
//尾节点
Node<E> last;
//大小
int size;

/**
 * 添加数据在最后
 */
public void add(E e) {
    linkLast(e);
}

/**
 * 添加到最后
 * @param e
 */
private void linkLast(E e) {
    Node<E> newNode = new Node<E>(last, e, null);
    Node<E> l = last;
    last=newNode;

    if(l==null){
        first=newNode;
    }else {
        l.next = newNode;
    }
    size++;
}
/**
 * 查找位置
 */
public E get(int index){
    if(index<0 || index>size){
        return null;
    }
    return node(index).item;
}
/**
 * 获取index位置上的节点
 */
private Node<E> node(int index){

    //如果index在整个链表的前半部分
    if(index<(size>>1)){   //1000 100   10
        Node<E> node=first;
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        return node;
    }else{
        Node<E> node=last;
        for (int i = size-1; i > index; i--) {
            node=node.prev;
        }
        return node;
    }


}

/**
 * 添加数据在index位置
 */
public void add(int index,E e) {
    if(index<0 || index>size){
        return ;
    }
    if(index==size){
        linkLast(e);
    }else{
        Node<E> target=node(index);//  index=2
        Node<E> pre=target.prev;
        Node<E> newNode=new Node<E>(pre,e,target);

        if(pre==null){
            first=newNode;
            target.prev = newNode;//4
        }else {
            pre.next = newNode;//3
            target.prev = newNode;//4
        }
        size++;
    }

}

/**
 * 删除元素
 */
public void remove(int index){
    Node<E> target=node(index);
    unlinkNode(target);
}

private void unlinkNode(Node<E> p) {//index=2
    Node<E> pre=p.prev;
    Node<E> next=p.next;
    if(pre==null){
        first=p.next;
    }else{
        pre.next=p.next;
    }
    if(next==null){
        last=p.prev;
    }else{
        next.prev=p.prev;
    }
    size--;
}

}

/**

• Created by Jett on 2018/11/28.
  */

public class test {
@Test
public void test() {
LinkedList<Integer> linkedList=new LinkedList<>();
linkedList.add(0,4);
linkedList.add(0,1);
linkedList.add(0,2);
linkedList.add(0,3);//43 66 12
linkedList.add(0,66);
linkedList.add(0,88);
//0:66 1:4 2:3 3:1 4:2
// linkedList.remove(0);

    for (int i = 0; i < linkedList.size; i++) {
        System.out.print(i+":"+linkedList.get(i)+"    ");
    }
}

}