算法和数据结构

数组这种数据结构的基本实现

2021年3月28日 /

1 为什么数组元素下标从0开始？

回答这个问题之前，先了解一下数组的特性：

首先，数组这种数据类型，在内存中是申请一片连续的存储空间。比如：如果每个数组元素占据1MB内从空间，申请长度为1000的数组，则内存中必须得有连续的1000MB的可用空间，否则数组分配空间申请失败。对比来看，如果申请的是一个链表的话，只要内存中的可用空间有1000MB即可，并不要求这些存储空间一定是连续的。

正是因为这种要求内存空间是连续的性质，就衍生出数组这种数据类型可以根据元素的索引下标快速定位元素，且其时间复杂度是O(1)。这是怎么实现的呢？因为内存连续，假定第1个元素内存地址为1000，每个元素占4个字节，那么，现在我想要访问第100个元素的话，则可以快速计算出内存地址=首元素地址+(100-1)*4=1396。更进一步，如果规定索引下标从0开始，那么要访问第100个元素的话，其实是要获取第99个元素。此时，其内存地址=首元素地址+99X4=1396。相比较而言，CPU就少了一次减法运算。

其次，数组这种数据类型是单一数据类型，长度固定，不可动态扩展长度。空间开辟小，则不够用，无法扩展，空间开辟大，用不完怎么办，空间浪费。

2 数组不仅是一种数据类型，还是一种数据结构

是的，这是在之前并没有认真认识到的一种数据结构，原来数组本身就是一种数据结构，还是一种非常常用的基础数据结构。

3 自己手写一个数组类

/**
 * @Author:asher
 * @Date:2021/3/26 20:28
 * @Description:PACKAGE_NAME
 * @Version:1.0
 */
//自己动手写一个Array类，让其封装一个整型数组
public class Array {
    //封装一个int[]数组的成员变量
    private int[] data;
    //表示数组实际存放的元素个数
    private int size;
​
    //构造方法，传入一个整型长度capacity，初始化一个数组
    public Array(int capacity) {
        data = new int[capacity];
        //初始化时，数组分配capacity个存储空间，但是没有存放任何元素，是空数组，size=0;
        size = 0;
    }
​
    //默认构造方法，初始化长度为10的数组
    public Array() {
        this(10);
    }
​
    //封装一个获取数组实际存放多少个元素的方法
    public int getSize() {
        return size;
    }
​
    //封装一个获取数组总共可以存放多少个元素的方法
    public int getCapacity() {
        return data.length;
    }
​
    //封装一个判断数组是否为空的方法
    public boolean isEmpty() {
        return size == 0;
    }
}

4 向数组中添加元素

a 向数组末尾添加元素：

前面，我们在自定义数组类的时候，指定了一个非常好用的成员变量，size，它不但表示当前数组中有几个元素，而且还指向数组中第一个元素为空的位置。比如，当size=3的时候，数组中，此时有3个元素，分别是data[0]，data[1]，data[2]，同时data[3]是空的，该索引位置处没有元素。当我们此时，向数组中添加元素的时候，我们就应该把新元素放到data[3]的位置。所以，我们可以定义一个向数组末尾添加元素的方法：

public void addLast(int e){
  //如果数组的实际存放元素个数==数组长度，抛出异常
  if( size == data.length){
    throw new IllegalArgumentException("addLast failed.Array is full");
  }
  //否则，将元素e插入到size位置处，同时，size++；
  data[size] = e;
  size++;
}
b 向任意位置添加元素：
public void add(int e,int index){
  //判断数组是否满
  if(size==data.length){
    throw new IllegalArgumentException("数组满,add failed.");
  }
  //判断插入位置index是否合法
  if(index<0||index>=data.length){
    throw new IllegalArgumentException("插入位置不合法");
  }
 
  //如果插入位置在index取值范围在[0,size]之间，意味着插入位置合法。
  //则先将[index,size-1]位置处的元素全部后移一位
  if(index<=size){
    for(int i=size;i>index;i--){
      data[size]=data[size-1];
    }
    //然后空出index位置，将元素e插入到index位置处,并且size++
    //其实，此时i=index,只是离开了变量作用域
    data[index]=e;
    size++;
  }else{
    //插入位置在[size+1,length-1],也认为是插入位置不合法，或者此时直接将元素放到size位置处
    data[size]=e;
    size++;
  }
}
c 向数组首位置插入元素

