数据结构Java版（1）——数组

一、数据结构

1. 是一门基础学科
2. 研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据和修改数据
3. 数据结构可以分为三类： 线性结构： 数组、队列、栈、链表、哈希表… 树型结构：二叉树、二分搜索树、AVL树，红黑树、堆、Trie、线段树、并查集… 图结构：邻接矩阵、邻接表 排序算法
4. 为什么学习数据结构： 根据不同的应用，灵活选择最合适的数据结构

数据结构 + 算法 = 程序

二、数组

1、数组基础

• 用来存储一组类型相同的数据
• 在内存中，分配连续的空间，数组创建时要指定容量（大小）
• 数据类型[] 数组名 int[] arr = new int[10] int[] arr2 = {1,2,3,4}
• 索引---访问数组时通过索引进行操作
• 索引从0开始，最大为 arr.length -1
• 常见的错误： NullPointException和ArrayIndexOutOfBoundsException
• 常见的数组： 字符串， 对象数组，哈希表

2.Java中数组的特点

（1）数组在内存中连续分配；

（2）创建数组时要指明数组的大小；

（3）可以通过索引进行访问，索引从0开始，这里索引可以理解为偏移量；

（4）使用索引：

• 获取指定索引位置的值——arr[index]
• 修改指定索引位置的值——arr[inedx]
• 删除数组中元素（假删除）

（5）数组的遍历：将数组中元素打印出来；

（6）数组创建好之后，大小不能改变。

3.演示数组的使用

import java.util.Arrays;
import java.util.Comparator;

public class ArrayDome {
    public static void main(String[] args) {
        //练习数组的相关知识
        //1.定义数组
        int[] ints  =  new int[]{1,1,4,5,1,4};
        //获取数组长度
        int length = ints.length;
        //获取指定元素位置
        int num = ints[2];
        System.out.println(num);
        //修改元素
        ints[2] =100;
        num = ints[2];
        System.out.println(num);
        //遍历数组
        for(int i= 0;i < ints.length;i++){
            System.out.print(ints[i]+"\t");
        }
        System.out.println();
        //数组越界错误
        try{
            System.out.println(ints[length]);
        }catch (Exception e){
            e.printStackTrace();
        }
        //数组为空错误
        String[] strings = null;
        try{
            System.out.println(strings);
            length = strings.length;
        }catch (Exception e){
            e.printStackTrace();
        }
        //数组的排序
        Arrays.sort(ints);
        for(int i= 0;i < ints.length;i++){
            System.out.print(ints[i]+"\t");
        }
        System.out.println();
    }
}

输出结果：

4.制作自己的数组

package leetcoke;

import java.util.Arrays;
import java.util.Comparator;

public class MyArray<T> {
    private T[] data;
    private int length;
    private int size;

    //构造方法
    public MyArray(int size) {
        if (size <= 0) {
            this.size = 16;
        } else {
            this.size = size;
        }
        this.length = 0;
        this.data = (T[]) new Object[this.size];
    }

    //获得当前的数组容量
    public int getSize() {
        return this.size;
    }

    //判断是否为空
    public boolean isEmpty() {
        return this.length == 0;
    }

    //添加
    public void add(T data) throws IllegalAccessException {
        add(this.length,data);
    }

    //在指定位置添加
    public void add(int index, T data) throws IllegalAccessException {
        if (index < 0 || index > this.length) {
            throw new IllegalAccessException("你看你传的是个啥！");
        }
        //判断数组已满
        if(this.size==this.length){
            //扩容
            resize(this.size*2);
        }

        for (int i = this.length; i > index; i--) {
            this.data[i] = this.data[i - 1];
        }
        this.data[index] = data;
        this.length++;
    }

    //扩容
    private void resize(int newCapacity){
        T[] newData = (T[]) new Object[newCapacity];
        newData = Arrays.copyOf(this.data,newCapacity);
        this.data = newData;
        this.size = newCapacity;
    }

    //修改指定位置的值
    public void modifyValueByIndex(int index, T value) throws IllegalAccessException {
        //入参判断
        if (index < 0 || index >= this.size) {
            throw new IllegalAccessException("你看你传的是个啥！");
        }
        this.data[index] = value;
    }

    //获取位置上的值
    public T getValueByIndex(int index) throws IllegalAccessException {
        //入参判断
        if (index < 0 || index >= this.size) {
            throw new IllegalAccessException("你看你传的是个啥！");
        }
        return this.data[index];
    }

    //查询
    public int containsValue(T val) {
        int i;
        for (i = this.length - 1; i >= 0; i--) {
            if (this.data[i] == val) {
                return i;
            }
        }
        return i;
    }

    //根据索引删除
    public T removeByIndex(int index) throws IllegalAccessException {
        //入参判断
        if (this.length == 0) throw new IllegalAccessException("已经一点都不剩下了！");
        if (index < 0 || index >= this.size) {
            throw new IllegalAccessException("你看你传的是个啥！");
        }
        T res = this.data[index];
        for (int i = index + 1; i < this.length; i++) {
            this.data[i - 1] = this.data[i];
        }
        this.length--;
        if(this.length<=this.size/3 && this.size/2!=0){
            resize(this.size/2);
        }
        return res;
    }


    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer("[");
        for (int i = 0; i < this.length; i++) {
            buffer.append(this.data[i]);
            if (i != this.length - 1) {
                buffer.append(",");
            }
        }
        buffer.append("]");
        return buffer.toString();
    }

    //排序
    private T[] toArray1() {
        return Arrays.copyOf(data, length);
    }

    public void sort() {
        T[] array = toArray1();
        Arrays.sort(array, new Comparator<T>() {
            @Override
            public int compare(T o1, T o2) {
                if ((o1 instanceof Integer) || (o1 instanceof Float) || (o1 instanceof Double) || (o1 instanceof Short) || (o1 instanceof Long) || (o1 instanceof Byte)) {
                    return (Integer) o1 - (Integer) o2;
                }
                return 0;
            }
        });
        for(int i = 0;i < this.length;i++){
            this.data[i] = array[i];
        }
    }

    public static void main(String[] args) throws IllegalAccessException {
        MyArray<Integer> array = new MyArray<>(5);
        //输入数组的值
        for (int i = 0; i < 5; i++) {
            array.add((int) (Math.random() * 100 % 11));
        }
        try {
            System.out.println(array.getSize());
            array.add(3, 8);
        } catch (Exception e) {
            e.printStackTrace();
        }
        //排序
        array.sort();
        //遍历
        System.out.println(array);

        //查询
        try {
            System.out.println(array.getValueByIndex(2));
            //找索引
            System.out.println("8在数组中的位置为：" + array.containsValue(8));
        } catch (Exception e) {
            e.printStackTrace();
        }

        //删除值
        try {
            System.out.println(array.removeByIndex(array.containsValue(8)));

        } catch (Exception e) {
            e.printStackTrace();
        }


        //删除索引的位置
        try {
            System.out.println(array.removeByIndex(3));


        } catch (Exception e) {
            e.printStackTrace();
        }

        //向数组中指定位置添加元素
        try {
            System.out.println(array.getSize());
            array.add(3, 8);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(array);


        coke coke1 = new coke("coke", 18);
        coke coke2 = new coke("coke", 20);
        MyArray<coke> cokeMyArray = new MyArray<>(0);
        cokeMyArray.add(coke1);
        cokeMyArray.add(coke2);
        System.out.println(cokeMyArray);
    }
}

?