数据结构与算法基础（王卓）

1.数据类型(一种性质相同的值的集合)

例如c语言中的int,char, float, double.//不需要自己进行定义

如果是复杂的数据类型，不能够直接表示。

数据类型规范了变量所有可能的取值范围。

2.抽象数据类型(ADT) 抽象类型名{ }。

可以自己进行自行定义。

(黑马)

时间复杂度

第一种叫做上界（大O表示法），第二种叫做下界，最后叫做紧界。(大O表示法)

例1

1. 找到原始f(n)函数
2. 找到g(n)可以作为f(n)的渐进上界
3. O(g(n))成立

例2

1. f(n) =5*floor($log_2(n)$)+9

2. $log_2(n)$

3. $O(log_2(n))$

常见大O表示法

优到劣

• 黑色/最优时间复杂度
• 绿色/对数时间
• 蓝色/线性时间，算法时间与数据规模成正比
• 橙色/O(n*log(n))拟线性时间
• 红色/O($n^2$)平方时间
• 黑色/O($2^n$)指数时间
• O（n!)阶乘时间

二分查找基础版

public static int barrySer(int[] a,int target){
        int i=0,j=a.length-1;
        int m=0;
        while(i<=j){//m的目的是找中间位的数，提高程序效率
            //m=(i+j)/2;//如果两数相加超出int的最高位，则改变符号位
            m=(i+j)>>>1;//无符号右移
           if(target<a[m]){
               j=m-1;
           }else if(target>a[m]){
               i=m+1;
           }else{
               return m;
           }
        }
        return -1;
    }

二分查找平衡版

public static int barrySer(int a[],int target){
        int i=0,j=a.length;
        int m=0;
        while(1<j-i){//范围内待查找的元素个数
            m=(i+j)>>>1;
           if(target<a[m]){
               j=m;
           }else{//循环内只能做一次比较，比较次数平衡了
               i=m;//中间值包括在内
           }
        }
     if(a[i]==target){
         return i;
     }else{
     	 return -1;
     }
   }

二分查找java版

Arrays包

public class testBs {
    @Test
    public void test(){
        int target=9;
        /*[2,5,8]   a
        * [2,0,0,0]  b
        * [2,4,0,0]
        * [2,4,5,8]
        * 分四步走，要扩容数组*/
        int []a={7,13,21,30,38,44,52,53};
        /*assertEquals(0,barrySer(a,7));//期望索引位置*/
        int i= Arrays.binarySearch(a,target);//二分查找方法
        System.out.println(i);
        if(i<0){
            int insertIndex =Math.abs(i+1);//计算可以插入的索引位置
            int[] b=new int[a.length+1];//创造一个较大的新数组
            System.arraycopy(a,0,b,0,insertIndex);//数组起始位置和copy的起始位置，还有下标索引
            b[insertIndex]=target;//将索引位置插入要插入的值
            System.arraycopy(a,insertIndex,b,insertIndex+1,a.length-insertIndex);
            //开始拷贝剩下的数组元素，长度为a数组的长度减去插入位置下标的大小
            System.out.println(Arrays.toString(b));
        }

    }
}

升级版找到重复元素中最左侧的

public static int barrySer(int a[],int target){
        int i=0,j=a.length-1;
        int m=0;
        int candidate =-1; 
        while(i<=j){
            m=(i+j)>>>1;
           if(target<a[m]){
               j=m-1;
           }else if(a[m]<target){
               i=m+1;
           }else{
               candidate =m;
               j=m-1;
           }
        }
     return candidate;
   }

升级版找到重复元素中最右侧的

public static int barrySer(int a[],int target){
        int i=0,j=a.length-1;
        int m=0;
        int candidate =-1;
        while(i<=j){
            m=(i+j)>>>1;
           if(target<a[m]){
               j=m-1;
           }else if(a[m]<target){
               i=m+1;
           }else{
               candidate =m;
               i=m+1;
           }
        }
     return candidate;
   }

可能出现的题目。

数组

类指针占四个字节，数组大小占四个字节，加起来就是八个字节

如果只有指针存在而数组中并未存进数，也会开辟空间，如图。

动态数组

数组添加元素以及遍历循环

public class array {//类名
    public int size = 0;//逻辑大小
    private int capacity = 8;//容量
    private int[] arrays = new int[capacity];
    //开辟容量大小的空间
    public void addList(int element) {//待插入值，用户键入的值
        arrays[size] = element;//进行键入size为索引的值
        size++;//索引值增加
    }
    void add(int index, int element) {//插入元素
        if (index >= 0 && index < size) {//1.将数组向后移动
            System.arraycopy(arrays, index, arrays,
                    index + 1, size - index);
         //原数组，要复制的起始位置，目的数组，赋值起始位置，数组的索引减去要插入到index位置的长度
        }
        arrays[index] = element;//2.将要插入的数插入
        size++;//索引++
    }