有了向数组任意位置插入元素的add(int e,int index)的方法，则可以借用此方法，实现一个向数组首位置插入元素的方法，只需要传入一个位置参数0即可，add(int e,0)

public void addFirst(int e){
  add(e,0);
}
d 改造向数组末尾添加元素

同时，我们也可以借助add(int e,int index)任意位置插入元素的方法，进而改造。只需，传入位置参数size即可，addLast(int e,size)






e 覆写父类Object的toString()





Java中，任何基本数据类型在打印输出时，编译器会自动将其转化成字符串打印输出。而对于自定义类类型的实例变量，在打印输出时，就需要覆写Object类的toString()方法，否则打印出来的将是该实例变量的内存地址值。其格式大概是：类名@实例变量内存地址。因此，对于我们这个自定义的Array类，我们需要重写toString()。





@Override
public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append(String.format("Array size: %d,capacity = %d \n", size, data.length));
    stringBuilder.append("[");
    //注意，此时遍历的时候，只能到达size位置处，因为可能数组开辟了100个空间的capacity，但是，数组实际存放了size=10个元素
    for (int i = 0; i < size; i++) {
        stringBuilder.append(data[i]);
        //如果没有到达最后一个元素时，则添加一个"空格+,+空格"
        if (i != size-1) {
            stringBuilder.append(" , ");
        }
    }
    stringBuilder.append("]");
    return stringBuilder.toString();
}





f 测试addLast(int e)，add(int e,int index)和addFirst(int e)方法





有了toString()方法，我们就可以定义一个main()方法，来分别测试这几个方法。





public static void main(String[] args) {
    Array array = new Array(20);
    for (int i = 0; i < 10; i++) {
        array.addLast(i);
    }
    System.out.println(array);
    array.add(111, 1);     
    System.out.println(array);
    array.addFirst(-1);
    System.out.println(array);
}
//输出结果为
Array size: 10,capacity = 20 
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20 
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]





5 按元素值查找并返回索引下标





//从数组中查找值等于e的元素，如果找到返回其索引位置，未找到，返回-1
 public int find(int e) {
     for (int i = 0; i < size; i++) {
         if (e == data[i]) {
             return i;
         }
     }
     return -1;
 }





6 按元素值修改元素





//如果数组中存在元素值等于e的元素，则修改它的值为newValue，否则不做任何操作
// 修改数组中元素值等于e的元素为newValue,如果
public void modify(int e, int newValue) {
    int temp = find(e);
    if (temp != -1) {
        data[temp] = newValue;
    }
}





7 测试按元素值查找和修改元素





public static void main(String[] args) {
    Array array = new Array(20);
    for (int i = 0; i < 10; i++) {
        array.addLast(i);
    }
    System.out.println(array);
    array.add(111, 1);
    System.out.println(array);
    array.addFirst(-1);
    System.out.println(array);
    System.out.println("The index of element 1 is:"+array.find(1));
    System.out.println("The index of element 18 is:"+array.find(18));
    array.modify(9, 999);
    System.out.println("After modify element 9 to 999:");
    System.out.println(array);
}
//结果
Array size: 10,capacity = 20 
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20 
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
The index of element 1 is:3
The index of element 18 is:-1
After modify element 9 to 999:
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]





8 按索引下标查找、修改元素





