ds之数组

发表于 | 分类于 | 阅读次数:
字数统计: 1.1k | 阅读时长 ≈ 4

为什么数组从零开始

数组是一种线性表数据结构 连续的内存空间来存储一组具有相同类型的数据

数组支持随机访问 根据下标随机访问的时间复杂度为1 适合查找

插入和删除这两个操作比较低效

避免数据搬移 可以先记录下已经删除的数据 每次的删除并不是真正地搬移数据 只是记录数据已经被删除 当数组没有更多空间存储数据时 再触发执行一次真正的删除操作 这样就大大减少了删除操作导致的数据迁移

警惕数组越界的问题 在c语言当中 只要不是访问受限的内存 所有的内存空间都是可以自由访问的 根据数组寻址公式 会定位到某个不属于数组的内存地址上 导致代码的无限循环

访问数组的本质就是访问一段连续内存 只要数组通过偏移计算得到的内存地址是可用的 那么程序有可能不会报任何错误

计算机病毒很多也是利用数组越界访问非法地址的漏洞 来攻击系统 一定要警惕数组越界

c语言当中数组越界检查的工作是給程序员来做的 java则是本身会做越界检查

java提供了容器类 ArrayList

最大的优势是将很多数组的操作封装起来 支持动态扩容

作为高级语言编程者，是不是数组就无用武之地了呢？当然不是

1.Java ArrayList 无法存储基本类型，比如 int long 需要进行封装
2.数据大小事先已知 并且操作简单 可以直接使用数组
3.多维数组情况下 数组更加直观比如 Object[][] array

业务开发情况下 直接使用容器即可 省时省力 做非常底层的开发

性能的优化做到极致 数组优于容器

下标其实是偏移 从1开始计数 每次随机访问元素都需要多一次减法操作

效率优化做到极致？

主要还是历史原因 c语言设计值用0开始计数数组下标。

无论是java js等都是进行模仿

python支持负数下标。

顺便复习学习一下java语言

google家的规范是 2个空格作为缩进！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package array;

/**
 * 1) 数组的插入、删除、按照下标随机访问操作；
 * 2）数组中的数据是int类型的；
 *
 */
public class ArrayOperate {
    //定义整型数据data保存数据
    public int data[];
    //定义数组长度
    private int n;
    //定义中实际个数
    private int count;

    //构造方法，定义数组大小
    public ArrayOperate(int capacity){
        this.data = new int[capacity];
        this.n = capacity;
        this.count=0;//一开始一个数都没有存所以为0
    }

    //根据索引，找到数据中的元素并返回
    public int find(int index){
        if (index<0 || index>=count) return -1;
        return data[index];
    }

    //插入元素:头部插入，尾部插入
    public boolean insert(int index, int value){
        //数组中无元素

        //if (index == count && count == 0) {
        //    data[index] = value;
        //    ++count;
        //    return true;
        //}

        // 数组空间已满
        if (count == n) {
            System.out.println("没有可插入的位置");
            return false;
        }
        // 如果count还没满，那么就可以插入数据到数组中
        // 位置不合法
        if (index < 0||index > count ) {
            System.out.println("位置不合法");
            return false;
        }
        // 位置合法
        for( int i = count; i > index; --i){
            data[i] = data[i - 1];
        }
        data[index] = value;
        ++count;
        return true;
    }
    //根据索引，删除数组中元素
    public boolean delete(int index){
        if (index<0 || index >=count) return false;
        //从删除位置开始，将后面的元素向前移动一位
        for (int i=index+1; i<count; ++i){
            data[i-1] = data[i];
        }
        //删除数组末尾元素  这段代码不需要也可以
        /*int[] arr = new int[count-1];
        for (int i=0; i<count-1;i++){
            arr[i] = data[i];
        }
        this.data = arr;*/
        --count;
        return true;
    }
    public void printAll() {
        for (int i = 0; i < count; ++i) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayOperate array = new ArrayOperate(5);
        array.printAll();
        array.insert(0, 3);
        array.insert(0, 4);
        array.insert(1, 5);
        array.insert(3, 9);
        array.insert(3, 10);
        //array.insert(3, 11);
        array.printAll();
    }


}