     void forEach(Consumer<Integer> consumer){//循环遍历，函数型接口
        for(int i=0;i<size;i++){
            //System.out.println(arrays[i]);
            //提供array[i]
            //返回void
            consumer.accept(arrays[i]);
        }
    }
}

	@Test
    public void test1(){
        array da=new array();
        da.addList(1);
        da.addList(2);
        da.addList(3);
        da.addList(4);
        da.addList(5);
        
        da.forEach((element)->{//函数型接口
            System.out.println(element);//自由定义要做什么事情
        });//开放功能，函数式接口
    }

java流遍历

public class array implements Iterable<Integer> {//要实现抽象方法，继承
    public int size = 0;//逻辑大小
    private int capacity = 8;//容量
    private int[] arrays = {};//懒惰初始化


    public void addList(int element) {//待插入值
        arrays[size] = element;
        size++;//索引的值
    }

    void add(int index, int element) {
        if (index >= 0 && index < size) {
            System.arraycopy(arrays, index, arrays,
                    index + 1, size - index);
        }//想最后一行插入
        arrays[index] = element;
        size++;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {//一键生成
            int i = 0;

            @Override
            public boolean hasNext() {//有没有下一个元素
                return i < size;//返还true或者false
            }
            @Override
            public Integer next() {//返回当前元素，并移动下一个元素
                return arrays[i++];//返还元素，然后进行自加
            }
        }
    }
    //***************java流遍历****************
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(arrays, 0, size));//遍历数组，起始位置，遍历大小
    }
}

    @Test
    public void test3(){
        array da=new array();
        da.addList(1);
        da.addList(2);
        da.addList(3);
        da.addList(4);
        da.stream().forEach(element->{//java流输出遍历
            System.out.println(element);
        });
    }

java进行删除和扩容

public class array implements Iterable<Integer> {//要实现抽象方法
    public int size = 0;//逻辑大小
    private int capacity = 8;//容量
    private int[] arrays = {};//懒惰初始化

    public void addList(int element) {//待插入值
        arrays[size] = element;
        size++;//索引的值
    }

    void add(int index, int element) {
        check();//抽取方法ctrl+alt+m
        if (index >= 0 && index < size) {
            System.arraycopy(arrays, index, arrays,
                    index + 1, size - index);
        }//想最后一行插入
        arrays[index] = element;
        size++;
    }

    private void check() {
        if (size == 0) {
            arrays = new int[capacity];//使用则开辟空间
        } else if (size == capacity) {
            //进行扩容，java一般扩容1.5倍
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];//为新数组开辟空间
            System.arraycopy(arrays, 0,//将数组先赋值给目标数组
                    newArray, 0, size);
            arrays = newArray;//将目标数组地址给原数组
        }
    }

    public int remove(int index) {//{0...size}
        int removed = arrays[index];//先获取要删除的位置
        if (index < size - 1) {//位置小于数组长度
            System.arraycopy(arrays, index + 1,//索引后都向前移动
                    arrays, index, size - index - 1);//移动到索引位置，相当于直接覆盖
        }
        size--;//要遍历的长度减少了
        return removed;
    }
}

数组缓存运算

如果读取[0] [0]那么后面64个字节都已经读取好了，不需要去内存中读取，缓存中可以直接找到数据。(外层循环控制行数，内层循环控制列数的原因)

链表

单向链表(头部添加)

class linkList{//链表类
   //方法要全部封装起来
    private head=null;
    public void addFirst(int value){
        head=new Node(value,head);//新节点的head赋值给引用值
    }
   
    public void loop(Consumer<Integer> consumer){
        Node p=head;
        while(p!=null){
            consumer.accept(p.value);
            p=p.next;
        }
    }
    
   private static class Node{//节点类
        int value;
        Node next;
        //构造方法
        public Node(int value,Node next){
            this.value=value;
            this.next=next;
        }
    }
}

//测试类
class testlinkList{
    @Test
    public void test1(){
        linkList l=new linkList();
        l.addFirst(1);
        l.addFirst(2);
        l.addFirst(3);
        l.addFirst(4);
        
        l.loop((value)->{
            System.out.println(value);
        });
    }
}

尾部添加

class linkList implments Interge<Interable>{
    private Node head=null;
    public void addFirst(int value){
        head=new Node(value,head);
    }
    private Node findLast(){
        Node p=head;
        while(p.next!=null){//p等于null(不会存在此情况)
            p=p.next;
        }
        return p;
    }
    public void addLast(int value){
		Node last=findLast();
        last.next=new Node(value,null);
    }
    public void loop(Consumer<Interge> consumer){
        while(p!=null){
            consumer.Accept(p.value);
            p=p.next;
        }
    }
    
