真正的数据结构和算法【1】

学习目录

1.数据结构和算法概述

数据结构:对计算机内存中的数据的一种安排;
算法:对结构中的数据进行各种处理;
应用:

1.现实世界的数据存储,把现实世界的东西抽象成数据下来; 
2.程序员的工具,不限制语言的,掌握了数据结构就能了解什么时候用哪种方式进行抽象;
3.现实世界的建模;

数据结构

1.数组 插入快,查找慢,删除慢,大小固定;
2.有序数组 比无序数组查找快;
3.栈 后进先出的方式存取,存取其他项很慢;
4.队列 先进先出的方式存取
5.链表 插入快,删除快,查找慢
6.二叉树 查找 插入 删除都快(树平衡的情况下) 删除算法复杂
7.红黑树 查找 插入 删除 都快 算法复杂
8.2-3-4树
9.哈希表 插入快,通过关键字存取快 删除慢
10.堆 插入 删除快 对最大数据项的存取快 对其他数据项存取慢
11.图 对现实世界建模 有些算法慢且复杂

算法

1.排序
2.增删改查

2.数组基础知识

数组:存储一种数据类型相同的数据的集合
声明数组,创建数组;

对数组的操作:

1.展示所有的数据(遍历)
2.插入
3.删除
4.修改
5.查找

设计一个数组类

1.声明变量 数组 数组中元素数量
2.构造方法 入参 传入为数组最大长度 初始化数组
3.查找 根据值查索引
4.插入 传入值
5.查看所有 
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package Array;

/**
 * @author Zen
 * @version $Id: MyArray.java, v 0.1 2019/05/08 15:23 Zen Exp $
 * 设计一个数组类
 *     1.声明变量 数组 数组中元素数量
 *     2.构造方法 入参 传入为数组最大长度 初始化数组
 *     3.查找 根据值查索引
 *     4.插入 传入值
 *     5.查看所有
 */
public class MyArray {

    int[] arr;
    int num = 0;

    /**
     * 构造方法:根据传入的maxsize值,初始化数组;
     * @param maxsize
     */
    public MyArray(int maxsize){
        arr = new int[maxsize];
    }

    /**
     * 插入 传入数值,在数组的末尾插入
     * @param value
     */
    public void add(int value){
        arr[num] = value;
        num++;
    }

    /**
     * 展示所有数组中的元素
     */
    public void showAll(){
        for(int i = 0;i < num; i++) {
            System.out.print(arr[i]+ "  ");
        }
    }

    /**
     * 根据值查找其在数组中的第一个索引值 线性查找
     * @param value
     * @return
     */
    public int searchFirstIndex(int value){
        int index = -1;
       for(int i = 0;i < num ; i++){
           if(arr[i] == value) {
               index = i;
           }
       }
       return index;
    }

    /**
     * 删除最后一个元素
     */
    public void pop(){
        arr[num] = 0;
        num --;
    }

    /**
     * 删除一个已知元素
     * @param value
     */
    public void delete(int value){
        int index = searchFirstIndex(value);
        for(int i = index;i < num - 1;i++) {
            arr[index] = arr[index + 1];
            index++;
        }
        num--;
    }
}

Java数据结构和算法_有序数组和二分查找

有序数组
优点:查找速度比无序数组快多了
缺点:插入时要按排序方式把后面的数据进行移动
有序数组和无序数组的共同缺点:删除时必须把后面的数据向前移动,来填补删除项的空洞。

设计:一个有序数组类

1.声明数组
2.数组元素个数
3.构造函数 根据传入的值 初始化数组;
4.查看元素个数
5.插入的方法[这个是主要需要思考的地方,对数据进行插入操作时,是需要考虑多种情况的]
6.添加数据项(线性查找)
7.删除数据项
8.显示所有数据量
9.二分查找

二分查找[建立在有序数组的基础上] 二分查找的效率很高;折半查找

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package array;

/**
 * @author Zen
 * @version $Id: OrderArray.java, v 0.1 2019/05/08 16:16 Zen Exp $
 * 设计:一个有序数组类
 *     1.声明数组
 *     2.数组元素个数
 *     3.构造函数 根据传入的值 初始化数组;
 *     4.查看元素个数
 *     5.插入的方法
 *     6.添加数据项(线性查找)
 *     7.删除数据项
 *     8.显示所有数据量
 *     9.二分查找
 *
 */
public class OrderArray {
    int[] arr;
    int size = 0;

    /**
     * 构造方法 根据传入的maxsize初始化数组
     * @param maxsize
     */
    public OrderArray(int maxsize) {
        arr = new int[maxsize];
    }

    /**
     * 获取数组元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 有序数组插入值
     * @param value
     */
    public void insert(int value){
        if(size == 0){
            arr[0] = value;
        }else if(value >= arr[size -1]){
            arr[size] = value;
        }else{
            for (int i = 0; i < size; i++) {
                if (arr[i] > value) {
                    for(int j = size; j > i;j--){
                        arr[j] = arr[j-1];
                    }
                    arr[i] =value;
                    break;
                }
            }
        }
        size++;

    }

    /**
     * 线性查找索引
     * @param value
     * @return
     */
    public int searchFirstIndex(int value){
        int index = -1;
        for(int i = 0 ;i < size ;i++){
            if(arr[i] == value){
                index = i;
            }
        }
        return index;
    }

    /**
     * 删除该值
     * @param value
     */
    public void delete(int value) {
        int index = searchFirstIndex(value);
        for (int i = index; i < size - 1; i++) {
            arr[index] = arr[index + 1];
            index++;
        }
        size--;
    }

    /**
     * 展示所有数组中的元素
     */
    public void showAll(){
        for(int i = 0;i < size; i++) {
            System.out.print(arr[i]+ "  ");
        }
        System.out.println();
    }

    public int binarySearch(int value) {
        int index = -1;
        int min = 0;
        int max = size -1;
        while(min <= max){
            int mid = (min + max) >>> 1;
            if(arr[mid] == value){
                index = mid;
                break;
            }else if(arr[mid] < value){
                min = mid + 1;
            }else{
                max = mid -1 ;
            }
        }
        return index;
    }

}

本文链接:

https://heyzen.club/index.php/Coder/287.html
1 + 2 =
快来做第一个评论的人吧~