二分法查找算法和数据结构-10

查找——从一组数据中查找需要的那一个数据的位置

• 顺序查找
  • 数组 [12，34，7，69，22，11，15]
  • 查找 11 ---- 4
  • 查找 17----- -1
• 二分法查找（折半查找）

前提：数组中的数据是有序的（默认：从小到大）

代码示例：

package com.qfedu.array_5;

import java.util.Scanner;

public class HalfSearch {

    
    public int search(int[] arr,int n,int startIndex ,int endIndex){
        int midIndex = (startIndex + endIndex)/2;
        if(arr[midIndex] == n){
            return midIndex;
        }else if( arr[midIndex]>n && startIndex
            //左边找
            return search(arr,n,startIndex,midIndex-1);
        }else if( arr[midIndex]
            //右边找
            return search(arr,n,midIndex+1,endIndex);
        }else{
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,4,6,9,12,15,17,18,23,35,44,56,58,61,63,65,69,77,86,90,94,100};
        System.out.println("请输入要查找的数字：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HalfSearch hs = new HalfSearch();
        int i = hs.search(arr, n, 0, arr.length - 1);
        System.out.println(i);
    }

}

数据结构——数据在程序中的存储方式（数据的组织形式）

• 通用数据结构：顺序表、链表、栈、树、图
• 自定义数据结构： …

• 特性
  • 存储的元素是有序的，且有索引
  • 顺序表支持数据的插入和移除操作
  • 顺序表的数据是连续存储的
• 优点
  • 查询数据、修改数据效率较高
• 缺点
  • 移除数据、插入数据涉及到内存移动，执行效率较低

package com.qfedu.array_6;

import java.util.ArrayList;

public class TestArrayList {

    public static void main(String[] args) {
        //顺序表：java.util.ArrayList

        //创建顺序表（就是创建ArrayList类的对象）
        ArrayList seqTable = new ArrayList();
        //获取顺序表的长度
        int size = seqTable.size();
        System.out.println(size);
        //往顺序表中添加一个元素
        seqTable.add("aaa");
        seqTable.add("bbb");
        seqTable.add("ccc");
        seqTable.add("ddd");
        size = seqTable.size();
        System.out.println(size);
        //直接打印顺序表对象，可以输出元素
        System.out.println(seqTable);
        //移除元素
        seqTable.remove(2);
        //获取元素
        System.out.println(seqTable.get(2));
        //插入元素
        seqTable.add(1,"ddd");
        System.out.println(seqTable);
    }

}

• 定义

  • 通过元素结点之间的相互指向建立的序列

  • 链表分为单向链表和双向链表

• 优点：

  • 插入元素、移除元素效率较高

• 缺点：

  • 查询元素、修改元素效率较低

package com.qfedu.array_6;

import java.util.ArrayList;
import java.util.LinkedList;

public class TestLinkedList {

    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();
        LinkedList linkedList = new LinkedList();

        //添加元素
        arrayList.add("aaa");
        arrayList.add("bbb");
        arrayList.add("ccc");
        
        linkedList.add("aaa");
        linkedList.add("bbb");
        linkedList.add("ccc");
        
        //获取元素
        String s1 = (String)arrayList.get(1);
        String s2 = (String) linkedList.get(1);

        //插入元素
        arrayList.add(1,"ddd");
        linkedList.add(1,"ddd");
        
        //修改元素
        arrayList.set(1,"eee");
        linkedList.set(1,"eee");
        
        //移除元素
        arrayList.remove(1);
        linkedList.remove(1);
        
    }
    
}

概念：存储数据的容器

特性：先进后出（FILO），后进先出

特性：先进先出（FIFO）

• 构造规则：小的放左边，大的放右边

• 遍历规则：

  • 先序遍历（父结点—左子结点—右子结点） ：8-6-4-3-5-17-12-29

  • 中序遍历（左子结点—父结点—右子结点）：3-4-5-6-8-12-17-29

  • 后续遍历（左子结点—右子结点—父结点）：3-5-4-6-12-29-17-8

略

• 在类中定义成员变量（直接定义在类中的变量），其对象可以用来存储数据的类称为实体类。

public class Product {

    
    public int productId ;
    public String productName;
    public double productPrice;
    public int productSellNum;

}

Product p2 = new Product();

Product p1 = new Product();
p1.productId = 1;
p1.productName = "娃哈哈";
p1.productPrice = 2.00;
p1.productSellNum = 999;