   private static class Node{
        int value;
        Node next;
        public void Node(int value,Node next){
            this.value=value;
            this.next=next;
        }
    }
}

指定位置插入

class linkList implments Interge<Interable>{
    private Node head=null;
    public void addFirst(int value){
        head=new Node(value,head);
    }
    private Node findLast(){
        Node p=head;
        while(p.next!=null){//p等于null(不会存在此情况)
            p=p.next;
        }
        return p;
    }
    public void addLast(int value){
		Node last=findLast();
        last.next=new Node(value,null);
    }
    public Node findNode(int index){//找到指定节点
        int i=0;
        while(p!=null){
            if(i==index){
                return p;
            }
            p=p.next;
            i++;
        }
        return null;
    }
    
    public int get(int index){
        Node node =findNode(index);
        if(node == null){
			illegalIndex(index);//抛出异常,抽取方法
        }
        return node.value;
    }
    private static void illegalIndex(int index){//抽取的方法
        throw new IllegalArgumentException(
        String.format("index[%d]不合法",index));
    }
    //因为接口必须要实现抽象的方法
    @Override
    public Iterator<Integer> iterator(){
		return new Iterator<Integer>(){//返还一个新的迭代器对象
            Node p=head.next;
            @Override
            public boolean hasNext(){
                return p!=null;
                //如果不等于就返回true，否则返回false
            }
            public Integer next(){//返回当前元素，指向下一个元素
                int v=p.value;
                p=p.next;
                return v;
            }
        };//分号不要忘记
    }
    public void loop(Consumer<Interge> consumer){
        while(p!=null){
            consumer.Accept(p.value);
            p=p.next;
        }
    }
    public void insert(int index,int value){
        if(index==0){
            addFirst(value);
            return ;
        }
        Node pres=findNode(index-1);
        if(pres==null){
            illegalIndex(index);
        }
        pres.next=new Node(value,pres.next);
    }
    private static class Node{
        int value;
        Node next;
        public void Node(int value,Node next){
            this.value=value;
            this.next=next;
        }
    }
}

找指定节点方法以及迭代器遍历

class linkList implements Interable<Integer>{
    Node head=null;
    public addFirst(int value){
      	head=new Node(value,head);
    }
    public Node findNode(int index){//找到指定节点
        int i=0;
        while(p!=null){
            if(i==index){
                return p;
            }
            p=p.next;
            i++;
        }
        return null;
    }
    
    public int get(int index){
        Node node =findNode(index);
        if(node == null){
			illegalIndex(index);//抛出异常,抽取方法
        }
        return node.value;
    }
    private static void illegalIndex(int index){//抽取的方法
        throw new IllegalArgumentException(
        String.format("index[%d]不合法",index));
    }
    //因为接口必须要实现抽象的方法
    @Override
    public Iterator<Integer> iterator(){
		return new Iterator<Integer>(){//返还一个新的迭代器对象
            Node p=head.next;
            @Override
            public boolean hasNext(){
                return p!=null;
                //如果不等于就返回true，否则返回false
            }
            public Integer next(){//返回当前元素，指向下一个元素
                int v=p.value;
                p=p.next;
                return v;
            }
        };//分号不要忘记
    }
    private static class Node{
        int value;
        Node next;
        public void Node(int value,Node next){
            this.value=value;
            this.next=next;
        }
    }
}

class testLinkList{
    @Test
    public void test(){
        getLinkList();
        for(Integer value:list){
            System.out.println(value);
        }
    }
    private void getLinkList(){
        LinkList list=new LinkList();
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.addFirst(4);
    }
}

删除功能(独立方法并未实现完整链表)

public void removeFirst(){
    if(head==null){
        illegalIndex(index);
    }
    head=head.next;
}

public void remove(int index){
    if(index==0){
        removeFirst();
        return ;
    }
    Node prev=findNode(index-1);
    if(prev==null){
        illeaglIndex(index);
    }
    Node removed=prev.next;
    if(removed==null){
        illeaglIndex(index);
    }
    prev.next=removed.next;
}

本栏目推荐文章
• 2024/1/13 算法笔记
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 【Shell基础】Bash基础与Linux三剑客
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 数据可视化是如何帮助大型企业提高效率的？

数据结构 算法 结构 基础 数据数据结构 算法 结构 基础 算法 数据结构 基础知识 工程师 数据结构 算法 结构 数据 算法 数据结构 根基 线性 算法 数据结构 根基 结构 算法 数据结构 结构 数据 数据结构 算法 结构 目录 队列 算法 层级 数据结构 数据结构 队列 算法 结构 数据结构 数组 算法 结构