数据结构与算法(二)数组

什么是数组

  • 数组是有序的元素序列,若将有限个类型相同的变量的集合命名,那么这个名称为数组名。
  • 组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。
  • 用于区分数组的各个元素的数字编号称为下标。
  • 数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按有序的形式组织起来的一种形式。这些有序排列的同类数据元素的集合称为数组。

数组的特点

  1. 数组是相同数据类型的元素的集合。
  2. 数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。
  3. 数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如,a[0]表示名字为a的数组中的第一个元素,a[1]代表数组a的第二个元素,以此类推。

表现形式

  1. 一维数组
    int[] a; String[] strs;

  2. 二维数组
    int[][] a; String[][] strs;

随机访问

数组是由一块连续的内存空间和相同类型的数据构成的,所有他有个非常重要的特性:随机访问,它可以不需要通过遍历而直接取出某个下标中的元素。
而也正是由于需要保证数组的连续性,当进行插入和删除操作时,就必须做大量的迁移工作。
一维数组寻址公式: i_loc = init_loc + i * size

size 为元素的数据长度 如int类型为4个字节

example: init_loc = 100000

元素内存地址寻址公式
a[0]100000100000 + 0*4
a[1]100004100000 + 1*4
a[2]100008100000 + 2*4

这也是为什么数组都是以0为下标开始的原因

手写一个ArrayList

//定义接口
public interface MyList<E> extends Iterable<E> {

    int size();

    void add(E e);

    void add(E e,int index);

    void remove(int index);

    void remove(E e);

    E get(int index);

    Iterator<E> iterator();

    int indexOf(E e);
}

public class MyArrayList<E> implements MyList<E> {

    private Object[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity == 0) {
            data = new Object[DEFAULT_CAPACITY];
        } else {
            data = new Object[initialCapacity];
        }
    }
    @Override
    public void add(E element) {
        ensureAdd();    //判断是否即将越界,扩容
        data[size++] = element;
    }

    @Override
    public void add(E element, int index) { //6  3 size = 5
        ensureAdd();
        // 1 2 3 4 5  -> 1 2 3 6 4 5
        int srcPost = index;
        int destPost = index + 1;
        int length = size - index;
        System.arraycopy(data, srcPost, data, destPost, length);
        data[index] = element;
        size++;
    }

    private void ensureAdd(){
        if (size + 1 > data.length) {
            int newCapacity = data.length * 2;
            data = Arrays.copyOf(data, newCapacity);
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        return (E) data[index];
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int cursor;       // index of next element to return
            @Override
            public boolean hasNext() {
                return cursor != size;
            }
            @SuppressWarnings("unchecked")
            @Override
            public E next() {
                if (cursor >= size)
                    throw new NoSuchElementException();
                Object[] elementData = MyArrayList.this.data;
                if (cursor >= elementData.length)
                    throw new ConcurrentModificationException();
                return (E) elementData[cursor++];
            }
        };
    }

    @Override
    public void remove(int index) { // index = 2 size = 5
        //1 2 3 4 5  -> 1 2 4 5
        int srcPost = index + 1;
        int destPost = index;
        int length = size - index - 1; //2
        System.arraycopy(data, srcPost, data, destPost, length);
        data[--size] = null;
    }

    @Override
    public void remove(E element) { // 3 size=5
        //1 2 3 4 5 -> //1 2 4 5
        for (int i = 0; i < size; i++) {
            if (element == data[i]) {
                remove(i);
            }
        }
    }
    @Override
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (element == data[i]) return i;
        }
        return -1;
    }
    @Override
    public int size() {
        return size;
    }
# 数组 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×