思维导图
什么是数组：
在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。(维基百科)
从以上概念可以看到数组具有：线性的、索引值、元素、长度等特点，我们也可以思维扩散一下，数组应该可以CRUD（增删改查）元素，也可以更改数组长度（所占内存大小）。
怎么使用JAVA自定义一个数组：
代码实现步骤：
•int型数组
public class Array {
private int[] array;
private int size;//数组元素个数,也可代表数组当前索引
/**
* 无参时初始数组容量为10
*/
public Array() {
this(10);
}
/**
* 数组容量为capaCity
*
* @param capaCity
*/
public Array(int capaCity) {
this.array = new int[capaCity];
}
//获取数组中的元素个数
public int size() {
return size;
}
//获取数组的容量
public int getCapaCity() {
return array.length;
}
//判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
//在指定位置增加元素
public void add(int index, int e) {
//数组元素是否已满
if (size == array.length) {
throw new IllegalArgumentException("Add faild,Array is null");
}
//参数越界(不能为负数，也不能大于size，因为数组元素是连续的，不能跳过空位置插入)
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
}
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = e;
size++;
}
//在最后一个位置增加元素
public void addLast(int e) {
add(size, e);
}
//在第一个位置增加元素
public void addFirst(int e) {
add(0, e);
}
//获得index位置的元素
public int get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed,Index is illegal");
}
return array[index];
}
//修改index位置的元素
public int set(int index,int e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Set failed,Index is illegal");
}
return array[index] = e;
}
//查找数组中含有e元素的索引，没有该元素返回-1
public int find(int e){
for (int i = 0; i < size; i++) {
if(e == array[i]){
return i;
}
}
return -1;
}
//查看是否含有指定元素
public boolean contains(int e){
for (int i = 0; i < size; i++) {
if(array[i] == e){
return true;
}
}
return false;
}
//删除指定位置的元素,返回删除的元素
public int remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
}
int ret = array[index];
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
return ret;
}
//删除第一个位置的元素,返回删除的元素
public int removeFirst() {
return remove(0);
}
//删除最后一个位置的元素,返回删除的元素
public int removeLast() {
return remove(size - 1);
}
//删除数组中含有的元素
public void removeElement(int e) {
int index = find(e);
if(index!=-1){
remove(index);
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array size = %d ,capacity = %d\n",size,array.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(array[i]);
if(i != size - 1){
res.append(',');
}
}
res.append(']');
return res.toString();
}
此时数组仅仅局限于Int型，而我们JAVA语言支持泛型的概念
•泛型型数组
public class GenericsArray<E> {
private E[] array;
private int size;//数组元素个数,也可代表数组当前索引
/**
* 无参时初始数组容量为10
*/
public GenericsArray() {
this(10);
}
/**
* 数组容量为capaCity
*
* @param capaCity
*/
public GenericsArray(int capaCity) {
this.array = (E[])new Object[capaCity];
}
//获取数组中的元素个数
public int size() {
return size;
}
//获取数组的容量
public int getCapaCity() {
return array.length;
}
//判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
//在指定位置增加元素
public void add(int index, E e) {
//数组元素是否已满
if (size == array.length) {
throw new IllegalArgumentException("Add faild,Array is null");
}
//参数越界
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
}
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = e;
size++;
}
//在最后一个位置增加元素
public void addLast(E e) {
add(size, e);
}
//在第一个位置增加元素
public void addFirst(E e) {
add(0, e);
}
//获得index位置的元素
public E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed,Index is illegal");
}
return array[index];
}
//修改index位置的元素
public E set(int index,E e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Set failed,Index is illegal");
}
return array[index] = e;
}
//查找数组中含有e元素的索引，没有该元素返回-1
public int find(E e){
for (int i = 0; i < size; i++) {
if(e.equals(array[i])){
return i;
}
}
return -1;
}
//查看是否含有指定元素
public boolean contains(E e){
for (int i = 0; i < size; i++) {
if(e.equals(array[i])){
return true;
}
}
return false;
}
//删除指定位置的元素,返回删除的元素
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
}
E ret = array[index];
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
return ret;
}
//删除第一个位置的元素,返回删除的元素
public E removeFirst() {
return remove(0);
}
//删除最后一个位置的元素,返回删除的元素
public E removeLast() {
return remove(size - 1);
}
//删除数组中含有的元素
public void removeElement(E e) {
int index = find(e);
if(index != -1){
remove(index);
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Array size = %d ,capacity = %d\n",size,array.length));
stringBuilder.append('[');
for (int i = 0; i < size; i++) {
stringBuilder.append(array[i]);
if(i != size - 1){
stringBuilder.append(',');
}
}
stringBuilder.append(']');
return stringBuilder.toString();
}
}
此时数组一旦初始化容量就固定了，那怎么使数组成为动态的呢？
•动态数组
我们只需要改动一点点代码：
新增一个方法
//将数组指向一个新的数组（新数组长度取决于参数）
private void resize(int newCapacity) {
E[] newArray = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[i];
}
array = newArray;
}
再将部分代码改动一下
//在指定位置增加元素
public void add(int index, E e) {
//数组元素已满将旧数组指向一个新数组（容量为旧数组2倍）
if (size == array.length) {
resize(2 * array.length);
}
//参数越界
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
}
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = e;
size++;
}
//删除指定位置的元素,返回删除的元素
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
}
E ret = array[index];
for (int i = index + 1; i < size; i++) {
array[i - 1] = array[i];
}
size--;
//如果数组元素个数为容量的四分之一（考虑到复杂度震荡）
//将该数组指向一个新的数组（容量为旧数组一半）
if (size == array.length / 4 && array.length / 2 != 0) {
resize(array.length / 2);
}
return ret;
}
时间复杂度：
•添加操作：
•删除操作：
•修改操作：
•查询操作：
•总结：
OK,大功告成!!!
网友评论