//获取索引位置为index的元素
public int get(int index) {
    //如果index<0，或者数组不为空时，index>=size
    if (index < 0 || (isEmpty() && index >= size)) {
        throw new IllegalArgumentException("get failed,index is invalid.");
    }
    //否则的话，返回该元素
    return data[index];
}

//获取第一个位置元素
public int getFirst(){
  return get(0);
}

//获取最后一个位置元素
public int getLast(){
  return get(size-1);
}

//修改索引位置为index的元素
public void set(int index,int e) {
    //如果index<0，或者数组不为空时，index>=size
    if (index < 0 || (isEmpty() && index >= size)) {
        throw new IllegalArgumentException("get failed,index is invalid.");
    }
    //否则的话，直接修改元素
    data[index] = e;
}





测试：





public static void main(String[] args) {
    Array array = new Array(20);
    System.out.println(array.get(0));
    for (int i = 0; i < 10; i++) {
        array.addLast(i);
    }
    System.out.println(array);
    array.add(111, 1);
    System.out.println(array);
    array.addFirst(-1);
    System.out.println(array);
    System.out.println("The index of element 1 is:"+array.find(1));
    System.out.println("The index of element 18 is:"+array.find(18));
    array.modify(9, 999);
    System.out.println("After modify element 9 to 999:");
    System.out.println(array);
  //测试修改索引下标为3的元素为333
    array.set(3, 333);
    System.out.println(array);
}
//输出
Array size: 10,capacity = 20 
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20 
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
The index of element 1 is:3
The index of element 18 is:-1
After modify element 9 to 999:
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]
Array size: 12,capacity = 20 
[-1 , 0 , 111 , 333 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]
//不注释System.out.println(array.get(0));的话， 按预期的抛出异常：
Exception in thread "main" java.lang.IllegalArgumentException: get failed,index is invalid.
  at Array.get(Array.java:100)
  at Array.main(Array.java:135)  





9 判断数组中是否包含元素e





// 判断数组中是否包含元素e
public boolean contains(int e){
  for(int i=0;i<size;i++){
    if(data[i]==e){
      return true;
    }
  }
  return false;
}





10 按索引下标删除数组中的元素并返回





public int remove(int index){
  if(index<0||index>=size){
    throw new IllegalArgumentException("remove failed.index is invalid");
  }
  //删除之前，把data[index]放入临时变量，删除之后，再返回临时变量
  int temp=data[index];
  for(int i=index;i+1<size;i++){
    data[i]=data[i+1];
  }
  size--;
  return temp;
}
​
//同理，参照add()方法，有addFist()和addLast(),可以有removeFirst(),removeLast()方法
//删除第1个元素并返回
public int removeFirst() {
    return remove(0);
}
//删除最后1个位置元素并返回
public int removeLast() {
    return remove(size - 1);
}





11 按元素值删除数组中的元素





借助前面定义的查找方法find()，按索引下标删除的方法remove()，是否包含元素的方法contains()，可以实现删除特定元素的方法，以及删除数组中所有的特定元素。





//删除指定元素e
public void removeElement(int e) {
    int index = find(e);
    if (index != -1) {
        remove(index);
    }
}
​
//删除所有的指定元素e
public void removeAllElement(int e) {
  //如果数组中包含特定元素，就一直删
    while (contains(e)) {
      //删除哪个元素呢？删除特定索引位置的元素，这个特定索引位置通过find()方法得到
        remove(find(e));
    }
}





12小结





我们通过自己动手写了一个数组类，并添加了增删改查的方法。这个数组还有一些局限性，比如不能支持任意类型的数据，长度不支持动态扩展。下一篇文章中着手将这个数组改写为支持泛型的数组。



				 Post Views: 3,186
			
	


	










			

				
您可能也喜欢


				
					

						
						
选择排序算法

						2021年3月5日
					


				
					

						
						
线性查找算法

						2021年3月3日
					


				
					

						
						
插入排序算法

						2021年3月11日