- 上一篇文章学习了：最好、最坏、平均、均摊时间复杂度的计算与分析方法.
- 本片文章学习数组这种结构。由于数组这种结构比较简单，本文直接简单介绍，然后给出两种实现数组类的Java代码:整形数组类与通用性的数组类
由于数组是相比于其他数据结构实在太简单，这里我们只做简单的介绍，然后直接给出实现的代码。
1 数组的概念
数组（Array）是一种线性表数据结构。它用一组连续的内存空，来存储一组具有相同类型的数据。对于线性表和非线性表这里不再多说。
我们要注意数组它是连续的内存空间和相同的数据类型。
还有一点就是我们要明白数组是如何做到根据下标来访问数组的元素的。我们拿一个长度为10的int类型的数组int[] a=new int[10];来说明。如下图是申请内存后数组元素的存储方式。
假设上述数组的起始地址为1000.当CPU要访问某一个数组的元素时，将会通过下面的公式进行访问元素：
a[i]_address = base_address + i * data_type_size
其中，base_address 为数组的起始地址。data_type_size为数组元素的类型的大小。
计算机就是通过上述的公式进行数组的随机访问的。不像链表等非线性结构，无法随机访问元素。
- 数组这种结构，虽然具有随机访问的高效性，但是它的插入和删除确实非常的低效。
- 以及数组的访问也是很容易越界的
以上插入和删除的低效，这里不再赘述。
我们注意一下数组访问的越界。
1.1 Java中数组的越界访问
在讲述Java中数组的越界访问之前，先来看一下C语言的越界访问。如下代码：
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
上述代码运行后，并非是打印3次hello world，而是无限次的打印hello world。这是为什么？
数组arr的大小是3，但是上面的for循环由于书写错误，访问了arr[3]，这就是越界访问。在C语言中，只要不是访问内存受限的地方，所有的内存都是可以访问的。所以由上面的数组访问的公式，a[3]也被定位到一块内存上，而这块内存中存储的刚好是局部变量i。那么arr[3]实际上就是i，这就导致此时又将i赋值为0。此时回到for循环发现i是0，继续循环。。。。。
数组越界在C语言中是一种未决行为，并没有规定数组越界访问时应该如何处理。因为数组访问的本质是访问一段连续的内存，只要数组通过偏移计算得到的内存是可用的，那么程序就可能不会报任何错误。C语言中这种行为，很难debug到错误。
但是不像c语言，Java语言不允许这种越界访问。Java编译器会做越界检查，如果有越界访问，将会抛出异常。如：java.lang.ArrayIndexOutOfBoundsException。
2 整形数组类的实现
由于数组比较简单，上面的内容我觉的就够了。下面直接给出int数组类的实现。可以直接在eclipse编译运行的代码。代码如下：
- Array.java
package Array;
/** * 1) 数组的插入、删除、按照下标随机访问操作； * 2）数组中的数据是int类型的； * */
public class Array {
//定义整形数据保存数据
public int data[];
//数组的长度
private int len;
//数组中的实际个数
private int cnt;
//构造方法，定义数组大小
public Array(int capacity) {
this.data=new int[capacity];
this.len=capacity;
this.cnt=0;//一开始一个数据都诶呦，所以为0
}
//根据索引找到数组中的元素并返回
public int find(int index) {
if(index<0 || index>=len)return -1;
return data[index];
}
//插入元素，包括头部插入，尾部插入，中间插入
public boolean insert(int index, int value) {
//数组空间已满
if(cnt==len) {
System.out.println("数组空间已满，无法插入！");
return false;
}
//插入位置不合法
if(index<0 || index>=len) {
System.out.println("插入位置不合法!");
return false;
}
//位置合法
for(int i=cnt;i>index;--i) {
data[i]=data[i-1];
}
data[index]=value;
++cnt;
return true;
}
//根据索引，删除数组中的元素
public boolean delete(int index) {
if(index<0 || index>=len)return false;
//从删除的位置开始，将后面的元素向前移动一位
for(int i=index+1;i<len;i++) {
data[i-1]=data[i];
}
--cnt;
return true;
}
public void printAll() {
for(int i=0;i<len;i++) {
System.out.print(data[i]+" ");
}
System.out.println();
}
public static void main(String args[]) {
Array array = new Array(5);
array.printAll();
array.insert(0,3);
array.insert(0, 4);
array.insert(1, 5);
array.insert(2, 2);
array.insert(3, 6);
array.insert(4, 8);
array.printAll();
}
}
- 运行结果如下：
以上代码只实现了数组类的插入和删除。更多的方法在下面的通用性数组的实现里面。
3 通用型数组类的实现
下面是实现通用的数组类，也就是大家所知的泛型。C++中叫做模板。
下面的代码已经经过测试，是可以正常使用的。如果你发现有其他bug，请在下方留言评论。
代码如下：
- GenericArray.java
package Array;//这个可能你的不一样
public class GenericArray<T>{
private T[] data;
private int size;
//构造函数
public GenericArray(int capacity) {
data = (T[])new Object[capacity];
size=0;
}
//无参构造方法，默认数组容量为10
public GenericArray() {
this(10);
}
//获取数组容量
public int getCapacity() {
return data.length;
}
//获取当前元素个数
public int count() {
return size;
}
//判断数组是否为空
public boolean isEmpty() {
return size==0;
}
//修改index位置的元素
public void set(int index, T e) {
checkIndex(index);
data[index]=e;
}
//获取对应index位置的元素
public T get(int index) {
checkIndex(index);
return data[index];
}
//查看数组是否包含元素
public boolean contains(T e) {
for(int i=0;i<this.size;++i) {
if(data[i].equals(e))
return true;
}
return false;
}
//获取对应元素的下标，未找到则返回-1
public int find(T e) {
for(int i=0;i<this.size;++i) {
if(data[i].equals(e))
return i;
}
return -1;
}
//在index位置插入元素e，时间复杂度是O（m+n）
public void add(int index, T e) {
checkIndex(index);
//如果当前元素的个数等于数组的容量，则将数组扩容为原来的两倍
if(size==data.length) {
resize(2*data.length);
}
for(int i=size-1;i>=index;--i) {
data[i+1]=data[i];
}
data[index]=e;
size++;
}
//向数组头插入元素
public void addFirst(T e) {
add(0, e);
}
//向数组尾插入元素
public void addLast(T e) {
add(size, e);
}
// 删除index位置的元素并返回
public T remove(int index) {
chaeckIndexForRemove(index);
T ret =data[index];
for(int i=index+1;i<size;++i) {
data[i-1]=data[i];
}
--size;
data[size]=null;
//缩小数组容量
if(size == (data.length/4) && (data.length/2)!=0) {
resize(data.length/2);
}
return ret;
}
//删除第一个元素
public T removeFirst() {
return remove(0);
}
//删除末尾元素
public T removeLast() {
return remove(size-1);
}
//从数组中删除指定的元素
public void removeElement(T e) {
int index=find(e);
if(index!=-1) {
remove(index);
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
builder.append('[');
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append(']');
return builder.toString();
}
private void chaeckIndexForRemove(int index) {
// TODO Auto-generated method stub
if(index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed! Require index >=0 and index < size.");
}
}
//扩容方法，时间复杂度O（n）
private void resize(int capacity) {
// TODO Auto-generated method stub
T[] newData= (T[])new Object[capacity];
for(int i=0;i<size;++i) {
newData[i]=data[i];
}
data=newData;
}
private void checkIndex(int index) {
// TODO Auto-generated method stub
if(index<0 || index>size) {
throw new IllegalArgumentException("Add failed! Require index >=0 and index <= size.");
}
}
//测试用的main，你可以自己写测试函数
public static void main(String args[]) {
GenericArray<Integer> a = new GenericArray<Integer>(5);
a.add(0, 2);
a.add(1, 4);
a.add(2, 3);
a.add(3, 7);
a.add(4, 9);
for(int i=0;i<a.size;++i) {
System.out.print(a.get(i)+" ");
}
System.out.println();
a.remove(1);
for(int i=0;i<a.size;++i) {
System.out.print(a.get(i)+" ");
}
a.addFirst(23);
System.out.println();
for(int i=0;i<a.size;++i) {
System.out.print(a.get(i)+" ");
}
a.addLast(24);
System.out.println();
for(int i=0;i<a.size;++i) {
System.out.print(a.get(i)+" ");
}
}
}
- 上述代码在eclipse中运行结果如下：
4 总结
- 注意数组的插入删除的效率以及越界访问
学习交流加
- 个人qq： 1126137994
- 个人微信： liu1126137994
- 学习交流资源分享qq群： 962535112
京公网安备 11010502036488号