动态数组的实现_JAVA_编程开发_程序员俱乐部

class="MsoNormal">用到的知识:

1.泛型

?

public class ArrayQueue<E> {}//E表示元素是什么类型,element

2.容量(arr.length)

private int initVolume;

3.增长比率

?

private int GrowthRate;

4.数组长度

?

?

private int length=0;

目的:用动态数组实现增加元素,插入元素,移除元素,修改元素等操作

Object[] src=new Object[0];

add思路:在已知数组最末尾增加元素,先建立新的数组,并初始化容量为旧数组+1,将旧数组拷贝到新数组,新元素增加到末尾,用新数组替换旧数组

实现:

public void add(E s){
		//定义一个新数组，用来装数据,长度比src+1
		Object []dest =new Object[src.length+1];
		//将新加进的元素放入新数组的最后一个下标位置
		dest[dest.length-1]=s;
		//将原来数组中的数据按照下标顺序拷贝到新数组
		for(int i=0;i<src.length;i++){
			dest[i] = src[i];
		}
		
		//将src指向新数组
		src = dest;
}

?insert思路:和add类似,将旧数组分为两个部分,一部分拷贝到新数组,将插入的元素放到指定位置,再拷贝剩余部分到新数组

实现:

/**
	 * 将指定元素插入到指定位置
	 * @param index 要插入元素的位置,第index个元素
	 * @param s 要插入的新元素
	 */
	public void insert(int index, E s) {
		//定义一个新数组，用来装数据,长度比src+1
				Object []dest =new Object[src.length+1];
				
				if(index>=0&&index<dest.length){
				//将原来数组中的数据按照下标顺序拷贝到新数组
				for(int i=0;i<index;i++){
					dest[i] = src[i];
				}
				for(int i=index;i<src.length;i++){
					dest[i+1] = src[i];
				}
				//将新加进的元素放入新数组的相应位置
				dest[index]=s;
				
				//将src指向新数组
				src = dest;
				}
				
				else{
					System.out.println("插入操作指定下标超出范围,请插入元素到0-"+(src.length-1)+"的位置");
				}
	}

?

移除操作:思路和插入差不多

/**
	 * 移除指定位置的元素
	 * @param index
	 *            要移除的元素的下标,0-src.length-1;
	 */
	public void remove(int index) {
		//定义一个新数组，用来装数据,长度比src+1
		Object []dest =new Object[src.length-1];
		
		if(index>=0&&index<dest.length){
		//将原来数组中的数据按照下标顺序拷贝到新数组
		for(int i=0;i<index;i++){
			dest[i] = src[i];
		}
		for(int i=index;i<src.length-1;i++){
			dest[i] = src[i+1];
		}		
		//将src指向新数组
		src = dest;
		}
		else{
			System.out.println("caozuo.html" target="_blank">删除操作指定下标超出范围,请删除从0-"+(src.length-1)+"的元素");
		}
	}

?

上述程序每增加一个数据都得重新分配空间,改进后程序如下:

public class ArrayQueue<E> {//E表示元素是什么类型,element
	private int initVolume;
	private int GrowthRate;
	private int length=0;
	Object[] src;
	
	public ArrayQueue(){
		this.initVolume=900000;
		this.GrowthRate=10000;
		src=new Object[initVolume];
	}
	
	
	/**
	 * 将指定的元素加入容器
	 * @param s 要加入到容器中的元素
	 */
	public void add(E s){
		if(length==src.length){
		
			Object []dest =new Object[src.length+GrowthRate];

			//将原来数组中的数据按照下标顺序拷贝到新数组
//			for(int i=0;i<src.length;i++){
//				dest[i] = src[i];
//			}
			System.arraycopy(src, 0, dest, 0, length);
			//将src指向新数组
			src = dest;
			
		}
		src[length]=s;
		length++;
		
	}
	
	/**
	 * 获取指定下标位置的元素
	 * 
	 * @param index
	 *            要获取的元素的下标
	 * @return 返回获取到的元素
	 */
	public E get(int index){
		return (E)src[index];
	}
	
	/**
	 * 修改指定位置元素的值
	 * 
	 * @param index要修改的元素位置
	 * @param s
	 *            修改后的新元素
	 */
	public void update(int index, E s) {
		if(index>=0&&index<size()){
		src[index]=s;
		}else{
			System.out.println("更新操作指定下标超出范围,请更新从0-"+(src.length-1)+"的元素");
		}
	}
	
	/**
	 * 将指定元素插入到指定位置
	 * @param index 要插入元素的位置,第index个元素
	 * @param s 要插入的新元素
	 */
	public void insert(int index, E s) {
		if(index>=0&&index<length){
			Object[] dest;
			if(length>=src.length-1){//即将超出范围就需要增加容量
			dest =new Object[src.length+GrowthRate];
			
			}else{
				dest =new Object[src.length];//至少还差一个超出范围,不需要增加容量
			}

				//将原来数组中的数据按照下标顺序拷贝到新数组
				System.arraycopy(src, 0, dest, 0, index);
				System.arraycopy(src, index, dest, index+1,src.length-index-1);
					
				//将src指向新数组
				src = dest;
			
			//将新加进的元素放入新数组的相应位置
			src[index]=s;
			length++;
				
	}
				
				else{
					System.out.println("插入操作指定下标超出范围,请插入元素到0-"+(src.length-1)+"的位置");
				}
	}
	
	/**
	 * 移除指定位置的元素
	 * 
	 * @param index
	 *            要移除的元素的下标,0-src.length-1;
	 */
	public void remove(int index) {
		if(index>=0&&index<length){
			Object[] dest;
			if(length>=src.length-1){//即将超出范围就需要增加容量
			dest =new Object[src.length+GrowthRate];
			
			}else{
				dest =new Object[src.length];//至少还差一个超出范围,不需要增加容量
			}

				//将原来数组中的数据按照下标顺序拷贝到新数组
				System.arraycopy(src, 0, dest, 0, index);
				System.arraycopy(src, index+1, dest, index,src.length-index-1);
					
				//将src指向新数组
				src = dest;

			length--;
				
	}
		else{
			System.out.println("删除操作指定下标超出范围,请删除从0-"+(src.length-1)+"的元素");
		}
	}

	/**
	 * 获得容器中元素个数的方法
	 * 
	 * @return 返回元素的个数
	 */
	public int size() {
		return length;
	}
}

?

public class Demo {
	public static void main(String args[]){
		ArrayQueue<String> queue =new ArrayQueue();

		long t1=System.currentTimeMillis();	
		for(int i=0;i<1000000;i++){
			queue.add(""+i);
		}

		
		long t2=System.currentTimeMillis();	
		for(int i=0;i<queue.size();i++){
			System.out.println(queue.get(i));	
		}
		
		System.out.println(t2-t1);
		/**测试不同容量.增长比率对时间的影响
		 * this.initVolume=900000;
		 *this.GrowthRate=10000;
		 *t2-t1=891
		 *this.initVolume=9000;
		 *this.GrowthRate=100;
		 *t2-t1=7792
		 */

	}
	
}

?