2345网址大全的网址,百度推广优化中心,河北盛通公路建设有限公司网站,济南网页制作设计上一篇文章学习了#xff1a;最好、最坏、平均、均摊时间复杂度的计算与分析方法.本片文章学习数组这种结构。由于数组这种结构比较简单#xff0c;本文直接简单介绍#xff0c;然后给出两种实现数组类的Java代码:整形数组类与通用性的数组类 由于数组是相比于其他数据结构实… 上一篇文章学习了最好、最坏、平均、均摊时间复杂度的计算与分析方法.本片文章学习数组这种结构。由于数组这种结构比较简单本文直接简单介绍然后给出两种实现数组类的Java代码:整形数组类与通用性的数组类 由于数组是相比于其他数据结构实在太简单这里我们只做简单的介绍然后直接给出实现的代码。 文章目录1 数组的概念1.1 Java中数组的越界访问2 整形数组类的实现3 通用型数组类的实现4 总结 1 数组的概念
数组Array是一种线性表数据结构。它用一组连续的内存空来存储一组具有相同类型的数据。对于线性表和非线性表这里不再多说。
我们要注意数组它是连续的内存空间和相同的数据类型。
还有一点就是我们要明白数组是如何做到根据下标来访问数组的元素的。我们拿一个长度为10的int类型的数组int[] anew 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(; i3; 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.datanew int[capacity];this.lencapacity;this.cnt0;//一开始一个数据都诶呦所以为0}//根据索引找到数组中的元素并返回public int find(int index) {if(index0 || indexlen)return -1;return data[index];}//插入元素包括头部插入尾部插入中间插入public boolean insert(int index, int value) {//数组空间已满if(cntlen) {System.out.println(数组空间已满无法插入);return false;}//插入位置不合法if(index0 || indexlen) {System.out.println(插入位置不合法!);return false;}//位置合法for(int icnt;iindex;--i) {data[i]data[i-1];}data[index]value;cnt;return true;}//根据索引删除数组中的元素public boolean delete(int index) {if(index0 || indexlen)return false;//从删除的位置开始将后面的元素向前移动一位for(int iindex1;ilen;i) {data[i-1]data[i];}--cnt;return true;}public void printAll() {for(int i0;ilen;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 GenericArrayT{private T[] data;private int size;//构造函数public GenericArray(int capacity) {data (T[])new Object[capacity];size0;}//无参构造方法默认数组容量为10public GenericArray() {this(10);}//获取数组容量public int getCapacity() {return data.length;}//获取当前元素个数public int count() {return size;}//判断数组是否为空public boolean isEmpty() {return size0;}//修改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 i0;ithis.size;i) {if(data[i].equals(e))return true;}return false;}//获取对应元素的下标未找到则返回-1public int find(T e) {for(int i0;ithis.size;i) {if(data[i].equals(e))return i;}return -1;}//在index位置插入元素e时间复杂度是Omnpublic void add(int index, T e) {checkIndex(index);//如果当前元素的个数等于数组的容量则将数组扩容为原来的两倍if(sizedata.length) {resize(2*data.length);}for(int isize-1;iindex;--i) {data[i1]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 iindex1;isize;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 indexfind(e);if(index!-1) {remove(index);}}Overridepublic 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 stubif(index 0 || index size) {throw new IllegalArgumentException(remove failed! Require index 0 and index size.);}}//扩容方法时间复杂度Onprivate void resize(int capacity) {// TODO Auto-generated method stubT[] newData (T[])new Object[capacity];for(int i0;isize;i) {newData[i]data[i];}datanewData;}private void checkIndex(int index) {// TODO Auto-generated method stubif(index0 || indexsize) {throw new IllegalArgumentException(Add failed! Require index 0 and index size.);}}//测试用的main你可以自己写测试函数public static void main(String args[]) {GenericArrayInteger a new GenericArrayInteger(5);a.add(0, 2);a.add(1, 4);a.add(2, 3);a.add(3, 7);a.add(4, 9);for(int i0;ia.size;i) {System.out.print(a.get(i) );}System.out.println();a.remove(1);for(int i0;ia.size;i) {System.out.print(a.get(i) );}a.addFirst(23);System.out.println();for(int i0;ia.size;i) {System.out.print(a.get(i) );}a.addLast(24);System.out.println();for(int i0;ia.size;i) {System.out.print(a.get(i) );}}
}上述代码在eclipse中运行结果如下 4 总结
注意数组的插入删除的效率以及越界访问 学习交流加 个人qq 1126137994个人微信 liu1126137994学习交流资源分享qq群 962535112
