不要小瞧数组
目录
-
Java自定义数组（包含了增删改查，数据结构底层实现）
package com.suanfa.array;
/**
* 自定义数组
* @author Administrator
*
*/
public class AutoArray {
private int[] data;
private int size;//索引初始值为0
public AutoArray(int capacity){
data=new int[capacity];
size=0;
}
public AutoArray(){
this(10);//如果没有指定长度，默认为10
}
public int[] getData() {
return data;
}
public void setData(int[] data) {
this.data = data;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public boolean isEmpty(){
return size==data.length;
}
//--------------------------------------------
/**
* 向数组中指定位置插入数据
* @param index
* @param e
*/
public void add(int index,int e){
if(index == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");
if(index < 0 || index >size)
throw new IllegalArgumentException("Add failed. Array is full.");
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];//指定位置的后面所有元素依次后移
}
data[index]=e;
size++;
}
/**
* 向数组开头添加元素
* @param e
*/
public void addFirst(int e){
add(0,e);
}
/**
* 向数组末尾添加元素
* @param e
*/
public void addLast(int e){
add(size,e);
}
/**
* 获取指定索引位置的元素
* @param index
* @return
*/
public int get(int index){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
/**
* 修改指定位置的元素
* @param index
*/
public void setIndex(int index,int e){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
data[index]=e;
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append(String.format("Array:size=%d,capacity=%d\n", size,data.length));
res.append("[");
for(int i=0;i<size;i++){
res.append(data[i]);
if(i!=size-1)
res.append(", ");
}
res.append("]");
return res.toString();
}
/**
* 判断数组中是否包含某元素
* @param e
* @return
*/
public boolean contains(int e){
for(int i=0;i<size;i++){
if(data[i]==e)
return true;
}
return false;
}
/**
* 查看元素的索引位置（最靠前的元素位置），如果没有返回-1，扩展（查询数组中所有e元素的位置集合）
* @param e
* @return
*/
public int findEleIndex(int e){
for(int i=0;i<size;i++){
if(data[i]==e)
return i;
}
return -1;
}
/**
* 删除指定位置的元素，并返回所删除的元素
* @param index
* @return
*/
public int remove(int index){
if(index<0 || index>=size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
int ret=data[index];
for(int i=index+1;i<size;i++){
data[i-1]=data[i];//从索引位置开始，后面的元素依次往前移动（覆盖），
}
size--;//维护索引，虽然现在size指定的位置有元素，但当下次插入时就会覆盖掉，并且也不能直接访问size位置的元素
return ret;
}
/**
* 删除数组第一个元素
* @return
*/
public int removeFirst(){
return remove(0);
}
/**
* 删除数组最后一个元素
* @return
*/
public int removeLast(){
return remove(size-1);
}
/**
* 删除数组中指定元素e，只删除了最靠前的一个，扩展（删除数组中所有的e元素）
* @param e
*/
public void removeEle(int e){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
}
/**
* 删除数组中所有的元素e
* @param e
*/
public void removeEleAll(int e){
boolean res=true;
while(res){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
else
res=false;
}
}
}
-
自定义泛型数组
package com.suanfa.array;
/**
* 自定义泛型数组
* @author Administrator
*
*/
public class FunXingArray<E> {
private E[] data;
private int size;//索引初始值为0
public FunXingArray(int capacity){
data=(E[])new Object[capacity];//java不支持直接创建泛型对象，必须进行类型强转
size=0;
}
public FunXingArray(){
this(10);//如果没有指定长度，默认为10
}
public E[] getData() {
return data;
}
public void setData(E[] data) {
this.data = data;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public boolean isEmpty(){
return size==data.length;
}
//--------------------------------------------
/**
* 向数组中指定位置插入数据
* @param index
* @param e
*/
public void add(int index,E e){
if(index == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");
if(index < 0 || index >size)
throw new IllegalArgumentException("Add failed. Array is full.");
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];//指定位置的后面所有元素依次后移
}
data[index]=e;
size++;
}
/**
* 向数组开头添加元素
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 向数组末尾添加元素
* @param e
*/
public void addLast(E e){
add(size,e);
}
/**
* 获取指定索引位置的元素
* @param index
* @return
*/
public E get(int index){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
/**
* 修改指定位置的元素
* @param index
*/
public void setIndex(int index,E e){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
data[index]=e;
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append(String.format("Array:size=%d,capacity=%d\n", size,data.length));
res.append("[");
for(int i=0;i<size;i++){
res.append(data[i]);
if(i!=size-1)
res.append(", ");
}
res.append("]");
return res.toString();
}
/**
* 判断数组中是否包含某元素
* @param e
* @return
*/
public boolean contains(E e){
for(int i=0;i<size;i++){
if(data[i].equals(e))
return true;
}
return false;
}
/**
* 查看元素的索引位置（最靠前的元素位置），如果没有返回-1，扩展（查询数组中所有e元素的位置集合）
* @param e
* @return
*/
public int findEleIndex(E e){
for(int i=0;i<size;i++){
if(data[i].equals(e))
return i;
}
return -1;
}
/**
* 删除指定位置的元素，并返回所删除的元素
* @param index
* @return
*/
public E remove(int index){
if(index<0 || index>=size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret=data[index];
for(int i=index+1;i<size;i++){
data[i-1]=data[i];//从索引位置开始，后面的元素依次往前移动（覆盖），
}
size--;//维护索引，虽然现在size指定的位置有元素，但当下次插入时就会覆盖掉，并且也不能直接访问size位置的元素
return ret;
}
/**
* 删除数组第一个元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 删除数组最后一个元素
* @return
*/
public E removeLast(){
return remove(size-1);
}
/**
* 删除数组中指定元素e，只删除了最靠前的一个，扩展（删除数组中所有的e元素）
* @param e
*/
public void removeEle(E e){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
}
/**
* 删除数组中所有的元素e
* @param e
*/
public void removeEleAll(E e){
boolean res=true;
while(res){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
else
res=false;
}
}
}
-
实现自定义动态泛型数组
package com.suanfa.array;
/**
* 动态自定义泛型数组
* @author Administrator
*
*/
public class DongTaifFunXingArray<E> {
private E[] data;
private int size;//索引初始值为0
public DongTaifFunXingArray(int capacity){
data=(E[])new Object[capacity];//java不支持直接创建泛型对象，必须进行类型强转
size=0;
}
public DongTaifFunXingArray(){
this(10);//如果没有指定长度，默认为10
}
public E[] getData() {
return data;
}
public void setData(E[] data) {
this.data = data;
}
public int getSize() {
return size;
}
public int getCapacity(){
return data.length;
}
public void setSize(int size) {
this.size = size;
}
public boolean isEmpty(){
return size==data.length;
}
//--------------------------------------------
private void createNewArray(Integer newcapacity){
//新建数组，容积为原来的两倍
E[]newdata=(E[])new Object[newcapacity];
//把原来数组中的元素转移到新数组中
for(int i=0;i<size;i++){
newdata[i]=data[i];
}
//把数组引用指向新的数组
data=newdata;
}
/**
* 向数组中指定位置插入数据
* @param index
* @param e
*/
public void add(int index,E e){
if(index < 0 || index >size)
throw new IllegalArgumentException("Add failed. Array is full.");
if(index == data.length){
createNewArray(2*data.length);//当数组空间不够用时，去新建一个新数组，容量为原来的两倍
}
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];//指定位置的后面所有元素依次后移
}
data[index]=e;
size++;
}
/**
* 向数组开头添加元素
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 向数组末尾添加元素
* @param e
*/
public void addLast(E e){
add(size,e);
}
/**
* 获取指定索引位置的元素
* @param index
* @return
*/
public E get(int index){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size-1);
}
/**
* 修改指定位置的元素
* @param index
*/
public void setIndex(int index,E e){
if(index<0 || index>=size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
data[index]=e;
}
@Override
public String toString(){
StringBuilder res=new StringBuilder();
res.append(String.format("Array:size=%d,capacity=%d\n", size,data.length));
res.append("[");
for(int i=0;i<size;i++){
res.append(data[i]);
if(i!=size-1)
res.append(", ");
}
res.append("]");
return res.toString();
}
/**
* 判断数组中是否包含某元素
* @param e
* @return
*/
public boolean contains(E e){
for(int i=0;i<size;i++){
if(data[i].equals(e))
return true;
}
return false;
}
/**
* 查看元素的索引位置（最靠前的元素位置），如果没有返回-1，扩展（查询数组中所有e元素的位置集合）
* @param e
* @return
*/
public int findEleIndex(E e){
for(int i=0;i<size;i++){
if(data[i].equals(e))
return i;
}
return -1;
}
/**
* 删除指定位置的元素，并返回所删除的元素
* @param index
* @return
*/
public E remove(int index){
if(index<0 || index>=size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret=data[index];
for(int i=index+1;i<size;i++){
data[i-1]=data[i];//从索引位置开始，后面的元素依次往前移动（覆盖），
}
size--;//维护索引，虽然现在size指定的位置有元素，但当下次插入时就会覆盖掉，并且也不能直接访问size位置的元素
data[size]=null;
//当数组中的元素是数组容量的一半时进行缩容
if(size == data.length/4 && data.length/2 != 0)//解决复杂度震荡，同时不能新建一个长度为0的数组
createNewArray(data.length/2);
return ret;
}
/**
* 删除数组第一个元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 删除数组最后一个元素
* @return
*/
public E removeLast(){
return remove(size-1);
}
/**
* 删除数组中指定元素e，只删除了最靠前的一个，扩展（删除数组中所有的e元素）
* @param e
*/
public void removeEle(E e){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
}
/**
* 删除数组中所有的元素e
* @param e
*/
public void removeEleAll(E e){
boolean res=true;
while(res){
int index=findEleIndex(e);
if(index!=-1)
remove(index);
else
res=false;
}
}
}